This isn't the hidden subgroup problem, and it isn't a hard problem
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
On 03/03/11 16:49, Billy O'Neal 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
-------------------------------------------------------------
Computer Science Student - Case Western Reserve University
http://stackoverflow.com/users/82320/billy-oneal
On Thu, Mar 3, 2011 at 11:01 AM, rachid baih<[email protected]> 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
https://docs.google.com/document/d/1sTHB52526LQW3YnU39HdZ49pXIlQKOXGAsm3oIdUELM/edit?hl=en#
--
You received this message because you are subscribed to the "Crypto++ Users"
Google Group.
To unsubscribe, send an email to [email protected].
More information about Crypto++ and this group is available at
http://www.cryptopp.com.
--
You received this message because you are subscribed to the "Crypto++ Users"
Google Group.
To unsubscribe, send an email to [email protected].
More information about Crypto++ and this group is available at
http://www.cryptopp.com.
