wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> RSA Glitch Hack
        
(Message started by: william wu on Mar 14th, 2004, 10:02pm)
Title: RSA Glitch Hack
Post by william wu on Mar 14th, 2004, 10:02pm
This problem is about RSA, the famous cryptosystem used all over cyberspace. My next post will have a quick textbookish description of how RSA encryption and RSA signatures work, which you can read if necessary. No special CS background is needed for this problem. The solution only involves very basic number theory.


Problem:

Modulus: N = pq, where p and q are primes
Public Encryption exponent: e
Private Decryption exponent: d

Suppose we are computing our RSA signature S of a message M using these parameters. Then we wish to compute S = Md mod N. Rather than doing this computation directly, we use a trick to speed up the computation. The trick is to separately compute

S1 = Md mod p
S2 = Md mod q

and then combine these values via the Chinese Remainder Theorem to get S. This speedup trick is almost always done in real-world practice.

Now, suppose that we are computing the signature of M using this speed up trick, and a hardware glitch causes our computation of C1 to be incorrect, although C2 is still correct. But we are unaware that such a glitch occurred, and so we proceed to publish both M and its invalid signature S'.


Suppose Carol is an eavesdropper who obtains a copy of both M and S'. Show that she can factor the modulus N, thereby completely compromising the cryptosystem. (Having factored the modulus she can now forge our signature on any document.)
Title: Re: RSA Glitch Hack
Post by william wu on Mar 14th, 2004, 10:52pm
My whirlwind summary of RSA. If you haven't learned about this before, I hope you find this an interesting read :)

Motivation

Imagine that Alice wants to send a love letter to Bob via the mail. She wants it to be secret, such that if any unscrupulous postman tries to look at what she's sending, the postman won't have any idea what he's looking at. Well, here's one solution: put the letter in a safe, lock the safe with a big padlock, and give Bob beforehand a copy of the padlock key. Then the postman won't be able to open the safe, but only Bob (and Alice herself) will be able to. Sounds good right? But there's something paradoxical about all this. If Alice and Bob were able to securely exchange the padlock key a priori, they could've just exchanged the letter instead of the keys!  :P So what we'd really like is a solution that doesn't require a symmetric key exchange a priori. Luckily, RSA offers a solution.


RSA Encryption

Alice wants to send a message M to Bob. She intends to encrypt this message such that an eavesdropper can't glean any information, and Bob is able to decrypt it.

Bob has a public key denoted by the 2-tuple (N,e), where N is a large composite number (larger than M), and e is an exponent.

So Alice looks up Bob's public key in some directory of keys. Then she computes and sends the ciphertext C = Me ( mod N ).

Upon reception of C, Bob uses his private key d to recover M:
M = Cd. Done.

So why does this work? Well, the computation C = Me ( mod N ) works as an encryption because there is no known efficient algorithm for inverting the operation, if the only values you know are the public values e and N. However, there does exist a secret decryption exponent d which allows Bob to easily invert the operation! And only Bob knows this decryption key.

Thus the RSA encryption operation can be thought of as a one-way trapdoor function. It is a one-way function since given C, it is hard to find the M such that C = Me ( mod N ). But it is also a trapdoor function since there exists a piece of information d which allows the operation to be easily inverted.

Finally, note that Alice and Bob didn't have to share a secret a priori. This is nice.


Using RSA to write Signatures

Just as we can use RSA to encrypt messages, we can also use it to write digital signatures.

A signature in the digital world serves the same purposes that you'd expect in the real world. A signature proves that a message was written by, or approved by, a particular person. It should be unforgeable, so no one can reproduce your signature. And it should be verifiable -- that is, anyone can show your signature to a judge, and the judge will be able to verify that the signature came from you.

We can use RSA to make digital signatures by putting a twist on the encryption procedure, running it almost backwards. Suppose I have an RSA public key (N,e) and a private key d. Then I can write a signature S for the document M by computing S = Md mod N. Since only I know the key d, my signature for this document is unforgeable. [smiley=maltese.gif] And a judge can verify my signature by checking if Se mod N = M.  This is the RSA signature procedure referred to in the first post.


[smiley=maltese.gif] I had to be careful with the wording here. The astute reader might realize that existential forgeries are possible with the RSA signature scheme. You can choose a random message R, and then compute the encryption X = Re mod N, using my public key values (N,e). Then R really is my signature on the message X. However, X is most likely a meaningless thing, since it is an RSA ciphertext. So you have only obtained a signature forgery for a garbage document. And there is no known efficient way to first choose the message X and then compute my signature on X, for if such an algorithm existed, the RSA encryption cryptosystem would also be broken. So no worries. As a last note, one way of defending against this existential forgery attack is to use hash functions in conjunction with signatures.


[smiley=spadesuit.gif] It should be noted that RSA as naively described in this post is vulnerable to a endless carnival of attacks. Real-world RSA involves various preprocesssing and padding procedures (OAEP). Generally, designing secure real-world implementations of cryptosystems is very difficult.
Title: Re: RSA Glitch Hack
Post by Eigenray on Mar 15th, 2004, 12:45am
Note that de = 1 mod [phi](N).
We also have:
S' = S1' [ne] S1 mod p
S' = S2 = S mod q.

Hint: [hide]S1'e [ne] S1e mod p[/hide].
Proof: Otherwise, we'd have [hide](S1'/S1)e = 1 mod p, and t | e, where t>1 is the order of (S1'/S1).  But we also have t | (p-1), so t | (e,p-1), which would contradict e being invertible mod [phi](N) = (p-1)(q-1)[/hide].

Now, Carol simply notes that[hide] mod p,
S'e = S1'e [ne] S1e = M
while mod q,
S'e = S2e = M.
So (S'e - M) is divisible by q, but not by p.  Therefore Carol may easily compute (S'e-M, N) = q, and N/q = p[/hide] (and proceed to compute the private key d = e-1 mod (p-1)(q-1)).
Title: Re: RSA Glitch Hack
Post by Barukh on Mar 15th, 2004, 9:32am
Hmm, it seems much more needs to be learned about RSA system to approach this problem...  ::) I still don't understand Eigenray's hints.

Nice problem, William  :D!
Title: Re: RSA Glitch Hack
Post by Barukh on Mar 18th, 2004, 8:56am
OK, finally I understood the matter.

Very nice solution, Eigenray!  :D


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board