分解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\) 近似等于 \(\sqrt{N}\)

\(N\) 为奇数，可以用2个平方数的差表示，当找到了这2个平方数即找到了对应的 \(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判圈算法，又称龟兔赛跑算法

伪随机数数列 #

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

\[x_1 = g(2), \quad x_2 = g(g(2)), \quad x_3 = g(g(g(2))), \quad \ldots\]

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

生日悖论 #

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

\[1 - \frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \times \frac{365-22}{365} > 0.5\]
第1个人：生日随便取，概率 = 365/365

第2个人：不能和第1人相同，剩余 364 天可选，概率 = 364/365

第3个人：不能和前2人相同，剩余 363 天可选，概率 = 363/365

……

第23个人：不能和前22人相同，剩余 343 天可选，概率 = 343/365

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

对于算法的作用就是：如果我们不断在某个范围内 \([1, N]\) 不断随机取整数，大约只需取 \(\sqrt{N}\) 量级个随机数，就有超过 50% 的概率出现两两重复，因此期望是 \(O(\sqrt{N})\)

Floyd判圈算法 #

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

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

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

设相遇时龟走了 \(d\) 步，则兔走了 \(2d\) 步，两者都在 B 点，差距必须是环长的整数倍： \(2d - d = m\lambda \implies d = m\lambda\)，对于龟，\( \mu + k = d \implies \mu = m\lambda - k\)

则从 B 再走 \(\mu\) 步，刚好是"补完剩余的一圈"，必然落在入口处。

两者同时各走一步，走了 \(\mu\) 步后：

  • 指针1（从起点出发）：恰好走到环入口 C
  • 指针2（从 B 点出发）：从 B 再走 \(\mu = m\lambda - k\) 步
  • B点本身已经在环入口后 k 步处，则指针2当前的位置，\(k + m\lambda - k = m\lambda \bmod \lambda = 0\)，即指针2恰好也到达了环入口 C

对于算法的作用就是：判断上述伪随机数数列是否存在环

算法思想 #

算法用于分解 \(n\)，\(n = pq\)

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

2个数列 \(\{x_k\}\) 和 \(\{x_k \bmod p\}\)，2个数列分别在期望 \(\sqrt{n}\) 和 \(\sqrt{p}\) 时出现重复进而开始循环

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

存在 \(i \neq j\) 使得：

\[x_i \equiv x_j \pmod{p}\]

即 \(p \mid (x_i - x_j)\)

如果 \( 1 \lt \gcd(x_i - x_j,\ n) \lt n\) ，则找到了 \(p\)。如果 \(\gcd(x_i - x_j,\ n)\) 是 \(n\) 本身，则换一个伪随机数生成器重新执行算法，如更换代码中的 c = random.randint(1, n-1)，换起始点 x = random.randint(2, n-1)，换一个完全不同的多项式 g(x) = (x² + x + 1) mod n / g(x) = (x³ + c) mod 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