周末打了强网杯，“坐大牢”。这里放一哈比赛中我搞出来的几道题目（都是一些没什么技术含量的题，还是太菜了。）
强网先锋
speed up
题目需要计算2^27的阶乘结果的各个位数之和
直接运行 factorial
sagemath 也还有一个 gamma 函数，
https://oeis.org/search?q=1%2C+2%2C+6%2C+9%2C+63&go=Search)
题目的 f(x) 函数就是个个位数相加，直接跑这个循环要跑麻，这里选择转 str 再求和
aaa = gamma(2^27+1)
bbb = str(aaa)
from tqdm import tqdm
res = 0
for each in tqdm(bbb):
res += int(each)
print(res)
或者计算一下 直接去查序列也能查到
1, 2, 6, 9, 63 - OEIS (https://oeis.org/search?q=1%2C+2%2C+6%2C+9%2C+63&go=Search)
石头剪刀布
根据代码，代码前五次出拳是随便出的，然后会“训练”。测试的时候发现，刚开始我出5个石头，然后第六七次代码都出布，如果我第八九次都出剪刀，代码第十次会出石头。所以其实代码出法是固定的，主要应该是根据我前面的出法。因此其实就相当于摸黑走迷宫。每次试错，然后根据代码的出法选择能赢的出法就可以了。
from pwn import *
context.log_level = 'debug'
flag="00000112201202021021100111222001200221101201010212202100221101012020210210011122101220120"
while True:
print(flag)
sh = remote("8.147.131.244"，14183)
index=0
for i in range(5):
sh.recvuntil("）：")
sh.sendline(flag[index])
index+=1
res = sh.recvuntil("-----------------------------------")
#print(res.decode())
while True:
sh.recvuntil("）：")
if index<len(flag):
sh.sendline(flag[index])
index+=1
else:
sh.sendline(flag[index-1])
res = sh.recvuntil("-----------------------------------")
print(res.decode())
if "Me10n出拳：剪刀" in res.decode():
flag+="0";break
elif "Me10n出拳：石头" in res.decode():
flag+="2";break
elif "Me10n出拳：布" in res.decode():
flag+="1";break
crypto
discrete_log
朴素dlp，只不过 flag 被填充了，填充已知，直接对c处理去填充，已知的“flag{}”，也可以去掉，多的偏移，就开根开掉，就能得到“裸”的 ，然后开始猜，45-6，flag最长是39个字节，这不可能解的出来，在 p-1=2q 的情况下。
猜长度不长，题目里有一个flag，里面有14 个字节.但是2^56，也是一个不切实际的数字。
猜字符不全，只有十六进制字符，结合bsgs算法，复杂度是16^7， 两个亿，可以接受，但是太慢，
后面试试 12 个字节， 一趟只有一千多万，运气不错，一发入魂（代码有点粗鄙，比赛的时候忘记 product 这个函数了哈哈哈哈哈，勿喷）
p = 173383907346370188246634353442514171630882212643019826706575120637048836061602034776136960080336351252616860522273644431927909101923807914940397420063587913080793842100264484222211278105783220210128152062330954876427406484701993115395306434064667136148361558851998019806319799444970703714594938822660931343299
g = 5
c = 105956730578629949992232286714779776923846577007389446302378719229216496867835280661431342821159505656015790792811649783966417989318584221840008436316642333656736724414761508478750342102083967959048112859470526771487533503436337125728018422740023680376681927932966058904269005466550073181194896860353202252854
from Crypto.Util.number import *
from tqdm import *
table = "0123456789abcdef"
ii=12
lengthpad = 128-ii-6
padding = bytes_to_long(b"flag{"+b'x00'*ii+b"}"+(chr(lengthpad)*lengthpad).encode())
#pad_inv = inverse(padding，p-1)
ctmp = c * (pow(g，-padding，p))%p
for _ in range(lengthpad*8+8):
ctmp = pow(ctmp，(p+3)//4，p)
mh={}
for i in tqdm(table):
for j in table:
for k in table:
for l in table:
for m in table:
for n in table:
mm = i+j+k+l+m+n
mm = mm.encode()
mm = bytes_to_long(mm)*1<<((ii//2)*8)
mh[pow(g，mm，p)] = mm
print("[+]")
ml={}
for i in tqdm(table):
for j in table:
for k in table:
for l in table:
for m in table:
for n in table:
mm = i+j+k+l+m+n
mm = mm.encode()
mm = bytes_to_long(mm)
if ctmp*pow(g，-mm，p) in mh:
print(mh[ctmp*pow(g，-mm，p)])
print(mm)
44%|████▍ | 7/16 [04:01<05:10， 34.51s/it]16771905891018463815302905856
60904317531494
56%|█████▋ | 9/16 [05:33<04:19， 37.05s/it]
>>> from Crypto.Util.number import *
>>> long_to_bytes(16771905891018463815302905856)
'61e800x00x00x00x00x00x00'
>>> long_to_bytes(60904317531494)
'7dd65f'
>>> 61e8007dd65f
not only rsa
题目的n是一个p^5，不过m填充了，所以不能偷鸡。另外 e 是p-1的因子。得先开根，再 lift一下。不过忘记lift怎么搞了。但是sagemath说它会，直接 nth_root 就可以了。他自己会 lift
from Crypto.Util.number import *
n = 6249734963373034215610144758924910630356277447014258270888329547267471837899275103421406467763122499270790512099702898939814547982931674247240623063334781529511973585977522269522704997379194673181703247780179146749499072297334876619475914747479522310651303344623434565831770309615574478274456549054332451773452773119453059618433160299319070430295124113199473337940505806777950838270849
e = 641747
c = 730024611795626517480532940587152891926416120514706825368440230330259913837764632826884065065554839415540061752397144140563698277864414584568812699048873820551131185796851863064509294123861487954267708318027370912496252338232193619491860340395824180108335802813022066531232025997349683725357024257420090981323217296019482516072036780365510855555146547481407283231721904830868033930943
c = Mod(c，n)
tmp = c.nth_root(e，all=True)
for t in tmp:
if b"flag{" in long_to_bytes(t):
print(long_to_bytes(t))
guess game
这题是分组相关的，估计是分组分析（赛后从 nepnep 师傅那里了解到好像是积分分析），但是不太会，但是看着解那么多，也许非预期了。看了一下要求，要求知道key的70%比特。key是随机生成的。那么期望我们是知道50%的。只要运气好那么亿点点就行了。好在交互也没有pow，放后台爆破就可以看下一题了。
from pwn import *
context.log_level = 40
for i in range(99999)
sh = remote('47.97.69.130'，22333)
sh.recvuntil('team token:')
sh.sendline('icq1f53668cd7a8a6cd934da51b6ac0f')
sh.recvuntil('>')
sh.sendline('2')
for _ in range(80):
sh.recvuntil(' > ')
sh.sendline('1')
fff = sh.recv()
if b"flag" in fff:
print("[+]"，fff)
break
sh.close()
babyrsa
论问题，一开始以为是用的虎符这篇：《Cryptanalysis of RSA Variants with Primes Sharing Most Signi cant Bits》
调了半天发现界不满足
后来找到这一篇:《A new attack on some RSA variants》
不过用的格子还是和虎符这篇一样，只是改了一下式子，
论文还贴心的给出了样例，和题目的参数几乎一致，用了一下虎符的板子 ，把样例跑通了，然后直接拿题目数据，梭了就好了。
# https://github.com/1umi3re/my_ctf_challenge/blob/main/hfctf_2022/RRSSAA/exp.py
from gmpy2 import next_prime， iroot
from Crypto.Util.number import getPrime， inverse， GCD， bytes_to_long， long_to_bytes
from sage.all import *
def attack2(N， e， m， t， X， Y):
PR = PolynomialRing(QQ， 'x，y'， 2， order='lex')
x， y = PR.gens()
v0 = int(851033777767430284858630579937210957794466604656176459982282)
a1 = int(v0*pow(2，1-2*r，e) % e)
a2 = int(-((N+1)^2-v0^2)*pow(2，-4*r，e) % e)
a3 = int(-pow(2，-4*r，e) % e)
F = x*y^2+a1*x*y+a2*x+a3
G_polys = []
# G_{k，i_1，i_2}(x，y) = x^{i_1-k}y_{i_2-2k}f(x，y)^{k}e^{m-k}
for k in range(m + 1):
for i_1 in range(k， m+1):
for i_2 in [2*k， 2*k + 1]:
G_polys.append(x**(i_1-k) * y**(i_2-2*k) * F**k * e**(m-k))
H_polys = []
# y_shift H_{k，i_1，i_2}(x，y) = y^{i_2-2k} f(x，y)^k e^{m-k}
for k in range(m + 1):
for i_2 in range(2*k+2， 2*k+t+1):
H_polys.append(y**(i_2-2*k) * F**k * e**(m-k))
polys = G_polys + H_polys
monomials = []
for poly in polys:
monomials.append(poly.lm())
dims1 = len(polys)
dims2 = len(monomials)
MM = matrix(QQ， dims1， dims2)
for idx， poly in enumerate(polys):
for idx_， monomial in enumerate(monomials):
if monomial in poly.monomials():
MM[idx， idx_] = poly.monomial_coefficient(monomial) * monomial(X， Y)
B = MM.LLL()
found_polynomials = False
for pol1_idx in range(B.nrows()):
for pol2_idx in range(pol1_idx + 1， B.nrows()):
P = PolynomialRing(QQ， 'a，b'， 2)
a， b = P.gens()
pol1 = pol2 = 0
for idx_， monomial in enumerate(monomials):
pol1 += monomial(a，b) * B[pol1_idx， idx_] / monomial(X， Y)
pol2 += monomial(a，b) * B[pol2_idx， idx_] / monomial(X， Y)
# resultant
rr = pol1.resultant(pol2)
# are these good polynomials?
if rr.is_zero() or rr.monomials() == [1]:
continue
else:
print(f"found them， using vectors {pol1_idx}， {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...")
PRq = PolynomialRing(QQ， 'z')
z = PRq.gen()
rr = rr(z， z)
soly = rr.roots()[0][0]
ppol = pol1(z， soly)
solx = ppol.roots()[0][0]
return solx， soly
n=5527823687914629445928751931351501568538008375615524908427389726990389715275837002861651510701228393924757035291457877675111540404203012135378834487753490236754111855821567310395547714573242118176027909363197756783356599319622032729503900145504768199117956830109488213721179197298976559379295734300889
e=16021660724557845861903926629189678508104614030647584377887691761323265228729978577912718772018351305060755997181165548896287262237118067747095895135689542315518542722282213749507552545174880598816723954290814011885379391990414696263834518312117922281210824958741501122210535644121406075221738197619232462600078762156908163867986801571665710762394459236886966450990535704563963180305912668319246133004743587146218547017334946743812609663005378905656444984371409043041484148339572240945472316645060906808117473860228212000852669342881620738498172046794549032176677232076775574888980921634064269760730733
#c = Complex(re=2012948531808535658618135982376157338497630873224229514232396588630318374103303632458672435554153057032250931230752901501660055660862099702318326352000431226866382254438987809465982480745411398406968025077723685872358629823751506867202963276004837767911659230345188497115504371022168504350112757911970， im=381189254885346479441224149330737027827963006108977158894650476797604540263935003393925783161307886586032523860105464648325293157866129992025717767014563299764845263099980532235028862005360622884509996726485571556604386339566439967304706464942491349381908685406278617323955301845117990230102559034276)
a=1.997
d=0.7
b=0.1
X = int(2*n^(a+d-2))
Y = int(3*n^(1/2-2*b))
v = attack2(n， e， 4， 4， X， Y)[1]
v = int(v)
r = 100
nn = Mod(n，2^r)
u0 = nn.nth_root(2，all=True)[0]
u0 = int(u0)
v0 = 2*u0+(n-u0^2)*inverse(u0，4^r) % 4^r
pq = int(2^(2*r)*v+v0)
ppq = isqrt(pq^2-4*n)
p = (pq+ppq)//2
q = n//p
p = 1900012498118758080386063557941332201661823681127196909513390375685272680057296393801682140714541517469250351359374711900794251164879414119839995155173
q = 2909361750718925654806263886008919952754040081505772293312305999147201945140177280651101936712818375809233132556289477012051690455667963261726156542693
from Crypto.Util.number import isPrime， inverse， bytes_to_long
from random import getrandbits， randrange
from collections import namedtuple
Complex = namedtuple("Complex"， ["re"， "im"])
def complex_mult(c1， c2， modulus):
return Complex(
(c1.re * c2.re - c1.im * c2.im) % modulus，
(c1.re * c2.im + c1.im * c2.re) % modulus，
)
def complex_pow(c， exp， modulus):
result = Complex(1， 0)
while exp > 0:
if exp & 1:
result = complex_mult(result， c， modulus)
c = complex_mult(c， c， modulus)
exp >>= 1
return result
def rand_prime(nbits， kbits， share):
while True:
p = (getrandbits(nbits) << kbits) + share
if p % 4 == 3 and isPrime(p):
return p
def gen():
while True:
k = getrandbits(100)
pp = getrandbits(400) << 100
qq = getrandbits(400) << 100
p = pp + k
q = qq + k
if isPrime(p) and isPrime(q):
break
if q > p:
p， q = q， p
n = p * q
lb = int(n ** 0.675)
ub = int(n ** 0.70)
d = randrange(lb， ub)
e = inverse(d， (p * p - 1) * (q * q - 1))
sk = (p， q， d)
pk = (n， e)
return pk， sk
from Crypto.Util.number import *
n=5527823687914629445928751931351501568538008375615524908427389726990389715275837002861651510701228393924757035291457877675111540404203012135378834487753490236754111855821567310395547714573242118176027909363197756783356599319622032729503900145504768199117956830109488213721179197298976559379295734300889
e=16021660724557845861903926629189678508104614030647584377887691761323265228729978577912718772018351305060755997181165548896287262237118067747095895135689542315518542722282213749507552545174880598816723954290814011885379391990414696263834518312117922281210824958741501122210535644121406075221738197619232462600078762156908163867986801571665710762394459236886966450990535704563963180305912668319246133004743587146218547017334946743812609663005378905656444984371409043041484148339572240945472316645060906808117473860228212000852669342881620738498172046794549032176677232076775574888980921634064269760730733
c = Complex(re=2012948531808535658618135982376157338497630873224229514232396588630318374103303632458672435554153057032250931230752901501660055660862099702318326352000431226866382254438987809465982480745411398406968025077723685872358629823751506867202963276004837767911659230345188497115504371022168504350112757911970， im=381189254885346479441224149330737027827963006108977158894650476797604540263935003393925783161307886586032523860105464648325293157866129992025717767014563299764845263099980532235028862005360622884509996726485571556604386339566439967304706464942491349381908685406278617323955301845117990230102559034276)
p = 1900012498118758080386063557941332201661823681127196909513390375685272680057296393801682140714541517469250351359374711900794251164879414119839995155173
q = 2909361750718925654806263886008919952754040081505772293312305999147201945140177280651101936712818375809233132556289477012051690455667963261726156542693
d = inverse(e， (p * p - 1) * (q * q - 1))
m = complex_pow(c， d， n)
print(m)
print(long_to_bytes(2284117282070580319467503526716887419216540004))
print(long_to_bytes(1119861848972936994707380976950224397710735485))
Complex(re=2284117282070580319467503526716887419216540004， im=1119861848972936994707380976950224397710735485)
b'flag{62b1a28d70e11d'
b'27b1cb1e2102b7e858}'
1515
论文题，2023 美密 《Finding short integer solutions when the modulus is small》
这回论文更加贴心的给了攻击实现: https://github.com/verdiverdiverdi/ISIS-small-q
改一下 q， 开盖即食（因为 q 变大了，得调一下参，把beta_BKZ 和 beta_sieve 调大，随便乱调的，越大，越好，但是越慢，嗯，应该是这样，我也不懂）
另外，题目没有给出的 m，n，q，v 都是可以测出的 m，n 看给出的矩阵维度就好，q 的话，多连接几次，发现出现的最大的数是 276，那 q 八九不离十就是 277了，刚好也是个素数。v 的话直接解线性方程组，前面加256个0，传过去，就会失败，但是能够知道 v 是1510
from fpylll import BKZ， GSO， IntegerMatrix， LLL
from fpylll.algorithms.bkz2 import BKZReduction as BKZ2
from sage.all import IntegerModRing， ZZ， matrix， identity_matrix，
random_matrix， random_vector， vector
from g6k import Siever
from numpy import array， zeros
from numpy.linalg import norm
import sys
# mitaka n512q257
n = 512
m_ = 1024
m = m_ + 1
q = 277
nu = 1510
Zq = IntegerModRing(q)
# get data
from hashlib import sha256
from pwn import *
# context.log_level = 'debug'
sh = remote("47.104.147.171"，"1515")
r1 = int(sh.recvuntil(" ")[:-1])
hash = (sh.recvuntil("n")[:-1])
for i in range(2**22):
if sha256(str(i*r1).encode()).hexdigest().encode() == hash:
sh.sendline(str(i))
break
data = sh.recvuntil("ers: ").split(b"n")[:-1]
u = eval(data[-1])
import re
A0 = []
for each in data[-513:-1]:
new = []
each = data[-513]
each = each.decode()
each = each.replace("Give me r0: "，"").replace("]"，"").replace("["，"")
each = each.split(" ")
for _ in each:
if _ != "":
new.append(int(_))
A0.append(new)
A0 = matrix(Zq，A0)
# ISIS matrix
Id = identity_matrix
# keeping the ``raw`` ISIS matrix to check everything at the end
AISIS = matrix.block(Zq， [[identity_matrix(ZZ， n)]， [A0]]) # % q
# uniform ISIS target
u = matrix(Zq，u)
# SIS* matrix
Au0 = matrix.block(Zq， [[matrix(u)]， [A0]]) # % q
Afull = matrix.block(Zq， [[identity_matrix(ZZ， n)]， [Au0]]) # % q
# keeping a numpy version of Afull makes life easier later
A_np = array(Afull.lift())
print("SIS* instance built")
# basis of the SIS* kernel lattice
B = matrix.block(ZZ， [[q*Id(n)， 0]， [-Au0， Id(m-n)]])
print("Full basis built")
"""
The basis B that has been built is the kernel for the SIS* matrix (columns)
A' = (Id || u || A0) in ZZ_q^(n x (n + 1 + n))
= (Id || Au0)
where u is the uniform ISIS target vector and A0 is uniform in ZZ_q^(n x n).
We rewrite this as
A' = (A_1' A_2') = (Id || Au0)
The basis， in ~row~ notation， is
[q I_n 0 ]
[ U I_(n+1) ]
where U = - (A_1')^-1 A_2' = -Au0
"""
# take a 2z dimensional block， with volume q^z
# i.e. symmetric around the centre of the basis
z1 = 80
z2 = 80
d = z1+z2
"""
Note that because of the form of the basis， the basis of the
projected sublattice we are concerned with can be directly
taken from the full basis as below.
First we project against some number k of q vectors to take
[q I_n 0 ]
[ U I_(n+1) ]
to
[0 0 0 ]
[0 q I_(n - k) 0 ]
[0 U[k:n] I_(n+1) ]
where U[k:n] is the kth to the (n-1)th columns of U.
Then we simply do not include the final k row vectors.
"""
B_ = matrix(B)[n-z1:n+z2， n-z1:n+z2]
beta_BKZ = 32
beta_sieve = 77
def complete_solution(v):
# this lifts and reduces a vector from the projected sublattice sieve
x = zeros(m， dtype="int32")
x[n-z1:n+z2] = v
y = (x.dot(A_np))[:n-z1] % q
y -= q * (y > q/2)
x[:n-z1] = -y
return x
print("Partial basis built")
C = B_.LLL()
print("Partial Basis LLL reduced")
X = IntegerMatrix.from_matrix(C)
M = GSO.Mat(X， float_type="ld"， U=IntegerMatrix.identity(d)，
UinvT=IntegerMatrix.identity(d))
lll = LLL.Reduction(M)
bkz = BKZ2(lll)
g6k = Siever(M)
for bs in range(5， beta_BKZ+1):
param = BKZ.Param(block_size=bs， max_loops=1， auto_abort=True)
print("rBKZ-%d / %d ... " % (bs， beta_BKZ)， end="")
bkz(param)
bkz.lll_obj()
sys.stdout.flush()
print("BKZ profile :")
for x in bkz.M.r():
print("%.3f" % (x**.5)， end=" ")
print
g6k.initialize_local(0， beta_sieve-20， beta_sieve)
g6k(alg="gauss")
while g6k.l > 0:
g6k.extend_left()
g6k(alg="gauss" if g6k.n < 50 else "hk3")
print("r Sieve-%d / %d ... " % (g6k.n， beta_sieve)， end="")
sys.stdout.flush()
with g6k.temp_params(saturation_ratio=.9):
g6k(alg="gauss" if g6k.n < 50 else "hk3")
print("n Sieving Done")
norms = []
X_ = array(matrix(X))[:beta_sieve]
print(X_.shape)
trials = 0
FailZ， FailC， FailN = 0， 0， 0
for vec in g6k.itervalues():
trials += 1
v = array(vec)
x = v.dot(X_)
if (x % q == 0).all():
# trivial vector: all mod q
FailZ += 1
continue
if abs(x[z1]) != 1:
# we do not recieve +/-1 in the first position， we we cannot
# solve ISIS for u
FailC += 1
continue
lx = norm(array(x))
y = complete_solution(x)
ly = norm(y)
if ly < nu:
break
# the norm of the solution is too long
FailN += 1
print("Failures: nt %d lifts were 0 mod q，nt %d lifts didn't had the coeff +/- 1，nt %d lifts were too long" % (FailZ， FailC， FailN)) # noqa
if trials == g6k.db_size():
print("FAILED: All candidates lifted. No solution found")
exit()
# Reconstructing ISIS solution from SIS* solution
f = - y[n]
x = vector(ZZ， list(f * y[:n])+list(f * y[n+1:]))
# Checking it all
assert (x * AISIS == u)
assert (x.norm().n() < nu)
# Claiming victory
print("SUCCESS: ISIS solved after %d lifts， out of %d candidates !" % (trials， g6k.db_size())) # noqa
print("Solution Norm:"， x.norm().n()， " < "， nu)
print("solution :"， x)
sh.sendline(str(list(x)))
print(sh.recv())
相关附件和论文放网盘里头了。
链接：https://pan.baidu.com/s/14AnBEHfkkDZ1ZSj56F2z4w?pwd=p2he
提取码：p2he
原文始发于微信公众号（Van1sh）：2023 强网杯 初赛
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论