吃瓜杯

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 1.7k 阅读时长 ≈ 2 分钟

做了下闪电五连鞭，题出的很有意思，春哥从国外比赛扒的题（BCACTF）,难度不大，结合了RSA和相似矩阵

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
朋友们好。

今天，和大家，探讨一下，怎样打RSA置换闪电鞭。

要做到三点。

一：要做到问题真正的放松。但是线性代数基本知识要用好。这里面，该松的松，该紧的紧。松中有紧，紧中有松。这个问题非常复杂，在这里不多说。在问题的描述中有详细的解释；

二：要练好内功，你才能代码中发力，打出RSA置换劲儿。慢练，这是签到的……快练！下合上开，上合下开！所以，这个RSA置换劲儿啊……这个RSA和置换都在动啊……

三：要用高维的RSA置换劲儿，才能打出RSA置换闪电鞭。因为这个鞭的劲儿，你看……是不是，你看……都是高维的啊……

下面我打一个连五鞭啊……打了五鞭：一鞭，两鞭，三鞭，四鞭，五鞭。这五鞭要连次打，你看：实战时间，一定要动武，全身松好，用高维的劲，RSA置换劲儿！才能打出flag，打出RSA置换闪电鞭！

谢谢朋友们。

1bian

题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *

n = 8870619487339789349033932217513908953609539651949986489986889710933094577873155191810742828503059670650154455297603719
e = 3

with open('flag.txt', 'rb') as f:
    m = bytes_to_long(f.read())

assert n > m

Zn = Zmod(n)
P = PermutationGroupElement('(1,6)(2,3,5)(4,7)')
P = Matrix(Zn, P.matrix())

def encrypt(m):
    C = (m * P) ^ e
    return C.list()

\[ [0, 0, 0, 0, 0, 6940158573485767169443582872275118843545217792197971962103010557916847970940437712181778807436191892307187137338300231, 0, 0, 6940158573485767169443582872275118843545217792197971962103010557916847970940437712181778807436191892307187137338300231, 0, 0, 0, 0, 0, 0, 0, 6940158573485767169443582872275118843545217792197971962103010557916847970940437712181778807436191892307187137338300231, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6940158573485767169443582872275118843545217792197971962103010557916847970940437712181778807436191892307187137338300231, 0, 0, 0, 0, 6940158573485767169443582872275118843545217792197971962103010557916847970940437712181778807436191892307187137338300231, 0, 0, 6940158573485767169443582872275118843545217792197971962103010557916847970940437712181778807436191892307187137338300231, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6940158573485767169443582872275118843545217792197971962103010557916847970940437712181778807436191892307187137338300231, 0, 0, 0] \]

解

题目生成了一个置换群和对应的矩阵P，加密算法为 \[ C=(mP)^e=m^eP^e\\ P^3同样是个置换矩阵，并且元素全为1。所以C中的元素即为c=m^3 \] 又由于n易分解，所以就就化为了最简单的RSA

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

c=6940158573485767169443582872275118843545217792197971962103010557916847970940437712181778807436191892307187137338300231
n = 8870619487339789349033932217513908953609539651949986489986889710933094577873155191810742828503059670650154455297603719
e = 3
a=[35200554341 , 35592761021 , 48105446183 , 48479007809 , 50240938337 , 50769514811 , 62183036099 , 63345654131 , 66104249843 , 67515121673 , 67704082961]
p=1
for i in a:
   p*=i-1
d=gmpy2.invert(e,p)
print(long_to_bytes(pow(c,d,n)))
#ctfshow{W4r_Dull_Eeeee_LLL3333_A_n0_F14sH_@w@}

2bian

题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
import random
random.seed(0x36D)

n = 3950848271664122675439855009329233027357977239695163232943132810210035583520735079984423511153607529820284200137188647
e = 3

with open('flag.txt', 'rb') as f:
    m = bytes_to_long(f.read())

assert n > m

Zn = Zmod(n)
P = PermutationGroupElement('(1,14,25,8,23,15)(2,22,17)(3,18,13,33,11,30,26,27,10,6,16,31,28,21,29,36,7,9)(4,35,12,32,20,5,24)(19,34)')
P = Matrix(Zn, P.matrix())
A = Matrix(Zn, 36, 36, lambda x, y: random.randint(0, 0x36D))
B = A * P * A^-1

def encrypt(m):
    C = (m * B) ^ e
    return C.list()

\[ A是一个随机矩阵，但随机数种子是确定的，所以A是确定的\\ 所以B=APA^{-1}也是确定的\\ 加密算法C=(mB)^e=m^eB^e\\ 那么CB^{-3}的元素即为m^3\\ 然后就化到了第一问上 \]

解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import random
from Crypto.Util.number import *
random.seed(0x36D)

n = 3950848271664122675439855009329233027357977239695163232943132810210035583520735079984423511153607529820284200137188647
e=3
Zn = Zmod(n)
P = PermutationGroupElement('(1,14,25,8,23,15)(2,22,17)(3,18,13,33,11,30,26,27,10,6,16,31,28,21,29,36,7,9)(4,35,12,32,20,5,24)(19,34)')
P = Matrix(Zn, P.matrix())
A = Matrix(Zn, 36, 36, lambda x, y: random.randint(0, 0x36D))
B = A * P * A^-1
C#C太太太大了，不丢了
c=788338113035295195878123865420815134674503086857319693837443675089195439938279689750424184012172121716196117254817680
phi=euler_phi(n)

d=inverse_mod(e,phi)
print((C*B^-3).trace())
print(long_to_bytes(pow(c,d,n)))

3bian

之后都变成了nc题，并且能给我条件是矩阵的迹

题

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
from Crypto.Util.number import *
import random
random.seed(0x36D)

n = 25126409997644048715497037905442671105116158875704245711785280791201683049008805107543997350200944348915833337286069203
e = 3

with open('flag.txt', 'rb') as f:
    m = bytes_to_long(f.read())
assert n > m

Zn = Zmod(n)
P = PermutationGroupElement('(1,3,6,29,25,34,22,33,10,16,7)(2,21,19,17,31,9,5,30,27,35,32,11)(4,20,28,23,18,15)(8,26,14,12)(36,24,13)')
P = Matrix(Zn, P.matrix())
A = Matrix(Zn, 36, 36, lambda x, y: random.randint(0, 0x36D))
B = A * P * A^-1

def encrypt(m):
    C = (m * B) ^ e
    return C

matrix_map = {"I": Matrix(Zn, matrix.identity(36)), "B": B, "C": encrypt(m)}

def server_add(matrix_map):
    print("第一个矩阵：")
    A = input("> ").strip()
    print("第二个矩阵：")
    B = input("> ").strip()
    C = matrix_map[A]+matrix_map[B]
    print(f"这两个矩阵之和的迹是：{C.trace()}，迹你实在是太美~")
    return C

def server_product(matrix_map):
    print("第一个矩阵：")
    A = input("> ").strip()
    print("第二个矩阵：")
    B = input("> ").strip()
    C = matrix_map[A]*matrix_map[B]
    print(f"这两个矩阵之积的迹是：{C.trace()}，迹你实在是太美~")
    return C

def server_kproduct(matrix_map):
    print("矩阵：")
    A = input("> ").strip()
    print("乘数：")
    k = input("> ").strip()
    k = int(k)
    B = k * matrix_map[A]
    print(f"数乘结果的迹是：{B.trace()}，迹你实在是太美~")
    return B

def server_power(matrix_map):
    print("矩阵：")
    A = input("> ").strip()
    print("幂次：")
    k = input("> ").strip()
    k = int(k)
    B = matrix_map[A] ^ k
    print(f"求幂结果的迹是：{B.trace()}，迹你实在是太美~")
    return B

def server_save(A, matrix_map):
    print("存个小档？ (Y/N)")
    s = input("> ").strip().upper()
    if s == "Y":
        print("运算结果叫啥名呢？")
        S = input("> ").strip()
        matrix_map[S] = A
        print("存上档咯！")

WELCOME = """
欢迎来打第三鞭！
在这一鞭中，你可以尝试打出两个矩阵的和，积。
或者一个矩阵的数乘，幂次。
但是由于av50183113，所以我只会告诉你运算结果的迹，因为迹你太美。
"""

MENU = """
请开始你的表演：
[S] 打印矩阵
[+] 两矩阵相加
[*] 两矩阵相乘
[K] 一矩阵数乘
[^] 一矩阵求幂
[Q] 886
"""

print(WELCOME)

while True:
    print(MENU)
    try:
        opt = input("> ").strip().upper()
        if (opt == "S"):
            print("迹你太美……baby……迹你实在是太美……")
            for k, v in matrix_map.items():
                print(f"{k}: {v.trace()}")
        elif (opt == "+"):
            M = server_add(matrix_map)
            server_save(M, matrix_map)
        elif (opt == "*"):
            M = server_product(matrix_map)
            server_save(M, matrix_map)
        elif (opt == "K"):
            M = server_kproduct(matrix_map)
            server_save(M, matrix_map)
        elif (opt == "^"):
            M = server_power(matrix_map)
            server_save(M, matrix_map)
        elif (opt == "Q"):
            print("再见！")
            break
        else:
            print("李在……赣神魔？")
    except:
        print("这波和闪电鞭配合得不是很好……")

端口那边初始储存了三个矩阵，B、C和I，I即单位矩阵，能够进行矩阵相加、相乘、数乘、求幂、展示的操作并且给出的是结果矩阵的迹，也就是对角线上元素的和

我的解

由第二问可以知道，得到的\[C*B^{-3}\]的是一个对角阵，而且对角线上的元素全为\[m^3\]，已知矩阵是36x36的大小，所以迹=36*c，然后就可以解出m了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
import random
random.seed(0x36D)

n = 25126409997644048715497037905442671105116158875704245711785280791201683049008805107543997350200944348915833337286069203
e = 3

Zn = Zmod(n)
P = PermutationGroupElement('(1,3,6,29,25,34,22,33,10,16,7)(2,21,19,17,31,9,5,30,27,35,32,11)(4,20,28,23,18,15)(8,26,14,12)(36,24,13)')
P = Matrix(Zn, P.matrix())
A = Matrix(Zn, 36, 36, lambda x, y: random.randint(0, 0x36D))
B = A * P * A^-1
print((P^12).trace())
D=B^3

c=(9857562962643282087288501924102632185114609865442470151120627871503036282427052725871725631485463201834546369527295236*inverse_mod(36,n))%n
phi=euler_phi(n)
d=inverse_mod(e,phi)
print(long_to_bytes(pow(c,d,n)))

出题人的wp

出题人想法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
# Put the trace of the cipher here
tr = 14813573939127972566346276778703360636838383920024039547829404416974023159738670520401495234532257783312488372282988720
# 3 * m^3
n = 25126409997644048715497037905442671105116158875704245711785280791201683049008805107543997350200944348915833337286069203
e = 3
fac = factor(n)
cs = []
ns = []
for p, alpha in fac:    
    PR.<x> = PolynomialRing(Zmod(p))   
    f = 3 * x^3 - tr    
    cs.append(int(f.roots()[0][0]))    
    ns.append(p)
m = crt(cs, ns)
print(long_to_bytes(m))

用CRT的思想就是将一个大问题拆分成几个小问题，然后求解出更易求得的小问题，再用CRT算法求出原问题的解，学到了

4bian

这一题e=17，每次nc后n随机给出，n还是满足易分解的特点；

这次没有给出矩阵B的生成方式，但是通关trace(I)=88可以判断出矩阵的阶数是88；

但是得到的trace(B)=trace(C)=0，测试后发现\[trace(CB^{-17})!=0\]，所以就转换到3bian上了

1
2
3
4
5
6
7
8
9
from Crypto.Util.number import *

n = 3517510500012578106622165513758529071479627734667631280414059054641298876493975288768988113516424615888881460323558373
e = 17

c=(1085260800784001954133584897165283180613148497110186223344717673152088774523221770328958058661702434339964578373746248*inverse_mod(88,n))%n
phi=euler_phi(n)
d=inverse_mod(e,phi)
print(long_to_bytes(pow(c,d,n)))

出题人的WP

4bian

思路是试出使得C的迹不为0的幂次，然后使用相关明文攻击进行多项式辗转相除，构造拿到密文c。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
n = 3525391383893454949178974275545607641708362073574956727334904966529494223283130893750994940957609615705033001171886177
tr1 = 3049270810698445654099605477449981251458767119860329568250296940497378143674701051415025737368773161813012045690902750
tr2 = 2188079608695802322451864004898125123944812594307497345389217291001509103650388567869655694926044170369531992486933204

PR.<x> = PolynomialRing(Zmod(n))
f1 = 12 * x^12 - tr1
f2 = 49 * x^49 - tr2
def compositeModulusGCD(a, b):    
    if (b == 0):        
        return int(-a.monic().coefficients()[0])    
    else:        
        return compositeModulusGCD(b, a % b)
c = compositeModulusGCD(f1, f2)
e = 17
d = inverse_mod(e, euler_phi(n))
m = pow(c, d, n)
print(long_to_bytes(m))

5bian

在4bian的基础上，使得每一个操作只能使用一次；

但是trace(C)不为0，因此找到trace(B)不为0的一组，由\[trace(C)=m^etrace(B)\]，直接拿到c

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

n = 3292011909327659421775049456711303402369135799358104929999970787062175640424891481702884769338853356800690265327619267

e = 0x1337



#c=(1085260800784001954133584897165283180613148497110186223344717673152088774523221770328958058661702434339964578373746248*inverse_mod(88,n))%n
c=2507485887326570401463415497945317383847101547433009173857509227786381170695740614311577886312431809984908609722898546
phi=euler_phi(n)
d=inverse_mod(e,phi)
print(long_to_bytes(pow(c,d,n)))