Re: RSA encryption/decryption

From: Spamless (Spamless_at_Nil.nil)
Date: 09/11/05 

Date: Sun, 11 Sep 2005 00:30:06 GMT

On 2005-09-10, Unruh <unruh-spam@physics.ubc.ca> wrote:
> Spamless <Spamless@Nil.nil> writes:
>
>>On 2005-09-10, Troky <troky2001@yahoo.com> wrote:
>>> Hi all,
>>>
>>> I have question about 'breaking' and reversing 512bit RSA.
>>>
>>> I know public key N and decryption exponent d, so I can decrypt messages
>>> easily. What I need is to encrypt
>>> plaintext message back to ciphertext. I guess that I need encryption
>>> exponent e for that.
>>> So, my question is: is there any other way except factorization to get 'e'?
>
>>If you have e and d, with polynomial time work, you can factor.
>>With a factorization you can get e from d.
>
>>If you could get e from d, that is what people would use to factor.
>
>>Getting e would just be another factorization method.
>
>>Encrypting with squaring (encrypted = M^2 mod N) decrypting is provably
>>about the same amount of work as factoring (i.e. if you can find square
>>roots mod N, you can use that to factor N and vice versa). One the other
>
> Only if the length of M is greater than half the length of N. Otherwise
> taking square roots is trivial.

Ah ... I see ... I said "decrypting" - now did I mean "a method of
decrypting" or did I mean decrypting a (single) message you got.
Ah ... terminology ... it can be read either way ...

Not if you can find the square root of an "M". If you can (generally) find
square roots (and it is probabalistic, taking a random number M mod N,
squaring it, using the assumed method of taking square roots and half the
time - for N=pq, p,q primes, M relatively prime to N (if M is not rel.
prime to N, well, first check their GCD and if it is not one, you have
a factor of N) one will get an M' (taking square roots of M^2) which is
NOT either +/-M mod N. So M^2=M'^2 mod N or
(M-M')(M+M')=0 mod N and neither M-M' (M is not M' mod N) nor M+M'
(M is not -M' mod N) is congruent to zero mod N. So one of N's factors
must divide M-M' and the other M+M' and GCD(M-M',N) gives a factor of N.

Relevant Pages

  • Re: Modular arithmetic question
    ... > solve this problem when the factorization of k is unknown (and k is ... algorithm for computing square roots mod p which ... If you could quickly compute the square roots of -1 mod F_n ... F_n as the sum of two squares. ...
    (sci.math)
  • Re: RSA encryption/decryption
    ... >> I know public key N and decryption exponent d, so I can decrypt messages ... >With a factorization you can get e from d. ... taking square roots is trivial. ...
    (sci.crypt)
  • Reduction from FACTORING to SQROOT
    ... I would like to know if it exists a reduction from the factorization ... problem to the square roots problem, ... n by applying the Rabin algorithm. ...
    (sci.crypt)