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?
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:

&gt;&gt;&gt; n = 0xffffffa95256a837568a41c265f4fe27110814aae19f144762d5cc0bcb931807
&gt;&gt;&gt; e = 0x11
&gt;&gt;&gt; d = 0xc3c3c3817b3335577e69b9d0e48e2bc1fdf71f1f4f73a38a7d628d39739bbaf1
&gt;&gt;&gt; from fractions import gcd
&gt;&gt;&gt; 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$.