Re: RSA algorithm
From: Spamless (Spamless_at_Nil.nil)
Date: 07/07/03
- Previous message: Spamless: "Re: RSA"
- In reply to: vicky: "RSA algorithm"
- Next in thread: Mark Wooding: "Re: RSA algorithm"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: 6 Jul 2003 18:21:01 -0400
In article <35dab32c.0307060215.6219dabb@posting.google.com>, vicky wrote:
> Any idea?
>
> Suppose that the public key of RSA is (n,e) and C=M^e (mod n). An
> algorithm A can invert 1% of the inputs in form y=M^e (mod n). Prove
> that using algorithm A we can invert every input with high
> probability.
> Thank you :)
Given U=M^e mod n
Generate your own random x and calculate V=x^e mod n
You know x and V.
Look at UV=(Mx)^e mod n.
If you can invert that you know Mx and x mod n and
can divide (Euclidean algorithm) to get M.
If you can't invert, try another random x.
If you can invert a decent percentage of random messages,
you can invert all (with high probability - i.e. the x's
you choose don't happen to give non-invertible messages
all the time).
- Previous message: Spamless: "Re: RSA"
- In reply to: vicky: "RSA algorithm"
- Next in thread: Mark Wooding: "Re: RSA algorithm"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
