决赛
回文
1、题目信息
=QfzEDO4YDNlBzN4gzN0YGM1QzYyUGZ3QDZzgDM7V2Sn52bI52Q=2、解题方法
base64解码，两种思路：
要么是去掉前面=号解码
QfzEDO4YDNlBzN4gzN0YGM1QzYyUGZ3QDZzgDM7V2Sn52bI52Q=要么去掉后面=号再翻转一下解码
Q25Ib25nS2V7MDgzZDQ3ZGUyYzQ1MGY0Nzg4NzBlNDY4ODEzfQ=显然试过后发现第二种是对的
CnHongKe{083d47de2c450f478870e468813}RSA2
1、题目信息
from Crypto.Util.number import*
import random
from gmpy2 import gcd ,invert
import os,random
from functools import reduce
flag = 'flag{*****}'
nbit = 2048
pbit = 658
qbit = nbit-pbit
def GCRT(mi, ai):
assert (isinstance(mi, list) and isinstance(ai, list))
curm, cura = mi[0], ai[0]
for (m, a) in zip(mi[1:], ai[1:]):
d = gcd(curm, m)
c = a - cura
assert (c % d == 0)
K = c / d * invert(curm / d, m / d)
cura += curm * K
curm = curm * m / d
return (cura % curm, curm)
def genkey():
p = getPrime(pbit)
q = getPrime(qbit)
assert(gcd(p-1,(q-1)//2) != 1 and q >= int(pow(p*q,qbit//nbit)))
n = p*q
while 1:
dp,dq = random.getrandbits(50), getPrime(50)
d = GCRT([p-1,q-1],[dp,dq])[0]
if(gcd(d, (p-1)*(q-1)) == 1):
break
e = invert(d,(p-1) * (q-1))
return n,e
n,e= genkey()
flag = flag + os.urandom(40)
flag = bytes_to_long(flag)
assert(flag2、解题方法
这个题还是很难的，从大佬那里学到的方法。。。。
首先观察d的产生方式，而且发现p,q相差很大，因此想到Cryptanalysis of Unbalanced RSA with Small CRT-Exponent
这里讲了公私钥的产生方式，有个疑惑的点是论文里说了p-1和（q-1）/2must be coprime（互素），但是题目附件中
不是这样的。why？
然后网上搜索一番后找到了lazzzaro大神的脚本：https://lazzzaro.github.io/2020/05/06/crypto-RSA/index.html
#sage
N=
e=
n = 12 # 或n=5
beta = 0.32 # beta = 0.3212890625
delta = 0.02 # delta = 0.0244140625
X = int(N ** delta*(n+1)/2)
Y = int(N ** (delta + beta)*(n+1)/2)
def C(a,b):
ret=1
for i in range(b):
ret*=(a-i)
ret/=(b-i)
return ret
def get_Matrix(n,m):
MM=[[0 for __ in range(n)] for _ in range(n)]
for j in range(n):
pN=max(0,m-j)
for i in range(j+1):
MM[j][i]=pow(N,pN)*pow(X,n-i-1)*pow(Y,i)*pow(e,j-i)*C(j,i)*pow(-1,i)
MM=Matrix(ZZ,MM)
return MM
M=get_Matrix(n,n//2+1)
L=M.LLL()[0]
x,y = var('x'),var('y')
f=0
for i in range(n):
f+=x**(n-i-1) * y**i * (L[i] // pow(X,n-i-1) // pow(Y,i))#将x,y参数化
print(f.factor())参数beta：
参数delta：
参数n：n为格子的维度，大佬用下面的式子计算出n，对于本题来说，求得的n=3.408695
但是实际用脚本的过程中，发现n=4并不能得到想要的结果，n=5可能是一个最低值
beta =
delta =
n = round((1-2*beta-2*delta)/((1-beta)^2-2*delta-beta),6)
m = (1-beta)*n
print(m,n)结果得到：
...(603601239605461619719962824215850028370828276194986402520006784945171666555162381560306067089554862768237542295127706223128204911327713581268000464342787657534895446276895456449104343518846054862311913534953258511*x + 1115967702502739*y)从后往前， 第一个是dp，第二个是k
然后利用这两个式子求p
exp：
from Crypto.Util.number import *
import gmpy2
k = 603601239605461619719962824215850028370828276194986402520006784945171666555162381560306067089554862768237542295127706223128204911327713581268000464342787657534895446276895456449104343518846054862311913534953258511
dp = 1115967702502739
n = 24520888125100345615044288264230762903878924272518571342713995342063192899124989891699091460914318368533612522321639660343147487234147817765379565866063142022911783047710228071012334390251457138278189863078398353697056081286846816500611712981402958876560909958985941278622099006464269427107124576069124593580390423932176305639686809675964840679026457045269910781753881177055233058940084858058581167930068081780478893848660425039669034700316924547379360271738374641525963541506226468912132334624110432284070298157810487695608530792082901545749959813831607311669250447276755584806773237811351439714525063949561215550447
e = 11548167381567878954504039302995879760887384446160403678508673015926195316468675715911159300590761428446214638046840120602736300464514722774979925843178572277878822181099753174300465194145931556418080206026501299370963578262848611390583954955739032904548821443452579845787053497638128869038124506082956880448426261524733275521093477566421849134936014202472024600125629690903426235360356780817248587939756911284609010060687156927329496321413981116298392504514093379768896049697560475240887866765045884356249775891064190431436570827123388038801414013274666867432944085999838452709199063561463786334483612953109675470299
c = 7903942109284616971177039757063852086984176476936099228234294937286044560458869922921692962367056335407203285911162833729143727236259599183118544731181209893499971239166798975272362502847869401536913310597050934868114362409772188138668288760287305966467890063175096408668396691058313701210130473560756912616590509776003076415730640467731466851294845080825312579944440742910769345079740436037310725065646739277834041891837233390010487460412084089630786396822488869754420904734966722826157548254882580507819654527378643632759059506306290252851428488883937359516531613654502801727220504711666666550673928496325962262842
k = k + 1
p = (e * dp - 1) // k + 1
print(int(p).bit_length())
q = n // p
print(int(q).bit_length())
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(int(m)))
#CnHongKe{1b35037a-a472-4e9c-bdba-768f7e84dd0e}根据
但是，这题不知道为什么k要加上1
总之，理解不太透彻，只能存下脚本了。。。
RSA3
1、题目信息
from Crypto.Util.number import *
from secret import flag
m = bytes_to_long(flag)
p1, q1 = getPrime(512), getPrime(512)
n1 = p1*q1
e = 65537
p2, q2 = getPrime(512), getPrime(512)
n2 = p2*q2
print(f'n1 = {n1}')
print(f'n2 = {n2}')
print(f'c1 = {pow(m,e,n2)}')
print(f'c2 = {pow(n1-m,e,n2)}')
# n1 = 52579135273678950581073020233998071974221658902576724000130040488018033110534210901239397446395736563148970863970460542205225993317478251099451639165369081820130823165642873594136020122857712288395352930384057524510346112486008850200845915783772351449146183974239444691330777565342525218070680067550270554767
# n2 = 68210568831848267339414957973218186686176324296418282565773310695862151827108036984694027795077376921170907068110296451176263520249799154781062517066423984526868547296781709439425857993705489037768605485740968600877866332458671029054092942851472208033494968784822459369206497698469167909174346042658361616469
# c1 = 42941712708129054668823891960764339394032538100909746015733801598044118605733969558717842106784388091495719003761324737091667431446354282990525549196642753967283958283202592037329821712755519455155110675327321252333824912095517427885925854391047828862338332559137577789387455868761466777370476884779752953853
# c2 = 627040432528616388953706748275598041846507086922277895328799415900389117998572328986923354297734808896240461677925738851259455113564560736884359119751610532315890199344271512309240049448472914341670679058031802071832098880822755831206334082327491193002005553278837194663491640621634593005189939520468737240052、解题方法
e太大了，对于Franklin攻击来说要跑很久，看到大佬WP后了解需要用到 half-gcd
参考文章：
HALF-GCD算法的阐述
多项式 gcd 的正确姿势：Half-GCD 算法
脚本来源：
https://github.com/rkm0959/rkm0959_implements/blob/main/Half_GCD/code.sage
exp:
from Crypto.Util.number import *
import sys
def HGCD(a, b):
if 2 * b.degree() = PolynomialRing(Zmod(n2))
f = x^e - c1
g = (n1 - x)^e - c2
res = GCD(f,g)
m = -res.monic().coefficients()[0]
print(m)
flag = long_to_bytes(int(m))
print(flag)
#CnHongKe{Fr4nkl1n_R31ter_4nd_gcD}GCD(f,g)返回ax-bM，a,b代表任意数字
用monic()使得上式变为x-M，再提取 M
RSA4
1、题目信息
from Crypto.Util.number import *
from os import *
from secret import flag
assert len(flag) 2、解题方法
展开后发现
在Coppersmith下模n，会把q全部模完，所以可以直接求出t
hint = 43691909620514553907337084747877613125770180914725560231672822190047048268654323014909857087117101555550872581680976037673609645072816688179430921113411189775681186282652913102207473404267361338845128228750191128828347979058211793191911795538917687509092140331114867217314732225741963090158157118956958361667
n = 139415227833650606627481949032630333904915784502498383402775795770352459104117035911044614539656661779065034631025979910419387363425628162982061251276669112098757186870838748231794731153245273066810769109396532311364451556967782895742561287251234088360088678874714586399626016737310602036235187097500522638791
R. = PolynomialRing(Zmod(n))
f = x^4 + x^3 + x^2 + x + 2023 - hint
res = f.small_roots(X=2^32,beta=0.4)
print(res)
# res = [4000655279]
发现m一直出不来
接着就是爆破k
exp:
from Crypto.Util.number import *
c = 6580860405834148836110773014414875358234621644983930335529135801623195480368832
n = 139415227833650606627481949032630333904915784502498383402775795770352459104117035911044614539656661779065034631025979910419387363425628162982061251276669112098757186870838748231794731153245273066810769109396532311364451556967782895742561287251234088360088678874714586399626016737310602036235187097500522638791
hint = 43691909620514553907337084747877613125770180914725560231672822190047048268654323014909857087117101555550872581680976037673609645072816688179430921113411189775681186282652913102207473404267361338845128228750191128828347979058211793191911795538917687509092140331114867217314732225741963090158157118956958361667
r = 11779674470989201650533406519886591289516202072957618550910646323186300227953911
R. = PolynomialRing(Zmod(n))
f = x^4 + x^3 + x^2 + x + 2023 - hint
res = f.small_roots(X=2^32,beta=0.4)
# print(res)
t = res[0]
# print(t)
t = 4000655279
m = discrete_log(mod(c,r),mod(t,r))
print(int(m).bit_length())
order = []
for i in factor(r-1):
if pow(t,(r-1)//i[0],r) == 1:
order.append(i[0])
# print(order)
# [2, 17]
phi = (r - 1) // 34
for k in range(2^22):
temp = m + k*phi
flag = long_to_bytes(temp)
try:
if len(flag.decode()) 复赛
asr
1、题目信息
from Crypto.Util.number import *
from secret import flag
def genprime():
while True:
r = getRandomNBitInteger(64)
p = r**6 + 8*r**4 - 41*r**3 + 14*r**2 - 116*r + 31387
q = r**5 - 9*r**4 + 17*r**3 - 311*r**2 - 16*r + 14029
if isPrime(p) and isPrime(q):
return p, q
def enc(flag, n):
m = bytes_to_long(flag)
return pow(m, 31387, n)
p, q = genprime()
n = p * q
c = enc(flag, n)
print(n)
print(c)2、解题方法
把n开11次方，得到的r’会略大于或者略小于r
爆破一下
exp:
from Crypto.Util.number import *
import gmpy2
n = 73553176031506251642448229714220151174734540964434813056145000616720019024269982417494553771890010861489245572362590935764438928110836109730139595790550323300572059713433794357690270439325805603980903813396260703
c = 6035303231100318215656164353047198868742763055193754611914191674005776329646395050293747516587004104241717689072827492745628156828285466831779549229513115371571798719567117034735830671759951028004405762435531685
e = 31387
r = gmpy2.iroot(n,11)[0]
for i in range(100000):
p = r**6 + 8*r**4 - 41*r**3 + 14*r**2 - 116*r + 31387
q = r**5 - 9*r**4 + 17*r**3 - 311*r**2 - 16*r + 14029
r = r+1
if isPrime(p) and isPrime(q) and n==p*q:
print(p)
q = n // p
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))
break
# b'CnHongKe{m0re_fuN_RSA!!!}'结果发现，只需要r+1就行了
脚本来源：2023 江苏领航杯
ezrsa
1、题目信息
from Crypto.Util.number import *
from gmpy2 import invert
#from secret import flag,e
e=11299
flag="CnHongKe{xxxxx}"
def enc(key, p):
e, n = key
cipher = [pow(ord(char), e, n) for char in p]
return cipher
def dec(pk, c):
key, n = pk
plain = [chr(pow(char, key, n)) for char in c]
return ''.join(plain)
p = getPrime(512)
q = getPrime(512)
n = p*q
pubkey = (e,n)
assert(e 2、解题方法
直接爆破
exp:
e = 11299
n =
c = [...]
flag = ''
for j in range(len(c)):
for i in range(32,128):
if pow(i,e,n) == c[j]:
flag += chr(i)
print(flag)
#CnHongKe{a8cc755d375811f55cec82153388c}prng
1、题目信息
from Crypto.Util.number import *
from secret import flag
import random
def base(n, l):
bb = []
while n > 0:
n, r = divmod(n, l)
bb.append(r)
return ''.join(str(d) for d in bb[::-1])
def prng(secret):
seed = base(secret, 5)
seed = [int(i) for i in list(seed)]
length = len(seed)
R = [[ random.randint(0,4) for _ in range(length)] for _ in range(length*2)]
S = []
for r in R:
s = 0
for index in range(length):
s += (r[index] * seed[index]) % 5
s %= 5
S.append(s)
return R, S
m = bytes_to_long(flag)
R, S = prng(m)
with open('output.txt', 'w') as f:
f.write(f'R = {R}nS = {S}')2、解题方法
divmod(n,l)返回(n // l,n % l)
base(n,l)就是把n，写成l进制
分析代码知道
上面代码自己生成数据
在GF(5)下解这个矩阵方程
exp:
#sage
from Crypto.Util.number import *
R = [[] , ... , []]
S = []
r = Matrix(GF(5),R)
s = vector(GF(5),S)
seed = r.solve_righ服务器托管网t(s)
m = list(seed)
flag = ""
# flag="".join(map(str,m))
for i in m:
flag += str(i)
flag = long_to_bytes(int(flag,5))
print(flag)
# CnHongKe{l1ne4r_prng_1s_d4ngr0s~~!d9uxdj9223}bd
1、题目信息
from Crypto.Util.number import *
from secret im服务器托管网port flag
p = getPrime(512)
q = getPrime(512)
n = p * q
d = getPrime(299)
e = inverse(d,(p-1)*(q-1))
m = bytes_to_long(flag)
c = pow(m,e,n)
hint1 = p >> (512-70)
hint2 = q >> (512-70)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"hint1 = {hint1}")
print(f"hint2 = {hint2}")
"""
n = 73337798113265277242402875272164983073482378701520700321577706460042584510776095519204866950129951930143711572581533177043149866218358557626070702546982947219557280493881836314492046745063916644418320245218549690820002504737756133747743286301499039227014032044403571945455215839074583290324966069724343874361
e = 42681919079074901709680276679968298324860328305878264036188155781983964226653746568102282190906458519960811259171162918944726137301701132135900454469634110653076655027353831375989861927565774719655974876907429954299669710134188543166679161864800926130527741511760447090995444554722545165685959110788876766283
c = 35616516401097721876690503261383371143934066789806504179229622323608172352486702183654617788750099596415052166506074598646146147151595929618406796332682042252530491640781065608144381326123387506000855818316664510273026302748073274714692374375426255513608075674924804166600192903250052744024508330641045908599
hint1 = 740477612377832718425
hint2 = 767891335159501447918
"""2、解题方法
根据大佬师傅WP，需要利用上高位的boneh_durfee攻击
参考论文：https://eprint.iacr.org/2023/367.pdf
他们实验时的脚本：https://pastebin.com/zpUkrfDh
论文中提到：
对于1024bit的模，当m = 7, t = 3的时候，至少需要27位p的高位，才能成功
exp:
import time
time.clock = time.time
debug = True
strict = False
helpful_only = True
dimension_min = 7 # 如果晶格达到该尺寸，则停止移除
# 显示有用矢量的统计数据
def helpful_vectors(BB, modulus):
nothelpful = 0
for ii in range(BB.dimensions()[0]):
if BB[ii,ii] >= modulus:
nothelpful += 1
print (nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")
# 显示带有 0 和 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'
if BB.dimensions()[0] = bound:
a += '~'
#print (a)
# 尝试删除无用的向量
# 从当前 = n-1（最后一个向量）开始
def remove_unhelpful(BB, monomials, bound, current):
# 我们从当前 = n-1（最后一个向量）开始
if current == -1 or BB.dimensions()[0] = bound:
affected_vectors = 0
affected_vector_index = 0
# 让我们检查它是否影响其他向量
for jj in range(ii + 1, BB.dimensions()[0]):
# 如果另一个向量受到影响：
# 我们增加计数
if BB[jj, ii] != 0:
affected_vectors += 1
affected_vector_index = jj
# 等级：0
# 如果没有其他载体最终受到影响
# 我们删除它
if affected_vectors == 0:
#print ("* removing unhelpful vector", ii)
BB = BB.delete_columns([ii])
BB = BB.delete_rows([ii])
monomials.pop(ii)
BB = remove_unhelpful(BB, monomials, bound, ii-1)
return BB
# 等级：1
#如果只有一个受到影响，我们会检查
# 如果它正在影响别的向量
elif affected_vectors == 1:
affected_deeper = True
for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
# 如果它影响哪怕一个向量
# 我们放弃这个
if BB[kk, affected_vector_index] != 0:
affected_deeper = False
# 如果没有其他向量受到影响，则将其删除，并且
# 这个有用的向量不够有用
#与我们无用的相比
if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) = PolynomialRing(ZZ) #多项式环
Q = PR.quotient(x*y + 1 - u) # u = xy + 1
polZ = Q(pol).lift()
UU = XX*YY + 1
# x-移位
gg = []
for kk in range(mm + 1):
for ii in range(mm - kk + 1):
xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
gg.append(xshift)
gg.sort()
# 单项式 x 移位列表
monomials = []
for polynomial in gg:
for monomial in polynomial.monomials(): #对于多项式中的单项式。单项式（）：
if monomial not in monomials: # 如果单项不在单项中
monomials.append(monomial)
monomials.sort()
# y-移位
for jj in range(1, tt + 1):
for kk in range(floor(mm/tt) * jj, mm + 1):
yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
yshift = Q(yshift).lift()
gg.append(yshift) # substitution
# 单项式 y 移位列表
for jj in range(1, tt + 1):
for kk in range(floor(mm/tt) * jj, mm + 1):
monomials.append(u^kk * y^jj)
# 构造格 B
nn = len(monomials)
BB = Matrix(ZZ, nn)
for ii in range(nn):
BB[ii, 0] = gg[ii](0, 0, 0)
for jj in range(1, ii + 1):
if monomials[jj] in gg[ii].monomials():
BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)
#约化格的原型
if helpful_only:
# #自动删除
BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
# 重置维度
nn = BB.dimensions()[0]
if nn == 0:
print ("failure")
return 0,0
# 检查向量是否有帮助
if debug:
helpful_vectors(BB, modulus^mm)
# 检查行列式是否正确界定
det = BB.det()
bound = modulus^(mm*nn)
if det >= bound:
print ("We do not have det 多项式 1 和 2
if debug:
print ("在格中寻找线性无关向量")
found_polynomials = False
for pol1_idx in range(nn - 1):
for pol2_idx in range(pol1_idx + 1, nn):
# 对于i and j, 构造两个多项式
PR. = PolynomialRing(ZZ)
pol1 = pol2 = 0
for jj in range(nn):
pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)
# 结果
PR. = PolynomialRing(ZZ)
rr = pol1.resultant(pol2)
if rr.is_zero() or rr.monomials() == [1]:
continue
else:
print ("found them, using vectors", pol1_idx, "and", pol2_idx)
found_polynomials = True
break
if found_polynomials:
break
if not found_polynomials:
print ("no independant vectors could be found. This should very rarely happen...")
return 0, 0
rr = rr(q, q)
# solutions
soly = rr.roots()
if len(soly) == 0:
print ("Your prediction (delta) is too small")
return 0, 0
soly = soly[0][0]
ss = pol1(q, soly)
solx = ss.roots()[0][0]
return solx, soly
def example():
############################################
# 随机生成数据
##########################################
#start_time =time.perf_counter
start =time.clock()
size=512
length_N = 2*size;
ss=0
s=70;
M=1 # the number of experiments
delta = 299/1024
# p = random_prime(2^512,2^511)
for i in range(M):
# p = random_prime(2^size,None,2^(size-1))
# q = random_prime(2^size,None,2^(size-1))
# if(p
题目给出了p的高70位，所以exp中把s由27改为了70，得出：
d=783087701705468761679148299766995936398557044101882919430819055852416479930185217204358163
from Crypto.Util.number import *
n =
d =
c =
m = pow(c,d,n)
print(long_to_bytes(m))
#CnHongKe{Y0u_m4d3_n3w_rec0rd!!!1113dsd2et}另外一种解法参考：2023 江苏领航杯 misc密码wp
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
相关推荐: 企业APP混乱繁杂？WorkPlus助您实现统一入口管理
在现代企业中，随着移动应用的不断发展和应用，公司内部往往存在着各种各样的APP。这些APP不仅需要单独下载和安装，而且管理起来也显得非常繁琐。为了解决这一问题，公司统一APP入口逐渐成为了企业的追求。而在众多选择中，WorkPlus作为领先品牌，以其出色的解决…
