# 6.1200 Lecture 10 Notes

For a more readable version of these notes, see https://hackmd.io/@vinodnathan/BkAu5vz13

So far, we saw:
* greatest common divisors
* Euclidean algorithm to compute gcds
* Extended Euclidean algorithm or the "pulverizer"
* some modular arithmetic: add, subtract, multiply, exponentiate

How about division?!

****Modular Division****

Addition, Subtraction, Multiplication, and bases of exponents can be substituted mod $n$ (but not the exponents).

Can we divide mod $n$? Hmm... $3 \cdot 2 \equiv 3 \cdot 4 \bmod 6$. Can we "divide both sides by 3" and conclude that $2 \equiv 4 \bmod 6$? No!

A multiplicative inverse of $x$ is a number you can multiply $x$ by to get $1$. In $\mathbb{R}$, the multiplicative inverse of $3$ is $1/3$, because $3 \cdot 1/3 = 1$. If "1/3" made sense mod 6, then we could multiply both sides by 1/3 to conclude that $2 \equiv 4 \bmod 6$. So $3$ doesn't have a multiplicative inverse mod 6.

When do mod $n$ inverses exist for a number $a$?

**Theorem 5**. $a$ has an inverse mod $n$ if and only if $\mathsf{gcd}(a, n) = 1$.

*Proof* $a$ has an inverse mod $n$ IFF there exists $b$ such that $ab\equiv 1 \bmod n$ IFF there exists $b$ and $q$ such that $ab−1 = nq$. i.e. $ab−nq = 1$ IFF $1$ is a linear combination of $a$ and $n$. By Bezout, this last part happens IFF $\mathsf{gcd}(a, n) = 1$. QED.

**Corollary 6**. If $p$ is prime and $a \not\equiv 0 \bmod p$, then $a$ has an inverse mod $p$.

*Proof* $\mathsf{gcd}(a,p)$ must be $p$ or $1$. Since $a \not\equiv 0 \bmod p$, $p$ does not divide $a$ and therefore the gcd is $1$. Now apply the previous result. QED.

Having a multiplicative inverse means we "can cancel from both sides" or "divide" by that amount. e.g. $7$ and $13$ are inverses of each other mod $30$. If we know $7x \equiv 14 \bmod 30$, can we conclude that $x \equiv 2 \bmod 30$? Instead of dividing, let's multiply both sides by 13:
$$ 7x \equiv 14 \bmod 30$$ $$13 \cdot 7x \equiv 13 \cdot 14 \bmod 30$$ $$(13\cdot 7)x \equiv (13 \cdot 7) \cdot 2 \bmod 30$$ $$ (1)x \equiv (1) \cdot 2 \bmod 30.$$

So, since $7$ has a multiplicative inverse, we can indeed "cancel it from both sides".

Important fact:

**Theorem 7 (Fermat's little theorem)**: If p is prime, and a is not a multiple of p, then
$$a^{p-1} \equiv 1 \bmod{p}.$$

(Not to be confused with Fermat’s **Last** Theorem. Very different, much harder to prove.)

Example 1: $p=7, a=4$, $a^{p-1} = 4^6 \equiv 2^3 \equiv 8 \equiv 1 \pmod 7$ as Fermat's little theorem predicts.

Example 2: It is crucial that $p$ is prime. For example, if $p=8$, $a=3$, we have $a^{p-1} = 3^7 \equiv 3*(3^2)^3 \equiv 3*1^3 \equiv 3 \pmod 8$. // Make sure you understand how each of these steps in this calculation is accomplished.

Example 3: It is also crucial that $a$ is not a multiple of $p$. For example, if $p=3$ and $a=3$, then $a^{p-1} = 3^{2} \equiv 0 \pmod 3$.

**Proof**: Look at $a, 2a, 3a,\ldots, (p-1)a$ all modulo $p$. In example 1 above, they are $[4, 1, 5, 2, 6, 3]$. All within $1$ and $p-1$ of course, but you see a curious pattern: these numbers are a permutation of $[1, 2, 3, 4, 5, 6]$. Hmm...

We will start by showing that the numbers $a, 2a, 3a,\ldots, (p-1)a$ are all different modulo $p$. Suppose that two of these multiples are the same modulo $p$. That is, $ia \equiv ja \bmod p$. Since $\mathsf{gcd}(a,p) = 1$, $a$ has a multiplicative inverse. Multiplying both sides by $a^{-1} \bmod p$, we have $i \equiv j \bmod p$. So, these two numbers weren't distinct multiples after all. So, all the distinct multiples of $a$ modulo $p$ are distinct.

In other words:
$$\{a, 2a, ..., (p-1)a\} = \{1, 2,..., p-1\}$$

Multiplying all the elements of each set together, we have
$$a^{p-1} (p-1)! \equiv (p-1)! \bmod p$$

Does $(p-1)!$ have an inverse mod $p$? Yes! [Prove it!] [Bonus points if you can guess what the inverse is!]

Multiplying both LHS and RHS by $((p-1)!)^{-1} \bmod p$ gives us the desired outcome:
$$a^{p-1} \equiv 1 \bmod p.$$

***Application:*** How to compute $2029^{2029} \bmod 2027$. You are told that $2027$ is a prime number.

First, reduce the base mod 2027. So,
$$ 2029^{2029} \equiv 2^{2029} \bmod 2027$$
Next, note that $2^{2029} \equiv 2^3 * 2^{2026} \bmod 2027$ and that $2^{2026} \equiv 1 \bmod 2027$, the latter using Fermat's little theorem. So,
$$ 2029^{2029} \equiv 2^{2029} \equiv 2^3 \equiv 8 \bmod 2027$$

****Cryptography****

Cryptography has become a subject of enormous significance to our daily life over the last 20-30 years. It relies on mathematical problems from algebra, geometry and most famously, ... number theory, problems that you would have never thought would have any application at all. Like... modular arithmetic! Today we will see how GCDs and modular arithmetic are extremely important for computer security!

Cryptography, in a sentence, is the science of keeping secrets.

Idea: **Encrypt** a message that you want to send privately, in such a way that only certain parties can read it. The intended recipient should be able to **decrypt** it to recover the original message.

Convention: Alice is sending encrypted messages to Bob, Bob is decrypting them, and Eve is an Eavesdropper who overhears everything being sent, but hopefully still can't understand it.

An encryption method together with a decryption method is known as an encryption scheme.

*Caesar Cipher*

Early example: Caesar Cipher. Actually used by Julius Caesar for sensitive military messages. To encrypt a message m made of letters A to Z: move each letter forward 3 letters in the alphabet, wrapping around. So CRYPTO becomes FUBSWR. Said differently: think of A–Z as numbers 1–26, and add 3 mod 26. To decrypt, just subtract 3 mod 26.

Very easy to break!

Another try: rely on some secret key, or parameter.

Alice and Bob **agree beforehand** on a secret shift value $k$, that Eve doesn't know. To encrypt, add $k \bmod 26$ to each letter. To decrypt, subtract $k \bmod 26$ from each letter. Above example used $k = 3$. Rot13 uses $k = 13$, to move each letter halfway around the alphabet.

Is this better? Eve doesn’t know $k$, so are we safe? Susceptible to a brute force attack: just try all 26 options. One will probably look more like English than the others. E.g., try looking at all 26 shifts of "ORJMJVYNYDQZMBZYDIVTZGGJRRJJY". This site makes that easy: https://cryptii.com/pipes/caesar-cipher

*Substitution Cipher*

Need larger set of secret keys, known as the key space. One idea: Alice and Bob agree on a table mapping each letter to a different letter. E.g., $A \rightarrow X, B \rightarrow T, C \rightarrow W$, etc. There are $26!$ different keys, so Eve isn’t going to try them all.

Susceptible to frequency analysis. E.g., if W is the most common letter in your message, W probably decrypts to the most common English letter, E.

Probabilistic encryption, first invented by Shafi Goldwasser and Silvio Micali in the 1980s when they were students at UC Berkeley, is the way to solve the "frequency analysis" problem. They have been faculty at MIT since the 1980s and a decade ago, received [the 2012 Turing award](https://www.acm.org/articles/bulletins/2013/march/goldwasser-micali-2012-turing-award) for their discovery of probabilistic encryption.


Let's see a bit more history...

*German Enigma*

Imagine changing the shift each time? The WWII German Enigma Machine used a complicated mechanical device (about the size of a lunchbox) to change the shift values depending on the letters in the message itself, as well as the secret initial configuration of the machine. Complicated arrangement of rotors and wires and reflectors, oh my! For a total of around $3 \cdot 10^{114}$ different possible settings. Can't possibly check them all.

But still, allies broke the code. Developed a room-sized machine (called "bombe" because of the ticking sound). Used, among other things, knowledge about the kinds and formats of messages often sent, e.g., weather reports that all started with the same phrase. This is known as a Known Plaintext Attack, more on that soon. Lots of other clever ideas went into it too.

The british mathematician / cryptographer Alan Turing worked on the Bombe, and it informed his thinking on computing machines and resulted in the birth of a theory of computing.

*One-time Pad*

Different idea: Caesar Shift, but with bigger numbers. Instead of encoding a single character at a time, group letters into much larger numbers. An example (bad, but that’s ok): HELLOWORLD, using 1–26, becomes 08051212152315181204, just a 20-digit number. Let's work with numbers with hundreds of digits! No problem. Or do it in ASCII and read the binary bits. The encoding doesn't matter. What matters is that now, messages are numbers.

Pick a large $n$ (imagine $100$ digits), and now a message $m$ is just a remainder mod $n$, i.e., a number $0,1,2,\ldots,n−1$. If Alice and Bob agree on a number $0 \leq k \leq n−1$, then we can Caesar Shift: Alice sends $m + k \bmod n$, and Bob subtracts $k \bmod n$ to recover $m$.

Advantages: $k$ is arbitrary, so without knowing $k$, any message can have any encoding! No information is revealed. If $k$ is chosen uniformly randomly, then $m + k \bmod n$ is also uniformly random. Will learn more about randomness later.

Disadvantage 1: Message has to be smaller than $n$. What if we need to send a longer message? Break it into chunks of size $< n$ and send each with key $k$? No, bad things happen when reusing $k$.

First bad thing: Known Plaintext Attack: If Eve ever gets hold of your encrypted and unencrypted message, or has some information on it, then she can subtract to learn $k!$ On future messages, she can subtract $k$ and read your messages.

Second bad thing: Say $enc(m_1, k) = m_1 + k = m_1' \bmod n$ and same for $m_2'$. Then $m_1' − m_2' \equiv m_1 − m_2 \bmod n$. So info is leaking about how two messages relate to each other. It mushes the two messages together, but still a lot of info is revealed.

OK, so we won’t re-use k. That’s why this scheme (and ones like it) is known as a One-Time Pad.

So for longer messages, I’ll just send the new $k$ value before each one. . . Oh, huh. Well, maybe I’ll encrypt the new $k$ value first. . . But that needs us to already have an earlier agreed-upon key. . . Hm. If I had a secure way to send a new one-time pad, then I’d just use that method instead!

*RSA*

RSA = Rivest, Shamir, Adleman, the three inventors of the crypto- graphic scheme. It's really a workhorse of modern internet security. And they did it here at MIT! And [won a Turing award](http://www.ams.org/notices/200307/comm-turing.pdf) for it, in 2002!


Public-Key cryptosystem. You can tell everybody the encryption key, publicly! But it only lets you encrypt, not decrypt. You have the accompanying secret key that only you know, that you can use to decrypt. Boggling that this is possible!

Start with two large primes, $P$ and $Q$. Keep these primes secret, but publish $N := PQ$. Then, choose a large number $e$ that is relatively prime to $(P − 1)(Q − 1)$. Your public key is $(N, e)$.

Next, compute $d$ which is an inverse of $e \bmod (P−1)(Q−1)$, which we can do with the Pulverizer, because e is relatively prime to $(P−1)(Q−1)$ (by the way we chose it). Keep $P$, $Q$, $d$ secret.

To encrypt message $m$, output $(m^e \bmod N)$. To decrypt an encrypted message $c$, compute $(c^d \bmod N)$.

After encrypting and then decrypting, you’re computing $(m^e)^d \equiv m^{ed} \bmod N$. Claim: $m^{ed} \equiv m \bmod N$.

Why is this true?! Fermat’s Little Theorem!

We know $ed = 1+t·(P−1)(Q−1)$ for some integer $t \geq 0$. Let's assume $m$ is relatively prime to $PQ$. (In practice, these primes are much too big to stumble on “by chance”, so this assumption doesn’t matter in practice.) Working mod $P$, we find
$$m^{ed} \equiv m^{1+t(P−1)(Q−1)} \equiv m \cdot (m^{P−1})^{t(Q−1)} ≡ m \cdot 1^{t(Q−1)} \equiv m \bmod P.$$ The same is true mod $Q$.
$$m^{ed} \equiv m^{1+t(P−1)(Q−1)} \equiv m \cdot (m^{Q−1})^{t(P−1)} ≡ m \cdot 1^{t(P−1)} \equiv m \bmod Q.$$
So $P$ and $Q$ both divide $m^{ed}-m$, so $N=PQ$ divides $m^{ed}−m$. In other words, $m^{ed} \equiv m \bmod N$.

*Security* The public key is $N = PQ$ and $e$. Private key: $P, Q, d$. Relies on Factoring being hard! No efficient method known to factor $N$ into its two primes. (Not true with Quantum Computers! Which we can’t actually build yet. But soon? Maybe?)

Important point: we are assuming factoring is hard; we don’t have a proof. No algorithm to efficiently factor large numbers is currently known publicly, but that doesn’t mean it doesn’t exist! It might! It might even be known right now, by someone or some intelligence agency that just hasn’t shared it around. No way to know for sure.

"Cryptographers seldom sleep at night" --- Silvio Micali

*Finding large primes* How do we find large primes $P$ and $Q$? Two key insights:

* Numbers can be easily tested for primality. This is the Miller-Rabin algorithm from the pset. So, naive idea: pick random $300$-digit numbers and test for primality, until one of them is prime! Are there enough primes for that?! Don’t they get more and more sparse as numbers get big! Wouldn’t this take forever?

* This is actually fast, because there are lots of primes. Prime Number Theorem (PNT): the number of primes less than or equal to $k$ is denoted $\pi(k)$. The PNT tells us that
$$\pi(k) \sim k/ \ln k.$$ Around $k = 10^{300}$, the density of primes is about $1/ \ln(10^{300}) \approx 1/700$, so in expectation, $700$ tries is enough! This is fast.

**Statutory Warning** Don’t implement RSA yourself now, expecting it to be secure! What we described above is an over-simplified version which, while it gives you a taste of what's going on, is subject to lots of attacks and is insecure without further precautions.

Go to 6.1600 for more of a taste of cryptography and 6.5620 for the real deal.

https://61600.csail.mit.edu/2022/
https://mit6875.github.io/