1
$\begingroup$

I`m solving one crypto problem on rsa.

p^e - q^e = C1 (mod n)
(p-q)^e   = C2 (mod n)

n = p*q*r; p,q,r are prime numbers
e = 2 * 65537

We have e, n, C1, C2.

It's impossible to find p, q, r from this system of equations, since there are 3 unknowns in the system of 2 equations. But is there any way to reduce the possible options?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ The argument about the number of variables and equations only holds for real valued variables. With just n as the product of the primes, over the integers it is uniquely defined (ignoring relabeling). You could try: Expand the C2 equation and see what you get. And also make use of the fact that e is even. But I don't have an intuition if C1 and C2 reveal the factorization or not. $\endgroup$
    – tylo
    Nov 17, 2022 at 9:45
  • 2
    $\begingroup$ See if you can find a combination of $C_1$ and $C_2$ that is divisible by $p$ and ditto for $q$. $\endgroup$
    – Daniel S
    Nov 17, 2022 at 11:05

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.