连分数与其在rsa中的运用

首先先要了解一下连分数的表现形式

也就是把一个数不停细分下去例如x=13/8

可以继续划分为如图所表示的形式

这就是简单连分数，为了方便计算，通常我们会写成[a0,a1,a2,a3]，上图我举的例子可以写成[1,1,1,1,2]

我也简单写了个模拟代码，大部分情况应该是适用的（原创代码，可能写的比较差）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def lianfenshu(a,b):
    list=[]
    t=a//b
    list.append(int(t))
    h=1/(a/b-t)
    if h % 1 == 0:
        list.append(int(h))
    while h%1!=0:
        t=int(h-h%1)
        list.append(int(t))
        h=round(1/(h%1),4)
        if h%1==0 :
            list.append(int(h))
    return list

简单连分数的概念也要知道，分为有限连分数和无线连分数，也代表着有理数和无理数吧

当然连分数[a0,a1,a2,a3,.......,an]也可以写为(a0*[a1,a2,a3,....,an]+1)/[a1,a2,a3,....,an]最后可以化简为a/b,

连分数的倒数:例如假如这个数为[a0,a1,a2,a3,.......,an]，他的倒数就是[0,a0,a1,a2,a3,.......,an]

然后再看渐近分数

渐近分数的定义是称[a0,a1,a2,a3,.......,am]是渐近数[a0,a1,a2,a3,.......,an]第m个渐近分数(0<=m<=n)

然后还存在一个特性

pnqn-1-pn-1 qn=(-1)^(n-1)

可以通过上述可以替换出来

然后又有一个概念完全商，是逆过来的举个例子

[2,3,1,4]

[4]第三个完全商

[1,4]第二个完全商

[3,1,4]第一个完全商

[2,3,1,4]第零个完全商

其定义为称[at,.....,an]为[a0,a1,a2,a3,.......,an]的第t个完全商（0<=t<=n）

渐近分数的单调性

第t个渐近分数xt=pt/qt

性质1：所有偶数编号的渐近分数是严格递增的，奇数编号是相反的

性质2：任何奇数编号的渐近分数大于偶数编号的渐近分数

大概基础就这么多

然后看看连分数在rsa中的应用

作用于RSA维纳攻击

Wiener 表示如果满足：

d < (1 /3) n ^(1/ 4) d以危害 RSA 的安全。此时需要满足：

q<p<2q

回想一下 RSA：

N = pq

φ(n)=(p−1)(q−1)=pq−(p+q)+1=N−(p+q)+1

p, q 非常大， pq≫p+q，φ(n)≈N

ed≡1 mod φ(n)，∴ed−1=kφ(n)，这个式子两边同除 dφ(n) 可得

可得到e/n-k/d=1/dφ(n)

同样 dφ(n) 是一个很大的数，所以 e /N 略大于 k/ d

因为 e 和 N 是我们是知道的，公钥中给我们的，所以我们计算出 e/ N 后，比它略小的 k/ d怎么出来呢，计算 e /N 的连分数展开，依次算出这个分数每一个渐进分数，由于 e/ N 略大于 k/ d ，wiener 证明了，该攻击能精确的覆盖 k /d .

我们也可以看一下羊城杯 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
38
39
40
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()


首先发现

1
2
3
4
5
6
7
N1 = P1 * P1 * Q1
N2 = P2 * P2 * Q2
P1 = getPrime(1038)
P2 = sympy.nextprime(P1)
assert(P2 - P1 < 1000)
Q1 = getPrime(512)
Q2 = sympy.nextprime(Q1)

p1与 p 2 是相邻的素数，且两者差值小于1000

q1 与 q2 也是相邻的素数

换而言之， p 1 / p 2 ≈ 1

很容易想到维纳攻击

N1/N2=(P1/P2)**2(Q1/Q2)

N1/N2<Q1/Q2

任何有理数都可以写为q/p=[a0;a1,a2,...,an]

计算连分数我们可以使用欧几里得算法

连分数的收敛性

我们定义 c i 为连分数每一次分式展开的收敛，也就是上文的渐近连分数

img

根据这个定理，我们可以通过计算一个数（e/N）的连分数来找到与这个数近似的两个数的比值(k/d)，这就是Wiener’s attack的攻击方法。

img

此题考查这个论文

因为p1和p2过于接近，相比而言取q1/q2更合适

而选择 N 1/ N 2 ≈ Q 1 /Q 2 可以进行维纳攻击的前提条件是：

∣N2/N1−Q2/Q1∣<1/2∗(Q2)**2

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import gmpy2
N1, N2 = (
    28539239760609998188190348006307254423529984523926011298354682217538318221201323233400895681944936240127760319591714405028970789289069319799896668405374649890651532747231344681669678805558659075027847592497103008180667401328194026698749233856463858487096300279373254961880228864461848969277992345170787143090948199697266462389362914238819698112687026213976658417210663710975098053456243238943838516217798558036642447022751111845270483110159293737669560262193958772015914816987850140197853369767380678566336063010710812528919482513791382363881826680659095433918156094107350594201368395060384315773118343026193511099009931177740948978534045707679969732723167077325752299598557383348276880809860413060977442176372544771414690543709674125255716088409107695219200275948083389811120343,
    28539239760609998188190348006307254423529984523926011298354682217538318221201323233400895681944936240127760319591714405028970789289069319799896668405377378062335966544017315329665365256524558696688888741558627244653037221467229159144343040629127843297021870442297090214085287305843208151069804261723045390513830069085816369993597001968164660390663983571269250460727348123970070188870297493687465127551913118724304293942732950040939150438510454614095673775735977217966562306548665616925803946575019193754095625773160561193234183507671760318885800972555685452762447998320093072265818485061557955267533908006243431570323359331106169234651310488306412479972526063665874847216797986275140105142694301359006633212114432527436809944525332728559649659936613255629968696993687582732203577)
c1, c2 = (
    1432582014696304280729383293185554513436929310033823269133977593539672022744978340029313742941392672688363895524640351487464959860278576282854691764963077939567531721178912737755379413034164798305484717033762726637503348022397339246940965129765378824268519081645805470821347112369377592502109678876165836108257610182421452838639591697308432137885174692492190957254254995673010537260331832973067691597718100899475899017281060822990010249568584370589711942182283002241043038119931455622397903939297537776804134742442672001638774739818585840571993745726530468147630711418520486306194651956014117679528472239294239116641656014852458465706006398065574504399016286485027421474307531748266141136418468990741046806688381193860509615850629805172129297224123462801586090084637746562423808,
    15573518512630583133605706431375892476846434992703760807266881477212729790675502562405142453118932977842339803883111403869334521098950030048699583130857582338419182841819307757252097704148569218757559761264396801310961344678392000382263595912787825617009851110457692404940207973548999796553024456145274114257889573707649959860997335143214788897776951837248853483762434899857463503651914305981628033038172123120703537802061315610043298426738218704990852775023413248589434394708618489802771255075164976384643287270994751622452142844176084933641827641239534332334446368745588970480750957569438747829980771324981588625047320914720986351721280038816715323656526802000900688313558979941992015923305782197562859553039256619824373010017972420560224632828808074734952385591551175446599133)
e1= 165789626975534012040420057284463500775834911397214992496515507176272849770841998477139944440126985014248815418211585858658342524799286016374109756516450870298232454995876047057825952563581619963387275065218691863272435560584657400761485940130783607258311246708485662913432455714363728035174035069036312370233
e2=165789626975534012040420057284463500775834911397214992496515507176272849770841998477139944440126985014248815418211585858658342524799286016374109756516450870298232454995876047057825952563581619963387275065218691863272435560584657400761485940130783607258311246708485662913432455714363728035174035069036312370859

def continuedFra(x, y): #不断生成连分数的项,如127/52 = 2 + 1/2+ 1/3+ 1/1+ 1/5，生成[2,2,3,1,5]
    cF = []
    while y:
        cF += [x // y]
        x, y = y, x % y		#这里是连分数生成项的算法
    return cF

def Simplify(ctnf): 			#对前面生成的连分数项化简
    numerator = 1
    denominator = 0
    for x in ctnf[::-1]: 		#注意这里是倒叙遍历，从后面把连分数项合成总和。
        numerator, denominator = x * numerator + denominator, numerator
    return (numerator, denominator) 		#把连分数分成和算出来的分母以元组的形式导出来，如Simplify(continuedFra(127,52))生成(127, 52)

def getit(c):
    cf=[]
    for i in range(1,len(c)):
        cf.append(Simplify(c[:i])) 	#各个阶段的连分数的分子和分母
    return cf 							#得到一串连分数，如：[(2, 1), (5, 2), (17, 7), (22, 9)]

def wienerAttack(e, n):				#低解密指数攻击，自己修改要碰撞的分子或分母
    cf=continuedFra(e,n)
    for (q1,q2) in getit(cf):			#遍历得到的连分数，令分子分母分别是Q1，Q2，因为前面我们说了N1/N2=(p1/p2)**2 (q1/q2)
        if q1 == 0:
            continue
        if N1%q1==0 and q1!=1:		#满足这个条件就找到了Q1，其实同理也可以找出Q2
            return (q1,q2)
    print('没找到能覆盖的分子/分母')

q1,q2=wienerAttack(N1,N2)				#找出一个Q1,其实这里也可以找出Q2的，但处于p2=sympy.nextprime(p1)的限制，只能用p1求出p2，不能用p2求出p1

from Crypto.Util.number import *
p1=gmpy2.iroot(N1//q1,2)[0]
p2=gmpy2.iroot(N2//q2,2)[0]

phi1=((p1-1)*p1*p1*p1)*(q1-1)
phi2=((p2-1)*p2*p2*p2)*(q2-1)

d1=gmpy2.invert(e1,phi1)				#逆模求d
d2=gmpy2.invert(e2,phi2)				#逆模求d
m1=long_to_bytes(gmpy2.powmod(c1,d1,N1))		#普通解密算法，但是要用将long型数转为字节型数据
m2=long_to_bytes(gmpy2.powmod(c2,d2,N2))		#普通解密算法，但是要用将long型数转为字节型数据
print((m1+m2))