Cryptography is the study of mathematical techniques related to various aspects of information security. Refer to slides for definitions of “adversary” (passive and active) and “channel” (secure and unsecure).
Encryption using the key $e$ and decryption using the key $d$ are represented as $E_{e}(\cdot)$ and $D_{d}(\cdot)$ respectively. The plaintext message is represented as $M$ and the ciphertext as $C$.
The aim in cryptography is for an encryption scheme to be unbreakable, i.e., for the problem of plaintext recovery (without prior knowledge of the key pair) to be computationally infeasible.
In symmetric-key encryption, the same key can be used for encryption as well as decryption. The key needs to be conveyed to the receiver via a secure channel for this form of communication.
In asymmetric-key encryption, however, there are two keys - a private and a public key. Each person has his or her own private key, known to no one else, and a public key, which is available to everyone. The private key can be used to decrypt a message encrypted using the public key, and vice versa. RSA is a common algorithm for asymmetric encryption.
This cryptosystem relies on modular arithmetic (specifically, Euler’s Theorem) and the computational infeasibility of factoring large numbers. We will consider that Alice would like to send a message $M$ to her friend Bob.
The key includes a number $n$, which is the product of two large, distinct primes $p$ and $q$. We know that $\phi(n) = (p-1)(q-1)$.
Both Alice and Bob have a private and a public key each. Their public keys are known to each other, while their private keys are not. Alice uses Bob’s public key $(e,n)$ to encrypt the message, and Bob decrypts it using his private key $(d,n)$.
$e$ and $d$ are numbers such that $d \equiv e^{-1}$ (mod $\phi(n)$), i.e., $ed \equiv 1$ (mod $\phi(n)$).
According to Euler’s Theorem, if $gcd(a,n) = 1$, then $a^{\phi(n)} \equiv 1$ (mod n).
As $p$ and $q$ are both large primes, we take them both to be coprime to $M$, the plaintext message. Consequently, $gcd(M,n) = 1$.
Alice raises the message $M$ to the power of Bob’s public key $e$ and takes the remainder modulo $n$ to obtain the ciphertext $C$, i.e.,
$C \equiv M^{e}$ (mod n).
Bob receives the ciphertext $C$. To decrypt it, he raises it to the power of his private key $d$ and takes the remainder modulo $n$.
$C^{d} \equiv M^{ed}$ (mod n).
However, since $ed \equiv 1$ (mod $\phi(n)$), we know that $ed = k \phi(n) + 1$ for some $k$. Substituting this,
$M^{ed} = M^{k \phi(n) + 1}$
$= M^{k \phi(n)} \cdot M^{1}$
$= {(M^{\phi(n)})}^{k} \cdot M$
$\equiv 1^{k} \cdot M$ (mod n), by Euler’s Theorem and since $gcd(M,n) = 1$
$\equiv M$ (mod n).
Since $M < n$, the above yields $M$ itself, and Bob has decrypted the message.
Let the message be encoded as a number, say $M = 6$.
Let $p = 13, q = 17$. Therefore $n = 221$ and $\phi(n) = 192$.
Suppose $e = 77$. Since $d = e^{-1}$ (mod $\phi(n)$), $d = 5$.
Encryption. $C \equiv M^{e}$ (mod n) $\equiv 6^{77}$ (mod 221) $= 197$.
Hence $C = 197$ is the ciphertext.
Decryption. $M \equiv C^{d}$ (mod n) $\equiv 197^{5}$ (mod 221) $\equiv 6$ (mod 221).
Hence the plaintext message $M = 6$ is retrieved and can be decoded to obtain the original message.