Kdybychom mohli projít seznam prvočísel rychle (ve smyslu máme vzoreček pro výpočet příštího prvočísla vyčíslitelný za pár taktů CPU), ještě to nic neznamená. Když budu uvažovat RSA-2048, mám 2048b modulus, který je součinem dvou prvočísel o délce cca 1024b. Počet prvočísel zde lze odhadnout na 2^1024/(ln(2^1024)-1), což mi kalkulačka nepobrala, ale dá se to zjednodušit, že cca každé (ln(2^1024)-1)-té číslo v tomto intervalu je prvočíslo. Sice ani ln(2^1024)-1 mi kalkulačka nepobrala, ale když jsem to zjednodušil na 1024*ln(2)-1, dostal jsem, že cca jedno ze 709 čísel je v tomto intervalu prvočíslo. To jsem zaokrouhlil na 1024 a došel jsem k výše uvedenému odhadu 2^(1024-10)=2^1014 prvočísel v tomto intervalu. Řekl bych, že ani dnes není problém v tom, že bychom neuměli dostatečně rychle prvočísla procházet, jako spíš s tím, že je jich prostě moc. Hrubou silou to při jakkoli efektivním způsobu procházení prostě neprojdete. Pro srovnání: AES staví mj. na tom, že neprojdete všech jeho 2^128 až 2^256 (podle varianty) klíčů. To je o poznání méně než počet prvočísel v uvažovaném rozsahu.
Jestli to zefektivní nějaký jiný algoritmus lámání RSA – možná ano, čekal bych ale spíše zlepšení nějakých faktorů, rozhodně ale od toho nečekám polynomiální složitost. Prakticky to znamená, že čekám spíše přinejhorším nutnost používat delší klíče v RSA než kompletní průlom RSA.
A i kdybychom měli průlom RSA, není to dnes nenahraditelný algoritmus… Náhrady se hledají asi spíše z jiných důvodů – rychlost, délka klíče nutná k zajištění dané úrovně bezpečnosti a kvantové počítače.
s: Ale vždyť to používání známých prvočísel vyvracím.
63 Odpovědí
16014 Zhlédnutí