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
RSA-titkosítás: 2. lépés
Csapóajtó típusú egyirányú függvény készítése. Készítette: Brit Cruise.
Szeretnél részt venni a beszélgetésben?
Még nincs hozzászólás.
Videóátirat
A megoldást egy másik brit
matematikus és kriptográfus, Clifford Cocks találta meg. Cocksnak egy speciális egyirányú
függvényt kellett megalkotnia, amit csapóajtó-típusú
egyirányú függvénynek hívnak. Ez egy olyan függvény, amit
az egyik irányban könnyű kiszámolni, de nehéz visszaalakítani, ha nem rendelkezel adott információval,
amit csapóajtónak hívnak. Ehhez a moduláris
hatványozást alkalmazta, amit óra-aritmetikaként
mutattunk be a Diffie-Hellman kulcscsere részben
az alábbiak szerint: Vegyél egy számot,
számold ki valamilyen hatványát, oszd el a modulussal,
és add meg a maradékot. Ezt így használhatod
egy üzenet kódolására: Tegyük fel, hogy Bobnak van egy üzenete, amit egy m számmá konvertáltunk. Ezt a számot e-szer
megszorozza önmagával, ahol e a nyilvános hatványkitevő, majd az eredményt elosztja
egy véletlen N számmal, majd közli az osztás eredményét. Ez legyen a c szám. Ezt a számítást könnyű elvégezni, de ha csak c-t, e-t és N-et ismerjük, sokkal nehezebb a felhasznált m
meghatározása, mert a próbálkozás valamilyen
formáját kell alkalmaznunk. Ez az egyirányú függvényünk,
amit m-re kiszámolunk, könnyű alkalmazni,
de nehéz visszaalakítani. Ez a matematikai lakatunk. Mi a helyzet a kulccsal? A kulcs a csapóajtó, egy olyan információ, ami megkönnyíti
a titkosítás visszaalakítását. Ki kell számolni c valamilyen másik,
mondjuk d hatványát, ami visszaalakítja az eredeti
m-en végrehajtott műveletet, és visszaadja m eredeti értékét. A két művelet együtt ugyanaz: m az e-edik hatványon
felemelve a d-edik hatványra, ami megegyezik m az e-szer d-ediken, ahol e a rejtjel, d a megfejtőkulcs. Ehhez az kell, hogy Alíz készíteni tudjon
olyan e-t és d-t, ami más számára nehézzé teszi
d-t megtalálni. Ehhez egy második egyirányú függvény kell,
ami a d-t generálja, ehhez visszatérünk Euklidészhez.