Lecture 18: Encryption #2 - Public Key Systems

RSA

In 1978, Rivest, Shamir and Adleman of MIT proposed a number-theoretic way of implementing a Public Key Cryptosystem. Their method has been widely adopted. The basic technique is:

Choose two large prime numbers, p and q.
compute n = p * q and x = (p-1)*(q-1)
Choose a number relatively prime to x and call it e. This means that e is not a prime factor of x or a multiple of it.
Find d such that e * d = 1 mod x.

To use this technique, divide the plaintext (regarded as a bit string) into blocks so that each plaintext message P falls into the interval 0 <= P < n. This can be done by dividing it into blocks of k bits where k is the largest integer for which 2^k < n is true.

To encrypt: C = P^e (mod n)
To decrypt: P = C^d (mod n)

The public key, used to encrypt, is thus: (e, n) and the private key, used to decrypt, is (d, n))

Lecture 18: Encryption #2 -- Public Key Systems

previous | start | next