RSA-7 低解密指数攻击

知识点

本例是一种特殊的攻击方法，因而具有很明显的攻击特征。如果知道此种攻击方法，则能一瞬轻易得到 flag。但是如果不知道这种攻击方法，则几乎不可能得到 flag。

除非大佬

本例将引出一种典型的攻击类型 Wiener’s attack 。

连分数

如果想要看懂下面的攻击原理，则需要具备连分数的知识。这里推荐一个写的比较详细的参考文章。

限于篇幅，这里不做展开介绍，有点太长了。

但是仅仅是使用的话，不需要进行太深入研究，只需要知道是啥，怎么展开，数学中研究是主要意义的什么。看到参考文章的第一章结束就好了。

Wiener’s attack

背景介绍

由于 RSA 需要进行模幂计算，越大的指数计算时间越长。在有些场景下，解密方的算法可能受限，所以需要减轻解密方的计算压力以避免超长时间的解密。故通过将解密指数 $d$ 设计得很小，可以加快解密的速度。

攻击介绍

但由此，也会引入安全问题，即 Wiener’s attack。

攻击条件

条件：如果满足解密的指数 $d < \frac{1}{3}n^{\frac{1}{4}}$ 且 $q<p<2q$，可以通过 Wiener’s attack 攻击得到解密的指数 $d$ 从而破译出密文得到明文。

攻击原理

回忆 RSA 的加解密过程：

$$n=pq, \varphi(n)=(p-1)(q-1)$$

其中 $p, q$​​​ 都是很大的质数，所以不难得到 $pq \gg p+1$​​ ，所以:

$$\varphi(n)=(p-1)(q-1)=pq-(p+1)+1 \to n$$

同时加解密指数 $e, d$​​ 又满足:

$$ed \equiv 1 \pmod {\varphi(n)} \\ \to ed - k\varphi(n) = 1$$

将上述式子进行变化，左右同除以 $d\varphi(n)$ 可以得到：

$$\frac{e}{\varphi(n)} - \frac{k}{d} = \frac{1}{d\varphi(n)}$$

此处开始进行近似，利用上面的结论：

$$\because \varphi(n) \to n \\ \therefore \frac{e}{n} - \frac{k}{d} \approx \frac{1}{d\varphi(n)}$$

此处又因为 $\varphi(n)$ 很大，同时又乘以 $d >1$ ，故 $d\varphi(n)$ 也很大，所以 $\frac{1}{d\varphi(n)} \to 0$ ：

$$\because \frac{1}{d\varphi(n)} \to 0 \\ \therefore \frac{e}{n} - \frac{k}{d} \approx \frac{1}{d\varphi(n)} \to 0 \\ \therefore \frac{e}{n} \approx \frac{k}{d} \cdots (\frac{e}{n}>\frac{k}{d}\\$$

上面主要是想通过近似代换将未知的 $\varphi(n)$​ 进行代换或者消除。这样左侧的两个数字 $e, n$ 属于公钥，我们可以直接计算出来。

然后 Winner 在 paper 《Cryptanalysis of short RSA secret exponents》 中证明了：将 $\frac{e}{n}$ 的连分数进行展开，可以精确覆盖到比 $\frac{e}{n}$ 略小的 $\frac{k}{d}$ 。

此时枚举 $\frac{e}{n}$​ 展开的连分数，然后逐一进行判断，在每一次判断中，都相当于假设了一组可能的 $d, k$​ 然后通过 $ed - k \varphi(n) = 1$​ 可以计算出 $\varphi(n)$​ 。此时就转化为了前面提到的已知 $\varphi(n), n$​ 分解 $n$​ 的方法了。然后再尝试进行分析，事实上，只需要判断一下构建的二次方程是否有解即 $\Delta>0?$​ 来确定是否分解成功，从而得到此时猜测的 $d$​ 是否是正确的。（你也可以直接假设 $d$​ 是正确的，然后进行解密，判断明文中是否有 flag 字样。

从这个分析过程也很容易看出，解密指数 $d$ 越大，通过连分数就越难进行分解，所以前面的条件中指出需要 $d$ 足够小。

攻击利用代码

有了上述的分析，其实代码实现就很简单了。可以用网上的很多轮子如：rsa-wiener-attack

以下代码是我自己写的：

# 显然对于不互质的可以先将 gcd 提出来
import gmpy2

def gcd(a, b):
	"""
	return gcd(a,b)
	"""
	while b:
		a, b = b, a%b
	return a

def get_continued_Frac(a, b):
	"""
	将 a/b 展开为连分数
	"""

	frac = []

	# 辗转相除法展开
	while b:
		frac.append(a//b)
		a, b = b, a%b

	return frac

def general_division_add(numerator, denominator, addnum):
	"""
	通分计算 numerator/denominator + addnum
	"""

	# 先直接按照乘法通分
	numerator = numerator + addnum * denominator

	# 再将当前分数化简
	d = gcd(numerator, denominator)
	numerator //= d
	denominator //= d

	return numerator, denominator


def calc_continued_Frac(frac):
	"""
	计算前 i 项 构成的连分数 frac 通分加合之后的分子和分母，分别表示猜测的 k 和 d
	"""
	# [29,2,2,1]

	numerator = 0
	denominator = 1
	# 枚举的是 addnum
	for addnum in frac[::-1]:
		# 计算完了要取倒数
		denominator, numerator = general_division_add(numerator, denominator, addnum)

	return denominator, numerator


def guess_k_d(frac):
	"""
	这样嵌套写是为了看起来更清晰知道，本次连分数求和的目的是为了猜测 k 和 d
	"""
	return calc_continued_Frac(frac)


def calc_d(k, d, e, n):
	"""
	通过 Delta 判断是否有解，确定 d 是否正确
	phi = (ed-1)/k
	"""

	if (e*d-1) % k != 0:
		return False

	phi = (e*d-1)//k

	a = 1
	b = phi - n - 1
	c = n

	delta = b**2-4*a*c
	x = gmpy2.iroot(delta, 2)
	if not x[1]:
		return False

	p = (-b+x[0])//(2*a)
	q = (-b-x[0])//(2*a)
	d = gmpy2.invert(e, phi)

	return (p, q, d)


def wieners_attack(e, n):
	"""
	wiener's attack to get d by (e, n)
	"""
	FRAC = get_continued_Frac(e, n)

	for i in range(len(FRAC)):
		k, d = guess_k_d(FRAC[:i])
		# 0 的逼近没有意义
		if k == 0:
			continue

		tag = calc_d(k, d, e, n)
		if tag:
			print("success!")
			return tag


if __name__ == "__main__":
	e = 3047442173541658754667464233797118324917469250436575767227172319344577259865313428705759330024959317716760816959590728238918140105663188172228696589411452947738069773833351725455888549656717874059636289036277785342126992626060696063089487811946920569580454880169977542532087635095357205433679009382368108273
	n = 135568509670260054049994954417860747085442883428459182441559553532993752593294067458983143521109377661295622146963670193783017382697726454953197805014428888491744355387957923382241961401063461549210355871385000347645387907568135032087942016502668629010859519249039662555733548461551175133582871220209515648241

	p, q, d = wieners_attack(e, n)
	print(f"p = {p}\nq = {q}\nd = {d}")

例题

题目

听说前面你都搞定啦？这次就很不一样了！

e = 11850552481503020257392808424743510851763548184936536180317707155841959788151862976445957810691568475609821000653594584717037528429828330763571556164988619635320288125983463358648887090031957900011546300841211712664477474767941406651977784177969001025954167441377912326806132232375497798238928464025466905201977180541053129691501120197010080001677260814313906843670652972019631997467352264392296894192998971542816081534808106792758008676039929763345402657578681818891775091140555977382868531202964486261123748663752490909455324860302967636149379567988941803701512680099398021640317868259975961261408500449965277690517
n = 12238605063252292170613110607692779326628090745751955692266649177882959231822580682548279800443278979485092243645806337103841086023159482786712759291169541633901936290854044069486201989034158882661270017305064348254800318759062921744741432214818915527537124001063995865927527037625277330117588414586505635959411443039463168463608235165929831344586283875119363703480280602514451713723663297066810128769907278246434745483846869482536367912810637275405943566734099622063142293421936734750356828712268385319217225803602442033960930413469179550331907541244416573641309943913383658451409219852933526106735587605884499707827
c = 6423785507684416773666948899915169554070001400671738254418895224701431744592066315840324501358322894303666459029450295999767148813342646167264341287124393625378316616139863708766163081219598771527606199602984020288261461737264281249264845116375731213029934802447231553854792109268285484082449452535764527888708733739012186167288822598437102840518848315984522212122067222074782253835923782275677317977038532227511279242281012000471845266622423324215667858024608033813931825929847132259909037530308932262269043122554140838785194939880489778556772907801622627958920544315663033749462060571279761917620516943658053070420

题解

这个题给人一种很明显的感觉就是 $e$​ 不对劲，一般的公钥也就是 $65537$​ 这个不是也不要紧，但是这个也太大了吧？一看就和 $n$​​ 差不多长了。于是这就是很显然的 Wiener’s attack 的特征。因为 $ed \equiv 1 \pmod{\varphi(n)}$ 你 $e$ 变大了 $d$ 自己就变小了，虽然有 mod ，但基本规则还是满足的。

那都知道了是用什么攻击了，于是就直接将上面的轮子贴下来咯。

解密脚本如下：

# 显然对于不互质的可以先将 gcd 提出来
import gmpy2

def gcd(a, b):
	"""
	return gcd(a,b)
	"""
	while b:
		a, b = b, a%b
	return a

def get_continued_Frac(a, b):
	"""
	将 a/b 展开为连分数
	"""

	frac = []

	# 辗转相除法展开
	while b:
		frac.append(a//b)
		a, b = b, a%b

	return frac

def general_division_add(numerator, denominator, addnum):
	"""
	通分计算 numerator/denominator + addnum
	"""

	# 先直接按照乘法通分
	numerator = numerator + addnum * denominator

	# 再将当前分数化简
	d = gcd(numerator, denominator)
	numerator //= d
	denominator //= d

	return numerator, denominator


def calc_continued_Frac(frac):
	"""
	计算前 i 项 构成的连分数 frac 通分加合之后的分子和分母，分别表示猜测的 k 和 d
	"""
	# [29,2,2,1]

	numerator = 0
	denominator = 1
	# 枚举的是 addnum
	for addnum in frac[::-1]:
		# 计算完了要取倒数
		denominator, numerator = general_division_add(numerator, denominator, addnum)

	return denominator, numerator


def guess_k_d(frac):
	"""
	这样嵌套写是为了看起来更清晰知道，本次连分数求和的目的是为了猜测 k 和 d
	"""
	return calc_continued_Frac(frac)


def calc_d(k, d, e, n):
	"""
	通过 Delta 判断是否有解，确定 d 是否正确
	phi = (ed-1)/k
	"""

	if (e*d-1) % k != 0:
		return False

	phi = (e*d-1)//k

	a = 1
	b = phi - n - 1
	c = n

	delta = b**2-4*a*c
	x = gmpy2.iroot(delta, 2)
	if not x[1]:
		return False

	p = (-b+x[0])//(2*a)
	q = (-b-x[0])//(2*a)
	d = gmpy2.invert(e, phi)

	return (p, q, d)


def wieners_attack(e, n):
	"""
	wiener's attack to get d by (e, n)
	"""
	FRAC = get_continued_Frac(e, n)

	for i in range(len(FRAC)):
		k, d = guess_k_d(FRAC[:i])
		# 0 的逼近没有意义
		if k == 0:
			continue

		tag = calc_d(k, d, e, n)
		if tag:
			print("success!")
			return tag


if __name__ == "__main__":
	e = 3047442173541658754667464233797118324917469250436575767227172319344577259865313428705759330024959317716760816959590728238918140105663188172228696589411452947738069773833351725455888549656717874059636289036277785342126992626060696063089487811946920569580454880169977542532087635095357205433679009382368108273
	n = 135568509670260054049994954417860747085442883428459182441559553532993752593294067458983143521109377661295622146963670193783017382697726454953197805014428888491744355387957923382241961401063461549210355871385000347645387907568135032087942016502668629010859519249039662555733548461551175133582871220209515648241
	c = 130120812377832417286104222457458309983570304365625148630229089933000228028818603755020533891985367026152405860566430269955539189768231036509478907868355152155314871113690115899272595597568805364726625998391205488017790451017392782657028623338866335943620081638386626654885413162134521065866286150284452978399

	p, q, d = wieners_attack(e, n)
	m = pow(c, d, n)
	
	flag = long_to_bytes(m)
	print(flag)
	# b"flag{baby_RSA_wiener's_attack_so_easy}"