Another way to CRACK RSA
rachid baih
The public key is (n = 5183, e = 8609).
The private key is (n = 5183, d = 209).
m= 127 to encrypt
c =
127^8609 mod 5183
c =
2324
to decrypt c = 2324
2324 ^8609 mod 5183 = 3748
3748 ^8609 mod 5183 = 123
123 ^8609 mod 5183 = 2257
2257^8609 mod 5183 = 3247
3247^8609 mod 5183 = 127
127 ^8609 mod 5183 = 2324
Now we have successfully decrypted c with m = 127
Take any number c ( rsa encrypted message) You can continue encrypting
process (with rsa function )
no matter what number c you start with, you will always eventually
reach
m the decrypted message.
plez visit
https://docs.google.com/document/d/1sTHB52526LQW3YnU39HdZ49pXIlQKOXGAsm3oIdUELM/edit?hl=en#
Billy O'Neal
The basic idea is that the RSA function is periodic (it does involve a
modulus after all), so applying it to the same message over and over
again should result in a cycle back to the cleartext (if the author of
the presentation indicated is correct). While this is true, there's no
way for the attacker to know when they've cycled back around to the
message text, unless (s)he can control what the plaintext message is.
And if the attacker already knows part of the plaintext, RSA is
already broken ->
http://en.wikipedia.org/wiki/RSA#Attacks_against_plain_RSA .
This is why RSA messages are padded with pseudorandomized data, to
prevent attackers from determining these kinds of things.
Please correct me if I am wrong.
Billy3
-------------------------------------------------------------
Computer Science Student - Case Western Reserve University
http://stackoverflow.com/users/82320/billy-oneal
> --
> You received this message because you are subscribed to the "Crypto++ Users" Google Group.
> To unsubscribe, send an email to cryptopp-user...@googlegroups.com.
> More information about Crypto++ and this group is available at http://www.cryptopp.com.
rachid baih
process (with rsa function )
no matter what number c you start with, you will always eventually
then m = c-1
function is periodic
On 3 mar, 16:49, "Billy O'Neal" <billy.on...@gmail.com> wrote:
> If I'm reading this right, it's nothing new.
>
> The basic idea is that the RSA function is periodic (it does involve a
> modulus after all), so applying it to the same message over and over
> again should result in a cycle back to the cleartext (if the author of
> the presentation indicated is correct). While this is true, there's no
> way for the attacker to know when they've cycled back around to the
> message text, unless (s)he can control what the plaintext message is.
> And if the attacker already knows part of the plaintext, RSA is
> already broken ->http://en.wikipedia.org/wiki/RSA#Attacks_against_plain_RSA.
>
> This is why RSA messages are padded with pseudorandomized data, to
> prevent attackers from determining these kinds of things.
>
> Please correct me if I am wrong.
>
> Billy3
> -------------------------------------------------------------
> On Thu, Mar 3, 2011 at 11:01 AM, rachid baih <sta_s...@hotmail.com> wrote:
> > A worked example
> > The public key is (n = 5183, e = 8609).
> > The private key is (n = 5183, d = 209).
>
> > m= 127 to encrypt
> > c =
> > 127^8609 mod 5183
> > c =
> > 2324
>
> > to decrypt c = 2324
>
> > 2324 ^8609 mod 5183 = 3748
>
> > 3748 ^8609 mod 5183 = 123
>
> > 123 ^8609 mod 5183 = 2257
>
> > 2257^8609 mod 5183 = 3247
>
> > 3247^8609 mod 5183 = 127
>
> > 127 ^8609 mod 5183 = 2324
>
> > Now we have successfully decrypted c with m = 127
>
> > Take any number c ( rsa encrypted message) You can continue encrypting
> > process (with rsa function )
> > no matter what number c you start with, you will always eventually
> > reach
> > m the decrypted message.
> > plez visit
rachid baih
i use
The public key (n = 5183, e = 8609).
i continue to encrypt 2324 to reach 2324
one gets the sequence
2324, 3748 , 123,
2257, 3247, 127,2324
then is esy to find m
m = 127
Mike Hamburg
does not work so well for large N. You might want to try running this
on a realistic-sized RSA key before claiming to have broken RSA.
In particular, here Zn* ~= Z2 * Z2520. Now 2520 = 2^3 * 3^2 * 5 * 7 has
no large prime factors, and in fact Z2520* ~= Z2^2 * Z3 ^2 * Z4^2 which
has exponent 12. So every e will always cycle after 12 encryptions, or
after some number dividing 12 (in your example, 6).
However, on a real-life RSA modulus, phi(N) will almost certainly have
at least one very large prime factor q -- and if not, you can factor N
anyway by known techniques (and by your technique -- notice that
gcd(C-3247,N)=71 is a factor of N). So for essentially all e, the
period of this sequence will be on the order of q-1, which is too large
to iterate over.
Cheers,
Mike
Mike Hamburg
either. Rachid has already pointed out that you can check it by
encrypting one more time, and seeing if you get C.
Also, having now read the Google doc, I'd like to point out that Rachid
assumes that factoring takes either p time or sqrt(p) time (didn't
entirely understand which...). But actually, there are factoring
algorithms which are much faster than that; see
http://en.wikipedia.org/wiki/Integer_factorization for more details.
RSA keys are chosen to be long enough that these algorithms are too
slow, and similarly, Rachid's algorithm is also too slow for real-world N.
-- Mike
On 03/03/2011 09:04 AM, Antony Vennard wrote:
> You're right; it's called the hidden subgroup problem.
>
> Antony
>
> http://stackoverflow.com/users/257111/ninefingers
David-Sarah Hopwood
> Take any number c ( rsa encrypted message) You can continue encrypting
> process (with rsa function )
> no matter what number c you start with, you will always eventually
> reach m the decrypted message.
This amounts to just a very inefficient way to do a brute-force search for d.
Billy O'Neal wrote:
> there's no way for the attacker to know when they've cycled back around
> to the message text, unless (s)he can control what the plaintext message is.
That's not the problem. For secure RSA padding schemes you could recognize
a valid plaintext easily enough, if it were feasible to do the number of
encryptions required, which it isn't.
--
David-Sarah Hopwood ⚥ http://davidsarah.livejournal.com
Florian Weimer
> tanks
> Take any number c ( rsa encrypted message) You can continue encrypting
> process (with rsa function )
> no matter what number c you start with, you will always eventually
> reach c the encrypt message.
> then m = c-1
> function is periodic
I think this is sometimes called "superencryption" in the literature.
I cannot find the original paper from Simmons and Norris, but here is
Rivest's rebuttal: