巧解picoCTF的RSA挑战题Sum-O-Primes

一个偶然的机会，接触到一道picoCTF的RSA挑战题Sum-O-Primes。这道题不难，了解RSA的基本算法就能做出来。另外，如果熟悉RSA算法演变的历史，还能找到第二种巧妙的快速解法。

xkcd-security

picoCTF项目

picoCTF是由卡内基梅隆大学的安全和隐私专家创建的一个免费的计算机安全教育项目，其通过建立于CTF（Capture the Flag，夺旗赛）框架之上的原创内容，以各种挑战的形式，为参与者提供系统学习网络安全知识并获取实践经验的宝贵机会。

picoCTF的练习题集合被称为picoGym。通用的题解是从给定的信息中搜索或破解出格式为“picoCTF{...}”的字符串，即要夺取的旗标。如下图所示，当前picoGym包含了271道网络安全挑战练习，内容涵盖一般技能、密码学、逆向工程、取证等领域。

Sum-O-Primes挑战

picoGym中密码学相关的挑战题有50道，其中一个就是Sum-O-Primes。此挑战的谜面很简单，其说明如下：

We have so much faith in RSA we give you not just the product of the primes, but their sum as well!

• gen.py
• output.txt

就是说我们不仅给出RSA所用的两个素数的乘积，还告诉你它们的和。具体是怎么给出的呢？这需要解题者自己去从剩下的信息中去发掘。点击给出的两个链接下载后，打开第一个Python文件：

gen.py

#!/usr/bin/python

from binascii import hexlify
from gmpy2 import mpz_urandomb, next_prime, random_state
import math
import os
import sys

if sys.version_info < (3, 9):
    import gmpy2
    math.gcd = gmpy2.gcd
    math.lcm = gmpy2.lcm

FLAG  = open('flag.txt').read().strip()
FLAG  = int(hexlify(FLAG.encode()), 16)
SEED  = int(hexlify(os.urandom(32)).decode(), 16)
STATE = random_state(SEED)

def get_prime(bits):
    return next_prime(mpz_urandomb(STATE, bits) | (1 << (bits - 1)))

p = get_prime(1024)
q = get_prime(1024)

x = p + q
n = p * q

e = 65537

m = math.lcm(p - 1, q - 1)
d = pow(e, -1, m)

c = pow(FLAG, e, n)

print(f'x = {x:x}')
print(f'n = {n:x}')
print(f'c = {c:x}')

如果你具备初级Python编程技能，并了解RSA算法的基本原理，应该可以很快读懂上面的程序。它所做的事情是：

1. 打开旗帜文件flag.txt读入内容。再使用hexlify和int函数将其转换为整数，结果存入变量FLAG。
2. 调用get_prime函数生成两个素数p和q，二者之和存入x，之积存入n。然后取e值为65537，计算出RSA私钥d。
3. 运用标准的pow函数执行模幂运算，实现RSA加密，将明文FLAG加密为密文c。
4. 打印输出x、n和c。

打开第二个文件，显然它就是Python第一个程序输出的结果：

output.txt

x = 154ee809a4dc337290e6a4996e0717dd938160d6abfb651736d9f5d524812a659b310ad1f221196ee8ab187fa746a1b488a4079cddfc5db08e78be0d96c83c01e9bb42420b40d6f0ad9f220633459a6dc058bb01c517386bfbd2d4811c9b08558b0e05534768581a74884758d15e15b4ef0dbd6a338bf1f52eed4f137957737d2
n = 6ce91e471f1df651b0d275d6d5522703feecdd77e7821a2caf9514104c059781c1b2e64772d9220addd657ecbd4e6cb8b5941608f6ab54bd5760074a5cd5854920439422192d2ee8912f1ebcc0d97714f209ee2a22e2da60e071541cb7e0772373cfea71831673378ee6432e63abfd14db0d4aa601928923253f9edd419ce96f4d68ce0aa3e6d6b530cd46eefbdac93038ce949c9dd2e573a47471cf8223f88b96e00a92f4d47fd277c42c4075b5e99b41a9f279f442bc0d533b9ddc50592e369e7026b3f7afaa8edf8972f0c3055f4de67a0eea963f099a32e1539de1d1727abadd9235f66371998ec883d1f89b8d907270842818cae49cd5c7f906c4752e81
c = 48b89662b9718fb391c96527272bf74c27810edaca09b63e694af9d11608010b1db9aedd1c867849371121941a1ccac610f7b28b92fa2f981babe816e6d3ecfab83514ed7e18e2b23fc3b96c7002ff47da897e9f2a9cb1b4e245396589e0b72affb73568a2016031555d2a46557919e44a15cd43fe9e1881d40dce1d1e36625e63b1472d3c317898102943072e06d79688c96b6ee2e584002c66497a9cdc48c38aa0548a7bc4fed9b4c23fcd493f38ece68788ef37a559b7f20c6941fcf8e567d9f50807259a7f11fa7a01d3125a1f7609cd94781f224ec8351605354b11c6b078fe015826342c3271ee3af4b99bb0a538b1e6b845594ee6546be8abd22ef2bd

理解了题意，就能马上做出判断——如果能从密文c解密出FLAG，就可以得到原始flag.txt的内容，即夺旗。

常规解法

RSA解密需要私钥指数\(d\)。参考下面的RSA算法步骤，很明显这要求先解出大素数\(p\)和\(q\)。

1. 选择两个大素数 \(p\) 和 \(q\)，计算 \(n=pq\)
2. 计算 \(n\) 的卡迈克尔函数 \(\lambda(pq)=\operatorname{lcm}(p − 1, q − 1)\)，\(\operatorname{lcm}\) 是求最小公倍数的函数
3. 选择一个小于 \(\lambda(n)\) 且与之互素的数 \(e\)，并求得 \(e\) 关于 \(\lambda(n)\) 的模逆元 \(d\equiv e^{-1}\pmod {\lambda(n)}\)
4. \((n,e)\) 是RSA公钥，\((n,d)\) 是RSA私钥
5. 使用公钥将明文\(m\)加密的计算公式是 \(c\equiv m^e\pmod n\)
6. 使用私钥将密文\(c\)解密的计算公式是 \(m\equiv c^d\pmod n\)

由此，挑战题转化为已知两个大素数的乘积\(n\)与和\(x\)，求这两个大素数。即求解二元一次方程组 \[ \left\{ \begin{aligned} p+q &=n \\ p*q &=x \end{aligned} \right. \] 运用初等数学的知识，可将以上的方程组变成一元二次方程` 显然\(p\)和\(q\)就是它的两个解。根据解题公式得到 \[(p,q)={\frac {x}{2}}\pm {\sqrt {\left({\frac {x}{2}}\right)^{2}-n}}\] 得到\(p\)和\(q\)，余下的工作就很简单了。由\(p\)和\(q\)算出\(d\)的代码可以直接从gen.py中第28、30和31行复制过来。最后的完整Python解题代码如下：

import math

file = open('output.txt', 'r')
Lines = file.readlines()
file.close()

x = int((Lines[0].split())[2], 16) # x = p + q
n = int((Lines[1].split())[2], 16) # n = p * q
c = int((Lines[2].split())[2], 16) # Ciphertext

def solve_rsa_primes(s: int, m: int) -> tuple:
    '''
    Solve RSA prime numbers (p, q) from the quadratic equation
    p^2 - s * p + m = 0 with the formula p = s/2 +/- sqrt((s/2)^2 - m)

    Input: s - sum of primes, m - product of primes
    Output: (p, q)
    '''
    half_s = s >> 1
    tmp = math.isqrt(half_s ** 2 - m)
    return int(half_s + tmp), int(half_s - tmp);  

# Now run with the real input
p, q = solve_rsa_primes(x, n)
m = math.lcm(p - 1, q - 1)
e = 65537
d = pow(e, -1, m)
FLAG = pow(c, d, n)
print(FLAG.to_bytes((FLAG.bit_length() + 7) // 8, 'big'))

上面的程序定义了一个通用的函数solve_rsa_primes求解两个大素数。在得出\(d\)之后，同样调用pow函数解密，最后将明文从大的整数转化为字节序列并打印输出。程序运行的结果是

b'picoCTF{pl33z_n0_g1v3_c0ngru3nc3_0f_5qu4r35_92fe3557}'

BINGO！夺旗成功！

注意： 函数solve_rsa_primes调用了math.isqrt计算整数平方根，这是必须的！如果误写成math.sqrt，就会出现如下的溢出错误

>>>
=============== RESTART: /Users/zixi/Downloads/Sum-O-Primes.py ==============
Traceback (most recent call last):
  File "/Users/zixi/Downloads/Sum-O-Primes.py", line 35, in <module>
    p, q = solve_rsa_primes(x, n)
  File "/Users/zixi/Downloads/Sum-O-Primes.py", line 31, in solve_rsa_primes
    tmp = math.sqrt(int(half_s ** 2 - m))
OverflowError: int too large to convert to float

这是因为math.sqrt是使用浮点数运算，但这里它无法将大的整数转换为浮点数。

快速解法

本题的常规解法要解一元二次方程，所以整数平方根运算必不可少。那么有不需要平方根运算的解法吗？答案是肯定的。

在原始的RSA论文中，公钥指数\(e\)和私钥指数\(d\)之间的关系是 \[d⋅e≡1\pmod{\varphi(n)}\] 这里模数为欧拉函数\(\varphi(n)=(p-1)(q-1)\)。由于\(\varphi(N)\)总是能被\(\lambda(n)\)整除，任何满足上式的\(d\)也满足\(d⋅e≡1\pmod{\lambda(n)}\)，所以私钥指数\(d\)并不唯一。虽然这时算出的\(d>\lambda(n)\)，但是应用到Sum-O-Primes题解，却可以避免平方根运算。这是因为

\[ \begin{aligned} \varphi(n)&=(p-1)(q-1)\\ &=pq-(p+q)+1\\ &=n-x+1 \end{aligned} \] 由此私钥指数\(d\)的计算公式变成 \[ \begin{aligned} d&≡e^{-1}\pmod{\varphi(n)}\\ &≡e^{-1}\pmod{(n-x+1)} \end{aligned} \] 既然\(n\)和\(x\)都是现成的，这种方法完全不必求出\(p\)和\(q\)，自然也就不需要平方根运算。此新解法的Python代码非常简洁

d1 = pow(e, -1, n - x + 1)
FLAG = pow(c, d1, n)
print(FLAG.to_bytes((FLAG.bit_length() + 7) // 8, 'big'))

print("d = ", d)
print("d1 = ", d1)
assert(d1>d)
print("d1/d = ", d1/d)

为了比较两种解法求出的\(d\)的不同，在末尾还加上了4行打印和断言语句。代码的执行结果是

>>>
=============== RESTART: /Users/zixi/Downloads/Sum-O-Primes.py ==============
b'picoCTF{pl33z_n0_g1v3_c0ngru3nc3_0f_5qu4r35_92fe3557}'
d =  1590433953643304448870807755026766943237397482033766155980367645454600169745357277163199312196609495875891431590581528929277583062406061101224041553945564552302546648687338536694903918084325519368961617691238793972703013656395301935576994660878296156727353260699130612675943209520489312860964899655070852366584778594425834982623831654304915478835573020874834723387183369976749895237126850604587166433366381884290402338703266523462767765540527102747754912478720160791675179128443712374832507705614160658601242723842366612805686436771142338154848447759947887908800687914418476358484536216953925324788380823429735298973
d1 =  11901952834426939436403812982514571575614906347331071933175950931208083895179963694981295931167346168378938101218143770786299673201984563299831132533757316974157649670783507276616478666261648674806749337918514985951832847720617452268824430679672778783943236259522437088812130196067329355430038927225825521934485847159262037514154059696664148362902872186817856316128403800463106817000251243818717005827615275821709043532925457271839955998044684537152992871171338447136672661193487297988293156428071068861346467230927990425182893890027896377626007826573834588309038513191969376781172191621785853174152547091371818954913
d1/d =  7.483462489694971

如上所示，此解法亦成功夺旗。新解法算出的\(d\)值（d1）是常规解法的7倍多。

本文全部的代码点击这里下载：Sum-O-Primes.py.gz