multiPrimeRSA
多个素数组成的n¶
# multi prime RSA
e = 65537
c = 48761539940486768790697951968441053167086423529120379009399989923982917278530780108524481919294548305561552133247376067350664771674488982501980538923179804440135482761541868213581098181220801732284669971107195377327445661261746882474615837238429855596647745621191046720648860759474615170945636435027382702345930153884587334870109990234396501579
n = 81736943705459767985288486167314099164146317197040392194768161097750074479540025761100109449092862009195976097250151609584294118669228141027624354052423638509988705830737675936098155468596924772948252465412194715615408850250410310761063399013426728554729053139453019049285162533445627620506060381552244023004446417793032764776342793336374803699
# primes are factored from n
primes = [13791271931, 14045354431, 9135653437, 13351818269, 12139150253, 16755272693, 12624207653, 17085139931, 10173449261, 14433479449, 9864787187, 16512953389, 11924202263, 15640499503, 11824459483, 16610374789, 10802213987, 14984854631, 13227411217, 16593548737, 13898961539, 8883963797, 16733116537, 12405130123, 13370635781, 10965930293, 11279137189, 9312576787, 15410839123, 14616587107, 15424024453, 9190503997, 15975600409, 12580269851]
## two primes
e=354611102441307572056572181827925899198345350228753730931089393275463916544456626894245415096107834465778409532373187125318554614722599301791528916212839368121066035541008808261534500586023652767712271625785204280964688004680328300124849680477105302519377370092578107827116821391826210972320377614967547827619
primes=[15991846970993213322072626901560749932686325766403404864023341810735319249066370916090640926219079368845510444031400322229147771682961132420481897362843199,28805791771260259486856902729020438686670354441296247148207862836064657849735343618207098163901787287368569768472521344635567334299356760080507454640207003]
n=primes[0]*primes[1]
c=38230991316229399651823567590692301060044620412191737764632384680546256228451518238842965221394711848337832459443844446889468362154188214840736744657885858943810177675871991111466653158257191139605699916347308294995664530280816850482740530602254559123759121106338359220242637775919026933563326069449424391192
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
ts = []
xs = []
ds = []
for i in range(len(primes)):
ds.append(modinv(e, primes[i]-1))
m = primes[0]
for i in range(1, len(primes)):
ts.append(modinv(m, primes[i]))
m = m * primes[i]
for i in range(len(primes)):
xs.append(pow((c%primes[i]), ds[i], primes[i]))
x = xs[0]
m = primes[0]
for i in range(1, len(primes)):
x = x + m * ((xs[i] - x % primes[i]) * (ts[i-1] % primes[i]))
m = m * primes[i]
print hex(x%n)[2:-1].decode("hex")
本页面的全部内容在 CC BY-NC-SA 4.0 协议之条款下提供，附加条款亦可能应用。