CNS - 23 - Asymmetric Cryptography II
Lecture Info
Date:
Lecturer: Giuseppe Bianchi
Slides:
Introduction: In this lecture we started talking more in depth about asymmetric cryptography.
1 The RSA Cryptosystem
The RSA is widely deployed, ultra-well known, and it is the first public key cryptography. It can also be used as a digital signature system.
The asymmetric problem used in the RSA crypto system is different from the one used by the Diffie-Hellman key agreement. The problem they found was the prime number factoring problem, which asks the following: given \(N = p \cdot q\), where \(p\) and \(q\) are very large prime, it is hard to factor \(N\). So far all algorithms found to factor have exponential complexity.
In RSA the both the encryption and the decryption are done through modular exponentiation:
The encryption of a message using \(\{N, P_k\}\), where \(N\) is the modulus and \(P_k\) is the public key of the user is done as follows
\[\text{ciphertext} = (\text{message})^{P_k} \mod N\]
The decryption of a message using \(\{N, S_k\}\), where \(N\) is the modulus and \(_k\) is the private key of the user is done as follows
\[\text{message} = (\text{ciphertext})^{S_k} \mod N\]
We will now describe the main principle behind the RSA cryptosystem: Euler's theorem.
1.1 Euler's Theorem
For us a string is a number \(m\). The value of the message \(m\) must be shorter than some other value \(N\). Notice that the function \(m^x \mod N\) is a periodic function. The following examples illustrate this:
If \(N = 10 = 2 \cdot 5\) and \(m = 3\) the period is \(4\).
\[3^x \mod 10 = \{3, 9, 7, 1, 3, 9, 7, 1, \ldots\}\]
If \(N = 10\) and \(m = 7\) the period is still \(4\).
\[7^x \mod 10 = \{7, 9, 3, 1, 7, 9, 3, 1, \ldots\}\]
If \(N = 10\) and \(m = 9\) the period is instead \(2\)
\[9^x \mod 10 = \{9, 1, 9, 1, 9, 1, \ldots\}\]
The maximum period of \(m^x \mod N\) can be computed using Euler Theorem (also known as Euler-Fermat Theorem, or Euler's Totient Theorem). It says that the maximum period of the function is the value of the Euler's Totient function \(\Phi(N)\). More formally, it says that if \(m\) is coprime with \(N\), i.e. if \(\text{GCD}(m, N) = 1\), then
\[m^{\Phi(N)} \mod N = 1\]
1.1.1 Computing \(\Phi(N)\)
The computation of \(\Phi(N)\) can be broken down depending on the value of \(N\):
If \(N = p\) with \(p\) prime, then
\[\Phi(p) = p-1\]
If \(N = p \cdot q\) with \(q\) and \(q\) prime, then
\[\Phi(N) = \Phi(p \cdot q) = \Phi(p) \cdot \Phi(q) = (p-1) \cdot (q-1)\]
If \(N = p^k\) then
\[\Phi(p^k) = \Phi(p) \cdot p^{k-1} = (p-1) \cdot p^{k-1}\]
If \(N = p_1^{k_1} \cdot \ldots p_z^{k_z}\) then
\[\Phi(N) = (p_1 - 1)p_1^{k_1 - 1} \cdot \ldots (p_z - 1) p_z^{k_z - 1}\]
Notice that for our purposes the only case we're interested in is the second one, which tells you how to compute \(\Phi(N)\) when \(N\) can be expressed as the product of two primes.
1.1.2 Consequence
The main consequence of Euler's Theorem is that when working with numbers \(m^x \mod N\) with \(m\) and \(N\) coprime, then we have that
\[m^x = m \mod N \iff x = 1 \mod \Phi(N)\]
1.2 RSA Construction
The RSA construction works as follows:
Generate two large primes \(p, q\) which must remain secret.
Compute RSA module \(N = p \cdot q\), which can be made public.
Compute \(\Phi(N) = (p-1)(q-1)\), which must remain secret.
Generate a public key \(1 < e < \Phi(N)\) such that \(e\) is coprime with \(\Phi(N)\).
Generate a private key \(d\) such that \(e \cdot d = 1 \mod \Phi(N)\).
The idea of RSA is to give you an exponent (public key) \(e\), such that given a message \(M\) we have that \((M^e)^d = M \mod N\).
As far as the encryption and decryption operations are concerned, we have the following
The encryption operation is done as follows
\[C = M^e \mod N\]
The decryption operation is done as follows
\[\begin{split} M &= C^d \mod N \\ &= (M^e)^d \mod N \\ &= M^{ed} \mod N \\ &= M^1 \mod N \\\ \end{split}\]
Typically both \(e\) and \(d\) should be choosen to be in the middle of the possible range from \((0, \Phi(N))\). The important thing is to have \(d\) large. If you choose your public key to be too small there are some crypto attacks which can leave you vulnerable.
1.3 RSA Security
The security of this construction relies on the fact that, given \(N\), it must be hard to find factors \(p\) and \(q\), and hence it is hard to find \(\Phi(N)\); finally, without \(\Phi(N)\), it is hard to compute \(d\) from \(e\).
In particular we have the following decryption challenge: given a public key \(N\), \(e\) and an encrypted message \(m^e\), computing the decryption key \(x\) such that \((m^e)^x = m \mod N\) is hard unless you know how to compute \(\Phi(N)\).
1.4 Toy Example
Consider the following primes \(p = 11, q = 17\). Then \(N = p \cdot q = 187\), and \(\Phi(N) = (p-1) \cdot (q-1) = 160\). Finally, consider the following public key \(e = 7\). From this we can compute the private key \(d\) such that \(e \cdot d = 1 \mod 160\), which is \(d = 23\).
If we now know want to encrypt we simply have to compute
\[C = M^7 \mod 187\]
while if we want to decrypt we have to compute
\[M = C^{23} \mod 187\]
1.5 Extended Euclidean Algorithm
Consider to have two coprime numbers, like \(51\) and \(11\). The idea is to find two numbers \(a, b\) such that
\[51 \cdot a + 11 \cdot b = 1\]
these numbers can be obtained using the following algorithm
\[\begin{array}{c | c | c | c} \text{a} & \text{b} & \text{val} & \text{rem}\\ \hline 1 & 0 & 51 & \\ 0 & 1 & 11 & \\ 1 = 1 - 4 \cdot 0 & -4 = 0 - 4 \cdot 1 & 7 = 51 - 4 \cdot 11 & 4 = \lfloor 51/11 \rfloor \\ -1 = 0 - 1 \cdot 1 & 5 = 1 - 1 \cdot (-4) & 4 = 11 - 1 \cdot 7 & 1 = \lfloor 11/7 \rfloor \\ 2 & -9 & 3 & 1 \\ -3 & 14 & 1 & \\ \end{array}\]
At the end when in the third row we have \(1\) we stop, and the find the following equation
\[51 \cdot (-3) + 11 \cdot (14) = 1\]
1.6 Computing RSA Inverse
If we know \(\Phi(N)\) and the public key \(e\) to actually compute the private key we can use the extended euclidean algorithm, which we explained in the previous section.
The idea is to find \(a, b\) such that
\[\Phi(N) \cdot a + e \cdot b = 1\]
if that holds then we have
\[e \cdot b = 1 \mod \Phi(N)\]
and thus \(b\) is the inverse of \(e\) modulus \(\Phi(N)\). That is, \(b\) is the private key associated to the public key \(e\).
1.7 RSA Signature
When using the RSA cryptosystem, if \(M\) is a message the RSA signature of \(M\) with respect to a pair of keys \((e, d)\) where \(e\) is the public key and \(d\) is the private key is the value \(H(M)^d \mod N\).
Thea idea is then to transfer the message \(M\) with the appended tag \(H(M)^d \mod N\).