Public-key cryptography 1: RSA
Do arithmetic mod p?q.
- Given public key e, private key d can be found from inverting e mod p-1 and q-1, and then using Chinese remainder theorem.
- Encryption and decryption are done by raising message to the e or d power.
- Fermat’s little theorem makes it work:
- m^(1+k*(p-1)) = m (mod p)