RSA(1) - crypto - 网络安全 | Xming = 世界如此美好，我想体会三万种人生

# RSA(1)

# 生成公私钥

选取两个不同的大素数 p 和 q ，计算 N=p*q 。
求欧拉函数值 φ*(N)=φ(p)φ(q)=(p−1)(*q−1)。
选择一个小于 φ(N) 的整数 e ，并且满足 e 和 φ(N) 互质，求得 e 在模 φ(N) 意义下的乘法逆元 d，有 ed≡1 (modφ(N))。
销毁 p 和 q 。

此时（N，e）为公钥，（N，d）为私钥。

互质：两个正整数只有一个公因数 1 时，则称其为互质。
欧拉函数 φ(N)：小于或等于 N 的正整数中与 N 互质的数的数目
若 p 为素数，则 φ(p)=p−1 (因为每一个小于 p 的数都与 p 互质。)
又有若 N=p⋅q，则 φ(N)=φ(p)φ(q)。
由此我们有在 RSA 中，φ(N)=(p−1)(q−1)。
乘法逆元：
在加法中，我们有 a+(−a)=0，我们称其互为相反数。
在乘法中，我们有 a⋅(1/a)=1，我们称其互为倒数。
在矩阵中，我们有 M⋅M^(−1)=E，我们称其为逆矩阵。
但是其实我们可以用一个统一的称呼：逆元，即某种运算下的逆元素，我们会发现，元素和其逆元素进行运算之后总是一个定值，实际上在代数中，他们构成了一个群（不用深究），而我们进行要了解则是在模意义下的乘法逆元。
在模 p 意义下，指的是后续的所有运算都是在模 p 的条件下满足，例如 3⋅4≠1
但 (3⋅4) mod 11=(1) mod 11，对于这种式子我们称其为同余式，并且有专门的同余符号进行表示
$3*4\equiv1\pmod {11}$
所以参考上面乘法中的逆元运算规则，在模意义下则有
$a*a^{-1}\equiv1\pmod p$
我们称 a 和 a^(−1) 互为在模 p 意义下的乘法逆元。例如上述中的 3 与 4 互为在模 11 下的乘法逆元。

# 加密

$c\equiv m^e \pmod N$

得到密文 c。

# 解密

$m\equiv c^{d} \pmod N$

得到明文 m。

# 欧拉函数

求解欧拉函数值

$\phi(n) = \prod_{i=1}^{r} p_i^{k_i - 1} (p_i - 1)$

# 模的性质

同余：
若 a mod p = b mod p，则称 a 与 b 在模 p 意义下同余，记作：
$a\equiv b\pmod p$
对称性：
$a\equiv b\pmod p~~~与~~~b\equiv a\pmod p~~~等价。$
传递性：
$若a\equiv b\pmod p且b\equiv c\pmod p，则a\equiv c\pmod p$
结合律：
$((a+b)~mod~p+c)~mod~p=(a+(b+c)~mod~p)~mod~p$
交换律：
$(a+b)~mod~p=(b+a)~mod~p$
分配律：
$(((a+b)~mod~p)*c)~mod~p=(ac~mod~p+bc~mod~p)~mod~p$

# gmpy2

# gmpy2 安装

找到 [Release 2.1.0rc1] 下载对应版本的 whl 文件。 cp36 代表 Pythone3.6，x86 代表 Windows64 位，其他同理。

打开终端，输入 pip install gmpy2-2.xx-cpxx-xxxxxx.whl，其中 gmpy2-2.xx-xxx 是你下载的完整文件名，即可安装成功。

# gmpy2 求解代码

1
2
3

sn=isqrt(n)
q=next_prime(sn)
p=n//q

# 费马分解

当 p 和 q 值比较接近时可用费马分解。

$\frac{(p+q)^2}{4}-n=\frac{(p+q)^2}{4}-pq=\frac{(p-q)^2}{4}$

def fermat_attack(n):
    a = isqrt(n)
    b2 = a*a - n
    b = isqrt(n)
    count = 0
    while b*b != b2:
        a = a + 1
        b2 = a*a - n
        b = isqrt(b2)
        count += 1
    p = a+b
    q = a-b
    assert n == p * q
    return p, q

遍历大于 n 的每一个整数 x，若满足 x^{2−n 为平方数，即 x}2−n=y^2*x*2−n=*y^{*2，则有 x}2=((p+q)^2)/4,y2=((p−q)^2)/4
解上述式子，即可得到 p,q。

# 已知素数求解明文

# 三素数

$已知p1，p2，q，则有n1=p1*q，n2 = p2 * q。$

# 三素数因子

已知 p，q，r

$φ(N)=φ(p)φ(q)φ(r)=(p−1)(q−1)(r-1)$

推广

$φ(N)=φ(p_1)φ(p_2)φ(p_3)...φ(p_i)=(p_1−1)(p_2−1)(p_3-1)...(p_i-1)$

# 多素数

已知 n=p^3*q

$φ(N)=φ(p^3)φ(q)=p^2(p-1)(q-1)$

\begin{flalign} & r=2r_n*e+1 & \end{flalign}
$φ(N)=φ(p)φ(q)φ(r)=(p−1)(q−1)*2r_n*e$
$c_1=c~mod~pq=(m^e~mod~n)~mod~pq=m^e~mod~pq$
$ed_1≡1(~mod~φ(pq))$
$c_1^{d_1}≡m(~mod~pq)$
即 c1 为 c 再模 pq 的结果，根据模的性质有 c1 便是消息使用公钥 *(pq,e) 加密的结果，那么此时我们可以求出该公钥对应的私钥进行解密，得到 m mod pq * 的结果，又因为 m 比较小，所以该结果直接就是 m。

# 不互素

不互素且 m 比较小的情况

$m^2~~mod~~n$

crypto