Satish brings up one time padding, which involves $\text{XOR } [a \oplus b= a+b \text{ (mod 2)} ]$ on a message $m$ and a secret code word $s$. The sender sends $m \oplus s$ and the recipient then decodes this encryption with $(m \oplus s ) \oplus s \equiv m$.

Rivest–Shamir–Adleman Encryption

Public-key encryption scheme in which a user encrypts sent messages with a number $e$ and decrypts received messages with a number $d$.

Public Key. A tuple $(N, e)$ where $N=pq$ is the encoding/decoding modulus, $p,q$ are sufficiently large ($>$ 512 bits) primes, and $e$ is a small number coprime to $(p-1)(q-1)$.

Private Key. A number $d$ that is the inverse of $e$ modulo $(p-1)(q-1)$.

For a message $x \text{ (mod $N$)}$, the scheme goes as follows:

  1. The sender encrypts $x$ using $E(x) \equiv x^e \text{ (mod $N$)}$.
  2. The recipient decrypts $E(x)$ using $D(y) \equiv y^d \text{ (mod $N$)}$.

$$ x \rightarrow E(x) \equiv x^e \text{ (mod $N$)} \xrightarrow{\text{Encrypted }} D(E(x)) \equiv x^{ed} \text{ (mod $N$)} \xrightarrow{\text{Decrypted}}x $$

Security

Although the security of this algorithm has never been formally proved, its robustness comes from how computationally hard known approaches are.

  1. Brute Force. Let $y$ be the encrypted message transmitted. Compute $x^e \text{ (mod $N$)}$ and check if this is congruent to $y$. If not, repeat for all $N-1$ possible remaining values of $x$.
  2. Prime Factorization. Factor $N$ to find $p$ and $q$. These values can then be used to compute the private key $d \equiv e^{-1 }\text{ (mod $(p-1)(q-1)$)}$.

Implementation

Implementing RSA involves first generating $p$ and $q$ then computing the exponentials that occur during encoding and decoding.