pctf2014 rsa450

get modulus with
openssl rsa -noout -modulus -pubin -in public.pub

======== maskpriv.py ======
#!/usr/bin/env python

import re
import sys
import gmpy
from math import floor, ceil
from Crypto.PublicKey import RSA
from binascii import hexlify, unhexlify

import fileinput

def nhex(n):
    t = str(hex(n))[2:-1]
    # make sure we're an even number of nybbles, goddamnit
    if len(t) % 2:
        t = '0' + t
    return t

def nhex2(n):
    t = str(hex(n))[2:]
    # make sure we're an even number of nybbles, goddamnit
    if len(t) % 2:
        t = '0' + t
    return t

def hexn(x):
    return gmpy.mpz(x, 16)

partials = []
accum = ''
for line in fileinput.input():
    m = re.match('^    (.+)', line)
    if m:
        cleaned = m.group(1).replace(' ', '_').replace(':', '')
        accum += cleaned
    elif len(accum) > 0:
        partials.append(accum)
        accum = ''

b =  1024
N =  partials[0]
e =  65537
p =  partials[2]
q =  partials[3]
d =  partials[1]
dp = partials[4]
dq = partials[5]

print b
print hexn(N)
print e
for part in [p, q, d, dp, dq]:
    print hexn(part.replace('_', '0'))
    print hexn(re.sub('[0-9a-f]', 'f', part).replace('_', '0'))


=========== fixed.pem =========
Private key: (1024 bit)
modulus:
    00:db:fa:bd:b1:49:5d:32:76:e7:62:6b:84:79:6e:
    9f:c2:0f:a1:3c:17:44:f1:0c:8c:3f:3e:3c:2c:60:
    40:c2:e7:f3:13:df:a3:d1:fe:10:d1:ae:57:7c:fe:
    ab:74:52:aa:53:10:2e:ef:7b:e0:09:9c:02:25:60:
    e5:7a:5c:30:d5:09:40:64:2d:1b:09:7d:d2:10:9a:
    e0:2f:2d:cf:f8:19:8c:d5:a3:95:fc:ac:42:66:10:
    78:48:b9:dd:63:c3:87:d2:53:8e:50:41:53:43:04:
    20:33:ea:09:c0:84:15:5e:65:2b:0f:06:23:40:d5:
    d4:71:7a:40:2a:9d:80:6a:6b
publicExponent: 65537 (0x10001)
privateExponent:
     f:  :  : a: a:9 :e :  : 1: 2:  :  :e :  :1 :
    3 : 1:  :  :  : a:  :2 :  :  :  :  :  :  :  :
    9 : a:  :  :  :  :  : 5:c1: 0:b : 3: 2:0 :b0:
      :c : f:  :f :  :d2:  :  : d:  :1 :  :3 :  :
      :  :  :0 : 3:  :  : 5:c :  :3 :6 :  :a4:  :
    4 :  :  :8f:  :  :  :  : a:  : c:5f: 7: 6:  :
     1:  : b:  : 5:  :84:0 :b : f: 3:  :  : 4: 6:
      :  : 5:1 :  :d :  : f:  : c:  :  : 5:  :  :
      :e :f4:b :4 :8e:  :  
prime1:
      :6 : 1:1 :  :b :0 : 2:c : b:2 :  : a:1 :
    c :  : 0:  :28:0 :  :cd:  : 8:  :  :20: c:  :
      : 5:  :9 : c:3 :  :  : a:b :c :3 :  :  :  :
     f:  :  : f: 1: 1:b :  : c:f : a:  :a :  :  :
     a:38:  :6 :  
prime2:
    e :  :d :2 :6 : 7:  :33:  :46:  : 4:  :  :
      :5 :  : 4:6 :  : 6:  : e:d :  :  : 9: e:1 :
      :  :  :  :  :0 :  :  :  :c : 5:  :  :a :0 :
    6 :  :  :8 :e9:f : f:7 :5 : e:1 :  :  : 1:9 :
     4:d :e9: 6:  
exponent1:
     9:d : 5:  :c :67:  : 9:  :  :  : d:  :  : 3:
     f:6 : 0:c :  :6 :ad:  :2 :d :d :  :  :0 :7 :
      :5 : 6:  : 5:1 :f : d:  : 2:  :  : 2: 3:  :
    9 :  :  :  :  :67: 3:  :4 : 7:c0: 4:b :c :f :
      :3 :b : 1
exponent2:
    1 : 9:47:8 :  :  :  : 3:  :  :  :6 :  :  :0 :
    e :e :8 :  :  :  :  : 1:c :74:  :  :d : 9:3 :
    5 : e:  : 2:  :7 : 2:c :  :  :  :  :5 :  : 8:
      :  :c :  : 1:  :a :  : 9: 5:  : 3:  : e:c :
      :  : 6:  
coefficient:
      :a :d :84:f :  : c:43:  :  :  : 6:  :  :  :
      : b:  :c :9 :  :  :  :  :  : 4:23:8b:  :6 :
    2 : 2:  :  : 7:5b:  :  :  :7 :  :  :  :  :  :
    f1:7 :1 :  :f : a:  : 5:  :  :  : 5:  : c: 1:
      :48: b: 6:  

from http://cseweb.ucsd.edu/~hovav/papers/hs09.html
=========== rsa.C.diff ===========
--- rsa.C.orig	2014-04-12 14:51:26.528340000 -0700
+++ rsa.C	2014-04-12 20:27:10.834026000 -0700
@@ -129,6 +129,38 @@
 };
 
 void
+read_degraded_rsa_key(char *filename,
+             rsa_pub &pub, rsa_priv &priv, rsa_mask &mask, int &bits)
+{
+  ifstream file(filename);
+  if (!file)
+    {
+      cerr << "Error: can't open output file " << filename << endl;
+      exit(1);
+    }
+
+  clear(mask.p);
+  clear(mask.q);
+  clear(mask.d);
+  clear(mask.dp1);
+  clear(mask.dq1);
+
+  file >> bits;
+  file >> pub.N;
+  file >> pub.e;
+  file >> priv.p;
+  file >> mask.p;
+  file >> priv.q;
+  file >> mask.q;
+  file >> priv.d;
+  file >> mask.d;
+  file >> priv.dp1;
+  file >> mask.dp1;
+  file >> priv.dq1;
+  file >> mask.dq1;
+}
+  
+void
 read_rsa_key(char *filename,
              rsa_pub &pub, rsa_priv &priv, int &bits)
 {
@@ -369,8 +401,9 @@
 
 #define NUM_POSS 32
 
-static int MODULUS_BITS = 2048;
+static int MODULUS_BITS = 1024;
 static int VERBOSE = 0;
+static int MASKED = 0;
 static int TIMING = 0;
 static int PANICWIDTH = -1;
 static ZZ E;
@@ -589,7 +622,7 @@
   char *filename = NULL;
 
   int c;
-  while((c = getopt(argc, argv, "e:n:f:svtw:i:h")) != EOF)
+  while((c = getopt(argc, argv, "e:n:f:smvtw:i:h")) != EOF)
     switch (c)
       {
       case 'e':
@@ -604,6 +637,9 @@
       case 's':
         do_seed = 0;
         break;
+      case 'm':
+        MASKED = 1;
+        break;
       case 'v':
         VERBOSE = 1;
         break;
@@ -624,12 +660,29 @@
   if (do_seed)
     seed();
 
-  if (filename)
-    read_rsa_key(filename, pub, key, MODULUS_BITS);
-  else
+  if (filename) {
+    if (MASKED) {
+      read_degraded_rsa_key(filename, pub, key, mask, MODULUS_BITS);
+    } else {
+      read_rsa_key(filename, pub, key, MODULUS_BITS);
+      degrade_rsa_key(mask, key, delta);
+    }
+  } else {
     make_rsa_key(pub, key, MODULUS_BITS, E);
-  degrade_rsa_key(mask, key, delta);
-
+    degrade_rsa_key(mask, key, delta);
+  }
+  if (VERBOSE) {
+    cerr << "Loaded p data:   " << key.p    << endl;
+    cerr << "Loaded p mask:   " << mask.p   << endl;
+    cerr << "Loaded q data:   " << key.q    << endl;
+    cerr << "Loaded q mask:   " << mask.q   << endl;
+    cerr << "Loaded d data:   " << key.d    << endl;
+    cerr << "Loaded d mask:   " << mask.d   << endl;
+    cerr << "Loaded dp1 data: " << key.dp1  << endl;
+    cerr << "Loaded dp1 mask: " << mask.dp1 << endl;
+    cerr << "Loaded dq1 data: " << key.dq1  << endl;
+    cerr << "Loaded dq1 mask: " << mask.dq1 << endl;
+  }
 
   double start_time = 0.0, mid_time = 0.0, stop_time = 0.0;
 
@@ -825,12 +878,21 @@
   if (TIMING)
     stop_time = timenow();
 
+  ZZ cand_n;
   int found = 0;
   while (!Q_gh.empty())
     {
       item &soln = Q_gh.front();
-      if (soln.key.p == key.p)
+      mul(cand_n, soln.key.p, soln.key.q);
+      if (cand_n == pub.N || soln.key.p == key.p)
         {
+          cout << "N   " << cand_n        << endl;
+          cout << "e   " << pub.e         << endl;
+          cout << "p   " << soln.key.p    << endl;
+          cout << "q   " << soln.key.q    << endl;
+          cout << "d   " << soln.key.d    << endl;
+          cout << "dp1 " << soln.key.dp1  << endl;
+          cout << "dq1 " << soln.key.dq1  << endl;
           found = 1;
           break;
         }
@@ -840,8 +902,16 @@
   while (!Q_hg.empty())
     {
       item &soln = Q_hg.front();
-      if (soln.key.p == key.p)
+      mul(cand_n, soln.key.p, soln.key.q);
+      if (cand_n == pub.N || soln.key.p == key.p)
         {
+          cout << "N   " << cand_n        << endl;
+          cout << "e   " << pub.e         << endl;
+          cout << "p   " << soln.key.p    << endl;
+          cout << "q   " << soln.key.q    << endl;
+          cout << "d   " << soln.key.d    << endl;
+          cout << "dp1 " << soln.key.dp1  << endl;
+          cout << "dq1 " << soln.key.dq1  << endl;
           found = 1;
           break;
         }


====================================

$ ./maskpriv.py fixed.pem > tmp; ./rsa -n 1024 -m -i tmp
N   154474827976763920165328949257571486434054251040123235562919548556971732070036122886862766211654838938928846787154262963082378690764949775798531506812312124840119183803533318584572089721609968673990239446902280820375462104365472096034361037571656667701094669603984656457986138035424322928756694319644654201451
e   65537
p   12643740637395110652894262209502063899047520218436247735878188180335985789877601396069401620713231058940443043891453952791936466967524033214476598572706213
q   12217494205780318874865198006759446969679921137474855298485716817925925911890415286181103665676748660959871257808447814451048738105000263500773868071134927
d   16130416271811423626134361840539083443901333206277546416386030222120577777829837705182414752102327199027103474794089381451205281781309182766246155000873801
dp1 3028926072403424588407158043382858586982102742411906090502884697671162502114505423169959037569582489667896848941755452016927880912921362306289311344606673
dq1 961001916944589221354808668764895389302226123619983811643710731287793888578895750496110432222464246871967534888727718441417157406217500928429578557253163

key can be built in python like so

from Crypto.PublicKey import RSA
rsa = RSA.construct((long(n), long(.e), long(d), long(p), long(q)))
print rsa.exportKey()