RSA学习

发表于 更新于 阅读次数： 本文字数： 2.9k 阅读时长 ≈ 5 分钟

1.构造格解决RSA中m>n问题

首先我们肯定都对RSA加密以及解密原理有了一定认识，比如加密的这句代码：$c=m^e\mod(n)$通过这种方式来得到我们的密文c，但是这个方法有个前提就是m必须小于于n，原因下面再提。然后再看解密，$m=c^d \mod(n)$可以通过欧拉定理来证明这个过程得到$c^d\mod(n)=m\mod(n)$,显然我们能发现如果m大于n会导致得到的密文$newm=m\mod(n)$，我们得到的是newm，而不是m，所以就不完整了，自然还原出来的明文多半就是乱码，那么如何处理这类m>n的问题就是要学习的构造格。学习参考：2024-NSSCTF-密码工坊非官方dlc-wp-crypto | 糖醋小鸡块的blog

例题

1.1 2024羊城杯crypto RSA_loss

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
from gmpy2 import *
p = getPrime(100)
q = getPrime(100)
n = p * q
e = 65537
message = b""
m = bytes_to_long(message)
c = pow(m, e, n)
print(f'c = {c}')
print(f'p = {p}')
print(f'q = {q}')
d = invert(e,(p-1)*(q-1))
newm = pow(c, d, n)
print(long_to_bytes(newm))
#c = 356435791209686635044593929546092486613929446770721636839137
#p = 898278915648707936019913202333
#q = 814090608763917394723955024893
#b'X\xee\x1ey\x88\x01dX\xf6i\x91\x80h\xf4\x1f!\xa7"\x0c\x9a\x06\xc8\x06\x81\x15'

由题目可以知道进行了一个加密再解密的过程，最后解出来是乱码的原因也就是在于m大于n导致数据丢失了。

我们先猜测message范围是所有数字大小字母以及下划线，那么对应的ASCII码范围就在（48，128）之间，假设message长度为le，那么：
$$
m=256^{le-7}*pre+256m_0+suf
$$
(其中pre=b’DASCTF{‘,suf=b’}’,m_0为括号中间部分)。

那么就有：
$$
c=(256^{le-7}*pre+256m_0+suf)\mod(n)
$$
就能得到$m_0 \mod(n)$的值：
$$
m_0=256^{-1}(c-256^{le-7}pre-suf)\mod(n)
$$
然和记$m_0$每个字节为$s_i$从而用ascii的角度将其表示为：
$$
m_0=\sum_{i=0}^{le-9}256^{i}s_i=s_0+256s_1+256^{2}s_2+…+256^{le-9}s_{le-9}\mod(n)
$$
即可以写成：
$$
m_0=\sum_{i=0}^{le-9}256^is_i+kn
$$
就可以构造格来找目标向量:

$$
M = \left(
\begin{array}{*{7}{c}}
1 &0 &0 &0 & 0& 0& 1\\
0& 1 & 0& 0& 0& 0& 256\\
0& 0& \ddots & 0&0 &0 & \vdots\\
0& 0&0 & \ddots & 0&0 & \vdots\\
0& 0& 0& 0& 1 & 0& 256^{le-9}\\
0& 0& 0& 0&0 & 1 & -m_0\\
0&0 & 0&0 & 0&0 & n\\
\end{array}
\right)
$$
有:
$$
(s_0,s_1,…,s_{le-9},1,k)*M=(s_0,s_1,…,s_{le-9},1,0)
$$
这样解出来的向量预期就在48-128之间，范围太大了结果肯定不太行，优化方法就是令:
$$
t_i=s_i-88
$$
这样目标向量范围就为（-40，40）可以解了。

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

p = 898278915648707936019913202333
q = 814090608763917394723955024893
newm = bytes_to_long(b'X\xee\x1ey\x88\x01dX\xf6i\x91\x80h\xf4\x1f!\xa7"\x0c\x9a\x06\xc8\x06\x81\x15')
n = p * q
c = newm

prefix = b"DASCTF{"
suffix = b"}"
for le in range(33, 50):
    length = le - len(prefix) - len(suffix)
    #part1 remove prefix and suffix
    c -= 256^(len(suffix) + length) * bytes_to_long(prefix)
    c -= bytes_to_long(suffix)
    c = c * inverse(256,n) % n

    L = Matrix(ZZ,length+2,length+2)
    for i in range(length):
        L[i,i] = 1
        L[i,-1] = 256^i
        c -= 256^i*88

    L[-2,-2] = 1
    L[-2,-1] = -c
    L[-1,-1] = n
    L[:,-1:] *= n
    res = L.BKZ()
    for i in res[:-1]:
        flag = ""
        if(all(abs(j) <= 40 for j in i[:-2])):
            if(i[-2] == 1):
                for j in i[:-2][::-1]:
                    flag += chr(88 + j)
            elif i[-2] == -1:
                for j in i[:-2][::-1]:
                    flag += chr(88 - j)
        if(flag != ""):
            print(flag)
    c = newm
# o0p5_m3ssaGe_to0_b1g_nv93nd0

由于此题不知道长度所以找了一个范围进行遍历求解，然后找出有意义的输出