惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

量
量子位
cs.AI updates on arXiv.org
cs.AI updates on arXiv.org
F
Fortinet All Blogs
博
博客园 - 聂微东
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
Hugging Face - Blog
Hugging Face - Blog
V
Visual Studio Blog
小众软件
小众软件
有赞技术团队
有赞技术团队
雷峰网
雷峰网
钛媒体：引领未来商业与生活新知
钛媒体：引领未来商业与生活新知
AWS News Blog
AWS News Blog
C
Cisco Blogs
美
美团技术团队
T
Threat Research - Cisco Blogs
C
CERT Recently Published Vulnerability Notes
人人都是产品经理
人人都是产品经理
宝玉的分享
宝玉的分享
Threat Intelligence Blog | Flashpoint
Threat Intelligence Blog | Flashpoint
酷 壳 – CoolShell
酷 壳 – CoolShell
Stack Overflow Blog
Stack Overflow Blog
W
WeLiveSecurity
D
DataBreaches.Net
博
博客园 - 司徒正美
Blog — PlanetScale
Blog — PlanetScale
IT之家
IT之家
云风的 BLOG
云风的 BLOG
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
Simon Willison's Weblog
Simon Willison's Weblog
Google DeepMind News
Google DeepMind News
T
The Blog of Author Tim Ferriss
Know Your Adversary
Know Your Adversary
NISL@THU
NISL@THU
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
The Cloudflare Blog
Vercel News
Vercel News
月光博客
月光博客
T
Tailwind CSS Blog
H
Help Net Security
aimingoo的专栏
aimingoo的专栏
P
Proofpoint News Feed
Application and Cybersecurity Blog
Application and Cybersecurity Blog
Spread Privacy
Spread Privacy
cs.CL updates on arXiv.org
cs.CL updates on arXiv.org
Cisco Talos Blog
Cisco Talos Blog
Microsoft Security Blog
Microsoft Security Blog
V
V2EX
WordPress大学
WordPress大学
Cyberwarzone
Cyberwarzone
Recent Announcements
Recent Announcements

网络热度

LeetCode 75 学习计划清单和参考答案 AI辅助生成的统计博客文章浏览量的网络爬虫 程序员面试题精解（5）— 素数判定 程序员面试题精解（4）— 双指针 哈佛 CS50AI 课程介绍：从零开始学习人工智能 解决不蒜子文章阅读计数错误的问题 RSA的攻与防（三） RSA的攻与防（二） 启用 TLS 1.3 提升网络应用的安全性和性能 程序员面试题精解（3）— 二分查找 嵌入式Linux系统中uClibc标准库使用经验笔记 请马上停止使用TLS 1.0和TLS 1.1！ 自己动手使用树莓派搭建家用NAS和流媒体服务器 iTerm2 + Oh-My-Zsh + Powerlevel10k 打造酷炫macOS终端 AddressSanitizer — 程序员检测内存访问错误的利器 程序员面试题精解（2）— 平方根运算 思科 Catalyst Wi-Fi 6 MU-MIMO 带你畅享速度与激情 程序员面试题精解（1）— 比特位计数 C编程支持16位存取接口的存储设备
巧解picoCTF的RSA挑战题Sum-O-Primes
子曦 · 2022-06-18 · via 网络热度

一个偶然的机会，接触到一道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!

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

gen.py
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


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
1
2
3
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解题代码如下：

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
import math

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

x = int((Lines[0].split())[2], 16) 
n = int((Lines[1].split())[2], 16) 
c = int((Lines[2].split())[2], 16) 

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);  


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函数解密，最后将明文从大的整数转化为字节序列并打印输出。程序运行的结果是

1
b'picoCTF{pl33z_n0_g1v3_c0ngru3nc3_0f_5qu4r35_92fe3557}'

BINGO！夺旗成功！

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

1
2
3
4
5
6
7
8
>>>
=============== 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代码非常简洁

1
2
3
4
5
6
7
8
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行打印和断言语句。代码的执行结果是

1
2
3
4
5
6
>>>
=============== 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

此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。