强网杯2024
21_steps
网上常见32bits的variable-precision SWAR算法求汉明重量
//计算32位二进制的汉明重量
uint32_t swar(uint32_t i)
{
i = (i & 0x55555555) + ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
i = (i & 0x0F0F0F0F) + ((i >> 4) & 0x0F0F0F0F);
i = (i * (0x01010101) >> 24);
return i;
}其本质如图：
第一次是计算数量，后面每一次位移都是在将之前的数量进行加和。 那么对于本题的长度，可以有：
import random
for _ in range(10):
A = random.randrange(0, 2**128)
clear_A = bin(A).count('1')
print(f'{A}\t的准确汉明重量是:\t{clear_A};', end='\t')
B = A >> 1
B = B & 0x55555555555555555555555555555555
A = A & 0x55555555555555555555555555555555
A =A + B
B = A >> 2
B = B & 0x33333333333333333333333333333333
A = A & 0x33333333333333333333333333333333
A = A + B
B = A >> 4
B = B & 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f
A = A & 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f
A = A + B
B = A >> 8
B = B & 0x00ff00ff00ff00ff00ff00ff00ff00ff
A = A & 0x00ff00ff00ff00ff00ff00ff00ff00ff
A = A + B
B = A >> 16
B = B & 0x0000ffff0000ffff0000ffff0000ffff
A = A & 0x0000ffff0000ffff0000ffff0000ffff
A = A + B
B = A >> 32
B = B & 0x00000000ffffffff00000000ffffffff
A = A & 0x00000000ffffffff00000000ffffffff
A = A + B
B = A >> 64
B = B & 0x0000000000000000ffffffffffffffff
A = A & 0x0000000000000000ffffffffffffffff
A = A + B
print(f'计算得到的汉明重量是:{A};', end='\t')
if A == clear_A:
print('计算正确')
else:
print('计算错误')
'''
82962123225600263380152948962299823829 的准确汉明重量是: 66; 计算得到的汉明重量是:66; 计算正确
279118512269027783758020377127073791218 的准确汉明重量是: 65; 计算得到的汉明重量是:65; 计算正确
24062365656261301754500154445709337479 的准确汉明重量是: 62; 计算得到的汉明重量是:62; 计算正确
81854661205650153152348182964470461766 的准确汉明重量是: 68; 计算得到的汉明重量是:68; 计算正确
211801759776211314755721283629774550465 的准确汉明重量是: 64; 计算得到的汉明重量是:64; 计算正确
60940536090310557361602843597216687041 的准确汉明重量是: 61; 计算得到的汉明重量是:61; 计算正确
43519910578333575023205492441558917426 的准确汉明重量是: 53; 计算得到的汉明重量是:53; 计算正确
206222555609674979001076533303072264095 的准确汉明重量是: 70; 计算得到的汉明重量是:70; 计算正确
279976217354585315326572257531444465752 的准确汉明重量是: 67; 计算得到的汉明重量是:67; 计算正确
67698258308178592418036430165885591557 的准确汉明重量是: 59; 计算得到的汉明重量是:59; 计算正确
'''这是种准确的算法，但是呢，本题要求21步，现在有28步，那么就得再审视一下算法过程了。 这种移位加和，真正有用的是每一步的最后几位承载着1的数量的地方，那么前边的就不起作用。 对于128bits，汉明重量最多128=2^7，那么8位足矣，就是说，当步骤进行到长度足以容纳8位时，就不用再进行位移了。 举个例子(16bits=2^4)：
A=0b0111010111001010#初始值
B=B>>1 =0b0011101011100101
B=B&0b0101010101010101 =0b0001000001000101
A=A&0b0101010101010101 =0b0101010101000000
A=A+B =0b0110010110000101
B=A>>2 =0b0001100101100001
B=B&0b0011001100110011 =0b0001000100100001
A=A&0b0011001100110011 =0b0010000100000001
A=A+B =0b0011001000100010
B=A>>4 =0b0000001100100010
B=B&0b0000111100001111 =0b0000001100000010
A=A&0b0000111100001111 =0b0000001000000010
A=A+B =0b0000010100000100
B=A>>8 =0b0000000000000101
B=B&0b0000000011111111 =0b0000000000000101#到这里以后，A和B“与”的值对AB的关键值就没有影响了
A=A&0b0000000011111111 =0b0000000000000100
A=A+B =0b0000000000001001=9
所以可以稍微省略一下
B=B>>1 =0b0011101011100101
B=B&0b0101010101010101 =0b0001000001000101
A=A&0b0101010101010101 =0b0101010101000000
A=A+B =0b0110010110000101
B=A>>2 =0b0001100101100001
B=B&0b0011001100110011 =0b0001000100100001
A=A&0b0011001100110011 =0b0010000100000001
A=A+B =0b0011001000100010
B=A>>4 =0b0000001100100010
B=B&0b0000111100001111 =0b0000001100000010
A=A&0b0000111100001111 =0b0000001000000010
A=A+B =0b0000010100000100
B=A>>8 =0b0000000000000101
A=A+B =0b0000010100001001
A=A&0b11111 =0b0000000000001001=9会发现，只要最后5位就够了（使用“与”来获取后5位），即使A中还有前边的10100000000，也不会干扰最终结果。
那么对于128bits，可以：
import random
for _ in range(10):
A = random.randrange(0, 2 ** 128)
clear_A = bin(A).count('1')
print(f'{A}\t的准确汉明重量是:\t{clear_A};', end='\t')
B = A >> 1
B = B & 0x55555555555555555555555555555555
A = A & 0x55555555555555555555555555555555
A = A + B
B = A >> 2
B = B & 0x33333333333333333333333333333333
A = A & 0x33333333333333333333333333333333
A = A + B
B = A >> 4
B = B & 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f
A = A & 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f
A = A + B
B = A >> 8
A = A + B
B = A >> 16
A = A + B
B = A >> 32
A = A + B
B = A >> 64
A = A + B
print(f'\t{'0b'+str(bin(A))[2:].zfill(128)}\t', end='')
A = A & 0b11111111
print(f'\t{'0b'+str(bin(A))[2:].zfill(128)}\t', end='')
print(f'计算得到的汉明重量是:{A};', end='\t')
if A == clear_A:
print('计算正确')
else:
print('计算错误')
'''
156579242306083359745180389594184682537 的准确汉明重量是: 64; 0b00000101000010010000101000001111000100010001011000011100001000000010001000101000001011100011001000110110001110110011110101000000 0b00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000 计算得到的汉明重量是:64; 计算正确
330870058660576211238599018870086049597 的准确汉明重量是: 59; 0b00000101000010110000110100010011000101100001101100011110001000000010010000100110001010000010110100101111001100010011011000111011 0b00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111011 计算得到的汉明重量是:59; 计算正确
3493174688920508492761457636753791180 的准确汉明重量是: 72; 0b00000001000000110000011000001100000100000001011000011110001000000010010000101010001011010011001100111010010000000100010001001000 0b00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001001000 计算得到的汉明重量是:72; 计算正确
111535249942145413184139912575106524284 的准确汉明重量是: 65; 0b00000100000010000000110000010000000101010001100000011101001000010010010100101001001010110011000100110100001110010011110001000001 0b00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000001 计算得到的汉明重量是:65; 计算正确
225013720372839435306733250002222284524 的准确汉明重量是: 59; 0b00000100000001100000011100001100000100100001011000010111000110100001101100100000001001010010101000101011001100000011011000111011 0b00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111011 计算得到的汉明重量是:59; 计算正确
292370324689757547981087286186540795099 的准确汉明重量是: 67; 0b00000110000010110001000000010111000111000001111100100100001001110010101100101110001100010011010000111001001111000011110101000011 0b00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000011 计算得到的汉明重量是:67; 计算正确
167230798881246611653236628394895035567 的准确汉明重量是: 71; 0b00000110000011000001000100010111000110110001110100100100001010010010110000101110001100010011010100111010001111100100000101000111 0b00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000111 计算得到的汉明重量是:71; 计算正确
168493424224678898982919544934046416759 的准确汉明重量是: 72; 0b00000110000010010000111000010001000101000001101000011101001000010010010000101010001100000011010100111000001110110100001001001000 0b00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001001000 计算得到的汉明重量是:72; 计算正确
202599588640453602660878813651801106433 的准确汉明重量是: 56; 0b00000011000010000000101000010000000100110001100000011101001000000010001000100111001010010010110000101111001101000011011100111000 0b00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111000 计算得到的汉明重量是:56; 计算正确
58493809962237551737237235332990765999 的准确汉明重量是: 65; 0b00000011000001000000101100010001000100110001011100011001001000000010010100101000001011000010111100110100001110000011101101000001 0b00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000001 计算得到的汉明重量是:65; 计算正确
'''而且刚好是减8步加1步，共计21步：
B=A>>1;B=B&113427455640312821154458202477256070485;A=A&113427455640312821154458202477256070485;A=A+B;B=A>>2;B=B&68056473384187692692674921486353642291;A=A&68056473384187692692674921486353642291;A=A+B;B=A>>4;B=B&20016609818878733144904388672456953615;A=A&20016609818878733144904388672456953615;A=A+B;B=A>>8;A=A+B;B=A>>16;A=A+B;B=A>>32;A=A+B;B=A>>64;A=A+B;A=A&255;测试验证成立
adbq
第一步：直接用p+q求phi
from gmpy2 import *
from Crypto.Util.number import *
p_q=18978581186415161964839647137704633944599150543420658500585655372831779670338724440572792208984183863860898382564328183868786589851370156024615630835636170
n= 89839084450618055007900277736741312641844770591346432583302975236097465068572445589385798822593889266430563039645335037061240101688433078717811590377686465973797658355984717210228739793741484666628342039127345855467748247485016133560729063901396973783754780048949709195334690395217112330585431653872523325589
e= 65537
enc=23664702267463524872340419776983638860234156620934868573173546937679196743146691156369928738109129704387312263842088573122121751421709842579634121187349747424486233111885687289480494785285701709040663052248336541918235910988178207506008430080621354232140617853327942136965075461701008744432418773880574136247
d= inverse(e,n+1-p_q)
print(long_to_bytes(pow(enc,d,n)))
#b'flag{yOu_can_'第二步：参考：https://github.com/DownUnderCTF/Challenges_2023_Public/blob/main/crypto/apbq-rsa-ii/solve/solv.sage
import itertools
from Crypto.Util.number import long_to_bytes
n,e = (73566307488763122580179867626252642940955298748752818919017828624963832700766915409125057515624347299603944790342215380220728964393071261454143348878369192979087090394858108255421841966688982884778999786076287493231499536762158941790933738200959195185310223268630105090119593363464568858268074382723204344819, 65537)
c = 30332590230153809507216298771130058954523332140754441956121305005101434036857592445870499808003492282406658682811671092885592290410570348283122359319554197485624784590315564056341976355615543224373344781813890901916269854242660708815123152440620383035798542275833361820196294814385622613621016771854846491244
hints =[18167664006612887319059224902765270796893002676833140278828762753019422055112981842474960489363321381703961075777458001649580900014422118323835566872616431879801196022002065870575408411392402196289546586784096, 16949724497872153018185454805056817009306460834363366674503445555601166063612534131218872220623085757598803471712484993846679917940676468400619280027766392891909311628455506176580754986432394780968152799110962, 17047826385266266053284093678595321710571075374778544212380847321745757838236659172906205102740667602435787521984776486971187349204170431714654733175622835939702945991530565925393793706654282009524471957119991, 25276634064427324410040718861523090738559926416024529567298785602258493027431468948039474136925591721164931318119534505838854361600391921633689344957912535216611716210525197658061038020595741600369400188538567]
V = hints
k = 2^800
M = Matrix.column([k * v for v in V]).augment(Matrix.identity(len(V)))
B = [b[1:] for b in M.LLL()]
M = (k * Matrix(B[:len(V)-2])).T.augment(Matrix.identity(len(V)))
B = [b[-len(V):] for b in M.LLL() if set(b[:len(V)-2]) == {0}]
for s, t in itertools.product(range(4), repeat=2):
T = s*B[0] + t*B[1]
a1, a2, a3 = T[:3] #只取前3个
kq = gcd(a1 * hints[1] - a2 * hints[0], n)
if 1 < kq < n:
print('find!', kq, s, t)
break
for i in range(2**16, 1, -1):
if kq % i == 0:
kq //= i
q = int(kq)
p = int(n // kq)
print("p=",p)
print("q=",q)
d = pow(e, -1, (p - 1) * (q - 1))
m = int(pow(c, d, n))
print(long_to_bytes(m).decode())
'''
find! 9067773077510925207378520309595658022345214442920360440202890774224295250116442048990578009377300541280465330975931465993745130297479191298485033569345231 0 1
p= 8112940945910485817171807897687451701452029959677470272197529542411816926233172848066074195817612280582244564398252967013953964546888998662975298338523549
q= 9067773077510925207378520309595658022345214442920360440202890774224295250116442048990578009377300541280465330975931465993745130297479191298485033569345231
s0lve_the_@pb
'''第三步：（正常做的话）
x,y = (68510878638370415044742935889020774276546916983689799210290582093686515377232591362560941306242501220803210859757512468762736941602749345887425082831572206675493389611203432014126644550502117937044804472954180498370676609819898980996282130652627551615825721459553747074503843556784456297882411861526590080037, 117882651978564762717266768251008799169262849451887398128580060795377656792158234083843539818050019451797822782621312362313232759168181582387488893534974006037142066091872636582259199644094998729866484138566711846974126209431468102938252566414322631620261045488855395390985797791782549179665864885691057222752)
n,e = (94789409892878223843496496113047481402435455468813255092840207010463661854593919772268992045955100688692872116996741724352837555794276141314552518390800907711192442516993891316013640874154318671978150702691578926912235318405120588096104222702992868492960182477857526176600665556671704106974346372234964363581, 65537)
c = 17737974772490835017139672507261082238806983528533357501033270577311227414618940490226102450232473366793815933753927943027643033829459416623683596533955075569578787574561297243060958714055785089716571943663350360324047532058597960949979894090400134473940587235634842078030727691627400903239810993936770281755
R = Integers(n)
P.<a, b, p, q> = PolynomialRing(Integers(n))
f1 = a*p + q
f2 = p + b*q
f3 = p*q
I = Ideal([f1 - x, f2 - y, f3 - n])
B = I.groebner_basis()
g = B[-1]
z = ZZ(g.coefficient({q: 1}))
assert g.constant_coefficient() == R(-y)
_, (z1, _), (z2, _) = list(g)
z1 = ZZ(z1)
z2 = ZZ(z2)
S = 2^512
def run():
for p_upper_bits in range(16):
p_upper = p_upper_bits << 510
for q_upper_bits in range(16):
q_upper = q_upper_bits << 510
M = matrix(ZZ, [[S, -1, 0, 0], [S*z1, 0, -1, 0], [S*(z2 + p_upper + q_upper*z1), 0, 0, S], [S*n, 0, 0, 0]])
B = M.LLL()
for b in B:
if b[-1] == S:
if b[1] < 0:
b *= -1
p_guess = b[1] + p_upper
q_guess = b[2] + q_upper
if p_guess * q_guess == n:
print("p=",p_guess)
print("q=",q_guess)
return
run()
#p= 9905620548201605885156022422063415601085834480000151605822057987478159841594294294921326498715477204858289946663768215404888792873149548220792561611271773
#q= 9569255094279531622931948225245971611906701972848014414215393188650730586931457021749130842033610157350354264040281415912589345114086187990999221247539297不过题目上使用RSA2加密的第三部分，直接用第二部分的pq：
from Crypto.Util.number import *
enc3 = 17737974772490835017139672507261082238806983528533357501033270577311227414618940490226102450232473366793815933753927943027643033829459416623683596533955075569578787574561297243060958714055785089716571943663350360324047532058597960949979894090400134473940587235634842078030727691627400903239810993936770281755
p=8112940945910485817171807897687451701452029959677470272197529542411816926233172848066074195817612280582244564398252967013953964546888998662975298338523549
q=9067773077510925207378520309595658022345214442920360440202890774224295250116442048990578009377300541280465330975931465993745130297479191298485033569345231
print(long_to_bytes(pow(enc3,inverse(e,(p-1)*(q-1)),n)))
#b'q_prob1em!!}'得到：#b'flag{yOu_can_s0lve_the_@pbq_prob1em!!}'
EasyRSA
本组的数据：
N=26299046616519328889516990195355203808210597385783734446970139991670842996383198381608796833248111959165031570309171711828885776018076179265706042403646945935242546890573064942876047961706370732617212711332724006319143086851119725243503614260905696450459437995987228354165096759554242138156349453504610239522130822246155579783139771648997351611423841248627159519888403602258018136319761051167703397533090987820738751255251681108772006196840218956927973902840616295136278392050230597514253771464322328323363939172932959422462991813310904073824321862705997710832597874870703407142887905952492680088495378079332072026783
e=65537
g=2503333429399421101969681910713350584255829348186635106557514398091987183753426294288248352613479498022713830553099751206487620196498450418076503043343
enc=25363652910592342908839541410273330011973605682212630500683400457202384376003485837929431762668636449201546267418236512102957623905379540462761078860173512517439240620356452187675927127540204507321544020003692000244752356417047006970423577793813144098039763309274758871734315876673387255092360700278912080627418727309331791752513345472569626563654947572996281382016928311710580690820140923853413628930886494965845073428127183334223139593885223670519228700582019374176774529423749462525815354962016826777267850179329689962346110269725464824909934182272018637734715980117701142427688114534046717688582956950804025541231根据核心生成代码：
def factorGen(self):
while True:
self.g = getPrime(500)
while not gmpy2.is_prime(2*self.g*self.a+1):
self.a = random.randint(2**523, 2**524)
while not gmpy2.is_prime(2*self.g*self.b+1):
self.b = random.randint(2**523, 2**524)
self.h = 2*self.g*self.a*self.b+self.a+self.b
if gmpy2.is_prime(self.h):
self.N = 2*self.h*self.g+1
print(len(bin(self.N)))
return得到N=(2*self.g*self.b+1)*(2*self.g*self.a+1)，也即p和q 此时显然p-1和q-1有大公因子：2*self.g 使用如下代码可以求出p和q：
import sympy
from gmpy2 import iroot
b=2*2503333429399421101969681910713350584255829348186635106557514398091987183753426294288248352613479498022713830553099751206487620196498450418076503043343
n=26299046616519328889516990195355203808210597385783734446970139991670842996383198381608796833248111959165031570309171711828885776018076179265706042403646945935242546890573064942876047961706370732617212711332724006319143086851119725243503614260905696450459437995987228354165096759554242138156349453504610239522130822246155579783139771648997351611423841248627159519888403602258018136319761051167703397533090987820738751255251681108772006196840218956927973902840616295136278392050230597514253771464322328323363939172932959422462991813310904073824321862705997710832597874870703407142887905952492680088495378079332072026783
D=int(iroot(n,4)[0]/b)*3
u,v=divmod((n-1)//b,b)
a=pow(3,b,n)
l=[pow(a,r*D,n) for r in range(D+1)]
for s in range(D+1):
if pow(a,u-s,n) in l:
r=l.index(pow(a,u-s,n))
c=r*D+s
x,y=sympy.symbols('x,y')
r=sympy.solve([x+y-c*b-v,x*y-u+c])[0]
x,y=r[x],r[y]
p,q=int(x*b+1),int(y*b+1)
break
print(p)
print(q)
#p=145908757809339994209024075322898670842458131616710612897350581106322783455661508555941237452243846180359407410405698407105701145196595872123928508362403341227026054713612624516931172326272718897942427590715959951579696200296826777129457208718901212269992145681980163439342287529682355541224028050036184177641
#q=180243098573181461165362068311475662479453585331431602297467620056101904083885223843472590920401292300516187749308647143400440324455843770551794197778631059355541279850718222698584563989691479330696930863618102294136520804956843894624014137452244643869367947244512560707040047109105964723726056166763318619463然后直接计算即可
phi=(p-1)*(q-1)
d=invert(e,phi)
print(long_to_bytes(pow(enc,d,N)))
#b'flag{fcf6da18-7fbc-4fea-aaca-caa0f8521d70}'