4 The RSA Cryptosystem
4.1 Introduction
The RSA Cryptosystem is one significant examples of Number Theory and Cryptography applied in the real world; over the last 50 years, this algorithm has made the internet safe and secure from passwords to online transactions and any other communication of secure data. As discussed in Section 2.3, the RSA Cryptosystem is a public key cryptosystem that relies upon the Number Theory in the Mathematics Section. This algorithm works by utilizing Theorem 3. Below is a reminder of Theorem 3):
Let \(p\) and \(q\) be distinct positive primes. Let \(n = pq\) and \(k = (p-1)(q-1).\) Choose \(d\) such that \(\gcd(d, k) = 1\). Furthermore, let \(e\) be an integer such that \(de \equiv 1 \!\! \mod k\). Then \(b^{ed} \equiv b \!\! \mod n\) for every integer \(b\).
With the requisite \(p, q, n , k, d,\) and \(e\), it follows \(e\) is the public exponent for encryption, where any sender can then "scramble" and encrypt a message. Taking the encrypted message to the power of \(d\), the private key, \((b^e)^d\) results in \(b^{ed} \equiv b \!\! \mod n\), which is the original plain text message \(b\).
The chosen primes \(p,q\) in Theorem 3 are usually 300 or so digits long for RSA, creating an \( n\)that is 600 digits long. This \(n\), the product of two enormous primes is extremely hard to factor and would take modern computers on the order of centuries to compute n's prime factorization (Teitelbaum, 2021). This difficulty in factoring is what makes RSA encryption incredibly secure, although advances in computing technology could render this cryptosystem unusable.
4.2 RSA Algorithm Example Applet
Work through this exmple with this applet!
4.3 RSA Algorithm Example Explained
For this example, the distinct positive primes \(p\) and \(q\) will be \(p = 7\) and \(q = 17\). Then \[k = (7-1)(17-1) = 6 \cdot 16 = 96\] (which is actually the value of Euler's totient function). Furthermore \(n = pq = 119\). Then an arbitrary \(d\) that is relatively prime to \(k\) is chosen; for this example \(d = 5\). Next, an integer \(e\) must be discovered such that \(de = 1 \!\! \mod 96\). For finding \(e\), the Euclidean Algorithm (Lynn, n.d.) would prove useful, but \(e\) can also be solved for by using a computer algebra system and solving for \(5 \cdot e \equiv 1 \! \! \mod 96\) \(k\). Notice that \[96 \cdot 4 + 1 = 385 = 5 \cdot 77\ \quad \text{so} \quad e = 77 \quad \text{since} \quad de = 5 \cdot 77 = 384 = 1 \!\! \mod 96\]
Thus \[p = 7, q = 17, n = 119, k = 96, d = 5 \quad \text{and} e = 77 \] By Theorem 3, \(b^{ed} \equiv b \!\! \mod n\) for every integer \(b\). In the algorithm, \(b\) is the message, \(e\) and \(n\) are the published public keys for encryption, and \(d\) is the secret decryption key (Teitelbaum, 2021). Notice that the plain text message \(b\) cannot be larger than \(n\), so sometimes messages such as credit card numbers must be split into smaller messages.
To encrypt a message, say \(b = 46\), the sender simply uses the public key \(e\) to computer \[b^e \! \! \mod 119 = 46^{76} \!\! \mod 119 \equiv 65 \!\! \mod 119\] This modular exponentiation can be calculated using repeating squaring methods (which are used on online calculators such as dCode). The cipher text is 65, which the receiver can then use to decrypt the message with the private key \(d\) by \[65^d \!\! \mod 119 = 65^{5} \!\! \mod 119 \equiv 46 \!\! \mod 119\] where 46 is the original plain text message.