In RSA algorithm we have the value of $e$ & $d$ exponent and also one of the prime numbers. My question is how to produce another prime number that is not equal to the first one and the digit of a prime number is 1024.

  • 1
    $\begingroup$ Do I understand correctly that you have $e$, $d$, and $p$, but not $n$ or $q$, and you want to find some $q$ so that $ed \equiv 1 \pmod{\phi(pq)}$? $\endgroup$ – Squeamish Ossifrage Jun 4 '19 at 18:02
  • $\begingroup$ I have just the value of e, d, p and I want to find the exact q so that ed≡1(modϕ(pq)) $\endgroup$ – Aida Jun 7 '19 at 10:25

Here's the problem: you have values $e, d, p$ that satisfy the relation:

$$ed - 1 = k(p-1)$$

for some integer $k$; what you want to do is find some other prime $q$ (within some size range) that satisfies the relation:

$$ed - 1 = k'(q-1)$$

(for some integer $k'$)

Without this first relation, finding the second one would be difficult (as we would need to find a 1024 bit factor in $ed-1$, and that's difficult), however by leveraging the first relation, it is practical.

Here's one way to proceed:

  • Compute $k = (ed - 1)/(p - 1)$, and then obtain a partial factorization (that is, find all the prime factors below a smoothness bound $M$ of both $k$ and $p-1$); namely:

$$p - 1 = p_0 p_1 p_2 … p_n c$$

$$k = p'_0 p'_1 p'_2 … p'_{n'} c'$$

(for prime $p_0, p_1, …, p_n, p'_0, p'_1, …, p'_{n'}$, and integers $c, c'$ with no prime factors $< M$)

Then, iterate through the various subsets of the values $c', p_0, p_1, …, p_n, p'_0, p'_1, …, p'_{n'}$, for a subset which:

  • The product $q-1$ of the elements of the subset is within the size range

  • One more than the product ($q$) is prime.

A value $q$ that satisfies both above relations is a valid possibility for the prime you're looking for (and there may be multiple).

This will always succeed if there is such a $q$ (that is, your $e, d, p$ values came from a valid RSA key), and if $\gcd( p-1, q-1 ) < M$ (which is likely to be the case if $p, q$ were not specially selected to have a large gcd).

| improve this answer | |

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