RSA cryptosystem (tsz. RSA cryptosystems)
A nyilvános kulcsú kriptorendszerekben a titkosítási kulcs nyilvános, és különbözik a titkosított (privát) visszafejtő kulcstól . Egy RSA-felhasználó két nagy prímszám alapján hoz létre és tesz közzé egy nyilvános kulcsot egy segédértékkel együtt. A prímszámokat titokban tartják. Az üzeneteket bárki titkosíthatja a nyilvános kulccsal, de csak az tudja visszafejteni, aki ismeri a privát kulcsot.
Az RSA biztonsága a két nagy prímszám szorzatának faktorálásának gyakorlati nehézségén múlik , a " faktorálási problémán ". Az RSA titkosítás feltörése RSA problémaként ismert . Nyitott kérdés, hogy ez olyan nehéz-e, mint a faktoring probléma. Nincsenek publikált módszerek a rendszer leküzdésére, ha elég nagy kulcsot használnak.
Az RSA egy viszonylag lassú algoritmus. Emiatt nem gyakran használják a felhasználói adatok közvetlen titkosítására. Az RSA-t gyakrabban használják megosztott kulcsok továbbítására a szimmetrikus kulcsú titkosításhoz, amelyeket aztán tömeges titkosításhoz és visszafejtéshez használnak.
Történelem
Adi Shamir , az RSA társfeltalálója (a többiek Ron Rivest és Leonard Adleman ) Az aszimmetrikus nyilvános-privát kulcsú kriptorendszer ötlete Whitfield Diffie-nek és Martin Hellmannek tulajdonítható , akik 1976-ban publikálták ezt a koncepciót. Ők vezették be a digitális aláírásokat is, és megkísérelték a számelmélet alkalmazását. A megfogalmazásukban egy megosztott titkos kulcsot használtak, amelyet valamilyen szám hatványozásából hoztak létre, modulo egy prímszámot. Nyitva hagyták azonban az egyirányú függvény megvalósításának problémáját, valószínűleg azért, mert a faktoring nehézségeit akkor még nem vizsgálták kellőképpen. Ráadásul a Diffie-Hellmanhoz hasonlóan az RSA is a moduláris hatványozáson alapul .
Ron Rivest , Adi Shamir és Leonard Adleman a Massachusetts Institute of Technology munkatársai egy év során többször is kísérletet tettek egy nehezen megfordítható függvény létrehozására. Rivest és Shamir informatikusként számos lehetséges függvényt javasoltak, míg Adleman matematikusként volt felelős a gyenge pontjaik megtalálásáért. Számos megközelítést kipróbáltak, beleértve a " hátizsák -alapú" és a "permutációs polinomokat". Egy ideig azt hitték, hogy az egymásnak ellentmondó követelmények miatt lehetetlen, amit el akarnak érni. 1977 áprilisában egy diák házában töltötték a húsvétot , és jó sok bort ittak, mielőtt éjfél körül visszatértek otthonukba. Rivest, aki nem tudott aludni, lefeküdt a kanapéra egy matematikai tankönyvvel, és elkezdett gondolkodni az egyirányú funkciójukon. Az éjszaka hátralévő részét azzal töltötte, hogy hivatalossá tegye az elképzelését, és hajnalra készen volt a papír nagy része. Az algoritmus ma RSA néven ismert – a vezetéknevük kezdőbetűi ugyanolyan sorrendben, mint a papírjukban.
Clifford Cocks , a brit hírszerző ügynökségnél dolgozó angol matematikus , a Government Communications Headquarters (GCHQ) 1973-ban írt le egy hasonló rendszert egy belső dokumentumban. Azonban a megvalósításhoz akkoriban viszonylag drága számítógépek miatt ezt többnyire érdekességnek tekintették, és a nyilvánosság szerint soha nem alkalmazták. Ötleteit és koncepcióit szigorúan titkos minősítése miatt csak 1997-ben hozták nyilvánosságra.
A Kid-RSA (KRSA) egy egyszerűsített, nem biztonságos nyilvános kulcsú titkosítás, amelyet 1997-ben adtak ki, oktatási célokra. Vannak, akik úgy érzik, hogy a Kid-RSA tanulása betekintést nyújt az RSA-ba és más nyilvános kulcsú titkosításokba, hasonlóan az egyszerűsített DES-hez .
Szabadalom Az RSA algoritmust leíró szabadalmat 1983. szeptember 20-án engedélyezték az MIT- nek: 4 405 829 számú amerikai egyesült államokbeli szabadalom "Cryptographiai kommunikációs rendszer és módszer". A DWPI szabadalomkivonatából :
A rendszer tartalmaz egy kommunikációs csatornát, amely legalább egy kódolóeszközzel rendelkező terminálhoz és legalább egy dekódolóeszközzel rendelkező terminálhoz van kapcsolva. Az átvitelre kerülő üzenetet a kódoló terminálon titkosított szöveggé kódolják úgy, hogy az üzenetet M számként kódolják egy előre meghatározott készletben. Ezt a számot ezután egy első előre meghatározott teljesítményre emelik (a tervezett vevőhöz társítva), és végül kiszámítják. A maradékot vagy maradékot, C-t... akkor számítjuk ki, ha a hatványozott számot elosztjuk két előre meghatározott prímszám szorzatával (a kívánt vevőhöz társítva).
Az algoritmus részletes leírása 1977 augusztusában jelent meg a Scientific American Mathematical Games rovatában. Ez megelőzte a szabadalom 1977. decemberi bejelentési dátumát. Következésképpen a szabadalomnak nem volt jogi ereje az Egyesült Államokon kívül . Ha Cocks munkája nyilvános lett volna, az Egyesült Államokban sem lett volna legális a szabadalom.
A szabadalom kiadásakor a szabadalom futamideje 17 év volt. A szabadalom 2000. szeptember 21-én lejárt, de az RSA Security 2000. szeptember 6-án nyilvánosságra hozta az algoritmust .