04-01-2013, 10:38 AM
The RSA Cryptosystem
The RSA.ppt (Size: 265.5 KB / Downloads: 28)
Is RSA a one-way permutation?
To invert the RSA one-way function (without d) attacker must compute:
M from C = Me (mod N).
How hard is computing e’th roots modulo N ?
Best known algorithm:
Step 1: factor N. (hard)
Step 2: Find e’th roots modulo p and q. (easy)
Shortcuts?
Must one factor N in order to compute e’th roots?Exists shortcut for breaking RSA without factoring?
To prove no shortcut exists show a reduction:
Efficient algorithm for e’th roots mod N
efficient algorithm for factoring N.
Oldest problem in public key cryptography.
Evidence no reduction exists: (BV’98)
“Algebraic” reduction factoring is easy.
Unlike Diffie-Hellman (Maurer’94).