2
$\begingroup$

I used primes $p = 7$, $q = 13$, to get $n = 91$ and $\phi(n) = 72$.

I chose $E=19<\phi(n)$, but found that $D=19$, which meant $x^E=x$ $(mod$ $n)$, i.e. the encryption is just the identity transformation!

I encountered the same issue with $E=17$.

My first question then is when you find $E$ and $D$ in practice, is it a case of trial and error until you find $E$ and $D$ that do encrypt the text? Is there some better way than trial and error?

Then I tried $E=11$ and got $D=59$. However, here I discovered that $x^{11}$ $(mod$ $91)$ and $x^{59}$ $(mod$ $91)$ are actually the same function, as well as being inverses of each other. I don't recall reading anywhere that the encryption key can also sometimes be the decryption key.

Further investigation showed that $x^{59}$ $(mod$ $91)$ may be split into $(x^{7})^7x^{10}$ $(mod$ $7)=x^{11}$ $(mod$ $7)$ and $(x^{13})^4x^7$ $(mod$ $13)=x^{11}$ $(mod$ $13)$, by the CRT and FLT, which $x^{11}$ $(mod$ $91)$ can also be split up into. Therefore they are the same function.

So my second question is under what conditions does the encryption key also act as the decryption key? Again in practice, is it just trial and error until you find keys without this drawback?

A third question also could be, is there something about $n=91$ that makes it impossible to use for RSA?

Thank you for your time. This is my first time using Stack Exchange so I hope to have posed an original and clear question.

$\endgroup$
  • $\begingroup$ In the first example, you do not get $x^E\equiv x\bmod n$. $\endgroup$ – Gerry Myerson Feb 21 at 5:53
  • $\begingroup$ You get $D=E$ when $D^2\equiv1\bmod{\phi(n)}$. $\endgroup$ – Gerry Myerson Feb 21 at 5:55
  • $\begingroup$ The original version of your question was better. $\endgroup$ – Randall Feb 21 at 15:41
  • $\begingroup$ Thank you Randall for taking the time to explore this for me. You have covered all the points I made. I think the final result you state is quite useful. $\endgroup$ – Kristof Arnaldo Feb 23 at 0:47
  • $\begingroup$ In practice, people don't choose a random $e$, but $e=2^{16}+1$ (an industry standard), as this ensures fast exponentiation and as this $e$ is prime, it will almost surely be relatively prime with $\phi(n)$; $d$ is then computed and typically (we're talking 100's of digits numbers here, eg. around 616 for 2048 bit moduli) is a lot larger than $e$. $e=d$ never occurs in practical cases, just in small toy examples. $\endgroup$ – Henno Brandsma Feb 23 at 17:50
0
$\begingroup$

If you know some basic group/ring theory (or maybe just quadratic residues) this is all easily explainable. Recall that once $E$ is selected, $D$ is dictated as $E^{-1} \bmod \varphi(n)$. In other words, $E$ is selected from the group of units $\mathbb{Z}_{\varphi(n)}^*$ and $D$ is then its inverse in this group. (As pointed out, your edit with $E=D=19$ is wrong regarding $x \mapsto x^E$ being the identity map.)

Now, how large is the group of units $\mathbb{Z}_{\varphi(n)}^*$? By some basic ring theory, this group has size $\varphi(\varphi(n))$. [In general, the ring $\mathbb{Z}_k$ has $\varphi(k)$ units.] For example, with $n=91$, $\varphi(n) = 72$ and sure enough, working mod $72$ there are $\varphi(\varphi(91)) = \varphi(72)=24$ units. In short, you only have $24$ valid choices for $E$ when you work RSA mod $91$.

Your (original) first question was, paraphrased: is $D=E$ always a possibility? And why does this happen? Here is the relevant fact for your question on why $D=E$ is possible. (In fact, it is inescapable: no RSA moduli avoid this phenomenon completely.)

Theorem: When $m \geq 3$, the value of $\varphi(m)$ is even.

The only RSA modulus for which this is false is $n=6$, which gives $\varphi(\varphi(6))=1$, odd. For all other RSA moduli $n$, we have that $\varphi(\varphi(n))$ must always be even.

Hence the group of units $\mathbb{Z}_{\varphi(n)}^*$, from which you selected $E$, has even order. Now any group of even order has at least one (probably more) element of order $2$ (meaning $x^2=1$), and such elements are there own inverses (meaning $x=x^{-1}$). This is what happened in your example. If you get out your modular calculator, set the modulus to $72$ and ask for the multiplicative inverse of $19$, you will see that the answer is itself. This must always happen for at least one key-choice of $E$ because this group has even order.

If this bothers you, then don't use it. Check that $D$ is not $E$, and if it was, then choose again. By probability, it won't happen again.

In your second example, you chose $E=11$ and $D=E^{-1} \bmod 72$ is in fact $D=59$. Nice observation that exponentiation by each results in the same function; this is insightful on your part. I'm not sure of a completely general set of conditions that explain or predict this based on $n$, $p$, $q$, etc. I will point out that, in your example, $n=91=7 \cdot 13$, and $p-1=6$ divides $q-1=12$.

Proposition: Suppose we have an RSA setup $n=pq$ with $E$ and $D$ correctly chosen. Then the encryption function $f: x \mapsto x^E \bmod n$ is the same as the decryption function $g: x \mapsto x^D \bmod n$ if $D$ is simultaneously congruent to $E$ modulo $p-1$ and $q-1$.

The proof of this is basically the same as the proof that RSA works. You can write $D=E + k(p-1)$ for some $k$, and $D = E + j(q-1)$ for some $j$. Show that $x^D \equiv x^E \bmod n$ by arguing mod $p$ and mod $q$ in cases. You'll need to consider when $x$ is divisible by $p$ and not $q$, the vice versa, then neither. It will all work because of Euler's theorem.

It gets worse in some cases. If we additionally knew that $p-1$ divides $q-1$, then we don't have to check both congruences above. This is your "problem," since $91 = 7 \cdot 13$ and $7-1$ divides $13-1$.

Corollary: Suppose we have an RSA setup $n=pq$ where $p < q$ and with $E$ and $D$ correctly chosen. Suppose also that $p-1$ divides $q-1$. Then the encryption function $f: x \mapsto x^E \bmod n$ is the same as the decryption function $g: x \mapsto x^D \bmod n$ if $D$ is congruent to $E$ modulo $q-1$.

Proof. If $q-1$ divides $D-E$ then $p-1$ also divides $D-E$, so the previous result applies. $\Box$

Note: This is exactly your situation. You have $E=11$ and $D=59$, and $D-E=48$ is divisible by $q-1=12$.

Finally, this business of $p-1$ dividing $q-1$ is not sufficient to create this behavior. So, whatever is going on with $n=91$, this isn't the whole explanation.

Example: With $p=11$ and $q=71$ we have $n=781$, $\varphi(n)=700$, and $p-1$ dividing $q-1$. However, plenty of key choices do NOT result in $x \mapsto x^E$ agreeing with $x \mapsto x^D \bmod n$. One example is $(E,D) = (3, 467)$.

There is one general thing you can say about the encryption function agreeing with the decryption function. Let $f : x \mapsto x^E$ be the encryption, and $g: x \mapsto x^D$ be the decryption, all mod $n$. We have $f \circ g =1=g \circ f$ by design. Certainly if $D=E$ then we'll have $f=g$, but as you've pointed out this need not be necessary. If $f=g$ this will say $f \circ f=1$. The converse is also true by uniqueness of inverses for bijective functions: $f \circ f =1$ implies that encryption is decryption. However, $f \circ f =1$ means that $f(f(x))=(x^E)^E = x^{E^2} \equiv x \bmod n$. However, we are now multiplying up in the exponent, so we should work mod $\varphi(\varphi(n))$, not just $\varphi(n)$. Hence we would have $f=g$ if $E^2 \equiv 1 \bmod \varphi(\varphi(n))$.

Sure enough, this is your example! With $n=91$, $\varphi(\varphi(n))=24$, and with $E=11$ we get $E^2 = 121 \equiv 1 \bmod 24$.

$\endgroup$

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.