欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-14 08:10:03
...
  • 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:
第一届祥云杯密码学(一)

相关标签: 祥云杯 密码学