Práce obsahuje rozší?enou verzi p?ísp?vku z letošní konference CRYPTO 2004. Je zde popsán deterministický polynomiální algoritmus, který ze znalosti (
N,
e,
d), kde
N je modul RSA,
e je ve?ejný a
d privátní exponent, nalezne prvo?íselné faktory
p a
q modulu
N. Tím je prokázána polynomiální ekvivalence úlohy faktorizace modulu
N a prolomení klí?e RSA. Vylepšením oproti p?edchozímu stavu je, že tato ekvivalence se opírá o deterministický algoritmus, zatímco d?ív?jší výsledek se opíral o algoritmus pravd?podobnostní (všeobecn? dob?e známý, který byl mj. popsán už v originálním ?lánku Rivesta, Shamira a Adlemana z roku 1978).
P?ísp?vek si s ohledem na p?ímou souvislost s prokazováním teoretické bezpe?nosti RSA zaslouží delší komentá?: Je nutné upozornit na možnou zám?nu s dokazováním vztahu mezi problémem faktorizace modulu
N a problémem inverze RSA. Úloha inverze RSA je zadána takto:
Máme dán ve?ejný klí? (N, e) a hodnotu y, y = x^e mod N. Úkolem je najít x. Velkou výzvou pro kryptology je ukázat, zda
tato úloha je ?i není ekvivalentní s faktorizací modulu
N. Sami auto?i ?lánku, a? už v?dom? nebo „omylem“, ve svém p?ísp?vku pon?kud podporují dojem, že jejich výsledek mí?í tímto sm?rem. Proto dopl?uji, že vztah mezi t?mito dv?ma problémy, který je z hlediska bezpe?nosti RSA podstatn? významn?jší než p?edchozí, v ?lánku adresován není. Ani se nezdá, že bychom díky diskutované práci byli jeho vy?ešení n?jak blíž.
Uvedeným komentá?em nechci ?lánek samoz?ejm? nijak zatracovat. Naopak. Je to další velmi zajímavá aplikace teorie celo?íselných m?ížek (a fenomenálního algoritmu Lenstra-Lenstra-Lovász) v kryptologii, která ur?it? stojí za p?e?tení. P?i praktickém ?ešení daného problému bych ovšem sáhl spíše po pravd?podobnostním algoritmu popsaném nap?íklad v Bonehov? p?ehledové práci
Twenty Years of Attacks on the RSA Cryptosystem . To je ovšem nakonec dob?e známý jev: Význam deterministických polynomiálních algoritm? je ?asto spíše teoretický, v praxi vládnou pravd?podobnostní „d?evorubci“...
