0CTF RSA?总结 || RSA学习笔记

果然不是信息安全专业的,只是自学会有很多技能点的缺失。

该题用的是中国剩余定理,顺便学了一遍RSA,发现了数学技能点的缺失

(PS: ^表示为次方,xor才是异或,%和mod为求余,/表示为整除)

RSA学习笔记

先来学学前置技能

前置技能

学前符号助记

$ x = y\ (mod\ n) $ 可以看成是 $ x \% n = y$
$ x \equiv y\ (mod\ n)$ 可以看成是 $ x \% n = y \% n$

欧拉函数

$$\phi(q) = \prod_{k=1}^∞ (1 - q^k)$$

然后在RSA中用到的性质:

m是素数时,有 $\phi(m) = m - 1$

当m, n互质时,有 $\phi(m*n) = \phi(m) * \phi(n)$

欧拉定理

设p和q互质,则 $q^{p-1} \equiv 1\ (mod\ p)$

根据前面这说的该公式的意义为: $q^{p-1} \% p = 1 \% p$
所以最后可以得出:$q^{p-1} \% p = 1$

模反元素

设x为q的模反元素,则x必须满足:

$q * x \equiv 1\ (mod\ p) \Longrightarrow (q*x) \% p = 1$

性质:

x为q的模反元素,则$x + kp$ 都是q的模反元素(k为整数)

模逆元

也就是上面说的模反元素的公式:$q * x \equiv 1\ (mod\ p)$等同于$x^{-1} \equiv q\ (mod\ p)$

中国剩余定理

已知p, q互质
$n = p * q$
$\begin{cases}
c_1 \equiv x \% p\\
c_2 \equiv x \% q
\end{cases}$
求 $c \equiv x \% n$

类似RSA?这题来举个例子:
已知存在三个互质数$n_1, n_2, n_3$
可以计算出
$$\begin{cases}
N = n_1 * n_2 * n_3\\
N_1 = N / n_1 = n_2 * n_3\\
N_2 = N / n_2 = n_1 * n_3\\
N_3 = N / n_3 = n_2 * n_1\\
d_1 = N^{-1}_1 (mod\ n_1)\\
d_2 = N^{-1}_2 (mod\ n_2)\\
d_3 = N^{-1}_3 (mod\ n_3)\\
\end{cases}$$

有存在一数x,已知
$$\begin{cases}
c_1 \equiv x \% n_1\\
c_2 \equiv x \% n_2\\
c_3 \equiv x \% n_3
\end{cases}$$

则我们可以求得:
$$
c \equiv x \% n \Rightarrow c \equiv (c_1N_1d_1 + c_2N_2d_2 + c_3N_3d_3) (mod\ N)
$$

欧几里德算法

公式:
$$gcd(a,b) = gcd(b, a\ mod\ b)$$
Python实现该算法:

1
2
3
4
5
6
7
8
9
10
def gcd(a, b):
while b:
a, b = b, a % b
return a
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a%b)

扩展算法:
扩展算法是已知a, b 求 $ax + by = gcd(a, b) = d$中的x, y
x和y是一个多解的集合,而扩展算法是计算其中的一个特解,而我们取的特解是在上面的欧几里德算法中最后一步:
$a = gcd(A, B)$
$b = 0$
这时候我们可以有特解$x = 1, y = 0$
$$gcd(a, b) * 1 + 0 * 0 = gcd(a, b)$$
那么怎么把这个算法扩展开来呢?最开始是
$$A_0x_0 + B_0y_0 = gcd(A, B)$$
在一次求余之后
$A_1 = B_0$
$B_1 = A_0 \% B_0$
这时候
$$A_1x_1 + B_1y_1 = gcd(A, B)$$
$$\Downarrow$$
$$B_0x_1 + (A_0 \% B_0)y_1 = gcd(A, B)$$
因为
$A \% B = A - (A / B) * B$
所以上面的式子可以转换成:
$$B_0x_1 + (A_0 - (A_0 / B_0)B_0)y_1 = gcd(A, B)$$
$$\Downarrow$$
$$A_0y_1 + B_0(x_1 - (A_0 / B_0)y_1) = gcd(A, B)$$
和最开始的式子比较,可以得出:
$$
\begin{cases}
x_0 = y_1\\
y_0 = x_1 - (A_0 / B_0)y_1
\end{cases}
$$
通过上面的算法,可以写出下面的代码:

1
2
3
4
5
6
7
8
def e_gcd2(a, b):
if b == 0:
x = 1
y = 0
return (a, x, y)
(ans, x, y) = e_gcd2(b, a % b)
x, y = y, x - a / b * y
return (ans, x, y)

由于数学知识的限制,只能用递归写出。下面是wp中别人用循环的方法:

1
2
3
4
5
6
7
8
def extended_gcd(aa, bb):
lastremainder, remainder = abs(aa), abs(bb)
x, lastx, y, lasty = 0, 1, 1, 0
while remainder:
lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
x, lastx = lastx - quotient * x, x
y, lasty = lasty - quotient * y, y
return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1

Other

经常看到的两个定义:

$lcm(x, y)$ x和y的最小公倍数
$gcd(e, l)$ e和l的最大公约数

RSA密钥生成

前置技能学完了,开始研究RSA了
在密钥中包含了两个数据:
公钥:(N, e)
私钥:(N, d)
下面来看看怎么求N, e, d这三个数

  • 搞出两个超大的互质数设为p和q

    p和q互质

  • p和q相乘得出密钥长度N

    $N = p * q$

  • 计算N的欧拉函数

    $\phi(N) = \phi(p*q) = \phi(p) * \phi(q) = (p - 1) * (q - 1)$

  • 然后通过随机数生成方法随机出一个e,必须满足两个条件

    $1 < e < \phi(N)$ 还有 e和$\phi(n)$为互质数

  • 再随机出一个d, 为e的模反元素

    $e * d \% \phi(N) = 1$

好了,三个值求出来了,现在来看看加解密
加解密都是对字符的二进制进行计算
假设明文是字符串mingwen则被加密的
$m = 0b01101101011010010110111001100111011101110110010101101110 = 30796695364658542$

加密

加密公式:密文$c \equiv m^e \% N$

解密

解密公式:明文$m \equiv c^d \% N$

由于明文和密文的长度皆小于N,所以上面的加密解密公式可以变成:
$c = m^e \% N$
$m = c^d \% N$

openssl简单用法小记

再来用openssl来生成个公钥私钥对

先生成私钥

1
2
3
4
5
$ openssl genrsa -out private.pem 1024
Generating RSA private key, 1024 bit long modulus
.......++++++
........++++++
e is 65537 (0x10001)

这里的e就是上面计算中的e,1024为上面计算中N的bits长度

1
2
3
4
$ cat private.pem
-----BEGIN RSA PRIVATE KEY-----
xxxxxxxxxxxxxxxxxxxxxxxxxxx
-----END RSA PRIVATE KEY-----

这就是私钥

再生成公钥

1
2
3
4
5
6
$ openssl rsa -in private.pem -pubout -out public.pem
writing RSA key
$ cat public.pem
-----BEGIN PUBLIC KEY-----
xxxxxxxxxxxxxxxxxxxxxxxxx
-----END PUBLIC KEY-----

查看密钥信息

查看公钥信息

1
2
3
4
5
6
7
8
9
$ openssl rsa -in public.pem -pubin -text
Public-Key: (1024 bit)
Modulus:
xxxxxxxxxxxxx
Exponent: 65537 (0x10001)
writing RSA key
-----BEGIN PUBLIC KEY-----
xxxxxxxxxxxx
-----END PUBLIC KEY-----

Modulus就是上面计算过程中的N,e为0x10001
查看私钥信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
$ openssl rsa -in private.pem -text
Private-Key: (1024 bit)
modulus:
xxxxxxxxxxx
publicExponent: 65537 (0x10001)
privateExponent:
xxxxxxxxxxx
prime1:
xxxxxxxxxxxxxx
prime2:
xxxxxxxxxxxx
exponent1:
xxxxxxxxxxxx
exponent2:
xxxxxxxxxxx
coefficient:
xxxxxxxxxx
writing RSA key
-----BEGIN RSA PRIVATE KEY-----
xxxxxxxxxxxx
-----END RSA PRIVATE KEY-----

私钥藏了所有的信息啊。。所以说如果私钥泄露了。。就GG了。。
$modulus = N$
$publicExponent = e$
$privateExponent = d$
$prime1 = p$
$prime2 = q$
$exponent1 = d \% (p-1)$
$exponent2 = d \% (q-1)$
$coefficient = q^{-1} \% p$

RSA?

然后来扯0CTF的RSA?这题,首先查看公钥的信息:

1
2
3
4
5
6
7
8
9
10
11
12
$ openssl rsa -in public.pem -pubin -text
Public-Key: (314 bit)
Modulus:
02:ca:a9:c0:9d:c1:06:1e:50:7e:5b:7f:39:dd:e3:
45:5f:cf:e1:27:a2:c6:9b:62:1c:83:fd:9d:3d:3e:
aa:3a:ac:42:14:7c:d7:18:8c:53
Exponent: 3 (0x3)
writing RSA key
-----BEGIN PUBLIC KEY-----
MEEwDQYJKoZIhvcNAQEBBQADMAAwLQIoAsqpwJ3BBh5Qflt/Od3jRV/P4Seixpti
HIP9nT0+qjqsQhR81xiMUwIBAw==
-----END PUBLIC KEY-----

从这里可以得到
$N = 0x2CAA9C09DC1061E507E5B7F39DDE3455FCFE127A2C69B621C83FD9D3D3EAA3AAC42147CD7188C53$
$e = 3$

然后用http://factordb.com/因式分解出了三个值
$p = 26440615366395242196516853423447$
$q = 27038194053540661979045656526063$
$r = 32581479300404876772405716877547$

接下来:
$\phi(p*q*r) = \phi(N) = \phi(q) * \phi(p) * \phi(r) = (p-1) * (q-1) * (r-1)$
$\phi(N) = 2329271097867038040364127327000042742184870900536 0280557445800298810723014218767619832560713992$

但是这时候出问题了,上面说了e和$\phi(N)$ 要互质数,但是 $\phi(N) \% e = 0$
所以不能通过求d来解密密文,不过我们仍然可知
$$c \equiv m^3 \% N$$

这时候就可以用到中国剩余定理了
$$m^3 \equiv c \% N$$
$$\Downarrow$$
$$\begin{cases}
m_1^3 \equiv c \% n_1\\
m_2^3 \equiv c \% n_2\\
m_3^3 \equiv c \% n_3
\end{cases}$$
$$\Downarrow$$
$$m \equiv (m_1N_1d_1 + m_2N_2d_2 + m_3N_3d_3)\ mod\ N$$
由于m是明文,小于N,所以可以直接得出
$$m = (m_1N_1d_1 + m_2N_2d_2 + m_3N_3d_3)\ mod\ N$$

然后计算$m_1^3 \equiv c \% n1$ 可以在这个网站中进行解密http://www.wolframalpha.com/

研究这研究了一个星期,表示心累,解密脚本看github那篇wp去吧。。撸BCTF去了。。。

文章目录
  1. 1. RSA学习笔记
    1. 1.1. 前置技能
      1. 1.1.1. 学前符号助记
      2. 1.1.2. 欧拉函数
      3. 1.1.3. 欧拉定理
      4. 1.1.4. 模反元素
      5. 1.1.5. 模逆元
      6. 1.1.6. 中国剩余定理
      7. 1.1.7. 欧几里德算法
      8. 1.1.8. Other
    2. 1.2. RSA密钥生成
      1. 1.2.1. 加密
      2. 1.2.2. 解密
      3. 1.2.3. openssl简单用法小记
        1. 1.2.3.1. 先生成私钥
        2. 1.2.3.2. 再生成公钥
        3. 1.2.3.3. 查看密钥信息
  2. 2. RSA?