XCTF-4th-QCTF-2018-babyrsa

Baby RSA e = 0x10001 n = 0x0b765daa79117afe1a77da7ff8122872bbcbddb322bb078fe0786dc40c9033fadd639adc48c3f2627fb7cb59bb0658707fe516967464439bdec2d6479fa3745f57c0a5ca255812f0884978b2a8aaeb750e0228cbe28a1e5a63bf0309b32a577eecea66f7610a9a4e720649129e9dc2115db9d4f34dc17f8b0806213c035e22f2c5054ae584b440def00afbccd458d020cae5fd1138be6507bc0b1a10da7e75def484c5fc1fcb13d11be691670cf38b487de9c4bde6c2c689be5adab08b486599b619a0790c0b2d70c9c461346966bcbae53c5007d0146fc520fa6e3106fbfc89905220778870a7119831c17f98628563ca020652d18d72203529a784ca73716db c = 0x4f377296a19b3a25078d614e1c92ff632d3e3ded772c4445b75e468a9405de05d15c77532964120ae11f8655b68a630607df0568a7439bc694486ae50b5c0c8507e5eecdea4654eeff3e75fb8396e505a36b0af40bd5011990663a7655b91c9e6ed2d770525e4698dec9455db17db38fa4b99b53438b9e09000187949327980ca903d0eef114afc42b771657ea5458a4cb399212e943d139b7ceb6d5721f546b75cd53d65e025f4df7eb8637152ecbb6725962c7f66b714556d754f41555c691a34a798515f1e2a69c129047cb29a9eef466c206a7f4dbc2cea1a46a39ad3349a7db56c1c997dc181b1afcb76fa1bbbf118a4ab5c515e274ab2250dba1872be0  

这个话题很简单，然后n是一个长2048位的大整数，n是奇数

通过factordb以及yafu.factor()等不能直接分解。

标题中还有一个服务端口，请访问试试。

┌──(mangofeng?kali)-[~] └─$ nc 111.200.241.244 55759                                                                 1 ? ----------------------------- baby rsa ----------------------------- Come and Decode your data If you give me ciphertext, I can tell you whether decoded data is even or odd You can input ciphertext(hexdecimal) now 

一般意思如下：

通过输入一个加密的密文，服务器会告诉你用私钥d解密该密文后，所得的明文结果是even偶数还是odd奇数

转换成数学表达就是:

I n p u t :    c ≡ m e ( m o d n )    O u t p u t : P a r i t y ( m ≡ c d ( m o d n ) ) = o d d   o r   e v e n Input:\ \ c\equiv m^e\pmod{n} \ \ Output: Parity(m\equiv c^d\pmod{n})=odd \ or\ even Input:  c≡me(modn)  Output:Parity(m≡cd(modn))=odd or even

通过这种机制，我们可以向服务器传入的值进行一些修改操作

例如:

我们传入 2 e ∗ c 即 为 ( 2 m ) e , 而 服 务 器 会 将 ( 2 m ) e 解 密 成 2 m 后 告 诉 我 们 其 模 下 的 奇 偶 性 . 2^e*c即为(2m)^e,而服务器会将(2m)^e解密成2m后告诉我们其模下的奇偶性. 2e∗c即为(2m)e,而服务器会将(2m)e解密成2m后告诉我们其模下的奇偶性.

我们知道任意一个自然数m,其与2的乘积一定为偶数

所 以 在 m o d ( n ) 下 : 所以在mod(n)下: 所以在mod(n)下:

若 2 m < n ， 即 解 密 后 的 传 入 参 数 没 有 经 过 取 模 操 作 的 话 , 那 么 其 奇 偶 性 一 定 为 e v e n ， 因 为 2 m 为 偶 数 若2m<n，即解密后的传入参数没有经过取模操作的话,那么其奇偶性一定为even，因为2m为偶数 若2m<n，即解密后的传入参数没有经过取模操作的话,那么其奇偶性一定为even，因为2m为偶数

若 2 m > n , 即 解 密 后 的 传 入 参 数 经 过 了 取 模 操 作 ， 那 么 其 奇 偶 性 一 定 为 o d d , 因 为 2 m 为 偶 数 , n 为 奇 数 若2m>n,即解密后的传入参数经过了取模操作，那么其奇偶性一定为odd,因为2m为偶数,n为奇数 若2m>n,即解密后的传入参数经过了取模操作，那么其奇偶性一定为odd,因为2m为偶数,n为奇数

根据上面两点我们可以得到以下结论:

若返回了even，我们可以得到 0 < 2 m < n ⇒ 0 < m < n 2 0<2m<n\Rightarrow 0<m<\frac{n}{2} 0<2m<n⇒0<m<2n​

若返回了odd,我们可以得到 n < 2 m < 2 n ⇒ n 2 < m < n n<2m<2n\Rightarrow \frac{n}{2}<m<n n<2m<2n⇒2n​<m<n

通过返回的结果，我们可以将明文所在的缩小到原来范围的二分之一。

若我们继续将 2 2 e ∗ c 即 4 e ∗ c 传 入 ， 即 可 将 范 围 缩 小 到 四 分 之 一 2^{2e}*c即4^e*c传入，即可将范围缩小到四分之一 22e∗c即4e∗c传入，即可将范围缩小到四分之一

如 此 进 行 下 去 ， 我 们 只 需 要 l o g 2 n 次 就 可 以 找 出 明 文 如此进行下去，我们只需要log_2^n次就可以找出明文 如此进行下去，我们只需要log2n​次就可以找出明文

e = 0x10001
n = 0x0b765daa79117afe1a77da7ff8122872bbcbddb322bb078fe0786dc40c9033fadd639adc48c3f2627fb7cb59bb0658707fe516967464439bdec2d6479fa3745f57c0a5ca255812f0884978b2a8aaeb750e0228cbe28a1e5a63bf0309b32a577eecea66f7610a9a4e720649129e9dc2115db9d4f34dc17f8b0806213c035e22f2c5054ae584b440def00afbccd458d020cae5fd1138be6507bc0b1a10da7e75def484c5fc1fcb13d11be691670cf38b487de9c4bde6c2c689be5adab08b486599b619a0790c0b2d70c9c461346966bcbae53c5007d0146fc520fa6e3106fbfc89905220778870a7119831c17f98628563ca020652d18d72203529a784ca73716db
c = 0x4f377296a19b3a25078d614e1c92ff632d3e3ded772c4445b75e468a9405de05d15c77532964120ae11f8655b68a630607df0568a7439bc694486ae50b5c0c8507e5eecdea4654eeff3e75fb8396e505a36b0af40bd5011990663a7655b91c9e6ed2d770525e4698dec9455db17db38fa4b99b53438b9e09000187949327980ca903d0eef114afc42b771657ea5458a4cb399212e943d139b7ceb6d5721f546b75cd53d65e025f4df7eb8637152ecbb6725962c7f66b714556d754f41555c691a34a798515f1e2a69c129047cb29a9eef466c206a7f4dbc2cea1a46a39ad3349a7db56c1c997dc181b1afcb76fa1bbbf118a4ab5c515e274ab2250dba1872be0
from pwn import *
from tqdm import tqdm
from Crypto.Util.number import *
left=0
right=n
num=0
import gmpy2
for find in tqdm(range(len(bin(n)[2:]))):# 加一个进度条，让人很安心
    num+=1
    tmp=gmpy2.powmod(2,num*e,n)
    senddata=hex((c*tmp)%n)[2:]
    io=remote('111.200.241.244',64931)# 将该连接放入循环是因为 他连接一次只能给你判断一次parity 然后断开
    io.recv()
    io.sendline(senddata)
    ans=io.recvline().decode()[:-1]
    print(ans)
    if ans=='odd': #当返回为奇时，证明经过了取模，范围取大的那部分，即左边区间left向右移动
        left=(left+right)//2 if (left+right)%2==0 else (left+right)//2+1
    else: #当返回为偶时，证明没经过取模，范围取小的那部分，即右边区间right向左移动
        right=(left+right)//2 if (left+right)%2==0 else (left+right)//2+1
    print(right-left)# 不断夹逼（二分）当log n次以后，right与left会确定下明文
print((left,right))
with open(r"D:\\Mango\\babyrsa\\output.txt",'w')as f:
    f.write((left,right)) # 有时候一跑完然后结束之后全是连接服务的断开提醒，次数太多直接刷屏，所以记录下来
    f.close()
import gmpy2
for i in tqdm(range(left-2**10,right+2**10)): # 为了计算进误差，在最后left与right左右两边2^10为范围寻找明文
    if(gmpy2.pow(i,e,n)==c):
        print(i)
        print(number.long_to_bytes(i))
        break
    else:
        continue

总结:对密文乘(2^e%n)操作,再解密的时候，如果为偶数，说明明文再(0, n/2)之间，否则在(n/2, n)之间

如此迭代操作，只需要log n的次数就可以知道明文

(慎重调试！！！！每次调一次想看一看结果会怎么变化，你就要等差不多40分钟才能跑出结果来，复现这道题我大概跑了六次吧)

odd
6
100%|█████████████████████████████████████████████████████████████████████████████▉| 2045/2048 [06:01<00:00,  5.77it/s][x] Opening connection to 111.200.241.244 on port 64931
[x] Opening connection to 111.200.241.244 on port 64931: Trying 111.200.241.244
[+] Opening connection to 111.200.241.244 on port 64931: Done
odd
3
100%|█████████████████████████████████████████████████████████████████████████████▉| 2046/2048 [06:02<00:00,  5.88it/s][x] Opening connection to 111.200.241.244 on port 64931
[x] Opening connection to 111.200.241.244 on port 64931: Trying 111.200.241.244
[+] Opening connection to 111.200.241.244 on port 64931: Done
odd
1
100%|█████████████████████████████████████████████████████████████████████████████▉| 2047/2048 [06:02<00:00,  5.96it/s][x] Opening connection to 111.200.241.244 on port 64931
[x] Opening connection to 111.200.241.244 on port 64931: Trying 111.200.241.244
[+] Opening connection to 111.200.241.244 on port 64931: Done
odd
0
100%|██████████████████████████████████████████████████████████████████████████████| 2048/2048 [06:02<00:00,  5.65it/s]
(560856645743734814774953158390773525781916094468093308691660509501812376, 560856645743734814774953158390773525781916094468093308691660509501812376)
  0%|                                                                                         | 0/2048 [00:00<?, ?it/s]560856645743734814774953158390773525781916094468093308691660509501812349
b'QCTF{RSA_parity_oracle_is_fun}'
 49%|████████████████████████████████████▉                                       | 997/2048 [00:00<00:00, 13114.39it/s]

https://ctf-wiki.org/crypto/asymmetric/rsa/rsa_chosen_plain_cipher/

[https://blog.csdn.net/weixin_44110537/article/details/108956759](