• 新闻动态
  • 行业动态
  • 公司新闻
  • 关于我们
  • 公司简介
  • 经典活动
  • 技术分享
    RSA之拒绝套路(1)
    2018-08-27 15:09

     

    前言

     

     


    近期在复习数论和密码学的题目,于是先从RSA开始,做一些题目推导与证明希望知其然,知其所以然,而不是一味的跟着套路走


    RSA大众套路


     

     

    这里简单的概述总结一下:

    e较大:Wiener攻击

    2.e较小:直接开方

    3.低加密指数广播攻击:相同低指数的e和多个相同的消息m

    4.Coppersmith定理攻击:只有部分高位的p或q

    5.共模攻击:相同n,相同m

    话不多说,下面从非套路的题目开始

    题干

     

     

    例如题目

    e = 65537

    n=248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113

    dp=905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657

     

    c=140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

    注意,其中dp的意思为:

    dp≡d mod (p−1)dp≡d mod (p−1)


    公式推导

     

     


    现在我们可以知道的是

    故此可以得到

    k2∗(p−1)∗(q−1)+1=k1∗(p−1)+dp∗ek2∗(p−1)∗(q−1)+1=k1∗(p−1)+dp∗e

    变换一下

    (p−1)∗[k2∗(q−1)−k1]+1=dp∗e(p−1)∗[k2∗(q−1)−k1]+1=dp∗e

    因为

    dp<p−1dp<p−1

    可以得到

    e>k2∗(q−1)−k1e>k2∗(q−1)−k1

    我们假设

    x=k2∗(q−1)−k1x=k2∗(q−1)−k1

    可以得到x的范围为

    (0,e)(0,e)

    因此有

    x∗(p−1)+1=dp∗ex∗(p−1)+1=dp∗e

    那么我们可以遍历

    x∈(0,e)x∈(0,e)

    求出p-1,求的方法也很简单,遍历65537种可能,其中肯定有一个p可以被n整除那么求出p和q,即可利用

    ϕ(n)=(p−1)∗(q−1)d∗e≡1 mod ϕ(n)ϕ(n)=(p−1)∗(q−1)d∗e≡1 mod ϕ(n)

    推出

    d≡1∗e−1 mod ϕ(n)d≡1∗e−1 mod ϕ(n)

    注:这里的-1为逆元,不是倒数的那个-1


    payload

     

     


    写下如下脚本:

    import gmpy2import libnume = 65537n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

    for i in range(1,65538):

        if (dp*e-1)%i == 0:

            if n%(((dp*e-1)/i)+1)==0:

                p=((dp*e-1)/i)+1

                q=n/(((dp*e-1)/i)+1)

                phi = (p-1)*(q-1)

                d = gmpy2.invert(e,phi)%phi

                print libnum.n2s(pow(c,d,n))

    即可得到flag

    flag{wow_leaking_dp_breaks_rsa?_98924743502}


    反思

     

     

    现在不难得出结论,RSA中,如果dp或者dq任意一个泄露都可以导致密文被破解因为上述的证明过程,没有用到任何特例情况。但是如果e较大的话,可能会比较困难一些,但是如果e过大,那就可以使用维纳攻击了XD



     

     



     


    上一篇:HDwiki二次注入案例分享
    下一篇:RSA之拒绝套路(2)
    版权所有 合天智汇信息技术有限公司 2013-2020 湘ICP备14001562号-6
    Copyright © 2013-2020 Heetian Corporation, All rights reserved
    4006-123-731