|
|
楼主 |
发表于 2021-11-9 23:41:42
|
显示全部楼层
本帖最后由 pukr 于 2021-11-19 09:57 编辑
rsa2 低解密指数（wiener 攻击）这类攻击的特征是e很大，接近于N，导致d较小。
两篇文章可供阅读，攻击脚本下载地址：[rsa-wiener-attack](https://github.com/pablocelayes/rsa-wiener-attack)
攻击原理
知识储备
 
- # -*- coding: utf-8 -*-
- import hashlib
- d = 8920758995414587152829426558580025657357328745839747693739591820283538307445
- flag = "flag{" + hashlib.md5(hex(d)).hexdigest() + "}"
- print(flag)
得到d的过程：
github上下载的脚本，修改一下d那里，其他的直接运行。
- '''
- Created on Dec 14, 2011
- @author: pablocelayes
- '''
- import ContinuedFractions, Arithmetic, RSAvulnerableKeyGenerator
- def hack_RSA(e,n):
- '''
- Finds d knowing (e,n)
- applying the Wiener continued fraction attack
- '''
- frac = ContinuedFractions.rational_to_contfrac(e, n)
- convergents = ContinuedFractions.convergents_from_contfrac(frac)
-
- for (k, d) in convergents:
-
- #check if d is actually the key
- if k != 0 and (e*d-1) % k == 0:
- phi = (e*d-1)//k
- s = n - phi + 1
- # check if the equation x^2 - s*x + n = 0
- # has integer roots
- discr = s*s - 4*n
- if discr >= 0:
- t = Arithmetic.is_perfect_square(discr)
- if t != -1 and (s+t) % 2 == 0:
- print("Hacked!")
- return d
- # TEST functions
- def test_hack_RSA():
- print("Testing Wiener Attack")
- times = 5
-
- while times>0:
- # e,n,d = RSAvulnerableKeyGenerator.generateKeys(1024)
- n = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471
- e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085
- print("(e,n) is (", e, ", ", n, ")")
- # print("d = ", d)
-
- hacked_d = hack_RSA(e, n)
-
- # if d == hacked_d:
- # print("Hack WORKED!")
- # else:
- # print("Hack FAILED")
-
- # print("d = ", d, ", hacked_d = ", hacked_d)
- print("hacked_d = ", hacked_d)
- print("-------------------------")
- times -= 1
- if __name__ == "__main__":
- # test_is_perfect_square()
- # print("-------------------------")
- test_hack_RSA()
代码分析：
分析一下github上求d的代码，其实过程就是上面写的那样，学习一下大佬怎么写的代码。
运算核心应该是这个文件：ContinuedFractions.py
第一个函数用于将实数变成连分数的数组表示形式。
- def rational_to_contfrac(x,y):
- '''
- Converts a rational x/y fraction into
- a list of partial quotients [a0, ..., an]
- '''
- a = x//y
- pquotients = [a]
- while a * y != x:
- x,y = y,x-a*y
- a = x//y
- pquotients.append(a)
- return pquotients
第二个函数，用于分割原实数的连分数数组，因为求渐进分数的时候是一个个p、q逐渐求的。
- def convergents_from_contfrac(frac):
- '''
- computes the list of convergents
- using the list of partial quotients
- '''
- convs = [];
- for i in range(len(frac)):
- convs.append(contfrac_to_rational(frac[0:i]))
- return convs
第三个函数，用于求出所给数组的渐进分数。
- def contfrac_to_rational (frac):
- '''Converts a finite continued fraction [a0, ..., an]
- to an x/y rational.
- '''
- if len(frac) == 0:
- return (0,1)
- num = frac[-1]
- denom = 1
- for _ in range(-2,-len(frac)-1,-1):
- num, denom = frac[_]*num+denom, num
- return (num,denom)
这样，convs数组就是保存连分数的渐近分数的数组，遍历frac逐渐求出渐进分数。
|
|
