General description 1/4

RSA algorithm can be used for encryption and decryption of communication and also for digital signature. Protocol was introduced by Ron Rivest, Adi Shamir and Leonard Adleman in 1977. Security of protocol relies on difficulties of decomposition of natural number into prime numbers.

Mathematical background 2/4

Before definition of RSA protocol we remind some mathematical facts.

Euler's phi function

For natural number \(n\), \(\phi(n)\) denote a cardinality of set of numbers among \(1,2,..,n\) coprime with \(n\):
If we do not know prime numbers dividing \(n\) it is hard to compute a value of \(\phi(n)\).
Otherwise, if we know prime numbers dividing \(n\) we have: \[\phi(n)=n\Pi_{p|n}(1-\frac{1}{p}) \]

Fermat's Little Theorem

Theorem states that for every coprime natural number \(n\) and \(a\) and \(n\) we have \[a^{\phi(n)}=1 (\textrm{mod}\ n)\]

RSA protocol 3/4

Key generation

We choose two secret prime number \(p\), \(q\), then compute \(n=pq\) and \(\phi(n)=(p-1)(q-1)\). Next we choose \(a\) natural number smaller than n and coprime with n. Using Euclidean algorithm we find b such that \(ab=1 (\textrm {mod }\ \phi(n))\) (so \(ab=1+\phi(n)k\) for some \(k\)). Public key is a pair of numbers \((a,n)\), and private key is a pair \((b,n)\).

Encryption

To encrypt a message \(M\) we divide it into a blocks \(M=m_{1},m_{2},...\) such that each block as a number is smaller than \(n\). Next for every \(i\) compute \(c_{i}= m_{i}^{a}\). Finally a cipher is a sequence \(C=c_1,c_2,...\).

Decryption

To decrypt a ciphertext \(c_{i} \) we must compute \(d_{i}= c_{i}^{b}\)

Protocol analysis 4/4

Note that, decryption of ciphertext \(c_i\) gives a text \(m_i\): \(c_{i}^{b}=m_{i}^{ab}=m_{i}^{1+ \phi(n)k}=m_{i}(m_{i}^{\phi(n)})^k=m_{i}1^k=m_{i}\).