Loading...

​​Discussion 4A

​​Fermat’s Little Theorem

​​If ​​$p$​ is a a prime number and ​​$a \in \{1, 2, \cdots, p-1 \}$​ then ​​$a^{p-1} \equiv 1 \mod p$​.

​​Variation: if ​​$p$​ is prime then ​​$a^p \equiv a \mod p$​ for any integer ​​$a$​

​​Generalization

​​Let ​​$\phi(n)$​ be the number of integers between ​​$1$​ and ​​$n$​ that are relatively prime with ​​$n$​ (this is Euler’s totient function). Then ​​$a^{\phi(n)} \equiv 1 \mod n$​.

​​RSA

​​Premise: Alice wants to securely send a message ​​$x$​ to Bob

​​Procedure

1. ​​Bob chooses two primes ​​$p$​ and ​​$q$​, and lets ​​$N = p q$​

2. ​​Bob finds ​​$e$​ and ​​$d$​ which are multiplicative inverses ​​$\mod (p-1) (q-1)$​

1. ​​this means ​​$e$​ and ​​$d$​ are relatively prime with ​​$(p-1) (q-1)$​

3. ​​Bob posts his public key ​​$(N, e)$​ to the world and keeps ​​$d$​ private

4. ​​Alice sends Bob the value of ​​$E(x) = x^e \mod N$​

5. ​​Bob receives ​​$E(x)$​ and decrypts it using the function ​​$D(y) = y^d \mod N$​

1. ​​​​$D(E(x)) = E(x)^d = (x^e)^d = x^{e d} \mod N$​

6. ​​It turns out that ​​$x^{e d} = x \mod N$​, which is the original message

​​