Sunday, December 23, 2018

elementary number theory - RSA with small encryption exponent

In RSA: Fast factorization of N if d and e are known a comment under the OPs question stated that if the encrytion exponent e is small compared to N=pq for the RSA-primes p,q (like e<N) one could find k in de=1+kφ(N) by rounding deN as k is an integer and φ(N)N.




I don't know how to show this rigorously as I don't find a way to use e<N and I'm unsure whether the floor function or some other approximation was meant. (For the following i went with the floor as it seemed to be the most reasonable)



As φ(N)N I know that:
k=1N+kdeN
As φ(N)=Npq+1 is also know that:
deN=1N+kφ(N)N=1N+kpqpq+1pq=1N+k(1N1q1p)+k

So it would be nice to have 1N+k(1N1q1p)=0 as this would show the preposition.



Does this result even hold true?

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...