非对称加密

crypto 备份
CTF
发布日期:   2021-09-02
更新日期:   2021-09-02
作者: Phoenix 文章字数:   3.2k
阅读时长:   14 分
阅读次数:  

非对称加密

RSA

在介绍RSA之前，默认已经掌握了一些基本的数论知识！

基本原理

公钥与私钥的产生

  1. 随机选择两个不同大质数 $p$ 和 $q$，计算 $N=p×q$
  2. 根据欧拉函数，求得$ φ(N)=φ(p)φ(q)=(p−1)(q−1)$
  3. 选择一个小于 $φ(N)$​ 的整数 e，使 $e$​ 和$ φ(N)$​ 互质。并求得 $e$​ 关于 $φ(N)$​ 的模逆元d，有 $ed≡1(mod\ φ(N))$​

此时，$(N,e)$是公钥，$(N,d)$ 是私钥。

消息加密

首先需要将消息 以一个双方约定好的格式转化为一个小于 $N$，且与 $N$ 互质的整数 $m$。如果消息太长，可以将消息分为几段，这也就是我们所说的块加密，后对于每一部分利用如下公式加密：
$$
m^e≡c\ (\ mod\ N)
$$

消息解密

利用密钥$d$进行解密。
$$
c^d≡m\ (\ mod\ N)
$$

正确性证明

即要证$m^{ed}≡m\ mod\ N$，已知$ed≡1\ mod\ ϕ(N)$，那么$ ed=kϕ(N)+1$，即需要证明

$m^{kϕ(N)+1}≡m\ mod\ N$

这里我们分两种情况证明

第一种情况 $gcd(m,N)=1$，那么 $m^{ϕ(N)}≡1\ mod\ N$,因此原式成立。

第二种情况 $gcd(m,N)≠1$，那么 $m$ 必然是$ p$ 或者$ q$ 的倍数，并且 $m$ 小于$ N$。我们假设
$$
m=xp
$$
那么 $x$必然小于 $q$，又由于 $q$ 是素数。那么
$$
m^{ϕ(q)}≡1\ mod\ q
$$
进而
$$
m^{kϕ(N)}=m^{k(p−1)(q−1)}=(m^{ϕ(q)})^{k(p−1)}≡1\ mod\ q
$$
那么
$$
m^{kϕ(N)+1}=m+uqm
$$
进而
$$
m^{kϕ(N)+1}=m+uqxp=m+uxN
$$
所以原式成立。

RSA攻击相关

直接模数分解

破解RSA的难点主要在于分解n，如果题中的n是可以直接分解的，一般用以下两种方法，一是用神器yafu分解，二是一个比较好的分解网站http://factordb.com/index.php。若以上两个都无法分解n，那么这题肯定是用其它方法。下面给出标准的RSA解密过程。

from Crypto.Util.number import long_to_bytes
from gmpy2 import modinv
n = 41376961156168948196303384218941117367850019509202049026037168194982219784159
e = 65537
c = 4161293100530874836836422603625206824589693933040432789074054165274087272587
# from yafu
p = 130451115685568383270871808144053983073
q = 317183651045971246384245233153006206783
# calc
d = modinv(e, (p - 1) * (q - 1))
m = pow(c, d, n)
print(long_to_bytes(m).decode())
# flag(rsa_256bit_brute)

公约模数分解

如果Alice和Bob之间进行了两次消息传递过程，且Bob不小心在两次通信中生成的大素数有一个是相同的，那么可以通过对两次通信的n求公约数进而分解两次通信的n。

其它模数分解

有的时候题目中会给出一些其它信息来辅助分解n。举个例子，有一题在提供了(n,e,c)的同时，还给出了npp的值，npp的值为$(p+1)(q+1)$。那么构造一个方程:$x^2-(p+q)x+p\times q=0$，此方程中(p+q)的值和pq的值都可以通过npp和n转化得到，而此方程的两个根即为p和q的值。

小指数明文爆破

如果Bob使用的e太小了，比如$e=3$，且Alice要传给Bob的明文也很小，比如就几个字节，那么由c=$m^e\ mod\ m$​​​，e=3，m很小，n很大，所以可能发生$m^e<n$，那么此时c=$m^3$​​​，直接对c开三次方根即可得到m。当然这是一种极端的情况。如果$m^3>n$但是没有超过太多，即$k\times n<m^3<(k+1)\times n$，且k是可以爆破大小的，则可以通过关系式$k\times n+c=m^3$​​​​来爆破明文。

$d_p、d_q$泄露

$$
d_p\equiv d\ mod\ p-1
$$

$$
d_q\equiv d\ mod\ q-1
$$

所谓$d_p、d_q$​泄露就是虽然知道N的分解，但不知道$e$​（也就不知道$d$），但是知道$d_p$​和$d_q$​可以通过计算得到明文$m$，这里需要用到中国剩余定理。

将$d$写成
$$
d=k(p-1)+d_p
$$
则
$$
m\equiv c^d\equiv c^{k(p-1)+d_p}\equiv c^{d_p}\ mod\ p
$$
同理
$$
m\equiv c^d\equiv c^{d_q}\ mod\ q
$$
对上两式利用中国剩余定理可得模$n$唯一解
$$
m\equiv a_1\times b_1\times p+a_2\times b_2\times q\ mod\ n
$$
其中
$$
a_1=c^{d_p}\ mod\ p
$$

$$
a_2=c^{d_q}\ mod\ q
$$

$$
qb_1\equiv 1\ mod\ p
$$

$$
pb_2\equiv 1\ mod\ q
$$

from Crypto.Util.number import long_to_bytes, inverse

p = 
q = 
dp = 
dq = 
c =
n = p * q
a1 = pow(c, dp, p)
a2 = pow(c, dq, q)
b1 = inverse(q, p)
b2 = inverse(p, q)
m = (a1 * b1 * q + a2 * b2 * p) % n
print(long_to_bytes(m).decode())

$d_p$泄露

$d_p$​​泄露是只知道一个$d_p$​​（或$d_q$​​）,但是知道e，在e不太大的情况下可以通过枚举来分解n。

已知
$$
d_p\equiv d\ mod\ p-1
$$

$$
ed\equiv 1\ mod\ (p-1)(q-1)
$$

则
$$
ed_p\equiv ed \equiv 1\ mod\ p-1
$$
写成
$$
ed_p=k(p-1)+1
$$
则
$$
k=(ed_p-1)/(p-1)<e
$$
只需枚举$k$，便能得到$p$。

from tqdm import tqdm
from gmpy2 import invert
from Crypto.Util.number import long_to_bytes

e = 
n = 
dp = 
p = 0
c = 
t = e * dp - 1
for i in tqdm(range(1, e)):
    if t % i == 0:
        if n % (t // i + 1) == 0:
            p = t // i + 1
            break
q = n // p
phi = (p - 1) * (q - 1)
d = invert(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m).decode())

上述方法在$e$​比较大时，枚举的时间复杂度就很高，事实上利用费马小定理有很巧妙的解法。
$$
a^{p-1}\equiv 1\ mod\ p
$$
而
$$
ed_p=k(p-1)+1
$$
则
$$
a^{ed_p-1}\equiv a^{k(p-1)}\equiv 1\ mod\ p
$$
写成
$$
a^{ed_p-1}=sp+1
$$
记
$$
b\equiv a^{ed_p-1}\equiv sp+1\equiv \ mod\ n
$$

$$
b=sp+1-tn
$$

从而
$$
p=gcd(b-1,n)=gcd(sp-tn,n)=gcd(sp,pq)
$$

from gmpy2 import invert, gcd
from Crypto.Util.number import long_to_bytes

e = 
n = 
dp = 
c = 
p = gcd(pow(3, e * dp - 1, n) - 1, n)
q = n // p
phi = (p - 1) * (q - 1)
d = invert(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m).decode())

Rabin密码体制

$Rabin$​密码与$RSA$​类似，取$e=2$​，且$p\equiv q\equiv 3\ mod\ 4$​​，下面是解密过程。

首先由加密过程$c\equiv m^2\ mod\ n$​​​，得$c\equiv m^2\ mod\ p$​​​和$c\equiv m^2\ mod\ q$​​​​，则$c$​​是模$p$​​和$q$​​​的二次剩余。利用二次剩余的欧拉判别法​
$$
c^{\frac{p-1}{2}}\equiv 1\ mod\ p
$$
回代
$$
m^2\equiv c*c^{\frac{p-1}{2}}\equiv c^{\frac{p+1}{2}}\ mod\ p
$$
开方得
$$
m\equiv \pm c^{\frac{p+1}{4}}\ mod \ p
$$
有
$$
m_1 \equiv c^{\frac{p+1}{4}}\ mod \ p
$$

$$
m_2 \equiv (p-c^{\frac{p+1}{4}}) \ mod \ p
$$

对$q$同理可得
$$
m_3 \equiv c^{\frac{q + 1}{4}}\ mod \ q
$$

$$
m_4 \equiv (q - c^{\frac{q + 1}{4}}) \ mod \ q
$$

然后从模$p$和模$q$的式子中各取一个，有四种可能，用四次中国剩余定理可以得到四个$m$​，明文为其中的一个。​

from gmpy2 import invert

n = 
p = 
q = 
e = 2
c = 
inv_p = invert(p, q)
inv_q = invert(q, p)

mp = pow(c, (p + 1) // 4, p)
mq = pow(c, (q + 1) // 4, q)

a = (inv_p * p * mq + inv_q * q * mp) % n
b = n - a
c = (inv_p * p * mq - inv_q * q * mp) % n
d = n - c

LLL-attack

如果Bob使用的e是3，同时Alice习惯性地在密文前面附上了一句众所周知的问候语，也就是说明，密文的一部分已经泄露，或者Bob不小心泄露了生成的p或者q的一部分，又或者Bob泄露了明文的部分bit。那么在泄露的信息长度足够的时候，可以通过Coppersmith method的方法求得明文。

假设已知m的一部分为base，此时可以使用LLLattack的方法进行攻击。目前GitHub上提供给了进行LLLattack的sage代码，地址为https://github.com/mimoo/RSA-and-LLL-attacks。

如遇到这类题，可以使用sage-online解决，修改LLLattack的源代码进行攻击。
以上方法同样适用p泄露了三分之二的情况。给出的代码在泄漏的字节略小于三分之二时也是可以接受的，在条件合适的情况下，1024bit的p只泄露了576bit的情况下也可以成功破解，链接地址为http://inaz2.hatenablog.com/entries/2016/01/20。

Wiener Attack &​ Boneh Durfee Attack

上两节的情况都是Bob选取的e太小造成的。如果Bob选择的e很大，但产生的d太小，也会被成功攻击。这就是RSA Wiener Attack。

一般来说，如果e很大，远远超过了65537，那么基本确定就是Wiener Attack。在GitHub上也有成功攻击的脚本，地址为https://github.com/pablocelayes/rsa-wiener-attack。

下面简单介绍Wiener Attack的原理。其成功的前提是$d<\frac{1}{3}n^{\frac{1}{4}}$

首先介绍连分数，对于任意一个整数都能展开成连分数
$$
x=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\frac{1}{\cdot}}}}
$$
在对一个分数展开成连分数的时候，事实上就是在对分子分母不断做辗转相除法，因此很快能得出一个结论：对于任意有理数(两个整数的比)的连分数永远是有限的。这很简单，对于两个数辗转相除，最终会停在两个数的最大公约数上，对于无理数也能连分数展开，例如π，e，无理数连分数展开是无限的。

对于连分数，我们观察每一个分母，它后面加的那一项都小于1,所以相比$a_i$是一个非常小的数，如果我们把第i个分母后面的分数全部略去，我们称这个分数为这个连分数第$i$个渐进分数，显然$i$越大离$x$越接近，并且由于约去了分母前$n-1$个渐进分数都是小于$x$​的。比如祖冲之发现圆周率的疏率和密率22 / 7与355 / 113 就是π连分数展开的两个渐进分数。

回到RSA，从下式开始
$$
ed-1=k\phi(n)
$$
变形
$$
\frac{e}{\phi(n)}-\frac{k}{d}=\frac{1}{d\phi(n)}
$$
考虑到$\phi(n)\approx n$
$$
\frac{e}{n}-\frac{k}{d}=\frac{1}{d\phi(n)}
$$
$d\phi(n)$是一个很大的数，所以不难发现$\frac{e}{n}$略大于$\frac{k}{d}$

为啥要这么写呢，因为e和n是我们是知道的，所以我们计算出e/N后，比它略小的k/d怎么出来呢，计算e/N的连分数展开，依次算出这个分数每一个渐进分数，由于e/N 略大于k/d，wiener证明了，该攻击能精确的覆盖k/d。

最终我们能算出$\phi(n)$​从而最终分解n，当然在那个过程中也是直接得到d。

共模攻击

Bob为了省事，在两次通信中使用了相同的n，而Alice是对相同的m加密。这时，Cat可以不计算d而直接计算m的值。

通过扩展欧几里得算法可以得到$(s_1,s_2),st$
$$
e_1s_1+e_2s_2=1
$$
而由
$$
m^{e_1}≡c_1\ (\ mod\ N)
$$

$$
m^{e_2}≡c_2\ (\ mod\ N)
$$

则
$$
c_1^{s_1}e_2^{s_2}\equiv m^{e_1s_1+e_2s_2}\equiv m\ mod\ n
$$
特别地，注意$s_1、s_2$中有一个人是负的，需要作一点转换。不妨$s_1$是负的，则
$$
c_1^{s_1}\equiv (c_1^{-1})^{-s_1}\ mod\ n
$$
其中$c_1^{-1}$为模逆元，而$-s_1>0$。

from gmpy2 import invert
def same_n_attack(n, e1, e2, c1, c2):
    def egcd(a, b):
        x, lastx = 0, 1
        y, lasty = 1, 0
        while (b != 0):
            q = a // b
            a, b = b, a % b
            x, lastx = lastx - q * x, x
            y, lasty = lasty - q * y, y
        return (lastx, lasty)
    s = egcd(e1, e2)
    s1 = s[0]
    s2 = s[1]
    if s1 < 0:
        s1 = -s1
        c1 = invert(c1, n)
    elif s2 < 0:
        s2 = -s2
        c2 = invert(c2, n)
    m = (pow(c1, s1, n) * pow(c2, s2, n)) % n
    return m

广播攻击

Bob不仅多次选择的加密指数低（例如3或其它较小的素数），而且这几次加密过程，加密的信息都是相同的，那么由：
$$
c_1\equiv m^e\ mod\ n_1
$$

$$
c_2\equiv m^e\ mod\ n_2
$$

$$
c_3\equiv m^e\ mod\ n_3
$$

那么通过中国剩余定理，可以计算出一个数$c_x$为：
$$
c_x\equiv m^3\ mod\ n_1n_2n_3
$$
然后对$c_x$开三次方即可得到m。Python代码如下

from gmpy2 import iroot
def broadcast_attack(data):
    def extended_gcd(a,b):
        x, y = 0, 1
        lastx, lasty = 1, 0
        while b:
            a,(q,b)=b,divmod(a,b)
            x, lastx = lastx - q * x, x
            y, lasty = lasty - q * y, y
        return (lastx, lasty,a)
    def chinese_remainder_theorem(items):
        N = 1
        for a, n in items:
            N *= n
        result = 0
        for a, n in items:
            m = N // n
            r,s,d=extended_gcd(n,m)
            if d!=1:
                N=N//n
                continue
            result += a * s * m
        return result % N
    x = chinese_remainder_theorem(data)
    m = iroot(x, 3)[0]
    return m
# 其中data=[(c1,n1),(c2,n2),(c3,n3)]

相关消息攻击

当Alice使用同一对公钥对两个具有某种线性关系的消息$M_1$​和$M_2$​进行加密，并将加密后的消息$C_1$​、$C_2$​发送给Bob时，我们可以获得对应的消息$M_1$​与$M_2$​、这里假设模数为N，两者之间的线性关系为$M_1=a\times M_2+b$​，那么当e=3时可以得到：
$$
M_2=\frac{2a^3bC^2-b^4+C_1b}{aC_1-a^4C_2+2ab^3}=\frac{bC_1+2a^3C_2-b^3}{aC_1-a^3C_2+2b^3}
$$

from gmpy2 import invert
def relate_message_attack(a, b, c1, c2, n):
    b3 = pow(b, 3, n)
    part1 = b * (c1 + 2 * c2 - b3) % n
    part2 = a * (c1 - c2 + 2 * b3) % n
    part2 = invert(part2, n)
    return part1 * part2 % n
文章作者: Phoenix
文章链接: https://ysy-phoenix.github.io/2021/090265116.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Phoenix !
crypto 备份
赏
  目录