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实现该算法：

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}
$$
通过上面的算法，可以写出下面的代码：

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中别人用循环的方法：

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来生成个公钥私钥对

先生成私钥

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

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

$ cat private.pem 
-----BEGIN RSA PRIVATE KEY-----
xxxxxxxxxxxxxxxxxxxxxxxxxxx
-----END RSA PRIVATE KEY-----

这就是私钥

再生成公钥

$ openssl rsa -in private.pem -pubout -out public.pem
writing RSA key
$ cat public.pem 
-----BEGIN PUBLIC KEY-----
xxxxxxxxxxxxxxxxxxxxxxxxx
-----END PUBLIC KEY-----

查看密钥信息

查看公钥信息

$ 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
查看私钥信息

$ 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?这题，首先查看公钥的信息：

$ 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去了。。。