欢迎来到 黑吧安全网 聚焦网络安全前沿资讯,精华内容,交流技术心得!

HITB 2015加密类300分题详细解析

来源:本站整理 作者:佚名 时间:2018-07-22 TAG: 我要投稿

介绍
加密类300分这道题是有关于RSA生成的质数p和q。题目提供了3个文件,其中mail.msg是RSA加密过的邮件,hitbctf.crt是含有公钥的证书文件, gen_rsa.py是产生RSA参数的源码。这题网上有一篇老外的writeup,但其中省略了一些步骤,导致我等小白看起来非常费劲。而且老外的代码选择性省略,跑不出最终结果。freebuf上有一篇翻译的文章,跟老外的内容完全一样。本人小白,经过网上各种翻查,终于弄清楚了这题的完整原理。基本思路都是参考老外的文章,在此向原作者致敬!
参考
1.http://www.romainthomas.fr/post/writeup-hitb2015-crypto300/
题目的文件在老外的文章中链接,可以自行下载。
原理
RSA的原理网上的文章很多,请自行搜索。
文件及函数分析
mail.msg是RSA加密过的邮件,是最终要解密的文件。
hitbctf.crt是含有公钥的证书文件,从中可以获取RSA的参数e、N。
gen_rsa.py是产生RSA参数的源码,从源码中能推导出解题的关键。
gen_rsa.py中有几个函数,功能如下:
rabin_miller(num)
Miller-Rabin素性测试算法判断num是否素数,原理网上很多文章。
is_prime(num)
判断num是否素数。如果是1000以内素数或倍数,则直接返回false。
egcd(a,b)
扩展欧几里得算法求最大公约数。函数返回a和b的最大公约数g和两个数字x、y,其中x和y可以实现g = ax+ by。
modinv(a,m)
从函数名称就能判断是求模反元素的,即乘法逆元,在RSA中就是通过e、N求d。
next_prime(n)
求大于等于n的第一个素数。
gen_rsa_parameters()
首先获取2个随机数,通过next_prime算出2个素数作为e、p。然后求出(p-1)模e的乘法逆元alpha,算出(p *alpha % e)判处是否素数,如果不是则加e。通过得到的p、q最终求出d。
攻击假想
根据源程序gen_rsa.py中,假设(p-1)模e的乘法逆元为α,可得2个已知条件:
α *(p − 1) ≡ 1 (mod e)
q = (pα mod e) + k*e
假设N’=N mod e,带入上面的已知条件可得:
N’ ≡ p* q  (mod e)
    ≡ p * ((pα mod e) + k *e) (mod e)
    ≡ p * (pα mod e) (mod e)
    ≡ p * (pα – j * e) (mod e)
    ≡ p2α (mod e) 由于已知条件中有α⋅(p−1) ≡ 1 (mod e),所以引入p-1分析:
           N’ ≡ (p – 1 + 1)2α (mod e)                ≡ (p – 1)2α + 2(p – 1)α + α (mod e)
               ≡ (p – 1) + 2 + α (mod e)
(p – 1) N’ ≡ (p – 1)2 + 2(p – 1) + 1 (mod e)
(p – 1)2 – (N’ – 2) (p -1) + 1 ≡ 0 (mod e)
令 X = p – 1并假设N’ – 2为偶数,所以有N’- 2 = 2b,上面的二次方程可写成:
      X2- 2bX + 1 ≡ 0 (mod e)
 (X- b)2 – b2 + 1 ≡ 0  (mod e)
             (X – b)2 ≡ b2 – 1  (mod e)
上述方程从二次剩余(quadratic residue)能找到解决方案。

转换成SageMath的公式就是:
Np = N % e
b = (Np – 2)/ 2
pp =int(Mod(pow(b, 2) – 1, e).sqrt()) + b + 1
设pp = p % e ,求q:
q= (p * modinv(p – 1, e) % e)
  = (pp + ke)* modinv(p – 1, e) % e
  = (pp *modinv(p – 1, e)) % e
  = (pp *modinv(pp + ke – 1, e)) % e
  = (pp *modinv(pp – 1, e)) % e
算出pp后也可以直接通过pp + ke循环测试发现p。老外放弃了这一途径,原因是:I tried to find pp by adding some e but the distance betweenp and p mod e is huge。个人觉得很奇怪!
实际操作:
假设N’ – 2为偶数(N’ = N mod e),很明显本题符合要求。
第一步:从证书文件中获取RSA的参数e和N。方法很多,简单列出2种。
方法1:利用openssl可以直接显示
openssl x509 -in hitbctf.crt -text -noout

方法2:通过证书文件生成公钥文件,显示公钥文件的内容
openssl x509 -outform PEM -in hitbctf.crt -pubkey -noout >public.pem
openssl rsa -pubin -text -modulus -in public.pem

需要10进制数的可以利用python的int函数转换:

第二步:使用SageMath的数学计算功能,算出正确的pp(p % e)
e= 21558488234539889837938770635971330903489839146766895224490179041465516193145582266963154883831707522081140734421052039099233464837201660281606980530249

[1] [2]  下一页

【声明】:黑吧安全网(http://www.myhack58.com)登载此文出于传递更多信息之目的,并不代表本站赞同其观点和对其真实性负责,仅适于网络安全技术爱好者学习研究使用,学习中请遵循国家相关法律法规。如有问题请联系我们,联系邮箱admin@myhack58.com,我们会在最短的时间内进行处理。
  • 最新更新
    • 相关阅读
      • 本类热门
        • 最近下载