RSA (cryptosystem) (Magyar)

A kínai fennmaradó algoritmusszerkesztés

a hatékonyság érdekében számos népszerű titkosítási könyvtár (például az OpenSSL, a Java és a.net) a következő optimalizálást használja a dekódoláshoz és az aláíráshoz a kínai maradék tétel alapján. Ezek az értékek lehetővé teszik a címzett számára, hogy az M = cd (mod pq) exponenciát az alábbiak szerint hatékonyabban számítsa ki:

ez hatékonyabb, mint az exponencia kiszámítása, annak ellenére, hogy két moduláris exponenciát kell kiszámítani., Ennek oka az, hogy ez a két moduláris exponencia mind kisebb exponenst, mind kisebb modulust használ.

Integer faktorizációs RSA problemEdit

A biztonság, az RSA cryptosystem alapján két matematikai probléma: a probléma a faktoring a nagy számok pedig az RSA probléma. Úgy gondolják, hogy az RSA rejtjelszöveg teljes dekódolása tévedhetetlen abban a feltételezésben, hogy mindkét probléma nehéz, azaz nincs hatékony algoritmus a megoldásukhoz., A részleges dekódolás elleni védelem biztosítása biztonságos párnázási rendszer hozzáadását igényelheti.

az RSA problémát úgy definiáljuk, mint az eth roots modulo kompozit n felvételének feladatát: az m érték helyreállítása úgy, hogy a c ≡ me (mod n), ahol (n, e) egy RSA nyilvános kulcs, a c pedig egy RSA rejtjelszöveg. Jelenleg az RSA probléma megoldásának legígéretesebb megközelítése a modulus n. a prímtényezők helyreállításának képességével a támadó kiszámíthatja a D titkos exponenst egy nyilvános kulcsból (n, e), majd visszafejtheti a C-t a szokásos eljárással., Ehhez a támadó tényezők N A P és q, és kiszámítja lcm (p − 1, q − 1), amely lehetővé teszi a meghatározása d e. nincs polinom-idő módszer faktoring nagy egész számok egy klasszikus számítógép még nem találtak, de nem bizonyított, hogy egyik sem létezik. Lásd egész faktorizáció a vita ezt a problémát.

Több polinom kvadratikus szita (MPQS) lehet használni, hogy a tényező a nyilvános modulus n.,

Az első RSA-512 faktorizációs 1999-ben használt több száz számítógép, szükséges egyenértékű 8,400 MIPS éve, egy eltelt idő körülbelül hét hónapja. 2009-re Benjamin Moody 73 nap alatt egyetlen nyilvános szoftver (GGNFS) és asztali számítógépe (egy 1900 MHz-es cpu-val rendelkező kétmagos Athlon64) segítségével egy RSA-512 bites kulcsot is kiszámíthat. Csak kevesebb, mint öt gigabájt lemeztárolásra volt szükség, körülbelül 2, 5 gigabájt RAM-ra a szitálás folyamatához.,

Rivest, Shamir és Adleman megjegyezte, hogy Miller megmutatta, hogy-feltételezve a kiterjesztett Riemann-hipotézis igazságát – a d megtalálása n-ből és e-ből olyan nehéz, mint az n faktorálása p-be és q-Ba (polinom időeltolódásig). Rivest, Shamir és Adleman azonban tanulmányuk IX / D szakaszában megjegyezte, hogy nem találtak bizonyítékot arra, hogy az RSA megfordítása olyan nehéz, mint a faktoring.

2020-tól a legnagyobb ismert faktorált RSA szám 829 Bit volt (250 decimális számjegy, RSA-250). Factorizációja a legkorszerűbb elosztott megvalósítással körülbelül 2700 CPU évet vett igénybe., A gyakorlatban az RSA kulcsok általában 1024-4096 bit hosszúak. 2003-ban az RSA Security becslése szerint az 1024 bites kulcsok valószínűleg 2010-re feltörhetővé válnak. 2020 – tól nem ismert, hogy az ilyen kulcsok megrepedhetnek-e, de a minimális ajánlások legalább 2048 bitre költöztek. Általában feltételezik, hogy az RSA biztonságos, ha n elég nagy, a kvantumszámításon kívül.

Ha n 300 Bit vagy annál rövidebb, akkor néhány órán belül faktorálható egy személyi számítógépen, a már szabadon elérhető szoftver használatával., Az 512 bites kulcsokról 1999-ben kiderült, hogy gyakorlatilag törhetők, amikor az RSA-155-öt több száz számítógép használatával állították össze, és ezeket néhány hét múlva közös hardver segítségével veszik figyelembe. Az 512 bites kódaláírási tanúsítványokat használó, esetleg faktorált kizsákmányolásokról 2011-ben számoltak be. A Shamir and Tromer által 2003-ban leírt, TWIRL nevű elméleti hardvereszköz megkérdőjelezte az 1024 bites kulcsok biztonságát.,

1994-ben Peter Shor megmutatta, hogy egy kvantumszámítógép-ha valaha is gyakorlatilag létre lehetne hozni erre a célra – képes lenne a polinom időben számolni, megtörve az RSA-t; lásd Shor algoritmusát.

hibás kulcs generationEdit

Megtalálni a nagy prímszám p q többnyire a vizsgálat véletlenszerű számokat a megfelelő méret valószínűségi primality vizsgálatok, gyorsan megszünteti, gyakorlatilag az összes nonprimes.

A P és q számok nem lehetnek “túl közel”, nehogy az N Fermat faktorizációja sikeres legyen., Ha a p − q kisebb 2n1 / 4-nél (n = p * q, ami még a kis 1024 bites n értékeknél is 3×1077), akkor a P és q megoldása triviális. Továbbá, ha a P − 1 − nek vagy a q-1-nek csak kis prímtényezői vannak, akkor az N-T Pollard P-1 algoritmusa gyorsan faktorálhatja, ezért a p vagy q ilyen értékeit el kell dobni.

fontos, hogy a privát exponens d elég nagy legyen. Michael J. Wiener megmutatta, hogy ha P q és 2Q között van (ami meglehetősen jellemző) és d < n1/4 / 3 között, akkor D hatékonyan számítható N-ből és e-ből.,

Nincs ismert támadás a kis nyilvános exponensek, például e = 3 ellen, feltéve, hogy a megfelelő párnázást használják. Coppersmith támadása sok alkalmazás támadja RSA kifejezetten, ha a nyilvános exponens e kicsi, ha a titkosított üzenet rövid, nem párnázott. A 65537 az e általánosan használt értéke; ez az érték kompromisszumnak tekinthető a potenciális kis exponens támadások elkerülése és a hatékony titkosítás (vagy aláírás-ellenőrzés) engedélyezése között., A számítógépes biztonságról szóló NIST speciális kiadvány (SP 800-78 Rev 1 2007.augusztus) nem teszi lehetővé a 65537-nél kisebb e nyilvános exponenseket, de nem indokolja ezt a korlátozást.

2017 októberében a Masaryk Egyetem kutatói bejelentették a ROCA sebezhetőséget, amely befolyásolja az RSA kulcsokat, amelyeket az Infineon Rsalib néven ismert könyvtárában megtestesített algoritmus generál. Kiderült, hogy számos intelligens kártya és megbízható platformmodul (TPMS) érintett. A sebezhető RSA kulcsok könnyen azonosíthatók a csapat által kiadott tesztprogram segítségével.,

Fontosságát erős véletlen szám generationEdit

ha Egy támadó erős véletlenszám-generátor, amely már megfelelő magot megfelelő entrópia, arra kell használni, hogy létrehoz a fővezérek p, illetve q. Egy elemzés összehasonlítása millió nyilvános kulcsok gyűjtött az Interneten végzett 2012 elején által Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung, valamint Christophe Wachter. A kulcsok 0,2% – át csak Euclid algoritmussal tudták faktorálni.

az egész faktorizáción alapuló kriptosystemekre jellemző gyengeséget használták ki., Ha n = pq egy nyilvános kulcs, és n ‘= p’q ‘egy másik, akkor ha véletlenül p = p’ (de q nem egyenlő q’), akkor egy egyszerű számítás gcd(n, n’) = p tényezők mind n, mind n’, teljesen veszélyeztetve mindkét kulcsot. Lenstra et al. vegye figyelembe, hogy ez a probléma minimalizálható egy erős, véletlenszerű, bithosszú vetőmag használatával, amely kétszerese a tervezett biztonsági szintnek, vagy determinisztikus funkció alkalmazásával a q adott p kiválasztásához, a P és q független kiválasztása helyett.

Nadia Heninger egy hasonló kísérletet végző csoport tagja volt. Daniel J ötletét használták., Bernstein kiszámítja az egyes RSA-kulcsok GCD-jét az összes többi N’ kulcs termékével szemben (egy 729 millió számjegyű szám), ahelyett,hogy külön-külön kiszámítaná az egyes gcd-ket(n, n’), ezáltal nagyon jelentős gyorsítást ér el, mivel egy nagy osztás után a GCD-probléma normál méretű.

Heninger a blogjában azt mondja, hogy a rossz kulcsok szinte teljes egészében beágyazott alkalmazásokban történtek, beleértve a “tűzfalakat, útválasztókat, VPN eszközöket, távoli szerver adminisztrációs eszközöket, nyomtatókat, projektorokat és VOIP telefonokat” több mint 30 gyártótól., Heninger elmagyarázza, hogy a két csoport által feltárt egy-megosztott-prime probléma olyan helyzetekből származik, amikor a pszeudorandom számgenerátor kezdetben rosszul van beültetve, majd az első és a második prímek generációja között újraindul. A problémát meg kell oldani a kulcsütemű időzítésekből vagy az elektronikus dióda zajból vagy az állomások között hangolt rádióvevőből származó, kellően magas entrópia magjainak felhasználásával.

az erős véletlenszám-generáció fontos a nyilvános kulcs-kriptográfia minden szakaszában., Például, ha egy gyenge generátort használnak az RSA által elosztott szimmetrikus kulcsokhoz, akkor egy lehallgató megkerülheti az RSA-t, és közvetlenül kitalálhatja a szimmetrikus kulcsokat.

időzítési támadásokszerkesztés

Kocher leírt egy új támadás RSA 1995-ben: ha a támadó Eve tudja Alice hardver kellő részletességgel, és képes mérni a dekódolás alkalommal több ismert ciphertexts, Eve lehet következtetni a dekódolás kulcs d gyorsan. Ez a támadás az RSA aláírási rendszer ellen is alkalmazható., 2003-ban Boneh és Brumley egy gyakorlatiasabb támadást mutatott be, amely képes az RSA faktorizációk helyreállítására hálózati kapcsolaton keresztül (pl. Secure Sockets Layer (SSL)-kompatibilis webszerver) ez a támadás kihasználja a kínai fennmaradó tétel optimalizálás által kiszivárogtatott információkat, amelyeket számos RSA implementáció használt.

ezeknek a támadásoknak a meghiúsításának egyik módja annak biztosítása, hogy a dekódolási művelet állandó időt vesz igénybe minden titkosításhoz. Ez a megközelítés azonban jelentősen csökkentheti a teljesítményt., Ehelyett a legtöbb RSA implementáció egy alternatív technikát használ, amelyet kriptográfiai vakításnak neveznek. Az RSA vakító az RSA multiplikatív tulajdonságát használja. A cd (mod n) kiszámítása helyett Alice először egy titkos véletlen értéket választ r és kiszámítja (rec)d (mod n). Ennek a számításnak az eredménye az Euler-tétel alkalmazása után az rcd (mod n), így az r hatása az inverz szorzatával eltávolítható. Az R új értékét választják minden rejtjelszöveghez. A blinding alkalmazása esetén a dekódolási idő már nem korrelál a bemeneti rejtjelszöveg értékével, így az időzítési támadás sikertelen.,

adaptív választott ciphertext attacksEdit

1998-ban Daniel Bleichenbacher leírta az első gyakorlati adaptív választott ciphertext támadást, az RSA-titkosított üzenetek ellen a PKCS #1 V1 padding sémával (a padding scheme randomizálja és hozzáadja a struktúrát egy RSA-titkosított üzenethez, így meg lehet határozni, hogy a dekódolt üzenet érvényes-e). A PKCS #1 rendszer hibái miatt a Bleichenbacher képes volt gyakorlati támadást indítani a Secure Socket Layer protokoll RSA implementációi ellen, valamint a session kulcsok helyreállítására., E munka eredményeként a kriptográfusok most olyan bizonyíthatóan biztonságos párnázási rendszerek használatát javasolják, mint például az optimális aszimmetrikus titkosítási párnázat, az RSA Laboratories pedig kiadta a PKCS #1 új verzióit, amelyek nem érzékenyek ezekre a támadásokra.

Side-channel analysis attacksEdit

a branch prediction analysis (BPA) segítségével oldalcsatornás támadást írtak le. Sok processzor egy ág-prediktort használ annak meghatározására, hogy egy feltételes ág a program utasításfolyamában valószínűleg megtörténik-e vagy sem. Gyakran ezek a processzorok egyidejű többszálú (SMT) végrehajtást is végrehajtanak., Branch jóslás elemzés támadások használja a kém folyamat felfedezni (statisztikailag) a privát kulcsot, ha feldolgozzák ezeket a processzorokat.

Simple Branch predikciós elemzés (Sbpa) azt állítja, hogy javítja a BPA nem statisztikai módon. Az “On The Power of Simple Branch predikciós elemzés” című tanulmányukban az sbpa (Onur Aciicmez és Cetin Kaya Koc) szerzői azt állítják, hogy 10 iterációban 512 RSA kulcsból 508-at fedeztek fel.

a teljesítmény hiba támadás RSA megvalósítások leírták 2010-ben., A szerző helyreállította a kulcsot azáltal, hogy a CPU tápfeszültségét külső határokon változtatta; ez több hálózati hibát okozott a kiszolgálón.