# How can I find the prime numbers used in RSA?

I got this question in a local hacking event, but I couldn't solve it.

Problem Statement ----

Continuing their snooping habit, NSA kept bugging Alice's communication. Resorting to the age old RSA encryption, Alice used 128-bit RSA encryption to exchange messages. Alice shares her public key as 0xffffffa95256a837568a41c265f4fe27110814aae19f144762d5cc0bcb931807 and her public key exponent $e$ (derived from $\phi(n)$) as 0x11 with Warden.

However, NSA, with its enormous resource, cracked this 128 bit encryption super easily. Seeing your work on the previous ciphers, NSA decided to offer you a job in their Cryptography group. As a final test, NSA shared this public key which they intercepted from Alice and Warden's conversation. They also gave away the private key that they computed from their message exchange.

Public Key:
0xffffffa95256a837568a41c265f4fe27110814aae19f144762d5cc0bcb931807
0x11

Private Key:
0xffffffa95256a837568a41c265f4fe27110814aae19f144762d5cc0bcb931807
0xc3c3c3817b3335577e69b9d0e48e2bc1fdf71f1f4f73a38a7d628d39739bbaf1


What are the values of $p$ and $q$? (the prime numbers used in key generation)

How can I find the prime numbers used in RSA?

• To answer this question you need to understand what the private key given in the problem means (what do the two numbers stand for). Once you do the answer should be relatively simple. Commented Jan 25, 2014 at 7:20
• @Thomas can you please explain what those two number mean in private key. Commented Jan 25, 2014 at 7:51
• Alice did as explained here, but with a public key which would have been imprudently small even in 1978, thus you can solve the problem given the first number only, or be smarter and use all three.
– fgrieu
Commented Jan 25, 2014 at 10:51

Well, this is semi-easy. You should know that public key consists of modulus $N = pq$ with public exponent $e$ and private key is the same modulus with private exponent $d$, where $de=1\pmod{\varphi(N)}$. Now, calculate $k = de-1$ then brute force $gcd(g^{k/2^x}\pm 1, N)$ for random $g$ and small $x$, and with high probability that quickly provides one of the primes. Code example in Python:

>>> n = 0xffffffa95256a837568a41c265f4fe27110814aae19f144762d5cc0bcb931807
>>> e = 0x11
>>> d = 0xc3c3c3817b3335577e69b9d0e48e2bc1fdf71f1f4f73a38a7d628d39739bbaf1
>>> from fractions import gcd
>>> for g in range(1, 9): print (g, gcd(n, pow(g, ((d * e - 1) / 2 ** 2), n) - 1))
...
(1, 115792086900472091959223405310199004229068084504756221892949117819703713273863L)
(2, 115792086900472091959223405310199004229068084504756221892949117819703713273863L)
(3, 115792086900472091959223405310199004229068084504756221892949117819703713273863L)
(4, 115792086900472091959223405310199004229068084504756221892949117819703713273863L)
(5, 340282363487254643170864374573732807431L)
(6, 115792086900472091959223405310199004229068084504756221892949117819703713273863L)
(7, 340282363487254643170864374573732807431L)
(8, 115792086900472091959223405310199004229068084504756221892949117819703713273863L)


Voila. $p$ is 340282363487254643170864374573732807431 and $q$ is $N/p$.

• unable to get the value of q. can you plz tell the value of q Commented Jan 25, 2014 at 12:13
• @user11621 $N=p*q$ so, given $N$ and $p$, simply divide. If you mean you don't have a calculator that supports such large numbers, install python. Commented Jan 25, 2014 at 14:14
• Or if you are lazy, just use WolframAlpha Commented Jan 25, 2014 at 14:35
• I have Wolfram Alpha Pro Premium and it failed me because the input was too big; python on the other hand did not! Commented Sep 29, 2018 at 21:42

If $N = pq$ and both $p$ and $q$ are close to $\sqrt N$, chances are that there exists an odd integer $x$ close to $\sqrt N$, such that $r = N \bmod x^2$ is significantly smaller than $N$. This happens to be the case for the public modulus in the example. When this happens, note that $p = x - s$ and $q = x + t$ for some positive integers $s, t$ such that $k = |s-t|$ is a small integer (e.g. $k = 0, 2, 4$) that can be determined from $r$ by noting that $r + st - xk = 0$. By quickly finding $k$ you may determine $r' = xk - r$ and you are left with the equation $r' = s(s+k)$ which is also quickly solved in $s$.

In this case:

• $\sqrt N \approx x =$ 0xFFFFFFD4A92B507086D1D87406814303
• $r = N \bmod x^2 =$ 0x1FFFFFF99525AA0E0CD8BB0EB0D0285FE
• $k = 2$
• $r' =$ 0xFFFFC00004017FFFD00000008
• $\sqrt {r'} \approx s =$ 0x3FFFF80000002
• $p =$ 0xFFFFFFD4A92B507086D5D87386814307
• $q =$ 0xFFFFFFD4A92B507086CDD87486814301

This is calculated in a split second on an ordinary PC and only requires that you know the public modulus.

• Interesting approach, where to read about it? Also, Fermat's factorization method factors this modulus in one step. Commented Jan 27, 2014 at 13:20
• The approach is just basic algebra. If the factors are close to the floor $x$ of the square root, the equation $r + (x-p)(q-x) - x(q+p-2x)$ will be dominated by the first and third term and the second factor of the third term will consequently be a function of the magnitude of $r$. Commented Jan 27, 2014 at 13:34
• so to avoid such solution for finding p and q, there should be distance between p and q? Commented May 17, 2017 at 7:48
• Yes. But most importantly, to avoid such solutions p and q have to be much greater (1024 bits each or more) and have to generated randomly from a greater range of numbers. Commented May 17, 2017 at 8:08

The private key (the "private" part of it) can be either given as $p$ and $q$, $\varphi(n)=(p-1)(q-1)$ or as your private exponent. In the latter case, see https://stackoverflow.com/questions/5747013/how-to-factor-rsa-modulus-given-the-public-and-private-exponent, in the former see Why is it important that phi(n) is kept a secret, in RSA? to find out how to get $p$ and $q$.