Kryptografové padělali podpisy 1024bitového klíče RSA, aniž ho rozložili na činitele
Pětice kryptografů z Kalifornské univerzity v San Diegu a z INRIA Nancy dokázala padělat podpisy 1024bitového klíče RSA, aniž ho rozložila na prvočísla. Výpočet zabral 1 380 procesorových jádroroků, tedy zhruba tři setiny toho, co by stál rozklad téhož klíče. Útok ale potřebuje dočasný přístup ke službě, která podepisuje surová data bez výplně, takže běžných podpisů RSA se netýká.
Bezpečnost RSA se odjakživa odhaduje z jediné otázky: jak těžké je rozložit veřejný modul na dvě prvočísla. Práce Forging 1024-bit RSA signatures in nearly SNFS time, kterou archiv IACR přijal 22. září 2026, ukazuje, že ta otázka nepokrývá všechno. Podpisy se dají padělat i bez rozkladu, a podstatně levněji.
Pět měsíců a 1 380 jádroroků na jeden klíč
Za prací stojí Laura Shea, Miro Haller, Adam Suhl a Nadia Heninger z Kalifornské univerzity v San Diegu a Emmanuel Thomé z INRIA Nancy. Útok pustili na 1024bitový klíč. Spotřeboval 1 380 procesorových jádroroků rozložených do pěti kalendářních měsíců a 232 dotazů na podepisovací službu; výpočet doběhl 31. srpna 2026.
Většina té práce je předvýpočet, který závisí jen na veřejném modulu, a zabrala zhruba 1 200 jádroroků. Po něm útočník padělá libovolný podpis offline za nějakých 180 jádroroků a žádné další dotazy už nepotřebuje. Rozložit 1024bitový modul se přitom odhaduje na 500 tisíc až milion jádroroků. Objemem výpočtu se útok pohybuje mezi rekordy RSA-240 a RSA-250.
Algoritmus je z roku 2007, běh v plné velikosti je první
Postup popsali Antoine Joux, David Naccache a Emmanuel Thomé v práci z roku 2007. Je to varianta speciálního síta v číselném tělese (SNFS), tedy rychlejšího příbuzného obecného síta, kterým se moduly RSA rozkládají. Devatenáct let ho nikdo veřejně nespustil na plnou velikost; kód, který to teď udělal, staví na knihovně CADO-NFS.
Autoři zdůrazňují, že algoritmus není polynomiální a ani se tomu neblíží. Je subexponenciální, stejně jako nejlepší známé metody rozkladu – jen patří do rychlejší subexponenciální třídy. Proč to trvalo do roku 2026, vysvětlují prozaicky: takový výpočet je práce na měsíce, lidí v oboru je málo, peněz taky a studenty dnes víc zajímá postkvantová kryptografie.
Místo klíče stačí dočasný přístup k podepisování
Útok potřebuje věštce – službu, která na požádání podepíše nebo dešifruje surová data bez jakékoli výplně. Autoři si takového věštce obstarali hardwarovým bezpečnostním modulem Luna K6. Aby modul surové operace RSA vůbec dovolil, museli v něm vypnout režim schválený podle normy FIPS 140-2 a sáhnout po mechanismu CKM_RSA_X_509.
Výsledek je nepříjemný právě u zařízení, které má klíč chránit: útočník se dokáže za modul vydávat přes jeho vlastní rozhraní, přestože klíč modul nikdy neopustil. Stejný druh věštce nabízejí slepé podpisy RSA, kde server podepisuje data, která nevidí.
Odhady bezpečnosti klesají o 15 až 30 bitů
Změřený běh autoři přepočítali na delší klíče. Čísla v prvním sloupci jsou obvyklé odhady odvozené z rozkladu, ve druhém odhad ceny padělku:
| délka klíče | bezpečnost podle rozkladu | padělání podpisu | dotazů na věštce |
|---|---|---|---|
| 1024 bitů | 280 | 265 | 232 |
| 2048 bitů | 2112 | 290 | 243 |
| 4096 bitů | – | 2119 | 257 |
Rozdíl je 15 až 30 bitů podle délky klíče. Praktický dopad shrnují autoři jednou větou: ani 4096bitové RSA v tomhle modelu nedosáhne na 128 bitů bezpečnosti, které se dnes u kryptosystému považují za minimum.
Podpisů s výplní se to netýká
Drtivá většina dnešního RSA podepisuje s výplní podle PKCS#1 v1.5 nebo RSA-PSS. Ta surového věštce nenabízí, a útok proto nikam nevede. Na otázku, jestli se mají bát majitelé 2048bitových klíčů s výplní, odpovídají autoři v přiloženém seznamu častých dotazů prostým ne.
Jinak jsou na tom slepé podpisy. Nejznámější je protokol Privacy Pass, kterým Apple a Cloudflare vydávají anonymní žetony tomu, kdo jednou prošel ověřením, že je člověk. Útok na 2048bitový klíč by podle odhadu autorů stál 290 operací a 243 dotazů. Cloudflare veřejně uvádí přes sedm bilionů požadavků denně, což je zhruba právě 243; Apple naopak vydávání žetonů omezuje na jeden za minutu, takže by jediné zařízení potřebné podpisy sbíralo sedmnáct milionů let. Krátkodobě autoři radí zkrátit životnost klíčů a prodloužit je, střednědobě doplnit do protokolu důkaz s nulovou znalostí.
Klasická kryptoanalýza mluví pro odchod od RSA
Práce je zatím preprint a recenzí neprošla. Autoři sami píšou, že poplach to není: útok je praktický v akademickém smyslu, ne v tom, že by ho zvládl kdokoli, a předpoklad surového podepisovacího věštce je v praxi silný.
Jeden vedlejší údaj stojí za pozornost. Celý výpočet proběhl bez grafických karet a bez jazykových modelů, a na otázku, jestli by obojí pomohlo, autoři odpovídají, že skoro jistě ano. Uvedená čísla jsou tedy spíš strop než dno.
Argument práce míří dál než na jeden klíč. Dosavadní odhady bezpečnosti RSA vycházejí z rozkladu, a ten podle ní není jediná cesta ke klíči. Probíhající přechod na postkvantovou kryptografii je proto podle autorů příležitost opustit RSA úplně, a to i bez kvantového počítače. Kus cesty je za námi: IETF zakázal výměnu klíčů přes RSA v TLS 1.2 a postkvantové výměny klíčů popsal i pro SSH. Podpisy RSA v certifikátech, tokenech a v protokolu OAuth ale zůstávají tam, kde byly.
Zdroje: Forging 1024-bit RSA signatures in nearly SNFS time (Cryptology ePrint Archive, dokument 2026/2131), repozitář s implementací a seznamem častých dotazů, oznámení IACR z 22. září 2026 a text Dana Goodina na Ars Technice.