Skip to content

Instantly share code, notes, and snippets.

/pctf2014 rsa450

Created April 13, 2014 21:08
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save anonymous/10602398 to your computer and use it in GitHub Desktop.
Save anonymous/10602398 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment