baby-RRSA.py

#(p-1)!+(p-2)!=p*(p-2)  
#(p-1)!=p*(p-1)
#(p-2)! % p=1

import sympy
from Crypto.Util.number import long_to_bytes
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(" error")
    else:
        return x%m
a1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
b1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
a2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
b2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
p=1
q=1
i=1
l=0
for i in range(b1+1,a1-1):
    p *= modinv(i,a1)
    p %=a1
p=sympy.nextprime(p)
print "p="
print p
for i in range(b2+1,a2-1):
    q *=modinv(i,a2)
    q %=a2
q=sympy.nextprime(q)
print "q="
print q
r=n/q/p
print "r="
print r
fn=(p-1)*(q-1)*(r-1)
print "fn="
print fn
e=4097
d=modinv(e,fn)
print "d="
print d
m=pow(c,d,n)
print "m="
print m
print long_to_bytes(m)