2024 强网杯 - A1ic3's Blog

2024 强网杯

2024-11-07

刚学了两三个月的密码，就遇到了强网杯，倾尽全力只做出一道题，标*的都是赛后复现的

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()

分析：#

h=2gab+a+b\\ N=2hg+1=2g(2gab+a+b)+1=(2ga+1)(2gb+1)\\ p = 2ga+1\\ q = 2gb+1\\

参考：Common Prime RSA 笔记 | 独奏の小屋

由上述算法生成的素数 p,q满足 $g=gcd(p-1,q-1)$ 是一个大素数因子，故称 p,q为公素数(Common primes)

其中g为这两个素数的公因子(Common factor)

我们需要注意到对于公素数RSA有以下性质：

\lambda(pq)=lcm(p-1,q-1)=lcm(2ga,2gb)=2gab\\ \phi(pq)=(p-1)(q-1)=2ga*2gb=2g\lambda(pq)

此外存在额外定义，RSA加密指数和解密指数需要与 $\lambda(pq)$ 互素

根据以上定义，可以推导出：

N=pq=(2ga+1)(2gb+1)=2g(2gab+a+b)+1=2gh+1\\ 即N-1为：\\ N-1=2g(2gab+a+b)=2gh

定义 $\gamma$ 表示共因子g的相对于N的大小，即 $g=N^{\gamma}$ 。考虑 $g\leq N^{\frac{1}{2}},故0\leq \gamma \leq \frac{1}{2}$

对于本题来说，已知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#

给了 $hint=p+q$ ，联立解出p，q即可

stage2#

给了100组的 $a_ip+b_iq$ ，其中p，q都是512bit的，而 $a_i,b_i$ 则显得比较小，仅有180bit

这样的小量存在，会想到造格，为了使目标向量较短，所以当然要去消去p,q才行，因此固定前两组数据，将3~100组数据和前两组数据消元即可得到仅有 $a_1,a_2,a_i,b_1,b_2,b_i$ 的等式：

(a_ib_2-a_2b_i)h_1+(a_1b_i-a_ib_1)h_2+(a_2b_1+a_1b_2)h_i=0

显然作为系数的 $a_jb_k\pm a_kb_j$ 只有360bit，是小量，把数据放入格中就可以规约出来了

之后的问题是如何由规约出的这些和差来求出所有的a,b来，这一部分参考maple神的做法：DownUnderCTF 2023 Writeups | 廢文集中區

大致思路是把这三个等式做groebner_basis，由于等式不够，所以肯定不能得到a，b的值，但是却可以得到a，b的线性等式，因此可以再做一次LLL后gcd出来

构造出的格子：

\begin{bmatrix} &1&&&&&&&h_3&h_4\dots h_n\\ &&1&&&&&&h_1\\ &&&1&&&&&h_2\\ &&&&1&&&&&h_1\\ &&&&&1&&&&h_2\\ &&&&&&\ddots&&&&\ddots\\ &&&&&&&1 \end{bmatrix}

也是get到了一个新的工具flatter用来LLL

stage3#

给定了 $c_1=ap+q\\c_2=p+bq$ ，其中a,b和p,q均为512bit的数字，我的第一反应是ACD问题，一直没有做出来，后来看了别人的题解才知道

应该是

(c_1-q)(c_2-p)=0\ \ (mod\ n)\\ 展开后可以发现，p、q的乘积又被消掉了，所以整个式子其实是线性的：\\ c_1c_2-c_1p-c_2q=0\ \ (mod\ n)\\ 这个等式中，两个未知量p、q仅有模数n的一半bit而已，很接近LLL可以规约出的范围，小范围爆破一下：\\ c_1c_2-c_1(2^2p_h+i)-c_2(2^2q_h+j)=0\ \ (mod\ n)\\ 然后LLL就可以找到p、q了

题解：#

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)