Re: RSA encryption/decryption

From: Unruh (unruh-spam_at_physics.ubc.ca)
Date: 09/10/05

  • Next message: Troky: "Re: RSA encryption/decryption" 
    Date: 10 Sep 2005 21:31:34 GMT

    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.

    >hand I don't believe anyone has proven that finding, say, cube roots mod N
    >(say d=3 - find e, that is solve M^3=X mod N for M), is not much easier than
    >finding square roots. Perhaps there is a way to decode which does not use
    >"raising to a power" (e with de=1 mod lambda(N)) and which does not lead to
    >a factorization method. If that were the case, then one might be able to get
    >e without being able to factor. I don't know if there are many who think
    >that taking, say, 17th roots mod N is easier than finding square roots.

  • Next message: Troky: "Re: RSA encryption/decryption"

    Relevant Pages

    • 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. ... that taking, say, 17th roots mod N is easier than finding square roots. ...
      (sci.crypt)
    • Re: RSA encryption/decryption
      ... Troky wrote: ... > I know public key N and decryption exponent d, so I can decrypt messages ... is there any other way except factorization to get 'e'? ...
      (sci.crypt)
    • Re: RSA encryption/decryption
      ... Troky wrote: ... > I know public key N and decryption exponent d, so I can decrypt messages ... is there any other way except factorization to get 'e'? ...
      (sci.crypt)
    • 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
      ... >>If you have e and d, with polynomial time work, you can factor. ... >>Getting e would just be another factorization method. ... square roots (and it is probabalistic, taking a random number M mod N, ... must divide M-M' and the other M+M' and GCDgives a factor of N. ...
      (sci.crypt)