CTF导航 CTF导航

RSA专题——模数分解

密码学 11个月前 admin
284 0 0
RSA 是公钥密码体制，至今也仍在众多协议如 TLS1.2 等中使用。因此其算法本身仍具有一定的安全强度。但是，实际应用中却存在诸多误用情况，从而导致被 RSA 加密的机密信息被破解、泄露。
不过在介绍 RSA 各种攻击场景之前，我们还是要简单了解一下RSA公钥加密体制。

RSA公钥加密体制

我们假设接受消息的人是Alice，发送消息的人是Bob

参数生成

Alice 随机生成两个大素数 （大于等于1024比特），计算 ，然后选择公钥  （一般为 65537），需满足 ，并生成相应的私钥 。总结一下，分别是
大素数：
大素数：
模数：
公钥：
私钥：
分类一下，分别记为公钥对 ，私钥对 
随后，Alice 将公钥对发送给 Bob，用于加密计算。

加密计算

Bob 将消息  编码成数字 ，随后使用公钥对  计算密文 ，然后 Bob 将密文  发送给 Alice。

解密计算

Alice接收到密文  后，使用私钥对  计算明文 

解密算法正确性的证明

即证明，其中我们会用到一个数学工具——欧拉定理。
欧拉定理：若为正整数，且互素（即），则有 。 已知 ，求证

等式左边为 

等式右边为  ∵ 

∴ 

∵ 

∴ 

∴ 

∵ 

∴ 

∴ 

∵ $m<n$< p=””></n$<>

∴ 

∴ 

等式右边等于等式左边，证毕。

应用示例

Alice 选择了两个素数  （实际上Alice应该选择更大的素数，但这里为了方便举例，我们选择了两个很小的素数），选择了公钥 ，满足 ，计算私钥  。因此有公钥对  ，私钥对 
Bob 加密信息 ，于是他计算 ，得到密文并发送给Alice
Alice 使用私钥解密，计算 ，成功解密获得明文。

分解模数

我们注意到，想要解密一段密文的关键是获得私钥 ，而计算私钥  依赖式子 ，由于公钥是公开已知的，因此我们只要知悉  即可求取私钥的。而 ，其中模数  ，并且由于  均为素数，因此  有唯一的因式分解（除去 1 和 n 本身） 。于是，解密 RSA 密文这个问题就可以规约到如何分解模数  这个问题上来。
当模数  较小时，我们可以通过蛮力爆破的方式，遍历小于  的所有数字来寻找  可能的因子。然而，当模数变得很大时（例如有两千比特，大约为  ），即使用已知最快的分解  的算法在有限时间内也是无法求解。RSA 正是基于这样的 大整数分解问题 来保证其安全性。
不过，准确的来说，大整数分解问题其实是一个平均困难问题，即大多数时候， 的分解时困难的，但是不免在有些“极端”情况  的分解是简单的。比如我们前面提到的  足够小，或者  有特殊的形式时。那么这这一篇文章主要就是给大家介绍一下一些模数  可以被分解的场景以及对应的算法。

模数因子相差过小

一般情况下，参数  都是随机生成，然后一同乘积得到 ，然而，如果  之间相差的过于小，甚至更极限， 是两个相邻的素数，那么  就很容易遭到分解。我们用一个简单的不等式就能说明：
假设我们有 ，，那么有不等式  
同时开二次根，我们得到 
因此，我们只需要对  进行开根，就能够得到  之间的一个数。根据素数定理，两个素数之间不会间隔的很大，于是我们从这个数分别往前遍历和往后遍历就能够找到素数  和素数 。

两个模数有公因子

如果存在两个模数 ，设有三个素数 ，并且 。如果  的长度足够，那么这两个模数单独取出来均是无法分解的。但如果它们同时出现，那么我们利用欧几里得辗转相除法（）即可在线性时间内得到其公约数 ，即分解了 。
使用python我们可以使用简洁的代码就编写出  函数，下面给出示例
def gcd(a,b):
    while b != 0:
        a,b = b,a%b
    return a

已知公私钥分解模模数

这是一个很经典的关系，在知道 RSA 公钥的前提下，计算出RSA 的私钥  和 知道模数  的分解 是充要条件。即如果知道  的分解，我们按照正常参数生成的流程就能够利用公钥计算出私钥；而如果我们知道私钥 ，我们也能够利用以下的方法，分解模数 。
当给定私钥 ，我们首先计算。根据  和  的定义我们知道  是  的倍数。由于  肯定是偶数，则其可以写为  ，其中  为奇数且。根据欧拉定理，对于每个  都会有 ，因此  就是模乘单位元  模  的平方根。根据中国剩余定理， 在模  下会有四个平方根。其中两个平方根是 ，另外两个是 ，而  则分别满足  和  或者  和  。因此当结果不为  时，我们可以通过计算  来揭示  的因式分解。一个直截了当的论证表明，如果从  中随机选择 ，那么序列中的一个元素 不为  的概率大约为 。而序列中的所有元素可以在时间内有效地计算，其中。
下面我们给出 python 代码示例
from random import *

def gcd(a,b):
    while b != 0:
        a,b = b,a%b
    return a


def factor_n_with_ed(n,e,d):  
    p = 1  
    q = 1  
    while p == 1 and q == 1:  
        k = e*d - 1  
        g = randint(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
接下来，我们介绍一种当模数  的一个因子  具有特殊构造（即  光滑）时的一种分解  的算法。

Pollard’s p−1 method

我们有一个整数 ，假设通过运气、爆破或其他方法，我们找到了一个具有以下性质的整数 ，

（ 整除符号）这意味着存在整数  以及  满足

考虑一下如果我们随机选择一个整数  并计算  会发生什么？根据费马小定理，我们知道

由于指数 ，所以  不太可能在模  下与 1 同余。因此随机选择一个整数 ，我们有很大的可能发现

这就意味着我们用简单的  算法就可以分解出  来：（可以意识到  算法在整数分解方面的用处很广）

这一切都很顺利，但你可能会问，我们在哪里可以找到这样一个指数 ，它可以被 整除，而不被 整除。 Pollard 观察到，如果  是由一系列小素数乘积而来，那么它就能整除 （主要针对那些不太大的 ，否则也算不出它的阶乘）。那么想法出现，对于 ，我们随机选择一个整数 ，并计算

（实际操作中我们通常简单的固定 ）如果  算法的结果是 ，那么我们继续用下一个 ，如果 gcd 的结果是 ，那么我们就不太幸运了，不过兴许换一个  就能够成功。如果我们得到了一个大于  小于  的整数，那么就意味着我们找到了  的一个非平凡因子，算法结束。

在我们准备用代码实现 Pollard‘s p-1method ’之前，这里有两个需要注意的点。

第一，我们需要关注  值的大小。尽管 ,我们也选一个大小适中的 ，我们直接计算  的值也是不太适合。因为  的十进制位长高达  ，这比宇宙中已知基本粒子的数量还要多。幸运的是，我们并不需要准确的计算出它，这里我们只关注 和  的最大公因子，因此计算  就足够了，然后我们再计算其与  的 gcd。因此我们实际上不需要处理比  大的数字。

第二，我们甚至不需要去计算指数 。假设我们在上一步已经计算好了 ，那么我们可以通过以下的式子计算下一个值

RSA专题——模数分解

应用示例

我们使用 Pollard’s p−1 method 去分解 ，从  开始，然后连续增大指数，计算阶乘，我们发现
从最后一行我们得到一个非平凡因子 ，是素数，另外一个因子 ，也是素数。
之所以我们在  成功，是因为这里我们  可以分解为如下小素数的乘积：

对于另外一个因子有 ，并不是由小（对于这里来说）因子乘积而来。

williams p+1 algorithm

选择一个大于 2 的整数 ，以下是Lucas序列：

其中所有运算都在模  下进行。
然后，当  是  的倍数时，任何奇素数  都会整除 ，其中  是雅各比符号。
我们要求 ，也就是说， 是模  的二次非剩余。但是由于我们事先不知道  ，因此在找到解之前可能我们需要不止尝试一个  值。如果，则该算法退化为慢版本 Pollard p − 1算法。
因此，对于不同的  ，我们计算 ，当结果不等于  或  时，我们则计算出了  的非平凡因子。
所使用的  的值是连续的阶乘，并且  是由  生成的序列的第  个值。
为了找到序列的第  个元素，我们以类似于从左到右求幂的方式进行，下面给出伪代码
x := B           
y := (B ^ 2 − 2) mod N     
for each bit of M to the right of the most significant bit do
    if the bit is 1 then
        x := (x × y − B) mod N 
        y := (y ^ 2 − 2) mod N 
    else
        y := (x × y − B) mod N 
        x := (x ^ 2 − 2) mod N 
V := x

应用示例

我们设模数 ，连续的  值为
V1 of seq(5) = V_1! of seq(5) = 5
V2 of seq(5) = V_2! of seq(5) = 23
V3 of seq(23) = V_3! of seq(5) = 12098
V4 of seq(12098) = V_4! of seq(5) = 87680
V5 of seq(87680) = V_5! of seq(5) = 53242
V6 of seq(53242) = V_6! of seq(5) = 27666
V7 of seq(27666) = V_7! of seq(5) = 110229.
这里我们有 ，因此  就是  的一个非平凡因子。注意到这里 ，数  是能够被 140 整除的最低阶乘，因此在一步中我们找到了  的一个非平凡因子。

小结

上面我们大致介绍了几种可以分解模数  的场景，大部分都是针对具有特殊非平凡因子的模数 。但其实分解模数的算法还远远不止于此，还有费马分解、已知最快的筛法，包括二次筛法、数域筛法等，详情可以阅读我们公众号【山石网科安全研究院】的密码学板块文章 《29. 3.7 Smooth Numbers Sieves Building Relations for Factorization》
       

原文始发于微信公众号（山石网科安全技术研究院）：RSA专题——模数分解

版权声明：admin 发表于 2023年5月30日 上午11:41。
转载请注明：RSA专题——模数分解 | CTF导航

相关文章

密码学 ｜ 5.3.4 随机变量
admin
392
密码学基础之线性代数 Ⅱ
admin
82
密码学 ｜ 6.3.1 二重加法算法
admin
299
密码学｜6.4.2 椭圆Elgamal公钥密码系统
admin
279
从抛硬币到泊松分布
admin
295
Shor量子算法推演与分析
admin
312

暂无评论

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

相关文章

A quick post on Chen’s algorithm
0
A quick post on Chen’s algorithm
0
RSA相关的趣味数学题(7)
0
DKG 协议的门限提升漏洞分析
0
G.O.S.S.I.P 阅读推荐 2024-02-19 密码学误用检测工具的误用？
0
再探格密码
0
成果分享|RRL：推荐系统逆向学习算法
0
密码学攻击之RSA：惊艳
0
椭圆曲线加密算法之Sony惨案模拟题的答案
0
椭圆曲线加密算法之Sony惨案模拟题
0