What is the relation between RSA & Fermat's little theorem?

Question

I came across this while refreshing my cryptography brain cells.

From the RSA algorithm I understand that it somehow depends on the fact that, given a large number (A) it is computationally impossible to derive at the two prime numbers (B & C) whose product it is.

But that isn't the Fermat Theorem, is it?
It's something on the lines of showing that there is no solution $n$ ($n > 2$) such that: $X^n + Y^n = Z^n$.

Can someone throw some light on this?

Answer 1

To walk you through RSA from start to end, here's how it works.

1. Choose two large distinct primes $p$, $q$. Calculate $n=pq$.
2. Calculate $\phi(pq)$. This happens to be $(p-1)(q-1)$.
3. Choose $e$ such that $gcd(e, \phi(pq)) = 1$ and $1 < e < \phi(pq)$.
4. Compute $d$ such that $de = 1 \mod \phi(pq)$.
5. Do some crypto; $c = t^e \mod n$ and $t = c^d \mod n$.

What you really want to know is why these statements hold. Fermat's little theorem states that $a^p = a \mod(p)$. An alternative, equivalent definition is that $a^{p-1} = 1 \mod(p)$.

Actually, for the purposes of RSA, that's insufficient. What you want is a generalisation called the Euler-Fermat generalisation, which states:

$$a^{\phi(n)} = 1 \mod{n}$$ Next up—what the hell is this $\phi(x)$ function? In plain English, it's the number of numbers less than or equal to $x$ which are also coprime to it. For any given prime $p$, every number less than itself is coprime to it, which means $\phi(p) = p-1$. If you're wondering about why $\phi(1) = 1$, well, $gcd(x, 1) = 1$ is the definition of coprimality, including for 1 itself.

Now, it's also possible to prove that $\phi(xy) = \phi(x)\phi(y)$. Unless someone really wants me to, I'll skip the details (see a textbook on number theory) but, this essentially means $n = pq \Rightarrow \phi(n)=\phi(p)\phi(q) \Rightarrow \phi(n)=(p-1)(q-1)$.

Now, a little group theory too. Multiplication for certain sets of positive integers forms a group under modulo provided all the elements you pick for it are coprime to the modulo you're using. It so happens we've picked $e$ to be co-prime to our modulo $\phi(pq)$. Group theory guarantees us the existence of an integer in the group that acts as an inverse uniquely for that integer and transforms, under multiplication, that integer to the identity. The identity element under multiplication is $1$ and the inverse here is $d$.

So, let's recap: we've got $e$ and we've got $d$. One is the inverse of the other under the group $\phi(n)$. What we need is a link back to the Euler Fermat generalisation showing this:

$$ t = ((t^e)^d) = t^{ed} \mod (n) $$

So, before we do that let's just review what we understand by congruences. If I have the number $4 \mod (9)$, are you happy that $13 = 4 \mod(9)$? And that $22 = 4 \mod 9$? And that $31 = 4 \mod (9)$? You should see a patter emerging here; in fact, your general representation in this case is $4 + 9k$ generates you the set of numbers that are equivalent to $4$ modulo $9$.

So, $de = 1 \mod \phi(pq)$ could be expressed as $de = 1 + k\phi(pq)$, yes? I.e. to 1, I can add multiples of $\phi(pq)$ then apply modulo $\phi(pq)$ and it'll be equivalent to 1. This might take some getting your head around.

Once you've got there, $t^{ed} = t^{1+k\phi(pq)} \mod (pq)$. All I've done is substitute one expression for the other; no magic. Now a little re-arranging: $t^{1+k\phi(pq)} = t^1 t^{k\phi(pq)} \mod (pq)$ then $t^{1}t^{k\phi(pq)} = t^1 (t^{\phi(pq)})^k \mod (pq)$.

Now, we use the Euler-Fermat generalisation. Notice we have $t^{\phi(pq)} \mod (pq)$. Being "under modulo", we can still evaluate this, since the power to the $k$ simply means multiplying $k$ lots of that expression together. So now, apply the theorem:

$$t^{\phi(pq)} = 1 \mod (pq)$$

and we're left with $t^1 (t^{\phi(pq)})^k = t^1 \times (1)^k \mod (pq)$, which as you probably know is just $t$.

So, that is how they relate. This isn't the only way to prove RSA either. The Chinese Remainder Theorem proof I think is nicer, but I also think it is harder to understand.

Answer 2

$X^n + Y^n = Z^n$ (i.e. the impossibility of this with $n > 2$ and $X,Y,Z > 1$) is known as "Fermat's (big) theorem" (the one where the margin was not big enough for the proof). But the theorem important for RSA theory is known as "Fermat's little theorem":

$$ a^p \equiv a \mod p \text{ (if $p$ prime)} $$

or, equivalent (for prime $p$ and $a < p$):

$$ a^{p-1} \equiv 1 \mod p $$

This is generalized by Euler's theorem for all integers, not just primes:

$$ a^{\phi(n)} \equiv 1 \mod n $$

If you let $n = p$ ($p$ prime), then $\phi(p) = p -1$. This translates as "The number of numbers between $1$ and $p$ that are co-prime to $p$ is $p-1$, if $p$ is prime".

This is used in RSA: We choose two large primes $p$ and $q$, $n = p·q$ and then we compute $\phi(n)$ which is equal to $(p-1)(q-1)$. This holds because if $p$ and $q$ are both prime, then the numbers co-prime to $p$ are also co-prime to $q$ and vice versa (other than the multiples of both), thus $$\phi(n) = \phi(p·q) = \phi(p) · \phi(q) = (p-1)(q-1).$$ We then derive the public and private exponents, aka the public and private key, from this $\phi(n)$.

Answer 3

No, it's not that Fermat Theorem. It's Fermat's Little Theorem which states

If $p$ is prime, then $a^p$ is congruent to $a$ modulo $p$.

This theorem is needed in the proof of correctness of the RSA algorithm (the Chinese remainder theorem is needed as well). Any introductory text that covers RSA should cover this (and any introductory text that does not is not worth the paper it is printed on).

From the RSA algorithm I understand that it somehow depends on the fact that given a large prime number (A) it is computationally impossible to derive at the two prime numbers (B & C) whose product it is.

This is not correct. A prime number can not possibly be the product of two other primes. Rather, it is the modulus $n$ that is the product of two large primes, typically called $p$ and $q$.

Answer 4

I guess that you mean the Fermat's Little Theorem.

The above anwers are very detailed, but they are incomplete.

This is the supplement to the above answers.

In order to point out the problem, we first review the Euler Theorem.

Euler Theorem If $n \ge 1$ and $gcd(a,n)=1$, then $a^{\varphi(n)} \equiv 1 \pmod n$.

If $p$ is a prime number, $\varphi(p)=p-1$, we get the Fermat's Little Theorem.

Fermat's Little Theorem Let $p$ be a prime and suppose that $p \not | a$. Then $a^{p-1} \equiv 1 \pmod p$

There's an implicit condition in the above answers according to Euler Theorem.

$$t^{ed} \equiv t \pmod {(pq)}$$

The implicit condition is $gcd(t,pq) = 1$, then $t^{ed} \equiv t^{k\varphi(pq)+1} \equiv t \pmod {pq}$
But what if $gcd(t,pq) \not= 1$? For instance $t=r\cdot p$ or $t=s \cdot q$.

Now we prove the situation $$t^{ed} \equiv t \pmod {(pq)}, gcd(t,pq) \not= 1$$
by a very simple method not using Chinese Remainder Theorem.

First we give one Theorem. It lies in the book 《elementary number thoery 6th》 Corollary 4.9.1.

Corollary 4.9.1 If $a\equiv b \pmod {m_1},a\equiv b \pmod {m_2},...,a\equiv b \pmod {m_k}$, where $a$ and $b$ are integers and $m_1,m_2,...,m_k$ are pairwise relatively prime positive integers,then
$$a \equiv b \pmod {m_1m_2\cdot \cdot \cdot m_k}.$$

So, If

$$t^{ed} \equiv t \pmod {p}$$ $$t^{ed} \equiv t \pmod {q}$$ $$gcd(p,q)=1$$

hence

$$t^{ed} \equiv t \pmod {(pq)}$$

since $p$ and $q$ are on an equal footing, we only prove:

$$t^{ed} \equiv t \pmod {p}$$

This is the proposition to be proved:

Let $p$ and $q$ be primes and suppose that $gcd(t,pq) \not=1$, $e\cdot d = k \varphi(pq)+1$, then
$$t^{ed} \equiv t \pmod {p}$$

Proof:

1. suppose $t \not \equiv 0 (mod\ p) \Rightarrow gcd(t,p) =1$

hence
$$ t^{ed} \equiv t^{k\cdot \varphi(n)+1} \equiv t^{k(p-1)(q-1)+1} \equiv t(t^{p-1})^{k(q-1)} \pmod p$$ since $gcd(t,p)=1$, by Fermat's Little Theorem
$$ t^{p-1} \equiv 1 \pmod p$$ hence
$$ t^{ed} \equiv t(t^{(p-1)})^{k(q-1)} \equiv t\cdot 1^{k(q-1)} \pmod p$$ hence
$$ t^{ed} \equiv t \pmod p$$

2. suppose $t \equiv 0 \pmod p $

hence $$t^{ed} \equiv 0^{ed} \equiv 0 \equiv t(mod\ p)$$

hence, we proved the proposition:

$$t^{ed} \equiv t \pmod {p}$$

In the same way:

$$t^{ed} \equiv t \pmod {q}$$

by Corollary 4.9.1:

$$t^{ed} \equiv t \pmod {(pq)}$$