密码学攻击之RSA:初见

密码学 8个月前 admin
240 0 0


  • RSA 基础加解密

  • 私钥  泄露

  • 欧几里得算法

  • RSA 额外相关参数

  • 已知 ,分解

  • 欧几里得拓展算法

  • 共模攻击

  • 广播攻击


在了解了一些基础的抽象代数基础知识以及数论四大定理后,我们就能完成一些基础的 RSA 题目了,也能够通过公式推导去理解攻击手法背后的数学原理。

RSA 基础加解密

设有明文 、公钥 、私钥 、密文 、模数 ,其中 为两个大素数(大于512比特)
RSA 的加密公式为
RSA 的解密公式为
其中 满足 表示为 的欧拉函数,决定式为

其中 的各个素因子(如果素因子重复也只计算一次)。这里由于 ,因此
另外根据欧拉函数的性质, ,而 而素数,因此 ,也能够得到
关于解密公式的正确性验证需要用到欧拉定理,具体过程这里就不再赘述了,我们在上一篇《密码学基础之数论四大定理》中已经介绍过了。另外在其中我们还介绍了 RSA-CRT 签名算法,因此如果相关参数 泄露,其造成的影响也不小于私钥 泄露。

私钥 泄露

根据 RSA-CRT 签名算法流程,如果我们已知
我们可以先计算
最后使用中国剩余定理即可计算得到
使用 sagemath,我们只需要一行代码即可完成计算
m = crt([mp,mq],[p,q])
不过又要泄露 ,还得知道 的分解 ,这个攻击的利用条件也过于严苛了。
问题不大, 我们有稍微普适一点的攻击手法。已知公钥对 ,只需要再加上一个 或者 就足够了。
已知
所以有
又因为
于是有 ,化作等式则有
那么根据费马小定理,对于任意整数 ,有
再将上面的同余式化成等式,就有
然后我们对 求一个最大公约数即可获得素数 ,从而分解了 ,也就能够完成任意由该模数生成的密文的解密了。

欧几里得算法

在上述攻击中我们构造出了 ,然后和 求最大公约数以分解出 。那么如何求最大公约数呢?我们使用欧几里得算法(天呐,我们在用两千多年前的算法)。
设有两个整数 的最大公约数,我们证明 为整除符号)
则有
由于  
因此
于是
时,我们定义
于是我们构建欧几里得算法(使用 python 语言)
def gcd(a,b):
    while b != 0:
        a,b = b, a % b
    return a
欧几里得算法的时间复杂度非常低,只有 ,是比线性复杂度还低的对数复杂度,因此即使 很大,我们也能够在极短的时间内计算出他们的最大公约数 。(不得不感叹一下两千年前古人的智慧)

RSA 额外相关参数

这种类型是简单 RSA 题目中出现比较多的,比较偏“数学题”。除了给出的基本 RSA 参数 之外的额外参数就是我们需要关注的点。一般涉及到公式的推导,利用已知信息构造式子求出一个 (或者 )的倍数 (或者 ) ,然后和 求一个 GCD 以分解 ,下面我们给出一个例子。

第一颗?:

import gmpy2
from Crypto.Util import number
FLAG = "************************************"
mybytes = FLAG.encode('utf-8')
flag = int.from_bytes(mybytes, 'little')
e = 65537
p = number.getPrime(2048)
q = number.getPrime(2048)
r = 663111019425944540514080507309
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
k = (p-r)*d
enc = gmpy2.powmod(flag, e, p * q)
print("n", p*q)
print("e", e)
print("k", k)
print("enc", enc)
看到题目,除了常规参数 外,我们还额外知道一个 ,其中 已知, 未知
由于
即有
这里我们并不知道 或者 ,但是有
于是
我们考虑使用费马小定理,设一个整数 满足
于是
因此有 ,和 求一个 GCD 就能得到 了。
使用 python,核心代码也只需要一行
p = gcd(pow(a,e*k+r,n)-a,n)

已知 ,分解

如果我们知道额外参数 的值,我们也能够利用 GCD 来分解模数
首先我们计算 。根据 的定义我们知道 的倍数。
由于 是偶数,因此 可以表示为 其中 为奇数且
根据费马小定理,对于每个 都有 ,于是 就是模 下的一个二次根。
我们知道理论上一个数的二次根有两个,一正一负,而根据前面的知识(引理 3),我们有 ,所以开根后 在模 下和模 下的子群中各有两个解(是分别在模 和 模 下的
然后我们使用中国剩余定理,于是表现出 1 在模 下有四个平方根。其中两个平方根是 ,另外两个是,其中 满足 (或者反一下)。
于是我们计算 ,当发现其值不为 时,就可以通过计算 或者 分解。
一个直截了当的论证表明,如果从中随机选择 ,那么序列中的一个元素 中是 的概率至少为,即随机选取一个 就能分解  的概率很高。(如果运气不好都没分解出来,那就再换一个

python 代码实现

from Crypto.Util.number import *

def factor_n_with_ed(n,e,d):  
    p = 1  
    q = 1  
    while p==1 and q==1:  
        k = e * d - 1  
        g = getRandomRange(0,n)  
        while p==1 and q==1 and k % 2 == 0:  
            k //= 2  
            y = pow(g,k,n)  
            if y!=1 and GCD(y-1,n)>1:  
                p = GCD(y-1,n)  
                q = n//p  
                return p,q
前面我们提到了欧几里得算法,那就不得不再提一下欧几里得拓展算法了。

欧几里得拓展算法

设有整数 ,其中 ,那么必然存在整数 满足 ,而使用欧几里得拓展算法就能够求出这样的

第二颗?:

,我们知道 ,我们跟踪一下使用欧几里得算法求它们最大公约数的流程
于是有
现在我们反一下,
替换一下有,, 整理一下
再将 替换一下有, , 整理一下
于是我们计算出来
欧几里得拓展算法的 python 代码实现
def exgcd(a, b):
    if (b == 0):
        return 10, a
    x, y, g = exgcd(b, a % b)
    x, y = y, x - a // b * y
    return x, y, g
另外,也可以直接调包
from gmpy2 import gcdext
那么,欧几里得拓展算法有啥用呢?

共模攻击

如果手中恰好有这么两条密文
并且运气不错,,那么我们就能够通过欧几里得拓展算法计算出  满足
这样我们再计算 ,于是在不知道 分解的情况下我们利用两条密文就成功解密出了明文
但是这样的场景也不现实,因为加密使用的公钥是消息接收者,怎么会有两个接受者的公钥有一样的模数呢?
更现实的场景是消息发送者使用所有消息接受者的不同公钥对 加密同一消息 得到不同的密文 并广播(也许会再给每一条密文加一个身份id表示)。消息接收者选择属于自己的那条密文,解密获得消息。

广播攻击

如果攻击者在信道中收集到了多条广播的密文

一般来说加密者喜欢选取的公钥指数是 这三个数(由于是 的素数,加密计算效率高)。假设公钥指数都是是 ,那么我们搜集了 条密文后,就可以通过中国剩余定理计算  crt([c1,c2,c3],[n1,n2,n3]) 得到 ,由于加密时要求 ,所以得到的就是 ,我们直接对其开 次根即可得到消息
同理如果公钥是 ,那就搜集 条,如果是 ,则需要 条。具体需要的条数为 ,其中 表示数据的比特长度。因此如果 在加密前未经过数据填充的话,则可以少搜集一些。
例如我们有 比特的 比特的消息,公钥 ,那么需要的密文数为 条。
同理,如果 ,而 的比特长度小于  的比特长度的 ,那么我们就只需要一条密文 ,直接对其开 次根即可。
可以看到,RSA 的各类攻击真离不开欧拉定理、费马小定理和中国剩余定理。


原文始发于微信公众号(Van1sh):密码学攻击之RSA:初见

版权声明:admin 发表于 2023年8月23日 上午10:44。
转载请注明:密码学攻击之RSA:初见 | CTF导航

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...