Modular arithmetic
RSA
Diffie-Hellman
Public key algorithms are based on modular arithmetic
– modular addition
– modular multiplication
– modular exponentation
Addition modulo (MOD) M
Additive inverse: addition MOD M yields 0
e.g. M=10, for k=2, its inverse is k^-1=8 because 2+8 MOD 10 = 0
Reversible: by adding the inverse
– convenient for decryption
e.g., for c = 3, p = c + k = 3+2 MOD 10 = 5;
p+k^-1 = 5+8 MOD 10 = 3 = c
