Multiplication modulo M
Multiplicative inverse: multiplication MOD
M yields 1
e.g., M=10, 3 and 7 are inverse of each other because 3*7 MOD 10 = 1
Only some numbers have inverse
but 2, 5, 6, 8 do not have inverse when M=10
Use Euclid’s algorithm to find inverse
Given x, n, it finds y such that x*y mod n = 1
Only the numbers relatively prime to n has MOD n multiplicative inverse
Totient Function
x is relatively prime to n: no common factor other than 1
Totient function Θ(n): number of integers smaller than n and relatively prime to n
if n is prime, Θ(n)= n-1
if n = p*q, and p, q are primes, Θ(n)=(p-1)(q-1)
if n = p*q, and p, q are relative prime to each other, Θ(n)=Θ(p)Θ(q)
X^y mod n = X^ymodΘ(n)mod n
if y = 1 mod Θ(n)then x^y mod n = x mod n
RSA(Rivest, Shamir, Adleman)
– Widely used, and one of the first(1977)
– Support both public key encryption and digital signature
– Assumption/theoretical basis:
Factoring a very large integer is hard
Variable key length
Variable plaintext block size
– Plaintext treated as an integer, and must be “smaller” then the key
– Ciphertext block size is the same as the key length
