Public-Key Cryptography

RSA

We need to understand the difference between symmetric encryption and asymmetric encryption.

Definition

Public-key cryptography separates encryption keys from decryption keys. Each participant B has a decryption key which they hold secretly, and a related encryption key which they share in a public repository of some sort. Even though B’s decryption key and encryption key are mathematically related, it should be computationally infeasible for an eavesdropping adversary to determine B’s decryption key from B’s encryption key. Now, if any user A wishes to send a confidential message M to user B, A would somehow obtain an authentic copy of B’s public encryption key, encrypt M with this public key, and send the resulting ciphertext C to B. Since B is the only person who possesses the private decryption key, only B can decrypt C to recover M.

Diffie-Hellman Key Exchange Protocol https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange See wikipedia article, where it talks about mixing colored paintings.

Modular Exponentiation

RSA Encryption Algorithm

(a) Setting up RSA: To set up the RSA encryption scheme, Bob does the following.

1. Randomly choose two large, distinct primes $p$ and $q$ and let $n=pq$.
2. Select an arbitrary integer e so that $\gcd (e,(p-1)(q-1))=1$ and $1<e<(p-1)(q-1)$.
3. Solve the congruence $ed\equiv 1(\mathrm{mod}(p-1)(q-1))$ for an integer $d$ where $1<d<(p-1)(q-1)$
4. Publish the public key $(e,n)$.
5. Keep secret the private key $(d,n)$, and the primes $p$ and $q$.

(b) RSA Encryption: To encrypt a message as ciphertext and send securely to Bob, Alice does the following.

1. Obtain an authentic copy of Bob’s public key $(e,n)$.
2. Construct the plaintext message $M$, an integer such that $0\le M<n$.
3. Encrypt $M$ as the ciphertext $C$, given by $C\equiv M^e(\mathrm{mod}n)$ where $0\le C<n$.
4. Send $C$ to Bob

(c) RSA Decryption: To decrypt the ciphertext received from Alice, Bob does the following.

1. Use the private key $(d,n)$ to decrypt the ciphertext $C$ as the received message $R$, given by $R\equiv C^d(\mathrm{mod}n)$ where $0\le R<n$.
2. Claim: The received message $R$ equals the original plaintext message $M$, i.e., $R=M$.