Alex's Notes

Week 8 - RSA

3 min read

Week 8 - RSA

To talk about the RSA algorithm we first need a little more theory.

Fermat's little theorem

Statement

Fermat's little theorem

For any prime number and we have

Proof

Note if is a multiple of the statement is true as both sides are zero. It suffices to prove this for as all other integers are congruent to one of these mod . Moreover, we only need to show (mod ).

Consider the set . From the proof of Modular multiplicative inverse existence we know .

Therefore by multiplying the entries in together we have However as for is coprime to from modular multiplicative inverse existence lemma. We know therefore has a multiplicative inverse mod . So we have as desired.

Theory

This is generalised by Euler’s theorem (modular arithmetic).

Link to original

In fact we need a generalisation of Fermat’s little theorem called Euler’s theorem (modular arithmetic).

Euler's theorem (modular arithmetic)

Statement

Euler's theorem

For integers such that gcd(n,a) = 1. Then where is Euler’s totient function.

Proof

Theory

This generalises Fermat’s little theorem.

Link to original

Where we define Euler’s totient function as follows.

Euler's totient function

Euler's totient function

For a natural number define Eulers totient function as

Theory

This is normally calculated using Eulers product formula (totient function).

Statement

Euler's product formula

Given some with prime decomposition with distinct primes and . Then the Euler’s totient function of is

Link to original

Link to original

For example if was a prime power we would have.

Transclude of Eulers-product-formula-(totient-function)#claim-2
Transclude of Eulers-product-formula-(totient-function)#proof-of-claim-2

For RSA it is also good to know

Claim 1

Claim 1

Let be coprime then

Link to original

Proof of Claim 1

As and are coprime the Chinese remainder theorem gives has a bijection where (mod ) and (mod ).

Note if if and only if and as and are coprime. Therefore

Missing \begin{array} or extra \end{array}\ \{y \in \mathbb{N} \ \vert \ 0 < x \leq n, \ gcd(x,n) = 1 \} \end{array} \mapsto \left \{b(x,y) \in \mathbb{N} \ \Bigg \vert \begin{array} \ 0 < b(x,y) \leq mn, \\ \ gcd(b(x,y),mn) = 1 \end{array} \right \}$$ and we have $$\phi(mn) = \phi(m) \phi(n).$$ ## Claim 2 >[!important] Claim 1 > >If $p$ is prime and $k \geq 1$, then >$$\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1) = p^k\left ( 1 - \frac{1}{p} \right ).$$ ## Proof of Claim 2 As $p$ is [[Prime|prime]] we know the positive divisors of $p^k$ are powers of $p^i$ for $0 \leq i \leq k$. Therefore of $gcd(p^k, x) > 1$ we know $x$ will have to be a multiple of $p$. So $x = mp$ with $m \in \mathbb{Z}_{\not = 0}$ and for $0 < x < p^k$ we have $0 < m \leq p^{k-1}$. So $$\phi(p^k) = \big \vert \left \{x \in \mathbb{N} \ \vert \ 0 < x \leq p^k, \ gcd(x,p^k) = 1 \right \} \ \big \vert = p^k - p^{k-1}$$ giving the desired result.Link to original

Which as a corollary has for two distinct prime numbers.

RSA idea

Here we want to pass a message from one person to another where the message sent between them is unintelligible without more information.

Let and be distinct primes. We are going to use Euler’s theorem (modular arithmetic) that to recover a message.

Rivest-Shamir-Adleman algorithm (RSA algorithm)

Rivest-Shamir-Adleman algorithm (RSA algorithm)

To set up the RSA algorithm you do the following:

  1. You pick 2 n-bit random primes and .
  2. You choose relatively prime to .
  3. You let and you publish the public key .
  4. You compute your private key (mod ).

Then to encrypt a message someone else does the following:

  1. Take a public key .
  2. You compute (mod ).
  3. Then you send message .

Lastly to decipher the message using the private key you do the following.

  1. You receive the message .
  2. You calculate (mod ).
  3. Revel in your secrete knowledge.

Note this works from Euler’s theorem (modular arithmetic) as so as .

Limitations

  1. gcd(m,N) = 1
    1. Otherwise the encrypted message and share a common factor or and they can work out and using the extended Euclidean algorithm and work out .
    1. Otherwise looking at the message mod gives the wrong message.
    2. This is normally gotten around by breaking the message up and giving it in little chunks.
    1. Otherwise they can just calculate the ‘th root to understand the message.
    2. If is too small then you normally augment it by a factor and encrypt sending afterwards to let the person know they need to subtract it.
  4. Can’t send the same and out multiple times.
    1. If you have 3 public keys , and then using the Chinese remainder theorem you can recover the original message .
  5. We assume factoring is hard.
    1. If it was not other people would be able to recover and calculate .
Link to original

Selecting random primes

The first stage of the RSA algorithm is to select two random -bit primes. To do this we first select a random number by randomly selecting each bit in this number.

As primes are dense the probability that this number is prime is . So we just keep repeating ourselves until we hit a prime number.

random_prime(n):
	Input: n the length of the number in bits.
	Output: A prime number that has n-bits.
1. Select a random n-bit number.
2. If it is prime return it
3. Go back to step 1.

Though how do we check if a number is prime.

Fermat’s test

If is a prime then for all we have So if we find where (mod ) we know is composite.

Such are called a Fermat witness for and every composite number has one.

Existence of a Fermat witness if and only if composite

Statement

Lemma

A number has a Fermat witness if and only if is not prime.

Proof

If is prime from Fermat’s little theorem we know no Fermat witness exists.

If for then .

Suppose then we would have so is the inverse of .

Though by the existence modular multiplicative inverse lemma we know no such inverse exists for and therefore (mod ). So is a Fermat witness for .

Link to original

However, the Fermat witness constructed in the proof are not dense in the numbers between to . We need the existence of non-trivial Fermat witness to guarantee this.

Carmichael number

Carmichael number

A is called a Carmichael number if it is not prime and has no non-trivial Fermat witness.

Link to original

Luckily for us the existence of Carmichael numbers is rare. The first couple are 561, 1105, 1729, …

Non-trivial Fermat witnesses are dense

Statement

Lemma

If has non-trivial Fermat witness then atleast 1/2 of are Fermat witnesses.

Proof

Pick a non-trivial Fermat witness . Then for any such that it has a twin where Note as we are just multiplying by which is a bijection on integers mod we have that at most half of are not Fermat witnesses.

Link to original

Simple Primality testing algorithm

We want to use the above to test the primality of a number randomly.

Primality Test(r)
	Input: An postive integer r.
	Output: If the algorithm thinks r is prime or not
1. Choose z_1, ..., z_k randomly from {1,2, ... , r-1}
2. For i = 1 -> k
	1. Compute z_i^{r-1} (mod r)
3. If for all i, z_i^{r-1} = 1 (mod r) then output r is prime
4. Otherwise output r is composite

This algorithm is always correct if is prime. However, there are two cases where we can be unlucky:

  1. is a Carmichael number, then it is quite likely we will return it is prime, or
  2. We are unlucky is composite and not a Carmichael number then We can adapt this algorithm to search for non-trivial square roots of 1 mod that only exist when is not prime also. This doesn’t take into account Carmichael numbers so makes the algorithm slightly safer.

Graph View

Backlinks