View Question
Q: SWITCH QUESTION BASED ON HASH VALUE ( Answered,   1 Comment )
 Question
 Subject: SWITCH QUESTION BASED ON HASH VALUE Category: Computers > Security Asked by: israel55555-ga List Price: \$25.00 Posted: 20 Oct 2002 20:56 PDT Expires: 19 Nov 2002 19:56 PST Question ID: 85706
 ```For this question you will digitally sign a message to send to George using RSA. The message to be signed M, is obtained as follows. Convert the digits: 1 8 8 6 3 6 6 4 into a 32 binary number. Now add all the 1s in this binary number. The total number of ones is the message M. The values that have been given to you are: p = 3, q = 11, Your key pair e = 11, d = 7 George's key e' = 13, d' = 5 What is the value of the signed message?``` Request for Question Clarification by rbnn-ga on 20 Oct 2002 23:50 PDT ```I don't think your key pair is valid for the values of p=3 and q=11 . For the key pair to be valid, the secret key should be a multiplicative inverse to the public key modulo phi(p*1) = phi(33)=((3-1)*(11-1))= 20 . But 11*7 is not equal to one mod 20, so I don't think your key pair is valid. (If this is the correct answer I'd be happy to post it as one!) A brute force application of RSA does yield (12,12) for the message and signature.``` Request for Question Clarification by rbnn-ga on 21 Oct 2002 07:15 PDT ```There is a typo in my request for question clarification: the phrase "multiplicative inverse to the public key modulo phi(p*1)" should read "multiplicative inverse to the public key modulo phi (p*q)"``` Clarification of Question by israel55555-ga on 21 Oct 2002 09:31 PDT ```The format of the question is valid. Please try to solve it according to the numbers provided. I confirmed that the structure of the question is correct.``` Clarification of Question by israel55555-ga on 21 Oct 2002 09:40 PDT `Please show all work needed.` Request for Question Clarification by rbnn-ga on 22 Oct 2002 10:19 PDT ```I appreciate your checking that the problem is correct. If you don't mind, I would like to expand a little bit more on why I am still concerned about the correctness of the problem. There are many descriptions of RSA on the web, for example, http://world.std.com/~franl/crypto/rsa-guts.html . Here we have: p: 3 q: 11 e: 11 d: 7 Now, mathematically we know this CANNOT be a valid RSA data because e*d=77 is not congruent to 1 mod (p-1)(q-1) since (p-1)(q-1)=2*10=20 . You might be thinking: what does this matter? Why can't we still use RSA? Well, because the problem with this set of p,q,e, and d is that when I try to encrypt something with my secret key, sometimes it will not decrypt to the same message! Let's suppose for example that the message to be encrypted is 7. Then to ENCRYPT I compute ciphertext= (message ^ e) mod (p*q) = 7^11 mod 33 = 7 To decrypt I compute plaintext = (ciphertext ^ d) mod (p*q) = (7 ^ 7) mod (33) = 28 This is NOT THE SAME as the original message. So you see, RSA just cannot work with the p,q, public key and private key given.``` Request for Question Clarification by rbnn-ga on 24 Oct 2002 22:19 PDT ```Is it OK with you if I repost my request for answer clarification, which demonstrates that the p/q d/e pair is not valid for RSA, as an answer, including how the message would be done if it were valid?```
 ```Thank you for your question; I'm reposting my answer clarifications as an answer, as for the values given in the question, that analysis seems to be the only one possible. The p,q,e,d values are not valid for RSA, as explained in the clarification above. This is because e*d is not congruent to 1 modulo (p-1)*(q-1). Therefore, I will answer the question as if the p,q,e,d values were valid, then I will recapitulate the reasons for the invalidity of the question. We first get the value of the message to be signed. By the phrase "Convert the digits: 1 8 8 6 3 6 6 4 into a 32-bit binary number" I am going to assume is meant: "Convert each digit into a byte and append the bytes to get the 32-bit number". The binary representation of each digit, follows; the 32-bit number is their concatenation: 1 8 8 6 3 6 6 4 0001 1000 1000 0110 0011 0110 0110 0100 We add the number of ones here to get the message: 1 + 1 + 1 +2 +2 +2 +2 +1 = 12 . Hence the message to be signed is 12. (Note that this seems more like a message hash than a full message to me, but I am just following the instructions in the problem). The digital signature of the message is simply 12^d (mod p*q) = 12^7(mod 33) = 12 For the last step I used a calculator (actuall a Java interpreter). Thus, you need to send the message pair: (12,12) Now, there are two key points one should mention: The first is that this message is sent in plaintext: the message itself is not encrypted. This is what the question asks for, but you might want to check that this is what is required. The second point is that I am sending the (message,signature) as a pair. In reality, there will be some way of appending the signature to the message to create one long bitstream. However, I don't think the problem is asking for this. To verify the signature, George applies your public key to the signature, 12, to get: M^e(mod p*q) =12^11(mod 33) =12 which equals the plaintext message, so George knows that the message was indeed sent correctly. Let me conclude once again by reiterating that RSA just won't work with the p,q,d,e values given, although it does happen to work in this example. For completeness, I will include my earlier answer clarification demonstrating this fact here: There are many descriptions of RSA on the web, for example, http://world.std.com/~franl/crypto/rsa-guts.html . Here we have: p: 3 q: 11 e: 11 d: 7 Now, mathematically we know this CANNOT be a valid RSA data because e*d=77 is not congruent to 1 mod (p-1)(q-1) since (p-1)(q-1)=2*10=20 . You might be thinking: what does this matter? Why can't we still use RSA? Well, because the problem with this set of p,q,e, and d is that when I try to encrypt something with my secret key, sometimes it will not decrypt to the same message! Let's suppose for example that the message to be encrypted is 7. Then to ENCRYPT I compute ciphertext= (message ^ e) mod (p*q) = 7^11 mod 33 = 7 To decrypt I compute plaintext = (ciphertext ^ d) mod (p*q) = (7 ^ 7) mod (33) = 28 This is NOT THE SAME as the original message. So you see, RSA just cannot work with the p,q, public key and private key given. References: ---------- In addition to the link above, I used the standard textbook Contemporary Cryptology, by Gustavus Simmons (ed), IEEE Press, 1991. I also used the standard work on cryptography, Applied Cryptography, by Bruce Schneier. John Wiley and Sons, 1995. I had also done research into RSA at a previous job where I was involved in implementing SSL, a transport method over TCP/IP that often uses RSA, so some of this is based on personal experience.```
 ```For p=3,q=11, 'e' is a number chosen to be less than, and which shares no factors with the product(p-1)*(q-1)=20. If you choose e=11 than d its an integer that obeys the equation: d*e MOD [ product ] = 1, in this case: d * 11 MOD 20 = 1 So, the only acceptable value for d is 11, NOT 7. This is, in my opinion, the first mistake in the question. The second, which does not afect the results, is that we don't need to know George's keys to send him a signed message.```