0
$\begingroup$

I am studying RSA cryptosystem and here is the question that came to my mind. Let's pick $p, q$ to be two primes and $n = p * q$. From that we calculate Euler's totient function:

$$ \phi(n) = (p - 1)(q - 1). $$ Then we chose the public and private key pair as $e, d$ such that: $$ e * d \equiv 1 \text{ mod } \phi(n). $$

Now I want to prove that for the same pair $(e, d)$ it no longer holds that:

$$ e * d \equiv 1 \text{ mod } n. $$

I have tried writing: $$ e * d = k * \phi(n) + 1\\ e * d = l * n + 1, $$ for some integer $k$ and $l$. So it should be that: $$ k * \phi(n) + 1 = l * n + 1 \\ k * \phi(n) = l * n. \\ $$ So replacing the values of $n = pq$ and $\phi(n) = (p - 1)(q - 1)$ we get: $$ k * (p - 1) * (q - 1) = l * p * q. $$ I sense that there is an impossibility. But can't figure out what it is. Thanks in advance.

$\endgroup$
2
  • $\begingroup$ What is the proposition to prove exactly? The proposition in title is incorrect. A counterexample is $e=d=1$. Another with $e$ valid in some mathematical definition of RSA is $p=13$, $q=17$, $e=5$, $d=16973$. These parameters work, in the sense that we can successfully decrypt with $(n,d)$ what was encrypted with $(n,e)$. $\endgroup$
    – fgrieu
    Dec 3, 2023 at 17:52
  • $\begingroup$ I don't understand what you exactly mean. I think your question can be converted to another representation: There is no isomorphic function $\zeta:Z^*_{\phi(N)}\to Z^*_N$ , s.t. given two group elements $e,d=e^{-1} \in Z^*_{\phi (N)}$, $\zeta(e)\cdot\zeta(d)=1modN$. $\endgroup$
    – X.H. Yue
    Dec 4, 2023 at 0:37

1 Answer 1

2
$\begingroup$

Now I want to prove that for the same pair $(e,d)$ it no longer holds that:

That you are running into difficulties proving it may be due to the fact that it is, as you have laid out, not true.

Consider the values:

$$e = 1 + apq(p-1)(q-1)$$ $$d = 1 + bpq(p-1)(q-1)$$

for arbitrary integers $a, b$.

With these values, it is straight-forward to verify that these both hold:

$$ed = 1 \pmod{(p-1)(q-1)}$$ $$ed = 1 \pmod{pq}$$

Of course, if $a, b > 0$, these are huge values of $d, e$, but there's nothing that says they can't be huge.

On the other hand, if we add in the assumptions that:

  • $p-1$ does not have $q$ as a factor
  • $q-1$ does not have $p$ as a factor
  • $p, q$ are both primes (standard with RSA; let us be explicit about that)
  • $e, d > 1$
  • $e, d < \phi(n)$

Then both relations cannot hold simultaneously. I believe that you would find it instructive to show that from what you have; the steps you have written out is already half the work...


To show that the first two assumptions are necessary, I found this counterexample if we don't include those assumptions:

$$N = 5671 = 53 \times 107$$ $$E = 615$$ $$D = 959$$

Computation shows that both $E\cdot D = 1 \pmod{N}$ and $E \cdot D = 1 \pmod{\phi(N)}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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