Factoring Fun

Some time ago I discovered an interesting mathematical property that encompasses all base numbering systems, and which involves the use of modular arithmetic in conjunction with the “ceiling” digit of any base numbering system (the number 9 in base-10 for example). This post will document those findings including a novel attack against (but not limited to) the RSA encryption algorithm.

This is a factoring attack against RSA with an up to 80% reduction in the search candidates required for a conventional brute force key attack, and affects any cryptosystem that uses modular arithmetic including the RSA encryption algorithm, and possibly reduction of entropy attacks against PRNG functions such as those that are used to seed TCP/IP Initial Sequence Numbers (ISNs) and DNS servers for example. Sample Erlang proof of concept factoring code is included at the end of this post, and implements the attack against the prime number multiplication process in RSA so that security enthusiasts and armchair cryptographers alike can experiment with and validate these findings. For lack of a more descriptive term and in keeping with the field of cryptanalysis’ somewhat arcane nomenclature, I am referring to this attack method as a “Reduction Sieve”.

RSA is the most widespread public key encryption algorithm in use today for email security, electronic commerce, online purchasing etc, and is used extensively for both digital signatures and conventional encryption algorithm key exchange processes and protocols. The entire crux of the RSA encryption algorithm is actually quite simple: randomly generate two large prime numbers, multiply them against each other, and then derive public and private key materials from the relatively prime number that results (referred to as a semiprime number).

The RSA encryption algorithm is most commonly expressed as n = pq:

36453233 (n) = 9461 (p) * 3583 (q)

In this example, 9461 (p) and 3583 (q) are both prime numbers generated by the RSA encryption algorithm implementation, and the product 36453233 (n) is used to create the public and private key materials by way of an inverse modulo function. Once the product n has been created and the exponents calculated, the two prime numbers represented as p and q that were used to create n are then discarded from memory in a secure fashion, with the resulting public and private keys referred to as an RSA “keypair”. This public and private keypair combination are mutually inclusive, an encryption ying and yang of sorts: the public key is distributed “publically” across insecure communication mediums, while the private key is kept private to the user or application, and is usually stored in another secure container (a smart card, encrypted in a file on a disk, etc.).

From that point, the only way that a message encrypted with a public key can be decrypted is by decrypting said message with the associated keypair’s private key; in the event of a key signing operation, a message is signed with the user or application’s private key, and the keypair’s public key is used for the digital signature verification process. As is the basis for most, if not all other encryption algorithms, the size of the two initial prime numbers generated by the RSA encryption algorithm are intended to be large enough so that the costs associated with a brute force recovery of the original key materials p and q would be cost prohibitive. A recent example of this would be the factoring of RSA-640, in which the semiprime number RSA-640 (the product n) was factored yielding the original p and q primes used to create the number, and which required more than five months of computational effort on a cluster of 80 2.2 GHz Opteron CPUs. RSA-640 was 193 decimal digits in length, with both p and q weighing in at 97 decimal digits each. It is not uncommon for the keys used in today’s RSA implementations to meet or exceed 2048 bits in length based upon recent advances in computing horsepower and distributed clustering technologies.

Several aspects of the RSA encryption algorithm can be attacked: attacks against the quality of the entropy pool used by the random number generator (RNG) that creates the p and q primes; “side channel” cryptanalysis attacks where key materials are divined from power rails, shared bus architectures, shared memory segments etc; exponential “increase by two” factoring attacks and more esoteric subexponential factoring attacks such as the General Number Field Sieve; and, even the tried and true (and highly effective) Rubber Hose Cryptanalysis method.

This Reduction Sieve method of factoring does not require precomputed lattice sieving or initial polynomial selection inherent to GNFS, and is easily implemented in a clustered computing environment such as MPI or PVM. I chose the functional programming language Erlang for the second proof of concept factoring code based upon Erlang’s massively parallel architecture of concurrency and its ability to spawn and schedule hundreds of thousands of lightweight threads on a single host or across a distributed clustering environment of Erlang nodes if need be. The current proof of concept implementation works and has been tested with up to 30,000 concurrent factoring threads on an OpenSUSE 11.1 Erlang node, but has plenty of room for improvements such as performance optimizations and both logic and structural refinements. I have not yet compared the performance of this Reduction Sieve method to GNFS or any other subexponential factoring methods.

The first step in the Reduction Sieve is a modulo operation with the base numbering system’s ceiling digit; in base-10, using our previous example:

36453233 = 9461 * 3853 is described as 36453233 mod 9 = 2, the operation of which can be used to determine properties about the p and q primes which were used to create n, and which corresponds to the following function and table in reductionsieve.erl:

analyze(N) ->
case (N rem 9) of
0 -> PQ = [{1,9}, {2,9}, {3,3}, {3,6}, {3,9}, {4,9}, {5,9}, {6,6}, {6,9}, {7,9}, {8,9}, {9,9}];
1 -> PQ = [{1,1}, {2,5}, {4,7}, {8,8}];
2 -> PQ = [{1,2}, {4,5}, {7,8}];
3 -> PQ = [{1,3}, {2,6}, {3,4}, {3,7}, {5,6}, {6,8}];
4 -> PQ = [{1,4}, {2,2}, {5,8}, {7,7}];
5 -> PQ = [{1,5}, {2,7}, {4,8}];
6 -> PQ = [{1,6}, {2,3}, {3,5}, {3,8}, {4,6}, {6,7}];
7 -> PQ = [{1,7}, {2,8}, {4,4}, {5,5}];
8 -> PQ = [{1,8}, {2,4}, {5,7}]
end.

Using this table, we see that the product n can only be made of certain combinations of numbers in p and q;  if n has a mod 9 result of 2, then (p mod 9 = 1 * q mod 9 = 2) OR (p mod 9 = 4 * q mod 9 = 5) OR (p mod 9 = 7 * q mod 9 = 8).  In essence, using a simple mod 9 function on n we can determine properties about the p and q that were used to create n, thus reducing the possible candidates we will search through during a factoring attack.  Another interesting property of base numbering systems is that conversion from one base to another will yield the p opposite q, for example converting 36453233 (n) to base 9461 (p) will yield a result of 3853 (q) and vice versa.  The process required for base conversion is still exponential so that won’t buy us much more speed than what would be associated with trial division, but it’s an interesting property nonetheless, and as they say attacks only get better over time never worse.

reductionsieve.erl includes two Pollard RHO factoring hybrids, which have been modified to create an RNG that always results in a p and q that will have a mod 9 result according to the table above (RNG * 9 + desiredmod, or RNG * 9 + 2 in other words).  Erlang’s built in RNG is not very high quality but high performance; right now both RHO variants first seed the internal Erlang RNG with the OpenSSL crypto entropy pool, then use the Erlang RNG to generate p and q combinations that match the output of reductionsieve:analyze().  The first RHO variant uses a traditional division operator with only a single RNG; the second RHO hybrid uses two RNGs that result in a candidate created from the lookup table.  I haven’t yet performed any timing analysis to see which one is more efficient, and Erlang is a very complex functional language to get accustomed to.  There is a RHO factoring method floating around out there that supposedly can be used to factor Elliptical Curve Cryptography, but I haven’t had time to study it in any detail yet.

To use the reductionsieve.erl factoring code, you have to have Erlang R13B installed first.  Here is a walkthrough of the basic  functions included:

$ erl
Erlang R13B (erts-5.7.1) [source] [smp:2:2] [rq:2] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.7.1  (abort with ^G)
1> c(”reductionsieve.erl”).
./reductionsieve.erl:112: Warning: variable ‘PQ’ is unused
./reductionsieve.erl:113: Warning: variable ‘PQ’ is unused
./reductionsieve.erl:114: Warning: variable ‘PQ’ is unused
./reductionsieve.erl:115: Warning: variable ‘PQ’ is unused
./reductionsieve.erl:116: Warning: variable ‘PQ’ is unused
./reductionsieve.erl:117: Warning: variable ‘PQ’ is unused
./reductionsieve.erl:118: Warning: variable ‘PQ’ is unused
./reductionsieve.erl:119: Warning: variable ‘PQ’ is unused
./reductionsieve.erl:120: Warning: variable ‘PQ’ is unused
{ok,reductionsieve}
2> c(”lin.erl”).
./lin.erl:38: Warning: variable ‘Y’ is unused
./lin.erl:57: Warning: variable ‘Other’ is unused
./lin.erl:61: Warning: variable ‘A’ is unused
./lin.erl:62: Warning: variable ‘A’ is unused
./lin.erl:63: Warning: variable ‘A’ is unused
{ok,lin}
3> reductionsieve:make_prime(4).
Generating a 4 digit prime ……
9461
4> reductionsieve:make_prime(4).
Generating a 4 digit prime ..
3853
5> N = 9461 * 3853.
36453233
6> reductionsieve:analyze(N).
[{1,2},{4,5},{7,8}]
7> reductionsieve:buildworld1(N, 20000).
N was 36453233 mod 9 = 2
Result was 9461 mod 9 = 2
PQ offsets were {1,2}
PTry was 78724981 mod 9 = 1
N was 36453233 mod 9 = 2
Result was 3853 mod 9 = 1
PQ offsets were {7,8}
PTry was 138496085 mod 9 = 8
N was 36453233 mod 9 = 2
Result was 3853 mod 9 = 1
PQ offsets were {7,8}
PTry was 134712439 mod 9 = 7
N was 36453233 mod 9 = 2
Result was 3853 mod 9 = 1
PQ offsets were {1,2}
PTry was 103341313 mod 9 = 1
N was 36453233 mod 9 = 2
Result was 3853 mod 9 = 1
PQ offsets were {1,2}
PTry was 134828029 mod 9 = 1

The first two options compile both modules into the runtime interpreter; make_prime(4) generates a four digit prime number; we assign the product of two primes to N; reductionsieve:analyze(N) then shows us the possible pairs of p and q that can exist; reductionsieve:buildworld1(N, 20000) then creates 20,000 factoring threads each with a separate RNG seed using the first RHO variant.  reductionsieve:buildworld2(N, 20000) would alternately create 20,000 factoring threads with the second RHO variant, using two RNGs and a Greatest Common Denominator function to find the p and q candidates.  If you want to load up n from a text file, use reductionsieve:readfile(”rsa-140-n.txt”).

Download reductionsieve.erl and lin.erl.

Gregory Perry (Gregory.Perry [at] LiveAmmo.com)