分解n

介绍 #

素数分解问题是困难的，但是可以通过计算机进行暴力分解。通常意义上来说，一般认为 2048bit 以上的 n 是安全的

满足以下条件可以快速分解 n:

  • 如果 n 的大小小于 256bit，通过本地工具即可爆破成功，可以在几分钟内完成 256bit 的 n 的分解
  • 如果 n 在 768bit 或者更高，可以尝试使用一些在线的 n 分解网站(factordb.com)，这些网站会存储一些已经分解成功的 n
  • 如果在两次公钥的加密过程中使用的 n1 和 n2 具有相同的素因子，那么可以利用欧几里得算法直接将 n1 和 n2 分解。通过欧几里得算法可以直接求出 n1 和 n2 的最大公约数 p
  • 在 p，q 的取值差异过大，或者 p，q 的取值过于相近的时候，Fermat 方法与 Pollard rho 方法都可以很快将 n 分解成功。此类分解方法有一个开源项目 yafu 将其自动化实现了，不论 n 的大小，只要 p 和 q 存在相差过大或者过近时，都可以通过 yafu 很快地分解成功
题目也有可能提供其他信息用于快速分解n，如题目提供了gcd(n1,n2)=p，则能快速对n1/n2进行分解

Fermat’s factorization method #

此方法适用于 |p - q| 相差不大的情况下，p 或 q 近似等于 N 的平方根

N 为奇数，可以用2个 square 的差表示，当找到了这2个 square即找到了 对应的 N 质因数分解 N = a^2 - b^2 = (a + b)(a - b)

p = a + b, q = a - b，p 和 q很接近，python实现代码如下

import math

N = 55

a = math.ceil(math.sqrt(N))

while a < N:
    b = math.sqrt(a*a - N)
    if math.floor(b) == b:
        if (a+b) != 1 or (a-b) != 1:
            print("p is:", (a+b), "q is:", (a-b))
            break
    a += 1

References
https://fermatattack.secvuln.info/
https://en.wikipedia.org/wiki/Fermat%27s_factorization_method
https://math.stackexchange.com/questions/263101/prove-every-odd-integer-is-the-difference-of-two-squares

Pollard’s rho algorithm #

Pollard’s rho 算法是一种整数分解算法，分解计算的时间复杂度与被分解合数的最小质因数的平方根成正比，所以此方法适用于 |p - q| 相差较大即存在一个很小的质因数的情况下

理解该算法需要先理解以下前置知识：

  • 伪随机数数列
  • 生日悖论，Birthday problem
  • Floyd判圈算法，又称龟兔赛跑算法

伪随机数数列 #

使用一个多项式 mod n，g(x) = (x^2 + 1) mod n 来生成伪随机数数列，如开始值为 g(2)

x1 = g(2), x2 = g(g(2)), x3 = g(g(g(2))), ...

因为后一个数的取值取决于前一个数，所以中间一旦某个数 xi 出现重复(repeated)，则后续的数列会出现循环(cycle)

生日悖论 #

生日悖论是指在不少于 23 个人中至少有两人生日相同的概率大于 50%

1 - 两两不相同的概率
1 - 365/365 x 364/365 x 363/365 x (365-22)/365 > 0.5

这和我们的直观感觉不符合，因为我们一般会将自己带入，但是50%的概率是针对整体而言

对于算法的作用就是：如果我们不断在某个范围内[1,N]生成随机整数，很快便会生成到重复的数，期望大约在根号N级别

Floyd判圈算法 #

可以在有限状态机、迭代函数或者链表上判断是否存在环，求出该环的起点与长度的算法

可以用我们跑步的例子来解释：

  • 判断是否有环：如果两个人同时出发，如果赛道有环，那么快的一方总能追上慢的一方，追上时快的一方肯定比慢的一方多跑了几圈，多跑的长度是圈的长度的倍数
  • 求环的长度：设相遇点为B点，让其中一个人停在B不动，另一个一步一步向前走并记录步数，再次相遇时步数即为环的长度
  • 确定环的起点：方法是将其中一个指针移到链表起点，另一个指针为B点，两者同时移动，每次移动一步，那么两者相遇的地方就是环的起点

在算法中的用途是判断上述伪随机数数列是否存在环

算法思想 #

算法用于分解N，N = pq

使用g(x) = (x^2 + 1) mod n 来生成伪随机数数列 {xk}

2个数列 {xk} 和 {xk mod p}，2个数列分别在期望根号 N 和根号 p 时出现重复进而开始循环

使用序列中的2个数 xi 和 xj，xi 每次走一步，xj 每次走两步，判断 gcd(xi - xj, n) 是否等于 1，如果不等于1，则说明 {xk mod p} 数列出现了循环，

xi - xj 的差是 p 的倍数，如果 gcd(xi - xj, n) 大于1小于n，则找到了p。如果 gcd(xi - xj, n) 如果是n本身，则换一个伪随机数生成器重新执行算法

python实现代码如下

import math
import random

def pollard_rho(n):
    if n % 2 == 0:
        return 2
    
    x = y = 2
    c = 1

    d = 1
    
    def gcd(a, b):
        while b != 0:
            a, b = b, a % b
        return a
    
    def f(x):
        return (x**2 + c) % n
    
    while d == 1:
        x = f(x)
        y = f(f(y))
        d = gcd(abs(x-y), n)
    
    return d

def factorize(n):
    factors = []
    
    while n > 1:
        factor = pollard_rho(n)
        factors.append(factor)
        n //= factor
        
    return factors

# 示例用法
n = 987654321
factors = factorize(n)
print(f"Factors of {n}: {factors}")

题目 #

n = 0x888f5dc4bcc2384b948bbb07c8a4571c49d9f17dcf3f16f8801eec59580f10e264461753af699bc0d19a1311e50a1bfd892091751e005ed83038aa4ca8f74db64f7b033e6cc59e924c1c8f3b66208504d6fc7cc753060da5e56b1186e2e99332ee2c16775e33470fb49e80dfb821f2a6676360541bef23a1e8b2404d58a230605e360b3b
e = 0x10001
c = 0x2f3bc742059df8c4e1c951bf84a005d52a67300434c5b16d7e47f622831e2bce7402d2fc59ee16a73e0640f85ad93462948f66b0f3ed79dcf8403ad59433e7d838246d4fae570edf6feefaa34049072d51aa7e78b50846ffd8a79c613672534e9511990236cc566753ec0c4996cb0a4cc0f7429b8a3bf6312db5b8683a9ab4cbdc12fc40

思路 #

  • 使用yafu工具分解n

答案 先试用 yafu 进行分解得到 p 和 q

root@ctf-crypto:~# yafu
YAFU Version 2.11

>> factor(0x888f5dc4bcc2384b948bbb07c8a4571c49d9f17dcf3f16f8801eec59580f10e264461753af699bc0d19a1311e50a1bfd892091751e005ed83038aa4ca8f74db64f7b033e6cc59e924c1c8f3b66208504d6fc7cc753060da5e56b1186e2e99332ee2c16775e33470fb49e80dfb821f2a6676360541bef23a1e8b2404d58a230605e360b3b)
fac: factoring 411868939986456363373990173141778791902817011526575418612339832876100462958316233209828010224992434354613342590841746178700615197354061668001966691103301956982861535695157774527412186140547807215622989999341143026241272142696297783130879727847037082845435612822592859982970300687091786386580932104341934289646232406843
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
fac: no tune info: using qs/snfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 3, starting 1000 iterations on C318 
Total factoring time = 2.4719 seconds


***factors found***

P10 = 3056773583
P309 = 134739760339801511355180464192652894927487016144687553265975680501063942542687249207959414056802398882355606444287223539088212277760338675369259984573512966329132770346621310266476542675796805070604076206236025635740150317406187091852684245029683993721374558484135152898882632317976226892360228861720679915221

ans = 1

解题代码如下

import libnum

p = 3056773583
q = 134739760339801511355180464192652894927487016144687553265975680501063942542687249207959414056802398882355606444287223539088212277760338675369259984573512966329132770346621310266476542675796805070604076206236025635740150317406187091852684245029683993721374558484135152898882632317976226892360228861720679915221

e = 0x10001

c = 0x2f3bc742059df8c4e1c951bf84a005d52a67300434c5b16d7e47f622831e2bce7402d2fc59ee16a73e0640f85ad93462948f66b0f3ed79dcf8403ad59433e7d838246d4fae570edf6feefaa34049072d51aa7e78b50846ffd8a79c613672534e9511990236cc566753ec0c4996cb0a4cc0f7429b8a3bf6312db5b8683a9ab4cbdc12fc40

n = p*q

phi_n = (p-1)*(q-1)

d = libnum.invmod(e, phi_n)

m = pow(c,d,n)

print(libnum.n2s(m))

# flag{w3_May_pRim3_f@ct0riZe}
Edit Edit this page