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: 3. lépés
RSA-titkosítás (3. lépés). Készítette: Brit Cruise.
Szeretnél részt venni a beszélgetésben?
Még nincs hozzászólás.
Videóátirat
2000 évvel ezelőtt
Euklidész bebizonyította, hogy minden számnak
pontosan egy prímtényezős felbontása van, amit tekinthetünk egy titkos kulcsnak. Az is tény, hogy a prímtényezőkre bontás alapvetően egy bonyolult probléma. Határozzuk meg, mit tekintünk
„könnyűnek” illetve „nehéznek”. Vezessük be az
„időbonyolultság” függvényét! Mindannyian tudunk számokat szorozni, és vannak trükkjeink, amivel fel tudjuk gyorsítani a számítást. Ha szorzáshoz készítünk egy
számítógépes programot, az az embernél sokkal gyorsabb lesz. Ez a grafikon megmutatja, hogy mennyi idő kell a számítógépnek
két szám összeszorzásához. Természetesen ahogy a számok
mérete nő, úgy nő a számításhoz szükséges idő is. Figyeld meg, hogy a számítási idő jóval egy másodperc alatt marad még egész nagy számok esetében is. Erre azt mondjuk,
hogy azt „könnyű” végrehajtani. Hasonlítsuk ezt
a prímtényezős felbontáshoz! Ha meg kell találnod az 589
prímtényezőit, ez érezhetően nehezebb feladat. Függetlenül az alkalmazott stratégiától,
próbálgatásra van szükség, amíg meg nem találod azt a számot,
ami egyenletesen osztja el az 589-et. Egy kis küzdelem után eljutsz oda, hogy a prímtényezős felbontás 19-szer 31. Ha a feladat 437 231 prím
osztóinak megtalálása, valószínűleg feladod,
és számítógépet hívsz segítségül. Ez kis számok esetében működik, de ha olyan gépet keresünk, ami egyre nagyobb számok
faktorizációjára képes, exponenciális a növekedés. A számítások elvégzéséhez
szükséges idő gyorsan növekszik a szükséges
lépések számának növekedésével. Ahogy nőnek a számok,
a számítógépnek percekre, majd órákra, végül száz, vagy több ezer évre van
szüksége nagy számok faktorizációjához. Erre azt mondjuk,
hogy ez egy „nehéz” probléma a megoldáshoz szükséges idő
növekedési üteme miatt. Ezért Cocs a faktorizációra
alapozta a csapóajtó kialakítását. Első lépésként Alíz generál egy több,
mint 150 számjegyből álló prímszámot: legyen ez „p1”. Azután vesz egy másik, körülbelül
ugyanolyan hosszú prímet, nevezzük „p2”-nek. Ezután ezt a két prímszámot
összeszorozza, így megkapja az N
összetett számot, ami több, mint 300
számjegyből áll. Ez a szorzás egy másodpercnél
rövidebb idő alatt megvan; akár egy web böngészőben
is elvégezhető. Ezután az N felbontását, p1-et és p2-t elrejti. Ha bárkinek odaadja N-et, az évekig futtathatja a számítógépen, amíg megkapja a megoldást. Második lépésként Cocksnak
találnia kellett egy függvényt, ami az N prímtényezős felbontásától függ. Ehhez visszanyúlt Leonhard Euler
svájci matematikus 1760-as munkájához.