Részletesen

Riemann hipotézise és az internet II


1977-ben R. Rivest, A. Shamir és L. Adleman tudósok egy RSA néven ismert nyilvános kulcsú kriptográfiai rendszert javasoltak. Ez a rendszer néhány alapvető ötletet használ a Számelméletből.

Noha az alkalmazott ötletek elemi, ez nem azt jelenti, hogy triviálisak. Valójában a minden idők egyik legnagyobb matematikusa, a német matematikus Gauss (1777-1855) létrehozta és fejlesztette az összeegyeztethetőség fogalmát, amely alapvető fontosságú a kulcsok kódolásában és dekódolásában az RSA rendszerben. A kongrugenciák és az ebből következő moduláris számtani elnevezésű fejlesztés nagyban hozzájárulnak a számelmélethez. Különösen az oszthatóság kérdése, mivel amikor szükség van az euklideszi divízió maradványaival való munkavégzésre, az összehangolások a megfelelő eszközök.

Gauss bemutatta a kongruencia fogalmát az 1801-ben megjelent „Disquisitiones Arithmeticae” című munkájának első fejezetében. Gauss, a kongruencia fogalmával egyidejűleg bevezette a „≡” jelölést is, amely a fogalom erőteljes technikává tette az algebrát és a számelméletet. Menjünk a meghatározásokhoz.

Két egész számot tekintünk az, b és n pozitív egész szám. ha n megosztott az - b, akkor ezt mondjuk az egybeesik a b modulo n, és írtunk azb (mod n).

Például:

37 ≡ 2 (mod 5), mert az 5 osztja a 37 - 2 = 35-et,

27 ≡ 3 (mod 4), mert a 4 osztja a 27 - 3 = 24-et,

7 ≡ 7 (mod 4), tehát 4 osztja a 7 - 7 = 0-t.

ezért azb (mod n) azt jelenti n megosztott az - b; tehát van egy egész szám k olyan, hogy az - b = kn az oszthatóság meghatározásával. Például, 37 ≡ 2 (5. mod) azt sugallja, hogy van k (= 7) olyan, hogy 37 - 2 = 35 = 7 • 5.

Az egész számok alapján az és n, a Division algoritmusból tudjuk, hogy vannak egész számok q és r hányados, illetve fennmaradó érték, azaz: az = qn + rahol 0 ≤ r < n; logó, az - r = qn, azaz n megosztott az - r. Ezért a kongruencia meghatározásával azr (mod n).

A többit r bármilyen értéket feltehet 0 és 0 között n - 1. Így arra következtethetünk, hogy minden egész az egybevágó modul n pontosan az egyik értékre 0, 1, 2,…, n - 1. A készlet {0, 1, 2,…, n - 1} egész szám m amelyek a modulos megosztások maradványai n, modul hulladék osztálynak hívják n. Ha javítunk n = 7, tehát a 7 modul pontosan 7 elemmel rendelkezik, nevezetesen: 0, 1, 2,…, 6. Ezért, az egész számtól függetlenül, a 7 modul egyetlen eleméhez tartozik.

Például 20-at a 6 képviseli a mod 7 maradékosztályban, mivel 206 (mod 7).

A kongruencia gondolata jelen van a mindennapi életünkben, ha úgy gondoljuk, hogy az órák a 12. óra modult jelölik, a hét napjait a 4. modul alapján mérjük, az év hónapjai a 12. modul mintáját követik.Mivel a kongruencia és az egyenlőség közötti sok hasonló tulajdonság miatt Gauss választotta a A megfelelő jel „≡” szimbóluma.

Vegye figyelembe azaz (mod n) és ha azb (mod n) majd baz(mod n). Az összeadási, szorzási és potencírozási műveletek a következők szerint viselkednek.

ha azb (mod n) és cd (mod n) majd:

az + c b + d (mod n),

az c b d (mod n),

azrbr (mod n).

A következő példában bemutatott módszer alapvető fontosságú a kulcskódolás és -kódolás kezelésében az RSA rendszerben. Ezenkívül nagyon érdekes példa a kongruenciák fogalmának alkalmazására.

A felosztás fennmaradó részének meghatározása az által n elegendő egész számot találni r olyan, hogy azr (mod n) ahol 0 r < n. Például a 3-os osztás többi részének meghatározására10 13-ra készítettünk 3-at10 majd ossza el 13-mal, ami nem könnyű. A kongruencia fogalma azonban nagyban megkönnyíti ezt az eljárást. Először megjegyezzük, hogy:

33 ≡ 1 (mod 13), ez könnyű!

Most mindent a kocka felemelésével kapunk

(33)3 ≡ (1)3 mod 13, azaz 39 ≡ 1 (13. módosítás).

Ha megszorozzuk a kongruencia mindkét oldalát 3-tal, akkor 3-tal kapjuk meg10 ≡ 3 (13. módosítás).

A mai számítógépek olyan kifinomult szintet értek el, hogy minden kriptográfiai rendszernek elég robusztusnak kell lennie ahhoz, hogy ellenálljon azoknak a támadásoknak, akik meg akarják tönkreteni ügyleteik biztonságát.

1975-ben W. Diffie és M. Hellman matematikusok egy teljesen új titkosítási rendszert javasoltak: a nyilvános kulcsú titkosítást. Ebben a kódoló módszerben két kulcsot használunk: egyet a kódoláshoz és egy a dekódoláshoz. Néhány speciális módszert fejlesztettek ki Diffie és Hellmann ötleteinek megvalósításához. Az alapértelmezettként továbbra is a legjobban támogatott módszer az RSA rendszer.

Szöveg kódolásához az RSA rendszer szerint szüksége van:

(1) nagy szám Namely két különálló unokatestvére terméke p és q, azaz N = p • q.

(2) egy egész szám éskódoló kulcsként ismert, amely kielégíti a következő tulajdonságokat: a legnagyobb közös osztó (MDC) között és és a termék (p - 1) (q - 1) 1, és az MDC között és és N szintén 1.

Szöveg dekódolásához az RSA rendszer szerint a következőkre van szükség:

(3) egy egész szám D, amely dekódolási kulcsként ismert, és amely teljesíti a feltételt:

E • D ≡ 1 (mod (p -1) (q -1)).

Megfigyeltük, hogy a és és D szimmetrikus, vagyis ha D a. dekódolási kulcs ésmajd és a. dekódolási kulcs D.

Kódoljuk az üzenetet NYILVÁNOS KULCS az RSA rendszer használatával N = 2537 és titkosítási kulcs és = 13. Először ezt megjegyezzük N = 43,59, ahol 43 és 59 prímszámok.

Így az MDC (13, (43 - 1) • (59 - 1)) = MDC (13, 42 • 58) = 1, mivel a 13 egész szám nem osztja a 42-et és az 58-at; MDC (13, 2537) = 1, mert a 13, 43 és 59 (2537 = 43 • 59) prímszámok. Most konvertáljuk a szöveget a betű-szám egyezési táblázat segítségével:

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

mint N = 2537 4 számjegyből áll, betűpárokba csomagoljuk a szöveget:

PU BL IC KE Y

és töltse ki az utolsó blokkot a betűvel C szerzés

<>

PU BL IC KE YC<>

.

A fenti átalakítási táblázat segítségével az 5 konvertált üzenetblokk a következő:

1520 0111 0802 1004 2402.

Hívjuk a B számjegyû blokkot. A következő lépés a mind a négy számjegyű blokk értékének kiszámítása a 13 exponenssel (mod 3127), vagyis ha a B mondatot úgy akarjuk meghatározni, hogy C = P13 (mod 2537).

Például, amikor az első blokkot kódoljuk, meg kell oldani a C ≡ 1520-ot13 r (mod 2537). Ezután a következőképpen járunk el:

<>

15202 = 2,310,400 = 910 • 2537 + 1730 ≡ 1730 (mod 2537);

<>

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

<>

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).

Így az 1520 kódolása 0095.

A többi üzenetblokkot ugyanúgy kódoljuk, vagyis mindegyik blokk négy számjegyből áll, amelyek a 13 teljesítményre emelkednek (mod 2537). Ezért a vevő megkapja a titkosított üzenetet:

0095 1648 1410 1299 0811.

Vegye figyelembe, hogy nem konvertálhatjuk ezt az üzenetet betűkké, mivel néhány blokk alkotóelem-szám meghaladja a 25-et. A következő oszlopban megtesszük az üzenetek dekódolásának módját az RSA rendszer szerint, és dekódoljuk az üzenetet ebből a példából.

Vissza az oszlopokhoz

<