Math 240 Discrete Mathematics - RSA encryption

RSA encryption

RSA encryption is not vulnerable to man in the middle attack. Let’s discover why.

Public Key

A piece of info I published by an entity, allowing others to securely send messages to that entity. The info, I should allow others to send me securely encrypted messages that only I can quickly decrypt

RSA Encryption Practice

Based on hardness of factorization. (This is not the same as primality testing)

My private info: Two large primes $q_1$ and $q_2$

My public key $I$:

  1. A large prime p
  2. The product n

Where $ I = (P,n) $ and $ n = q_1 \cdot q_2 $

Aside: $p$, $q_1-1$, $q_2-1$ needs to be all relatively prime, this happen by chance

Now Bob wants to send me a message M (think of M as a number of less than 500 digits). To encrypt, he calculates $\hat M = M^p \pmod n$, then sends it. To decrypt, I want to rise $\hat M$ to some power d, need to find d such that $\hat M^d \pmod n =M$

Step 1

Solve $a\cdot (q_1 -1)\cdot(q_2 -1 ) \equiv -1 \pmod p$. This can be done by using Euclid’s algorithm to find a, b such that $a\cdot (q_1 -1)\cdot (q_2 -1 ) = b \cdot p -1$

Step 2

Compute $\hat M^b \pmod n = M^{p\cdot b} \pmod n$

Claim: $M^{p \cdot b} \pmod {n} = M $

Proof: \[ \begin{aligned} M^{b\cdot p}\pmod{q_1} & = M^{a(q_1-1)(q_2-1)+1} \pmod {q_1} \\ & = [M^{q_1-1}]^{a(q_2-1)} \14\pmod {q_1} \\ by \ FLT & = M \pmod{q_1} \\ &=M \end{aligned} \] Similarily \[ \begin{aligned} M^{b\cdot p}\pmod{q_2} & = M^{a(q_1-1)(q_2-1)+1} \pmod {q_2} \\ & = M \end{aligned} \]


$q_1 \mid (M^{b\cdot p} -M)$ and $q_2 \mid (M^{b\cdot p} -M)$. Since $q_1$, $q_2$ are primes, we get $q_1 \cdot q_2 = n \mid (M^{b\cdot p} -M)$

$\therefore M^{b\cdot p} \pmod{n} = M$