密码学学习笔记之连分数

Van1sh 密码小屋 continued_fraction
创建时间:
字数:2.5k 阅读:
  1. 前置知识
    1. 定义一：连分数
    2. 定义二：收敛分数
  2. 应用场景
    1. wiener‘s attack
    2. pell equation
  3. 特意构造的CTF题目
    1. 羊城杯 Crypto RRRRRRRSA
  4. 总结

之前对论文《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 语言来表示：

1
2
3
4
5
6
7
8
9
def continued_fraction(dn,n):
	res = []
	while dn % n:
		res.append(dn//n)
		dn, n = n, dn % n
	res.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 语言来表示：

1
2
3
4
5
6
7
8
9
10
11
12
def Convergence_function(continued):
	res =[]
	for i in range(1,len(continued)+1):
		tmp = 1
		conver = continued[:i][::-1]
		tmp = conver[0]
		for j in conver[1:]:
			tmp = j + 1/tmp
		res.append(tmp)
	return res

print(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脚本

1
2
3
4
5
6
7
8
9
10
11
12
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import hashlib
import sympy
from 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 * Q1
N2 = P2 * P2 * Q2

E1 = 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，也可以邮件至 643713081@qq.com

赏

文章标题:密码学学习笔记之连分数

文章字数:2.5k

本文作者:Van1sh

发布时间:2022-11-15, 17:59:00

最后更新:2023-03-07, 18:34:43

原始链接:http://jayxv.github.io/2022/11/15/密码学学习笔记之连分数/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

©2020 Van1sh

Built with Hexo and 3-hexo theme

目录
×

喜欢就点赞,疼爱就打赏