RSA实现 #
Python实现如下：
# encoding: utf-8
# pip install libnum
import libnum
from uuid import uuid1
#生成随机素数
p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
e=65537
n=p*q
phi_n=(p-1)*(q-1)
#求逆元
d=libnum.invmod(e,phi_n)
m="flag{"+str(uuid1())+"}"
print(m)
#字符串转数字
m=libnum.s2n(m)
c=pow(m,e,n)
m=pow(c,d,n)
print(c, libnum.n2s(m))
# encoding: utf-8
# pip install gmpy2 pycryptodome
import gmpy2
from Crypto.Util.number import * #getPrime, bytes_to_long, long_to_bytes
from uuid import uuid1
#生成随机素数
p = getPrime(512)
q = getPrime(512)
e=65537
n=p*q
phi_n=(p-1)*(q-1)
#求逆元
d=gmpy2.invert(e,phi_n)
m="flag{"+str(uuid1())+"}"
print(m)
#字符串转数字
m=bytes_to_long(m)
c=pow(m,e,n)
m=pow(c,d,n)
print(c, long_to_bytes(m))
素数判定 #
素数判定或素性检测参看博客中的其他文章
题型扩充 #
已知p、q #
题目
p = 0xb6ce21ea137206f9ac1a0e9a004457b090a7fd1745026ba230bd6e33d134eebf8498d98e061be16bc5cb3dfa1e24adc9fbf4214af86aaf6100a064dd6bb0d737ff3a38ac274487a1bf2a6a736fd03fa783b84399d65c79d64c19090b9adf629e55b40e735320535e09684d830432c53e740ba62da8498022820b89aec87b8941L
q = 0xf77307cf5c1bc4f5e45b6515d2de47ce64e9bfc1b3362391a8a791063dcd6c7711c5f1397780abcfb8eaa1201ab82f87e5b314c57fefbfb4f7b2b99a42f93918fd12cb039b50e1ba38bf86f8efc40fe60cc2e57eafce3f3597d6ed8b939d988a34dcadac6b394bf447ce5024d2083dc12b7f1ccd73073f0af70943cf2f133defL
e = 0x10001
c = 0x9aa88a7c5cd1ada3f7ba0d28161dab5f9f27f4b2320e8308b7205f43654ed01f55a7f463b21193fb89f6e97328f68bbf14656d0f3c4aeafdaf90f29f0e1410adddb71573ae164587cc613754467f49ca714c11489a7b70fe7b8382f9d44e5702edab0482d15d8f6b788125fc3f14d63e9f6ce71da93c4de00b2b918201c45adef2dc207fc264057885754f426e9a26072bd9d3ae41ed4f2ba7ac2105a80bd6b783e413fe8004c0ad75bbf9409dddb2ea005eec76f6106b1884b3ed0d16bf794926e32d872d29786135edd4ecc0ac8d490f79a922e3b910ab3d573e248a05763afa778d8a5ad9a418133e20a76cb54f6b864e0d88c3c772e3b12dd035cc372feaL
思路
- p、q题目已经提供，就是简单考查RSA的代码实现
答案
import libnum
p = 0xb6ce21ea137206f9ac1a0e9a004457b090a7fd1745026ba230bd6e33d134eebf8498d98e061be16bc5cb3dfa1e24adc9fbf4214af86aaf6100a064dd6bb0d737ff3a38ac274487a1bf2a6a736fd03fa783b84399d65c79d64c19090b9adf629e55b40e735320535e09684d830432c53e740ba62da8498022820b89aec87b8941
q = 0xf77307cf5c1bc4f5e45b6515d2de47ce64e9bfc1b3362391a8a791063dcd6c7711c5f1397780abcfb8eaa1201ab82f87e5b314c57fefbfb4f7b2b99a42f93918fd12cb039b50e1ba38bf86f8efc40fe60cc2e57eafce3f3597d6ed8b939d988a34dcadac6b394bf447ce5024d2083dc12b7f1ccd73073f0af70943cf2f133def
e = 0x10001
c = 0x9aa88a7c5cd1ada3f7ba0d28161dab5f9f27f4b2320e8308b7205f43654ed01f55a7f463b21193fb89f6e97328f68bbf14656d0f3c4aeafdaf90f29f0e1410adddb71573ae164587cc613754467f49ca714c11489a7b70fe7b8382f9d44e5702edab0482d15d8f6b788125fc3f14d63e9f6ce71da93c4de00b2b918201c45adef2dc207fc264057885754f426e9a26072bd9d3ae41ed4f2ba7ac2105a80bd6b783e413fe8004c0ad75bbf9409dddb2ea005eec76f6106b1884b3ed0d16bf794926e32d872d29786135edd4ecc0ac8d490f79a922e3b910ab3d573e248a05763afa778d8a5ad9a418133e20a76cb54f6b864e0d88c3c772e3b12dd035cc372fea
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{we1c0me_t0_Chainer_s_training_r00m}
PKCS/OpenSSL #
基于n e d p q等信息生成PKCS#1 RSA密钥（或使用OpenSSL），对文件进行解密
PyCryptodome RSA.construct 构建密钥
# 私钥生成公钥
openssl rsa -in prikey.pem -pubout -out pubkey.pem
# 提取公钥信息
openssl rsa -pubin -in pubkey.pem -text -noout # pubin表示in的文件是一个公钥，默认是私钥，所以in不能少
Public-Key: (64 bit)
Modulus: 13826123222358393307 (0xbfe041d1197381db)
Exponent: 65537 (0x10001)
提取私钥信息
openssl rsa -in prikey.pem -text -noout
Private-Key: (64 bit, 2 primes)
modulus: 13826123222358393307 (0xbfe041d1197381db)
publicExponent: 65537 (0x10001)
privateExponent: 9793706120266356337 (0x87ea3bd3bd0b9671)
prime1: 4184799299 (0xf96ef843)
prime2: 3303891593 (0xc4ed6289)
exponent1: 1771565249 (0x6997f0c1)
exponent2: 1637452169 (0x61998989)
coefficient: 568112984 (0x21dcb758)
公钥加密（需注意n的长度和数据长度）
openssl rsautl -encrypt -pubin -inkey pubkey.pem -in flag -out flag.enc
私钥解密
openssl rsautl -decrypt -inkey prikey.pem -in flag.enc -out flag
题目
p=135107209955704896198000222334245302654243745495559567671804820858012561141225874582790552130071789809406337174186164537655634738483338212007882091015146536797144814807921423249530783205417173226847805817505933320625728612032490509116441285849207880363824490795277589839619746571582256964496474979903709862693
q=160171769876064727845900448109595638308600010847305736067559931842453822615214982070630165865716840658372045734198096532958184768278400375005563834778185401064339526040432896616673824937436636299621536578531174689764824667158071306658990307745089364592739535140109411467625983684900575582794083374148143857419
e = 65537
和一个oaep.txt文件
思路
- PKCS#1解密，和 OAEP Padding使用
答案
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
# RSA private key components (p, q, and exponent)
p = 135107209955704896198000222334245302654243745495559567671804820858012561141225874582790552130071789809406337174186164537655634738483338212007882091015146536797144814807921423249530783205417173226847805817505933320625728612032490509116441285849207880363824490795277589839619746571582256964496474979903709862693
q = 160171769876064727845900448109595638308600010847305736067559931842453822615214982070630165865716840658372045734198096532958184768278400375005563834778185401064339526040432896616673824937436636299621536578531174689764824667158071306658990307745089364592739535140109411467625983684900575582794083374148143857419
e = 65537
# Modulus calculation
n = p * q
# Function to calculate the private exponent d
def calculate_private_exponent(p, q, e):
from Crypto.Util.number import inverse
phi = (p - 1) * (q - 1)
return inverse(e, phi)
# Calculate the private exponent
d = calculate_private_exponent(p, q, e)
# Generate an RSA private key using p, q, and exponent d
key = RSA.construct((n, e, d, p, q))
# 也可尝试将key导出然后使用openssl解密
# with open("prikey.pem", "wb") as f:
# data = key.export_key()
# f.write(data)
with open('oaep.txt', 'rb') as file:
ciphertext = file.read()
# Decrypt the message using RSA with OAEP padding
cipher = PKCS1_OAEP.new(key)
plaintext = cipher.decrypt(ciphertext)
# plaintext: flag{Simple_OpenSSL_Operation}
print("plaintext:", plaintext.decode())
当使用Crypto包或者openssl解密失败后，可以尝试使用pow(c,m,d)进行解密分解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}
孪生素数 #
孪生素数(twin prime)指一对素数，它们之间相差2，如11和13、2999和3001等。孪生素数也满足上述分解n的条件（p，q 的取值过于相近），但这里想强调说明下孪生素数特定于RSA题目下的一些特征。
n = pq = p(p+2) = (p+1)^2 - 1
如果p、q为孪生素数，那么 n+1 是一个完全平方数，平方根为 p+1。
如果使用openssl发现 n 以重复的
0xff结尾，Public-Key: (8587 bit) Modulus: 06:2d:3d:61:c9:24:52:63:01:47:e8:96:70:ff:ff: ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff: ... ... ...则要怀疑 p、q 是否为孪生素数，因为
n+1 = xxxxx*(16^?)可能是一个完全平方数
题目
有以下2个文件：
思路
使用openssl发现，n较大，且重复以ff结尾，推测p、q可能为孪生素数
openssl rsa -pubin -in key.pem -text -noout
Public-Key: (8587 bit)
Modulus:
06:2d:3d:61:c9:24:52:63:01:47:e8:96:70:ff:ff:
ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
...
...
答案
>>> int("062d3d61c92452630147e89671",16)
489370006782504706395349751409
>>> gmpy2.iroot(489370006782504706395349751409,2)
(mpz(699549860111847), True)
# n = p*(p+2) = (p+1)^2 - 1
# n + 1 = (699549860111847^2)*0xf*2122 = (p+1)^2
from Crypto.PublicKey import RSA
from Crypto.Util import number
p = 699549860111847*16**1061 - 1
q = 699549860111847*16**1061 + 1
n = p*q
e = 65537
phi_n = (p-1)*(q-1)
d = number.inverse(e,phi_n)
cipher = open("cipher.bin", "rb").read()
flag = pow(number.bytes_to_long(cipher), d, n)
# b'Congratulations! Here is a treat for you: flag{how_d0_you_7urn_this_0n?}'
print(number.long_to_bytes(flag))
Rabbin #
Rabin cryptosystem是一种基于模合数平方根困难性问题的非对称加密算法，该算法Rabin于1978年发布的Rabin signature scheme签名算法演变而来。有以下特点：
- 算法的安全性被证明了等价于大数的质数分解，在这点上RSA没有证明
- 相当于 e=2 的RSA
- trapdoor function的每个输出都可以由四个可能输入中的任何一个生成
为什么算法的安全性被证明了等价于大数的质数分解，可以参看以下链接：
https://en.wikipedia.org/wiki/Quadratic_residuosity_problem
https://crypto.stackexchange.com/questions/27121/why-is-rabin-encryption-equivalent-to-factoring
https://crypto.stackexchange.com/questions/9332/quadratic-residuosity-problem-reduction-to-integer-factorization
https://crypto.stackexchange.com/questions/24720/is-computing-roots-moduli-a-composite-n-a-hard-problem-without-knowing-the-fac
算法描述 #
Key 生成
- 选择2个大的质数 p 和 q
- 计算 n = p * q
n 是公钥，(p, q) 是私钥
加密
c = m^2 (mod n) (m < n)
解密
由 c = m^2 (mod n) 显然可得，
m^2 ≡ c mod p，同时模平方根记做 ±mp
m^2 ≡ c mod q，同时模平方根记做 ±mq
求解可以参看 Cipolla’s algorithm。Cipolla’s algorithm 可用于解二次剩余方程 x ≡ n mod p，p为奇素数时的通解
同时，如果找到了 m 满足 m^2 ≡ c mod p 和 m^2 ≡ c mod q，即也找到了 m 满足 m^2 ≡ c mod p*q
根据等式构造出 r, s 满足：
r^2 ≡ m^2 ≡ c mod p
s^2 ≡ m^2 ≡ c mod q
解 r, s 的过程相当于求解二次剩余方程 m^2 ≡ c mod (p or q)
对mp和mq两两联立，即以下4组同余方程组分别使用中国剩余定理求解，可得 m 的4个解
1:
r ≡ mp mod p
s ≡ mq mod q
2:
r ≡ mp mod p
s ≡ -mq mod q
3:
r ≡ -mp mod p
s ≡ mq mod q
4:
r ≡ -mp mod p
s ≡ -mq mod q
使用中国剩余定理求解过程如下：
- 根据裴蜀定理 p 和 q互质，存在 yp 和 yq 满足： yp * p + yq * q = 1
- 可以使用扩展欧几里得求得 yp 和 yq
- 4个解分别为：
- r1 = (yp * p * mq + yq * q * mp) mod n
- r2 = n - r1
- r3 = (yp * p * mq - yq * q * mp) mod n
- r4 = n - r3
https://en.wikipedia.org/wiki/Chinese_remainder_theorem#:~:text=In%20mathematics%2C%20the%20Chinese%20remainder,are%20pairwise%20coprime%20(no%20two https://crypto.stackexchange.com/questions/29949/how-to-use-crt-to-compute-4-square-roots-while-decryption-in-rabin-cryptosystem
由于常规Rabin加密规定 p ≡ q ≡ 3 (mod 4)，这个条件保证了mp和mq的唯一性，mp = c^(1/4(p+1)), mq = c^(1/4(q+1))
为什么当p ≡ 3 (mod 4) 时，mp = c^(1/4(p+1)) mod p 是 m^2 ≡ c (mod p) 的模平方根？
由于 m^2 ≡ c (mod p)，所以 c 是模 p 的二次剩余，记做勒让德符号(c/p) = 1
mp^2 ≡ c^1/2(p+1) ≡ c*c1/2(p-1) mod p，根据欧拉准则，得
c * c1/2(p-1) mod p ≡ c * 1 mod p
https://en.wikipedia.org/wiki/Quadratic_residue https://en.wikipedia.org/wiki/Euler%27s_criterion
加密：
- 取 p = 7, q = 11，则 n = 77
- 取 m = 20 作为明文
- 密文为 c = m^2 mod n，即 400 mod 77 = 15
解密：
- 计算 mp = c^(1/4(p+1)) mod p，即 15^2 mod 7 = 1，同理 mq = 15^3 mod 11 = 9
- 使用扩展欧几里得求得 yp 和 yq，满足 yp * p + yq * q = 1，得 yp = -3 和 yq = 2 (-3 * 7 + 2 * 11 = 1)
- 计算4个明文候选：
- r1 = (-3 * 7 * 9 + 2 * 11 * 1) mod 77 = 64
- r2 = 77 - 64 = 13
- r3 = (-3 * 7 * 9 - 2 * 11 * 1) mod 77 = 20
- r4 = 77 - 20 = 57
r1-r4都是理论满足的，r3是实际想要的
import libnum
def rabin_encrypt(msg, n):
return pow(msg, 2, n)
def rabin_decrypt(ciphertext, p, q):
n = p * q
mp = pow(ciphertext, (p+1)//4, p)
mq = pow(ciphertext, (q+1)//4, q)
yp, yq, gcd = libnum.xgcd(p, q)
r1 = (yp*p*mq + yq*q*mp) % n
r2 = n - r1
r3 = (yp*p*mq - yq*q*mp) % n
r4 = n - r3
return r1, r2, r3, r4
def generate_prime(bits):
while True:
p = libnum.generate_prime(bits)
if p % 4 == 3:
return p
# 生成两个满足条件的素数
p = generate_prime(32)
q = generate_prime(32)
while p == q:
q = generate_prime(32)
print(p, q)
n = p*q
# 加密和解密
msg = 123456789
ciphertext = rabin_encrypt(msg, p*q)
plaintext1, plaintext2, plaintext3, plaintext4 = rabin_decrypt(ciphertext, p, q)
print("明文：", msg)
print("密文：", ciphertext)
print("解密结果1：", plaintext1)
print("解密结果2：", plaintext2)
print("解密结果3：", plaintext3)
print("解密结果4：", plaintext4)
题目
有以下2个文件：
思路
提取公钥信息，发现 e=2
openssl rsa -pubin -in pubkey.pem -text -noout
Public-Key: (256 bit)
Modulus:
00:c2:63:6a:e5:c3:d8:e4:3f:fb:97:ab:09:02:8f:
1a:ac:6c:0b:f6:cd:3d:70:eb:ca:28:1b:ff:e9:7f:
be:30:dd
Exponent: 2 (0x2)
yafu分解
starting SIQS on c77: 87924348264132406875276140514499937145050893665602592992418171647042491658461
***factors found***
P39 = 275127860351348928173285174381581152299
P39 = 319576316814478949870590164193048041239
ans = 1
使用rabbin算法解密
答案
import libnum
# from Crypto.Util.number import bytes_to_long, long_to_bytes
def rabin_decrypt(ciphertext, p, q):
n = p * q
mp = pow(ciphertext, (p+1)//4, p)
mq = pow(ciphertext, (q+1)//4, q)
yp, yq, gcd = libnum.xgcd(p, q)
print(yp, yq)
r1 = (yp*p*mq + yq*q*mp) % n
r2 = n - r1
r3 = (yp*p*mq - yq*q*mp) % n
r4 = n - r3
return r1, r2, r3, r4
p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
with open('flag', 'rb') as f:
ciphertext = libnum.s2n(f.read())
# 45617141162985597041928941111553655146539175146765096976546144304138540198644
print(ciphertext)
plaintext1, plaintext2, plaintext3, plaintext4 = rabin_decrypt(ciphertext, p, q)
print("解密结果1：", libnum.n2s(plaintext1))
print("解密结果2：", libnum.n2s(plaintext2))
print("解密结果3：", libnum.n2s(plaintext3))
print("解密结果4：", libnum.n2s(plaintext4))
# flag{R0bin_rsa_666666}
低加密指数 #
如果e比较小，n比较大时，如 e=3，n为2048bits，有以下2种攻击方式：
m^e < n: c 开 3 次方根，得到 mm^e > n: 有 c = m^e + kn，爆破 k，如果 c-kn 能开 3 次方根，得到 m
题目
Bob最近在研究RSA密码的实现，Jone发现Bob犯了个错误。
然后利用公钥就把密文解密了，你能知道里面写了什么吗？
flag 格式 flag{}
Public key is:
-----BEGIN RSA PUBLIC KEY-----
MIIBCAKCAQEAsKE2J66COeSM8Adt6nrijJZ1HahnRUK2P/9GVIb+bu/gObCWuGdH N5BcSRUzlux6Ri65r2ITJNdgYA1hFnJQlf1t0BzC8Z6/msn1N6/oQjCBHsF5YGeH m9s4l6JNI3HcWpmi9JXnRAT4a319EjJG7Sba1Rny1gMvrYsxi2bmqy5LP1NLl2g+ IA1ykv5vttwZhm6rOY8x03aG+vJ/rzOlYFtNHBMk8z+lm8Hwqb0kEmFPqZHuSB4p EipjtNCS+CNs+/3sMPIH99/n36RtaHlLfkWr8PAEWGOPjbbq95foVBteWvgGJi+K CTUE7ZmIqMgUYazIStc8yv/aBiN+pIM8WwIBAw==
-----END RSA PUBLIC KEY-----
思路
发现n比较大，e比较小，遂爆破
openssl rsa -pubin -in pubkey.pem -text -noout
Public-Key: (2048 bit)
Modulus:
00:b0:a1:36:27:ae:82:39:e4:8c:f0:07:6d:ea:7a:
e2:8c:96:75:1d:a8:67:45:42:b6:3f:ff:46:54:86:
fe:6e:ef:e0:39:b0:96:b8:67:47:37:90:5c:49:15:
33:96:ec:7a:46:2e:b9:af:62:13:24:d7:60:60:0d:
61:16:72:50:95:fd:6d:d0:1c:c2:f1:9e:bf:9a:c9:
f5:37:af:e8:42:30:81:1e:c1:79:60:67:87:9b:db:
38:97:a2:4d:23:71:dc:5a:99:a2:f4:95:e7:44:04:
f8:6b:7d:7d:12:32:46:ed:26:da:d5:19:f2:d6:03:
2f:ad:8b:31:8b:66:e6:ab:2e:4b:3f:53:4b:97:68:
3e:20:0d:72:92:fe:6f:b6:dc:19:86:6e:ab:39:8f:
31:d3:76:86:fa:f2:7f:af:33:a5:60:5b:4d:1c:13:
24:f3:3f:a5:9b:c1:f0:a9:bd:24:12:61:4f:a9:91:
ee:48:1e:29:12:2a:63:b4:d0:92:f8:23:6c:fb:fd:
ec:30:f2:07:f7:df:e7:df:a4:6d:68:79:4b:7e:45:
ab:f0:f0:04:58:63:8f:8d:b6:ea:f7:97:e8:54:1b:
5e:5a:f8:06:26:2f:8a:09:35:04:ed:99:88:a8:c8:
14:61:ac:c8:4a:d7:3c:ca:ff:da:06:23:7e:a4:83:
3c:5b
Exponent: 3 (0x3)
答案
import libnum
import gmpy2
e = 3
n = 0x00b0a13627ae8239e48cf0076dea7ae28c96751da8674542b63fff465486fe6eefe039b096b8674737905c49153396ec7a462eb9af621324d760600d6116725095fd6dd01cc2f19ebf9ac9f537afe84230811ec1796067879bdb3897a24d2371dc5a99a2f495e74404f86b7d7d123246ed26dad519f2d6032fad8b318b66e6ab2e4b3f534b97683e200d7292fe6fb6dc19866eab398f31d37686faf27faf33a5605b4d1c1324f33fa59bc1f0a9bd2412614fa991ee481e29122a63b4d092f8236cfbfdec30f207f7dfe7dfa46d68794b7e45abf0f00458638f8db6eaf797e8541b5e5af806262f8a093504ed9988a8c81461acc84ad73ccaffda06237ea4833c5b
with open('secret.txt', 'rb') as f:
c = libnum.s2n(f.read())
k = 0
while True and k < 10000:
me = c + n*k
result, flag = gmpy2.iroot(me, e)
if flag:
print(k)
print(libnum.n2s(int(result)))
# 2149
# b'Hi, I am BOB. This is the first time I realize the RSA algorithm. flag{I_am_a_genius!}'
k += 1
低加密指数广播攻击 #
向一个群体，使用了相同的加密指数，对同一个消息进行加密发送，即 n，c 不同，m，e 相同，可以使用中国剩余定理求解
题目
flag = 'flag{******}'
e = 13
n[0] = 125555486791884560550086293758712483294510553604123519820907020215034995204390948081864439539909169296492177365235090384993072772138361359041765927316343490532738831918870696932710694270916806965315587461692983744021352859105991836739783213149047996149309892957265100172211808806855993047183329176918476277943
c[0] = 47985569888451044875834999419693114861280107318544860754113780012532140642673053441707087040282426588992596723953200758593209986877560329799805308131470882809965962453230745638224460112819244548496592643359269646263150981650722710403348583341824538859229153500953920166092770596758267149672456076095705688676
n[1] = 112883266462445425802434919418873471090248803163688234621801401415102456833761636004089567693154693499526779404083395825758197457394510713501221716047101003306739104992510287961020463484275341827406714393355960313608298578691669591088847249751781402136271752915097598418731653272218245292196912328247036851531
c[1] = 46936678784825428013905083837174505377012515764570128419415678190582232833261987416426758984350908316097335085597164285720546198677295231015076773949878880531028398636102852522367567059524890358991293212414090037991613098577614012870049308493226860998087642998605167577262856491838885313581336598650389383698
n[2] = 141891435774484135253511040721977018354351862998913169440118302699252537213981567646087964573241310102453274932048075979968352040320740148813228798031283100948477567349375966058780737436321276511283869440655442974624195780417975458458216902203018955858756824439727628043859418703644560387224538015692863377441
c[2] = 30319416754155381786393273784558838748605102476110732553896390422331423008056170393289663632073894997311764704968248364641795159787530087623808642702359859579892482398013892706721435644985530357751013038996746838520539774047599915465689212212505739233428198721612660545819402246874358724906859780647555029076
n[3] = 141317275786967099118542015277041196217188680521986966466508435934476693997288152751129086261469948905525476866366039861705536278828084284078392086948582779261396025576743303042453843528085686087907607370299535322822936337945188187326861089109467095954514186370284149230185424519163694478794525801944003578189
c[3] = 105181475292346726733036498428815453788683853491512459229097908320044584572903359994502866246149103775202863978346711216048869827311033131243018044824858737992075077934965099924950777144650896422762676106846892545313103560801720862361244603560139169052564653670237081726232991337801130794953501225040539640090
n[4] = 154573474384962240035047976381058996392353118375867886715307375788266986784203900163875932804802696271642077242296813812769960796059732225429555976731213011318783567454920370043493629259763484347274852953527788384400305084480690803023575032106591477086913360746534962846302890690214188327604713600734360952343
c[4] = 109593969556984351842620118572315298033420938047374461051453149475406201310207678225379542217626076252306567208006153514081458047612743320062710856486199549114571707486140605839412348792664469193905188596391215294425137377815284687633404218786555343578490365493535988882305923447144114851835047505321433754615
n[5] = 141868209896583481644438896377575235782325347583451906249705924736692551303303330136636427543850825881248606426778414988800788214400042998635979082207429559923014906988949420387851157976903350105064751496036382885130411424952083235845740295404762083228786900200610139445787134627623585931615544503097123111127
c[5] = 68412839850036388547704077738465408846304295926494397797830509868276768727296453864892495409182044283915755962560042656432301401002639949469912633619260824917634088948361533826181901533174694487097266815236120251863358079110301232306430079540017828592004431768106587207890107777450972075786513119426723782793
n[6] = 131962494917764778496012283189503013226635436798020622332024982884859913900595471642568631185708361970072636304088622803559869546249273314661090353617795219913102433369307391428622317321829132615326610197287558941772755012371434895252005218033806411346526124179859436604512822449481303632635058103149463328733
c[6] = 107382230607815539153054561533944551741393661795304903588564340109395814668893871143054931011435980884739608826669167798067504098654243917639791202646471416796617695579526070997409324229440529897831434906126323510278305445951276506412672248585491384087094030683715120519801662432257911356845996674339833558344
n[7] = 168354327623343637509464988139733705126691323150440059423973046485867854620292430303242749907653188313076916690802044847801061852804141022724523010541256081035760143817365344638570547216627509013355038232767842841914274692026787497094356285310019672547751105319324003212263824064644522434404826868928141649937
c[7] = 87312041667167879938644978553255389969861034888702618958126674691301644883609383042457794162172845551994604628966053868419836495333520997539366345596272542275943972638233820513142088353490560812999165809482473636473735371967431269964444045076864441555247313901513446392359385947061406334455913758230610313379
n[8] = 112505382706826100948865870136508406813591439834964471850595747058146612900374112289748301292904623920891395528812660872404400181693496383798011319064451601662124876579532042712469171633051363393884464990856719487149851571837405748451113858260707448448834019697930740061824971134930237920695727669670057756343
c[8] = 27026836341384400752477829514398995059065216828477308362436179009713720854890107915855854011508891147788688830475245731024687073350439109511564633992820140999386430738401654394758030041961934903937498525894610734110118464359999763831284549228234520284159792502027620940425089686670849818512355789390698860725
n[9] = 134803300873444115285551658371041993653859511462236710928524237114466007394967358533248484641612876621298959586473135047997191990242794617765145338002677372422807177049620773214005105309892899242644557063099403473326259622351347190697391800015454386557557505090875814084283051931987026667230183319194373776843
c[9] = 87908911254659252200138393296025901300613844177700832422208536887886634094000727023092781134821774617084398012377589777799051270993705505929161947245999525817644738986397892405298044971042612242103678025801557240724611548947081914702262016033612827534525596059524942376474035301638102357547372998067909576155
n[10] = 135003685107553613484440333357724358049336421471894331224713204893408096655257854571639259933509156503800076616777921439985354621857930875758615726686573523823868827516393421013775032219919603522955615479164339781749451079548041357613801233979170028123816393936688658019972278626072167306617977353239540808439
c[10] = 47749231170929223098536641527116759130616321402723589292012483416622985539678686997190425715886241990155937320850958212070112948881665222779112313010441280954856893386672047249882218601029707177013337424735423117891683102068276780958796911579677205463567257946047276649478555742285991469192869042220796664340
n[11] = 143842122021226602598402348604722013159913905048093528969239895117462881577099433633398546162669165932678977618203657664514070842362733464025257687580619781892584579524306810038271872404249818378209765262934712913754871901959719138614103557995406036019956879085986403366995886878175104752928022429312455071261
c[11] = 40188944062758207789374764497229013486027845991197846276680534377154607161336890858282175507374739900596900448305893469849740240079660894040193732483705430387058183852203712454129091275544214794526593559116536100264569948756809174125350537188477043699378536990153267720824041937166729050752778812258644593783
n[12] = 151876421561086041766058272155488539361648665633305003745959449032546495049159583975217808514614373163582580024268523011793131622189336234658095852135675474511819799997749205054832576450000518037088593161090984148860671276682657782103191741557105531662557083243191308312358122543540701245578777624830519913407
c[12] = 61715481793179434386204123545434472455167488202643735827987774706694119799011592891052732712639476515596322238800544940973507687712739826693430950989456133858000916201776575965490887692270588136126043577889158945382871312620702232836775227078809520696414770841498652623478396278505564849751130064926018053684
n[13] = 135016017018948889892048077249861491427352902732332516945637226790898648225663837569282687534364366720233352891460740377822386643847103327572343806660476560232499273717295242461153887132846279800653763024858720608921581505544729802871411203869802569242521343789275867774497637036110200640123645725979190183839
c[13] = 68565704227733669950636398347662221636657372004548730227084295963458161495355972469434823892237128525015532669862457389948907388480271637497428680042093643646043299691344439877484774299326019688577752189931461410692252412628771116225934663408435090805821074043516578571069931431644167754579448079451350700371
n[14] = 113617407069768718815568962087960271189063680447715859867460683191555851040807389458227997123072019644417236586676984950862411795377024992433100418870908970649855403566857611231431431938666855318046141236903014237486725116950814567032217850474391145519548123511512152874525317839149559675140909304158309368249
c[14] = 22420067924577024371212816540053263625334466227156509518088868639627017202370946558909539519132862931889664835464953788170309406828810581854594900970162730882544579983361507946160161827121700109721709458936368787493714016904757193455561247606914263673762059209294384255106246945972387596118582294356346152090
n[15] = 142964256697842595875726567523655036262719517971688933644150057302331972969009499317404642176995816605575245035431843384954943500580505844169834763702905511413461076111098342691213799048457893917322364457662739680843566249304110991689706932146469604618447377431130459013761433613394766792797269374487657274263
c[15] = 29296328371708756614952060672336699915653877998161762759300006889694985600479897782631944509031428641239305565320135675495502103290482334232859799321140440910761400830595823312071796468217334802230008314008727836228061620500354484233024143148813015984403480953520854808313238808795398635692172533655746386394
n[16] = 142512510657073273778974294710511553063187223481953597629101021239354784652123873737019870881002085066507828639267359636234516890750919418616517458479021334808058572707196658887914111480601364376793894020789271696715384378180886645830785938849363190151918033826415737484868530078421282705813412286419554086159
c[16] = 36258067373877105825055087493773088880305319143163425991802501933592307634380565282211792536203349189146260447850666488075593005988144091839363944118216422232321032023187550701341956217683120682286236821157044056789207847505973325335487617141876394158040170302511026147698140117870936078053149940693809742344
n[17] = 102533335494389392218090303604786825301160249511835750951539887595950113542294097548480828631584449025777895886056739168311356354112944193554125469014191460217511098299228148720240631680208416303682061231842176710265170164701926774972275949411579750112583283495239062063864399525977165271427381589747953436631
c[17] = 3860830094490961085752930884310966690918909746779021840910765828272134765906916258416361041880241208337797182124709475409638427184157760682062239499378258139634870508832957715200906725559847289585974782965946274822184675941355910172994426277285817711407659299873774679529467353447340574476173095090997270887
n[18] = 93097135723163336847586617493687161480054327293298516195605188721713074772196301777516304975195728152915409458804701511060816216467740400187574307448990662189172679995988813287442315109673935739807537289999442702392212067453489314621577211533367402111172994889702662484284368528960831716715092315215045825889
c[18] = 58174930659603530051481089696633182639458958436222609892129088639113327368911105551511748550690912984592653380933017502134980761460623474839151362671442618757892193516120069483995146320454008624814011679255342019163335555032690250948599813711603812851179611383594880308670070294772541300929900936407942446206
n[19] = 144433370570770095167735345888539043699876517597114505863411096023274087944757777877426454857528133446258009694532035411730285329907095877944735687824248690700545076260122879413162485910119218187406100726941124563382230343790472703035275965860068538362112460159627364967177261108925146517058656137775109299597
c[19] = 44079089028711152982021028496891544027497861560917278801060597134507130629029590138353932484080222751995776415833575786219736764105345566270091010823997065161186675184474098872736189906830945504257759361652735423910178644048032275677684693137034101100555989481630131431167092816069402540842828905339322687933
思路
使用中国剩余定理求解以下同余方程组，同时对m^e进行爆破 ci = m^e mod ni
答案
from libnum import invmod, gcd, n2s
import gmpy2
def CRT(residues, moduli):
# Compute the product of the moduli
M = 1
for m in moduli:
M *= m
# Compute the solution using the CRT
solution = 0
for i in range(len(moduli)):
mi = M // moduli[i]
mi_inv = invmod(mi, moduli[i])
solution += residues[i] * mi * mi_inv
# Reduce the solution modulo M
solution %= M
return solution, M
# Define the moduli and residues
moduli = [
125555486791884560550086293758712483294510553604123519820907020215034995204390948081864439539909169296492177365235090384993072772138361359041765927316343490532738831918870696932710694270916806965315587461692983744021352859105991836739783213149047996149309892957265100172211808806855993047183329176918476277943,
112883266462445425802434919418873471090248803163688234621801401415102456833761636004089567693154693499526779404083395825758197457394510713501221716047101003306739104992510287961020463484275341827406714393355960313608298578691669591088847249751781402136271752915097598418731653272218245292196912328247036851531,
141891435774484135253511040721977018354351862998913169440118302699252537213981567646087964573241310102453274932048075979968352040320740148813228798031283100948477567349375966058780737436321276511283869440655442974624195780417975458458216902203018955858756824439727628043859418703644560387224538015692863377441,
141317275786967099118542015277041196217188680521986966466508435934476693997288152751129086261469948905525476866366039861705536278828084284078392086948582779261396025576743303042453843528085686087907607370299535322822936337945188187326861089109467095954514186370284149230185424519163694478794525801944003578189,
154573474384962240035047976381058996392353118375867886715307375788266986784203900163875932804802696271642077242296813812769960796059732225429555976731213011318783567454920370043493629259763484347274852953527788384400305084480690803023575032106591477086913360746534962846302890690214188327604713600734360952343,
141868209896583481644438896377575235782325347583451906249705924736692551303303330136636427543850825881248606426778414988800788214400042998635979082207429559923014906988949420387851157976903350105064751496036382885130411424952083235845740295404762083228786900200610139445787134627623585931615544503097123111127,
131962494917764778496012283189503013226635436798020622332024982884859913900595471642568631185708361970072636304088622803559869546249273314661090353617795219913102433369307391428622317321829132615326610197287558941772755012371434895252005218033806411346526124179859436604512822449481303632635058103149463328733,
168354327623343637509464988139733705126691323150440059423973046485867854620292430303242749907653188313076916690802044847801061852804141022724523010541256081035760143817365344638570547216627509013355038232767842841914274692026787497094356285310019672547751105319324003212263824064644522434404826868928141649937,
112505382706826100948865870136508406813591439834964471850595747058146612900374112289748301292904623920891395528812660872404400181693496383798011319064451601662124876579532042712469171633051363393884464990856719487149851571837405748451113858260707448448834019697930740061824971134930237920695727669670057756343,
134803300873444115285551658371041993653859511462236710928524237114466007394967358533248484641612876621298959586473135047997191990242794617765145338002677372422807177049620773214005105309892899242644557063099403473326259622351347190697391800015454386557557505090875814084283051931987026667230183319194373776843,
135003685107553613484440333357724358049336421471894331224713204893408096655257854571639259933509156503800076616777921439985354621857930875758615726686573523823868827516393421013775032219919603522955615479164339781749451079548041357613801233979170028123816393936688658019972278626072167306617977353239540808439,
143842122021226602598402348604722013159913905048093528969239895117462881577099433633398546162669165932678977618203657664514070842362733464025257687580619781892584579524306810038271872404249818378209765262934712913754871901959719138614103557995406036019956879085986403366995886878175104752928022429312455071261,
151876421561086041766058272155488539361648665633305003745959449032546495049159583975217808514614373163582580024268523011793131622189336234658095852135675474511819799997749205054832576450000518037088593161090984148860671276682657782103191741557105531662557083243191308312358122543540701245578777624830519913407,
135016017018948889892048077249861491427352902732332516945637226790898648225663837569282687534364366720233352891460740377822386643847103327572343806660476560232499273717295242461153887132846279800653763024858720608921581505544729802871411203869802569242521343789275867774497637036110200640123645725979190183839,
113617407069768718815568962087960271189063680447715859867460683191555851040807389458227997123072019644417236586676984950862411795377024992433100418870908970649855403566857611231431431938666855318046141236903014237486725116950814567032217850474391145519548123511512152874525317839149559675140909304158309368249,
142964256697842595875726567523655036262719517971688933644150057302331972969009499317404642176995816605575245035431843384954943500580505844169834763702905511413461076111098342691213799048457893917322364457662739680843566249304110991689706932146469604618447377431130459013761433613394766792797269374487657274263,
142512510657073273778974294710511553063187223481953597629101021239354784652123873737019870881002085066507828639267359636234516890750919418616517458479021334808058572707196658887914111480601364376793894020789271696715384378180886645830785938849363190151918033826415737484868530078421282705813412286419554086159,
102533335494389392218090303604786825301160249511835750951539887595950113542294097548480828631584449025777895886056739168311356354112944193554125469014191460217511098299228148720240631680208416303682061231842176710265170164701926774972275949411579750112583283495239062063864399525977165271427381589747953436631,
93097135723163336847586617493687161480054327293298516195605188721713074772196301777516304975195728152915409458804701511060816216467740400187574307448990662189172679995988813287442315109673935739807537289999442702392212067453489314621577211533367402111172994889702662484284368528960831716715092315215045825889,
144433370570770095167735345888539043699876517597114505863411096023274087944757777877426454857528133446258009694532035411730285329907095877944735687824248690700545076260122879413162485910119218187406100726941124563382230343790472703035275965860068538362112460159627364967177261108925146517058656137775109299597,
]
residues = [
47985569888451044875834999419693114861280107318544860754113780012532140642673053441707087040282426588992596723953200758593209986877560329799805308131470882809965962453230745638224460112819244548496592643359269646263150981650722710403348583341824538859229153500953920166092770596758267149672456076095705688676,
46936678784825428013905083837174505377012515764570128419415678190582232833261987416426758984350908316097335085597164285720546198677295231015076773949878880531028398636102852522367567059524890358991293212414090037991613098577614012870049308493226860998087642998605167577262856491838885313581336598650389383698,
30319416754155381786393273784558838748605102476110732553896390422331423008056170393289663632073894997311764704968248364641795159787530087623808642702359859579892482398013892706721435644985530357751013038996746838520539774047599915465689212212505739233428198721612660545819402246874358724906859780647555029076,
105181475292346726733036498428815453788683853491512459229097908320044584572903359994502866246149103775202863978346711216048869827311033131243018044824858737992075077934965099924950777144650896422762676106846892545313103560801720862361244603560139169052564653670237081726232991337801130794953501225040539640090,
109593969556984351842620118572315298033420938047374461051453149475406201310207678225379542217626076252306567208006153514081458047612743320062710856486199549114571707486140605839412348792664469193905188596391215294425137377815284687633404218786555343578490365493535988882305923447144114851835047505321433754615,
68412839850036388547704077738465408846304295926494397797830509868276768727296453864892495409182044283915755962560042656432301401002639949469912633619260824917634088948361533826181901533174694487097266815236120251863358079110301232306430079540017828592004431768106587207890107777450972075786513119426723782793,
107382230607815539153054561533944551741393661795304903588564340109395814668893871143054931011435980884739608826669167798067504098654243917639791202646471416796617695579526070997409324229440529897831434906126323510278305445951276506412672248585491384087094030683715120519801662432257911356845996674339833558344,
87312041667167879938644978553255389969861034888702618958126674691301644883609383042457794162172845551994604628966053868419836495333520997539366345596272542275943972638233820513142088353490560812999165809482473636473735371967431269964444045076864441555247313901513446392359385947061406334455913758230610313379,
27026836341384400752477829514398995059065216828477308362436179009713720854890107915855854011508891147788688830475245731024687073350439109511564633992820140999386430738401654394758030041961934903937498525894610734110118464359999763831284549228234520284159792502027620940425089686670849818512355789390698860725,
87908911254659252200138393296025901300613844177700832422208536887886634094000727023092781134821774617084398012377589777799051270993705505929161947245999525817644738986397892405298044971042612242103678025801557240724611548947081914702262016033612827534525596059524942376474035301638102357547372998067909576155,
47749231170929223098536641527116759130616321402723589292012483416622985539678686997190425715886241990155937320850958212070112948881665222779112313010441280954856893386672047249882218601029707177013337424735423117891683102068276780958796911579677205463567257946047276649478555742285991469192869042220796664340,
40188944062758207789374764497229013486027845991197846276680534377154607161336890858282175507374739900596900448305893469849740240079660894040193732483705430387058183852203712454129091275544214794526593559116536100264569948756809174125350537188477043699378536990153267720824041937166729050752778812258644593783,
61715481793179434386204123545434472455167488202643735827987774706694119799011592891052732712639476515596322238800544940973507687712739826693430950989456133858000916201776575965490887692270588136126043577889158945382871312620702232836775227078809520696414770841498652623478396278505564849751130064926018053684,
68565704227733669950636398347662221636657372004548730227084295963458161495355972469434823892237128525015532669862457389948907388480271637497428680042093643646043299691344439877484774299326019688577752189931461410692252412628771116225934663408435090805821074043516578571069931431644167754579448079451350700371,
22420067924577024371212816540053263625334466227156509518088868639627017202370946558909539519132862931889664835464953788170309406828810581854594900970162730882544579983361507946160161827121700109721709458936368787493714016904757193455561247606914263673762059209294384255106246945972387596118582294356346152090,
29296328371708756614952060672336699915653877998161762759300006889694985600479897782631944509031428641239305565320135675495502103290482334232859799321140440910761400830595823312071796468217334802230008314008727836228061620500354484233024143148813015984403480953520854808313238808795398635692172533655746386394,
36258067373877105825055087493773088880305319143163425991802501933592307634380565282211792536203349189146260447850666488075593005988144091839363944118216422232321032023187550701341956217683120682286236821157044056789207847505973325335487617141876394158040170302511026147698140117870936078053149940693809742344,
3860830094490961085752930884310966690918909746779021840910765828272134765906916258416361041880241208337797182124709475409638427184157760682062239499378258139634870508832957715200906725559847289585974782965946274822184675941355910172994426277285817711407659299873774679529467353447340574476173095090997270887,
58174930659603530051481089696633182639458958436222609892129088639113327368911105551511748550690912984592653380933017502134980761460623474839151362671442618757892193516120069483995146320454008624814011679255342019163335555032690250948599813711603812851179611383594880308670070294772541300929900936407942446206,
44079089028711152982021028496891544027497861560917278801060597134507130629029590138353932484080222751995776415833575786219736764105345566270091010823997065161186675184474098872736189906830945504257759361652735423910178644048032275677684693137034101100555989481630131431167092816069402540842828905339322687933,
]
solution, M = CRT(residues, moduli)
print(solution) # 通解是 solution + M*k
e = 13
k = 0
while True and k < 10000:
me = solution + M*k
result, flag = gmpy2.iroot(me, e)
if flag:
# 0
# b'flag{Chin3s3_KoNgfu}'
print(k)
print(n2s(int(result)))
k += 1
共模攻击 #
同一明文，使用相同的n，不同e进行加密
c1 = m^e1 mod n
c2 = m^e2 mod n
存在 t,s ，满足
te1 + se2 = gcd(e1,e2) = 1
所以
m^(te1 + se2) = m = c1^t*c2^s mod n
题目
n = 91988711096585254014061902029475785803436775040554413428256857601825281840455608000774499416291457871961485087751117936437502930850587505865207476188105549312952072118122473162952400356867887948408387500334877603885410549445229594299085046830314155571330761098182289454294497671288261064082431841717340592187
e1 = 44711
e2 = 36107
c1 = 45785021880113060583057817298928264078319672990057453058535114930745081117350671804547532293189756511044707050358716998140422860602096919314641673748035892210055235733849526369450014412275302283454864946883454538070831344218113408123784371750701629215262246625257443708313921084008244294488544498144136325671
c2 = 82157023975190324829950195353512888766091853099212035316581414227270256183328901829718074761557585217027148568170314345005671176170566675734144091265695558355594124080382697434235537650169471002210604280903079558999016166723084575878943269434519454156000332232807389767834129476229838924645359587705755210849
答案
import libnum
import gmpy2
n = 91988711096585254014061902029475785803436775040554413428256857601825281840455608000774499416291457871961485087751117936437502930850587505865207476188105549312952072118122473162952400356867887948408387500334877603885410549445229594299085046830314155571330761098182289454294497671288261064082431841717340592187
e1 = 44711
e2 = 36107
c1 = 45785021880113060583057817298928264078319672990057453058535114930745081117350671804547532293189756511044707050358716998140422860602096919314641673748035892210055235733849526369450014412275302283454864946883454538070831344218113408123784371750701629215262246625257443708313921084008244294488544498144136325671
c2 = 82157023975190324829950195353512888766091853099212035316581414227270256183328901829718074761557585217027148568170314345005671176170566675734144091265695558355594124080382697434235537650169471002210604280903079558999016166723084575878943269434519454156000332232807389767834129476229838924645359587705755210849
t, s, gcd = libnum.xgcd(e1, e2)
result = pow(c1, t, n)*pow(c2, s, n) % n
# b'flag{Share_M0dulus_i2_Danger0u2}'
print(libnum.n2s(result))
Wiener 攻击 #
Wiener攻击是一种针对使用较小的私钥解密指数进行RSA加密的攻击方法。Wiener’s theorem 的描述如下：
N = pq, q < p < 2q (即 p + q - 1 < 3sqrt(N)), d < 1/3N^(1/4)
给定的 <N,e> 满足 ed ≡ 1 (mod φ(N))，则能够有效地求得 d 的值
理解该定理需要先了解连分数和渐进分数概念
连分数(continued fraction)表现形式如下
连分数可以用以下形式进行简写，叫做连分数展开(continued fraction expansion)：
x = [a0,a1,a2,a3,a4,a5,...,an]
如 π =[3,7,15,1,292,1,1,1,2,…]
有理数（无理数）具有有限（无限）连分数展开式。
基于连分数可以得到渐进分数，渐进分数是有理数，可以看作是一种近似逼近。如下
c0 = 3/1 = 3.0
c1 = 3 + 1/7 = 22/7 = 3.142857
c2 = 3 + 1/(7+1/15) = 333/106 = 3.141509
c3 = 3 + 1/(7+1/(15+1/1)) = 355/113 = 3.141593
这些 ci 有理数被称为连分数的渐进分数(the convergents of a continued fraction)。ci 越来越接近 π (3.141592…)。
# Continued Fraction Expansion of Rationals
# Rationals can be reprensented by n = Nominators / d = Denominators
import math
def cf_expansion(n, d):
e = []
q = n // d
r = n % d
e.append(int(q))
while r != 0:
n, d = d, r
q = n // d
r = n % d
e.append(int(q))
return e
# math.pi: 3.141592653589793
# [3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 3, 3, 2, 1, 3, 3, 7, 2, 1, 1, 3, 2, 42, 2]
print(cf_expansion(math.pi, 1))
# 17993/90581
# [0, 5, 29, 4, 1, 3, 2, 4, 3]
print(cf_expansion(17993, 90581))
def convergents(e):
n = [] # Nominators
d = [] # Denominators
for i in range(len(e)):
if i == 0:
ni = e[i]
di = 1
elif i == 1:
ni = e[i]*e[i-1] + 1
di = e[i]
else: # i > 1
ni = e[i]*n[i-1] + n[i-2]
di = e[i]*d[i-1] + d[i-2]
n.append(ni)
d.append(di)
yield (ni, di)
e = [0, 5, 29, 4, 1, 3, 2, 4, 3]
# 0/1
# 1/5
# 29/146
# 117/589
# 146/735
# 555/2794
# 1256/6323
# 5579/28086
# 17993/90581
for n, d in convergents(e):
print("%d/%d" % (n,d))
理解上述连分数和渐进分数后，我们尝试理解 Wiener’s theorem 证明的思路
- 结合RSA实现及Wiener’s theorem中的各种限制条件，我们可以最终得到
abs(e/N - k/d) < 1/(2d^2)（详细过程请参看wiki中的证明部分）
- 根据
Legendre定理，如果abs(x - a/b) < 1/(2b^2)，那么 a/b 是 x 渐进分数中的一个。体现在这里就是k/d是e/N渐进分数中的一个 - 联立以下2个式子，可以筛选出正确的
k/d值ed - kφ(N) = 1- 由
φ(N)可以推出N=pq的分解：φ(N) = N - p - q + 1 = N - p - N/p + 1->p^2 + p(φ(N) - N - 1) + N = 0，如果根 p1p2 = N，则得到正确的k/d值
- 总体上，获得了
k/d值 能推出φ(N)，推出φ(N)能得到N = pq
Wiener 攻击的列子和代码实现如下：
<N,e> = <90581,17993> 求 d
e/N 的连分数扩展是 [0, 5, 29, 4, 1, 3, 2, 4, 3]
对应的 convergents 是，其中会有 k/d
0
1/5
29/146
117/589
146/735
555/2794
1256/6323
5579/28086
17993/90581
挨个判断，最终确定 1/5 为正确的 k/d，判断过程如下：
φ(N) = ed - 1 / k = 17993 * 5 - 1 / 1 = 89964
根据 p^2 + p(φ(N) - N - 1) - N = 0 即
p^2 - 618p + 90581 = 0 得 p1 = 379, p2 = 239，满足 N = 90581 = p1 x p2
import gmpy2
def cf_expansion(n, d):
e = []
q = n // d
r = n % d
e.append(int(q))
while r != 0:
n, d = d, r
q = n // d
r = n % d
e.append(int(q))
return e
def convergents(e):
n = [] # Nominators
d = [] # Denominators
for i in range(len(e)):
if i == 0:
ni = e[i]
di = 1
elif i == 1:
ni = e[i]*e[i-1] + 1
di = e[i]
else: # i > 1
ni = e[i]*n[i-1] + n[i-2]
di = e[i]*d[i-1] + d[i-2]
n.append(ni)
d.append(di)
yield ni, di
def wiener_attack(e, n):
cf = cf_expansion(e, n)
for k, d in convergents(cf):
if k == 0:
continue
phi = (e * d - 1) // k
b = phi - n - 1
delta = b * b - 4 * n
if delta < 0:
continue
root, exact = gmpy2.iroot(delta, 2)
if exact:
p, q = (-b + root) // 2, (-b - root) // 2
if p * q == n:
return p, q
# or
# p = Symbol('p', integer=True)
# roots = sympy.solve(p**2 + (phi - N - 1)*p + N, p)
# p, q = roots
# if p * q == n:
# return p, q
e = 17993
n = 90581
p, q = wiener_attack(e, n)
# p = 379
# q = 239
print("p = %d" % int(p))
print("q = %d" % int(q))
参考链接：
https://zhuanlan.zhihu.com/p/400818185
https://sagi.io/crypto-classics-wieners-rsa-attack/
https://en.wikipedia.org/wiki/Wiener%27s_attack
https://crypto.stackexchange.com/questions/56204/rsa-attack-with-continued-fractions-wieners-attack
题目
n = 460657813884289609896372056585544172485318117026246263899744329237492701820627219556007788200590119136173895989001382151536006853823326382892363143604314518686388786002989248800814861248595075326277099645338694977097459168530898776007293695728101976069423971696524237755227187061418202849911479124793990722597
e = 354611102441307572056572181827925899198345350228753730931089393275463916544456626894245415096107834465778409532373187125318554614722599301791528916212839368121066035541008808261534500586023652767712271625785204280964688004680328300124849680477105302519377370092578107827116821391826210972320377614967547827619
c = 430518885052463211928880150309746899793280569494514717229804457610645654546618397141033560961143804493709939917151868116850149667503379601542677290248006042112387562073597991532984562273435948997353239670931506060376329812189999562605693486930504349878154273868213374018040795628048038832072369044250913887074
思路
- e 比较大，推测d比较小，尝试使用 Wiener 攻击
答案
import gmpy2
import libnum
def cf_expansion(n, d):
e = []
q = n // d
r = n % d
e.append(int(q))
while r != 0:
n, d = d, r
q = n // d
r = n % d
e.append(int(q))
return e
def convergents(e):
n = [] # Nominators
d = [] # Denominators
for i in range(len(e)):
if i == 0:
ni = e[i]
di = 1
elif i == 1:
ni = e[i]*e[i-1] + 1
di = e[i]
else: # i > 1
ni = e[i]*n[i-1] + n[i-2]
di = e[i]*d[i-1] + d[i-2]
n.append(ni)
d.append(di)
yield ni, di
def wiener_attack(e, n):
cf = cf_expansion(e, n)
for k, d in convergents(cf):
if k == 0:
continue
phi = (e * d - 1) // k
b = phi - n - 1
delta = b * b - 4 * n
if delta < 0:
continue
root, exact = gmpy2.iroot(delta, 2)
if exact:
p, q = (-b + root) // 2, (-b - root) // 2
if p * q == n:
return p, q
e = 354611102441307572056572181827925899198345350228753730931089393275463916544456626894245415096107834465778409532373187125318554614722599301791528916212839368121066035541008808261534500586023652767712271625785204280964688004680328300124849680477105302519377370092578107827116821391826210972320377614967547827619
n = 460657813884289609896372056585544172485318117026246263899744329237492701820627219556007788200590119136173895989001382151536006853823326382892363143604314518686388786002989248800814861248595075326277099645338694977097459168530898776007293695728101976069423971696524237755227187061418202849911479124793990722597
p, q = wiener_attack(e, n)
# p = 28805791771260259486856902729020438686670354441296247148207862836064657849735343618207098163901787287368569768472521344635567334299356760080507454640207003
print("p = %d" % int(p))
# q = 15991846970993213322072626901560749932686325766403404864023341810735319249066370916090640926219079368845510444031400322229147771682961132420481897362843199
print("q = %d" % int(q))
c = 430518885052463211928880150309746899793280569494514717229804457610645654546618397141033560961143804493709939917151868116850149667503379601542677290248006042112387562073597991532984562273435948997353239670931506060376329812189999562605693486930504349878154273868213374018040795628048038832072369044250913887074
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{wieneR_is_n0t_diFFicuLt}
Boneh Durfee Method #
当私钥解密指数 d 比 n小很多时(d < n^0.292)适用，论文参看Cryptanalysis of RSA with Private Key d Less Than N^0.292 ，实现参看https://www.cryptologie.net/article/241/implementation-of-boneh-and-durfee-attack-on-rsas-low-private-exponents/
题目
思路
发现 e 比较大，尝试wiener攻击不成功，遂尝试Boneh Durfee Method(推测d < n^0.292)
openssl rsa -pubin -in pub.key -text -noout
Public-Key: (1018 bit)
Modulus:
03:a6:16:08:48:fb:17:34:cb:d0:fa:22:ce:f5:82:
e8:49:22:3a:c0:45:10:d5:15:02:55:6b:64:76:d0:
73:97:f0:3d:f1:55:28:9c:20:11:2e:87:c6:f3:53:
61:d9:eb:62:2c:a4:a0:e5:2d:9c:d8:7b:f7:23:52:
6c:82:6b:88:38:7d:06:ab:c4:27:9e:35:3f:12:ad:
8e:c6:2e:a7:3c:47:32:1a:20:b8:96:44:88:9a:79:
2a:73:15:2b:c7:01:4b:80:a6:93:d2:e5:8b:12:3f:
a9:25:c3:56:b1:eb:a0:37:a4:dc:ac:8d:8d:e8:09:
16:7a:6f:cc:30:c5:c7:85
Exponent:
03:65:96:2e:8d:ab:a7:ba:92:fc:08:76:8a:5f:73:
b3:85:4f:4c:79:96:9d:55:18:a0:78:a0:34:43:7c:
46:69:bd:b7:05:be:4d:8b:8b:ab:f4:fd:a1:a6:e7:
15:26:9e:87:b2:8e:ec:b0:d4:e0:27:26:a2:7f:b8:
72:18:63:74:07:20:f5:83:68:8e:55:67:eb:10:72:
9b:b0:d9:2b:32:2d:71:99:49:e4:0c:57:19:8d:76:
4f:1c:63:3e:5e:27:7d:a3:d3:28:1e:ce:2c:e2:eb:
4d:f9:45:be:5a:fc:3e:78:49:8e:d0:48:9b:24:59:
05:96:64:fe:15:c8:8a:33
答案
python3 RsaCtfTool.py --publickey pub.key --uncipherfile flag2.enc --attack boneh_durfee
...
STR : b'\x00\x02\xff\x1c\xd4\xd6\x1e\xa4\x84S\xa3c\xd3\xcb?f\xa4@\xba\t\x19h\xfc\xcc\xd8e\x94\xe55\x88\xfe\xe5[\x9f\xf0\xb4\x85\x08(\xcf\xd1\xe0\xd9\x91GHj`\x93\xfa\x9b\x1a\x80S\x1f\xf9~\x9d\x11(\xb7\x82\xb6?\\\x04\x8d\xba\xb9\r\x96\x9b\xba*\x12(~\xfe\xee\x1eLj\x085\x95U\x13\xad\x00flag{6cff864a062f2aa63a2e332c1b152a95}\n'
dp泄漏 #
dp 这个信息使用 openssl 命令展示私钥信息时会有展示，这种参数是为了让解密的时候更快速而产生的
已知dp = d mod (p-1)，能推出如下结论：
dp = k1(p-1) + d -> d = dp - k1(p-1)
ed = 1 mod (p-1)*(q-1) -> ed = k2(p-1)(q-1) + 1 -> 1 = ed - k2(p-1)(q-1)
结合以上，1 = e(dp - k1(p-1)) - k2(p-1)(q-1) -> edp = 1 mod (p-1) -> edp = k3(p-1) + 1
又因为 dp < p - 1，代入 edp = k3(p-1) + 1，所以 1 < k3 < e
结合做题就是爆破k3 in range(1,e+1)，如果使得k | edp - 1，则得商可能为 p-1；同时通过n % p筛选
题目
n = 0xe0f788940e961b1ec62e32684a42bec46851acea223ee6119e918c7f1067a2d7401b944a19122dbbd5adf164b9327d966122f7e4ed9a33f89c3e7bffb935f6240f87c3cf9e27d95eaad3c4efc1b3b1fc315b81de8513b80c1d907efe9075c4ac581d8c992854aae86981c7e23b167203f0ebcb8e9ebceb77631815041aa7dbdf
e = 0x10001
c = 0x89c678cdc9267c37a1d819b9d0934da926ee7865aa36da2632c8c9f91487b0824b6dfc4a595857c92c0d2519dfff6d5eb87cc98c5a6b060c003443c589b04803cff1be79d337aaf13bacebf18c7f6d549aa7b4cbd5ffe85a50bd1a291f629e6db02b438b3d61e5f560a63b3b4941c3fbc58e8886eb482f40b087a006f426204c
dp = 0x185c5fb9e2623b0c766e9a661b062f205f88ad87a93f743578ccfa1744af966899e49feeb2842b3b34aa6f8bc167f5015f76460219354c686d5e3d9dabb1591d
（dp = d % (p-1)）
思路
dp泄漏
代码
import libnum
n = 0xe0f788940e961b1ec62e32684a42bec46851acea223ee6119e918c7f1067a2d7401b944a19122dbbd5adf164b9327d966122f7e4ed9a33f89c3e7bffb935f6240f87c3cf9e27d95eaad3c4efc1b3b1fc315b81de8513b80c1d907efe9075c4ac581d8c992854aae86981c7e23b167203f0ebcb8e9ebceb77631815041aa7dbdf
e = 0x10001
c = 0x89c678cdc9267c37a1d819b9d0934da926ee7865aa36da2632c8c9f91487b0824b6dfc4a595857c92c0d2519dfff6d5eb87cc98c5a6b060c003443c589b04803cff1be79d337aaf13bacebf18c7f6d549aa7b4cbd5ffe85a50bd1a291f629e6db02b438b3d61e5f560a63b3b4941c3fbc58e8886eb482f40b087a006f426204c
dp = 0x185c5fb9e2623b0c766e9a661b062f205f88ad87a93f743578ccfa1744af966899e49feeb2842b3b34aa6f8bc167f5015f76460219354c686d5e3d9dabb1591d
temp = e*dp - 1
for k in range(1, e+1):
if temp % k == 0:
p = temp // k + 1
if n % p == 0:
break
q = n // p
n = p*q
phi_n = (p-1)*(q-1)
d = libnum.invmod(e, phi_n)
m = pow(c,d,n)
# b'flag{tRy_t0_fiNd_faCt0rs}'
print(libnum.n2s(m))
e 与 φ(N) 不互素 #
e 与 φ(N) 不互素时，g = gcd(e, φ(N)，分为以下几种情况讨论：
- 当
m^g < n时
gcd(e, φ(N) = g
e = g * e1
c ≡ (m ^ (g * e1)) mod n，将 m^g 视为新的消息m1，c ≡ (m1 ^ e1) mod n
求得解密指数 e1d1 ≡ 1 mod φ(N)
e = 2，rabbin加密
e 与 (p-1)互素
ed ≡ 1 mod (p-1)(q-1)，而gcd(e, p-1) = 1
由 ed ≡ 1 mod (p-1)(q-1)定义得，ed ≡ 1 mod (p-1)，求得d
由 m ≡ c^d mod pq定义得，m ≡ c^d mod p
- 其他 有限域下开n次方根，可以使用AMM算法，同时利用中国剩余定理遍历得到的根的列表做筛选
https://blog.csdn.net/qq_57235775/article/details/132575196
https://zhouyetao.github.io/2021/11/03/RSA%E7%AC%94%E8%AE%B0/ https://blog.soreatu.com/posts/intended-solution-to-crypto-problems-in-nctf-2019/#easyrsa909pt-2solvers