2
$\begingroup$

When studying RSA, and proving simple concepts to myself, I went and understood groups and rings, but I failed to understand Lagrange's theorem.

I did understand how from invertible finite groups I could derive Euler's theorem and Fermat's little theorem, etc. But one point remained...

When extracting the invertibles from $N \rightarrow U(N)$, we get the elements which form a group. I also saw that the order of any element in that belongs to $U(N)$, which is the order of $U(N)$. For example, if the number $10$ is $N$, $1,3,7,9$, it forms a group under multiplication $\bmod 10$. Now any element $a$, let it be $7$, the order of $7$, is $4$, which is also the sum total of the co-primes or the order of $U(N)$. This proves Euler's theorem, and thus, Fermat's as well. But when doing RSA, we do the same thing; however, during key generation, we choose a number that is a co-prime to the order of $U(N)$, which also does from an invertible group $1$ and $4$.

Therein lies the rub, which I don't understand at this moment. What does the order of $U(N)$ have to do with key generation?

I have been unable to find a direct visual link. Ultimately, we are not choosing an element $E$ that belongs to $U(N)$, but an element that forms a group under $U|U(N)|$. And again, when encrypting, we are doing $M^{ed} \bmod N$.

I am not getting the relation between $U(N)$ and the number of elements in $U(N)$ when we are not using the order as an exponent to any element within $U(N)$ to get $1$ or something like that. Why are we generating the key from the number of elements in $U(N)$, and why does it work? What's the relation?

| improve this question | | | | |
$\endgroup$
  • $\begingroup$ It is not proving Euler's theorem, it just justifies it. $\endgroup$ – kelalaka Mar 12 at 15:33
2
$\begingroup$

What does the order of $U(N)$ has to do with RSA key generation?

The usual notation is $\Bbb Z_N^*$ for the multiplicative group modulo $N$, that the question names $U(N)$, and $\Phi(N)$ or equivalently $\varphi(N)$ for its order (number of elements), as given by Euler's totient function.

$\forall x\in\Bbb Z_N^*$, it holds $x^{\Phi(N)}\equiv1\pmod N$. This implies: $$\forall x\in\Bbb Z_N^*,\ \forall k\in\Bbb N,\ \text{ it holds }\ x^{(k\,\Phi(N)+1)}\equiv x\pmod N\tag{1}\label{eq1}$$

We want the RSA encryption exponent $e$ and decryption exponent $d$ (both strictly positive integers) to be such that textbook RSA encryption of a plaintext $m$ followed by decryption consistently returns the original plaintext. That is, we want that $\forall m\in[0,N)$, it holds $((m^e)\bmod N)^d\bmod N=m$. We can write this goal as: $$\forall m\in[0,N),\ \text{ it holds }\ m^{(e\,d)}\bmod N=m\tag{2}\label{eq2}$$

We can now see what $\Phi(N)$ has to do with RSA key generation: if $$e\,d\equiv 1\bmod\Phi(N)\tag{3}\label{eq3}$$ then by definition of that, and given that $e$ and $d$ are strictly positive integers, $\exists k\in N$ such that $e\,d=k\,\Phi(N)+1$, and we nearly can use $\eqref{eq1}$ to prove that $\eqref{eq2}$ holds. The one gap is that we only prove the weaker $$\forall m\in[0,N),\ \text{ if }\ \gcd(m,N)=1\ \text{ then }\ m^{(e\,d)}\bmod N=m\tag{2'}\label{eq2'}$$

We have proven that condition $\eqref{eq3}$ is sufficient to insure that textbook RSA encryption of a plaintext $m$ followed by decryption returns the original plaintext, at least when $\gcd(m,N)=1$. Since $N$ is the product of large primes, $\gcd(m,N)=1$ holds for most $m$.


Further, under the extra condition that $N$ is squarefree (including $ N=p\,q$ with $p$ and $q$ distinct primes), it can be proven that for all $m$ textbook RSA encryption followed by decryption returns the original plaintext.

Otherwise said: one way to see RSA is as working with message and ciphertext in the group $(\Bbb Z_N^*,*)$, but that restricts the message space. It can be extended to $(\Bbb Z_N,*)$ when $N$ is squarefree, that is when $N$ is not divisible by the square of any prime.

We first prove that $\eqref{eq3}$ implies that $m^{(ed)}-m\equiv0\pmod{p_i}$ for each prime $p_i$ dividing $N$, by treating separately the case $m\equiv 0\pmod{p_i}$. The integer $m^{(ed)}-m$ is thus divisible by each $p_i$, thus by their product, which is $N$ when $N$ is squarefree, thus $m^{(ed)}-m\equiv0\pmod N$.


Notice that the condition $\eqref{eq3}$ is sufficient, but not necessary. For a necessary and sufficient condition, we want $$e\,d\equiv 1\bmod\lambda(N)\tag{3'}\label{eq3'}$$ where $\lambda$ is the Carmichael function.


Notations:

  • $\forall$ is read "for all". $\in$ is read "in". $\exists$ is read "exists".
  • $\Bbb N$ is the set of natural numbers: $\Bbb N=\{0,1,2,3,4,5,\ldots\}$.
  • $\Bbb P$ is the subset of $\Bbb N$ consisting of primes: $\Bbb P=\{2,3,5,7,11,\ldots\}$.
  • $\Bbb Z$ is the set of (signed) integers: $\Bbb Z=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$.
    $(\Bbb Z,+)$ is a group.
  • $x\equiv y\pmod n$ is read "$x$ is equivalent to $y$ modulo $n$".
    It means that $n$ exactly divides $x-y$ (for $n$ a strictly positive integer).
    Alternative notations are $x\equiv y\ \ [n]$ or $x=y\pmod n$ or $x=y\ \ [n]$.
  • $x=y\bmod n$ is read "$x$ is set to $y$ modulo $n$" or "$x$ equals $y$ modulo $n$".
    It means that (after the setting, if any) $0\le x<n$ and $x\equiv y\pmod n$ (see above for the meaning).
    When $y\ge0$, the quantity $y\bmod n$ is the remainder of the Euclidean division of $y$ by $n$. The quantity $y\bmod n$ is $0$ when $n$ divides $y$ (and the C programmer writesx = y % n for a computation orx == y % n for a test). When $y<0$, we can compute $y\bmod n$ as $n-1-((-y-1)\bmod n)$.
    Note: Textbook RSA encryption and decryption reduce their result $\bmod N$, ensuring that the ciphertext and the deciphered plaintext are in $[0,N)$.
  • $\Bbb Z_n$ is the finite set of integers modulo $n$. That is, the elements of $\Bbb Z$ equivalent modulo $n$ are regrouped into a single element of $\Bbb Z_n$. Thus $\Bbb Z_n$ has $n$ elements.
    $(\Bbb Z_n,+)$ is a group. With multiplication noted $*$ when not omitted, it becomes the ring $(\Bbb Z_n,+,*)$.
    When the modulo $n$ is prime, $(\Bbb Z_n,+,*)$ is a field, because all elements except $0$ have a multiplicative inverse. As practice of notation: $\forall p\in\Bbb P$, $\forall x\in\Bbb Z_p$, if $x\ne0$ then $\exists y\in\Bbb Z_p$ such that $x*y=1\pmod p$ (also noted $x\,y=1\pmod p$ as a shortcut).
  • $\Bbb Z_n^*$ is the set of the elements of $\Bbb Z_n$ that have an inverse under multiplication, that is the set of $x$ with $n$ and $x$ having no common positive divisor beyond $1$, that is $\gcd(x,n)=1$.
    $(\Bbb Z_n^*,*)$ is a group including when $n$ is not prime. It has $\Phi(n)$ elements.
| improve this answer | | | | |
$\endgroup$
  • $\begingroup$ I would love if I could understand it. Being a non mathematics guy, the signs confuse me too much :( $\endgroup$ – C0DEV3IL Mar 12 at 22:10
  • $\begingroup$ @C0DEV3IL: notation helps a lot. I've added what you need for RSA. Try it, your question suggests that you understand the notions, and only have that little hurdle to pass. $\endgroup$ – fgrieu Mar 13 at 7:42
  • $\begingroup$ @kelaka: I got that you suggest that I change how I reference equations, but how exactly? $\endgroup$ – fgrieu Mar 13 at 18:10
  • $\begingroup$ I should change my nickname. I've checked that there is no direct support. However, this answer contains some nice tricks. Does MathJax really limited :) $\endgroup$ – kelalaka Mar 13 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.