## Badly Chosen Semiprimes

I am interested in working through some of the math of encryption, not because I want to be a secret agent or terrorist (I don’t have the stress tolerance for that), but because encryption underlies so much of our modern world.

I am starting with the concept that a public key is a semiprime number used to encrypt a signal, which can only then be decrypted using a privately held number that is a factor of the key. Obviously people would like to be able to work out private data to snoop, so the semiprime must be chosen to be a number that would take intractably long to factorise.

… if your only factorisation method is a brute force trial division algorithm then this is a slow algorithm for huge numbers of 100+ digits, so runtimes might be longer than you could wait. But of course with numbers there are always “clever” ways to obtain shortcuts. The rational sieve algorithm for factorisation is faster than just starting at 2 and trying to divide every number incrementing by 1. But keys wouldn’t be safe if that could bust them, so the numbers get bigger. They have to be so that no matter how clever the shortcuts, its still feasibly uncrackable.

This post is just an example of how a very large semiprime can still be factorised in reasonable time, using brainpower not big iron.

it starts with the idea of looking at a candidate number in a range of bases.

#!/usr/bin/python ## display a number in a base b to facilitate ## factorisation by expressing it as a ## polynomial with x = b and factorising ## numbers with a preponderance of zeros ## can be expressed as relatively simple ## polynomials, this is a way to beat ## badly chosen semiprimes in encryption ## because factorisation is then easy ## for familiarity we choose 2 <= b <=19 symbols = {0:'0', 1:'1', 2:'2', 3:'3', 4:'4', 5:'5', 6:'6', 7:'7', 8:'8', 9:'9', 10:'a', 11:'b', 12:'c', 13:'d', 14:'e', 15:'f', 16:'g', 17:'h', 18:'i'} def converter(x, base): a='' while x != 0: d = x % base a += symbols[d] x -= d x /= base return a[::-1] def test(x): for i in range(2,19): print "in base",i,"x is:",converter(x,i) print test(1827327646467) ## output ## in base 2 x is: 11010100101110101001101110001101100000011 ## in base 3 x is: 20110200122121100102222000 ## in base 4 x is: 122211311031301230003 ## in base 5 x is: 214414331334141332 ## in base 6 x is: 3515243541115043 ## in base 7 x is: 246006611500521 ## in base 8 x is: 32456515615403 ## in base 9 x is: 6420577312860 ## in base 10 x is: 1827327646467 ## in base 11 x is: 644a688aa984 ## in base 12 x is: 2561943b8a83 ## in base 13 x is: 103415a8350b ## in base 14 x is: 6462bd3d311 ## in base 15 x is: 327edc5db7c ## in base 16 x is: 1a975371b03 ## in base 17 x is: f6g3c103cf ## in base 18 x is: 93edb13d79

We can see that this number (which I chose just by hammering my numpad), is not a semiprime because in base 9 there is a terminal zero indicating at least 2 factors of 3 are present, in fact x here is divisible by 27, witness 3 trailing zeros for the base 3 representation.

shall we use a bad semiprime, then?

Here’s one I dug out:

1096701479680195021251744487000468921805220978805730849634339463534602327090904022918187355326875401517926536574395826252476131

shown in base 10 it looks inocuous, but lets try our code

in base 2 x is: 11001111011000000111011101001110011010000110111000110100111000010110101101111000011000110111111110100000110010000011011101010011011111110110101011010110111000100000011101110000000111001011011111100000010010100100010001000110010011111101110000100011011010011010000000100010100101101101000100110000001110000110100110101010011010011100100110110011110110101101101011000100110101110000011100111111101010111101110111011100011 in base 3 x is: 1012110121101011201221102001221000211010111012000120122111100102020110101121022012110010202202110210221120012000011010221202022111211122211022102102221202001101212111200100222210111000211011100101101222200202022010000001000212202220110111021120001021202110212001022 in base 4 x is: 121323000323221303100313012213002311233003012333310012100123222123332311122313010003232000321123330002110202020302133232010123103100010110231220212001300310311103103210312132311231120212232003213331113232323203 in base 5 x is: 1320020342423022423124221111332424444244322014400203241323244442442331130134003414131412420242430210302003003310030020010040303200430020143023310042330401001110013202204131113214011 in base 6 x is: 542025400001054440431132035000113345040141342530114040153413251100031331052321031311235355024302103112325020533012415523532134223002502353153043323103501135000055 in base 7 x is: 121444315600263451613656501030042641011064502411503426656353046205561413122412566461421020061601225025251246602106424265014142542122135363451634100411 in base 8 x is: 31730073516320670647026557030677640620335233766532670403560071337402244210623756043323200424555046016064652323446636655530465603477527567343 in base 9 x is: 1173541151842057024114160518440366411538173122673727505004127668454584272387661355450328714024140341880668100030782813437501252425038 in base 10 x is: 1096701479680195021251744487000468921805220978805730849634339463534602327090904022918187355326875401517926536574395826252476131 in base 11 x is: 10914070285a9a41a6516939818a4276519671679286a84782758a8248675a3441952714255702928853825506733735599451094653732400aa292028 in base 12 x is: 71b49417399442633bb67847a6673120674a7b16213bb8036a6b9281575411156a37278ab1b252615168b32891741a94116bbb350b0222296902b in base 13 x is: 15ca826901c350b7544b1783a002210490929444b41c8894789814b9b6c712c4883c87397380b21bb431a24425b1a2c88364a54245c5974808 in base 14 x is: cd35805a730429a398db91bd27d255305b579d002557a254969cbba70209654dbaa5599a79578c61a5126c48bcc61247dd81ac05a762b1 in base 15 x is: 18a361c9da70e4ae21ce0405dae8388ab3a7545b21ccee487aab8c63e25717ab3a2532e43a4dad1992721c7164716066e61c22d748db in base 16 x is: 67b03ba734371a70b5bc31bfd0641ba9bfb56b7103b80e5bf025222327ee11b4d0114b68981c34d534e4d9ed6d626b839fd5eeee3 in base 17 x is: 3730000000000000000000000000000000000000000000000096f00000000000000000000000000000000000000000000000143 in base 18 x is: 34b5ccc29da8da0045ad2937a7gf933g29e9edb3c24f1gd95c8153g219h3b7821c62bfcbe6fd62eca4hde55g2fa3hfbce401h

So here’s a discovery!

3730000000000000000000000000000000000000000000000096f00000000000000000000000000000000000000000000000143

shown in base 17, is in fact :

in decimal representation…which factors to:

and

so if you are running your revolutionary cell email address using this semiprime as your key then beware!!

see also: https://en.wikipedia.org/wiki/RSA_Factoring_Challenge

## Leave a Reply