Today for a change I will talk about a topic that is completely abstract to me. I got interested in it as a side-effect of a project I was working on and here’s a code that some may find useful. <\/p>\n\n\n\n
Researching RSA crypto internals you will surely come across a lot of information and practical examples talking about calculation of a private key \/ decryption if you can only factor ‘n = p & q’. For example this<\/a> great example.<\/p>\n\n\n\n I was curious how to do it not only for p & q, but also for multi-prime RSA setups, that is – these where ‘n = r[1] x r[2] x … x r[n]’. There is not that much published about it online and the best example I could find was this article<\/a> on StackExchange.<\/p>\n\n\n\n While I don’t read mathematical symbols very well, I decided to implement it in python to learn something new. In order to keep it flexible, the whole code works based on the content of the ‘r’ array (or list really), that specifies all multipliers of ‘n’. The Modular multiplicative inverse function is stolen from this article<\/a> on StackOverflow.<\/p>\n\n\n\n Here’s the code:<\/p>\n\n\n\n Here are the numbers from the StackExchange post:<\/p>\n\n\n\n And here is the output of the script:<\/p>\n\n\n\n And what about the article I mentioned<\/a> earlier?<\/p>\n\n\n\n For which the expected result is:<\/p>\n\n\n\n If I plug it in to the code I pasted above, I will get the following:<\/p>\n\n\n\n And the output is:<\/p>\n\n\n\n Today for a change I will talk about a topic that is completely abstract to me. I got interested in it as a side-effect of a project I was working on and here’s a code that some may find useful. … Continue reading import math\ndef egcd(a, b):\n if a == 0:\n return (b, 0, 1)\n else:\n g, y, x = egcd(b % a, a)\n return (g, x - (b \/\/ a) * y, y)\n\ndef cmi(a, m):\n g, x, y = egcd(a, m)\n if g != 1:\n return None\n else:\n return x % m\n\nr = [931164518537359, 944727352543879, 982273258722607]\ny = 529481440313141057262802385309623737292746309\nlr = len(r)\ne = 5\nN = 1\nd = [None] * lr\nt = [None] * lr\nx = [None] * lr\nfor i in range(lr):\n N = N * r[i]\n d[i] = cmi (e, r[i]-1)\n print (\"r[\", i , \"] = \", r[i])\n print (\"N = \", N)\n\nprint ()\n\nfor i in range(lr):\n print (\"d[\", i , \"] = \", d[i])\n\nprint ()\n\nm=r[0]\nfor i in range(1,lr):\n t[i] = cmi (m, r[i])\n m = m * r[i]\n print (\"t[\", i , \"] = \", t[i])\n\nprint ()\n\nfor i in range(lr):\n x[i] = pow(y, d[i] ,r[i]) % r[i]\n print (\"x[\", i , \"] = \", x[i])\n\nprint ()\n\nX = x[0]\nm = r[0]\nfor i in range(1,lr):\n X = X + m * ( ( (x[i] - (X % r[i]) ) * t[i] ) % r[i] )\n m = m * r[i]\n print (\"x = \", X)<\/pre>\n\n\n\n
e=5\nr1=931164518537359 r2=944727352543879 r3=982273258722607\nN=864102436520313334659779717201860718296307527\nd1=558698711122415 d2=566836411526327 d3=785818606978085\nt2=360227672914825 t3=882117903741868\ny=529481440313141057262802385309623737292746309\nx1=436496882968258 x2=903092574358267 x3=806961802724\nx=710532117316769399313215266414 (when i=2)\nx=111222333444555666777888999000000000000000042<\/pre>\n\n\n\n
r[ 0 ] = 931164518537359\nr[ 1 ] = 944727352543879\nr[ 2 ] = 982273258722607\nN = 864102436520313334659779717201860718296307527\n\nd[ 0 ] = 558698711122415\nd[ 1 ] = 566836411526327\nd[ 2 ] = 785818606978085\n\nt[ 1 ] = 360227672914825\nt[ 2 ] = 882117903741868\n\nx[ 0 ] = 436496882968258\nx[ 1 ] = 903092574358267\nx[ 2 ] = 806961802724\n\nx = 710532117316769399313215266414\nx = 111222333444555666777888999000000000000000042<\/pre>\n\n\n\n
e = 113\np = 338924256021210389725168429375903627261\nq = 338924256021210389725168429375903627349\nct = 102692755691755898230412269602025019920938225158332080093559205660414585058354<\/pre>\n\n\n\n
t :535645912235879621902477379288244888293287927881054157873533<\/strong><\/pre>\n\n\n\n
r = [338924256021210389725168429375903627261, 338924256021210389725168429375903627349]\ny = 102692755691755898230412269602025019920938225158332080093559205660414585058354\nlr = len(r)\ne = 113<\/pre>\n\n\n\n
r[ 0 ] = 338924256021210389725168429375903627261\nr[ 1 ] = 338924256021210389725168429375903627349\nN = 114869651319530967114595389434126892905129957446815070167640244711056341561089\nd[ 0 ] = 155965144363742834209812020597760961217\nd[ 1 ] = 329926266923302149289986966649109725737\nt[ 1 ] = 234936132014702656514037206726478650776\nx[ 0 ] = 22808800254162271774126722746602450507\nx[ 1 ] = 22808800254162132696325593613158654299\nx = 535645912235879621902477379288244888293287927881054157873533<\/strong><\/pre>\n","protected":false},"excerpt":{"rendered":"