2
$\begingroup$

I am not very familiar with RSA, so this question may appear to be stupid.

Suppose that in RSA encryption, we are given $c$ (the ciphertext) and $N$ (the semi-prime modulus), can we find a pair of exponents such that $c^a \bmod N = c^b \bmod N$?

This has nothing to do with decrypting RSA; I’m just curious whether it is possible to find a pair of exponents that can produce this result? Would this be feasible if the exponents are really large numbers (for example, 300 decimal digits or more)? If so, is there any computer algorithm that I can use to do this?

Improve this question
$\endgroup$
1
  • $\begingroup$ As an attacker, no. But there can be more than one private exponent, due to the Carmichael's $\lambda(n)$ Function. See an example here $\endgroup$
    – kelalaka
    Commented Dec 26, 2019 at 8:05

1 Answer 1

Reset to default
3
$\begingroup$

If you find such you can break RSA.

Assuming the order of c is maximal(likely if c is random ciphertext). If we have such distinct exponents 𝑎 and 𝑏 they must be equal mod $\lambda(n) = lcm(p-1,q-1)$.

Let the difference between the exponents be $f=b-a$, $f=0\space mod \lambda(n)$

We pick a value e coprime with e, pick a small prime and verify. We will then calculate $d = e^{-1} mod f$

We can then find the factorization of N using the algorithm described: https://www.di-mgt.com.au/rsa_factorize_n.html

So no, if you do not know the factorization of $n$ you can't find such an exponent pair.

Example: 

N= 25777 //from link
c= 1517 //randomly chosen
a = 111 //less randomly chosen(I picked)
Possible b are: 6475,12839,19203,25567 we will pick the last one
this gives us f=25456
We try e=3 and verify indeed gcd(e,f)=1
We use extended eucleadean algorithm to find d=16689 and this is exactly the value used in the above link to factorize n.

If we pick b=19203
we get f=19092 and e=3 doesn't work so we will pick e=5 
We get d=7637 

we follow the algorithm linked
k=de-1 = 38184

We try several g, skipping to g=5
t=k=38184
g^t % n = 1 
t=t/2 = 19092
g^t % n = 1 
t=t/2 = 9546
g^t % n = 15050
and we check gcd(15050,n) = 149

We found a non trivial factor of n. Q.E.D

Edit 2: Fgrieu comments the proof above does not hold in the general case. For some N the first assumption of high order may not be sound, and for very large b-a the last algorithm may not be efficient. I do not know how to rectify these. Which means though this "proof" should still be sufficient evidence that the original problem in the question of finding such a pair a,b is indeed very hard. Yet this is not a solid reduction between that problem and factorization in the general case.

Improve this answer
$\endgroup$
10
  • $\begingroup$ Can you write a reduction for this? Maybe they are equal mod $\phi(N)$ but multiplied by a large random number. I may be missing something really simple, but I'm not sure that this argument goes through. $\endgroup$
    – Yehuda Lindell
    Commented Dec 26, 2019 at 11:38
  • $\begingroup$ The answer here is equivalent: crypto.stackexchange.com/questions/62409/equations-modulo-phin $\endgroup$
    – Meir Maor
    Commented Dec 26, 2019 at 13:08
  • $\begingroup$ Is that really equivalent? There you have x+a1 = x+a2 but you know both a1 and a2. $\endgroup$
    – Yehuda Lindell
    Commented Dec 26, 2019 at 14:05
  • $\begingroup$ read the answer, it finds f=0 mod phi(n) and then creates a new d,e pair and then factorizes n. $\endgroup$
    – Meir Maor
    Commented Dec 26, 2019 at 16:29
  • 2
    $\begingroup$ Actually, they needn't be equal mod phi(n); for two reasons: one, if we looking for a, b values that work for any c, then they need to be equal mod lambda(n) = lcm(p-1, q-1), which is smaller than phi(n), and two: the order of c might be even smaller than that - it will be a divisor of lambda(n), but may be smaller. On the other hand, your main point that knowledge of such an a, b pair would allow you to efficiently factor is, with high probability, true (assuming c is selected randomly - some c values, such as c=1 and c=n-1, might not allow such an efficient factorization $\endgroup$
    – poncho
    Commented Dec 27, 2019 at 4:10

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.