Categories
Tags
1521 words
8 minutes
2024 强网杯
刚学了两三个月的密码,就遇到了强网杯,倾尽全力只做出一道题,标*的都是赛后复现的
EasyRSA
题面:
#encoding:utf-8
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime
import random, gmpy2
class RSAEncryptor:
def __init__(self):
self.g = self.a = self.b = 0
self.e = 65537
self.factorGen()
self.product()
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
def encrypt(self, msg):
return gmpy2.powmod(msg, self.e, self.N)
def product(self):
with open('/flag', 'rb') as f:
self.flag = f.read()
self.enc = self.encrypt(self.flag)
self.show()
print(f'enc={self.enc}')
def show(self):
print(f"N={self.N}")
print(f"e={self.e}")
print(f"g={self.g}")
RSAEncryptor()
分析:
参考:Common Prime RSA 笔记 | 独奏の小屋
由上述算法生成的素数 p,q满足是一个大素数因子,故称 p,q为公素数(Common primes)
其中g为这两个素数的公因子(Common factor)
我们需要注意到对于公素数RSA有以下性质:
此外存在额外定义,RSA加密指数和解密指数需要与互素
根据以上定义,可以推导出:
定义表示共因子g的相对于N的大小,即。考虑
对于本题来说,已知g
至于算法部分的证明如下:
于是照着板子打
题解:
from Crypto.Util.number import *
from sage.groups.generic import bsgs
N=18609249586511447022929188601029606630816796460795187470065452150283160549624372398383148374249992521068549349516037511009027303530058706112191091689108542770802393390942693648814845389265858611340109158309645284100825624911741650444467173946569096983438455034895955228543351436008546035535031019474847660151534447157873386841134028651786166708821300066332734338450150803713659027324704224480646285707278634645234095122804559045312923819794776928194098487972764363649361713512731460059740929840789043447155551107435766468071813945331313861835289050624825980714650042186547867057986370794200778277570803957071502251887
e=65537
g=2157382166227048008151606160068683153029902706798753603550075684775242674106840467207794609506075603345430902709796320595040305496549488048759451499003
enc=1706676139782916859705617140716929473350550599143215409850324617375385155893376548401557158261122335220199922229225746433590875391358929714141838314015655361989993985070285957305126847445442699828095001203266978036575956723172054402632901673504599481917025056824986547174258708944098866240451432510310007060414500907941107101001004474036283249456230343043785187819423163986135104740039129111213967847515011092231384245986891933365405336421413444499204268699546739391271911481490278065027465465222639265899471823742196086481403499948301061349936225773314002398442541447810628796808530412232638250097430811300924120316
gamma = 500/(1024*2)
cbits = ceil((1024*2)*(0.5-2*gamma))
M = (N-1)//(2*g)
u = M//(2*g)
v = M - 2*g*u
GF = Zmod(N)
x = GF.random_element()
y = x^(2*g)
# c的范围大概与N^(0.5-2*gamma)很接近
c = bsgs(y , y^u , (2**(cbits-1),2**(cbits+1)),operation = '*')
# (a,b,bounds,operation,identity=None,inverse=None,op=None)
ab = u-c
apb = v + 2*g*c
PR.<x> = ZZ[]
f = x^2 - apb*x + ab
a = f.roots()
if a:
a,b = a[0][0],a[1][0]
p = 2*g*a+1
q = 2*g*b+1
print(long_to_bytes(int(pow(enc,inverse(e,(p-1)*(q-1)),N))))
apbq
题面:
from Crypto.Util.number import *
from secrets import flag
from math import ceil
import sys
class RSA():
def __init__(self, privatekey, publickey):
self.p, self.q, self.d = privatekey
self.n, self.e = publickey
def encrypt(self, plaintext):
if isinstance(plaintext, bytes):
plaintext = bytes_to_long(plaintext)
ciphertext = pow(plaintext, self.e, self.n)
return ciphertext
def decrypt(self, ciphertext):
if isinstance(ciphertext, bytes):
ciphertext = bytes_to_long(ciphertext)
plaintext = pow(ciphertext, self.d, self.n)
return plaintext
def get_keypair(nbits, e = 65537):
p = getPrime(nbits//2)
q = getPrime(nbits//2)
n = p * q
d = inverse(e, n - p - q + 1)
return (p, q, d), (n, e)
if __name__ == '__main__':
pt = './output.txt'
fout = open(pt, 'w')
sys.stdout = fout
block_size = ceil(len(flag)/3)
flag = [flag[i:i+block_size] for i in range(0, len(flag), block_size)]
e = 65537
print(f'[+] Welcome to my apbq game')
# stage 1
print(f'┃ stage 1: p + q')
prikey1, pubkey1 = get_keypair(1024)
RSA1 = RSA(prikey1, pubkey1)
enc1 = RSA1.encrypt(flag[0])
print(f'┃ hints = {prikey1[0] + prikey1[1]}')
print(f'┃ public key = {pubkey1}')
print(f'┃ enc1 = {enc1}')
print(f'----------------------')
# stage 2
print(f'┃ stage 2: ai*p + bi*q')
prikey2, pubkey2 = get_keypair(1024)
RSA2 = RSA(prikey2, pubkey2)
enc2 = RSA2.encrypt(flag[1])
kbits = 180
a = [getRandomNBitInteger(kbits) for i in range(100)]
b = [getRandomNBitInteger(kbits) for i in range(100)]
c = [a[i]*prikey2[0] + b[i]*prikey2[1] for i in range(100)]
print(f'┃ hints = {c}')
print(f'┃ public key = {pubkey2}')
print(f'┃ enc2 = {enc2}')
print(f'----------------------')
# stage 3
print(f'┃ stage 3: a*p + q, p + bq')
prikey3, pubkey3 = get_keypair(1024)
RSA3 = RSA(prikey3, pubkey3)
enc3 = RSA2.encrypt(flag[2])
kbits = 512
a = getRandomNBitInteger(kbits)
b = getRandomNBitInteger(kbits)
c1 = a*prikey3[0] + prikey3[1]
c2 = prikey3[0] + b*prikey3[1]
print(f'┃ hints = {c1, c2}')
print(f'┃ public key = {pubkey3}')
print(f'┃ enc3 = {enc3}')
分析:
stage1
给了 ,联立解出p,q即可
stage2
给了100组的,其中p,q都是512bit的,而则显得比较小,仅有180bit
这样的小量存在,会想到造格,为了使目标向量较短,所以当然要去消去p,q才行,因此固定前两组数据,将3~100组数据和前两组数据消元即可得到仅有的等式:
显然作为系数的只有360bit,是小量,把数据放入格中就可以规约出来了
之后的问题是如何由规约出的这些和差来求出所有的a,b来,这一部分参考maple神的做法:DownUnderCTF 2023 Writeups | 廢文集中區
大致思路是把这三个等式做groebner_basis,由于等式不够,所以肯定不能得到a,b的值,但是却可以得到a,b的线性等式,因此可以再做一次LLL后gcd出来
构造出的格子:
也是get到了一个新的工具flatter用来LLL
stage3
给定了 ,其中a,b和p,q均为512bit的数字,我的第一反应是ACD问题,一直没有做出来,后来看了别人的题解才知道
应该是
题解:
from Crypto.Util.number import *
#from gmpy2 import *
from z3 import *
# stage 1
hints1 = 18978581186415161964839647137704633944599150543420658500585655372831779670338724440572792208984183863860898382564328183868786589851370156024615630835636170
n,e = (89839084450618055007900277736741312641844770591346432583302975236097465068572445589385798822593889266430563039645335037061240101688433078717811590377686465973797658355984717210228739793741484666628342039127345855467748247485016133560729063901396973783754780048949709195334690395217112330585431653872523325589, 65537)
c = 23664702267463524872340419776983638860234156620934868573173546937679196743146691156369928738109129704387312263842088573122121751421709842579634121187349747424486233111885687289480494785285701709040663052248336541918235910988178207506008430080621354232140617853327942136965075461701008744432418773880574136247
p,q = Int('p'), Int('q')
sol = Solver()
sol.add(p+q == hints1)
sol.add(p*q == n)
if sol.check() == sat:
m = sol.model()
p = m[p].as_long()
q = m[q].as_long()
d = inverse(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))
# stage 2
from re import findall
from subprocess import check_output
from itertools import *
def flatter(M):
z = "[[" + "]\n[".join(" ".join(map(str, x)) for x in M) + "]]"
ret = check_output(["flatter"],input=z.encode())
return matrix(M.nrows(),M.ncols(),map(int,findall(b"-?\\d+",ret)))
hints = ...
n,e = (73566307488763122580179867626252642940955298748752818919017828624963832700766915409125057515624347299603944790342215380220728964393071261454143348878369192979087090394858108255421841966688982884778999786076287493231499536762158941790933738200959195185310223268630105090119593363464568858268074382723204344819, 65537)
enc2 = 30332590230153809507216298771130058954523332140754441956121305005101434036857592445870499808003492282406658682811671092885592290410570348283122359319554197485624784590315564056341976355615543224373344781813890901916269854242660708815123152440620383035798542275833361820196294814385622613621016771854846491244
h = hints
nums = 100-2
L = Matrix(ZZ,1+nums*2,1+nums*3)
for i in range(1+nums*2):
L[i,i] = 1
for i in range(nums):
L[0,1+nums*2+i] = h[i+2]
L[2*i+1,1+nums*2+i] = h[0]
L[2*i+2,1+nums*2+i] = h[1]
L[:,-nums:] *= 2^512
L = flatter(L)
v,t,u = L[0,0],L[0,1],L[0,2]
a1s, a2s, a3s, b1s, b2s, b3s = QQ["a1,a2,a3,b1,b2,b3"].gens()
for sign in product((-1, 1), repeat=3):
I = ideal(
[
a3s * b2s - a2s * b3s + sign[0] * t,
a3s * b1s - a1s * b3s + sign[1] * u,
a2s * b1s - a1s * b2s + sign[2] * v,
]
)
if I.dimension() != -1:
print(sign)
print("dim", I.dimension())
def step2(f):
# this f is in the form of k1*a1+k2*a2+k3*a3==0
# for some reason, k1*b1+k2*b2+k3*b3==0 also holds
# use LLL to find it
print("=" * 40)
print(f)
L = matrix(f.coefficients()).T.augment(matrix.identity(3))
L[:, 0] *= n
L = L.LLL()
print(L[0])
print(L[1])
v1 = L[0]
v2 = L[1]
xs = []
for c1, c2 in product((-2, -1, 0, 1, 2), repeat=2):
v = c1 * v1 + c2 * v2
_, x1, x2, x3 = v
if all([0 <= x <= 2**180 for x in (x1, x2, x3)]):
xs.append((x1, x2, x3))
# we don't know which one is correct pair of (a1, a2, a3) and (b1, b2, b3)
# just try all combinations
for g1, g2 in combinations(xs, 2):
a1r, a2r, a3r = g1
b1r, b2r, b3r = g2
q = gcd(a2r * h[0] - a1r * h[1], n)
if 1 < q < n:
p = n // q
e = 0x10001
d = inverse_mod(e, (p - 1) * (q - 1))
m = pow(enc2, d, n)
flag = int(m).to_bytes(1024, "big").strip(b"\x00")
print(flag)
break
step2(I.groebner_basis()[1])
# stage 3
c1,c2 = (68510878638370415044742935889020774276546916983689799210290582093686515377232591362560941306242501220803210859757512468762736941602749345887425082831572206675493389611203432014126644550502117937044804472954180498370676609819898980996282130652627551615825721459553747074503843556784456297882411861526590080037, 117882651978564762717266768251008799169262849451887398128580060795377656792158234083843539818050019451797822782621312362313232759168181582387488893534974006037142066091872636582259199644094998729866484138566711846974126209431468102938252566414322631620261045488855395390985797791782549179665864885691057222752)
n,e = (94789409892878223843496496113047481402435455468813255092840207010463661854593919772268992045955100688692872116996741724352837555794276141314552518390800907711192442516993891316013640874154318671978150702691578926912235318405120588096104222702992868492960182477857526176600665556671704106974346372234964363581, 65537)
enc3 = 17737974772490835017139672507261082238806983528533357501033270577311227414618940490226102450232473366793815933753927943027643033829459416623683596533955075569578787574561297243060958714055785089716571943663350360324047532058597960949979894090400134473940587235634842078030727691627400903239810993936770281755
brute = 2
for i in range(2^brute):
for j in range(2^brute):
L = Matrix(ZZ,[
[1,0,0,2^brute*c1],
[0,1,0,2^brute*c2],
[0,0,2^(512-brute),c1*i+c2*j-c1*c2],
[0,0,0,n]
])
L[:,-1:] *= n
res = L.LLL()[0]
p = 2^brute * abs(res[0]) + i
if (n % p == 0):
print("p:", p)