# 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 $$, 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^+=$ 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 $$.

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