2022-11-08   14 m   2.2 k0 visits

N1CTF2022 Crypto赛题复现

题目非常好，总共只有三道题，比赛时都卡在不同的地方没解出来。赛后看了一些大佬的思路尝试进行了复现，这里把复现的过程做一下记录和总结。

brand_new_checkin

从题目描述可以知道改题是基于[CakeCTF2022]brand_new_crypto的改编。题目源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
from Crypto.Util.number import *
from random import getrandbits
from secret import flag

def keygen():
    p = getPrime(512)
    q = getPrime(512)

    n = p * q
    phi = (p-1)*(q-1)

    while True:
        a = getrandbits(1024)
        b = phi + 1 - a

        s = getrandbits(1024)
        t = -s*a * inverse(b, phi) % phi

        if GCD(b, phi) == 1:
            break
    return (s, t, n), (a, b, n)


def enc(m, k):
    s, t, n = k
    r = getrandbits(1024)

    return m * pow(r, s, n) % n, m * pow(r, t, n) % n


pubkey, privkey = keygen()

flag = pow(bytes_to_long(flag), 0x10001, pubkey[2])

c = []
for m in long_to_bytes(flag):
    c1, c2 = enc(m, pubkey)
    c.append((c1, c2))

print(pubkey)
print(c)

与原题的区别在于，在原题加密方式的前面，多了一层rsa的加密。

首先肯定得拿到rsa加密的密文。我们观察到程序中是逐字节进行的enc操作，那么这为我们按字节逐个爆破提供了可能。那么怎么去爆破呢？（其实这一部分在网上已经有题解了，有多种做法）

根据题目有： (s, t)是公钥，(a, b)是私钥。由于产生密文时，r是随机数未知的，因此考虑消去r的影响。做如下计算： 因此爆破单字节m的256种可能情况去验证该等式即可。然后就能拿到rsa的密文。

然而题目似乎没有给出更多有用的能够去分解n的信息，a和b也不能求出来。到这里我当时的思路就没有了。进行了一些尝试，可以求出每次r的值，但好像也无济于事。

赛后看别人的思路一瞬间就懂了，我是真滴眼瞎，这么多个getrandbits我没注意到，这不是妥妥的mt19937随机数预测吗。再扫一眼题目，r是1024bits可以计算，且足够多，那就确认无疑了。

然后是关于r的计算。这里由于s和t是互质的，我们可以通过扩展欧几里得算法计算出使得的A和B。然后做如下计算： 因此我们可以拿到计算每一个字节m所使用的r。为了进行预测，我们需要个r的值，然而实际计算出的数量远比这个多，已经足够了，取前20个即可。

复现时发现这里还有一个比较坑的点，这里的r是模n下计算出来的，而实际r产生时虽然与n一样是1024bits，但和n没有任何关系，也就是说r是可能大于n的。因此这里算出的r有小概率不是准确值，对于每个r需要在1024bits范围内进行小规模的枚举爆破。

然后本题的随机数预测是一个后向的，用到的是ExtendMT19937Predictor。可以通过s来进行验证预测是否正确，然后得到a的值。然后能计算出一个phi的倍数： 用求私钥d，解rsa即可得到flag。

复现解题脚本如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
from Crypto.Util.number import *
from gmpy2 import gcdext
from extend_mt19937_predictor import ExtendMT19937Predictor
from itertools import product
from tqdm import tqdm

def my_pow(m,e,n):
    if e<0:
        return inverse(pow(m,-e,n),n)%n
    else:
        return pow(m,e,n)

lines=open('output.txt','r').readlines()
s,t,n=eval(lines[0])
c=eval(lines[1])
g,A,B=gcdext(s,t)

encflag=[]

for c1,c2 in c:
    tmp=pow(c1,t,n)*inverse(pow(c2,s,n),n)%n
    for m in range(256):
        if my_pow(m,t-s,n)==tmp:
            encflag.append(m)
            break
encflag=bytes_to_long(bytes(encflag))
print(encflag)
#5808031027043628162680151939451046896318461702606899637261519628597633638670331617408988305725962951563713997335461555788456061664507614271209312052190146070886646800923406401095648933383421520598567936442062181397887455263188256755970400658783406029792373329955006020555525415893643918145187677700370550761

encflag=5808031027043628162680151939451046896318461702606899637261519628597633638670331617408988305725962951563713997335461555788456061664507614271209312052190146070886646800923406401095648933383421520598567936442062181397887455263188256755970400658783406029792373329955006020555525415893643918145187677700370550761
mlist=list(long_to_bytes(encflag))
possible_rlist=[]
for m,cc in zip(mlist,c):
    c1,c2=cc
    tmpr=int(my_pow(c1,A,n)*my_pow(c2,B,n)*inverse(my_pow(m,A+B,n),n)%n)
    assert c1==m*pow(tmpr,s,n)%n
    assert c2==m*pow(tmpr,t,n)%n
    if tmpr==0:
        break
    tmprlist=[]
    while tmpr.bit_length()<=1024:
        tmprlist.append(tmpr)
        tmpr+=n
    possible_rlist.append(tmprlist)

#624/(1024/32)=19.5
possible_rlist=possible_rlist[:20]
for rlist in tqdm(product(*possible_rlist)):
    predictor=ExtendMT19937Predictor()
    #624=19*(1024/32)+(512/32)
    for i in range(19):
        predictor.setrandbits(rlist[i],1024)
    predictor.setrandbits(rlist[19]&(2**512-1),512)
    for i in range(624):
        predictor.backtrack_getrandbits(32)
    guess_s=predictor.backtrack_getrandbits(1024)
    
    if guess_s==s:
        a=predictor.backtrack_getrandbits(1024)
        k_phi=s*a+t*(1-a)
        d=inverse(0x10001,k_phi)
        flag=long_to_bytes(pow(encflag,d,n))
        print(flag)
        exit(0)
#b'n1ctf{5255840f-9140-4479-950f-a3c03fe7f4cd}'

ezdlp

题目源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *
from math import prod
from secret import flag

def keygen(pbits,kbits,k):
    p = getPrime(pbits)
    x = [getPrime(kbits + 1) for i in range(k)]
    y = prod(x)
    while 1:
        r = getPrime(pbits - kbits * k)
        q = 2 * y * r + 1
        if isPrime(q):
            return p*q, (p, q, r, x)

def encrypt(key, message):
    return pow(0x10001, message, key)

key = keygen(512, 24, 20)
flag = bytes_to_long(flag)
messages = [getPrime(flag.bit_length()) for i in range(47)] + [flag]
enc = [encrypt(key[0], message) for message in messages]

print(messages[:-1])
print(enc)

可以观察到q-1是光滑数，然而题目并没有给出的值，需要先从47组(m, c)中求出n。由于模数n未知，无法直接做模幂运算，也不能直接对一个大数求幂。因此需要用间接法构造出具有因子n的式子。

我们先看最简单的情况，假设有, , 如果与非常接近（假设）, 那么就有, 也即是。通过构造一个比较小的差值来避免了大指数的幂运算。

借用以上思路，回到本题中，我们可以考虑m的线性组合，使t为一个比较小的值，且系数也比较小，从而便于我们计算。这种形式就很熟悉了，可以转化为一个格中的最短向量问题来求解。因此，可以构造如下格矩阵： 通过格基规约，我们可以得到一组短向量，通过观察发现规约出的这一组向量都能用于计算。但注意向量中会有负数出现，由于没有n无法求模逆，需要将正数和负数分开计算。然后每一个向量都能求出一个, 求gcd即可得到n的值。

求出n之后就比较好办了，由于q-1光滑，可以使用Pollard's p-1 方法对n进行分解。然后使用Pohlig-Hellman算法来求解dlp。

在实际操作时，gcd求出的n会带有一些小素数因子，需要先除掉这些因子得到应该是1034bits的n。然后，在使用Pollard's p-1 分解n时，可以直接使用yafu的pm1来分解，不过需要设置一下bound，根据题目参数可以设置为(, )。此外sagemath中的discrete_log方法自带Pohlig-Hellman算法，可以直接使用。

复现整个解题过程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
from Crypto.Util.number import *
from itertools import combinations
from gmpy2 import gcdext
from tqdm import tqdm

lines=open('output.txt','r').readlines()
messages=eval(lines[0])
enc=eval(lines[1])
e=0x10001
l=len(messages)

m=matrix(ZZ,l,l+1)
for i in range(l):
	m[i,i]=1
	m[i,l]=messages[i]
ml=m.LLL()
#print(ml)
kn=[]
for row in ml:
	v=vector(ZZ,row[:-1])
	mes=vector(ZZ,messages)
	assert v*mes==row[-1]
	t1,t2=0,0
	s1,s2=1,1
	for i in range(len(row[:-1])):
		if row[i]>0:
			t1+=messages[i]*row[i]
			s1*=enc[i]^row[i]
		else:
			t2+=messages[i]*(-row[i])
			s2*=enc[i]^(-row[i])
	if row[-1]<0:
		t1+=(-row[-1])
		s1*=e^(-row[-1])
	else:
		t2+=row[-1]
		s2*=e^row[-1]
	if t1<t2:
		kn.append(s1*e^(t2-t1)-s2)
	else:
		kn.append(s2*e^(t1-t2)-s1)

n=gcd(kn)
print(n)

'''
49611284910337799636686093973628884556519420722411744808788041251053464830295020698422734325291979154664020667752312689941156441913588062021033819091827109198856404394033383330790178899747263327203370892584838961198767774504917946326930691665376634864787990599380909937268721753630966833756746550396165568643515524639508308583115086758244593451557057086091631335435790943219993697350307236788433226079650671638629500149333590709610544282138758930744076756362806343446562260731142938656726337673043604423108674514420668104284015023085322240000000000000000000

div by small primes

131158523227880830085100826212925738665356578827561846263073537503153187073136528966506785633847097997799377037969243883439723340886038624250936927221630287086602285835045356221763554989140952262353930420392663280482277832613695689454662506372252641564106136178637816827646124189347219273164844809807934422046441
'''
n=131158523227880830085100826212925738665356578827561846263073537503153187073136528966506785633847097997799377037969243883439723340886038624250936927221630287086602285835045356221763554989140952262353930420392663280482277832613695689454662506372252641564106136178637816827646124189347219273164844809807934422046441
c=enc[-1]
'''
yafu pm1(131158523227880830085100826212925738665356578827561846263073537503153187073136528966506785633847097997799377037969243883439723340886038624250936927221630287086602285835045356221763554989140952262353930420392663280482277832613695689454662506372252641564106136178637816827646124189347219273164844809807934422046441) -B1pm1 33554432 -B2pm1 4294967296
'''
p=10104420349837363561278745998119091841853342383118385156657416134976061697027571349895988817770681767227605656666215380267313369652920490697343475330713803
q=12980311456459934558628309999285260982188754011593109633858685687007370476504059552729490523256867881534711749584157463076269599380216374688443704196597025947
res=discrete_log(mod(c,q),mod(e,q))
print(long_to_bytes(res))
b'n1ctf{1f1b18f9-8523-4584-a8eb-c8b5c9c9433d}'

babyecc

题目源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
from secret import flag

m = Integer(int.from_bytes(flag, 'big'))

for _ in range(7):
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    while 1:
        try:
            a = randint(0,n)
            b = randint(0,n)
            Ep = EllipticCurve(GF(p), [a,b])
            Gp = Ep.lift_x(m) * 2
            Eq = EllipticCurve(GF(q), [a,b])
            Gq = Eq.lift_x(m) * 2
            y = crt([int(Gp[1]),int(Gq[1])],[p,q])
            break
        except Exception as err:
            pass
    print(n, a, b, y)

题目代码很简单就不多作描述了。可以观察到，每一次加密使用的是相同的m，不同的a, b, n。因此可以类比于RSA中的Hastad广播攻击，主要的思想是计算多项式并求crt，然后求根。

这题的主要关键点在于y和m之间关系的一个推导。比赛时就因为这一步出了问题推错了，然后就卡住了。赛后复现又重新推了一遍这个过程，这里把推理过程写一下。

首先假设，。然后我们根据椭圆曲线公式及点的倍乘关系有： 然后把相关变量代入到中： 为了消掉，需要凑出偶数次幂。式子左边有，右边可以直接代入，因此需要两边平方。记： 因此上面的式子可以简写转化为: 其中，除了m之外的变量全部已知。

我们根据这个关系，可以得到7个不同域上的多项式。然后计算这7个多项式的crt得到，其中，的系数由的对应项系数crt计算得出。为7*1024bits，而m大概为344bits（8bits*43，根据flag格式特征），因此可以用small_roots求解。

注意多项式G为12阶，根据coppersmith相关参数的意义，在实际试验过程中，epsilon大概小于0.04左右才能得到结果。

复现解题脚本如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
from Crypto.Util.number import *

lines=open('output.txt','r').readlines()

enc=[tuple(map(int,lines[i].strip().split(' '))) for i in range(7)]
coeffi=[]

for i in range(7):
	n,a,b,y=enc[i]
	R.<x>=PolynomialRing(Zmod(n))
	f=x^3+a*x+b
	g=3*x^2+a
	l=64*f^3*y^2
	r=12*x*f*g-g^3-8*f^2
	F=l-r^2
	coeffi.append(F.monic())

deg=12
ns=[ enc[i][0] for i in range(len(enc))]
N=1
for n in ns:
    N*=n

Crtlist=[[0 for _ in range(7)] for __ in range(deg+1)]
for i in range(7):
    for j in range(deg+1):
        Crtlist[j][i]=ZZ(coeffi[i][j])

A=[]
for i in range(deg+1):
    A.append(CRT(Crtlist[i],ns))

R.<m>=PolynomialRing(Zmod(N))
G=R(A)

print('Finding Roots')
res=G.small_roots(X=2^350,epsilon=1/25)
if len(res)>0:
	print(res)
	print(long_to_bytes(int(res[0])))
else:
	print('No solution found.')
#b'n1ctf{7140f171-5fb5-484d-92f4-9f7ba02c33d0}'

N1CTF2022 Crypto赛题复现

https://litao6666.github.io/202211/eb902975.html

Author

zealot

Posted on

2022-11-08

Updated on

2022-11-09

Licensed under

Catalogue

×