Factoring Multiple RSA Keys
March 20, 2012
We gave a list of keys in the exercise, but if you want to create your own list of keys, here’s a method to do so; we choose p from a list of primes, then for each q in a second list of similar-sized primes pair the q with a randomly-chosen p and output the product p · q:
(define keys
(let ((ps (primes 12345 12543)))
(list-of (* (fortune ps) q)
(q in (primes 56789 56987)))))
Note that some p are unused, some are used only once, and some are used multiple times; it is the ones that are used multiple times that we will be able to discover. We used list comprehensions and the fortune function from the Standard Prelude and a segmented Sieve of Eratosthenes from a previous exercise. Your set of keys will differ from ours if your random-number generator is seeded differently.
The quadratic method uses a list comprehension to form the cross-product of all pairs of keys, then computes the gcd and reports those that are greater than 1. We use unique and sort from the Standard Prelude to make the list pretty, but that may not be necessary, depending on your objective:
> (unique equal?
(sort (lambda (a b) (< (car a) (car b)))
(list-of (list k1 d (/ k1 d))
(k1 in keys)
(k2 in keys)
(d is (gcd k1 k2))
(< 1 d k1))))
((704030867 12379 56873) (704387447 12377 56911)
(704488409 12401 56809) (704996429 12379 56951)
(705031051 12377 56963) (705674273 12421 56813)
(706323757 12401 56957) (707015741 12421 56921)
(707478271 12451 56821) (708093251 12457 56843)
(708374743 12451 56893) (708691187 12457 56891))
The linear method first computes the product of the keys, then uses a list comprehension to manage the computation:
> (unique equal?
(sort (lambda (a b) (< (car a) (car b)))
(let ((k-prod (apply * keys)))
(list-of (list k d (/ k d))
(k in keys)
(x is (/ (modulo k-prod (* k k)) k))
(integer? x)
(d is (gcd k x))
(< 1 d k))))))
((704030867 12379 56873) (704387447 12377 56911)
(704488409 12401 56809) (704996429 12379 56951)
(705031051 12377 56963) (705674273 12421 56813)
(706323757 12401 56957) (707015741 12421 56921)
(707478271 12451 56821) (708093251 12457 56843)
(708374743 12451 56893) (708691187 12457 56891))
You can run the program at http://programmingpraxis.codepad.org/5Frj9HCf.
Programming Praxis 
I’m glad to see you reference Nadia’s work. I know she was worried when the first NY Times article came out that her work would be lost in the shuffle.
Continuing my exercises in J, here’s what i have:
I’m sorry but I couldn’t get the idea of the second algorithm. All gathered public key are: Pi(p,qi)=p*qi where 1 <= i <= 21.
Then we follow next steps:
1. Compute kij=Pi*Pj where i,j is between [1,21].
2. gcd with the next arguments:
a. Pi where 1 is between [1,21]
b. kprod = kij. What means (mod k 2)
Second question, why it solves the problem? Why its outcome gives us p and q?
Thanks for your time.
Best regards
Diego
My Python solution:
import itertools
keys = ”’
708894553 704488409 705674273
707478271 710167019 708093251
702013379 704030867 708691187
708374743 712748719 713581951
704387447 707015741 704308279
710872423 707947453 704996429
706323757 705031051 714623803
”’
keys = [int(i) for i in keys.strip().split()]
# uses algorithm from paxis problem: three binary algorithms
def gcd(a, b):
if a == 0: return b
if b == 0: return a
if a % 2 == 0 and b % 2 == 0:
return gcd(a >> 1, b >> 1) <> 1, b)
if b % 2 == 0: return gcd(a, b >> 1)
if a > b: return gcd(a-b, b)
else: return gcd(a, b-a)
def algo1(keys):
result = set()
for x,y in itertools.combinations(keys, 2):
g = gcd(x,y)
if g > 1:
result.add(g)
return list(result)
def algo2(keys):
prod = reduce(lambda x,y: x*y, keys)
result = set()
for key in keys:
g = gcd(key, (prod % key**2)/key)
if g > 1:
result.add(g)
return [int(x) for x in result]
print algo1(keys)
print algo2(keys)
Johann: If you know Nadia, please point out this blog entry to her.
Diego: You’re making it too complicated. Let’s say the keys are K_1 through K_21. Multiply them together to produce K_prod. Then for each K_i, reduce K_prod modulo K_i squared, divide by K_i, and take the gcd with K_i; if the gcd is greater than 1, you’ve found a factor.
PHP CLI :
<? $keys=array(gmp_init(708894553),gmp_init(704488409),gmp_init(705674273),gmp_init(707478271),gmp_init(710167019),gmp_init(708093251),gmp_init(702013379),gmp_init(704030867),gmp_init(708691187),gmp_init(708374743),gmp_init(712748719),gmp_init(713581951),gmp_init(704387447),gmp_init(707015741),gmp_init(704308279),gmp_init(710872423),gmp_init(707947453),gmp_init(704996429),gmp_init(706323757),gmp_init(705031051),gmp_init(714623803)); $prod=gmp_init(1); foreach($keys as $k) $prod=gmp_mul($prod,$k); foreach ($keys as $k) { $val=gmp_strval(gmp_gcd($k,gmp_div(gmp_mod($prod,gmp_pow($k,2)),$k))); if($val!=1) print $val."\n"; } ?>output:
right?
[…] public keys are insecure. A couple days ago I noticed that the excellent Programming Praxis has a challenge based on that research and subsequent reporting in the press. This is excellent because it exposes […]
I managed to do it eventually, this has to be one of the most interesting exercises I’ve completed on here, along with the spigot algorithm for pi and the Mark V. Shaney exercise.
#include <iostream> #include <mpir.h> #include <vector> #include <boost/random/mersenne_twister.hpp> #include <boost/random/uniform_int_distribution.hpp> #include <time.h> #include <Windows.h> using namespace std; vector<long long> list_of_primes; boost::random::mt19937 gen; int sieve(){ vector<int> consecutive; int p = 0; int i; cout << "Initialising...\n"; consecutive.push_back(0); consecutive.push_back(0); consecutive.push_back(2); for(i = 3; i <= 50000; i+=2) { consecutive.push_back(i); consecutive.push_back(0); } while(p <= 50000) { if(consecutive[p] != 0) { p = consecutive[p]; for(i = p; i <= 50000; i+=p) { if(i > p && consecutive[i] != 0) { consecutive[i] = 0; } } } p++; } for(i = 0; i <= 50000; i++) { if(consecutive[i] != 0) { list_of_primes.push_back(consecutive[i]); } } consecutive.erase(consecutive.begin(), consecutive.end()); return 0; } int main(){ sieve(); gen.seed(static_cast<unsigned int>(time(0))); vector<long long> values_for_p; vector<long long> values_for_q; vector<unsigned long long> values_for_n; vector<unsigned long long> values_for_d; vector<long long> evalues; mpz_t n; mpz_init(n); mpz_t p; mpz_init(p); mpz_t q; mpz_init(q); mpz_t t; mpz_init(t); mpz_t e; mpz_init(e); mpz_t d; mpz_init(d); mpz_t buf; mpz_init(buf); mpz_t buf2; mpz_init(buf2); mpz_t pmo; mpz_init(pmo); mpz_t qmo; mpz_init(qmo); mpz_t n1; mpz_init(n1); mpz_t n2; mpz_init(n2); int x; int i; int outercounter; int single_q; for(x = 1; x <= 6; x++){ boost::random::uniform_int_distribution<> dist(1, 4); boost::random::uniform_int_distribution<> dist2(0, 5000); int loops = dist(gen); int single_p = list_of_primes[dist2(gen)]; for(i = 1; i <= loops; i++){ values_for_p.push_back(single_p); } } for(outercounter = 0; outercounter < values_for_p.size(); outercounter++){ boost::random::uniform_int_distribution<> dist(1, 4); boost::random::uniform_int_distribution<> dist2(0, 5000); Sleep(1000); mpz_set_ui(p, values_for_p[outercounter]); single_q = dist2(gen); single_q = list_of_primes[single_q]; values_for_q.push_back(single_q); mpz_set_ui(q, single_q); mpz_mul(n, p, q); values_for_n.push_back(mpz_get_ui(n)); mpz_sub_ui(pmo, p, 1); mpz_sub_ui(qmo, q, 1); mpz_mul(t, pmo, qmo); for(i = 0; i < list_of_primes.size(); i++){ mpz_set_ui(buf, list_of_primes[i]); mpz_gcd(buf, t, buf); if(mpz_cmp_ui(buf, 1) == 0 && mpz_cmp_ui(t, list_of_primes[i]) > 0){ evalues.push_back(list_of_primes[i]); } } gen.seed(static_cast<unsigned int>(time(0))); boost::random::uniform_int_distribution<> dist3(0, (evalues.size() - 1)); mpz_set_ui(e, evalues[dist3(gen)]); mpz_invert(d, e, t); values_for_d.push_back(mpz_get_ui(d)); mpz_out_str(stdout, 10, n); cout << endl; evalues.erase(evalues.begin(), evalues.end()); } int frontpointer; int backpointer; for(frontpointer = 0; frontpointer < values_for_n.size() - 1; frontpointer++){ for(backpointer = frontpointer + 1; backpointer < values_for_n.size(); backpointer++){ mpz_set_ui(n1, values_for_n[frontpointer]); mpz_set_ui(n2, values_for_n[backpointer]); mpz_gcd(buf, n1, n2); int tester = mpz_get_ui(buf); if(tester > 1){ cout << "Found Factors For: " << values_for_n[frontpointer] << " and " << values_for_n[backpointer] << "!" << endl; cout << values_for_n[frontpointer] << ": p = "; mpz_out_str(stdout, 10, buf); mpz_div(buf2, n1, buf); cout << " q = "; mpz_out_str(stdout, 10, buf2); cout << endl; cout << values_for_n[backpointer] << ": p = "; mpz_out_str(stdout, 10, buf); mpz_div(buf, n2, buf); cout << " q = "; mpz_out_str(stdout, 10, buf); cout << endl; } } } system("pause"); cout << "Actual Values: \n"; for(i = 0; i < values_for_p.size(); i++){ cout << "p: " << values_for_p[i] << " q: " << values_for_q[i] << " n: " << values_for_n[i] << endl; } system("pause"); return 0; }