8.gcd(n1,n2)
Sometimes,n1 n2 are too big to factor.you can try gcd(n1,n2)
def gcd(a, b):
if a < b:
a, b = b, a
while b != 0:
temp = a % b
a = b
b = temp
return a
def computeD(fn, e):
(x, y, r) = extendedGCD(fn, e)
#y maybe < 0, so convert it
if y < 0:
return fn + y
return y
def extendedGCD(a, b):
#a*xi + b*yi = ri
if b == 0:
return (1, 0, a)
#a*x1 + b*y1 = a
x1 = 1
y1 = 0
#a*x2 + b*y2 = b
x2 = 0
y2 = 1
while b != 0:
q = a / b
#ri = r(i-2) % r(i-1)
r = a % b
a = b
b = r
#xi = x(i-2) - q*x(i-1)
x = x1 - q*x2
x1 = x2
x2 = x
#yi = y(i-2) - q*y(i-1)
y = y1 - q*y2
y1 = y2
y2 = y
return(x1, y1, a)
n1 = 28989197955870674811941817152881961892555962828020048566215146047714999804743571465320756664500939106612607504133407755470924915037883788416084924998195415611009578161228226056524027626453567996030151847302248848345942762209886902216532270655286303624781479379460319335849225128417295447574269158603952744753408534894136230960676590980945838733350143370605144754932401806068003166087495356366335014736018745371974324955357717635855207674309628146381030418983172039685916675081977078212813718313201568394044637347955108623458947913411108888733982376607647705302281273170230540579872437433435253235534772724624778056181
n2 = 29703811006265969568420235185761287243393105045336995893094671661145408859269297497044834735198371987472186770953203812235003929122122129964989222762478116003185582578013431109127657242169359697936471497781547555222392181694624446976869099519331688628488881595076878345856808384797954271081176432330698334469596003760530797898645529616535584139559768170011693043197581376652770244664582733792825511473683193195672487559140733668442863818306947800631472845430628311685792799840854080385208783178691512540436222290062939858472754953657763052720510548438848633979413756332920634307585878271699119574149435107725143578613
c1=14200655400630956617529154837540349350095534430543196299987252783320359338882400858000649938298574946882176873795065987640380185922571487987903069796872680567596754211592988768630729844485795253975027297563832927176988502771266530781452168489731952873297707254669904609865565861351429459102567318447934677565870915603816516557032164955329497823771897899211076176905132170360842951444390670253036307048815943908305457043184642918674003085039564350070641592716116089015861491205237748561298604957423077954850396167621218521884114394431799317165818964438359695744604198246716410783223931430682808151056020475306791729591
e=0x10001
p = gcd(n1,n2)
q=n1/p
fn=(p - 1) * (q - 1)
d = computeD(fn, e)
m=pow(c1,d,n1)
print(hex(m)[2:-1].decode('hex'))
9.rsa_combinations
deforce rsa………!!!!
#! /usr/bin/python2.7
from Crypto.Util.number import size,bytes_to_long,getStrongPrime
from itertools import combinations
msg = bytes_to_long("Your secret flag is : flag{**************************}")
e = 65537
pri = []
f = open('cipherx.txt', 'w')
for i in range(5):
pri.append(getStrongPrime(1024,65537))
print('pri',pri)
for k in combinations(pri, 2):
n = k[0] * k[1]
print k[0],k[1]
f.write(str(pow(msg, e, n)) + '\n')
solve.py
#! usr/bin/python2.7
#coding=utf-8
import binascii
import gmpy2
def gcd(a, b):
if a < b:
a, b = b, a
while b != 0:
temp = a % b
a = b
b = temp
return a
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
c2 = 1246234818568605038771725387770032809896657624658751197487822667705150496788266236821445252745402061440344837126297118817722352360943422714353348519968257483217425318287123603122559539044278216514618542935008251728016376351207287908907419066172027356649934716661853550169371283110451199593919378518682893908073257597996213276417788967527409800490507319098619694553882580772197585922179030322385772341029003564359719244782484762058530989277184051441547024568631595655539528137422918541855814336215841836541683256179952847812650782272979437883178787135567291812430132598562391722110607279005808604132547633446702754242
c1 = 13455981172983326464102311937762831661788310626361076786164994487793945326981111197066703467784063584677545316464486222690177319997065759168374653040496712059568682406584202721616582863702654975066950060466986422582257001703187853927809075825528343329091775200012208860563692058684819775698290978617780577594014210672865880497874392738697086445744342656347507587613428993075257255547029724259635931665971785614738909042286207279739603543188892504358133043289264464915763121424437513688474543252743250750837754962444189265768058493217120380229238478428390747580847275659398491959011425398794606200760449574140326761335
c3 = 4888187708328317620094507614800274226981107085929590254185425273559042976171503907943793194842845890835133406885671925681517347731439124039971268535772441389943526257018243714512592593512323296725941627631582840937936230289732464068819395084847503736153991018426601148001171410680610396315398455868476519242523364370643315263903656899707643857165005292144961418736390628879183534554050946402008748537061851428674751948379857099827888766867529291843558247067650218013841320566949128247840292451599528568785840031947044173916230774125850838571273228740235067857273673072775479606479505558411747622879981674961795496398
c4 = 5945807707085423616106397090464145288661224101014907693104654596081518092031824289580553655597136400293583390581989219838293858796303129177903562794487009660324129992480484791256849653177916440709763357317237732026978876936371843211238777064330897077782446698577278202922221650609784909136488983753316374328060041688862833502261386605214386656750469198595184961624056503168436674528338454488445689162595307651649338939926811181397583426347049799471037024928424365956074689363634987714880064366326557578148205795406310315807810873199906864220949509516643869325208494504730147145059516579980994124490343208766447536810
c5 = 6187445948828077692015970911804646938282242052772994916845077569070730070453969382819385152870562813549652542234501650247554999118997287612656768657169917874500360552882579507148077964788035519927189184337650311696041346297615679489279371787315665879866086591715868260088943256008041145891355773432381271043597673424658569516927545882320343535771872720945022165744462740208023473214182506701311573606230422976998106293803156552098142853857635121713770388765373265153557740921629496699557717987765469270646934300913295007513219413849883613183601728166411181113787689840581266359785250985019212532583960800460788015491
c6 = 5212091418073782411520553214182135709421767268933861097557470068670598830761237108296366132955527825989098372862689616150847719971020880914262684813844505249039731390296288313064277036616294317850242554242344468349017823603991546642546139312359635120516022621977198868713265236780584328968456455227210401242292651898111573896055644196069499504205254423973191477361052269017513569237003435455766967610384127786317357129201800175882818678442257638418605140567086462026872695510406713566416179338847089594383139719544078973639147656333759205784973323451162915648440751084782358602950098354039646328692181357908591122714
c7 = 3655638351649160392053613377223998746456935081525685917833104279800461813163792301601632928836306436302774882558931553763046873854372645433876037722220899647761264466458772539363592772806366025160060082392022496959043608616479633871824843539139765269866557324139669669180299880464960812373747543711884223811204173243558307161330834607275612285093379360358536623915157494256701984991891771698584900549732277659667805289723868414345078895913383480318010760628083474820289670382156241646315278789987701943251698483519785588242374214684684812447667402223553085547756490931266818022366894997520489636576763520143455761239
c8 = 22473849661397275053996298243554884261414191820929237708168650853330395912319504073426952208513086627198829384154042315234052506082911684608144173835091410795393615116386997884885069683405033389454289189585622646957977150864405507253019700368456175153569120706431504842630017193823414614613515543944012768438615372135192092455771020625920899643657460748140525123446385745452885018242994907719060418829076821951353655094288932417789785658686354925401717179930381179237133075628900875416109603229568575866141143927588631408100548721530988132959911381450682687082674104687988294384311340599275049224252503713916928373410
c9 = 1873513506226622659558980965960349556051601818636390593699111238742079235436048735742501009666517921834732172263333584189891447981830661750295791445758897570358691214228971207469306988655891013882209331385427955502522192570359268476079812111160032458293920218131883616683323041237563743943563895577660520218905767619038915659113775800791354119111094458073436219216055603238833113774387249183198627105364934918297190119325269494891789384314242315970885073496066247057106399028140269736234473860608631980241965505615924442715413658175017031374265609800935996459163053296259788980765102199701839555511572730799034774424
c10= 20415066745705913332960559851272168836161858864856687615100156867932858500059203383582659999680270947712850092591947365553338831150848535525568756863490320019679102804007709747313186252161566229585999657772047185972884107522202907260488147758131548047735509416576778951156037782507571965765760567109821746219259712533369530160331404056822935924868818144471996283443950605787104623265573763097577017088633658357190202370173046308936352735690024216178434559387107878752418634566838258964132836294305792991271935081972613859675575909742688564959474926073661839487937083301362266785004789397144843903897244356681794196480
p = gmpy2.gcd((c1-c2),(c3-c2))
q = gmpy2.gcd((c6-c9),(c7-c9))
c = c1
n = p*q
d = modinv(65537,(p-1)*(q-1))
m = hex(pow(c,d,n))
flag = m[2:]
print(binascii.unhexlify(flag))
10.rsa blast
generally with other encryption algorithm,and can blast by bits.
question.py
# import signal
n = 0xBACA954B2835186EEE1DAC2EF38D7E11582127FB9E6107CCAFE854AE311C07ACDE3AAC8F0226E1435D53F03DC9CE6701CF9407C77CA9EE8B5C0DEE300B11DD4D6DC33AC50CA9628A7FB3928943F90738BF6F5EC39F786D1E6AD565EB6E0F1F92ED3227658FDC7C3AE0D4017941E1D5B27DB0F12AE1B54664FD820736235DA626F0D6F97859E5969902088538CF70A0E8B833CE1896AE91FB62852422B8C29941903A6CF4A70DF2ACA1D5161E01CECFE3AD80041B2EE0ACEAA69C793D6DCCC408519A8C718148CF897ACB24FADD8485588B50F39BCC0BBF2BF7AD56A51CB3963F1EB83D2159E715C773A1CB5ACC05B95D2253EEFC3CCC1083A5EF279AF06BB92F
e = 0x10001
def pad(s):
s += (256 - len(s)) * chr(256 - len(s))
ret = ['\x00' for _ in range(256)]
for index, pos in enumerate(s_box):
ret[pos] = s[index]
return ''.join(ret)
def unpad(s):
ret = ['\x00' for _ in range(256)]
for index, pos in enumerate(invs_box):
ret[pos] = s[index]
return ''.join(ret[0:-ord(ret[-1])])
def str2int(s):
return int(s.encode('hex'), 16)
s_box = [
0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16
]
invs_box = [
0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5, 0x38, 0xBF, 0x40, 0xA3, 0x9E, 0x81, 0xF3, 0xD7, 0xFB,
0x7C, 0xE3, 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87, 0x34, 0x8E, 0x43, 0x44, 0xC4, 0xDE, 0xE9, 0xCB,
0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D, 0xEE, 0x4C, 0x95, 0x0B, 0x42, 0xFA, 0xC3, 0x4E,
0x08, 0x2E, 0xA1, 0x66, 0x28, 0xD9, 0x24, 0xB2, 0x76, 0x5B, 0xA2, 0x49, 0x6D, 0x8B, 0xD1, 0x25,
0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xD4, 0xA4, 0x5C, 0xCC, 0x5D, 0x65, 0xB6, 0x92,
0x6C, 0x70, 0x48, 0x50, 0xFD, 0xED, 0xB9, 0xDA, 0x5E, 0x15, 0x46, 0x57, 0xA7, 0x8D, 0x9D, 0x84,
0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A, 0xF7, 0xE4, 0x58, 0x05, 0xB8, 0xB3, 0x45, 0x06,
0xD0, 0x2C, 0x1E, 0x8F, 0xCA, 0x3F, 0x0F, 0x02, 0xC1, 0xAF, 0xBD, 0x03, 0x01, 0x13, 0x8A, 0x6B,
0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA, 0x97, 0xF2, 0xCF, 0xCE, 0xF0, 0xB4, 0xE6, 0x73,
0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD, 0x35, 0x85, 0xE2, 0xF9, 0x37, 0xE8, 0x1C, 0x75, 0xDF, 0x6E,
0x47, 0xF1, 0x1A, 0x71, 0x1D, 0x29, 0xC5, 0x89, 0x6F, 0xB7, 0x62, 0x0E, 0xAA, 0x18, 0xBE, 0x1B,
0xFC, 0x56, 0x3E, 0x4B, 0xC6, 0xD2, 0x79, 0x20, 0x9A, 0xDB, 0xC0, 0xFE, 0x78, 0xCD, 0x5A, 0xF4,
0x1F, 0xDD, 0xA8, 0x33, 0x88, 0x07, 0xC7, 0x31, 0xB1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xEC, 0x5F,
0x60, 0x51, 0x7F, 0xA9, 0x19, 0xB5, 0x4A, 0x0D, 0x2D, 0xE5, 0x7A, 0x9F, 0x93, 0xC9, 0x9C, 0xEF,
0xA0, 0xE0, 0x3B, 0x4D, 0xAE, 0x2A, 0xF5, 0xB0, 0xC8, 0xEB, 0xBB, 0x3C, 0x83, 0x53, 0x99, 0x61,
0x17, 0x2B, 0x04, 0x7E, 0xBA, 0x77, 0xD6, 0x26, 0xE1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0C, 0x7D
]
def mul(x, y, z):
ret = 1
while y != 0:
if y & 1 != 0:
ret = (ret * x) % z
x = (x * x) % z
y >>= 1
return ret
def welcom():
# signal.alarm(5)
print r"""
____ ____ _ ______ ______ _____ _____ __ __
| _ \/ ___| / \ / ___\ \ / / ___|_ _| ____| \/ |
| |_) \___ \ / _ \ \___ \\ V /\___ \ | | | _| | |\/| |
| _ < ___) / ___ \ ___) || | ___) || | | |___| | | |
|_| \_\____/_/ \_\ |____/ |_| |____/ |_| |_____|_| |_|
"""
def main():
welcom()
flag = open('./flag', 'r').read()
flag_len = len(flag)
assert(flag_len == 38)
flag = pad(flag)
while True:
print '''
1. sign flag
2. get signed flag
Please give me your choice :'''
cmd = raw_input()
if cmd == '1':
assert(len(flag) == 256)
flag = unpad(flag)[:flag_len] + raw_input('Please sign your flag (0 - %d): ' % (256 - flag_len))
assert(len(flag) <= 256)
flag = pad(flag)
print 'Success'
elif cmd == '2':
signature = mul(str2int(flag), e, n)
print 'Your signed flag ciphertext is : 0x%x' % signature
else:
print 'Bye bye'
exit(0)
if __name__ == '__main__':
main()
solve.py
#encoding=utf-8
from pwn import *
from time import sleep
# context.log_level='debug'
ip='123.59.138.211'
# ip='127.0.0.1'
ppp=[99, 124, 119, 123, 242, 107, 111, 197, 48, 1, 103, 43, 254, 215, 171, 118, 202, 130, 201, 125, 250, 89, 71, 240, 173, 212, 162, 175, 156, 164, 114, 192, 183, 253, 147, 38, 54, 63]
n = 0xBACA954B2835186EEE1DAC2EF38D7E11582127FB9E6107CCAFE854AE311C07ACDE3AAC8F0226E1435D53F03DC9CE6701CF9407C77CA9EE8B5C0DEE300B11DD4D6DC33AC50CA9628A7FB3928943F90738BF6F5EC39F786D1E6AD565EB6E0F1F92ED3227658FDC7C3AE0D4017941E1D5B27DB0F12AE1B54664FD820736235DA626F0D6F97859E5969902088538CF70A0E8B833CE1896AE91FB62852422B8C29941903A6CF4A70DF2ACA1D5161E01CECFE3AD80041B2EE0ACEAA69C793D6DCCC408519A8C718148CF897ACB24FADD8485588B50F39BCC0BBF2BF7AD56A51CB3963F1EB83D2159E715C773A1CB5ACC05B95D2253EEFC3CCC1083A5EF279AF06BB92F
e = 0x10001
def str2int(s):
return int(s.encode('hex'), 16)
def s1(fff):
p.recvuntil('choice :\n')
p.sendline('1')
p.recvuntil('):')
p.sendline(fff)
def s2():
p.recvuntil('choice :\n')
p.sendline('2')
p.recvuntil('is : ')
t=p.recvline()
# print('t',t.replace('\n',''))
return t
flag="f"
for i in range(2,39):
p=remote(ip, 23333)
# p.interactive()
s1(chr(256-i)*218)
s1('')
c=s2()
m=[chr(256-i) for tm in range(256)]
for l in range(len(flag)):
m[ppp[l]]=flag[l]
for jj in range(0,256):
m[ppp[i-1]]=chr(jj)
kkk=""
for mm in m:
kkk+=mm
kkk=str2int(kkk)
if(pow(kkk,e,n)==int(c,16)):
flag+=chr(jj)
print(flag)
break
p.close()
- haved knowed high bits of Plaintext
with e=3,you can use Coppersmith theorem to find it with a log(n) algorithm.
you should use it in sage.(in sage cloud is ok)
import time
debug = True
# display matrix picture with 0 and X
def matrix_overview(BB, bound):
for ii in range(BB.dimensions()[0]):
a = ('%02d ' % ii)
for jj in range(BB.dimensions()[1]):
a += '0' if BB[ii,jj] == 0 else 'X'
a += ' '
if BB[ii, ii] >= bound:
a += '~'
print a
def coppersmith_howgrave_univariate(pol, modulus, beta, mm, tt, XX):
"""
Coppersmith revisited by Howgrave-Graham
finds a solution if:
* b|modulus, b >= modulus^beta , 0 < beta <= 1
* |x| < XX
"""
#
# init
#
dd = pol.degree()
nn = dd * mm + tt
#
# checks
#
if not 0 < beta <= 1:
raise ValueError("beta should belongs in (0, 1]")
if not pol.is_monic():
raise ArithmeticError("Polynomial must be monic.")
#
# calculate bounds and display them
#
"""
* we want to find g(x) such that ||g(xX)|| <= b^m / sqrt(n)
* we know LLL will give us a short vector v such that:
||v|| <= 2^((n - 1)/4) * det(L)^(1/n)
* we will use that vector as a coefficient vector for our g(x)
* so we want to satisfy:
2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)
so we can obtain ||v|| < N^(beta*m) / sqrt(n) <= b^m / sqrt(n)
(it's important to use N because we might not know b)
"""
if debug:
# t optimized?
print "\n# Optimized t?\n"
print "we want X^(n-1) < N^(beta*m) so that each vector is helpful"
cond1 = RR(XX^(nn-1))
print "* X^(n-1) = ", cond1
cond2 = pow(modulus, beta*mm)
print "* N^(beta*m) = ", cond2
print "* X^(n-1) < N^(beta*m) \n-> GOOD" if cond1 < cond2 else "* X^(n-1) >= N^(beta*m) \n-> NOT GOOD"
# bound for X
print "\n# X bound respected?\n"
print "we want X <= N^(((2*beta*m)/(n-1)) - ((delta*m*(m+1))/(n*(n-1)))) / 2 = M"
print "* X =", XX
cond2 = RR(modulus^(((2*beta*mm)/(nn-1)) - ((dd*mm*(mm+1))/(nn*(nn-1)))) / 2)
print "* M =", cond2
print "* X <= M \n-> GOOD" if XX <= cond2 else "* X > M \n-> NOT GOOD"
# solution possible?
print "\n# Solutions possible?\n"
detL = RR(modulus^(dd * mm * (mm + 1) / 2) * XX^(nn * (nn - 1) / 2))
print "we can find a solution if 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)"
cond1 = RR(2^((nn - 1)/4) * detL^(1/nn))
print "* 2^((n - 1)/4) * det(L)^(1/n) = ", cond1
cond2 = RR(modulus^(beta*mm) / sqrt(nn))
print "* N^(beta*m) / sqrt(n) = ", cond2
print "* 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n) \n-> SOLUTION WILL BE FOUND" if cond1 < cond2 else "* 2^((n - 1)/4) * det(L)^(1/n) >= N^(beta*m) / sqroot(n) \n-> NO SOLUTIONS MIGHT BE FOUND (but we never know)"
# warning about X
print "\n# Note that no solutions will be found _for sure_ if you don't respect:\n* |root| < X \n* b >= modulus^beta\n"
#
# Coppersmith revisited algo for univariate
#
# change ring of pol and x
polZ = pol.change_ring(ZZ)
x = polZ.parent().gen()
# compute polynomials
gg = []
for ii in range(mm):
for jj in range(dd):
gg.append((x * XX)**jj * modulus**(mm - ii) * polZ(x * XX)**ii)
for ii in range(tt):
gg.append((x * XX)**ii * polZ(x * XX)**mm)
# construct lattice B
BB = Matrix(ZZ, nn)
for ii in range(nn):
for jj in range(ii+1):
BB[ii, jj] = gg[ii][jj]
# display basis matrix
if debug:
matrix_overview(BB, modulus^mm)
# LLL
BB = BB.LLL()
# transform shortest vector in polynomial
new_pol = 0
for ii in range(nn):
new_pol += x**ii * BB[0, ii] / XX**ii
# factor polynomial
potential_roots = new_pol.roots()
print "potential roots:", potential_roots
# test roots
roots = []
for root in potential_roots:
if root[0].is_integer():
result = polZ(ZZ(root[0]))
if gcd(modulus, result) >= modulus^beta:
roots.append(ZZ(root[0]))
#
return roots
############################################
# Test on Stereotyped Messages
##########################################
print "//////////////////////////////////"
print "// TEST 1"
print "////////////////////////////////"
# RSA gen options (for the demo)
length_N = 1024 # size of the modulus
Kbits = 512 # size of the root
e = 3
# RSA gen (for the demo)
N=0x79982a272b9f50b2c2bc8b862ccc617bb39720a6dc1a22dc909bbfd1243cc0a03dd406ec0b1a78fa75ce5234e8c57e0aab492050906364353b06ccd45f90b7818b04be4734eeb8e859ef92a306be105d32108a3165f96664ac1e00bba770f04627da05c3d7513f5882b2807746090cebbf74cd50c0128559a2cc9fa7d88f7b2d
ZmodN = Zmod(N);
# Create problem (for the demo)
K = ZZ.random_element(0, 2^Kbits)
Kdigits = K.digits(2)
M = [0]*Kbits + [1]*(length_N-Kbits);
for i in range(len(Kdigits)):
M[i] = Kdigits[i]
M = ZZ(M, 2)
C=0x381db081852c92d268b49a1b9486d724e4ecf49fc97dc5f20d1fad902b5cdfb49c8cc1e968e36f65ae9af7e8186f15ccdca798786669a3d2c9fe8767a7ae938a4f9115ae8fed4928d95ad550fddd3a9c1497785c9e2279edf43f04601980aa28b3b52afb55e2b34e5b175af25d5b3bd71db88b3b31e48a177a469116d957592c
b=0xfedcba98765432100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
# Problem to equation (default)
P.<x> = PolynomialRing(ZmodN) #, implementation='NTL')
pol = (b + x)^e - C
dd = pol.degree()
# Tweak those
beta = 1 # b = N
epsilon = beta / 7 # <= beta / 7
mm = ceil(beta**2 / (dd * epsilon)) # optimized value
tt = floor(dd * mm * ((1/beta) - 1)) # optimized value
XX = ceil(N**((beta**2/dd) - epsilon)) # optimized value
# Coppersmith
start_time = time.time()
roots = coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX)
# output
print "\n# Solutions"
print "we want to find:",str(K)
print "we found:", str(roots)
print("in: %s seconds " % (time.time() - start_time))
print "\n"
12.wiener attack
if e looks very big.the d may very small.
wiener is best to deal it.
wiener attack
13.Boneh Durfee Method
if $ d \leq { N ^ 0.292 } $
waiting …..
14.choose cipher attack
alice : m,n,e,c
bob : p,q,d,e
alice give c to bob
but we attack it.
we choose a and a need gcd(a,n)==1.
computer y=(c * pow(a,e,n))%n
import gmpy2
e=3
d=76049878755826336166698139456670360823402717889604969895349508344800412770121957624523975279069318035733764051730593939133424845912466592703373981870874751299015095128705553078747239081130209768910810258649166320353848933996042110730355149970574587323408350943779715053374237240149786382572122316303550059037311599492982439109580656235437909296003096272288705370676044110102935615857801394460044326948435774452489727128000706767789005786209476060332099626876494991496861201654482133245707868426039793944745637143823027996364278711920669753886683794052292533067458821708034433961163807255826762446204313797046780518947
N=114074818133739504250047209185005541235104076834407454843024262517200619155182936436785962918603977053600646077595890908700137268868699889055060972806312126948522642693058329618120858621695314653366215387973749480530773400994063166095532724955861880985112526415669572580061355860224679573858183474455325088556643994673345465994162610420723170253345262031304174343327749668957998269532265104735742501097132399909676529715137398930849255495327761212026819673358330120772259339210848101393790624794141497382162858696771273350710124735773784422786465775396114824753700050260926501450377050949467981761553058188615697572753
r=234523452
M=int('flag{test_for_cca}'.encode('hex'),16)
cipher=pow(M,e,N)
print 'Initial cipher:\t',cipher
cipher_dash = (cipher * pow(r,e,N)) % N
print 'Eve gets Bob to decipher:\t',cipher_dash
# cipher_dash=90511031607784830273878497072346123546679455256898204196402641372333492940234358009499271727755472553207867386254653658733724900948880219984215792979665435989733167788337042506336114726850208031943574244260983595450232099102339183752672009132355515013239721171582732831124336428650165790015071038470233163029309771817779975903409021754911379543318740006147263912863780000070643964489448504069333128038084002549074569589992574916389850594000510506164205174491002424884037866223779862414707858447048555823073520047145522373211382098608293593800755101294502576108329124664271831858488981525137002348725042733161552081766
decipher = pow(cipher_dash,d,N)
print 'Bob says that the result is wrong:',decipher
print 'Eve determines as:',hex(decipher/r)[2:-1].decode('hex')
15.e is not prime number
if e is not prime number.use next two scripts.
solve1.py
#-*- coding:utf-8 -*-
from Crypto.Util.number import *
import sympy
def gcd(a,b):
if a < b:
a,b = b,a
while b != 0:
tem = a % b
a = b
b = tem
return a
def invalidExponent(p,q,e,c):
phiN = (p - 1) * (q - 1)
n = p * q
GCD = gcd(e, phiN)
if (GCD == 1):
return "Public exponent is valid....."
d = inverse(e//GCD,phiN)
c = pow(c, d, n)
plaintext = sympy.root(c, GCD)
plaintext = long_to_bytes(plaintext)
return plaintext
def main():
p =111052706592359766492182549474994387389169491981939276489132990221393430874991652628482505832745103981784837665110819809096264457329836670397000634684595709283710756727662219358743235400779394350023790569023369287367240988429777113514012101219956479046699448481988253039282406274512111898037689623723478951613
q =146182161315365079136034892629243958871460254472263352847680359868694597466935352294806409849433942550149005978761759458977642785950171998444382137410141550212657953776734166481126376675282041461924529145282451064083351825934453414726557476469773468589060088164379979035597652907191236468744400214917268039573
e = 200
c =7797067792814175554801975939092864905908878472965854967525218347636721153564161093453344819975650594936628697646242713415817737235328825333281389820202851500260665233910426103904874575463134970160306453553794787674331367563821223358610113031883172742577264334021835304931484604571485957116313097395143177603380107508691261081725629713443494783479897404175199621026515502716868988672289887933681890547568860707175288422275073767747544353536862473367590288531216644146154729962448906402712219657000812226637887827912541098992158458173920228864293993030475885461755767069329678218760943185942331149777258713727459739405
plaintext = invalidExponent(p,q,e,c)
print plaintext
main()
solve2.py
import gmpy2
p =111052706592359766492182549474994387389169491981939276489132990221393430874991652628482505832745103981784837665110819809096264457329836670397000634684595709283710756727662219358743235400779394350023790569023369287367240988429777113514012101219956479046699448481988253039282406274512111898037689623723478951613
q =146182161315365079136034892629243958871460254472263352847680359868694597466935352294806409849433942550149005978761759458977642785950171998444382137410141550212657953776734166481126376675282041461924529145282451064083351825934453414726557476469773468589060088164379979035597652907191236468744400214917268039573
e = 200
c =7797067792814175554801975939092864905908878472965854967525218347636721153564161093453344819975650594936628697646242713415817737235328825333281389820202851500260665233910426103904874575463134970160306453553794787674331367563821223358610113031883172742577264334021835304931484604571485957116313097395143177603380107508691261081725629713443494783479897404175199621026515502716868988672289887933681890547568860707175288422275073767747544353536862473367590288531216644146154729962448906402712219657000812226637887827912541098992158458173920228864293993030475885461755767069329678218760943185942331149777258713727459739405
# e=pow(2,3)*25
e1=25
n=p*q
d =gmpy2.invert(e1,(p-1)*(q-1))
flag8 = pow(c,d,n)
print hex(gmpy2.iroot(flag8,(e/e1))[0])[2:].decode('hex')
over
if something new,I’ll add it
tips:install gmpy2 in linux
conda install gmpy2 -n <your env >
