0

Using RSA: we know N, two public exponents ($e_1$ and $e_2$) and two secret exponents ($d_1$ and $d_2$). Find primes p and q if $N=pq$.

We know: $\gcd(e_1,(p-1)(q-1))=1$, $\gcd(e_2,(p-1)(q-1))=1$, $e_1d_1\equiv 1$ and $e_2d_2\equiv 1$ mod$(p-1)(q-1)$. We also get the hint $\gcd(e_1d_1-1,e_2d_2-1)=b$, where b is known.

Assuming we know $e_1,e_2,d_1,d_2,N, b$, how do I find p and q? I tried to rewrite some congruences but got nowhere.

Linelina
  • 205
  • Ok I have $\gcd(a(p-1)(q-1),b(p-1)(q-1))=b$ since $e_1d_1-1=a(p-1)(q-1)$ and $e_2d_2-1=a(p-1)(q-1)$. But I cant assume $\gcd(a,b)=1$ so I cant say that $(p-1)(q-1)=b$? – Linelina Feb 18 '20 at 19:00
  • In fact, knowing one pair $e$ and $d$ already lets you factor $N$. Read the original RSA paper for the algorithm... I don't see the point of this exercise. Of course it's almost sure that $\gcd(e_1d_1-1,e_2d_2-1)=\phi(N)=(p-1)(q-1)$ and knowing that value is certainly enough, to find $p$ and $q$ (it's a quadratic). – Henno Brandsma Feb 18 '20 at 22:59
  • @HennoBrandsma, I assume you used that a and b is relative prime, how do you show that? – Linelina Feb 19 '20 at 15:32
  • There is no $a$ involved. Most likely $b=\phi(N)$ or a small multiple. It's easily spotted. – Henno Brandsma Feb 20 '20 at 11:15

0 Answers0