Pokud vím, tak není známá polynomiální redukce RSA faktorizace na problém diskrétního logaritmu, i když RSA je zmiňováno v linkovaném článku. Nemysleli spíš DSA?
Po letmém prohlížení slajdů je vidět, že na technologyreview.com nemají tušení, o čem píšou. RSA a algoritmy založené na diskrétním logaritmu (DH, DSA, El-Gamal) jsou v prezentaci zmiňované, ale v jiném kontextu.
Zajímavá novinka z tohto roku jsou práce Joux, Barbulescu, et al. o DLP v tělesech s malou charakteristikou, kolem čeho se většina prezentace točí.
Snad jediná "přímá" spojitost mezi DLP a faktorizací jsou tyto dvě věty: "Factoring tend to lead to advances in Discrete Log" a "Discrete Log advances tend to lead to advances in Factoring".
Pokiaľ ja viem, tak problém diskrétneho logaritmu priamo ohrozuje RSA týmto spôsobom:
Ja ako útočník si zvolím priamy text P, a zašifrujem ho pomocou verejného kľúča obete (e, N) a dostanem zašifrovaný text C = P ^ e (mod N). Následne formulujem kongruenciu P = C ^ d (mod N), čo je sústava dvoch kongruencií P = C ^ d (mod p) a P = C ^ d (mod q), kde N = pq. Z tejto sústavy viem jednoznačne určiť tajný kľúč d pomocou riešenia diskrétneho logaritmu v Z_p.
Či som spravil niekde chybu?
Samozrejme, že som urobil chybu. Keďže p a q nepoznám, musím vedieť riešiť diskrétny logaritmus v Z_N^*, čiže hľadať d v kongruencii P = C ^ d (mod N). Predpokladám, že keď tvrdia, že ohrozujú RSA, tak to budú vedieť riešiť aj v Z_N^*. Detaily som nevidel, tak sa k tomu neviem vyjadriť.