Fő tartalom
Számítástudomány
Tantárgy/kurzus: Számítástudomány > 2. témakör
4. lecke: Modern kriptográfia- A számelmélet alaptétele
- Nyilvános kulcsú titkosítás – Mi az?
- A diszkrét logaritmus probléma
- Diffie-Hellman kulcs-csere
- RSA-titkosítás: 1. lépés
- RSA-titkosítás: 2. lépés
- RSA-titkosítás: 3. lépés
- Komplexitás időfüggvénye (szemléltetés)
- Euler-féle Φ függvény
- Euler-féle Φ függvényértékek szemléltetése
- RSA-titkosítás: 4. lépés
© 2023 Khan AcademyFelhasználási feltételekAdatkezelési tájékoztatóSüti figyelmeztetés
A diszkrét logaritmus probléma
Matematikai zár moduláris aritmetika alkalmazásával. Készítette: Brit Cruise.
Szeretnél részt venni a beszélgetésben?
Még nincs hozzászólás.
Videóátirat
Egy olyan numerikus eljárás kell nekünk, ami könnyű az egyik irányban,
de visszacsinálni nehéz. Ez elvezet a moduláris
aritmetikához, amit óra-aritmetikának is hívnak. Például ahhoz, hogy megkapjuk
46 modulo 12-t, vehetünk egy 46 egységnyi
kötelet, és körbetekerjük egy 12 egység
kerületű órán. Ezt modulusnak (maradékos osztásnak)
hívjuk, és a kötél vége mutatja az eredményt. Azt mondjuk, hogy 46 modulo 12
kongruens 10-zel. Könnyű. Ahhoz, hogy ez működjön,
prím számok modulusát használunk, például 17-et, majd megkeressük
17 egyik primitív gyökét, ez esetben 3-at, ami rendelkezik
azzal a fontos tulajdonsággal, hogy különböző hatványokra emelve, az eredmény egyenletesen
oszlik el az óra körül. A 3-at generátornak hívjuk. Ha kiszámoljuk a 3 tetszőleges
x hatványát, akkor az eredmény azonos valószínűséggel
0 és 17 közötti tetszőleges egész lehet. De a visszaalakítás nehéz. Mondjuk adott a 12, találd meg
3-nak a megfelelő hatványát! Ezt diszkrét logaritmikus problémának
hívják. Most megvan az egyirányú függvényünk, könnyű elvégezni, de visszacsinálni nehéz. Ha adott 12, csak próbálkozással
juthatunk el a megfelelő kitevőkhöz. Mennyire nehéz ez? Kis számokkal könnyű, de ha több száz számjegyű
prím modulust használunk, gyakorlatilag nem lesz megoldható. Még ha rendelkeznél a Föld összes
számítási kapacitásával, akkor is több ezer évig tartana
az összes lehetőség végigpróbálása. Az egyirányú függvény ereje
a visszaállítás időigényén alapul.