RSA Encryption and Sign (by hand!)
A bit of (usual) notation:
- means << I encrypt the message with A’s public key >> and
- is << I decrypt the encrypted message with A’s private key >>
- Let be an hash function that returns the hash value of
The user U wants to talk with the server V through a secure channel. How can V be sure that he his really receiving messages from U and not from another user between them ?
- U computes the sign of the message with his private key, and encrypts the message with V’s public key: . U sends to to V the tuple , where is U’s identifier.
- S is the only one that can decrypt with his private key: . S now computes the hash of and checks that is equal to : if it’s so, the message has really been sent by U.
Here it is an example with the RSA algorithm and little numbers. Recall that with where and two primes, and . is just a random number such that and . Encryption and decryption are easy :) !
- U wants to send the message to V. Assume that .
- U chooses and for his keys.
- V chooses and .
So, , . could be because . The first such that is integer is , so .
Similarly , , and (with ).
Let’s calculate the sign:. Here it is the encrypted message for V: (for these big numbers calculations look my previous post on modular exponentiation). So U sends .
V “encrypts” the sign: which is , good. V decrypts as
Algebra works! …but I suspected it :)