Hlavní navigace

Vlákno názorů ke zprávičce Pokrok v matematice způsobí do pěti let nepoužitelnost šifrování RSA od kallsyms - Pokud vím, tak není známá polynomiální redukce RSA...

  • Aktualita je stará, nové názory již nelze přidávat.
  • 7. 8. 2013 14:50

    kallsyms

    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 technologyrevi­ew.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 Fac­toring".

  • 7. 8. 2013 17:24

    grepo (neregistrovaný)

    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?

  • 8. 8. 2013 11:13

    grepo (neregistrovaný)

    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ť.