RSA and extended euclidian algorithm

Question

I'm learning about RSA, public private key stuff, and I just found a very nice article explaining the basics.

http://arstechnica.com/security/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/

Let's make this more concrete with an example. Take the prime numbers 13 and 7. Their product gives us our maximum value of 91. Let's take our public encryption key to be the number 5. Then using the fact that we know 7 and 13 are the factors of 91 and applying an algorithm called the Extended Euclidean Algorithm, we get that the private key is the number 29.

I can't seem to make sense out of that. How do we get that 29?

Answer 1

I assume you know how RSA works and you just want to understand how to do computations explicitely.

Since we know $91=13\cdot 7$ we can easily get $\varphi(91)=12\cdot 6=72$. The private (decryption) key in RSA is obtained by computing the inverse of the public (encryption) key modulo $\phi(N)$, where $N=p\cdot q$ is the public "maximun number" as you called it in the yellow window. In your case the public key is $5$, so we want to find the inverse of $5$ modulo $72$. Let's observe that $GCD(5,72)=1$ and so by Bezout's identity we can find integers $a$ and $b$ such that $$ 5\cdot a+72\cdot b=1.$$ In other words, $$ 5\cdot a\equiv 1\mod 72,$$ and $a$ is the required inverse, i.e. the private key.

By the Euclid's algorithm, $$ 72=5\cdot 14+2$$ $$ 5=2\cdot 2+1$$ and coming back we finally get, $$ 1=5-2\cdot 2=5-2(72-5\cdot 14)=5(29)+72(-2).$$ In other words we have just found $a=29$ and $b=-2$. The private key is thus $29$.

This arguments is called "Extended Euclidean Algorithm" and works in general, but maybe it is worth to see at least once in a particular case.

Answer 2

The link you mention does not give enough details on RSA.

It is based on Euler's theorem: for any integer $x$ coprime to $n$, $x^{\varphi(n)}\equiv 1\mod n$. Little Fermat is a particular case.

To encrypt, you choose two prime numbers $p$ and $q$, and in exponent $e$ coprime to $\varphi(pq)=(p-1)(q-1)$. Let's denote $n$ the cipher modulus. The exponent $e$ is invertible modulo $\varphi(n)$; let $f$ be its inverse (it can be found by the extended euclidean algorithm).

Each letter of a message is encoded with an integer $x<n$, then $x$ is encrypted as $y=x^e\bmod n$. To decrypt, it is enough to compute $y^f$.

Indeed, if $x$ is coprime to $p$: $$y^f=x^{ef}=x^{1+k\,\varphi(n)}=x\cdot\bigl(x^{p-1}\bigr)^{k(q-1)}\equiv x\cdot1=x \pmod p $$ This remains true if $x\equiv 0 \mod p$.

The same result is true for $q$. Hence $y^f\equiv x $ both modulo $p$ and modulo $q$. By the Chinese Remainder Theorem, $\,y^f\equiv x\mod pq=n$.