Maths and Computing:

RSA public key

• Consists of a modulus, n, and an exponent, e
• The modulus is usually generated by multiplying two primes together, although three or four primes can be used
• The best exponent values, e, are prime numbers close to a power of 2
• Fermat primes are favoured as values of exponents and take the form 2^2r + 1
• The first five fermat primes are: 3 (2¹+1), 5 (2²+1), 17 (2⁴+1), 257 (2⁸+1), 65537 (2¹⁶+1)
• 65537 is commonly used as the exponent
• A data value M, is encrypted using as the value C using the formula

C = M^e mod n

RSA private key

• Consists of the modulus from the public key, n and an exponent, d
• d is mathematically generated from n and e
• If n is sufficiently large, then it is almost impossible to determine the value of d
• The mathematics used to determine d uses elements from number theory, primarily Euler's totient theorem and Bézout's Identity
• The encoded value C, is deccrypted to M using the formula

M = C^d mod n

Calculating d

d can be calculated from n and e

1. Find the value of the Euler's totient function; φ(n)
2. If e is coprime to φ(n), then Bézout's Identity can be used:
   There exists integers d and k such that ed + kφ(n) = 1 mod n
3. Use Euclid's Extended Algorithm to calculate d

Example: n = 21, e = 17

Calculating φ(n)

• n = 3 × 7
• φ(8) = 2 × 6 = 12

Using Bézout's Identity

• 17d + 12k = 1
• d = 5 and k = -7

d = 5

Checking for M = 4

• C = 4¹⁷ = 16 mod 21
• C = 16
• M = 16⁵ = 4 mod 21
• M = 4

Checking for M = 5

• C = 5¹⁷ = 17 mod 21
• C = 17
• M = 17⁵ = 5 mod 21
• M = 5

Encrypting

The maths showing how RSA encryption works

1. Data M encrypted as C

   C = M^e mod n

2. Bézout's Identity

   ed + kφ(n) = 1
   M^{ed + kφ(n)} = M

3. Eulers Totient Theorem

   M^φ(n) = 1 mod n
   M^kφ(n) = 1 mod n

4. Using the result from 1 and 3

   M^{ed + kφ(n)} = M^ed × M^kφ(n)
   = M^ed × 1 mod n
   = M^ed mod n

5. Combining 2 and 4

   M^ed = M mod n

6. Combining 1 and 5

   M^ed = (M^e)^d
   = C^d

   M = C^d mod n

Using Euler's totient function

The public key contains the modulus n, which is usually created from the product or two primes.

If n is known, then it has to be factorised into the primes in oder to determine the value of φ(n)

Using large values of n

In reality, the primes used for RSA encryption are very large and the resulting value of the modulus n should contain at least 2048 bits.

If the public key is known, the the private key can be derived by factorising n into it's prime factors, p and q, to then generate the value of φ(n).

For such large values of n, it is so exceedingly difficult and time consuming to find the prime factors, that it is infeasible to find the private key from the resulting public key.