RSA-titkosítás. Leírás és megvalósítása az RSA algoritmus

RSA-titkosítás egyik első gyakorlati nyilvános kulcsú titkosító rendszer, amelyet széles körben használnak a biztonságos adatátvitelt. A fő különbség a hasonló szolgáltatásokat, hogy a titkosítási kulcs nyitott és eltér a dekódoló kulcsot, amelyet titokban tartják. Az RSA technológia , ez az aszimmetria alapul gyakorlati nehézség faktoring lejátszási két nagy prímszám (a probléma a faktoring).

Történelem folyamán

RSA neve áll az első betű a vezetéknevű Rivest, Shamir és Adleman - a tudósok, akik először nyilvánosan ismertetett ezek titkosító algoritmusok 1977. Klifford Koks, egy angol matematikus, aki dolgozott a brit hírszerzés, az első, hogy dolgozzon ki olyan egyenértékű rendszert 1973-ban, de ez nem volt minősítését 1997-ig

RSA felhasználó létrehoz, majd közzéteszi a nyilvános kulcs alapján két nagy prímszám együtt a kiegészítő értéket. Prímszámok titokban kell tartani. Bárki használhatja a nyilvános kulcsa segítségével titkosítja az üzenetet, de ha elég nagy, akkor csak aki ismeri a prímszámok képes dekódolni az üzenetet. RSA titkosítás közzététel ismert, mint a fő probléma ma az, hogy nyílt vita arról, hogy egy megbízható mechanizmus.

RSA algoritmus viszonylag lassú, és ezért ez nem olyan széles körben használják, hogy közvetlenül beavatkozik a felhasználó. A legtöbb esetben ezt a módszert alkalmazzák továbbítására a megosztott kulcs titkosított szimmetrikus titkosítási kulcsot, ami viszont műveleteket hajthat végre tömeges kódolási és dekódolási sokkal nagyobb sebességgel.

Amikor nem volt olyan kriptográfiai jelenlegi formájában?

Az az elképzelés, aszimmetrikus kriptográfiai kulcs tulajdonított Diffie és Hellman, aki megjelent a fogalom 1976-ban, és bevezeti a digitális aláírások és próbálják az elmélet a számok. Megfogalmazásuk egy megosztott titkos kulcsot generált egy bizonyos számú hatványozási modulo prímszám. Ezek azonban nyitva hagyta a kérdést a megvalósítását ez a funkció, mert elvei faktoring nem tisztázott idején.

Rivest, Adi Shamir és Adleman a MIT Számos kísérletet tettünk az elmúlt években, hogy hozzon létre egy egyirányú függvény, amelyet nehéz megfejteni. Rivest és Shamir (például a számítógépes tudósok) javasolta sok potenciális funkciókat, míg Adleman (így a matematika) keresni „gyenge pontok” az algoritmus. Régebben sok megközelítések és végül kifejlesztik a végleges rendszer, mai nevén RSA 1977 áprilisában.

Elektronikus aláírás és a nyilvános kulcs

Digitális aláírás vagy elektronikus aláírás, szerves részét képezi az elektronikus dokumentum típusokat. Úgy van kialakítva egy bizonyos titkosítási adatokat változásokat. Ezzel attribútum lehetséges integritásának ellenőrzésére a dokumentumot, azok titkosságát, valamint hogy ki a tulajdonosa. Tény, hogy egy alternatív általános, sztenderd aláírását.

Ez titkosítórendszer (RSA-titkosított) kínál a nyilvános kulcs, ellentétben szimmetrikus. Működési elve az, hogy a két különböző gombokat használjuk - zárt (titkosított) és a szabadtéri. Az első létrehozásához használt digitális aláírás és így képes visszafejteni a szöveget. A második - a tényleges titkosítás és elektronikus aláírás.

Segítségével aláírást, hogy jobban megértsék az RSA titkosítás, amelynek egyik példája lehet csökkenteni, mint egy normál titkos „zárva a kíváncsiskodó szemek”, a dokumentumot.

Mi az algoritmus?

RSA algoritmus négy lépésből áll: a legfontosabb fejlesztése, forgalmazása, titkosítás és dekódolás. Mint már említettük, az RSA-titkosítás tartalmaz egy nyilvános kulcsot és egy privát kulcsot. Kültéri lehet mindenki által ismert és titkosításához használt üzeneteket. Ennek lényege abban rejlik, hogy a kódolt üzeneteket a nyilvános kulcs csak akkor lehet visszafejteni egy adott időtartam alatt egy titkos kulcs használatával.

Biztonsági okokból az egész, hogy a véletlenszerűen kiválasztott és azonos méretű, de különböznek hossza néhány számot, hogy a faktoring nehezebb. Ugyanaz ugyanazt a számot meg lehessen találni egy teszt a maguk egyszerűségében, így a titkosítási információt szükségszerűen bonyolult.

A nyilvános kulcs áll a modulus és a nyilvános kitevő. Beltéri egység, és egy saját szám, amelyet titokban kell tartani.

RSA fájl- és gyengeségek

Van azonban számos olyan egyszerű hacker RSA mechanizmusokat. Kódolásnál alacsony és kis értékű kódszámok könnyen lehet nyitni, ha a pick gyökér rejtjelezett az egész.

Mivel az RSA-titkosítás egy determinisztikus algoritmus (azaz nincs véletlen komponens), a támadó sikeresen indítani a kijelölt szöveget nyílt támadás a titkosítási rendszer titkosítja valószínűleg plaintexts alatt a nyilvános kulcsot és ellenőrzését, hogy azok egyenlő rejtjelezett. Szemantikailag biztonságos titkosítási rendszer nevezzük abban az esetben, hogy a támadó nem tud különbséget tenni a kettő között titkosítás egymástól, még akkor is, ha tudja, hogy a vonatkozó szövegek a kibővített formában. Ahogy fentebb említettük, az RSA egyéb szolgáltatások betét nélkül nem szemantikailag biztonságos.

További algoritmusok titkosítás és védelem

Annak elkerülése érdekében, a fenti problémák, a gyakorlati megvalósítása az RSA rendszerint behelyezve valamilyen formában a strukturált, randomizált töltés előtt titkosítás. Ez biztosítja, hogy a tartalom nem tartozik a tartományban bizonytalan plaintexts, és hogy ezt az üzenetet nem lehet megoldani véletlen kiválasztással.

Biztonsági RSA titkosítási rendszer és a titkosítás alapja a két matematikai probléma: a problémát a faktoring nagy számban, és a tényleges RSA probléma. Teljes nyilvánosságra hozatala a rejtjelezett és aláírás az RSA elfogadhatatlannak minősül az a feltételezés, hogy mind a két problémát nem lehet megoldani közösen.

Azonban azzal a képességgel, hogy visszaszerezze prímosztók, a támadó ki tudja számítani a titkos kitevő nyilvános kulcsot, majd dekódolja a szöveget a szokásos eljárás. Annak ellenére, hogy ma nem létezik olyan módszer faktoring nagy egész számokat egy klasszikus számítógép nem találja meg, nem bizonyított, hogy nem létezik.

automatizálás

Az eszköz, az úgynevezett Yafu, fel lehet használni a folyamat optimalizálására. Automatizálási YAFU egy speciális funkció, amely egyesíti faktorizációs algoritmusok szellemi és adaptív módszer, amely minimálisra csökkenti az időt, hogy megtalálja azokat a tényezőket, önkényes számokat. A legtöbb implementáció többszálú algoritmus lehetővé teszi Yafu teljes mértékben kihasználja a multi- vagy több többmagos processzorok (beleértve SNFS, SIQS és ECM). Először is, ez által irányított parancssori eszköz. Az eltöltött idő keres titkosítás Yafu faktor egy hagyományos számítógépen, akkor lehet csökkenteni másodperc 103,1746. Az eszköz feldolgozza a bináris kapacitása 320 bit vagy annál nagyobb. Ez egy nagyon összetett szoftver, amely előírja egy bizonyos mennyiségű technikai készségek telepíteni és konfigurálni. Így, RSA-titkosítás sérülékeny lehet C.

Hacker az utóbbi időkben

2009-ben, Bendzhamin mudi RSA-512 bites kulcs dolgozott deciphering kriptoteksta 73 napig, alkalmazásával csak a jól ismert szoftver (GGNFS) és az átlagos asztali (kétmagos Athlon64 1900 MHz). Amint az a tapasztalat, szükséges valamivel kevesebb, mint 5 GB merevlemez, és körülbelül 2,5 gigabájt memória a folyamat „rostálás.”

Mivel 2010-ben a legnagyobb számot tényezőként RSA 768 bit hosszú (232 tizedesjegy vagy RSA-768). Ő közzététel két évig tartott több száz számítógépen egyszerre.

A gyakorlatban az RSA-kulcsok hosszúak - jellemzően 1024-4096 bit. Egyes szakértők úgy vélik, hogy az 1024 bites kulcsot megbízhatatlanná válhat a közeljövőben, vagy még tovább is repedt nagyon jól finanszírozott támadók. Azonban kevesen állítják, hogy 4096 bites kulcsot is lehet közölni a közeljövőben.

kilátások

Ezért, mint a szabály, hogy feltételezzük, hogy az RSA biztonságos, ha a számok elég nagy. Ha az alap száma 300 bit vagy annál rövidebb, és a rejtjelezett digitális aláírás lehet bontani néhány órán belül a személyi számítógép szoftver segítségével már rendelkezésre állnak a nyilvánosság. A kulcs hossza 512 bit, mint látható, ki lehet nyitni már 1999-ben, a használata néhány száz számítógépek. Napjainkban lehetséges néhány hét egy nyilvánosan elérhető hardver. Így lehetséges, hogy a buduschembudet könnyen ismertetett RSA-titkosítás az ujjak, és a rendszer lesz reménytelenül elavult.

Hivatalosan 2003-ben megkérdőjelezte a biztonságát a 1024 bites kulcsokat. Jelenleg ajánlott minimális hossza 2048 bit.