RSA

Tags

algorithm comp-sci

Is a algorithm for Asymmetric-key Encryption.

It's named for its [see page 14, inventors]: Ron Rivest, Adi Shamir, Len Adleman.

Procedure

Key Generation

First we pick two large primes \( pq \). The product of these primes \( n = pq \) will be half of our public key. Then we calculate the Euler totient of \( n \) as \( \Phi(pq) = pq (1 - \frac{1}{p}) (1 - \frac{1}{q}) = (p - 1) (q - 1) \) and choose a number \( e \) which is relatively prime to \( \Phi(pq) \) as the other half of our public key. In practice we often pick \( e = 2^{16} + 1 = 65537 \), although it can be as small as 3. Now the receiver calculates \( d \), the private key, such that \( de = 1 \mod \Phi(n) \).

Encryption and Decryption

Given an input message "HELLO" we first convert it to a number \( m \). Note: \( m \) must be less than \( n \), otherwise it will be lost when taking modulo \( n \). If the message is larger than this then it must be encrypted in pieces.

To encrypt the message we calculate the cipher-text \( c = m^e (\mod n) \). To decrypt it the receiver calculates \( m \equiv c^d (\mod n) \).

Proof of Correctness

To prove RSA we must show that \( (m^e)d = m \mod n \; \forall m \in \mathbb{N} \).