Public Key Encryption

9th March 2010

These are lecture notes from my Computer Science course, not a general reference for "Public Key Encryption"

You probably know a bit about public key encryption.

Authenticity of Data

Some schemes allow both public and private keys to be used for encryption and decryption. Thus to send a message and guarantee authenticity (Ka is public key, Ka^-1 is private):

A calculates C=Encrypt(Ka^-1: M)
B calculates M=Decrypt(Ka: C)

If the result makes sense then B knows it came from A.

RSA

Best known public key encryption algorithm. Based on the difficulty of factoring a number into its two constituent primes e.g. 21 = 3 x 7. Finding a prime is easier. There’s a slide detailing the algorithm and examples, it’s also in Schneier (handy).

Diffie-Helman

Made no money (unlike RSA) because they sat on it forever.

Why use Public Key?

Often used to distribute keys or encrypt small amounts of data. Public key is slow, modular exponentiation eats up CPU. RSA is about 1000 times slower than DES.

Hash functions

Produce a digest, MD5 for example. You can use hash functions with authentication too by encrypting the message AND the hash value; then you know it’s not been altered and that it was sent by the original person.

Factorisation: Pollard’s Rho Method

A simple algorithm (uhuh). Basically it’s about generating a random mapping over Z_n where Z_n are the numbers less than n, then you keep applying the function to a number (and the output of that function) checking for a gcd in the process. The slides explain better.