Üksikasjalikult

Riemann'i hüpotees ja Internet II


1977. aastal pakkusid teadlased R. Rivest, A. Shamir ja L. Adleman välja avaliku võtme krüptosüsteemi nimega RSA. See süsteem kasutab arvuteooria mõned elementaarsed ideed.

Kuigi kasutatud ideed on elementaarsed, ei tähenda see, et need oleksid triviaalsed. Tõepoolest, kõigi aegade suurim matemaatik, Saksa matemaatik Gauss (1777-1855) lõi ja arendas kongruentsuste mõistet, mis on RSA süsteemi võtmete kodeerimisel ja dekodeerimisel põhiline. Kogumised ja sellest tulenev areng, mida nimetatakse modulaarseks aritmeetikaks, annavad numbriteooriale olulise panuse. Eelkõige jagatavuse küsimused, sest kui on vaja töötada eukleidilise jaotuse jäänustega, on sobivad vahendid kongruentsid.

Gauss tutvustas kongruentsuse mõistet oma 1801. aastal ilmunud töö “Disquisitiones Arithmeticae” esimeses peatükis. Gauss tutvustas samaaegselt kongruentsuse mõistega ka märget “≡”, mis tegi sellest kontseptsioonist võimsa tehnika nii algebras kui ka numbriteoorias. Läheme määratluste juurde.

Me arvestame kahte täisarvu , b ja ei positiivne täisarv. Kui ei jagama - b, siis me ütleme seda on ühtlane b moodul ei, ja me kirjutasime b (mod ei).

Näiteks:

37 ≡ 2 (mod 5), kuna 5 jagab 37 - 2 = 35,

27 ≡ 3 (mod 4), kuna 4 jagab 27 - 3 = 24,

7 ≡ 7 (mod 4), seega 4 jagab 7 - 7 = 0.

Seetõttu b (mod ei) tähendab seda ei jagama - b; seega on täisarv k selline, et - b = kn jagatavuse määratluse järgi. Näiteks tähendab 37 ≡ 2 (mod 5), et on olemas k (= 7) selliselt, et 37 - 2 = 35 = 7 • 5.

Arvestades täisarvu ja ei, jagamisalgoritmi järgi teame, et on olemas täisarvud mis ja r vastavalt jagatis ja ülejäänud, nii et: = millal + rkus 0 ≤ r < ei; varsti, - r = millal, st ei jagama - r. Seetõttu kongruentsuse määratluse järgi r (mod ei).

Ülejäänud r võib eeldada mis tahes väärtust vahemikus 0 kuni ei - 1. Seega järeldame, et iga täisarv on ühilduv moodul ei täpselt ühele väärtusest vahemikus 0, 1, 2,…, ei - 1. Komplekt {0, 1, 2,…, ei - 1} täisarvudest m mis on mooduljaotuste jäänused ei, nimetatakse mooduli jäätmeklassiks ei. Kui me parandame ei = 7, nii et moodulil 7 on täpselt 7 elementi, nimelt: 0, 1, 2,…, 6. Seega, olenemata täisarvust, on see mooduli 7 üksiku elemendi jaoks ühine.

Näiteks tähistab 20 mod 7 jääkide klassis 6, kuna 20 since 6 (mod 7).

Kongruentsuse idee on meie igapäevaelus olemas, kui arvame, et kellad tähistavad tunnimoodulit 12, nädalapäevad mõõdetakse moodulina 4, aasta kuud järgivad moodulit 12. Märkuse sarnasuse ja võrdõiguslikkuse paljude sarnaste omaduste tõttu valis Gauss Vastavuse signaali sümbol ≡.

Pange tähele (mod ei) ja kui b (mod ei) siis b(mod ei). Liitmise, korrutamise ja potentseerimise toimingud toimivad järgmiselt.

Kui b (mod ei) ja cd (mod ei) siis:

+ c b + d (mod ei),

c b d (mod ei),

rbr (mod ei).

Järgnevas näites esitatud meetod on võtmekodeerimise ja dekodeerimisega RSA süsteemis käitlemisel põhiline. Lisaks on see väga huvitav näide kongruentside mõiste rakendamisest.

Ülejäänud jaotuse kindlaksmääramiseks poolt ei piisab täisarvu leidmisest r selline, et r (mod ei) kus 0 r < ei. Näiteks ülejäänud osa jagamiseks 3-st10 13ks tegime 310 ja jagage see siis 13-ga, mis pole lihtne. Kuid kongruentsuse mõiste hõlbustab seda protseduuri oluliselt. Esiteks märgime, et:

33 ≡ 1 (mod 13), see on lihtne!

Nüüd, kui tõsta kõik kuubikuks, saame

(33)3 ≡ (1)3 mod 13 st 39 ≡ 1 (mod 13).

Kui korrutame kongruentsi mõlemad pooled 3-ga, siis saame 310 ≡ 3 (mod 13).

Tänapäeva arvutid on jõudnud nii keerukale tasemele, et iga krüptosüsteem peab olema piisavalt vastupidav, et vastu pidada nende inimeste rünnakutele, kes soovivad oma tehingute turvalisust rikkuda.

Aastal 1975 pakkusid matemaatikud W. Diffie ja M. Hellman välja täiesti uue krüptimissüsteemi: avaliku võtme krüptograafia. Selles koodermeetodis kasutatakse kahte võtit: üks kodeerimiseks ja teine ​​dekodeerimiseks. Diffie ja Hellmanni ideede rakendamiseks töötati välja mõned konkreetsed meetodid. Kõige rohkem toetatud meetod, mis vaikimisi jääb, on aga RSA süsteem.

Teksti kodeerimiseks vastavalt RSA süsteemile peate:

(1) suur arv Nmis on kahe erineva nõo saadus lk ja mis, st N = p • q.

(2) täisarv E, tuntud kui kodeerimisvõti, mis vastab järgmistele omadustele: suurim ühine jagaja (MDC) vahel E ja toode (lk - 1) (mis - 1) on 1 ja MDC vahel E ja N on ka 1.

Teksti dekodeerimiseks vastavalt RSA süsteemile peate:

(3) täisarv D, mida nimetatakse dekrüpteerimisvõtmeks ja mis vastab tingimusele:

E • D ≡ 1 (mod (lk -1) (mis -1)).

Me täheldasime, et suhe E ja D on sümmeetriline, st D on dekrüpteerimisvõti Esiis E on dekrüpteerimisvõti D.

Kodeerime sõnumi AVALIK VÕTM kasutades RSA süsteemi koos N = 2537 ja krüptimisvõti E = 13. Esiteks märgime seda N = 43,59, kus 43 ja 59 on algarvud.

Seega MDC (13, (43 - 1) • (59 - 1)) = MDC (13, 42 • 58) = 1, kuna täisarv 13 ei jaga 42 ega 58; MDC (13, 2537) = 1, kuna 13, 43 ja 59 (2537 = 43 • 59) on algarvud. Nüüd teisendame teksti, kasutades tähtede ja numbrite vastavuse tabelit:

A = 00, B = 01, C = 02, D = 03,…, X = 23, Y = 24, Z = 25.

Kuidas N = 2537 sisaldab 4 numbrit, pakime teksti tähtede paaridesse:

PU BL IC KE Y

ja täitke viimane plokk tähega C saamine

<>

PU BL IC KE YC<>

.

Ülaltoodud teisendustabelit kasutades on 5 teisendatud sõnumiplokki:

1520 0111 0802 1004 2402.

Kutsume B-numbrit B-numbriks. Järgmine samm on eksponendile 13 (mod 3127) tõstetud neljakohalise ploki väärtuse arvutamine, see tähendab, et antud ploki B korral peame C määrama nii, et C = P13 (mod 2537).

Näiteks esimese ploki kodeerimisel peame lahendama C ≡ 152013 r (mod 2537). Seejärel toimime järgmiselt:

<>

15202 = 2310 400 = 910 2537 + 1730 1730 (mod 2537);

<>

15204 = 17302 = 2 992 900 = 1179 • 2537 + 1777 ≡ 1777 (mod 2537);

<>

15208 = 17772 = 3 157 729 = 1244 • 2537 + 1701 - 1701 (mod 2537);

<>

152012 = 15208.• 15204 = 1701 • 1777 = 3.022.677 = 1191 • 2537 + 1110 =

<>

= 1110 (mod 2537);

152013 = 152012 • 1520 = 1110 • 1520 = 1 687 200 = 665 • 2537 + 95 = 95 (mod 2537).

Seega on 1520 kodeering 0095.

Muud sõnumiplokid kodeeritakse samal viisil, see tähendab, et iga plokk koosneb neljast numbrist, mis tõuseb võimsuseni 13 (mod 2537). Seetõttu saab vastuvõtja krüptitud teate:

0095 1648 1410 1299 0811.

Pange tähele, et me ei saa seda sõnumit tähtedeks teisendada, kuna mõned ploki koostisosade numbripaarid on suuremad kui 25. Järgmises veerus astume samme, et dekodeerida teateid vastavalt RSA süsteemile ja dekodeerida sõnum selle näite järgi.

Tagasi veergude juurde

<