Theory matters

Notes from a student of Computer Science at the University of Pisa

RSA Encryption and Sign (by hand!)

with one comment

A bit of (usual) notation:

  • C(m, K_{A}^+) means << I encrypt the message m with A’s public key K^+ >> and
  • D(m, K_{A}^-) is << I decrypt the encrypted message c with A’s private key K^- >>
  • Let be h(m) an hash function that returns the hash value of m

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 f = D(h(m), K_{U}^-) of the message m with his private key, and encrypts the message with V’s public key: C(m, K_{V}^+). U sends to to V the tuple <ID_U, c, f>, where ID_U is U’s identifier.
  • S is the only one that can decrypt c with his private key: m = D(c, K_{V}^-). S now computes the hash of m and checks that is equal to C(f, K_{U}^+): 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 K^+=<e, n> with n = pq where p and q two primes, and K^- = d = {k \phi(n) + 1 \over e}. e is just a random number such that e<\phi(n) and gcd(e, \phi(n))=1. Encryption and decryption are easy :) !

C(x, K^+) = x^e \bmod n and D(x, K^-) = x^d \bmod n.

  • U wants to send the message m=28 to V. Assume that h(m)=3.
  • U chooses p_U = 5 and q_U=13 for his keys.
  • V chooses p_V = 7 and q_V=11.

So, n_U = p_{U}q_U =5*13=65, \phi(n_U)=(5-1)(13-1)=48. e_U could be 5 because \gcd(5, 48)=1. The first k such that d_U is integer is k=3, so d_U = {3*48+1 \over 5} = 29.

Similarly n_V=77, \phi(n_V)=60, e_V=7 and d_V=43 (with k=5).

Let’s calculate the sign:f=D(h(m), K_{U}^-)=h(m)^{d_U} \bmod n_U=h(28)^{29} \bmod 65=48. Here it is the encrypted message for V: c = C(m, K_{V}^+) = m^{e_V} \bmod n_V = 28^7 \bmod 77 = 63 (for these big numbers calculations look my previous post on modular exponentiation). So U sends <f=48, c=63>.

V “encrypts” the sign: f^{e_U} \bmod n_U=48^5 \bmod 65=3 which is h(28), good. V decrypts c as c^{d_V} \bmod n_V=63^43 \bmod 77=28.

Algebra works! …but I suspected it :)

Written by C.Santini

February 1, 2009 at 11:00 pm

Posted in Cryptography

One Response

Subscribe to comments with RSS.

  1. Hey There. I found your weblog the usage of msn.
    This is a very neatly written article. I’ll make sure to bookmark it and return
    to learn extra of your helpful info. Thank you for the post.
    I will certainly comeback.


    December 1, 2013 at 4:05 pm

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Get every new post delivered to your Inbox.

%d bloggers like this: