RSA oracle

Manger’s attack

这种oracle会判断接受到的数字 $m$ 是否大于一个给定的数字 $B$ 。如果 $m \le B$ 就返回 $True$ ，否则返回 $False$ , $m \in Integer(n)$ 。

Manger’s attack就是利用这个oracle恢复出 $m$ ，大致思想就是先一次找到 $f_1,f_2$ ，使得$f_1\cdot m\in [B,2B)$ 及 $f_2 \cdot m \in [n,n+B)$ 。

这样就给出了 $m$ 的一个初始范围，$m_{min}=\lceil\frac{n}{B}\rceil ,m_{max} = \lfloor \frac{n+B}{f_2} \rfloor$ 。然后再经过一些构造，不断将这个区间二分，从而得到 $m$ 。

下面给出oracle和attack的代码：

# https://github.com/rkm0959/rkm0959_implements/tree/main/Manger's_Attack
def oracle(c): # Oracle
	global cnt
	cnt += 1
	ptxt = pow(c, d, n)
	if ptxt < B:
		return True
	else:
		return False

def Manger_Attack(c):
	f1 = 2
	while True:
		val = (pow(f1, e, n) * c) % n
		if oracle(val):
			f1 = 2 * f1
		else:
			break
	f12 = f1 // 2
	f2 = ((n + B) // B) * f12
	while True:
		val = (pow(f2, e, n) * c) % n
		if oracle(val):
			break
		else:
			f2 += f12
	m_min = (n + f2 - 1) // f2
	m_max = (n + B) // f2
	# note the ERRATA from https://github.com/GDSSecurity/mangers-oracle
	while m_min < m_max:
		f_tmp = (2 * B) // (m_max - m_min)
		I = (f_tmp * m_min) // n 
		f3 = (I * n + m_min - 1) // m_min
		val = (pow(f3, e, n) * c) % n
		if oracle(val):
			m_max = (I * n + B) // f3
		else:
			m_min = (I * n + B + f3 - 1) // f3
	return m_min