用户
搜索
  • TA的每日心情
    开心
    2016-10-30 16:15
  • 签到天数: 4 天

    连续签到: 1 天

    [LV.2]偶尔看看

    i春秋-见习白帽

    Rank: 3Rank: 3

    23

    主题

    38

    帖子

    254

    魔法币
    收听
    0
    粉丝
    2
    注册时间
    2016-6-6
    发表于 2017-9-19 16:08:07 4102107
    本帖最后由 yanzm 于 2017-9-19 16:10 编辑


    00.png

    RSA是一种非对称加密算法,它由 公钥(n/e),私钥(n/d),明文M和密文C组成。我们做CTF题目时,一般题目中会给出公钥和密文让我们推出对应的私钥或者明文。RSA的相关公式都写在上面脑图中,在正式讲解RSA加密算法前我们先来普及一波数学的基本知识。

    一、相关数学基础

    1.1素数和互质数

    素数也称质数,它的定义为除本身和 1 的乘积外,不能表示其他数的乘积。比如2,3,5,7,11,13,17……等都是素数。
    互素数也称互质数,定义是公约数只有1的两个自然数,如:
    1和任何自然数 1 & 2
    任意 2个质数 2 & 3
    相邻2个自然数 4 & 5
    3 & 10 、7 & 10 、5 & 26等等

    1.2模指数运算

    模运算就是取余数,如5 mod 3 =2。而模指数就是,先做指数运算在做mod运算。
    如:53 mod 7 = 125 mod 7 =6
    我们可以使用python的pow()来求解模指数运算。

    1.2.png

    1.3同余运算

    两个整数a,b,它们除以整数M所得的余数相等:a ≡ b(mod m),比如说5除3余数为2,11除3余数也为2,于是可写成11 ≡ 5(mod 3)。

    二、RSA加密算法

    2.1 加解密算法

    前面已经说过,RSA是一种非对称加密算法,这个算法的特点就是明文使用公钥进行加密得到密文,而密文解密使用私钥来解。

    2.1.png

    所需的密钥对为n,d,e。密钥对是如何生成的?

    2.2生成密钥对

    密钥对的生成步骤如下:n  Led (L作为生成过程中的中间数)

    2.2.png

    三、CTF题目实战

    3.1 First Blood 已知p、q、e求d

    题目链接 : http://www.shiyanbar.com/ctf/1828
    题目:
    在一次RSA密钥对生成中,假设p=473398607161,q=4511491,e=17,求解出d

    此题直接告诉我们p、q、e,让我们求解d
    而d的计算公式为d*e ≡ 1 (mod L*i)  ,i=1,2,3...,
    由于1和任何数做mod都为1,所有该公式又可转换为:
    d*e mod (L*i )=1 , i=1,2,3...。
    d*e除(L*i)的余数为1,即d*e = (L*I) + 1 。
    直接使用脚本进行实现。
    p = int(raw_input("Entera p: "))   
    q = int(raw_input("Entera q: "))  
    e = int(raw_input("Entera e: "))   
    t = (p-1)*(q-1)  
    i=0  
    while True :   
       if (1-t*i)%e == 0:   
          break   
       
    i-=1  
       print i
    print 'ok:' + '%d' % ((1-t*i)/e)

    求d的脚本,也可以又rsatool.py这个脚本来实现,需要安装gmpy这个模块,链接如下
    链接:http://pan.baidu.com/s/1bCDyoQ 密码:09gj

    3.2 Double Kill  已知p、q、e和密文 求明文

    题目链接 : http://www.shiyanbar.com/ctf/1979
    题目:
    Use RSA to find the secret message
    直接跑上题脚本获取d:
    3.2 1.png
    3.2 2.png

    3.2 3.png


    5577446633554466577768879988

    3.3 Triple Kill  已知n、e和密文 求明文

    题目链接 : http://www.shiyanbar.com/ctf/1918

    3.3.png

    n=920139713,e=19
    因式分解 n 用yafu 或者在线因式分解
    使用yafu:链接:http://pan.baidu.com/s/1croXpO 密码:w43p

    n.png



    在线地址:
    http://www.atool.org/quality_factor.php

    dizhi.png

    p=18443,q=49891
    求d:

    d.png

    d=96849619
    解密:

    jiemi 1.png

    jiemi 2.png


    flag{13212je2ue28fy71w8u87y31r78eu1e2}

    3.4 Quadra Kill  已知公钥和密文 求明文
    题目链接 : http://www.shiyanbar.com/ctf/1772  
    题目:
    3.4 1.png



    此题只给了公钥,并没有做分解,我们可以对题目所给的公钥进行分解。
    python实现:
    p= int(raw_input("Entera p: "))   
    q = int(raw_input("Entera q: "))  
    e = int(raw_input("Entera e: "))   
    t = (p-1)*(q-1)  
    i=0  
    while True :   
       if (1-t*i)%e == 0:   
          break   
       
    i-=1  
       print i
    print 'ok:' + '%d' % ((1-t*i)/e)

    PY.png




    或则使用openssl:
    open.png

    使用yafu分解n 的值:

    yafu.png



    rsa-d.py计算d 的值:

    RSA 1.png

    rsa 2.png



    明文 = 密文d mod n

    明文.png


    3.5 Penta Kill  已知公钥和密文 求明文

    题目链接 : http://www.shiyanbar.com/ctf/730
    题目:

    3.5 1.png

    3.5 2.png



    分解公钥得n、e的值,然后求解d,这边提供另外一种求解d的方案,就是利用github上的一个开源项目
    github: https://github.com/pablocelayes/rsa-wiener-attack

    开源.png
    33.png




    python脚本下载:链接:http://pan.baidu.com/s/1qXVhKpI 密码:fuef


    三、总结


    限于篇幅,本篇先到这里告一个断落,下期会带来一些有一定难度RSA题目的解法,敬请期待,让斗哥带你走上RSA超神之路吧!

    640.webp.jpg



    感谢楼主,受益匪浅。
    使用道具 举报 回复
    感谢楼主,受益匪浅。
    使用道具 举报 回复
    666
    使用道具 举报 回复
    用openssl分解出来的那个Moduals是怎么转成十进制数字的啊,大佬请指点
    使用道具 举报 回复
    发新帖
    您需要登录后才可以回帖 登录 | 立即注册