The RSA Cryptosystem is a method of encryption wherein the security of any encrypted message stems from the difficulty in factoring large numbers into their primes. The cryptosystem takes its name from its inventors Rivest, Shamir and Adleman. It is one of the first public-key cryptosystems and is widely cited when explaining the paradigm of public key cryptography.

Public-Key Cryptography

In public key cryptosystems (also known as asymmetrical cryptography), members have a private key as well as a public key. Their private key is for them alone (kept secret) whereas the public key is published for all to see. This public-private split maintains secrecy and security whilst enabling anyone to send a message to the publisher of the public key. In particular, anyone can encrypt using a public key but private keys are necessary for decryption and forming public keys.

Public-key cryptography also has applications in authentication since the public key is derived from one’s private key and hence methods can be designed to prove that you must be the owner of that key.

The process of generating public keys and sharing them has a realm of cryptography all to itself. The sharing of private and composite keys over open channels is usually done using the Diffie-Hellman key exchange method.

Number theory background

Finding Prime Factors

The security of any encryption comes from the notion of one-way functions or operations that are easy to do yet near impossible to undo without information on how the initial calculation was made. This means that encryption is efficient and attacks will be unsuccessful.

The security of RSA encryption comes from the “factoring problem” – it is almost impossible (with current technology) to factor a large number into its prime factors. However, it is simple to calculate the product of a set of prime numbers.

Whilst it has not been proven that no efficient factorisation algorithm exists, no efficient, non-quantum algorithm is currently known. In 2009, an attempt to factor a 232-digit number using many hundreds of computers took two years to find the prime factors (Kleinjung; et al. 2010).

Greatest Common Divisors (GCDs)

The greatest common divisor (GCD) or largest common factor of two integers a and b, often denoted as GCD(a, b) is the largest integer x which divides both a and b.

If the GCD of two numbers is 1, i.e. the two integers share no common factors other than the trivial factor of 1, then the integers are referred to as coprime.

The GCD of two values can be found using Euler’s algorithm:

Euler’s Function

Euler’s function is a function that tells us how many values in the range from 0 to the argument are coprime to the argument. It is denoted by the Greek letter φ.

For a generic value of n, φ(n) is given by the equation below:

where p|n denotes the distinct prime divisors of n.

A frequently used special case is then n is the product of distinct primes. Let’s say n = p₁ × p₂ × … × p_k. Then, Euler’s function can be written as follows:

Examples

For example the prime factorization of 52 is 2² × 13 and hence the value of Euler’s function (and thus the number of integers coprime to 52) is given by:

In the case where the prime factorisation only consists of unique primes we may apply the alternative form of Euler’s equation. Take 1147 which has a prime factorisation of 1147 = 37 × 31. The number of values coprime to this is given by:

You can check that this is equivalent to the fractional formation of Euler’s function in this case and generally.

Euler’s Theorem

If a and n are coprime so that GCD(a, n) = 1 then Euler’s theorem states the following:

This means that when working modulo n we may work modulo φ(n) in exponents. For example, a^5φ(n)+3 ≡ a³ (mod n).

Encryption and Decryption

Engaging in a conversation using RSA encrypted messages follows the following algorithm. In this example, Alice is the sender, and Bob the desired recipient.

Generating the public and private keys (setup)

First, Bob generates his private and public keys (and shares the public key). This allows anyone to send messages to Bob.

1. Bob chooses large prime numbers. Let these prime numbers be p and q.
2. Bob computes n = p × q
3. Bob then chooses an encryption key e such that e is coprime to n, that is, the greatest common divisor of n and e is 1. This is necessary to ensure that e has a unique inverse modulo φ(n), this inverse is the decryption key d.
4. Bob then sends the pair which forms the pubic key (n, e) to Alice but keeps p, q and d private. Alice does not need to know p, q or d to send a message or perform encryption. The primes are only needed to find the decryption key d and hence knowledge of them enables decryption. This is the essence of a public key cryptosystem, anyone can encrypt using a public key but private keys are necessary for decryption and forming public keys.
5. Bob computes the decryption key d where d ≡ e^-1 (mod φ(n)) i.e. mod (p – 1)(q – 1). This requires knowledge of the private keys p and q and is performed using the extended Euclidean algorithm. The private decryption key d is kept secret. Knowledge of d and e is sufficient to factor n to obtain p and q. Knowledge of p and q is sufficient to find d.

Example

Suppose that Bob chooses primes 37 and 31 and therefore calculates n = 37 × 31 = 1147. He then chooses an encryption key e = 7 such that GCD(n, e) = GCD(1147, 7) = 1. n and e are then published.

The decryption key d is then given by 463. You can check that 7 * 463 ≡ 3241 ≡ 1 (mod 1080). Calculating modular inverse uses the extended euclidean algorithm to find x and y satisfying ax - my = 1. Then, x is modular inverse of a (mod m). Python code for calculating modular inverse is included below.

# the extended euclidean algorithm
# given a, b => returns g = gcd(a, b) and x, y such that a*x-b*y=1
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
# mod inverse using extended euclidean algorithm 
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
print modinv(7, 1080) # outputs 463

Sending messages

Once the set-up is complete, messages can be sent as follows:

1. Alice writes her message and coverts it to a number m. For example, this can be done by converting letters to numeric values (A = 01, B = 02, …). Note that no character is mapped to zero as zeros will be lost in the encryption if they appear at the start of messages or message segments. If m is larger than n then the message is broken into blocks and sent in segments.
2. Alice encrypts m to the ciphertext c by the equivalence: c ≡ m^e (mod n) and sends c to Bob.
3. Upon receiving the encrypted message c Bob decrypts it as follows: m ≡ c^d (mod n). This is true since, c^d (mod n) ≡ m^ed (mod n) ≡ m¹ (mod n), using ed ≡ 1 (mod φ(n)) and Euler’s theorem.

Continued Example

Suppose for simplicity that Alice wishes to send the message AABB which is then encoded numerically to 1122. The encryption leads to:

Bob then receives this and decrypts the message to attain.

Bob may then convert the numerical code back to text to get the original message AABB.

Attacks and Security

The algorithm is widely used and very secure. There are no known consistently effective attacks on the system with current technology. The necessity of keeping d and the prime numbers used to construct n (usually denoted p and q) secret are the greatest risk to security, which is usually a human and social problem, i.e. one might accidentally reveal them or be tricked into doing so.

Below, we’ll discuss various aspects related to RSA security in more detail, including some possible attacks and minor changes required in the RSA algorithm to circumvent these attacks.

Importance of large primes and other values

Suppose than an attacker, Eve, intercepts the communications and thus obtains n, e and c. Eve does not know m, d, p or q. Due to the near impossibility of factoring n to find p and q we assume that Eve has no way to factor n given n, e and c and that a brute force approach is impractical due to n, p, q, e, d, m and c being suitably large.

Eve has knowledge of the RSA protocol and hence knows that:

Eve knows c, e and n so why shouldn’t she find m by taking the e^th root of m mod n? This is very difficult due to n being large. The only way to solve this root problem is by trying each possible value of e or d in the absence of knowing the decryption key d ≡ e^-1 (mod φ(n)). Finding this key requires knowledge of p and q.

Bob’s choice of p and q affects the security of the cryptosystem. These primes should be large (with at least 100 digits for practical use) and chosen randomly and independently. Moreover, to protect against factoring using the ‘p – 1 technique’ one should check that both p – 1 and q – 1 have at least one large prime factor since if these values only have small prime factors it introduces vulnerabilities to the system. (See Footnote 1 for more details).

The choice of e should also be a large number to increase security. One possible way of choosing e is to take e to be a moderately large prime which is also likely to ensure that GCD(e, (p – 1)(q – 1)) = 1 so that the decryption key d is known to exist before finding it.

Short plaintext attack

RSA is commonly used to send short messages including encryption keys for other algorithms such as the Data Encryption Standard (DES) or Advanced Encryption Standard (AES) encryption algorithms. This means that encryption must be engaged in carefully as smaller messages can lead to possible vulnerabilities. Consider sending the message m ≈ 10¹⁷, an AES encryption key say. Let m be encrypted using RSA as below using a value of n with approximately 200 digits.

This means that c likely has approximately 200 digits like n, despite the small size of m (so long as e is sufficiently large). Eve intercepts this ciphertext and now knows c, n and e. These are public knowledge. In an attack on the system Eve makes two lists:

1. cx^-e (mod n) for all x such that 1 ≤ x ≤ 10⁹
2. y^e (mod n) for all y such that 1 ≤ y ≤ 10⁹

Eve then looks for matches in the first and second list. If one is found she has:

and hence can deduce:

Although this will not always work, it demonstrates that Eve will be able to get the original message (whilst not entirely breaking the cryptosystem by factoring n or finding d) when the message is equal to the product of two values x and y both smaller than 10⁹. Many values of m will satisfy this and hence this shows the vulnerability of the system when sending small messages. One way to avoid such an attack is to arbitrarily make the message longer by appending and/or prepending a number of random digits to the message m.

This meet-in-the-middle attack is much more efficient than trying all of the 10¹⁷ possible values for m. This attack requires the computation of the two lists so 2 × 10⁹ calculations rather than 10¹⁷. For more on this attack see Boneh, Joux and Nguyen (2000).

Algorithm summary

The encryption key of the system is given by (e, d, n) where ed ≡ 1 (mod φ(n)) and e and n are public whereas d is private. e is the encryption key and d is the decryption key, where arithmetic is performed modulo n. The larger the values used in constructing keys the more secure the cryptosystem at the cost of slightly slower computation times.

Setup:

1. Bob chooses secret primes p and q and calculates n = pq.
2. Bob chooses the encryption key e with GCD(e, (p – 1)(q – 1)) = 1.
3. Bob computes d such that de ≡ 1 (mod (p – 1)(q – 1)).
4. Bob makes n and e public while keeping d, p and q private.

Sending messages:

1. Alice encrypts the message m as c ≡ m^e (mod n) and sends c to Bob.
2. Bob decrypts the ciphertext c by computing m ≡ c^d (mod n).

Conclusion

This set of notes has considered the RSA cryptosystem and introduced the idea of public-key cryptosystems. The security of RSA encryption is derived from the near impossibility of prime factorization of large numbers.

This set of notes has also introduced concepts useful across cryptography and number theory such as Euler’s function, Euler’s theorem and the concept of greatest common divisors.

Footnotes

1. The p – 1 factoring algorithm: Choose an integer a > 1 (often a = 2). Choose a bound B. Compute b ≡ aB| (mod n). This is done as follows: let b₁ ≡ a (mod n) and b_j ≡ b_j-1^j (mod n). Then b_B ≡ b (mod n). Let d = GCD(b – 1, n). if 1 < d < n , we have found a non-trivial factor of n, namely b – 1.

Bibliography

1. Boneh, Joux and Nugyen (2000): D. Boneh, A. Joux and P. Nguyen, “Why textbook ElGalal and RSA encryption are insecure”, Advances in Cryptography – ASIACRYPT 2000, Lecture notes in Computer Sceince, 1976, Springer-Vering, 2000 pp. 30 – 43.
2. Kleinjung; et al. (2010): Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen K. Lenstra, Emmanuel Thomé, Joppe W. Bos, Pierrick Gaudry, Alexander Kruppa, Peter L. Montgomery, Dag Arne Osvik, Herman te Riele, Andrey Timofeev, and Paul Zimmermann, “Factorization of a 768-bit modulus”, International Association for Cryptologic Research, 2010
3. This article also draws on the textbook: “Introduction to Cryptography with Coding Theory” by Wade Trappe and Laurence C. Washington.