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. |
