CTF导航 CTF导航

密码学攻击之RSA：初见

密码学 1年前 (2023) admin
271 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 1, 0, 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导航

相关文章

G.O.S.S.I.P 阅读推荐 2022-11-09
admin
540
密码学｜第五章 组合学、概率论与信息论
admin
601
【RAG入门必备技能】Faiss框架使用与FaissRetriever实现
admin
93
密码学 ｜ 5.4 碰撞算法与中间相遇攻击
admin
480
密码学 ｜ 5.3.4 随机变量
admin
424
密评梳理（附完整版PPT）
admin
103

暂无评论

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