## Factoring and Security

So I’m taking this awesome class this semester, Computer and Network Security, taught by Prof. Ron Rivest, and today the class talked a bit about the history of cryptography and security. After lecture, I felt the need to do a more in-depth research of various number theory proofs and concepts that are the foundations of cryptography and here’s the result of that. I’ve also been doing quite a bit of application building over the past couple of weeks so this is certainly a nice switch back to theory.

To set the basis for modern cryptography, we need to know that:

• There are an infinite number of prime numbers. The proof is very straightforward.
We may prove by contradiction. We assume that we only have a finite set of primes given by $P = \left\{p_0, p_1,...p_n\right\}$. Then, we can create another number, $M$, such that $M = \prod\limits_{n\in M}n + 1$. Given our assumption that we know all of the finite primes in the universe, $M$ must be composite. Therefore, some prime in $P$ must divide $M$. However, this is not possible because that would imply that some prime in $P$ also divides $1$. Therefore, either another prime $\not\in P$ divides $M$ or $M$ is a prime. Both of these possibilities contradict our assumption. QED

But how does knowing this lead to better cryptographic systems? Well, this knowledge wouldn’t have as much weight if the RSA algorithm didn’t exist. The RSA algorithm is an example of what is known as public key cryptography. Public key cryptography is a simple scheme where someone named Alice can set a public key, $PK_A$ that others can use to encrypt a message, $M$, and this encrypted message, $C$ to Alice: $C = PK_A(M)$. Alice can then use a separate key known as her secret key, $SK_A$ to decrypt the encrypted message, $C$, back to $M$: $M = SK_A(C)$.

This sounds great and all except there is one condition that all safe and secure public key encryption schemes should follow: one may not obtain the secret key, $SK_A$, from the public key, $PK_A$. In other words, it is very hard (meaning it should take thousands and thousands of years) to decrypt a secret message encrypted by using $PK_A$ without $SK_A$.

This is where RSA comes in.

• The RSA algorithm describes a public key cryptosystem. To generate the public and private keys using RSA, one would:

1. Randomly generate two prime numbers, $p$ and $q$, and take their product, $n = p \cdot q$. Preferably, the two prime numbers should be of similar number of bits. (In an extreme case, think of how hard it would be to factor, $n = 17746761831$. Not too hard right?)
2. Then, compute Euler’s totient function, $\phi(n) = \phi(p) \cdot \phi(q) = (p-1) \cdot (q-1)$ where Euler’s totient function computes the number of numbers that are relatively prime to the input, are less than the input, and are positive.
3. Using the output of the totient function, choose a number, $e$ such that $1 < e < \phi(n)$ and $gcd(e, \phi(n)) = 1$. In other words, $e$ and $\phi(n)$ are relatively prime. In our previous case with Alice, the public key Alice would distribute are $n$ and $e$: $PK_A = (n, e)$.
4. Now, we need to determine Alice’s private key. First we define a number $d$ to be the multiplicative inverse of $e$ modulus $\phi(n)$, $d \cdot e = 1 \mod \phi(n)$. Then, the Alice’s secret key would consist of $d$, $SK_A = d$. However, even though $p$, $q$, and $\phi(n)$ are not included in the private key (because they are not necessary to decode the encrypted message that Alice receives), they should not be made public. In fact, the security of the system relies on keeping $p$, $q$, and $\phi(n)$ private.
5. Given Alice’s new public and secret keys, we can now encrypt and decrypt messages. To encrypt a message, an outsider (why don’t we call him Bob), takes Alice’s public key and computes the encrypted message: $C = PK_A(M) = M^e \mod n$. Then, Alice would take $C$ and decrypt this message by computing: $M = C^d \mod n$. To see why this works, we have to consider another property that Euler discovered.
Euler’s Theorem: $a^{\phi(n)} \equiv 1 \mod n$ if $a$ and $n$ are relatively prime.

We can now prove that we can get the original message that Bob sent by using the formula, $M = C^d \mod n$. NOTE: This is not correct. There is a slight flaw in the proof below. Try to find it or see the comments for the correct proof.

$M = C^d \mod n = M = (M^e \mod n)^d mod n = (M^{ed} \mod n) \mod n$. We know from our definition of $d$ that $ed \equiv 1 \mod \phi(n)$. We can thus rewrite, $ed = 1 + h \cdot \phi(n)$ where $h$ can be any positive integer.

Thus, $(M^{ed} \mod n) \mod n = (M^{1+h \cdot \phi(n)} \mod n) \mod n = (M \cdot (1)^h \mod n) \mod n$ by Euler’s Theorem.

Simplifying even further, we get: $(M \mod n) \mod n \equiv M$. QED

The security of the RSA algorithm depends on how hard it is to factor $n = p \cdot q$ given that no one besides Alice knows what $p$ and $q$ are. (We can see this because calculating $\phi(n)$ depends on knowing $(p-1) \cdot (q-1)$. Once we know $\phi(n)$, we can compute $de \equiv 1 \mod \phi(n)$.)

The entire algorithm hinges on the fact that we don’t know an efficient way to factor large numbers. I’ll talk about various factoring techniques in my next blog post since this is already a very long blog post and I should probably be doing homework and sleeping (not simultaneously of course).

EDIT (04/17/2014): There’s a slight problem in my proof above. There is also a simple fix for it. I will leave it as an exercise for you to find the flaw in the proof. Answer will be in the comments.

This entry was posted in Algorithms and tagged , , , . Bookmark the permalink.

### One Response to Factoring and Security

1. Quanquan Liu says:

The proof is incorrect because in order to use Euler’s Theorem, $M$ and $n$ have to be relatively prime. In general, this does not have to be the case. Therefore, we have to prove RSA in another way.

We apply a similar analysis using the Chinese Remainder Theorem and Fermat’s Little Theorem.
From the Chinese Remainder Theorem:

$x \equiv y \mod{n} \leftrightarrow x \equiv y \mod{n}$ and $x \equiv y \mod{q}$.

Then, we can prove $M^{ed} \equiv M \mod{p}$ to prove the correctness of RSA.

Fermat’s Little Theorem applies when $M$ and $p$ are relatively prime. If $\gcd(M, p) \neq 1$, then $M \equiv 0 \mod{p}$ and $0^{ed} \equiv 0 \mod{p}$.

In the case when $\gcd(M, p) = 1$, then $M^{ed} \equiv M^{1 + h\cdot (p-1)(q-1)} \mod {p}$. By Fermat’s Little Theorem, $M^{ed} \equiv (M \cdot (1^{h\cdot (q-1)})^{p-1} \mod{p})$. This simplifies to $M \mod{p}$. We can make a similar argument for $q$ and by the Chinese Remainder Theorem prove the original.