Mamor's Blog
0%

RSA光滑数问题[未完待续]

发表于 更新于 分类于
本文字数： 16k 阅读时长 ≈ 15 分钟

简述

光滑数【Smooth number】： 指 可以分解为小素数乘积的正整数

B-Smooth数： 如果一个整数的所有素因子都不大于B 那称这个数位B-Smooth数【例如 12 = 223 所以 12是3-Smooth数】

当p是N的因数，并且 p-1 是 光滑数，可以考虑 Pollard’s p-1 算法分解N

当p是N的因数，并且 p+1 是 光滑数，可以考虑 Williams’s p+1 算法来分解N

p-1光滑

根据费马小定理

有： 若p ∤ a, 则a^(p−1) ≡ 1 (mod p)

则有： a^t*(p−1) ≡ 1^t ≡ 1 (mod p)

即 a^(p-1) -1 = k*p 【$a^{t(p-1)} - 1$ 是 $p$ 的倍数 】

Pollard’s p-1算法：

如果 p-1 是很小质数的乘积 那么 n! 就能被 p-1 整除。 即 n! = t(p-1) 【 (p-1) | B! 】

1
2
3
4
5
6
7
8
9
10
11
12
from gmpy2 import *
a = 2
n = 2
while True:
    a = powmod(a, n, N)
    res = gcd(a-1, N)
    if res != 1 and res != N:
        q = N // res
        print("p=",res)
        print("q=",q)
        break
    n += 1

[NCTF2019] childRSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from random import choice
from Crypto.Util.number import isPrime, sieve_base as primes
from flag import flag

def getPrime(bits):
    while True:
        n = 2
        while n.bit_length() < bits:
            n *= choice(primes)  # primes 为前10000个素数的列表
        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)
# n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
# c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108

p q 均属有 多个小指数乘积+1 得到 即 p-1为多个小指数的乘积。利用 Pollar’s p-1算法分解N

WP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from gmpy2 import *
from Crypto.Util.number import long_to_bytes

N = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
C = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108
e = 0x10001


# 直接套 Pollard's p-1算法 求出 p q 
# py下跑 sage跑有问题
a = 2
n = 2
while True:
    a = powmod(a, n, N)
    res = gcd(a - 1, N)
    if res != 1 and res != N:
        q = N // res
        print("p=", res)
        print("q=", q)
        break
    n += 1

d = invert(e, (res - 1) * (q - 1))
m = pow(C, d, N)

print(long_to_bytes(m))
# b'NCTF{Th3r3_ar3_1ns3cure_RSA_m0duli_7hat_at_f1rst_gl4nce_appe4r_t0_be_s3cur3}'

CryptoCTF 2022 Cantilever (60 solves) *

What if you can find the message? If you can, that means you are genius, because we harden our crypto system with a very modern tool!

Challenge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

def gen_primes(nbit, imbalance):
    p = 2
    FACTORS = [p]
    while p.bit_length() < nbit - 2 * imbalance:
        factor = getPrime(imbalance)
        FACTORS.append(factor)
        p *= factor
    rbit = (nbit - p.bit_length()) // 2

    while True:
        r, s = [getPrime(rbit) for _ in '01']
        _p = p * r * s
        if _p.bit_length() < nbit: rbit += 1
        if _p.bit_length() > nbit: rbit -= 1
        if isPrime(_p + 1):
            FACTORS.extend((r, s))
            p = _p + 1
            break

    FACTORS.sort()
    return (p, FACTORS)

def genkey(nbit, imbalance, e):
    while True:
        p, FACTORS = gen_primes(nbit // 2, imbalance)
        if len(FACTORS) != len(set(FACTORS)):
            continue
        q, q_factors = gen_primes(nbit // 2, imbalance + 1)
        if len(q_factors) != len(set(q_factors)):
            continue
        factors = FACTORS + q_factors
        if e not in factors:
            break
    n = p * q
    return n, (p, q)

nbit = 2048
imbalance = 19
e = 0x10001

m_1 = bytes_to_long(flag[:len(flag) // 2])
m_2 = bytes_to_long(flag[len(flag) // 2:])

n, PRIMES = genkey(nbit, imbalance, e)

c_1 = pow(m_1, e, n)
c_2 = pow(e, m_2, n)

print(f'n = {n}')
print(f'c_1 = {c_1}')
print(f'c_2 = {c_2}')

p-1 光滑

n 2^19-smooth

利用 Pollard p-1 算法分解n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from gmpy2 import *
from Crypto.Util.number import long_to_bytes

N = 7069789930583271525053215046247773438899869283661158227309691853515987055334306019600324056376312479212090202373516405860759222837585952590589336295698718699890424169542280710721069784487366121478569760563045886361884895363592898476736269784284754788133722060718026577238640218755539268465317292713320841554802703379684173485217045274942603346947299152498798736808975912326592689302969859834957202716983626393365387411319175917999258829839695189774082810459527737342402920881184864625678296442001837072332161966439361793009893108796934406114288057583563496587655548536011677451960307597573257032154009427010069578913
c_1 = 488692928085934899944055554857568564903346089951134051486941368561567330884363274156339625953702601270565654444836193796061118053575538224794730472032345171432952984560662218697488844007827176184413713651118743456250147472678673801728916283759932987216388378211555067885210167894310696549664382751443669387953644382833924884208966436685137553434532738845959014828804809425096115758364136546390809453200055265653531950423111482644330073443545410319576097902472017235065047191133112557289289189187696092145850680765843608118584107829268136014912479701945735063525799796920293418182776436767911172221104640501952880057
c_2 = 109770827223661560471527567179288748906402603483328748683689436879660543465776899146036833470531024202351087008847594392666852763100570391337823820240726499421306887565697452868723849092658743267256316770223643723095601213088336064635680075206929620159782416078143076506249031972043819429093074684182845530529249907297736582589125917235222921623698038868900282049587768700860009877737045693722732170123306528145661683416808514556360429554775212088169626620488741903267154641722293484797745665402402381445609873333905772582972140944493849645600529147490903067975300304532955461710562911203871840101407995813072692212
e = 0x10001

# 直接套 Pollard's p-1算法 通过c_1 求出 p q
a = 2
n = 2
while True:
    a = powmod(a, n, N)
    res = gcd(a - 1, N)
    if res != 1 and res != N:
        q = N // res
        print("p=", res)
        print("q=", q)
        break
    n += 1

d = invert(e, (res - 1) * (q - 1))
m = pow(c_1, d, N)

print(long_to_bytes(m))

# p= 83408372012221120677052349409462320990177094246143674474872152829440524098582262384066400107950985845255268335597502228206679771838750219696329523257176739436871327238322817403970284015587320158034304282786944710043150568360761457471641695390427267786485448748458445872307883254297662715749746270343116946519
# q= 84761154786085445040051273337185621770653977624442810400422736258693219544281946893222923335092616440575888204882883202879374137962201839964482318483860286412488851522612902055732831909496637360268825720155284438779235801463340052531340653630637729255285872455686692027630814695155220888112228977346697309127
# b'CCTF{5L3Ek_4s_'

c_1 = pow(m_1, e, n)

c_2 = pow(e, m_2, n)

c2 = e^ m_2 mod n e^m2 = c2 + k*n

c2 e n 都已知 求m2

m2 = loge(c2)

利用sage

GFp = GF(p) # 有限域

log(GFp(c_2), e)

离散对数 Pohlig-Hellman算法求m2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# sage
from Crypto.Util.number import *

n = 7069789930583271525053215046247773438899869283661158227309691853515987055334306019600324056376312479212090202373516405860759222837585952590589336295698718699890424169542280710721069784487366121478569760563045886361884895363592898476736269784284754788133722060718026577238640218755539268465317292713320841554802703379684173485217045274942603346947299152498798736808975912326592689302969859834957202716983626393365387411319175917999258829839695189774082810459527737342402920881184864625678296442001837072332161966439361793009893108796934406114288057583563496587655548536011677451960307597573257032154009427010069578913
c_1 = 488692928085934899944055554857568564903346089951134051486941368561567330884363274156339625953702601270565654444836193796061118053575538224794730472032345171432952984560662218697488844007827176184413713651118743456250147472678673801728916283759932987216388378211555067885210167894310696549664382751443669387953644382833924884208966436685137553434532738845959014828804809425096115758364136546390809453200055265653531950423111482644330073443545410319576097902472017235065047191133112557289289189187696092145850680765843608118584107829268136014912479701945735063525799796920293418182776436767911172221104640501952880057
c_2 = 109770827223661560471527567179288748906402603483328748683689436879660543465776899146036833470531024202351087008847594392666852763100570391337823820240726499421306887565697452868723849092658743267256316770223643723095601213088336064635680075206929620159782416078143076506249031972043819429093074684182845530529249907297736582589125917235222921623698038868900282049587768700860009877737045693722732170123306528145661683416808514556360429554775212088169626620488741903267154641722293484797745665402402381445609873333905772582972140944493849645600529147490903067975300304532955461710562911203871840101407995813072692212
e = 0x10001

p = 83408372012221120677052349409462320990177094246143674474872152829440524098582262384066400107950985845255268335597502228206679771838750219696329523257176739436871327238322817403970284015587320158034304282786944710043150568360761457471641695390427267786485448748458445872307883254297662715749746270343116946519
q = n // p

assert p*q == n

phi = (p-1)*(q-1)//GCD(p-1,q-1)
d1 = int(inverse(e, phi))

m1 = int(pow(int(c_1), d1,n))

# 定义有限域 GF(p) GF(q)
Fp = GF(p)
Fq = GF(q)

# c2 e 转换为 GF()中的元素
c2p = Fp(c_2)
c2q = Fq(c_2)
ep = Fp(e)
eq = Fq(e)

# 计算 loge(c2)
dp = discrete_log(c2p, ep)
dq = discrete_log(c2q, eq)
# 中国剩余定理CRT 计算 满足 m^e = c2 mod n 的 m的值
m2 = int(crt([dp,dq],[p-1,q-1]))

m = long_to_bytes(m1) + long_to_bytes(m2)
print(long_to_bytes(m1))
print(long_to_bytes(m2))
print(m)
# b'CCTF{5L3Ek_4s_'
# b'_s1lK__Ri9H7?!}'
# b'CCTF{5L3Ek_4s__s1lK__Ri9H7?!}'

p+1光滑

Williams’s p+1算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def mlucas(v, a, n):
    """ Helper function for williams_pp1().  Multiplies along a Lucas sequence modulo n. """
    v1, v2 = v, (v**2 - 2) % n
    for bit in bin(a)[3:]: v1, v2 = ((v1**2 - 2) % n, (v1*v2 - v) % n) if bit == "0" else ((v1*v2 - v) % n, (v2**2 - 2) % n)
    return v1

for v in count(1):
    for p in primegen():
        e = ilog(isqrt(n), p)
        if e == 0: break
        for _ in xrange(e): v = mlucas(v, p, n)
        g = gcd(v-2, n)
        if 1 < g < n: return g # g|n
        if g == n: break

综合例题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import gmpy2
from libnum import n2s,s2n
from Crypto.Util.number import getPrime
import random


def gen_prime(digit):
    primes = []
    pri = 1
    while(len(primes)<100):
        pri = gmpy2.next_prime(pri)
        primes.append(int(pri))
    while True:
        count = 2
        while count < 2**digit:
            count *= random.choice(primes)
        count += 1
        if(gmpy2.is_prime(count)):
            return count

def gen_prime_2(digit):
    primes = []
    pri = 1
    while(len(primes)<100):
        pri = gmpy2.next_prime(pri)
        primes.append(int(pri))
    while True:
        count = 2
        while count < 2**digit:
            count *= random.choice(primes)
        count -= 1
        if(gmpy2.is_prime(count)):
            return count

def generate(start, modulus, a, b, c, d):
    arr = []
    arr.append(start)
    arr.append(start+1)
    arr.append(start+2)
    for i in range(10**100):
        arr.append((a * arr[-3] + b * arr[-2] + c * arr[-1] + d) % modulus)
    return arr

p1 = gen_prime(256)
q1 = getPrime(256)
p2 = gen_prime_2(256)
q2 = getPrime(256)
assert p1 > q1
assert p2 > q2
n1 = p1 * q1
n2 = p2 * q2
print "n1 = %s" % str(n1)
print "n2 = %s" % str(n2)

r = getPrime(512)
print "r = %s" % str(r)

flag = "flag{xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx}"
m = s2n(flag)

arr = generate(m, r, p1, q1, p2, q2)

print "arr[10**100] = %s" % str(arr[10**100])
print "arr[10**100+1] = %s" % str(arr[10**100+1])
print "arr[10**100+2] = %s" % str(arr[10**100+2])

# n1 = 1122627862697321019530282965736391850755580895936802291161309915792429961624747356094273651528053737694375752383507509008511083571424513544351844231796981247
# n2 = 42452228756074949430200119187674072800166259263276225653674599426683428744745000585507174701894408343398957593869403921976682474759688236534918012868451437
# r = 12562551311997602982227662257453842057851021749009292708783465660065261139703971906109320639580310598023202634257624805719964182261882169860035285540999137
# arr[10**100] = 4838353389408955215917845462224851356983185785715321739245030612236910363177888113470205298612968999913978808363082599570155255107799227941046736259627961
# arr[10**100+1] = 10699223576890057648654189340104320126576219437282628103579325446469238279292850193524138389756436672641376651989022132710127197616146958216805814995598472
# arr[10**100+2] = 10255743354332378416989087696439685123717830836779737961024112448965245238772080092701344614830923313888435306261206177140560579750917219609679498132161402

分析

WP

References

https://blog.csdn.net/m0_51507437/article/details/124205732

欢迎关注我的其它发布渠道

------------- 💖 🌞 本 文 结 束 😚 感 谢 您 的 阅 读 🌞 💖 -------------