Re: RSA and Number Theory

From: R Reynoldson (rreynoldson_ng_mail@yahoo.com)
Date: 02/13/03 

From: R Reynoldson <rreynoldson_ng_mail@yahoo.com>
Date: Thu, 13 Feb 2003 05:22:36 GMT

If M ^ (e ^ i) == M mod n, then d = e ^ (i - 1) (actually, you can take
d = e ^ (i - 1) mod( phi( n ) )).

Proof:

(M ^ e) ^ (e ^ (i - 1)) = M ^ (e * e ^ (i - 1))
                        = M ^ (e ^ i)
                        == M mod n.

In your example, for example, take d = e ^ 7 mod phi( n ), which is d =
831969019127. Then you have:

(514201303 ^ 61165167623 ) ^ 831969019127 == 514201303 mod 1571068647977

flip wrote:
>
> Hello,
>
> I have been messing around with the mathematics of RSA and was wondering
> something.
>
> I did an iterative attack using:
>
> pt = 514201303; {n, e} = {1571068647977, 61165167623};
>
> After doing PowerMod[pt, e^i,n] for i = 1 ... 10, I found that on the eigth
> iteration, I get the plaintext back.
>
> If I change to another plaintext, it can take more or less iterations to
> recover the plaintext.
>
> Although I see that you can recover palintext from ciphertext without need
> d, my question is this.
>
> Is there anyway to recover a valid d from this information?
>
> Thanks for any insights.

Relevant Pages

  • Re: RSA and Number Theory
    ... > iteration, ... > recover the plaintext. ... Such attacks were considered when RSA was first published. ... attack may apply here, though it is not guaranteed to succeed. ...
    (sci.crypt)
  • Re: RSA and Number Theory
    ... avoid in RSA because of the every thing you observed ... > iteration, I get the plaintext back. ... > recover the plaintext. ...
    (sci.crypt)
  • RSA and Number Theory
    ... I did an iterative attack using: ... iteration, ... If I change to another plaintext, it can take more or less iterations to ... Although I see that you can recover palintext from ciphertext without need ...
    (sci.crypt)
  • Re: A basic cryptanalysis question
    ... he assumes he's recovered the plaintext. ... but only for what is known as a ciphertext-only attack. ... include the keys in your construction. ... decryption table for F and use a meet-in-the-middle strategy to recover the ...
    (sci.crypt)
  • Re: a single OTP for a limited number of secure messages?
    ... > meet in a dark alley, and Alice hands the ... > piece of paper to Bob. ... for the plaintext to get short enough, brute-force a guess at the plaintext, ... educated guessing or brute force to recover more key material. ...
    (sci.crypt)