密码学学习笔记之连分数

之前对论文《Generalization of Some Attacks on RSA with Small Prime Combination and Small Private Exponent》进行简单的翻译过后我们发现连分数这个基础概念还是挺重要的，另外其在佩尔方程等其他地方也有重要的应用，于是就准备稍微系统地学习一下连分数相关的知识。主要参考知乎这篇文章Wiener’s Attack Ride(维纳攻击法驾驭)

前置知识

定义一：连分数

连分数，就是对于任何一个有理数 $\alpha$，我们可以化成如下形式：$$a_0+\frac{1}{a_1 + \frac{1}{a_2+\frac{1}{\cdots+\frac{1}{a_n}}}}$$通常简记为$a_0+\frac{1}{a_1+}\frac{1}{a_2+}\cdots \frac{1}{a_n}$ 或 $[a_0;a_1,a_2,\cdots,a_n]$，其中 $a_0 \in \mathbb{Z}$。$a_1,a_2,\cdots,a_n \in \mathbb{N^*}$，且 $a_n \gt 1$

定理 1 任何一个有理数与其连分数形式是一一对应的。

证明：对于任意一个有理数 $\frac{b_0}{r_0}$，且 $(b_0,r_0)=1$ （即 $b_0,r_0$ 互素），我们可以写出如下等式$$b_0 = a_0 r_0 + r_1,0 \le r_1\lt r_0;$$

$$r_0 = a_1 r_1 + r_2,0 \le r_2\lt r_1;$$

$$r_1 = a_2 r_2 + r_3,0 \le r_3\lt r_2;$$

由于 $r_i$ 严格单调减，并且 $r_i\in \mathbb{N}$，所以必然存在一个 $n \in \mathbb{N^*}$ 满足 $r_{n-1} = a_nr_n$

那么我们有$$\frac{b_0}{r_0} = a_0+ \frac{r_1}{r_0} = a_0 + \frac{1}{\frac{r1}{r0}}$$

$$= a_0 + \frac{1}{a_1 + \frac{1}{\frac{r_2}{r_1}}}$$

$$=\cdots$$

$$=[a_0;a_1,a_2,\cdots,a_n]$$

例 1： $\frac{5}{3}$的连分数形式：

$5 = 1 \cdot 3 + 2 \to \frac{5}{3} = 1 + \frac{2}{3} = 1 + \frac{1}{\frac{3}{2}}$

$3 = 1 \cdot 2 + 1 \to \frac{3}{2} = 1 + \frac{1}{2}$

所以 $\frac{5}{3} = 1+\frac{1}{1+\frac{1}{2}} = [1;1,2]$

$\frac{1234}{32}$ 的连分数形式

$1234 = 38 \cdot 32 + 18 \to \frac{1234}{32} = 38+\frac{1}{\frac{32}{18}}$

$32 = 1 \cdot 18 + 14 \to \frac{32}{18} = 1 + \frac{1}{\frac{18}{14}}$

$18 = 1 \cdot 14 + 4 \to \frac{18}{14} = 1 + \frac{1}{\frac{14}{4}}$

$14 = 3 \cdot 4 + 2 \to \frac{14}{4} = 3 + \frac{1}{2}$

所以 $\frac{1234}{32} = 38+\frac{1}{1+\frac{1}{1+\frac{1}{3+\frac{1}{2}}}} = [38;1,1,3,2]$

整个过程我们可以用 python 语言来表示：

123456789

def continued_fraction(dn,n):res = []while dn % n:res.append(dn//n)dn, n = n, dn % nres.append(dn//n)print(res)print(continued_fraction(5,3))

可以看到和求 $gcd$ 的整个过程是比较类似的，所以求一个数的连分数形式也是多项式时间复杂度（说白点就是非常的快）。

定义二：收敛分数

设有理数 $\alpha = [a_0;a_1,a_2,\cdots,a_n]$，其收敛分数为 $[a_0],[a_0;a_1],\cdots[a_0;a_1,a_2,\cdots,a_n]$

说白点就是把连分数某一项后面的全扔掉，得到一个 $\alpha$ 的近似值。有 定理 1 我们可以知道收连分数是有限的，并且越后面（就是项数越多）就越逼近 $\alpha$。

例 3： 计算 $\frac{1234}{32}$ 的收敛分数

由上面的例题我们已经知道 $\frac{1234}{32}$ 的连分数形式为 $[38;1,1,3,2]$

所以其收敛分数分别为

$[38] \to 38$

$[38;1] \to 38+\frac{1}{1} = 39$

$[38;1,1] \to 38+\frac{1}{1+\frac{1}{1}} = 38.5$

$[38;1,1,3] \to 38+\frac{1}{1+\frac{1}{1+\frac{1}{3}}} = \frac{270}{7} \approx38.571$

$[38;1,1,3,2] \to 38+\frac{1}{1+\frac{1}{1+\frac{1}{3+\frac{1}{2}}}} = \frac{1234}{32}=38.5625$

整个过程我们可以用 python 语言来表示：

123456789101112

def Convergence_function(continued):res =[]for i in range(1,len(continued)+1):tmp = 1conver = continued[:i][::-1]tmp = conver[0]for j in conver[1:]:tmp = j + 1/tmpres.append(tmp)return resprint(Convergence_function(continued_fraction(1234,32)))

明白了这两个定义后，我们再给出一个定理2，也就是著名的Legendre’s theorem：

定理 2 （Legendre’s theorem）

若 $|\alpha - \frac{p}{q}| \lt \frac{1}{2q^2}$，并且 $(p,q)=1$，则 $\frac{p}{q}$ 会在 $\alpha$ 的收敛分数上。

证明：具体证明读者可以去到我上面给的那个知乎文章，证明涉及的一些引理和定理师傅写得都很详细，这里就不再赘述了。

应用场景

接下来我们主要聊一聊连分数的一些应用场景，对于做密码学的 CTFer，wiener 攻击应该是比较耳熟能详的，主要用到的是 Legendre’s theorem，适用于私钥 $d$ 相对 $n$ 较小时

wiener‘s attack

由于$ed=1 \pmod {φ(N)}$，那么存在一个$k$满足$ed−kφ(N)=1$。所以，

$\vert \frac{e}{\varphi(N)}-\frac kd \vert= \frac 1 {d\varphi(N)}$，如果 $\frac{1}{d\varphi(N)}$ 足够小，则 $\frac kd $ 是 $\frac e {\varphi(N)}$的逼近，尽管我们不知道 $\varphi(N)$，但是我们可以用$N$来近似。

因为$\varphi(N)=(p−1)(q−1)=pq−p−q+1=N−p−q+1$，又$p+q−1<3\sqrt N $所以我们有$|N−φ(N)|<3\sqrt N$

使用$N$替换$φ(N)$，我们得到：

$\vert \frac e N - \frac k d\vert = \vert \frac{ed - kN}{Nd}\vert = \vert \frac{ed - k\varphi(N)-kN+k\varphi(N)}{Nd}\vert=\vert \frac {1-k(N-\varphi(N))}{Nd}\vert ≤ \vert \frac{3k\sqrt{N}}{Nd}\vert =\frac{3k}{d\sqrt N}$

因为 $k\varphi(N)=ed−1<ed$，并且 $e<\varphi(N)$，所以有 $d \gt k$

因此如果私钥较短，满足 $d \lt \frac{1}{3}N^{\frac{1}{4}}$，我们就有 $k<d<\frac13N^{\frac14}$，也就能得到$3k<3d<N^{\frac 14} \to dN^{\frac 14}>3d^2$）。

于是我们有：$\vert \frac e N - \frac k d\vert ≤ \frac{3k}{d\sqrt N}<\frac {N^{\frac1 4}}{d\sqrt N}≤\frac 1 {dN^{\frac 14}}< \frac 1{3d^2} \lt \frac{1}{2d^2}$

这里就用到我们的 Legendre’s theorem 了，分数$\frac k d$ 会在 $\frac e N$ 的收敛分数上。因此我们要做的便是计算$\frac e N$的收敛分数，因为$ed−kφ(N)=1$，所以我们有$gcd(k,d)=1$，那么其中一个收敛分数就等于 $\frac k d$。

pell equation

佩尔方程即丢番图方程 $x^2 - Dy^2 = 1$，其中 $D \in \mathbb{N^}$。可以证明其有无数组整数解，并且解集可以由一个特解迭代生成。一般情况下我们可能通过暴力搜索的方式去寻找一个特解，但其实我们也可以将连分数应用进去。主要也是用到了我们前面讲的 *Legendre’s theorem**，

引理： $\exist$ 无穷多组 $(p,q)$，满足 $|\frac{p}{q}-\sqrt d| \lt \frac{1}{q^2}$。

证明：详细证明可以查看知乎文章 佩尔（Pell）方程及其应用

注意到这里的求二次根 $\sqrt d$ 的连分数，即无理数的连分数。那么就不能用到我们上面的脚本了。查询了一下无理数的连分数如何求解，知乎文章无理数的连分数表示方法给出了求 $\sqrt 2 ,\sqrt 3$ 的样例，CSDN文章无理数sqrt(n)连分数 给出了 C 语言的demo。笔者才疏学浅，尚不能将两者结合理解。但是差生文具多，笔者直接使用sagemath自带的连分数对其进行处理。

于是最终我们得到使用连分数求解佩尔方程的sagemath脚本

123456789101112

def solve_pell_all(N , numTry = 1000):    '''    find the special solves of pell eqution using continued_fraction    '''    sols = []    cf = continued_fraction(sqrt(N))    for i in range (numTry):        denom = cf.denominator(i)        numer = cf.numerator(i)        if numer^2 - N * denom^2 == 1:            sols.append((ZZ(numer) , ZZ(denom)))    return sols

由于 $\sqrt d$ 是无理数，因此其有循环连分数；numTry 是寻找其收敛分数的个数，默认1000个；最后返回 numTry 个收敛分数内满足佩尔方程的解集。也可以仅返回一个特解，然后利用这一特解生成任意多个解。

特意构造的CTF题目

羊城杯 Crypto RRRRRRRSA

12345678910111213141516171819202122232425262728293031323334353637

import hashlibimport sympyfrom Crypto.Util.number import *flag = 'GWHT{************}'flag1 = flag[:19].encode()flag2 = flag[19:].encode()assert(len(flag) == 38)P1 = getPrime(1038)P2 = sympy.nextprime(P1)assert(P2 - P1 < 1000)Q1 = getPrime(512)Q2 = sympy.nextprime(Q1)N1 = P1 * P1 * Q1N2 = P2 * P2 * Q2E1 = getPrime(1024)E2 = sympy.nextprime(E1)m1 = bytes_to_long(flag1)m2 = bytes_to_long(flag2)c1 = pow(m1, E1, N1)c2 = pow(m2, E2, N2)output = open('secret', 'w')output.write('N1=' + str(N1) + '\n')output.write('c1=' + str(c1) + '\n')output.write('E1=' + str(E1) + '\n')output.write('N2=' + str(N2) + '\n')output.write('c2=' + str(c2) + '\n')output.write('E2=' + str(E2) + '\n')output.close()

注意到这里 $N1 = P1 * P1 * Q1,N2 = P2 * P2 * Q2$，于是 $\frac{N1}{N2}=\frac{P1P1*Q1}{(P2)(P2)(Q2)}=\frac{P1^2*Q1}{(P2)^2(Q2)}$，其中 $P2-P1 < 1000$，所以我们考虑$\frac{Q1}{Q2}$ 是否会在 $\frac{N1}{N2}$ 的连分数展开的收敛分数上。即考虑是否有 $|\frac{N1}{N2}-\frac{Q1}{Q2}| \lt \frac{1}{2Q2^2}$

$|\frac{N1}{N2}-\frac{Q1}{Q2}| = |\frac{P1P1Q1}{P2P2Q2}-\frac{P2P2Q1}{P2P2Q2}|=|\frac{(P1^2-P2^2)Q1}{P2P2Q2}|=\frac{1}{2Q2^2}\frac{2Q1Q2(P1^2-P2^2)}{P2^2}$

即考虑是否有 $\frac{2Q1Q2(P1^2-P2^2)}{P2^2} \lt 1$

注意到由于 $P2-P1<1000$，$(P1^2-P2^2)=(P1+P2)(P1-P2)$，考虑比特长度大约只有1039比特，$2Q1Q2$ 也就是 1025比特，但是 $P2^2$ 会有 2076 比特，所以 $\frac{2Q1Q2(P1^2-P2^2)}{P2^2} \lt 1$ 成立，即 $\frac{Q1}{Q2}$ 会在 $\frac{N1}{N2}$ 的连分数展开的收敛分数上。

求出 $Q1,Q2$ 后就意味着我们能够分解 $N1,N2$，那么此题也就宣告解答完成了。

总结

这篇文章我们简单聊了聊什么是连分数，什么是收连分数，以及连分的应用，比如wiener’s attack，pell equation，还有平时可能会碰到的 CTF 中密码学的题目。连分数这块的东西还有很多，也有一定的深度，直至今天，它仍是一个值得研究的课题。尤其是在构造方面，很多东西并不是那么的自然，如论文《Generalization of Some Attacks on RSA with Small Prime Combination and Small Private Exponent》中构造的， $\left |\frac{e}{N-\sqrt{\frac{i}{j}N}-\sqrt{\frac{j}{i}N}+1} - \frac{k}{d} \right | \lt \frac{1}{3} N^{-2\delta} + \frac{1}{6N^{2\delta}} = \frac{1}{2d^2}$，不是很能理解作者是怎么会想到构造出这样的分数。同时也不得不感叹自己的道行还是太浅，仅仅理解这些公式及其证明都要花费大量的精力。记录这篇文章也算是对自己习得知识的一种整理，同时也希望这篇文章能够给读者或多或少带来一点东西或启发，与君共勉叭~

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 [email protected] - source:Van1sh的小屋