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.

About these ads

Pages: 1 2

8 Responses to “Factoring Multiple RSA Keys”

  1. Johann Hibschman said

    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:

    k=: 708894553 704488409 705674273 707478271 710167019 708093251 702013379 704030867 708691187 708374743 712748719 713581951 704387447 707015741 704308279 710872423 707947453 704996429 706323757 705031051 714623803x
    
    NB. Method 1: gcd with themselves
    diag=: (<0 1)&|:           NB. select the diagonal
    IR=: @(i.@$@])             NB. indices of ravel
    gtOne=: #~ >&1             NB. select items greater than one
    ktab=: 1 diag IR} +./~k    NB. gcd table, replace diagonal with 1
    kfacts=: gtOne&.:>"1 ktab  NB. factors found
    
    NB. Method 2: product of keys
    kgcd=: k+.((*:k)|*/k)%k    NB. gcds
    kfacts2=: gtOne&.> kgcd    NB. factors found
    
  2. Diego Sanchez said

    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

  3. 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)

  4. programmingpraxis said

    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.

  5. 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";
    }
    ?>
    
  6. output:

    12401
    12421
    12451
    12457
    12379
    12457
    12451
    12377
    12421
    12379
    12401
    12377
    

    right?

  7. [...] 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 [...]

  8. Sam Kennedy said

    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;
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 574 other followers

%d bloggers like this: