RSA Parity Oracle

Dawn_whisper和他的辣鸡代码成长史（雾

先挂个CTFwiki的链接，~~如果能看懂就不用接着往下看我这个垃圾博客了~~

适用条件

搬一段wiki上的原话：

假设目前存在一个 Oracle，它会对一个给定的密文进行解密，并且会检查解密的明文的奇偶性，并根据奇偶性返回相应的值，比如 1 表示奇数，0 表示偶数。那么给定一个加密后的密文，我们只需要 log(N) 次就可以知道这个密文对应的明文消息。

~~说的是个啥玩意~~

简单来说就是有个服务器，他会提供一个不完整的解密功能，而不完整体现在哪里呢？这个服务器只会提供给你解密之后的数据的二进制的最后一位（你可以理解为他只返回明文m%2之后的结果），那么我们可以通过分析返回的这个值来判断明文m与n之间的关系，进而可以推出m。

原理

第一步

我们已知$c = m^e(mod n)$，那么我们第一次给服务器发送$c\cdot2^e$，接下来服务器会计算$(c\cdot2^e)^d=c^d\cdot2^{e\cdot d}=2\cdot m$，所以服务器返回的是2m%2的结果，接下来划重点：

如果返回0，说明$2m < n$，因为乘2之后必定是一个偶数，膜2之后一定等于0（亦可以理解为2m变为二进制后最低位是0），也就说明$0 < m < \dfrac{n}{2}$
如果返回1，说明$2m > n$，因为乘2之后必定是一个偶数，而n一定是一个奇数（俩质数相乘肯定是个奇数），返回1的原因是$2m$在膜$n$时，因为比n大，所以会变成$2m-n$，这样得到的就是一个奇数，膜2之后一定等于1（2m变为二进制后最低位是1），也就说明$ \dfrac{n}{2} < m < n$

如果上面没有看懂，请务必仔细理解！因为接下来会不断利用这个部分进行运算，也就是数学归纳

第二步

那么接下来我们继续分析，为了使其理解更容易，我们举个例子来想一想

我们假定$ \dfrac{3\cdot n}{4}< m <n$，而通过第一次我们的分析我们得知$ \dfrac{n}{2} < m < n$，接下来该怎么办呢？

我们第二次给服务器发送$c\cdot 4^e$，服务器则会输出$4m$与$n$的关系，而$3n<4m<4n$，所以在膜$n$之后会变成$4m-3n$，而减去了一个奇数，我们自然就会得到1！

如果假定$ \dfrac{n}{2}< m<\dfrac{3\cdot n}{4} $，我们就会得到0！

这个过程是不是很熟悉？没错当我们把2m当做一个整体时，就相当于我们又重复了一遍第一步！

第三步

草:hammer:，还等着我给你再写一遍啊，接着乘二就完事了

……

次数足够多之后，我们就可以通过二分法来找到最后的明文m

例题

1.2020 0xGame Crypto parityOracle

拿到题目一顿胡乱分析

看看代码，发现基本是板子题，只是把膜2换成了膜4

处理方法和平时基本一样，只是在数据分析时攻击函数从二分变成四分，

如果返回0，则$0< m<\dfrac{n}{4} $
如果返回1，则$\dfrac{n}{4}< m<\dfrac{n}{2}$
如果返回2，则$\dfrac{n}{2}< m<\dfrac{3\cdot n}{4}$
如果返回3，则$\dfrac{3\cdot n}{4}< m<n$

sol.py

from string import digits, ascii_letters
from pwn import *
from hashlib import sha256
from Crypto.Util.number import *

table = digits+ascii_letters
r = remote("49.235.239.97", "10001")

def passpow():
	r.recvuntil("sha256(XXXX+")
	pre = r.recv(16).decode()
	rev = r.recvuntil(" == ")
	res = r.recv(64).decode()
	for a in table:
		for b in table:
			for c in table:
				for d in table:
					if(sha256((a+b+c+d+pre).encode()).hexdigest() == res):
						return a+b+c+d

def read_data():
	r.recvuntil("e = ")
	e = int(r.recvline().strip().decode())
	r.recvuntil("n = ")
	n = int(r.recvline().strip().decode())
	r.recvuntil("c = ")
	c = int(r.recvline().strip().decode())
	return e,n,c

w = passpow()
print('Successfully pass the pow!')
r.send(str(w)+'\n')
e,n,c=read_data()
high = n
low = 0
cnt=1
data = []
print('Data get!')
print('Waiting......')
while True:
	#print('now cnt is:',cnt)
	r.recvuntil('2. exit\n> ')
	r.sendline('1')
	c = (c*(4**e))%n
	r.sendline(hex(c))
	r.recvuntil('Your cipher (in hex): ')
	back = r.recv(1).strip().decode()
	back=int(back)
	data.append(back)
	divide = (high-low) // 4
	if(back == 0):
		high -= 3 * divide
	elif(back == 1):
		high -= 2 * divide
		low += divide
	elif(back == 2):
		high -= divide
		low += 2 * divide
	else:
		low += 3 * divide
	cnt += 1
	if(high <= low + 4):
		break

print('get flag!\nflag=',end='')
print(long_to_bytes(high))

r.interactive()