it-swarm-eu.dev

Měl by být veřejný exponent RSA pouze z důvodu {3, 5, 17, 257 nebo 65537} z bezpečnostních důvodů?

V mém projektu používám hodnotu veřejného exponenta 4451h. Myslel jsem, že je to bezpečné a v pořádku, dokud jsem nezačal používat jednu komerční šifrovací knihovnu RSA. Pokud použiji tento exponent s touto knihovnou, vyvolá výjimku.

Kontaktoval jsem vývojáře této knihovny a dostal jsem následující odpověď: „Tato funkce má zabránit některým útokům na klíče RSA. Důsledkem je, že hodnota exponentu je omezena na {3, 5, 17, 257 nebo 65537}. Deaktivace této kontroly je stále je vyšetřováno, protože rizika mohou být velká. “

Je to poprvé, co jsem v životě slyšel, že jiné hodnoty než {3, 5, 17, 257 nebo 65537} se používají k rozbití RSA. Věděl jsem jen o použití 3 s nevhodným čalouněním.

Je to opravdu tak? Určitě mohu použít jinou knihovnu, ale po takové odpovědi jsem se obával o zabezpečení svého řešení.

70

Neexistuje žádná známá slabost pro jakýkoli krátký nebo dlouhý veřejný exponent pro RSA, pokud je veřejný exponent „správný“ (tj. Relativně připravený p-1 pro všechny prvočísla p , které dělí modul).

Pokud používáte malý exponent a nepoužíváte pro šifrování žádné výplně a Šifrujete přesně stejnou zprávu pomocí několik různých veřejných klíčů, pak je vaše zpráva ohrožena: pokud e = 3 a zašifrujete zprávu m pomocí veřejných klíčů n1, n2 a n3, pak máte ci = m3 mod ni pro i = 1 do 3. Podle Čínská věta o zbytk , pak můžete znovu vytvořit m3 mod n1n2n3, což se ukáže být m3 (bez modulo) protože n1n2n3 je větší celé číslo. Extrahování kořenů krychle (nemodulární) pak stačí k extrakci m.

Slabou stránkou je není malý exponent; spíše se jedná o použití nesprávného čalounění (tj. vůbec žádné čalounění) pro šifrování. Výplň je velmi důležitá pro zabezpečení RSA, ať už šifrování nebo podpis; Pokud nepoužíváte správné vycpávky (jako jsou ty, které jsou popsány v PKCS # 1 ), pak máte mnoho slabých stránek a ten, který je uveden v předchozím odstavci, není zdaleka největší. Nicméně, kdykoli někdo odkazuje na slabost související s velikostí exponentů, více či méně přímo na tento výskyt odkazuje. To je trochu stará a nesprávná tradice, která je někdy převedena na zákaz proti exponentům velký (protože je to mýtus, mýtus obrácený je také mýtem a už není - a ne méně podložené); Věřím, že to je to, co zde sledujete.

Existuje však několik důvodů, proč by se nemělo vyhýbat velkému veřejnému exponentu:

  • Malé veřejné exporty podporují efektivitu (pro operace veřejného klíče).

  • Existují bezpečnostní problémy s malým exponentem soukromé; byl popsán útok obnovy klíče, pokud délka soukromého exponentu není větší než 29% délky veřejného exponentu. Pokud chcete vynutit, aby byl soukromý exponent krátký (např. Pro urychlení operací soukromého klíče), musíte více či méně použít velký veřejný exponent (stejně velký jako modul); požadavek, aby byl veřejný exponent krátký, lze pak považovat za druh nepřímého protiopatření.

  • Některé široce nasazené implementace RSA škrtí velké veřejné exponenty RSA. Např. kód RSA ve Windows (CryptoAPI, používaný Internet Explorer pro HTTPS) trvá na kódování veřejného exponentu v rámci jednoho 32bitového slova; nemůže zpracovat veřejný klíč s větším veřejným exponentem.

Přesto „rizika mohou být velká“ vypadá jako obecné odůvodnění („toto je bezpečnostní problém“ je obvyklý způsob, jak říci „my jsme to neprovedli, ale nechceme připustit jakoukoli lenost“).

64
Thomas Pornin

Vývojáři jsou prostě nesprávní. S exponentem 0x4451 (desetinné číslo 17489) není nic špatného; nevytváří žádné bezpečnostní problémy.

Lidé si dávno mysleli, že malé exponenty jsou problémem, kvůli útoku, který Thomas Pornin vysvětlil zasláním stejné zprávy více příjemcům. Dnes však chápeme, že exponenti s tím nemají nic společného; problém byl nesprávný výplň. Těmto útokům je zabráněno řádným použitím čalounění. Jakákoli kryptografická knihovna, která stojí za její sůl, se zatraceně dobře hodila, že používá správné čalounění (jinak máte mnohem horší problémy).

Neexistuje tedy žádný dobrý důvod, aby krypto knihovna plochě zakazovala použití tohoto exponentu.

To znamená, že z hlediska výkonu, čím menší je exponent, tím lepší je výkon. Nejlepší volbou je e = 3, protože to poskytuje nejlepší výkon a nemá žádné známé bezpečnostní problémy. (Vlastně e = 2 je ještě o něco lepší. Je také známý jako Rabinovo šifrování. Toto schéma však není tak dobře známé a vyžaduje mírně odlišný kód, takže se široce nepoužívá.)

21
D.W.

Těchto pět čísel je Fermatovy prvočísla .

Protože jsou ve formě 2 k  + 1, šifrování je m e  = m · (( m 2)2... k krát...)2, což je jednodušší a rychlejší než exponentiace s exponentem podobné velikosti v obecný případ .

Protože jsou prvočísla, test, že e je coprime to ( p - 1) ( q - 1) je pouze test, který e nerozděluje.

Je to tedy spíše o rychlosti nebo konvenci než o bezpečnosti. Ne, že by něco bylo špatně s účinností. Ale pro jistotu si vyžádejte odkaz, jak navrhuje jiná odpověď .

Viz také tento příspěvek .

19
aaz

Nevím o žádném důvodu, proč by veřejný exponent klíče RSA měl být pouze v sadě {3,5,17,257,65537}. Jak jste zmínili, použití malých exponentů, jako jsou 3 nebo 5, je riskantnější, protože negativní účinky chyb implementace (například nesprávné vycpávky) mohou být větší. NIST povoluje pouze veřejné exponenty větší než 2 ^ 16, ale nevím důvod jejich rozhodnutí.

Odpovědi od vývojářů knihovny, kterou používáte, byste neměli být spokojeni a žádat o konkrétní reference. Příliš často se ukazuje, že nějaký papír byl nepochopen. Mohl bych si například představit, že někteří vývojáři přečtou sekci 4 článku „Můžeme důvěřovat kryptografickému softwaru? Kryptografickým chybám v GNU ochrana soukromí v1.2.3“) od Phong Nguyena a dochází k nesprávnému závěru, Tento článek si všiml, že když se veřejný klíč vygenerovaný GnuPG ukáže jako neobvyklá hodnota, jako je 65539, pak se útočník dozví malou informaci o tajném klíči. Závěrem je, že algoritmus generování klíčů GnuPG by mohl zlepšit, ale ne že 65539 je špatný veřejný klíč.

8
Accipitridae

Nemohl jsem najít žádný odkaz, že další hodnoty pro veřejného exponenta jsou zranitelné. Tvrdé použití veřejného exponentu blízkého výkonu 2 je vhodné z důvodů výkonu, podle Průvodce RSA.com k algoritmu RSA

Podle Wikipedia neumožňuje NIST veřejný exponent menší než 65537, protože menší exponenty jsou problémem, pokud nejsou řádně vyplněny.

7
Andreas Arnold