CISCN2021

​ 2021题目比之前难挺多的，卷卷年！

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

def gongmogongji(n, c1, c2, e1, e2):
    def egcd(a, b):
        if b == 0:
            return a, 0
        else:
            x, y = egcd(b, a % b)
            return y, x - (a // b) * y
    s = egcd(e1, e2)
    s1 = s[0]
    s2 = s[1]

    # 求模反元素
    if s1 < 0:
        s1 = - s1
        c1 = invert(c1, n)
    elif s2 < 0:
        s2 = - s2
        c2 = invert(c2, n)
    m = pow(c1, s1, n) * pow(c2, s2, n) % n
    return m

# part1
c1 = 19105765285510667553313898813498220212421177527647187802549913914263968945493144633390670605116251064550364704789358830072133349108808799075021540479815182657667763617178044110939458834654922540704196330451979349353031578518479199454480458137984734402248011464467312753683234543319955893
e1 = 3
print(long_to_bytes(iroot(c1,3)[0]))

# part2
e21 = 17
n21 = 111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977
e22 = 65537
c21,c22 = 54995751387258798791895413216172284653407054079765769704170763023830130981480272943338445245689293729308200574217959018462512790523622252479258419498858307898118907076773470253533344877959508766285730509067829684427375759345623701605997067135659404296663877453758701010726561824951602615501078818914410959610,91290935267458356541959327381220067466104890455391103989639822855753797805354139741959957951983943146108552762756444475545250343766798220348240377590112854890482375744876016191773471853704014735936608436210153669829454288199838827646402742554134017280213707222338496271289894681312606239512924842845268366950
print(long_to_bytes(gongmogongji(n21,c21,c22,e21,e22)))

# part3
#sage p高位攻击
n = 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
p_fake = 7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902

pbits = p_fake.nbits()
kbits = 200  # p失去的低位
pbar = p_fake * 2 ^ 200

PR. < x > = PolynomialRing(Zmod(n))
f = x + pbar

x0 = f.small_roots(X=2 ^ kbits, beta=0.4)[0]
p = x0 + pbar
print(p)

c3 = 59213696442373765895948702611659756779813897653022080905635545636905434038306468935283962686059037461940227618715695875589055593696352594630107082714757036815875497138523738695066811985036315624927897081153190329636864005133757096991035607918106529151451834369442313673849563635248465014289409374291381429646
n3 = 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
p = 11437038763581010263116493983733546014403343859218003707512796706928880848035239990740428334091106443982769386517753703890002478698418549777553268906496423
q = n3//p
assert p*q == n3
phi = (p-1)*(q-1)
d = invert(e22,phi)
print(long_to_bytes(pow(c3,d,n3)))

b' \nO wild West Wind, thou breath of Autum'
b"n's being,\nThou, from whose unseen presence the leaves dead\nAre driven, like ghosts from an enchanter fleeing,\nYellow, a"
b'nd black, and pale, and hectic red,\nPestilence-stricken multitudes: O thou,\nWho chariotest to their dark wintry bed\n'

imageencrypt

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
from Crypto.Util.number import *
from hashlib import *

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

def get_r(data):
    for i in range(len(data)-1):
        r = round(data[i] / round((data[i+1]*(3-data[i+1])),6),1)
        print("r:",r)
    # for i in range(len(data)-1):
    #     print(i,generate(data[i],r),data[i+1],(generate(data[i],r)-data[i+1]))

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,1.2)
        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 # bins相当于密钥序列
    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 get_nums():
    out = []
    for i in range(16*16):
        out.append((testimage[i]^testimage_enc[i])&0xff)
    print(out)

testimage = [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]
testimage_enc = [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]
flag_enc = [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]
get_nums()
# 全部取ch = 0进行计算，得到[78, 86, 169, 177]，这四个值有两个分别为key1和key2

keys = [78, 86, 169, 177]
bins_l = []
keys_l = []

for key1 in keys:
    for key2 in keys:
        if key1 == key2: continue # key1和key2应该是不相等的
        bins = ""
        err = False
        for i in range(16*16):
            if ((testimage[i]^testimage_enc[i])&0xff) == key1:
                bins+="00"
            elif ((~testimage[i]^testimage_enc[i])&0xff) == key1:
                bins+="01"
            elif ((testimage[i]^testimage_enc[i])&0xff) == key2:
                bins+="10"
            elif ((~testimage[i]^testimage_enc[i])&0xff) == key2:
                bins+="11"
            else:
                err = True
                print(key1,key2)
                print("This is not keys!")
                break
        if len(bins)==16*16*2:
            bins_l.append(bins)
            keys_l.append((key1,key2))

        if err: continue
# print(keys_l)
print(bins_l)
# 根据输出排除4组:[78,177] [86,169] [169,86] [177,78] keys对一共是A(4,2),12组,还剩下8组,保存此8组的keys和bins
# assert(len(str(r))==3) 这里r要么为几百要么为1位小数,后者更合理
# 用bins反算出seqs,这里的seqs是真实x序列的近似值,用相邻的x计算r,有一组基本相邻两个求出来都是1.2,故r应该是1.2

for bin_x in bins_l:
    x_list = []
    for i in range(len(bin_x) // 16):
        #print(i)
        # print(bin_x[i * 16:i * 16 + 16])
        x = int(bin_x[i * 16:i * 16 + 16], 2)
        data = round(x / 22000, 6)
        if (int(data * 22000) == x):
            x_list.append(data)
        elif (int(round(data - 0.000001, 6) * 22000) == x):
            data = round(data - 0.000001, 6)
            x_list.append(data)
        elif (int(round(data + 0.000001, 6) * 22000) == x):
            data = round(data + 0.000001, 6)
            x_list.append(data)
        else:
            print("ERROR")
            exit(0)
        assert int(x_list[i] * 22000) == x
    print(x_list)
    get_r(x_list)
    print(keys_l[bins_l.index(bin_x)])

#  爆破初始x0,10^6次可以接受
key1, key2, r = 169, 78, 1.2
bin_s = "10111011001001011011100010101011101111001001110010110110010000001100000001001010101011111110111011001001001001111001111100100100110110110100001101110110000001011110011001100000010110000100000111010000111101011000111010001100111001010110111001011010111011001101001111100010100001111110001011100111010110010101010101111011110011011011001110010101101011011110001000000001011001000110000011011100101010100111001001110110111001010001111001011011110011011101010011001110100001011011110011100111101101000101010001110111"
SEQS = [int(bin_s[i*16:i*16+16], 2) for i in range(len(bin_s)//16)]
print(SEQS)
for x0 in range(1000000):
    x = x0/1000000
    seqs = []
    for i in range(16*16//8):
        x = generate(x, r)
        seqs.append(int(x*22000))
    if SEQS==seqs:
        print(x0/1000000)
        break

# 这里需要用python2的md5...不管他了
x0 = 0.840264
flag = encrypt(flag_enc,key1, key2,x0,24,16)
flag_bytes = ""
for i in flag:
    flag_bytes+=chr(i)
print(md5(flag_bytes.encode("utf-8")).hexdigest())

扫一扫，分享到微信

微信分享二维码
本站总访问量： 总访客次数：

tag:

梦想是成为全栈佬并养一只猫