0x01 描述
Oracles can be your best friend, they will decrypt anything, except the flag’s ciphertext. How will you break it? Connect with nc mercury.picoctf.net 30048
0x02 题目
Welcome to the Padding Oracle Challenge
This oracle will take anything you give it and decrypt using RSA. It will not accept the ciphertext with the secret message... Good Luck!
n: 69315521541776181926029049649245965957391183332070023208364692145871604532959183886164793893186420533510702965448334751917216914952341930491349003881059329161182649877348336119029522943993244991000988440684576464264779368716970835831887993250097420699368246295904223717546014520011965308743488074716211808867
e: 65537
ciphertext: 10943743307634009656048470323622293474962047098124080105188909507102276585937857751044938488180933071088600052732305449558922661336669652695702626679056086341387362956365224096350649127425421670340891880770930198329196033426401510802532295066249393945633049602043815948296600643510994452951729385721327391503
Give me ciphertext to decrypt:
当输入ciphertext时提示Will not decrypt the ciphertext. Try Again
说明解密后的值不能是flag，必须想办法绕过
由于在RSA解密有
$$
c^d \equiv m \mod N
$$
所以令 $c’=k^e \cdot c$，即
$$
(k^e \cdot c)^d \equiv m’ \mod\ N
$$
但由 $c’$ 求出的明文为 $m’$ ，而非 $m$ ，因此还需要一些处理
由于
$$
ed \equiv 1 \mod \varphi(N)
$$
所以 $ed=1+t \varphi(N)(t \in Z)$
推导可得
$$
\begin{aligned} m’ &\equiv (k^e \cdot c)^d \mod N \\ &\equiv k^{ed} \cdot c^d\mod N \\ &\equiv k^{1+tN} \cdot m \mod\ N \\ &\equiv km \cdot k^{t \varphi(N)}\mod N \end{aligned}
$$
由欧拉定理
$$
a^{\varphi (n)} \equiv 1 \mod n
$$
所以
$$
\begin{aligned} m’ &\equiv km \cdot 1^t \mod N \\ & \equiv km \mod N\end{aligned}
$$
所以在拿到机器返回的 $m’$ 后只需要将其除以 $k$ 即可
$$
m = \frac{m’}{k} \mod N
$$
试过 $k=2$ ，结果在最后 $m’$ 除以二的时候丢失精度了…
所以为了计算方便，令 $k=-1$ ，写出脚本
0x03 EXP
from Crypto.Util.number import long_to_bytes
n = 69315521541776181926029049649245965957391183332070023208364692145871604532959183886164793893186420533510702965448334751917216914952341930491349003881059329161182649877348336119029522943993244991000988440684576464264779368716970835831887993250097420699368246295904223717546014520011965308743488074716211808867
e = 65537
c = 14760237527003939522037454953346983099427112390162061652582720571179693772355325689849852617578556135298342700083773562739027864155903546324197473112065043242830267629803151527521247107310926922165179622722790761716001099101933656981570255256791522657248037574253294665838558345981272938562782193380411371143
cprime = c * pow(-1, e, n) % n
print(cprime)
mprime = 69315521541776181926029049649245965957391183332070023208364692145871604532959183886164793893186420533510702965448334751917216914952341930491349003881059329161182649877348336119029522943702969960805138401211119845897323483647005086980609916493353700252664931778502864450223245482542713863358775177026288572902
print(long_to_bytes((mprime * -1) % n))
其中cprime，即 $c’$ 为
54555284014772242403991594695898982857964070941907961555781971574691910760603858196314941275607864398212360265364561189178189050796438384167151530768994285918352382247545184591508275836682318068835808817961785702548778269615037178850317737993305898042120208721650929051707456174030692370180705881335800437724
把这个数输入终端，返回 $m’$ ，即mprime
69315521541776181926029049649245965957391183332070023208364692145871604532959183886164793893186420533510702965448334751917216914952341930491349003881059329161182649877348336119029522943702969960805138401211119845897323483647005086980609916493353700252664931778502864450223245482542713863358775177026288572902
