import binascii
from Crypto.PublicKey import RSA
from base64 import b64decode
print "\n"
print "\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
print "\t RSA Hastad Attack "
print "\t JulesDT -- 2016 "
print "\t License GNU/GPL "
print "\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
def chinese_remainder(n, a):
sum = 0
prod = reduce(lambda a, b: a*b, n)
for n_i, a_i in zip(n, a):
p = prod / n_i
sum += a_i * mul_inv(p, n_i) * p
return sum % prod
def mul_inv(a, b):
b0 = b
x0, x1 = 0, 1
if b == 1: return 1
while a > 1:
q = a / b
a, b = b, a%b
x0, x1 = x1 - q * x0, x0
if x1 < 0: x1 += b0
return x1
def find_invpow(x,n):
high = 1
while high ** n < x:
high *= 2
low = high/2
while low < high:
mid = (low + high) // 2
if low < mid and mid**n < x:
low = mid
elif high > mid and mid**n > x:
high = mid
else:
return mid
return mid + 1
def parseC(argv, index, verbose):
import string
file = open(argv[index],'r')
cmd = ' '.join(argv)
fileInput = ''.join(file.readlines()).strip()
if '--decimal' in cmd:
if verbose:
print "##"
print "##",fileInput
print "## Considered as decimal input"
print "##"
return long(fileInput)
elif '--hex' in cmd:
if verbose:
print "##"
print "##",fileInput
print "## Considered as hexadecimal input"
print "##"
return long(fileInput,16)
elif '--b64' in cmd:
if verbose:
print "##"
print "##",fileInput
print "## Considered as base64 input"
print "##"
return long(binascii.hexlify(binascii.a2b_base64(fileInput)),16)
else:
try:
fileInput = long(fileInput)
if verbose:
print "##"
print "##",fileInput
print "## Guessed as decimal input"
print "##"
return long(fileInput)
except ValueError:
if all(c in string.hexdigits for c in fileInput):
if verbose:
print "##"
print "##",fileInput
print "## Guessed as hexadecimal input"
print "##"
return long(fileInput,16)
else:
if verbose:
print "##"
print "##",fileInput
print "## Guessed as base64 input"
print "##"
return long(binascii.hexlify(binascii.a2b_base64(fileInput)),16)
pass
def parseN(argv,index):
file = open(argv[index],'r')
fileInput = ''.join(file.readlines()).strip()
try:
fileInput = long(fileInput)
return fileInput
except ValueError:
from Crypto.PublicKey import RSA
return long(RSA.importKey(fileInput).__getattr__('n'))
pass
if __name__ == '__main__':
e = 7
n1 = 10022036265379037873283606776808482557866459308090111534883940865718177639983512662119342281119416241158033537298567286851709556229498058859877121683228774596682463530354223972067629198444968982788922250713559891865919261816911330848802614913631706032562776893224597357355324255263321117746371249374897281379618765006492730806494403308111072966637211560823960482878492897669436775113233218090173773953205373859777529204336743904524724605913439667291642450283502539056317167865950955271726411160185108661710605305209881749978968104668372320740311039079195405595564405545553067816984977942352952679613295335945453198237
n2 = 5466545789924978392117734846441651025566944649290017587961487324101229594609777422305368037344954585418241587633957551279641772525768764611188988227720597556634650034264505822514430445671371902394845226110100975570935303274836520009041255673258743208173396958290432905543148641745168024380646078191379194650244323448918977124653886707963511968894925605598683697007725355334218510153808020236986866621440493131392397106674236875719949237921916816824901951782815445968997182425608119302657645645838081847911729329333764403590828687896595484627953582720022494684431177689169562431514156723717431880081981556861583018517
n3 = 5216273350923762348996819172932047657740263255248423536832070896504436079290996116053910458202206066607495080005143242081376348478552546332314483414339219088245406077072653291793201707938210052137737032136008691204273974883871392886847900590411035963981133018158012140770585855836554605968542686051767074445169576528595295868833612083435959789899465479063315706805137423972403304919456897675923521668190245644201632092213606749130854730067502251227674778549657054487536558408785381601255488927062660442522496864532745842104460605804514922118066012819002689049981557892095296223518873642160006462186453091627377846719
n4 = 23877677498268410284879275681599753946472064168982107017698987574875291853430610166705520818854679284024035965166084667071782959877626088875201104444061372210767667483286033873186027043018865270765379778972734594727020084433542927434622162385031073045949543728094450158066806302710336945902706311444702067892897382023369572561933840697091647190739941807440726157963736515169755622514090303488227644584510175870987096541366007967982302476854613123392400570876217436169696368690150208874814955767774660004903549034030453797617219708937501949676157124852802614561580437881345741238143591504284958256829966154954860310643
n5 = 14095304106189288640829933284328100925981109805290171926596523882500992828050689610054551419208961617895244032677408948518722739184220513962788253695294440224817835843547289773514113860609727834208120554675150777100035341397359695754443831969620545126239117460426602273999534524462242741389375433175237422632997941648269022097426901783701566115072520388843879171454672942810241915423341751813855234874758865121037886735845464875242609743056346324057991215234482527871877337706502944703023808957350962273199545033462807203671480858363579332623386369851297631986187711675134368500976725781503614885257984375549898158689
n6 = 2805822354201662117320594043711993782804865769293499426012360087817858551003001395302163740603703828195195932459444805174556152674013174027197071452536007720377642902614079800876454139985267840390802982000981391589121247087945323071621814892873054291187100453510563927190923456819020327967812411342557586095287060637718034456241630931342321644065932761169946330107762168341828247523519427454538373734712173180277190763105614286976239296025622448068573996830818370176355468420604889972971911137825122031079799394840034520000378583048365213663261323826755042085539056699658078298352991498848183741926741253336809983081
n7 = 25454009749168470343695633209096091829115329722572151778843118833425745470034996921255287732666381145235781038972818879902175747917173596391714646458631517429967987558853821226063117620100131280109980358660151611745478185529770001530290709260636770225215186800776097876644514962324976911466656250316831758848397129882568596479711529118559633884457580705072157006277242414838614921959845416195868135339484150235079747708585021249992266719965641249640344662274664797188479304252760363884135230450876493335745378727727079727827645384850449255019980920544237025044248135670516643488962958548195014144666470074377908386063
c1 = 7391172673494652807685679927464443742804469716124686497937352685631944739927403334100753118718810827819939551249092644730733640887813475157863909267732710966904033874563749607452101004880603517576015117231543666882714876053816889315304434716583902097326869862769223330226929267650196146699723546298777721549327230579524043853731525842228354074211952590809573512193002908675659981910521560218722078118583409532890190350278993572874200629804040761922640444870232404736174533503458666401049021690701120014711135662159756073554655169987524174160454336199103732766648969310872094773896573037726906071280884398964499625020
c2 = 2843216698827041985234155126413219625102551967694195507616270458944256794024725727982775312996964360225107871298400288303715856835949437523897251998356574507142899492557143968158430397540293189973986706379386430519381858403628687144765951766733259166975201698201001559608435647196300391229794290104430338488390377935687114237067952186727947306540592887865659962691657932063711547531829312199823488118775597548579002212505954186919111624039557627729228692097539779090276034544147566301508294383730646789567286167983001460941761651651550106133788841812817514137482151210600991083197714286954280138543861307503606716687
c3 = 2302840660982990706559514467752282608279989971179438892300937945447548784136021634663470424995563089657378083878340327507907273677046617011731588253183115962507981205380038591937454135692479378461272309601984068994340223460110011927750428790367899740123933101545519333275378177450046677349361228228756023343552737751276656981842493825940592644061106798477517795237715348144352954728534699021231559916391882314536204099649751257130666668855055343556693412599766542087842727824032038771853002304289245363376208213623603995010083510086051017014020583014841158059684157033215101586049552797894220844380611133865673630801
c4 = 21542650580244090952784375188737468745448203348922868429406196302086271073676866277485976451720227641278427496915785578412784529024335740676758107987503859146577358215708248682437455044274509620470752764937668805057881069241160619380098319880566533327878406656365405208233812965208982731078254898819598904848966997244978017829737683687504578693319927257965587343277686790692897770069007188699761774062935389828173866322096724684461746266895396261083359145450376711339892131239899937109104845549497760224715797430549267596702844680269969086579967938513817206661072633561450576990683873838952925270459005180113251070249
c5 = 5841298358718613696062311056221508337701416292725004974138314539876150378702426703549430117040191903647122061403407396288001626124108215908094632322171004807595060730467760110047822011747633210272450557602443585240325321882265082987790788937409746656818781811819115452970840966600299402274664167896074281874767663751931697405940475209595160606989446399735956632932740140774120362773964862067823210273048778380937955790417026758705126758582714675929109140032046187572583702405164513719448544031934183587141634161632757693697249167749952737814924049718225194470053426092226496663009906557955566430066736079650924094775
c6 = 1840296233218477853481534562215626625414182376149520279565477106636326502423629202398872352247072974928247089059258779616805363438919346177179751144150840146502100528681001973857981344372271699254564085124019490542816704779558116713918712764905289545904746631301089653173086838314931849726257101196974182707388814949943497825270433233859953596462571591644141313685767121169211812959266024665387037379326240471760061808331954030889737904363024686917008151847474903564630772753685195974245871917099262116749552267414561620711561171348300446183668428521497810537883987976853838751652062973640912281502768323552961119727
c7 = 789032093589329919433103064912734499692800138044594105985741187192587133548423627123979828515942204884228205644612915396782678903901468096055669312556620684388723470685365523376229767716532460150705694588934426363146781448912873886792079146178749619507171787017137430583992061952004088013585625578578697225347700205144867425958935656640766720643294601810945228322481781587820554087577038637902482084286507222529109418279162740318995563410236088568237694026601631788889001088963413678782229872782538151806577918829849586853938669782376616395525544507480942096894639889844916812413303666411186051339002485237155449662
n = [n1,n2,n3,n4,n5,n6,n7]
a = [c1,c2,c3,c4,c5,c6,c7]
result = (chinese_remainder(n, a))
resultHex = str(hex(find_invpow(result,e)))[2:-1]
print ""
print "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
print "Decoded Hex :\n",resultHex
print "---------------------------"
print "As Ascii :\n",resultHex.decode('hex')
print "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
