RSA加密之分解n攻击(二)

• 本篇文章主要学点其他分解RSA模数n的其他方法，依旧主要讨论正常RSA模数$n=pq$

• 本篇文章主要讲解的是如下几个部分：

工具分解

• 其实使用最多的工具就两个

工具分解 yafu

工具分解 factordb

费马分解

费马分解 推导

• 费马分解的适用条件主要针对的是$|p-q|$比较小的时候。与前面遇到的一些使用费马小定理分解的题型不同（虽然前面也被我笼统的称为费马分解，但是还是需要区别开来。）
• 接下来具体推导一下费马分解，首先确定已知条件：
  • 已知$(e,n)$是有效的RSA公钥对，并且$(d,p,q)$是对应的私钥对。在此类题型中，我们只知道加密后的密文$c$，以及RSA公钥对$(e,n)$，其他条件未知。
  • 对于费马分解的题型，题目中生成素数的规则会隐含一个已知条件，就是$|p-q|$会比较小，具体小多少目前不知道（没做过数据测试，但具体大小可能与开平方有关），这里我们默认$p>q$
  • 对于$n=pq$，我们就可以这样表示$p、q$，设$p=a+b,q=a-b$，通过这样表示，此时$n=pq=(a+b)(a-b)=a^{2}-b^{2}$
  • 接下来我们通过移项就会得到：$b^{2}=a^2-n$，这里就会有一个点由于$|p-q|$比较小，所以$|p-q|=|a+b-a+b|=2b$是比较小的。
  • 这个时候，我们就可以从$a=\sqrt{n}$，此时$a^{2}-n=0$，接下来逐步让$a=a+1$，也就是自增，此时如果找到了一个完全平方数，使得$b=\sqrt{a^{2}-n}$有解（也就是$a^{2}-n$是完全平方数），那么就可以完成分解了。

费马分解 板子

• 板子如下：

import gmpy2

def Fermat_factor(n):
    """
    :param n: 传入要分解的大整数n
    :return: 返回分解完成的素数p、q
    """
    a = gmpy2.iroot(n,2)[0]
    while True:
        B_pow2_candidate = pow(a,2) - n

        if gmpy2.is_square(B_pow2_candidate):
            b = gmpy2.iroot(B_pow2_candidate,2)[0]
            p = a + b
            q = a - b
            if n % p == 0 and p > 1 and p != n:
                print("✅factor success!")
                return p,q
        a = a + 1

费马分解 例题1

• 题目附件如下：

from Crypto.Util.number import *
import gmpy2
flag = b'NSSCTF{******}'

p = getPrime(512)
q = gmpy2.next_prime(p)
n = p*q
e = 65537
phi = (p-1)*(q-1)

m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

'''
n = 115637000420176820831322601039129424406844427046456738651883381559357542765613732363445112111006849040385859313572091386802534464534403117787314180179562651607533039692795522388596550968316951090748054495960090527479954143448774136390568881020918710834542819900918984139672802889774720153267841255456602500057
e = 65537
c = 98161406745910866780822530171878255235776133393411573803496865047700715941955255328757920065032397556905095591171977170479344602512244671081108703687450560269408412671849929423399172588599903975793985819498354819305128607934552101433664794909855378636055525016664559476808490723554481335856183927702549281730
'''

• p和q相差不大，可以直接工具分解，也可以直接进行费马分解。
• 这里直接附上exp：

from Crypto.Util.number import *
import gmpy2

def Fermat_factor(n):
    """
    :param n: 传入要分解的大整数n
    :return: 返回分解完成的素数p、q
    """
    a = gmpy2.iroot(n,2)[0]
    while True:
        B_pow2_candidate = pow(a,2) - n

        if gmpy2.is_square(B_pow2_candidate):
            b = gmpy2.iroot(B_pow2_candidate,2)[0]
            p = a + b
            q = a - b
            if n % p == 0 and p > 1 and p != n:
                print("✅factor success!")
                return p,q
        a = a + 1


n = 
e = 65537
c = 
p,q = Fermat_factor(n)
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))
"""
b'NSSCTF{so_closed}'
"""

p-1光滑分解

p-1光滑分解 推导

光滑数：

• 文字定义：一个正整数，它的所有素因子都不超过某个给定的上界B，这个正整数就是光滑数。

• 符号定义：如果整数$n$的素因子中，最大素因子满足：$P(n)≤B$，那么称$n$是一个B-光滑数(B-smooth number)

注解1：这里的上界$B$是可以灵活指定某个具体的数。例如，在以前的计算机中由于运算效率比较慢，那可能就将$2^{44}$次方作为界限$B$，而现在的计算机运算效率比较快，那可能就将$2^{55}$次方作为界限$B$

可能的注解2：这里的上界$B$可能可以是某个函数

• 接下来具体分析一下$p-1$光滑分解模数$n$的方法。首先我们需要确定已知条件：
  • 已知$(e,n)$是有效的RSA公钥对，并且$(d,p,q)$是对应的私钥对。在此类题型中，我们只知道加密后的密文$c$，以及RSA公钥对$(e,n)$，其他条件就不知道了。
  • 对于$p-1$光滑，其实我们还已知$p-1$可以分解成比较小的素数的乘积，也就是$p-1=p_1p_2...p_n$，其中还满足$p_1,p_2,...,p_n≤B$，其中只知道$B$，甚至可能$B$都不知道要自己确定，但不知道$p_1,p_2,...,p_n$
  • 以上就是$p-1$光滑分解模数$n$的已知条件了。
• 接下来就是推导过程，推导过程需要用上费马小定理：
  • 首先就是由于$p_1,p_2,...,p_n<B$，于是我们计算$B!=1*2*...p_1...p_2....p_k...p_n...(B-1)*B$
  • 于是就有$p-1|B!$，这样就可以得到$B!=k(p-1)$
  • 这个时候我们又要引入一个已知量$a$，这个已知量$a$通常是由随机数生成的，其中这个$a$不能是$p$的倍数
  • 这样就由费马小定理可以得到：$a^{B!}\equiv a^{k(p-1)}\equiv 1~mod(~p)$
  • 这样就可以从而可以得到：$a^{B!}-1\equiv 0~mod(~p)\Rightarrow a^{B!}-1=kp$
  • 此时使用$gcd(a^{B!}-1,n)$就可以求出$p$了
  • 但是在一般的求解中，并不会直接求$B!$，因为求100!已经就很大了，已经是非常足够了
  • 所以一般来说，我们都会找一个$M$满足$p-1|M,M|B!$，在计算$gcd(a^{M}-1,n)$就行了
  • 为了提高指数运算的效率，我们一般计算的就是模幂运算$a^{M}-1~mod(~n)$

p-1光滑分解 板子

• Python脚本如下，这个算法比较简单，并且有使用同余模幂的性质从而提高遍历效率。

import random
import math

def Pollard_factor(n,B):
    """
    :param n: 传入模数n
    :param B: 传入光滑数B
    :return: 分解n之后得到的其中一个素数p
    """
    g = random.randint(2,n)
    for i in range(1,B+1):
        g = pow(g,i,n)
        p = math.gcd(g-1,n)
        if p != 1 and p != n:
            print("[+]factor success!")
            return p

• 这里给一个普通遍历的Python代码，这个运算效率会低一点

import random
import math

def Pollard_factor(n,B):
    """
    :param n: 传入模数n
    :param B: 传入光滑数B
    :return: 分解n之后得到的其中一个素数p
    """
    x = 1
    g = random.randint(2,n)
    for i in range(1,B+1):
        x = x * i
        p = math.gcd(pow(g,x,n)-1,n)
        if p != 1 and p != n:
            print("[+]factor success!")
            return p

• 这里再给一个加了tqdm的Python脚本：

import random
import math
import tqdm
def Pollard_factor(n,B):
    """
    :param n: 传入模数n
    :param B: 传入光滑数B
    :return: 分解n之后得到的其中一个素数p
    """
    g = random.randint(2,n)
    for i in tqdm.tqdm(range(1,B+1),leave=True):
        g = pow(g,i,n)
        p = math.gcd(g-1,n)
        if p != 1 and p != n:
            print("[+]factor success!")
            return p

p-1光滑分解 例题1

• 题目来源：NCTF 2019childRSA | NSSCTF
• 题目附件如下：

from random import choice
from Crypto.Util.number import isPrime, sieve_base as primes
#from flag import flag
flag = 'flag{test_flag}'

def getPrime(bits):
    while True:
        n = 2
        while n.bit_length() < bits:
            n *= choice(primes)
        if isPrime(n + 1):
            return n + 1

e = 0x10001
m = int.from_bytes(flag.encode(), 'big')
p, q = [getPrime(2048) for _ in range(2)]
n = p * q
c = pow(m, e, n)
print(p,q)
print(n)
# n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
# c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108

• 这里注意到题目中生成素数是n *= choice(primes)，当p+1是素数时就返回，这边我们看看primes这个变量。
• 我们看到primes这个变量是最开始的1000个素数，用于检测素性的，都比较小。这里面的一个素数是104729，所以我们不妨设光滑数$B=104730$，接下来就可以进行分解了。

• exp如下：

from Crypto.Util.number import *
import gmpy2
import tqdm
n = 
c = 
#x = 2
#for i in tqdm.tqdm(range(1,104730),leave=True):
#    x = pow(x,i,n)
#    p = gmpy2.gcd(x-1,n)
#    if p != 1 and p != n:
#        print('factor success',p)
#        break
p = 178449493212694205742332078583256205058672290603652616240227340638730811945224947826121772642204629335108873832781921390308501763661154638696935732709724016546955977529088135995838497476350749621442719690722226913635772410880516639651363626821442456779009699333452616953193799328647446968707045304702547915799734431818800374360377292309248361548868909066895474518333089446581763425755389837072166970684877011663234978631869703859541876049132713490090720408351108387971577438951727337962368478059295446047962510687695047494480605473377173021467764495541590394732685140829152761532035790187269724703444386838656193674253139
q = n // p
e = 65537
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
flag = long_to_bytes(m)
print(flag)
# b'NCTF{Th3r3_ar3_1ns3cure_RSA_m0duli_7hat_at_f1rst_gl4nce_appe4r_t0_be_s3cur3}'

p-1光滑分解 例题2

• 题目来源：MoeCTF 2022smooth | NSSCTF

• 题目附件如下：

from Crypto.Util.number import sieve_base,isPrime,getPrime
import random
from secret import flag

def get_vulnerable_prime():
    p=2
    while True:
        for i in range(136):
            smallp=random.choice(sieve_base)
            p*=smallp
        if isPrime(p+1):
            return p+1

P=get_vulnerable_prime()
Q=getPrime(2048)
N=P*Q
e=0x10001

for i in range(1,P-1729):
    flag=flag*i%P

c=pow(flag,e,N)
print("c=",hex(c))
print("N=",hex(N))

'''
c= 0x3cc51d09c48948e2485820f6758fb10c7693c236acc527ad563ba8369c50a0bc3f650f39a871ee7ef127950ed916c5f4dc69894e11caf9d178cd7e8f9bf9af77e1c69384cc5444da64022b45636eeb5b7a221792880dd242be2bb99be3ed02c430c2b77d4912bec1619d664e066680910317c2bb0c87fafdf25f0a2400103278f557b8eca51d3b67d61098f1ab68da072bb2810596180afbc81a840cd24efef4d4113235160e725a5af4824dc716d758b3bc792f2458e979398e001b27e44d21682e2ef80ae94e21cd09a12e522ca2e569df72f012fa40341645445c6e68c6233a8a39e5b91eb14b1ccfa61c9bad25e8e3285a22da27cd506ddd63f207517a4e8ede00b104d8806ff4c0e3162c3de69169d7e584952655272b96d39d242bb83019c7eab1ceb0b4b287591e1e0a5b6378e70340a82d3430c5925d215f31fda6d9d0bccea240591b22a3d0f6b5bf4ddf1243d71aca0fd53045c352c8c5497ebcdbd7ac11083d63aba7c053604fda2430c317a4e04702b5ad539e110f101165b21dcd9fdb5ba7324acdba6a506244ce7c911197dfe067441fe7488d164c050f45ef6476aaf399cedde1793cceb8c21d88ec8ecf5e17df27586713d7dd9566ec5023cfef75422b73e2d5a932c661b3cfdf9c4bda12b64380d2be1aa957c3e1416e068937bafe79b8cf303296792388e9c197702e11e7ded6088ae992d352b23a4a27
N= 0xdc77f076092cbe81c44789ccfc1b2ca55eabae65f44cf34382799e8bbb42d4d6c032bd897c21df1da401929d82deb56264823a757f6cacf63e0037146026cbab32ab9e4abc783dcabaac2b7ccc439937be3ab0fbf149524ff29ef0fe6f27e45215d74b40597c70e8207159dc7f542c2a6828500016480053dfc2d8dbf8fcdf6700640184c8f3318f7aab2e17e116edf680592f5eae951159bb8c20cfbd0cbab8b4b95925b5068038d0377a55a4d346ebbf53a1c2943b7c17e1b9d4a1b77916da2e15140b05b96655906942a07d04b7e25fa7521b3b7ae26eda68375a8b8ef2d5b4704a28168b236de97f24a663f0d0a3aeab47767dfe75a21662f5f25ef7f7d4b25c90fd7bcdd7137c23f03b6ea4209f8fb9b4628355e6ad62e6467d26666d3d1b0e6f078c5f3866413a6fcd3c1dc2ff3a5ab286e339d5c72f4d2f0473a4faddcba6b031bb6ec226fd4b319834b5029f09ea0ffeb5b6ed182d5a13675571b6708c38299118043390343e2f79edebd2ae0e0a765a3aebf776f54ca983cdae8547547cfc8430f7222aefa77301d7cc7c03b1451b6603028b21fea869d35138a9c83919985a91b3fdfa934f25a442cc10349b0ed6f2ee3955d40249e8b3fb9f1955534ee06cee41a3ad2d6ff7dbdb0f01e47b9e4d04f65232f5579135ae035e8ba2d1fe6465a730dcc8b9ba3a558ab38f040ea510757d25e92f886c50c24ad967f1
'''

• 这题还是随机选择sieve_base里面的小素数作为p-1的因子，所以p-1是光滑的，分解n的思路和例题1大差不差。但是这题使用B=104730是分解不出来的，原因应该是某一个靠后面的小素数被选择了多次，这就使得阶乘没有办法被p-1整除。
• 此时我们就需要扩大B的范围，本题就选取B=104730*2就可以分解出来了。

import random
import math
import tqdm
def Pollard_factor(n,B):
    """
    :param n: 传入模数n
    :param B: 传入光滑数B
    :return: 分解n之后得到的其中一个素数p
    """
    g = random.randint(2,n)
    for i in tqdm.tqdm(range(1,B+1),leave=True):
        g = pow(g,i,n)
        p = math.gcd(g-1,n)
        if p != 1 and p != n:
            print("[+]factor success!")
            return p
B = 104730*2

c= 
N= 
p = Pollard_factor(N,B)
print(p)

• 接下来就是正常的解密，但是注意一点，解密之后的flag并不是正确的flag，而是经过阶乘后的flag：$flag = flag*(P-1730)!~mod(~P)$的结果。

• 这里出现了阶乘，我们需要想到威尔逊定理：若$p$是素数，那么就有$(p-1)!+1\equiv 0~mod(~p)$

• 我们想要获得原来的flag，将解密的flag再模乘$P-1729,P-1728,...,P-1$，这样就会得到：$flag*(P-1)!\equiv -flag(~P)$

• 这样真正的flag就可以这样表示：$flag_{T} = P-flag*(P-1)!$

• 最终exp如下：

import random
import math
import tqdm
from Crypto.Util.number import *
def Pollard_factor(n,B):
    """
    :param n: 传入模数n
    :param B: 传入光滑数B
    :return: 分解n之后得到的其中一个素数p
    """
    g = random.randint(2,n)
    for i in tqdm.tqdm(range(1,B+1),leave=True):
        g = pow(g,i,n)
        p = math.gcd(g-1,n)
        if p != 1 and p != n:
            print("[+]factor success!")
            return p
B = 104730*2

c= 
N= 
p =
q = N//p
e = 65537
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,N)
for i in range(p-1729,p):
    m = m * i % p
m = p-m
flag = long_to_bytes(m)
print(flag)

# b'moectf{Charming_primes!_But_Sm0oth_p-1_1s_vu1nerab1e!}'