第一届祥云杯密码学(一)

• SimpleRSA
  题目：

from Crypto.Util.number import *
import gmpy2

p, q, r = [getPrime(512) for i in range(3)]
n = p * q * r
phi = (p - 1) * (q - 1) * (r - 1)
d = getPrime(256)
e = gmpy2.invert(d , phi)

flag = b"flag{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}"

c = pow(bytes_to_long(flag), e, n)

print(e, n)
print(c)
#e = 1072295425944136507039938677101442481213519408125148233880442849206353379681989305000570387093152236263203395726974692959819315410781180094216209100069530791407495510882640781920564732214327898099944792714253622047873152630438060151644601786843683746256407925709702163565141004356238879406385566586704226148537863811717298966607314747737551724379516675376634771455883976069007134218982435170160647848549412289128982070647832774446345062489374092673169618836701679
#n = 1827221992692849179244069834273816565714276505305246103435962887461520381709739927223055239953965182451252194768935702628056587034173800605827424043281673183606478736189927377745575379908876456485016832416806029254972769617393560238494326078940842295153029285394491783712384990125100774596477064482280829407856014835231711788990066676534414414741067759564102331614666713797073811245099512130528600464099492734671689084990036077860042238454908960841595107122933173
#c = 1079929174110820494059355415059104229905268763089157771374657932646711017488701536460687319648362549563313125268069722412148023885626962640915852317297916421725818077814237292807218952574111141918158391190621362508862842932945783059181952614317289116405878741758913351697905289993651105968169193211242144991434715552952340791545323270065763529865010326192824334684413212357708275259096202509042838081150055727650443887438253964607414944245877904002580997866300452

既然我们已经知道了n的值很自然的就想到了进行素数分解，但是这道题显然并不是我们想象的这么简单,解题原理参考了lazzzaro师傅的博客，写的非常的详细

低解密指数攻击/低私钥指数攻击（e长度较大，d小，Wiener Attack）

适用情况：已知 N,e，且 e 过大或过小，此时的d要么非常小，要么非常大

基础知识：

1. 连分数

连分数：形如下图这样的式子就是连分数的展开式

在这里附上一道例题，下图即为一个连分式的展开式：

2. 渐进分数

渐进分数是指一个以分数的形式出现的两个有理数的商的近似值
如我们熟知的密率355/113和约率22/7就是3.1415926/1的渐进分数
例：1/2，3/4，7/8，15/16，…，1
1/2，3/4，7/8，15/16，都可称是1的渐近分数
具体为：渐进分数示例

我们的目的就是结合连分数和渐进分数的运算，来计算无限接近于e/n的k/d,最终**出答案。

附上解题脚本：

#python3环境
from Cryptodome.Util.number import long_to_bytes
e = 1072295425944136507039938677101442481213519408125148233880442849206353379681989305000570387093152236263203395726974692959819315410781180094216209100069530791407495510882640781920564732214327898099944792714253622047873152630438060151644601786843683746256407925709702163565141004356238879406385566586704226148537863811717298966607314747737551724379516675376634771455883976069007134218982435170160647848549412289128982070647832774446345062489374092673169618836701679
n = 1827221992692849179244069834273816565714276505305246103435962887461520381709739927223055239953965182451252194768935702628056587034173800605827424043281673183606478736189927377745575379908876456485016832416806029254972769617393560238494326078940842295153029285394491783712384990125100774596477064482280829407856014835231711788990066676534414414741067759564102331614666713797073811245099512130528600464099492734671689084990036077860042238454908960841595107122933173
c = 1079929174110820494059355415059104229905268763089157771374657932646711017488701536460687319648362549563313125268069722412148023885626962640915852317297916421725818077814237292807218952574111141918158391190621362508862842932945783059181952614317289116405878741758913351697905289993651105968169193211242144991434715552952340791545323270065763529865010326192824334684413212357708275259096202509042838081150055727650443887438253964607414944245877904002580997866300452
#连分数展开算法
def lf(x,y):
	arr=[]
	while y:
		arr+=[x//y]
		x,y=y,x%y
	return arr
#渐进分数算法
def jj(k):
	x=0
	y=1
	for i in k[::-1]:
		x,y=y,x+i*y
	return (y,x)
data=lf(e,n)
for x in range(1,len(data)+1):
	data1=data[:x]
	d = jj(data1)[1]
	m = pow(c,d,n)
	flag = long_to_bytes(m)
	if b'flag{' in flag:
		print(flag)
		break

得到flag：