20210522-NEEPU Sec2021公开赛-CryptoSecWriteUp

Posted on Edited on In , Views: Symbols count in article: 7.9k Reading time ≈ 7 mins.

 

Crypto

RSA

题目描述

代码并不复杂，常规的运算

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
from Crypto.Util.number import *
from sympy import nextprime
import gmpy2
import random

def encode (p1,p2,e):
    not_hint = (p1 + 1) * (p2 + 1)
    S = gmpy2.invert(e, not_hint)
    not_p = S%(p1+1)
    return not_p

flag = b'Neepu{********************}'
flag = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
e = nextprime(random.randint(1,1000))
d = gmpy2.invert(e, (p-1)*(q-1))
c = pow(flag, e, n)
print(c)
print(n)

m = encode(p, q, e)
c1 = pow(m, 7, n)
c2 = pow(m+e, 7, n)
print(c1)
print(c2)

'78543767285872349029076059073458316000847341792088805258173041942425687239313215276670106926320359777962661495032475004417723103701253550583245518206305422982968675291500865382213182669036827898932991063338163290845510339896689210314509493839746410486257998875782496654704288722251878269643040214139429715671'
'91995272927105081122659192011056020468305570748555849650309966887236871318156855318666540461669669247866754568189179687694315627673545298267458869140096224628114424176937828378360997230874932015701507629238213240839370628366083111028544554453150572165461450371411341485911677167168492357154684642531577228543'
'10186066785511829759164194803209819172224966119227668638413350199662683285189286077736537161204019147791799351066849945954518642600518196927152098131117402608793752080104402893792812059620726950782670809837962606250674588612783027976958719051829085903720655233948024280118985875980227528403883475592567727892'
'46182103994299145562022812023438495797686077104477472631494150222038404419414100727667171290098624214113241032861128455086601197239761085752413519627251290509474327611253599768650908336142621210005389246714504358370629231557080301516460985022782887233790302054696967900384601182742759555421864610431428746119'

题目解析

首先套了一个短的padding的，用Related Message Attack可以整出来，接用la师傅的脚本

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
def short_pad_attack(c1, c2, e, n):
    PRxy.< x, y > = PolynomialRing(Zmod(n))
    PRx.< xn > = PolynomialRing(Zmod(n))
    PRZZ.< xz, yz > = PolynomialRing(Zmod(n))
    g1 = x ^ e - c1
    g2 = (x + y) ^ e - c2
    q1 = g1.change_ring(PRZZ)
    q2 = g2.change_ring(PRZZ)
    h = q2.resultant(q1)
    h = h.univariate_polynomial()
    h = h.change_ring(PRx).subs(y=xn)
    h = h.monic()
    kbits = n.nbits() // (2 * e * e)
    diff = h.small_roots(X=2 ^ kbits, beta=0.4)[0]  # find root < 2^kbits with factor >= n^0.4
    return diff


def related_message_attack(c1, c2, diff, e, n):
    PRx.< x > = PolynomialRing(Zmod(n))
    g1 = x ^ e - c1
    g2 = (x + diff) ^ e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

    return -gcd(g1, g2)[0]


if __name__ == '__main__':
    c2 = 10186066785511829759164194803209819172224966119227668638413350199662683285189286077736537161204019147791799351066849945954518642600518196927152098131117402608793752080104402893792812059620726950782670809837962606250674588612783027976958719051829085903720655233948024280118985875980227528403883475592567727892
    c1 = 46182103994299145562022812023438495797686077104477472631494150222038404419414100727667171290098624214113241032861128455086601197239761085752413519627251290509474327611253599768650908336142621210005389246714504358370629231557080301516460985022782887233790302054696967900384601182742759555421864610431428746119
    n = 91995272927105081122659192011056020468305570748555849650309966887236871318156855318666540461669669247866754568189179687694315627673545298267458869140096224628114424176937828378360997230874932015701507629238213240839370628366083111028544554453150572165461450371411341485911677167168492357154684642531577228543
    e = 7
    diff = short_pad_attack(c1, c2, e, n)
    print("difference of two messages is %d" % diff)
    m1 = related_message_attack(c1, c2, diff, e, n)
    print("m1:", m1)
    print("m2:", m1 + diff)

出来是

20210522 又是被组员嘲讽的一天-a21cb98f.png

显然第二个才是我们需要的m，两个相减可以得到e

其次，出题人用一个加密函数加密了p和q

1
2
3
4
5
def encode (p1,p2,e):
    not_hint = (p1 + 1) * (p2 + 1)
    S = gmpy2.invert(e, not_hint)
    not_p = S%(p1+1)
    return not_p

提取一下，已知

$e\times S\equiv 1\ (mod\ (p+1)*(q+1))$
$not_p\equiv S\ (mod\ (p+1))$

这里主要是引入一条显而易见的形式

若$n\ mod\ (p*q)=1$，则，
$$
n\ mod\ q=1，n\ mod\ p=1\notag
$$
这个结论的证明很简单，如果说n是p和q的乘积多1的话，那么，显然n也是p的倍数多1，q也同理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import isPrime, long_to_bytes
from gmpy2 import invert
c1 = 10186066785511829759164194803209819172224966119227668638413350199662683285189286077736537161204019147791799351066849945954518642600518196927152098131117402608793752080104402893792812059620726950782670809837962606250674588612783027976958719051829085903720655233948024280118985875980227528403883475592567727892
c2 = 46182103994299145562022812023438495797686077104477472631494150222038404419414100727667171290098624214113241032861128455086601197239761085752413519627251290509474327611253599768650908336142621210005389246714504358370629231557080301516460985022782887233790302054696967900384601182742759555421864610431428746119
n = 91995272927105081122659192011056020468305570748555849650309966887236871318156855318666540461669669247866754568189179687694315627673545298267458869140096224628114424176937828378360997230874932015701507629238213240839370628366083111028544554453150572165461450371411341485911677167168492357154684642531577228543
c = 78543767285872349029076059073458316000847341792088805258173041942425687239313215276670106926320359777962661495032475004417723103701253550583245518206305422982968675291500865382213182669036827898932991063338163290845510339896689210314509493839746410486257998875782496654704288722251878269643040214139429715671
m_e = 129256555243625096140386916253259867206651269142565502540823654159666398099455456877012993395632742360829588042575108302297567291349420390228163587340930
m = 129256555243625096140386916253259867206651269142565502540823654159666398099455456877012993395632742360829588042575108302297567291349420390228163587340859
# e = m_e - m
# print(e)
e = 71
not_p = m
p = 1
for i in range(1, 1000):
    if (e*not_p-1) % i == 0 and isPrime((e*not_p-1) // i - 1):
        p = (e*not_p-1) // i - 1
        break

assert n % p == 0
q = n // p
d = invert(e, (p-1)*(q-1))
print(long_to_bytes(pow(c, d, n)))

AES

代码

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.Cipher import AES
import os
from Crypto.Util.number import *

flag = os.urandom(18)
flag_enc = os.urandom(45)
print(flag_enc)
pad = b'a' * 12 + b'Neepu{'
flag_enc = pad+flag_enc+b'}'
masg1 = flag_enc[0:32]
masg2 = flag_enc[32:]

m = bytes_to_long(masg1) ^ bytes_to_long(masg2)
key = os.urandom(2)*16
iv = masg2[16:][:16]
print(bytes_to_long(key) ^ bytes_to_long(iv))
aes = AES.new(key, AES.MODE_CBC, iv)
enc_flag = aes.encrypt(long_to_bytes(m))
print(enc_flag)

'''
111074535590201916919246051309547040927554959486196038152130336189953949145068
b'\xd8\x83\xfd\x89\xc3+\x11\xb8g\xd2\xf5k\xeeU\x88\xb5\xde\x8bq\x9bC\xab\xe3K2R<\xaa\xbc\x92H\x19'
'''

首先可以跑出iv和key

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Cipher import AES
import os
from gmpy2 import*
from Crypto.Util.number import*

xor = 111074535590201916919246051309547040927554959486196038152130336189953949145068
enc_flag = b'\xd8\x83\xfd\x89\xc3+\x11\xb8g\xd2\xf5k\xeeU\x88\xb5\xde\x8bq\x9bC\xab\xe3K2R<\xaa\xbc\x92H\x19'
out = long_to_bytes(xor)
key = out[:16]*2
print(key)
iv = bytes_to_long(key[16:]) ^ bytes_to_long(out[16:])
print(iv)
iv = long_to_bytes(iv)

然后这里我们可以算出一部分的masg1，接着

1
2
3
aes = AES.new(key, AES.MODE_CBC, iv)
m = aes.decrypt(enc_flag)
print(long_to_bytes(bytes_to_long(m) ^ bytes_to_long(iv)))
1
b'\r\x11\x18\x0b\x08L\x08\x0b\r\x0c\x14\n!\x00\x16\x13u{qszeftwdr-thui'

一看刚好是16位，结合前面的12个a还有’Neep’，整好32位，masg1齐了，他们和密文是异或的关系

连起来是这样的

1
aaaaaaaaaaaaNeepu{qszeftwdr-thuilpyji-ijlmukoescfefcsukobhmtfhb}

尚师傅手打了一遍之后发现是一种新编码，在电脑键盘上被这些字母包围起来的是真正的明文

根据分隔符提示，flag里面包着的应该是下面这一串，可能会有几个字母对错，根据含义就好

1
are-you-kidding

中国古代加密

20210522 又是被组员嘲讽的一天-d5aef625.png

挺有意思的提道题，主要是运用到了反切注音

hint主要是说第一个红字处的对子是构成了flag的头尾，然后第二个红字处的一首诗歌要分成上下来看，还有就是排列组合，其他的感觉也没什么用

首先我们看头尾是花甲重逢+三七岁月和古稀双庆+一度春秋，这个对子的出处就是乾隆和纪晓岚为一为140岁老人对的，60 * 2 + 27和70 * 2 + 1都是等于141，所以收尾开头是141

其次两首诗分开，前两句是对应声母，找出密文对应的声母在头两句14个字中的位子，后两句是对应韵母，同样也是找对应的，并且这里不考虑声调，声调是另外编码的1~4，然后拼凑起来，注意这里是要凑的，因为存在重复的韵母和声母，而且也没有确切指明是哪一个

最后的flag是

1
141181832310414124141

这么看比较简单，但是当时提示比较少，反切注音还有很多变式和不成文的规定

Misc

The Puzzles of the Fifteen Tiles

20210522 又是被组员嘲讽的一天-76ae8347.png

小技巧

20210522 又是被组员嘲讽的一天-ee4c638b.png

最后两排应该先排第一列， 然后是第二列，依次下去