for (size_t i = 0; i < n_blocks; i++) { uint32_t v[2] = { enc[2*i], enc[2*i + 1] }; tea_decrypt(v, key); for (int b = 0; b < 4; b++) { flag[pos++] = (v[0] >> (8 * b)) & 0xFF; } for (int b = 0; b < 4; b++) { flag[pos++] = (v[1] >> (8 * b)) & 0xFF; } } flag[pos] = '\0';
printf("%s\n", flag); return0; }
LitCTF{590939df61690383a47ed1bc6ade9d51}
密码
第一题:basic
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
from Crypto.Util.number import * from enc import flag
m = bytes_to_long(flag) n = getPrime(1024) e = 65537 c = pow(m,e,n) print(f"n = {n}") print(f"e = {e}") print(f"c = {c}")
''' n = 150624321883406825203208223877379141248303098639178939246561016555984711088281599451642401036059677788491845392145185508483430243280649179231349888108649766320961095732400297052274003269230704890949682836396267905946735114062399402918261536249386889450952744142006299684134049634061774475077472062182860181893 e = 65537 c = 22100249806368901850308057097325161014161983862106732664802709096245890583327581696071722502983688651296445646479399181285406901089342035005663657920475988887735917901540796773387868189853248394801754486142362158369380296905537947192318600838652772655597241004568815762683630267295160272813021037399506007505 '''
瞄了一眼,它只用了单个素数n作为模板,那就没什么意思了,直接计算φ(n)和d,最后解m转字符串即可
1 2 3 4 5 6 7 8 9 10
from Crypto.Util.number import long_to_bytes, inverse
n = 150624321883406825203208223877379141248303098639178939246561016555984711088281599451642401036059677788491845392145185508483430243280649179231349888108649766320961095732400297052274003269230704890949682836396267905946735114062399402918261536249386889450952744142006299684134049634061774475077472062182860181893 e = 65537 c = 22100249806368901850308057097325161014161983862106732664802709096245890583327581696071722502983688651296445646479399181285406901089342035005663657920475988887735917901540796773387868189853248394801754486142362158369380296905537947192318600838652772655597241004568815762683630267295160272813021037399506007505 phi = n - 1 d = inverse(e, phi) m = pow(c, d, n)
from sage.allimport * from Crypto.Util.number import * from uuid import uuid4
flag = b'LitCTF{'+ str(uuid4()).encode() + b'}' flag = bytes_to_long(flag) len_flag = flag.bit_length() e = 65537 p = getPrime(512) P = GF(p) A = [[flag, getPrime(len_flag)], [getPrime(len_flag), getPrime(len_flag)]] A = matrix(P, A) B = A ** e
# e = 65537 # p = 8147594556101158967571180945694180896742294483544853070485096002084187305007965554901340220135102394516080775084644243545680089670612459698730714507241869 # B = [[2155477851953408309667286450183162647077775173298899672730310990871751073331268840697064969968224381692698267285466913831393859280698670494293432275120170, 4113196339199671283644050914377933292797783829068402678379946926727565560805246629977929420627263995348168282358929186302526949449679561299204123214741547], [3652128051559825585352835887172797117251184204957364197630337114276860638429451378581133662832585442502338145987792778148110514594776496633267082169998598, 2475627430652911131017666156879485088601207383028954405788583206976605890994185119936790889665919339591067412273564551745588770370229650653217822472440992]]
直接丁真到
1 2
A = [[flag, getPrime(len_flag)], [getPrime(len_flag), getPrime(len_flag)]]
from Crypto.Util.number import * from enc import flag
m = bytes_to_long(flag) e = 65537 p,q = getPrime(1024),getPrime(1024) n = p*q noise = getPrime(40) tmp1 = noise*p+noise*q tmp2 = noise*noise hint = p*q+tmp1+tmp2 c = pow(m,e,n) print(f"n = {n}") print(f"e = {e}") print(f"c = {c}") print(f"hint = {hint}") ''' n = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565066224724927142875488372745811265526082952677738164529563954987228906850399133238995317510054164641775620492640261304545177255239344267408541100183257566363663184114386155791750269054370153318333985294770328952530538998873255288249682710758780563400912097941615526239960620378046855974566511497666396320752739097426013141 e = 65537 c = 1443781085228809103260687286964643829663045712724558803386592638665188285978095387180863161962724216167963654290035919557593637853286347618612161170407578261345832596144085802169614820425769327958192208423842665197938979924635782828703591528369967294598450115818251812197323674041438116930949452107918727347915177319686431081596379288639254670818653338903424232605790442382455868513646425376462921686391652158186913416425784854067607352211587156772930311563002832095834548323381414409747899386887578746299577314595641345032692386684834362470575165392266454078129135668153486829723593489194729482511596288603515252196 hint = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565315879035806034866363781260326863226820493638303543900551786806420978685834963920605455531498816171226961859405498825422799670404315599803610007692517859020686506546933013150302023167306580068646104886750772590407299332549746317286972954245335810093049085813683948329319499796034424103981702702886662008367017860043529164 '''
这里存在噪声,会影响h 注意到
1
hint = p*q+tmp1+tmp2
那么就有了恢复p和q的方法 原式可转变为
1
hint−n=(noisep+noiseq+noise**2)=noise(p+q+noise).
那么就有了入手的方向,noise很小,PR法求noise,解pq然后复原d,直接解就可以了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
from Crypto.Util.number import * import gmpy2 n = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565066224724927142875488372745811265526082952677738164529563954987228906850399133238995317510054164641775620492640261304545177255239344267408541100183257566363663184114386155791750269054370153318333985294770328952530538998873255288249682710758780563400912097941615526239960620378046855974566511497666396320752739097426013141 e = 65537 c = 1443781085228809103260687286964643829663045712724558803386592638665188285978095387180863161962724216167963654290035919557593637853286347618612161170407578261345832596144085802169614820425769327958192208423842665197938979924635782828703591528369967294598450115818251812197323674041438116930949452107918727347915177319686431081596379288639254670818653338903424232605790442382455868513646425376462921686391652158186913416425784854067607352211587156772930311563002832095834548323381414409747899386887578746299577314595641345032692386684834362470575165392266454078129135668153486829723593489194729482511596288603515252196 hint = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565315879035806034866363781260326863226820493638303543900551786806420978685834963920605455531498816171226961859405498825422799670404315599803610007692517859020686506546933013150302023167306580068646104886750772590407299332549746317286972954245335810093049085813683948329319499796034424103981702702886662008367017860043529164 diff = hint - n X = 942430120937 s = (diff // X) - X D = gmpy2.isqrt(s * s - 4 * n) p = (s + D) // 2 q = (s - D) // 2 assert p * q == n, "p*q != n,解出错" phi = (p - 1) * (q - 1) d = gmpy2.invert(e, phi) m = pow(c, d, n) flag = long_to_bytes(m) print("Flag:", flag.decode())
挺不错的题
LitCTF{13dd217e-9a67-4093-8a1b-d2592c45ba82}
baby
这题好难好baby(背比)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
import gmpy2 from Crypto.Util.number import * from enc import flag
m = bytes_to_long(flag) g = getPrime(512) t = getPrime(150) data = (t * gmpy2.invert(m, g)) % g print(f'g = {g}') print(f'data = {data}') ''' g = 7835965640896798834809247993719156202474265737048568647376673642017466116106914666363462292416077666356578469725971587858259708356557157689066968453881547 data = 2966297990428234518470018601566644093790837230283136733660201036837070852272380968379055636436886428180671888655884680666354402224746495312632530221228498 '''
from Crypto.Util.number import long_to_bytes, isPrime defcont_frac(numer, denom):
while denom: a = numer // denom yield a numer, denom = denom, numer - a * denom defconvergents(cf_terms):
p0, q0 = 1, 0 p1, q1 = cf_terms[0], 1 yield p1, q1 for a in cf_terms[1:]: p2 = a * p1 + p0 q2 = a * q1 + q0 yield p2, q2 p0, p1 = p1, p2 q0, q1 = q1, q2 defmain(): g = 7835965640896798834809247993719156202474265737048568647376673642017466116106914666363462292416077666356578469725971587858259708356557157689066968453881547 data = 2966297990428234518470018601566644093790837230283136733660201036837070852272380968379055636436886428180671888655884680666354402224746495312632530221228498 cf = list(cont_frac(data, g)) for p, q in convergents(cf): t = data * q - p * g if t > 0and t.bit_length() == 150and isPrime(t): print("Found potential t:", t) m = q print("Recovered m (integer):", m) flag = long_to_bytes(m) print("Recovered flag:", flag) if __name__ == '__main__': main()
顺利出结果
1 2 3
Found potential t: 1195489027595714782252215502941452926270424077 Recovered m (integer): 637558173724466419510759412644075143734813144557473543913639658885806728973294110666447896405373 Recovered flag: b'LitCTF{56008a819331c9f3608a718327b7e6ce}