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: 1. lépés
Miért van szükség az RSA-ra– bevezetés. Készítette: Brit Cruise.
Szeretnél részt venni a beszélgetésben?
Még nincs hozzászólás.
Videóátirat
Az 1970-es évekig a kriptográfia
szimmetrikus kulcson alapult. Ez azt jelenti, hogy a küldő
titkosítja az üzenetét egy adott kulccsal, és a fogadó dekódolja azt
ugyanavval a kulccsal. (kattanó zár) Emlékszel? A titkosítás egy üzenet leképezése egy adott kulccsal egy rejtjelezett üzenetre. Az üzenet visszafejtéséhez ugyanaz a kulcs kell
a leképezés visszaalakításához. Alíz és Bob
biztonságos kommunikációjához először meg kell állapodniuk
egy közös kulcsban. De gyakran lehetetlen
közös kulcs létrehozása, ha Alíz és Bob nem tudnak
fizikailag találkozni, vagy külön kommunikációt igényel ha a Diffy-Hellman kulcs-csere
módszert használják. Ezen felül, ha Alíznak
számos emberrel kell kommunikálnia, mondjuk, ha Alíz egy bank, akkor külön-külön mindenkivel
más-más kulcsot kell cserélnie. Mindezeket a kulcsokat
nyilván kell tartani, és több ezer üzenet kell
csak a létrehozásukhoz. Nincs erre valami egyszerűbb lehetőség? 1970-ben James Ellis, egy brit mérnök
és matematikus egy nem-titkos rejtjelezésen dolgozott. Ez egy egyszerű, de zseniális elméleten
alapul: A zárás és nyitás inverz műveletek. Alíz vesz egy lakatot és
megtartja a kulcsot, majd elküldi a nyitott
lakatot Bobnak. Bob bezárja üzenetét,
és visszaküldi Alíznak. Nincs kulcs-csere. Ez azt jelenti, hogy Alíz széles körben
nyilvánossá teheti a lakatot, és bárki használhatja azt,
hogy üzenetet küldjön neki. Így Alíznak csak egyetlen kulcsot
kell nyilvántartani. Ellis nem jutott el
matematikai megoldáshoz, bár ösztönösen érezte,
hogyan kellene annak működni. Az elképzelés alapja az, hogy
egy kulcsot két részre kell osztani, egy titkosító,
és egy visszafejtő részre. A visszafejtő résszel
lehet megoldani a dekódolást, amit a titkosító kulccsal kódoltunk. A visszafejtő kulcs működését színekkel fogjuk illusztrálni. Hogyan küldhet Bob Alíznak egy színt
anélkül, hogy a mindig figyelő Éva megfejthetné? Egy szín inverzét
komplementer színnek hívják, amit, ha hozzáadunk a színünkhöz,
fehér színt ad ki, eltüntetve az eredeti színt. Ebben a példában feltesszük,
hogy a színkeverés egy egyirányú művelet,
mert gyorsan lehet színeket összekeverni, így létrehozva egy harmadik színt,
de visszacsinálni sokkal nehezebb. Alíz először a saját
privát kulcsát generálja, véletlenszerűen választ egy színt,
mondjuk pirosat. Ezután tegyük fel, hogy
használ egy titkos színgépet, amivel elkészíti a piros
tökéletes komplementerét, amihez senki más nem férhet hozzá. Ez cián-kék lesz, amit elküld Bobnak, ez lesz a publikus kulcsa. Mondjuk Bob egy titkos sárgát akar
küldeni Alíznak. Összekeveri a publikus színnel, és az eredményül kapott keveréket
visszaküldi Alíznak. Alíz a saját privát színét
hozzáadja Bob keverékéhez. Ez semlegesíti a nyilvános szín
hatását, így megmarad Bob eredeti titkos színe. Figyeld meg, hogy Évának könnyű
megtalálnia Bob sárgáját, mivel ehhez szüksége van
Alíz titkos pirosához. Ennek így kell működnie. Viszont a gyakorlatban egy matematikai
megoldásra volt szükség.