p-1光滑攻击

使用的条件

在这种类型下的RSA中，p会由多个小素数相乘的乘积加上1得到

$$ p=p_1p_2p_3...p_n+1 $$

光滑数的概念

在使用这个条件来解题之前，我们先要明确一个概念：光滑数

当一个数的最大素因子组不大于B时，我们可以称其为B-光滑数，例如6=2*3可以称其为3-光滑数，$12=2^{2}\ * 3$可以称其为4-光滑（因为$2^{2}$是最大的素因子组）数（注意我们也可以叫它5-光滑、6-光滑、n-光滑(n>3)）

p-1光滑攻击

对于p-1而言，它包含有许多小素数因子，我们假设它最大的素因子组为K，他的素因子为$p_1,p_2,...,p_n$,我们显然是有$(p-1)|k!$

根据欧拉定理，我们有

$$ a^{k!}\equiv a^{\delta (p-1)}\equiv1\ (mod\ p) $$

得到$a^{k!}-1=\beta p$，就有

$$ gcd(a^{k!}-1,n)=p $$

又因为p−1是由一些小素数相乘而来，所以k并不会很大，我们可以通过遍历的方式计算每一个$a^{x}−1$的值，如果它和n*的公因子不为1也不为n，则我们成功分解了n。

在具体计算中，可以代入降幂进行计算

$$ a^{(k+1)!} = (a^{k!}\ mod \ n)^{k+1}\ (mod\ n) $$

算法大致流程：

exp：

from Crypto.Util.number import *
from gmpy2 import *

def smooth_attack(n):
    a = 2
    m = 2
    while True:
        a = gmpy2.powmod(a, m, n)
        p = gcd(a-1, n)
        if p != 1 and p != n:
            return p
        m += 1

n = 53763529836257082401813045869248978487210852880716446938539970599235060144454914000042178896730979463959004404421520555831136502171902051936080825853063287829
e = 65537
c = 50368170865606429432907125510556310647510431461588875539696416879298699197677994843344925466156992948241894107250131926237473102312181031875514294014181272618

p = smooth_attack(n)
q = n // p
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
m = gmpy2.powmod(c, d, n)
print(long_to_bytes(m))

补充

通常情况下，我们的最大质因子组k可能会十分的大，我们所求的k！也会特别大，我们只需要找到一个数m能够覆盖p-1所有的因子即可，所以在通常的情况下我们会选择去构造一个M

$$ M=\prod_{i}{p_i}^{\lfloor log_{p_i}{k} \rfloor} $$

我们也是显然能够得到$(p-1)|M$

也能得到

$$ gcd(a^{M}-1,n)=p $$

也就是说构造出来了M我们便可以直接得到p为多少

（可若无法知道M，我们则需要想办法去覆盖n所有的质因子）

• k不可知时，我们可以划界，找一个$\xi$来替代k，若仍然不够大，再往上叠加找一个更大$\xi$
• 素因子不可知时，可以利用素因子表来进行穷举

对于我们寻找M的过程中，$a^M-1$的转移也可以通过下式实现

$$ a^{kM}\equiv(a^M\ mod\ n)^k \ (mod\ n) $$