writeup-for-2021-CISCN

Posted on Edited on In Word count in article: 22k Reading time ≈ 20 mins.

国赛初赛, 第一次参加国赛, 除了第一道恶心的古典, 其他题目还是做的挺有意思的
一共六道题, 出了四道题, 剩下一道古典(呕了), 一道AES
还可以吧, 记录一下, 虽然有些部分以前做过, 但还是学到了新东西的

0x00 classic

滚了, 等真密码👴👴的wp,

2021 / 5 /18 看了别的爷爷博客, 好家伙套娃爆破 ADFGX + 凯撒 +栅栏(话说是ADFGX这个顺序吗)

0x01 move

problem

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
66
67
68
69
70
71
72
from Crypto.Util.number import *
from math import sqrt, gcd
import random

BITS = 512
f = open("flag.txt", "rb")
flag = f.read()
f.close()

def get_prime(nbit):
    while True:
        p = getPrime(nbit)
        if p % 3 == 2:
            return p


def gen(nbit):
    p = get_prime(nbit)
    q = get_prime(nbit)
    if q > p:
        p, q = q, p
    n = p * q
    bound = int(sqrt(2 * n)) // 12
    while True:
        x = random.randint(1, round(sqrt(bound)))
        y = random.randint(1, bound) // x
        zbound = int(((p - q) * round(n ** 0.25) * y) // (3 * (p + q)))
        z = zbound - ((p + 1) * (q + 1) * y + zbound) % x
        e = ((p + 1) * (q + 1) * y + z) // x
        if gcd(e, (p + 1) * (q + 1)) == 1:
            break
    gifts = [int(bin(p)[2:][:22], 2), int(bin(p)[2:][256:276], 2)]
    return n, e, gifts


def add(p1, p2):
    if p1 == (0, 0):
        return p2
    if p2 == (0, 0):
        return p1
    if p1[0] == p2[0] and (p1[1] != p2[1] or p1[1] == 0):
        return (0, 0)
    if p1[0] == p2[0]:
        tmp = (3 * p1[0] * p1[0]) * inverse(2 * p1[1], n) % n
    else:
        tmp = (p2[1] - p1[1]) * inverse(p2[0] - p1[0], n) % n
    x = (tmp * tmp - p1[0] - p2[0]) % n
    y = (tmp * (p1[0] - x) - p1[1]) % n
    return (int(x), int(y))


def mul(n, p):
    r = (0, 0)
    tmp = p
    while 0 < n:
        if n & 1 == 1:
            r = add(r, tmp)
        n, tmp = n >> 1, add(tmp, tmp)
    return r


n, e, hint = gen(BITS)
pt = (bytes_to_long(flag[:len(flag) // 2]), bytes_to_long(flag[len(flag) // 2:]))
c = mul(e, pt)
f = open("output.txt", "w")
f.write(f"n = {n}\n")
f.write(f"e = {e}\n")
f.write(f"h1 = {hint[0]}\n")
f.write(f"h2 = {hint[1]}\n")
f.write(f"c = {c}\n")
f.close()

analyses

啊这，看到题目马上就想起刚结束不久的虎符的simultaneous了，当时那题没解出来恼火了好久。还好那个时候写wp写的够详细了，回去再看一遍又仿佛明白了一切hhh

传送门->

跟着虎符那样就能分解了，得到了，之后，再看看后面的加密

看到add() mul(), ECC没错了，吸取以前的教训，做ECC先看关系式是怎样的，从加法的那几行可以看出，这里用的椭圆曲线就是常用的那种，而且， 有一个点很容易就能算出参数

通过分解出的，我们就能造出曲线, 阶为，椭圆曲线的乘法就是一个环，乘完一个阶就转回来了，所以只需要求 就可以有

最后把点转回来就完事了

exp

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
66
67
68
69
70
71
72
73
74
75
76
77
n = 80263253261445006152401958351371889864136455346002795891511487600252909606767728751977033280031100015044527491214958035106007038983560835618126173948587479951247946411421106848023637323702085026892674032294882180449860010755423988302942811352582243198025232225481839705626921264432951916313817802968185697281
e = 67595664083683668964629173652731210158790440033379175857028564313854014366016864587830963691802591775486321717360190604997584315420339351524880699113147436604350832401671422613906522464334532396034178284918058690365507263856479304019153987101884697932619200538492228093521576834081916538860988787322736613809
c = (6785035174838834841914183175930647480879288136014127270387869708755060512201304812721289604897359441373759673837533885681257952731178067761309151636485456082277426056629351492198510336245951408977207910307892423796711701271285060489337800033465030600312615976587155922834617686938658973507383512257481837605, 38233052047321946362283579951524857528047793820071079629483638995357740390030253046483152584725740787856777849310333417930989050087087487329435299064039690255526263003473139694460808679743076963542716855777569123353687450350073011620347635639646034793626760244748027610309830233139635078417444771674354527028)
from Crypto.Util.number import long_to_bytes
from gmpy2 import is_prime
def find_p_puls_q(f,k):
    s = 0
    b = k
    for i in range(2000):
        a = (s+b) // 2
        if f.subs(x==a) > 0:
            s = a 
        else:
            b = a
    return a

def find_p(pq,n):
    p = var('p')
    if pq^2 - 4*n<0:
        return []
    f = p^2 - pq*p+n
    r = f.roots()
    res = []
    for i in r:
        if i[0]>0:
            res.append(int(i[0]))
    return (res[0],res[1])
def add(p1, p2):
    if p1 == (0, 0):
        return p2
    if p2 == (0, 0):
        return p1
    if p1[0] == p2[0] and (p1[1] != p2[1] or p1[1] == 0):
        return (0, 0)
    if p1[0] == p2[0]:
        tmp = (3 * p1[0] * p1[0]) * int(inverse_mod(2 * p1[1], n)) % n
    else:
        tmp = (p2[1] - p1[1]) * int(inverse_mod(p2[0] - p1[0], n) )% n
    x = (tmp * tmp - p1[0] - p2[0]) % n
    y = (tmp * (p1[0] - x) - p1[1]) % n
    return (int(x), int(y))


def mul(n, p):
    r = (0, 0)
    tmp = p
    while 0 < n:
        if n & 1 == 1:
            r = add(r, tmp)
        n, tmp = n >> 1, add(tmp, tmp)
    return r

sn = round(sqrt(n))
L  = [[sn,e],[0,-n]]
L = matrix(L)
R = L.LLL()[0]
x = abs(R[0]) // sn
s = abs(R[1])
A = round(n ^ 0.25)^2
y = (e * x  - s )//n
kk =  (e * x - y * n ) // y
x = var('x')
f =(3*(kk-1)*x-3*x^2)^2 - A*(x^2-4*n)

ppq = find_p_puls_q(f,kk)
p,q =find_p(ppq+1,n)


b = - ( c[0] ** 3 - c[1]**2) % p
E = EllipticCurve(GF(p), [0, 0, 0, 0, b])
P = E(c)
o = P.order()


d = inverse_mod(e,o)
m = d * E(c)
print(long_to_bytes(m[0])+long_to_bytes(m[1]))

0x02 imageencrypt

problem

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
import random
from flag import flag,image,r,key1,key2
import md5

assert(flag[:5]=='CISCN')
assert(len(str(r))==3)
data = ''.join(map(chr,image))
assert(flag[6:-1] == md5.new(data).hexdigest())
assert(key1<256)
assert(key2<256)

x0 = random.random()
x0 = round(x0,6)

def generate(x):
    return round(r*x*(3-x),6)


def encrypt(pixel,key1,key2,x0,m,n):
    num = m*n/8    
    seqs = []
    x = x0
    bins = ''
    tmp = []
    for i in range(num):
        x = generate(x)
        tmp.append(x)
        seqs.append(int(x*22000))
    for x in seqs:
        bin_x  = bin(x)[2:]
        if len(bin_x) < 16:
            bin_x = '0'*(16-len(bin_x))+bin_x
        bins += bin_x
    assert(len(pixel) == m*n)
    cipher = [ 0 for i in range(m) for j in range(n)]
    for i in range(m):
        for j in range(n):
            index = n*i+j
            ch = int(bins[2*index:2*index+2],2)
            pix = pixel[index]
            if ch == 0:
                pix = (pix^key1)&0xff
            if ch == 1:
                pix = (~pix^key1)&0xff
            if ch == 2:
                pix = (pix^key2)&0xff
            if ch == 3:
                pix = (~pix^key2)&0xff
            cipher[index] = pix 
    return cipher

flagimage = image
testimage = []
for i in range(16*16):
    testimage.append(random.randint(0,255))
print testimage
print encrypt(testimage,key1,key2,x0,16,16)
print encrypt(flagimage,key1,key2,x0,24,16)

analyses

这题做的时候没好好分析，有些结果没追究到底是为啥，拿到了就开始爆破了，现在好好分析一下。

这里模拟了一个图片的加密，加密会有一个范围在的六位小数初始值，以及一个咱们不知道的参数，但是这个参数有一个hint，len(str(r)) == 3，不过这个hint一开始误导我了。。。

先来看看具体的加密过程。加密大概可以分为两个过程

  1. bitstream生成
  2. 根据bitstream key1 key2对图片进行加密

bitstream生成

bitstream的生成跟两个变量有关，确定的这两个参数那么生成的bitstream将会一模一样，我们可以根据生成bitstream的函数写出这两个变量的一个关系

也就是说我们只需要确定两个就能大概的算出了，先记为，后面有用

而bitstream是根据生成的序列来生成的，具体是这样

这里的是拼接，而且在长度不够16的时候会在前面填充0到长度为16

加密

我们把bitstream每两位看成一个，也就是说比特流是这样的->，显然的范围是

再说加密过程之前，得先了解一个小知识(~a ^ a )会把的所有位都置为1

好了，现在来看整个加密过程

这里的图片其实就是一个范围在的数的序列

一块公式直接搞定加密！(公式里的-m都是m的反码的意思)

所以整个加密就是由bitstream来决定使用哪个密钥和操作

题目给了三个图片数据，要求

这里我们计算，如果是不取反的操作，那么异或出来的就是key，

如果是进行了取反操作的，那么异或出来的就是key的反码，

所以最后整个图片异或下来，出现的数据只会有四个数字

1
[78, 177, 78, 177, 169, 78, 86, 86, 78, 177, 78, 169, 78, 78, 78, 177, 78, 177, 177, 169, 78, 86, 177, 169, 78, 177, 86, 78, 86, 169, 169, 169, 177, 169, 169, 169, 86, 169, 78, 78, 78, 78, 177, 177, 177, 78, 177, 78, 177, 169, 78, 86, 169, 78, 86, 177, 78, 86, 177, 177, 169, 78, 86, 169, 177, 86, 78, 177, 86, 169, 169, 177, 86, 177, 86, 78, 169, 169, 86, 86, 177, 78, 86, 78, 86, 78, 169, 169, 86, 86, 78, 169, 86, 169, 169, 86, 177, 86, 169, 169, 177, 177, 86, 86, 78, 169, 177, 78, 78, 169, 177, 169, 177, 78, 86, 86, 86, 78, 177, 78, 86, 86, 78, 78, 177, 78, 177, 169, 177, 86, 169, 177, 177, 78, 169, 78, 78, 169, 86, 177, 177, 78, 169, 78, 177, 78, 86, 177, 86, 86, 78, 86, 86, 86, 86, 86, 86, 177, 78, 177, 177, 169, 177, 86, 78, 177, 169, 177, 78, 86, 86, 86, 78, 78, 177, 86, 177, 78, 169, 78, 169, 169, 169, 86, 86, 78, 86, 169, 86, 78, 169, 169, 177, 86, 177, 169, 78, 78, 78, 78, 86, 177, 169, 78, 86, 177, 86, 78, 177, 78, 86, 86, 169, 86, 177, 78, 86, 86, 78, 177, 177, 169, 177, 86, 177, 86, 86, 169, 177, 169, 177, 78, 78, 169, 86, 86, 78, 177, 177, 169, 177, 78, 86, 177, 78, 177, 86, 169, 86, 86, 86, 169, 86, 177, 86, 177]

[169,177,86,78]，而169对应的反码是86，177对应78

现在问题来了，有了这个能干嘛

能否通过这四个数字还原回bitstream呢，我们知道bitstream是决定使用哪个密钥的，而密钥的使用顺序我们是知道的(我们只是不知道哪个是key1 哪个是key2)，我们可以一一假设一下，也就8种组合

key1 key2 ~key1 ~key2
86 78 169 177
86 177 169 78
169 177 86 78
169 78 86 177
78 169 177 86
78 86 177 169
177 86 78 169
177 169 78 86
Xi 00 10 01 11

每种组合中，每个数字都对应一个，我们就能利用数字的顺序，还原出这种组合下所用的bitstream，也就是还原出

这里用而不是就是因为还原出的不一定是对的，只有上面的8种情况中的1种才有可能对

因为上面的

随便找了几个组合试了下算，发现都在中，再根据提示len(r) == 3，应该是个一位小数，比如这种（一开始我以为是3位数，几百的那种，让我懵了好久艹

现在，我们可以通过确定一种组合，来确定对应的和，但是加密用的bitstream比加密的长，所以想继续往下算bitstream，我们还需要

前面我们知道，是六位的小于1的小数，也就是说一共也就种可能，我们可以利用猜的和算出来的来生成bitstream，看得到的bitstream和我们算的bitstream是否相等来爆破，8种组合试完也就，十分钟不到就能解决。

爆破出，所有参数都可以对应的确定下来了。

剩下的就是重新算一次bitstream，直到长度够用来解密，解密就完事了

exp

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
# python2
import random
import md5
from time import time
m1 = [
    205, 237, 6, 158, 24, 119, 213, 32, 74, 151, 142, 186, 57, 28, 113, 62,
    165, 20, 190, 37, 159, 137, 196, 44, 97, 37, 7, 222, 220, 95, 4, 66, 0, 28,
    199, 142, 95, 105, 119, 232, 250, 215, 60, 162, 91, 211, 63, 30, 91, 108,
    217, 206, 80, 193, 230, 42, 221, 71, 136, 115, 22, 176, 91, 57, 61, 3, 87,
    73, 250, 121, 51, 72, 83, 120, 77, 199, 236, 190, 249, 116, 45, 6, 134,
    110, 149, 94, 214, 232, 153, 213, 119, 98, 81, 203, 240, 114, 240, 29, 122,
    188, 156, 53, 128, 185, 40, 147, 245, 204, 47, 101, 80, 229, 41, 150, 28,
    195, 25, 235, 119, 6, 192, 8, 73, 255, 159, 172, 77, 94, 254, 104, 236,
    219, 141, 91, 195, 162, 97, 56, 252, 173, 163, 43, 167, 214, 50, 73, 115,
    190, 254, 53, 61, 77, 138, 192, 15, 4, 190, 27, 37, 108, 101, 135, 90, 215,
    106, 243, 112, 111, 106, 89, 143, 150, 185, 142, 192, 176, 48, 138, 164,
    185, 61, 77, 72, 0, 17, 203, 210, 71, 186, 49, 162, 250, 218, 219, 195, 63,
    248, 220, 155, 180, 219, 132, 219, 94, 144, 247, 211, 95, 70, 227, 222, 31,
    69, 24, 13, 216, 185, 108, 137, 57, 186, 211, 55, 27, 158, 241, 223, 21,
    134, 106, 152, 127, 187, 245, 246, 131, 176, 177, 228, 100, 112, 11, 84,
    61, 193, 42, 41, 69, 229, 145, 254, 138, 3, 153, 123, 31
]
c1 = [
    131, 92, 72, 47, 177, 57, 131, 118, 4, 38, 192, 19, 119, 82, 63, 143, 235,
    165, 15, 140, 209, 223, 117, 133, 47, 148, 81, 144, 138, 246, 173, 235,
    177, 181, 110, 39, 9, 192, 57, 166, 180, 153, 141, 19, 234, 157, 142, 80,
    234, 197, 151, 152, 249, 143, 176, 155, 147, 17, 57, 194, 191, 254, 13,
    144, 140, 85, 25, 248, 172, 208, 154, 249, 5, 201, 27, 137, 69, 23, 175,
    34, 156, 72, 208, 32, 195, 16, 127, 65, 207, 131, 57, 203, 7, 98, 89, 36,
    65, 75, 211, 21, 45, 132, 214, 239, 102, 58, 68, 130, 97, 204, 225, 76,
    152, 216, 74, 149, 79, 165, 198, 72, 150, 94, 7, 177, 46, 226, 252, 247,
    79, 62, 69, 106, 60, 21, 106, 236, 47, 145, 170, 28, 18, 101, 14, 152, 131,
    7, 37, 15, 168, 99, 115, 27, 220, 150, 89, 82, 232, 170, 107, 221, 212, 46,
    235, 129, 36, 66, 217, 222, 36, 15, 217, 192, 247, 192, 113, 230, 129, 196,
    13, 247, 148, 228, 225, 86, 71, 133, 132, 238, 236, 127, 11, 83, 107, 141,
    114, 150, 182, 146, 213, 250, 141, 53, 114, 16, 198, 70, 133, 17, 247, 173,
    136, 73, 236, 78, 188, 150, 239, 58, 199, 136, 11, 122, 134, 77, 47, 167,
    137, 188, 55, 195, 41, 49, 245, 92, 160, 213, 254, 0, 85, 205, 193, 69, 2,
    140, 143, 155, 127, 236, 179, 199, 168, 35, 85, 40, 45, 174
]
c2 = [
    198, 143, 247, 3, 152, 139, 131, 84, 181, 180, 252, 177, 192, 25, 217, 179,
    136, 107, 190, 62, 4, 6, 90, 53, 105, 238, 117, 44, 5, 116, 132, 195, 214,
    171, 113, 209, 18, 31, 194, 174, 228, 212, 196, 14, 27, 41, 211, 56, 139,
    135, 225, 214, 89, 122, 178, 212, 185, 231, 204, 150, 204, 212, 160, 142,
    213, 173, 186, 166, 65, 238, 5, 32, 45, 31, 25, 189, 148, 38, 78, 79, 33,
    56, 227, 48, 103, 163, 31, 189, 37, 124, 106, 249, 86, 188, 86, 233, 41,
    250, 89, 7, 212, 234, 111, 104, 245, 102, 227, 96, 160, 67, 181, 13, 26,
    192, 214, 210, 188, 84, 216, 215, 243, 72, 233, 2, 122, 166, 107, 251, 70,
    128, 94, 190, 185, 210, 34, 85, 77, 29, 182, 77, 115, 208, 228, 252, 73,
    198, 151, 70, 10, 97, 138, 235, 21, 117, 239, 102, 129, 2, 253, 80, 53, 61,
    184, 220, 41, 82, 37, 140, 23, 143, 179, 53, 153, 113, 213, 211, 111, 197,
    248, 65, 60, 69, 1, 81, 48, 254, 251, 89, 195, 8, 93, 190, 66, 174, 97,
    175, 210, 191, 66, 112, 123, 128, 33, 230, 237, 104, 16, 192, 239, 173, 44,
    10, 120, 231, 114, 151, 140, 63, 103, 44, 243, 222, 242, 73, 51, 46, 98,
    137, 163, 152, 147, 95, 223, 3, 15, 112, 85, 215, 133, 131, 240, 239, 224,
    195, 140, 124, 70, 156, 221, 241, 37, 245, 1, 99, 9, 157, 99, 150, 47, 118,
    225, 16, 13, 141, 135, 99, 18, 119, 63, 160, 6, 247, 27, 68, 45, 199, 86,
    193, 252, 21, 135, 32, 42, 103, 114, 241, 49, 249, 182, 52, 18, 155, 157,
    61, 4, 246, 158, 52, 118, 242, 195, 54, 139, 232, 100, 31, 11, 233, 58,
    100, 101, 137, 83, 145, 209, 7, 241, 96, 57, 148, 207, 29, 237, 124, 177,
    166, 161, 20, 116, 122, 61, 71, 46, 82, 18, 157, 253, 130, 112, 66, 94, 57,
    221, 243, 222, 192, 147, 5, 130, 201, 174, 26, 160, 16, 188, 103, 187, 11,
    238, 182, 144, 4, 137, 33, 84, 100, 7, 239, 219, 83, 112, 189, 166, 58, 93,
    141, 30, 198, 220, 196, 118, 172, 5, 45
]

def decrypt(pixel,key1,key2,x0,m,n):
    num = m*n/8    
    seqs = []
    x = x0
    bins = ''
    tmp = []
    for i in range(num):
        x = generate(x)
        tmp.append(x)
        seqs.append(int(x*22000))
    for x in seqs:
        bin_x  = bin(x)[2:]
        if len(bin_x) < 16:
            bin_x = '0'*(16-len(bin_x))+bin_x
        bins += bin_x
    assert(len(pixel) == m*n)
    cipher = [ 0 for i in range(m) for j in range(n)]
    for i in range(m):
        for j in range(n):
            index = n*i+j
            ch = int(bins[2*index:2*index+2],2)
            pix = pixel[index]
            if ch == 0:
                pix = (pix^key1)&0xff
            if ch == 1:
                pix = (~(pix^key1))&0xff
            if ch == 2:
                pix = (pix^key2)&0xff
            if ch == 3:
                pix = (~(pix^key2))&0xff
            cipher[index] = pix 
    return cipher


def generate(x):
    return round(r * x * (3 - x), 6)


key = []

for i, j in zip(m1, c1):
    key.append(i ^ j)

'''
key1 may 169 177 78 86
if key1= 169 key2 only may 78 or 177 
8 combinations
ey1 = 169 ,key2 = 78 get result
'''
bitstream = ''
X = []
for i in key:
    if i == 78:
        bitstream += '10'
    if i == 169:
        bitstream += '00'
    if i == 177:
        bitstream += '11'
    if i == 86:
        bitstream += '01'

key1 = 169
key2 = 78
S = time()
X0 = int(bitstream[:16],2) / 22000.000000
X1 = int(bitstream[16:32],2) / 22000.000000
r = round(X1 / (3*X0 - X0**2),1)
print(r)
for x0 in range(10**6):
        x = round(x0 / 1000000.000000,6)
        bins = ''
        tmp = []
        seqs = []
        d = 16
        for i in range(d):
            x = generate(x)
            tmp.append(x)
            seqs.append(int(x*22000))

        for x in seqs:
            bin_x  = bin(x)[2:]
            if len(bin_x) < 16:
                bin_x = '0'*(16-len(bin_x))+bin_x
            bins += bin_x
        if bitstream[:d*16] == bins:
            x0 = round(x0 / 1000000.000000,6)
            break
print(time()-S,x0)
image = decrypt(c2,key1,key2,x0,24,16)
data = ''.join(map(chr,image))
print md5.new(data).hexdigest()

0x03 homo

problem

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
from poly import *
from math import floor, log
from copy import deepcopy
import os
import random
import sys

with open("/root/task/flag.txt", "rb")as f:
    flag = f.read()

q = 2**54
n = 1024
t = 83
T = 100
l = floor(log(q, t))
delta = floor(q/t)
mu = 0
sigma = 1
MENU = \
'''
1.game
2.decrypt
'''

def encode(s):
    _s = s + os.urandom(128 - len(flag))
    tmp = bin(int.from_bytes(_s, "big"))[2:].zfill(n)
    tmp = list(map(int, tmp))
    TMP = Poly(n, q)
    TMP.cofficient = deepcopy(tmp)
    return TMP

def Round(poly, t):
    c = deepcopy(poly)
    for i in range(c.n):
        c.cofficient[i] = c.cofficient[i] % t
        if c.cofficient[i] >= t/2:
            c.cofficient[i] -= t
    return c

def keygen():
    s = Poly(n, q)
    s.randomize(type=2, sigma=sigma,  mu=mu)
    e = Poly(n, q)
    e.randomize(type=1, sigma=sigma,  mu=mu)
    a = Poly(n, q)
    a.randomize(B=q)
    pk = [Round(-1*(a*s+e), q), a]
    return pk, s

def encrypt(pk, m):
    u = Poly(n, q)
    u.randomize(type=1, sigma=sigma,  mu=mu)
    e1 = Poly(n, q)
    e1.randomize(type=1, sigma=sigma, mu=mu)
    e2 = Poly(n, q)
    e2.randomize(type=1, sigma=sigma, mu=mu)
    return [Round(pk[0]*u+e1+delta*m, q), Round(pk[1]*u+e2, q)]

def decrypt(sk, ct):
    tmp = t * Round(ct[0] + ct[1] * sk, q)
    for i in range(tmp.n):
        tmp.cofficient[i] = round(tmp.cofficient[i] / q)
    return Round(tmp, t)

def fun():
    if not allowed:
        print("I can't let you use this.")
    else:
        a = Poly(n, q)
        b = Poly(n, q)
        tmp = [0]*n
        print("c0:")
        s = input().replace(" ", "").split(",")
        a.cofficient = deepcopy(list(map(int, s)))
        print("c1:")
        s = input().replace(" ", "").split(",")
        b.cofficient = deepcopy(list(map(int, s)))
        assert a.cofficient != ct[0].cofficient and b.cofficient != ct[1].cofficient
        assert tmp != a.cofficient and tmp != b.cofficient
        print(decrypt(sk, [a, b]).cofficient)

def game():
    global allowed
    count = 0
    random.seed(os.urandom(32))
    print("play a game with me!")
    for i in range(512):
        number = random.getrandbits(64)
        guess = int(input("your number:"))
        if guess == number:
            count += 1
            print("win")
        else:
            print(f"lose!my number is {number}\n")
    
    if count >= 200:
        allowed = True

pk, sk = keygen()
m = encode(flag)
ct = encrypt(pk, m)
allowed = False
print(pk[0].cofficient)
print(pk[1].cofficient)
print(ct[0].cofficient)
print(ct[1].cofficient)

while True:
    print(MENU)
    option = int(input())
    if option == 1:
        game()
    elif option == 2:
        fun()
    else:
        print("error")
        sys.exit(1)

还有个poly.py我到最后都没有用上。。就不放上来了

analyses

这题有两部分

  1. 第一部分。让我们猜服务端生成的64bit随机数，512次机会，猜错了会告诉你随机数是什么，猜对了就继续，如果一共猜对200次以上就可以进入下一部分
  2. 第二部分。白给的同态加密

第一部分 MT19937

其实这里考的就是 MT19937，这是python.random库用的伪随机数生成算法，状态有限，知道624*32 bit之后就能完全的算出后续的随机数。

还记得第一次解出MT19937就是我第一次比赛做密码，2020 N1CTF - VSS ，这道题当时做了一整场，始终没有做出来。看了wp才了解MT19937这种东西，不过也知道了一个可以用来预测随机数的库-> randcrack , 当我们得到了624*32bit之后，就能利用这个库算出后续的随机数

而这里刚好够，一共512次机会，前312次错误刚好可以得到31264 bit也就是624\32 bit，后面的200次机会就可以每次都猜中了。

第二部分 同态加密

说是同态加密。。。但我好像没用到里面的知识？

服务端提供了解密，我们是有密文的，按理来说直接给密文就行了，但是题目限制了提交上去解密的密文不能是flag的密文

考虑到整个过程都是的，直接给密文加上q就行了。。。

2021/5/18

吃饭的时候想着为啥题目是同态加密, 突然想到这玩意不就是个r-lwe吗, 本来密文有噪音就是可以的, 直接给c0,c1都加上1就行了, 噪音够小是不会影响解密的!

exp

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
from pwn import *
from randcrack import RandCrack
import random
import re
from Crypto.Util.number import long_to_bytes

R = lambda con: con.recv(1024)
S = lambda con, x: con.sendline(x)
con = remote('124.70.14.146', 23218)
kkk = ''
q = 2**54
for _ in range(512):
    k = R(con).decode()
    kkk += k
    if 'game' in k:
        break
kkk = kkk.split('\n')[:-5]
pk = [0, 0]
ct = [0, 0]
pk[0] = kkk[0][1:-1].split(',')
for i in range(len(pk[0])):
    pk[0][i] = int(pk[0][i])
pk[1] = kkk[1][1:-1].split(',')
for i in range(len(pk[1])):
    pk[1][i] = int(pk[1][i])
ct[0] = kkk[2][1:-1].split(',')
for i in range(len(ct[0])):
    ct[0][i] = int(ct[0][i])
ct[1] = kkk[3][1:-1].split(',')
for i in range(len(ct[1])):
    ct[1][i] = int(ct[1][i])
print(len(pk[0]))
rc = RandCrack()

S(con, b'1')
print(R(con).decode())
for _ in range(312):
    S(con, b'1')
    resp = R(con).decode()
    # print(resp)
    num = re.findall('my number is (.*)', resp)[0]
    r = bin(int(num))[2:].zfill(64)
    r1 = r[:32]
    r2 = r[32:]
    rc.submit(int(r2, 2))
    rc.submit(int(r1, 2))

num = 0
for _ in range(200):
    S(con, str(rc.predict_getrandbits(64)).encode())
    if 'win' in R(con).decode() :
        num += 1
        print(num)

c0 = ''
for i in ct[0]:
    c0 += str(i+q)+','
c1 = ''
for i in ct[1]:
    c1 += str(i + q)+','

S(con, b'2')
print(R(con).decode())
S(con,c0[:-1].encode())
print(R(con).decode())
S(con,c1[:-1].encode())
flag = ''
while True:
    flag += R(con).decode()
    if ']' in flag:
        break
print(flag)
'''
result
 [...] 出来的结果就是一堆0,1
'''
flag = [...]
for i in range(len(flag)):
    flag[i] = str(flag[i])
flag = int(''.join(flag),2)
print(long_to_bytes(flag))

0x04 oddaes

不会。。。差分分析，一直都每学会过，等一个wp学习

0x05 rsa

problem

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
from flag import text,flag
import md5
from Crypto.Util.number import long_to_bytes,bytes_to_long,getPrime

assert md5.new(text).hexdigest() == flag[6:-1]

msg1 = text[:xx]
msg2 = text[xx:yy]
msg3 = text[yy:]

msg1 = bytes_to_long(msg1)
msg2 = bytes_to_long(msg2)
msg3 = bytes_to_long(msg3)

p1 = getPrime(512)
q1 = getPrime(512)
N1 = p1*q1
e1 = 3
print pow(msg1,e1,N1)
print (e1,N1)

p2 = getPrime(512)
q2 = getPrime(512)
N2 = p2*q2
e2 = 17
e3 = 65537
print pow(msg2,e2,N2)
print pow(msg2,e3,N2)
print (e2,N2)
print (e3,N2)

p3 = getPrime(512)
q3 = getPrime(512)
N3 = p3*q3
print pow(msg3,e3,N3)
print (e3,N3)
print p3>>200

analyses

白给签到。

  1. 过小导致直接开次方得
  2. 共模攻击
  3. 已知高位

都是基础，不详细写了

exp

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
from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot
n = 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
c = 59213696442373765895948702611659756779813897653022080905635545636905434038306468935283962686059037461940227618715695875589055593696352594630107082714757036815875497138523738695066811985036315624927897081153190329636864005133757096991035607918106529151451834369442313673849563635248465014289409374291381429646
e = 65537
high_p = 7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902# high bits of p without low zeros
kbits = 200
_p = high_p<<kbits

PR.<x> = Zmod(n)[]
f = x + _p
roots = f.small_roots(X=2^kbits,beta=0.4)
p = _p+int(roots[0])
q = n // p
d = int(inverse_mod(e,(p-1)*(q-1)))
msg3 = pow(c,d,n)


#msg2
n = 111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977
c1 = 54995751387258798791895413216172284653407054079765769704170763023830130981480272943338445245689293729308200574217959018462512790523622252479258419498858307898118907076773470253533344877959508766285730509067829684427375759345623701605997067135659404296663877453758701010726561824951602615501078818914410959610
c2 = 91290935267458356541959327381220067466104890455391103989639822855753797805354139741959957951983943146108552762756444475545250343766798220348240377590112854890482375744876016191773471853704014735936608436210153669829454288199838827646402742554134017280213707222338496271289894681312606239512924842845268366950
e1 = 17 
e2 = 65537


# 利用扩展欧几里得求出s1 s2

def EX_GCD(a, b, arr, n=0):  # 扩展欧几里得
    if b == 0:
        arr[0] = 1
        arr[1] = 0
        return a
    g = EX_GCD(b, a % b, arr)
    t = arr[0]
    arr[0] = arr[1]
    arr[1] = t - int(a / b) * arr[1]
    return g  # output: s * a + t * b = 1  g:最大公因数 arr[0] = s,  arr[1] = t
arr = [0, 0]
EX_GCD(e1, e2, arr)
s1 = arr[0]
s2 = arr[1]
msg2 = (pow(c1, s1, n) * pow(c2, s2, n)) % n

# msg1 
c = 19105765285510667553313898813498220212421177527647187802549913914263968945493144633390670605116251064550364704789358830072133349108808799075021540479815182657667763617178044110939458834654922540704196330451979349353031578518479199454480458137984734402248011464467312753683234543319955893
msg1 = iroot(c,3)[0]

msg = long_to_bytes(msg1) + long_to_bytes(msg2) + long_to_bytes(msg3)

import md5
print(md5.new(msg).hexdigest())