目录
easySteram
根据题目发现hint数据的获取方式为lcg，进行解密
from functools import reduce
from gmpy2 import gcd
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, x, y = egcd(b % a, a)
return (g, y - (b // a) * x, x)
def modinv(b, n):
g, x, _ = egcd(b, n)
if g == 1:
return x % n
def crack_unknown_increment(states, modulus, multiplier):
increment = (states[1] - states[0]*multiplier) % modulus
return modulus, multiplier, increment
def crack_unknown_multiplier(states, modulus):
multiplier = (states[2] - states[1]) * modinv(states[1] - states[0], modulus) % modulus
return crack_unknown_increment(states, modulus, multiplier)
def crack_unknown_modulus(states):
diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
modulus = abs(reduce(gcd, zeroes))
return crack_unknown_multiplier(states, modulus)
hint = [3552318300093355576,7287716593817904745,10709650189475092178,9473306808836439162,7033071619118870]
print(crack_unknown_modulus(hint))
n = 11011221100673486657
m = 9842418632484481741
c = 9282148899700689121
s6 = (hint[4]*m+c)%n
print(s6)hint中的每一组数据都是文件的名称，提取二进制key，进行lfsr的正常解密即可
mask = [1,0,1,0,1,0,0,0,1,0,0,0,0,1,0,0,0,1,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,1,0,0,0,0,1,0]
s = [1,0,1,0,1,1,0,0,1,0,0,0,0,1,0,0,1,0,0,0,0,0,1,1,0,1,0,1,0,0,1,0,1,1,1,1,0,0,1,0,1,0,0,0,1,0,0,1]
suf = []
def bitAnd(a, b):
return list(map(lambda x,y: int(x)&int(y), a, b))
for i in range(48):
if bitAnd([0] + suf + s[0:47 - i], mask).count(1) % 2 == s[47 - i]:
suf = [0] + suf
else:
suf = [1] + suf
flag = ""
for i in suf:
flag +=str(i)
print(flag)bad-curve
椭圆曲线上的乘法问题，直接爆破log，正常解密
p = 5861
a=5144
b=7002
O = (0, 0)
def div(u, v):
return u*pow(v, 1, p)
def add(P, Q):
if P == O:
return Q
if Q == O:
return P
if P[0] == Q[0] and (P[1]+Q[1]) % p == 0:
return O
if P != Q:
l = div(Q[1]-P[1], Q[0]-P[0]) % p
else:
l = div(3*P[0]**2+a, 2*P[1]) % p
x = l**2-P[0]-Q[0]
y = l*(P[0]-x)-P[1]
return (x % p, y % p)
def mul(P, s):
if s == 1:
return P
Y = mul(P, s//2)
X = add(Y, Y)
if s % 2 == 1:
X = add(X, P)
return X
P = (1616,1351)
Q = (5733,603)
for i in range(1,100):
if mul(P,i)==Q:
print(i)
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes,bytes_to_long
from Crypto.Util.Padding import pad
from hashlib import sha256
aes=AES.new(int(89).to_bytes(16,'big'), AES.MODE_CBC, bytes(16))
c = long_to_bytes(4772913380768971224711602816943506381429523609738355134556748160902211637274533659159340900788332375138903310885955)
flag=aes.decrypt(pad(c,AES.block_size))
print(flag)RSA2
首先进行e2的爆破
import gmpy2
c1 = 8321449807360182827125
c2 = 8321441183828895770712
print(gmpy2.iroot(c1,3))
print(gmpy2.iroot(c2,3))
a = []
for i in range(20210401, 20210505):
for e in range(50000,60000):
if e+i+7==20264365 and e+i==20264358:
print(e)由g = d * (p – 0xdeadbeef)与费马小定理结合推导分解n
import gmpy2
from gmpy2 import gcd
a = [53957,53956,53955,53954,53953,53952,53951,53950,53949,53948,53947,53946,53945,53944,53943,53942,53941,53940,53939,53938,53937,53936,53935,53934,53933,53932,53931,53930,53929,53928,53927,53926,53925,53924,53923,53922,53921,53920,53919,53918,53917,53916,53915,53914,53913,53912,53911,53910,53909,53908,53907,53906,53905,53904,53903,53902,53901,53900,53899,53898,53897,53896,53895,53894,53893,53892,53891,53890,53889,53888,53887,53886,53885,53884,53883,53882,53881,53880,53879,53878,53877,53876,53875,53874,53873,53872,53871,53870,53869,53868,53867,53866,53865,53864,53863,53862,53861,53860,53859,53858,53857,53856,53855,53854]
for e in a:
n = 378094963578091245652286477316863605753157432437621367359342302751615833557269627727449548734187939542588641672789504086476494927855747407344197241746889123693358997028141479289459947165818881146467218957546778123656120190207960702225556466771501844979094137868818924556860636212754616730115341674681116573326890134855072314950288530400350483394140781434097516134282100603979066057391672872913866678519235744668652042193736205044674422210689619562242862928626697711582401250962536787125165979017740138070213899305175933585261127763164192929103624167063213758551239415744211455417108907505646457646161227272639379721764779734013149963229002406400371319674194009206372087547010201440035410745572669645666856126204769178179570446069571090298945041726576151255620825221663591127702492882834949100599423704250729752444923956601971323645242934249137015933524911614158989705977723056398299344849153945858516695027157652464450872079484515561281333287781393423326046633891002695625031041881639987758851943448352789469117137668229144914356042850963002345804817204906458653402636643504354041188784842235312540435896510716835069861282548640947135457702591305281493685478066735573429735004662804458309301038827671971059369532684924420835204769329
h = 73848642434738867367477225086726888395852920758614133495828335507877859511862002848037040713538347334802971992946443655728951228215538557683172582670964297757897239619386044898759264210423339349230213909268805339389420150987118078950524911018047255588024612603547365858714122701018350042307021931058343380562835003665731568505773484122782553098643140312700105413000212984821873751937531991369317400032403465633780535286923404386459988367374340142852850593284541563858829367072310534803205896401476440899512604526967410832990327872756442819020392626930518136601018466180890464963004282304763488756943631269919832869202
g = 3976547671387654068675440379770742582328834393823569801056509684207489138919660098684138301408123275651176128285451251938825197867737108706539707501679646427880324173378500002196229085818500327236191128852790859809972892359594650456622821702698053681562517351687421071768373342718445683696079821352735985061279190431410150014034774435138495065087054406766658209697164984912425266716387767166412306023197815823087447774319129788618337421037953552890681638088740575829299105645000980901907848598340665332867294326355124359170946663422578346790893243897779634601920449118724146276125684875494241084873834549503559924080309955659918449396969802766847582242135030406950869122744680405429119205293151092844435803672994194588162737131647334232277272771695918147050954119645545176326227537103852173796780765477933255356289576972974996730437181113962492499106193235475897508453603552823280093173699555893404241432851568898226906720101475266786896663598359735416188575524152248588559911540400610167514239540278528808115749562521853241361159303154308894067690191594265980946451318139963637364985269694659506244498804178767180096195422200695406893459502635969551760301437934119795228790311950304181431019690890246807406970364909654718663130558117158600409638504924084063884521237159579000899800018999156006858972064226744522780397292283123020800063335841101274936236800443981678756303192088585798740821587192495178437647789497048969720110685325336457005611803025549386897596768084757320114036370728368369612925685987251541629902437275412553261624335378768669846356507330025425467339014984330079364067149950238561943275006049728406278318846998650496707162387768801213108565185221147664770009978012050906904959264045050100404522270495606970447076283894255951481388496134870426452215997834228869196114684962261076716651779120620585343304887755029463545328534291186
kp = pow(2,e*g,n) * pow(2,0xdeadbeef-1,n)
p = gcd(kp-1,n)
q = n//p
phi = (p-1)*(q-1)
c = 141187369139586875794438918220657717715220514870544959295835385681523005285553297337947377472083695018833866941104904071675141602626896418932763833978914936423338696805941972488176008847789235165341165167654579559935632669335588215515509707868555632337151209369075754122977694992335834572329418404770856890386340258794368538033844221701815983303376617825048502634692029763947325144731383655217790212434365368739783525966468588173561230342889184462164098771136271291295174064537653917046323835004970992374805340892669139388917208009182786199774133598205168195885718505403022275261429544555286425243213919087106932459624050446925210285141483089853704834315135915923470941314933036149878195756750758161431829674946050069638069700613936541544516511266279533010629117951235494721973976401310026127084399382106355953644368692719167176012496105821942524500275322021731162064919865280000886892952885748100715392787168640391976020424335319116533245350149925458377753639177017915963618589194611242664515022778592976869804635758366938391575005644074599825755031037848000173683679420705548152688851776996799956341789624084512659036333082710714002440815131471901414887867092993548663607084902155933268195361345930120701566170679316074426182579947
if gcd(e,phi) == 1:
d = gmpy2.invert(e,phi)
m = hex(pow(c,d,n))
print(e)
print(m)RSA-with-hidden-p_part
与n1CTF 2019中的题目类似，简单分析，进行p的高位爆破
from gmpy2 import *
from libnum import *
e = 65537
n=17792839004069206505311165358965315159660960021876501638465779564660435354728866263950853789588593668127397781562022048299972203542490012884029610338759733016996976148246425653534473740879965981219064248163192069030090884735828855170495382479655366526033714537180090769165324090204860138147523482782402175203226238151594614492880153873145258957724395582001330822432735918506940599321342304662083198563995641394668197278283191088011830808723938187712792916629375128024721501299600284578947502283415715172218993597794995155493943923831639727793517623689226167983344366410056166618746678592793631650760012411580637035777
f = open('flag.enc','rb').read().split()
cipher = [int(i,0) for i in f]
data=[8137189, 8137231, 8137333, 8137387, 8137513, 8137609, 8137733, 8137783, 8137853, 8137919, 8137979, 8138239, 8138371, 8138443, 8138489, 8138513, 8138561, 8138717, 8138729, 8138737, 8138789, 8138807, 8138861, 8138881, 8138909, 8139017, 8139113, 8139151, 8139221, 8139301, 8139331, 8139377, 8139431, 8139451, 8139497, 8139589, 8139683, 8139709, 8139773, 8139797, 8139871, 8139959, 8139973, 8140043, 8140087, 8140103, 8140117, 8140133, 8140159, 8140177, 8140211, 8140421, 8140441, 8140537, 8140571, 8140609, 8140651, 8140661, 8140763, 8140843, 8140961, 8140981, 8141117, 8141137, 8141143, 8141153, 8141213, 8141267, 8141377, 8141459, 8141531, 8141603, 8141753, 8141879, 8141893, 8142137, 8142151, 8142157, 8142271, 8142389, 8142397, 8142467, 8142487, 8142557, 8142637, 8142731, 8142751, 8142803, 8142821, 8142833, 8143007, 8143043, 8143199, 8143273, 8143313, 8143319, 8143351, 8143601, 8143627, 8143651, 8143769, 8143781, 8143853, 8144009, 8144011, 8144083, 8144137, 8144219, 8144237, 8144261, 8144497, 8144651, 8144743, 8144803, 8144839, 8144879, 8144957, 8145031, 8145113, 8145139, 8145173, 8145209, 8145283, 8145349, 8145419, 8145443, 8145479, 8145671, 8145673, 8145689, 8145691, 8145911, 8146169, 8146363, 8146507, 8146511, 8146529, 8146609, 8146639, 8146673, 8146819, 8146867, 8146969, 8147071, 8147101, 8147123, 8147159, 8147261, 8147351, 8147407, 8147551, 8147567, 8147627, 8147653, 8147791, 8147813, 8147917, 8147921, 8147933, 8148059, 8148221, 8148263, 8148367, 8148499, 8148541, 8148551, 8148571, 8148677, 8148713, 8148727, 8148733, 8148737, 8148743, 8148779, 8148839, 8148977, 8149151, 8149237, 8149279, 8149301, 8149367, 8149369, 8149457, 8149553, 8149639, 8149741, 8149759, 8149949, 8150029, 8150047, 8150321, 8150333, 8150369, 8150561, 8150629, 8150647, 8150741, 8150839, 8151023, 8151079, 8151113, 8151167, 8151193, 8151203, 8151271, 8151401, 8151431, 8151827, 8151887, 8151937, 8151953, 8151967, 8151991, 8152031]
padding = []
for i in range(len(data)):
padding.append(data[i]**2)
ccc = {}
for i in range(len(padding)):
ccc[str(pow(padding[i]<<1,e,n))]=0
ccc[str(pow(padding[i]<<2,e,n))]=1
phar = ''
for i in range(len(cipher)):
phar = str(ccc[str(cipher[i])])+phar
print(int(phar,2))
import gmpy2
pbar = 11820026693187076726118808485305105465666823386947922735440269483223044778424815772142880112297698070148416497723797809485529364856468926499841358871215301672204583025074
n = 17792839004069206505311165358965315159660960021876501638465779564660435354728866263950853789588593668127397781562022048299972203542490012884029610338759733016996976148246425653534473740879965981219064248163192069030090884735828855170495382479655366526033714537180090769165324090204860138147523482782402175203226238151594614492880153873145258957724395582001330822432735918506940599321342304662083198563995641394668197278283191088011830808723938187712792916629375128024721501299600284578947502283415715172218993597794995155493943923831639727793517623689226167983344366410056166618746678592793631650760012411580637035777
for kbits in range(1024):
P.<x> = PolynomialRing(Zmod(n))
f = pbar*2**kbits + x
f = f.monic()
x0 = f.small_roots(X=2**kbits, beta=0.4)
if x0 != []:
print(x0)
import gmpy2
import binascii
#p = pbar*2**kbits + x
p = 7630565621866583539199284874408741078896087217771560834410788256164994537885828788563275406165578176249435378346388954770543720632831980647945543175466531292077886502002440355317924227295889233679028751283214292990688578864859032869399650269907501262691589498175018482073387903710462993127
e = 65537
n=17792839004069206505311165358965315159660960021876501638465779564660435354728866263950853789588593668127397781562022048299972203542490012884029610338759733016996976148246425653534473740879965981219064248163192069030090884735828855170495382479655366526033714537180090769165324090204860138147523482782402175203226238151594614492880153873145258957724395582001330822432735918506940599321342304662083198563995641394668197278283191088011830808723938187712792916629375128024721501299600284578947502283415715172218993597794995155493943923831639727793517623689226167983344366410056166618746678592793631650760012411580637035777
c=47544416942854840596876466634550757138457971777147902559332161978926437099575250451807599366474677616289825131936185950220522336363178955584220874970220865200716718183695366602106708856027144557504589893189728060818136500378667888349394918331945326795210323330208786962431108052065902363650047527024838196525288156921316276153197248136532473469956110283681199279132343194309319016175321231286064860091953668148386662333142666601571105164788444790879102866676641554466606414127621055197889576107822754427386801908786157440099385224491288571327853804008872915570680784690649728102620799753745868995526912824797945211
q = n//p
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(binascii.unhexlify(hex(m)[2:])