精华内容
下载资源
问答
  • RSA算法与DSA算法的区别

    千次阅读 2019-08-02 14:27:12
    当我们在Linux/Unix系统(windows下需用gitbash工具)中通过生成ssh认证密钥时,你要(用-t type来... DSA(用于数字签名算法签名生成速度很快,验证速度很慢,加密时更慢,但解密时速度很快,安全性与RSA密钥...

            当我们在Linux/Unix系统(windows下需用git的bash工具)中通过生成ssh认证密钥时,你要(用-t type来)选择创建一对RSA或者DSA密钥。这两者之间有什么区别?是什么原因让人们选择其中一个而不选另外一个?

    Go with RSA

            DSA(用于数字签名算法)的签名生成速度很快,验证速度很慢,加密时更慢,但解密时速度很快,安全性与RSA密钥相等,而密钥长度相等。此为一些重要的话,现在是一些观点。

            RSA算法(可用于加密和数字签名)的安全性基于这样的事实:大整数的因式分解被认为是‘难以破解’(困难的),而DSA安全性基于离散对数问题。今天已知用于分解大整数块的最快算法是通用数字场筛(可以理解为对简单合理筛或二次筛的改进算法),也是解决有限域中的离散对数问题的最快算法,该算法以DSA指定的大素数为模。

            现在,如果安全性可以被认为是平等的,那么我们当然会赞成更快的算法,但是,再一次,没有明确的赢家。

            如果你的计算机安装了OpenSSL,请运行。您将看到DSA在生成签名时执行的很快,但在验证具有相同密钥长度的签名时速度要慢得多。通常来说你想要验证得(速度)更快,如果你处理的是一个已签名的文件,(而如果你的)签名只生成一次,这很好,但文件签名最终可能会被用户频繁地验证(这就不好了,因为验证速度很慢)。

            两者都支持某种形式的加密方法,开箱即用的RSA和使用EI GAMAL(一种基于Diffie-Hellman密钥交换的非对称加密算法)的DSA。DSA解密速度通常很快,但加密较慢,而RSA则相反。同样,您会希望解密速度更快,因为一个加密文档可能会被频繁解密。

            从商业角度来看,RSA显然是赢家,商业RSA证书比DSA证书被更广泛地部署。

            关键是:(当查看)说DSA密钥必须长1024位,才能符合NIST(美国国家标准技术研究院)的FIPS 186-2(数字签名标准).因此,虽然理论上可能有更长的DSA密钥(FIPS 186-2也明确允许它们),但你仍然受限于1024位。

            今天,你最好使用RSA 2048位密钥(也可以直接生成4096位的RSA密钥)

            FIPS 186-4规定了三种可用于数据保护的数字签名生成和验证技术:数字签名算法(DSA),椭圆曲线数字签名算法(ECDSA)和Rivest-Shamir Adelman算法( RSA)。

    后记

            实际上,OpenSSH 7.0及以上版本默认禁用了ssh-dss(DSA)公钥算法。官方没有给出具体的解释,但其中可能有OpenSSH,DSA密钥位数生成的原因,同时生成签名时随机性差,可能会泄漏私钥,且以现在机算机的算力,DSA 1024-bit已经实际上可破解,建议不使用。

     

    展开全文
  • DSA算法 和 RSA算法

    2009-09-22 18:03:36
    [size=small][b]RSA算法 [/b][/size]1978年就出现了这种算法,它是第一个既能用于数据加密也能...但RSA的安全性一直未能得到理论上的证明。 RSA的安全性依赖于大数分解。公钥和私钥都是两个大素数( 大于 100个十...
    [size=small][b]RSA算法 [/b][/size]1978年就出现了这种算法,它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作,也很流行。算法的名字以发明者的名字命名:Ron Rivest, AdiShamir 和Leonard Adleman。但RSA的安全性一直未能得到理论上的证明。 
    RSA的安全性依赖于大数分解。公钥和私钥都是两个大素数( 大于 100个十进制位)的函数。据猜测,从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。
    密钥对的产生。选择两个大素数,p 和q 。计算:
    n = p * q
    然后随机选择加密密钥e,要求 e 和 ( p - 1 ) * ( q - 1 ) 互质。最后,利用Euclid 算法计算解密密钥d, 满足
    e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )
    其中n和d也要互质。数e和n是公钥,d是私钥。两个素数p和q不再需要,应该丢弃,不要让任何人知道。
    加密信息 m(二进制表示)时,首先把m分成等长数据块 m1 ,m2,..., mi ,块长s,其中 2^s <= n, s 尽可能的大。对应的密文是:
    ci = mi^e ( mod n ) ( a )
    解密时作如下计算:
    mi = ci^d ( mod n ) ( b )
    RSA 可用于数字签名,方案是用 ( a ) 式签名, ( b )式验证。具体操作时考虑到安全性和 m信息量较大等因素,一般是先作 HASH 运算。
    RSA 的安全性。
    RSA的安全性依赖于大数分解,但是否等同于大数分解一直未能得到理论上的证明,因为没有证明破解 RSA就一定需要作大数分解。假设存在一种无须分解大数的算法,那它肯定可以修改成为大数分解算法。目前, RSA的一些变种算法已被证明等价于大数分解。不管怎样,分解n是最显然的攻击方法。现在,人们已能分解140多个十进制位的大素数。因此,模数n必须选大一些,因具体适用情况而定。
    RSA的速度。
    由于进行的都是大数计算,使得RSA最快的情况也比DES慢上100倍,无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。
    RSA的选择密文攻击。
    RSA在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装(Blind),让拥有私钥的实体签署。然后,经过计算就可得到它所想要的信息。实际上,攻击利用的都是同一个弱点,即存在这样一个事实:乘幂保留了输入的乘法结构:
    ( XM )^d = X^d *M^d mod n
    前面已经提到,这个固有的问题来自于公钥密码系统的最有用的特征--每个人都能使用公钥。但从算法上无法解决这一问题,主要措施有两条:一条是采用好的公钥协议,保证工作过程中实体不对其他实体任意产生的信息解密,不对自己一无所知的信息签名;另一条是决不对陌生人送来的随机文档签名,签名时首先使用One-Way Hash Function对文档作HASH处理,或同时使用不同的签名算法。在中提到了几种不同类型的攻击方法。
    RSA的公共模数攻击。
    若系统中共有一个模数,只是不同的人拥有不同的e和d,系统将是危险的。最普遍的情况是同一信息用不同的公钥加密,这些公钥共模而且互质,那末该信息无需私钥就可得到恢复。设P为信息明文,两个加密密钥为e1和e2,公共模数是n,则:
    C1 = P^e1 mod n
    C2 = P^e2 mod n
    密码分析者知道n、e1、e2、C1和C2,就能得到P。
    因为e1和e2互质,故用Euclidean算法能找到r和s,满足:
    r * e1 + s * e2 = 1
    假设r为负数,需再用Euclidean算法计算C1^(-1),则
    ( C1^(-1) )^(-r) * C2^s = P mod n
    另外,还有其它几种利用公共模数攻击的方法。总之,如果知道给定模数的一对e和d,一是有利于攻击者分解模数,一是有利于攻击者计算出其它成对的e’和d’,而无需分解模数。解决办法只有一个,那就是不要共享模数n。
    RSA的小指数攻击。 有一种提高RSA速度的建议是使公钥e取较小的值,这样会使加密变得易于实现,速度有所提高。但这样作是不安全的,对付办法就是e和d都取较大的值。
    RSA算法是第一个能同时用于加密和数字签名的算法,也易于理解和操作。RSA是被研究得最广泛的公钥算法,从提出到现在已近二十年,经历了各种攻击的考验,逐渐为人们接受,普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解,但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何,而且密码学界多数人士倾向于因子分解不是NPC问题。
    RSA的缺点主要有:A)产生密钥很麻烦,受到素数产生技术的限制,因而难以做到一次一密。B)分组长度太大,为保证安全性,n 至少也要 600 bits以上,使运算代价很高,尤其是速度较慢,较对称密码算法慢几个数量级;且随着大数分解技术的发展,这个长度还在增加,不利于数据格式的标准化。目前,SET(Secure Electronic Transaction)协议中要求CA采用2048比特长的密钥,其他实体使用1024比特的密钥。
    [size=small][b]DSS/DSA算法[/b][/size]
    Digital Signature Algorithm
    (DSA)是Schnorr和ElGamal签名算法的变种,被美国NIST作为DSS(Digital SignatureStandard)。算法中应用了下述参数:
    p:L bits长的素数。L是64的倍数,范围是512到1024;
    q:p - 1的160bits的素因子;
    g:g = h^((p-1)/q) mod p,h满足h < p - 1, h^((p-1)/q) mod p > 1;
    x:x < q,x为私钥 ;
    y:y = g^x mod p ,( p, q, g, y )为公钥;
    H( x ):One-Way Hash函数。DSS中选用SHA( Secure Hash Algorithm )。
    p, q,
    g可由一组用户共享,但在实际应用中,使用公共模数可能会带来一定的威胁。签名及验证协议如下:
    1. P产生随机数k,k < q;
    2. P计算 r = ( g^k mod p ) mod q
    s = ( k^(-1) (H(m) + xr)) mod q
    签名结果是( m, r, s )。
    3. 验证时计算 w = s^(-1)mod q
    u1 = ( H( m ) * w ) mod q
    u2 = ( r * w ) mod q
    v = (( g^u1 * y^u2 ) mod p ) mod q
    若v = r,则认为签名有效。
    DSA是基于整数有限域离散对数难题的,其安全性与RSA相比差不多。DSA的一个重要特点是两个素数公开,这样,当使用别人的p和q时,即使不知道私钥,你也能确认它们是否是随机产生的,还是作了手脚。RSA算法却作不到。
    展开全文
  • DSA签名算法的攻击

    2019-01-21 23:05:00
     DSA是在ElGamal和Schnorr两个签名方案基础上设计,其安全性基于求离散对数困难性。生成签名长度 320 bit,算法描述如下: (1) 全局公开钥  lp:满足2L-1<p<2L大素数,其中512≤L≤1024且L是64...

    DSA算法介绍:

      DSA是在ElGamal和Schnorr两个签名方案的基础上设计的,其安全性基于求离散对数的困难性。生成签名长度 320 bit,算法描述如下:

    (1) 全局公开钥

      l p:满足2L-1<p<2L 的大素数,其中512≤L≤1024且L是64的倍数

      l qp-1的素因子,满足2159<q<2160 ,即q长为160比特。

      l gg=h(p-1)/q mod ph是满足1<h<p-1且使得h(p-1)/q mod p >1的任一整数

    (2) 用户秘密钥x

      l x是满足0<x<q的随机数或伪随机数

    (3) 用户的公开钥y

      l ygx mod p

    (4) 用户为待签消息选取的秘密数k

      l k是满足0<k<q的随机数或伪随机数。

    (5) 签名过程

      l 用户对消息M的签名为(r, s),其中r≡(gk mod p) mod q

      l  s≡[k-1(H(M)+xr)] mod q,H(M)是由SHA求出的杂凑值

    (6) 验证过程

      l 设接收方收到的消息为M¢,签名为(r¢,s¢)。计算

      l w≡(s¢)-1 mod q,u1≡[H(M¢)w] mod q

      l u2≡r¢w mod q, v≡[(gu1yu2) mod p] mod q

      l 检查v=r ¢是否成立,若相等,则认为签名有效。

     


     


     

    1.利用如下的参数,恢复DSA的秘密钥x

     

    p = 800000000000000089e1855218a0e7dac38136ffafa72eda7

     

         859f2171e25e65eac698c1702578b07dc2a1076da241c76c6

     

         2d374d8389ea5aeffd3226a0530cc565f3bf6b50929139ebe

     

         ac04f48c3c84afb796d61e5a4f9a8fda812ab59494232c7d2

     

         b4deb50aa18ee9e132bfa85ac4374d7f9091abc3d015efc87

     

         1a584471bb1

     

      q = f4f47f05794b256174bba6e9b396a7707e563c5b

     

      g = 5958c9d3898b224b12672c0b98e06c60df923cb8bc999d119

     

         458fef538b8fa4046c8db53039db620c094c9fa077ef389b5

     

         322a559946a71903f990f1f7e0e025e2d7f7cf494aff1a047

     

         0f5b64c36b625a097f1651fe775323556fe00b3608c887892

     

         878480e99041be601a62166ca6894bdd41a7054ec89f756ba

     

         9fc95302291

     

    y = 84ad4719d044495496a3201c8ff484feb45b962e7302e56a392aee4

     

          abab3e4bdebf2955b4736012f21a08084056b19bcd7fee56048e004

     

          e44984e2f411788efdc837a0d2e5abb7b555039fd243ac01f0fb2ed

     

          1dec568280ce678e931868d23eb095fde9d3779191b8c0299d6e07b

     

          bb283e6633451e535c45513b2d33c99ea17

     

    被签名的消息为:For those that envy a MC it can be hazardous to your health

     

     So be friendly, a matter of life and death, just like a etch-a-sketch,它的SHA1 值为(十六进制):0xd2d0714f014a9784047eaeccf956520045c45265。

     

    得到的签名为:

     

      r = 548099063082341131477253921760299949438196259240

     

      s = 857042759984254168557880549501802188789837994940

     

      已知签名用的"k" 的范围是 0 到2^16。

     

      请编程恢复DSA的秘密钥x,它的SHA1 值为:

     

    0954edd5e0afe5542a4adf012611a91912a3ec16

    思路:

      首先,根据题目提示,可以根据r的取值先计算求出k的值(r≡(gk mod p) mod q);因为2^16穷举一下很轻松,时间复杂度还是可以接受的。

     

    #先恢复k的值,穷举1-65536

     

    for k in range(2**16):

     

      temp=fastExpMod(g,k,p)

     

      temp %=q

     

      if temp == r:

     

        break

     

      else:

     

        pass

     

    print "k=",k

     

    上面用到了:自定义的幂次取模的函数fastExpMod,

     

    def fastExpMod(b, e, m):  #快速幂取模函数;b为底数,e为指数,m为模数

     

        result = 1

     

        while e != 0:

     

            if (e&1) == 1:

     

                result = (result * b) % m

     

            e >>= 1

     

            b = (b*b) % m

     

    return result    #返回取模结果

     

    其次,可以根据s的取值计算x:

     

    s≡[k-1(H(M)+xr)] mod q

     

    可以继续推出 xr -1 *[ks-H(M)]  mod q

     

    这一步将要计算r -1的取值,用到一个自定义的求模逆函数:

     

    findModReverse,原理是基于扩展欧几里得算法求模逆,贴一下代码:

     

    def gcd(a,b):  #求最大公约数函数

     

        while a!=0:

     

            a,b = b%a,a

     

        return b

     

    def findModReverse(a,m):#这个扩展欧几里得算法求模逆

     

        if gcd(a,m)!=1:

     

            return None

     

        u1,u2,u3 = 1,0,a

     

        v1,v2,v3 = 0,1,m

     

        while v3!=0:

     

            q = u3//v3

     

            v1,v2,v3,u1,u2,u3 = (u1-q*v1),(u2-q*v2),(u3-q*v3),v1,v2,v3

     

    return u1%m

     

    代码:

    # -*- coding=utf-8 -*-
    # py2
    import hashlib 
    p = 0x800000000000000089e1855218a0e7dac38136ffafa72eda7859f2171e25e65eac698c1702578b07dc2a1076da241c76c62d374d8389ea5aeffd3226a0530cc565f3bf6b50929139ebeac04f48c3c84afb796d61e5a4f9a8fda812ab59494232c7d2b4deb50aa18ee9e132bfa85ac4374d7f9091abc3d015efc871a584471bb1
    q = 0xf4f47f05794b256174bba6e9b396a7707e563c5b
    g = 0x5958c9d3898b224b12672c0b98e06c60df923cb8bc999d119458fef538b8fa4046c8db53039db620c094c9fa077ef389b5322a559946a71903f990f1f7e0e025e2d7f7cf494aff1a0470f5b64c36b625a097f1651fe775323556fe00b3608c887892878480e99041be601a62166ca6894bdd41a7054ec89f756ba9fc95302291
    y = 0x84ad4719d044495496a3201c8ff484feb45b962e7302e56a392aee4abab3e4bdebf2955b4736012f21a08084056b19bcd7fee56048e004e44984e2f411788efdc837a0d2e5abb7b555039fd243ac01f0fb2ed1dec568280ce678e931868d23eb095fde9d3779191b8c0299d6e07bbb283e6633451e535c45513b2d33c99ea17
    hash_x=0x0954edd5e0afe5542a4adf012611a91912a3ec16
    Hash_M=0xd2d0714f014a9784047eaeccf956520045c45265
    r = 548099063082341131477253921760299949438196259240
    s = 857042759984254168557880549501802188789837994940
    
    def fastExpMod(b, e, m):    #快速幂取模函数;b为底数,e为指数,m为模数
        result = 1
        while e != 0:
            if (e&1) == 1:
                result = (result * b) % m
            e >>= 1
            # b, b^2, b^4, b^8, ... , b^(2^n)
            b = (b*b) % m
        return result
    def gcd(a,b):          #求最大公约数函数
        while a!=0:
            a,b = b%a,a
        return b
    def findModReverse(a,m):    #这个扩展欧几里得算法求模逆
        if gcd(a,m)!=1:
            return None
        u1,u2,u3 = 1,0,a
        v1,v2,v3 = 0,1,m
        while v3!=0:
            q = u3//v3
            v1,v2,v3,u1,u2,u3 = (u1-q*v1),(u2-q*v2),(u3-q*v3),v1,v2,v3
        return u1%m
    if __name__ == '__main__':
        #先恢复k的值,穷举1-65536
        for k in range(2**16):
            temp=fastExpMod(g,k,p)
            temp %=q
            if temp == r:
                break
            else:
                pass
        print "k=",k    
        r_rev=findModReverse(r,q)
        print "r^-1=",r_rev 
    
        x=(k*s-Hash_M)%q
        x=x*r_rev %q
        print "x=",x
        hex_x=hex(x)[2:-1]
        print "hex_x=",hex_x
        Hash_x=hashlib.sha1(hex_x).hexdigest()
        print "Sha1(x)=",Hash_x
        if hash_x==int(Hash_x,16):
            print "哈希匹配,求解私钥x正确!"

    执行结果:



    2.如下是十一组消息及其DSA签名:

    msg: Listen for me, you better listen for me now.
    s: 1267396447369736888040262262183731677867615804316
    r: 1105520928110492191417703162650245113664610474875
    m: a4db3de27e2db3e5ef085ced2bced91b82e0df19
    
    msg: Listen for me, you better listen for me now. s: 29097472083055673620219739525237952924429516683 r: 51241962016175933742870323080382366896234169532 m: a4db3de27e2db3e5ef085ced2bced91b82e0df19
    msg: When me rockin' the microphone me rock on steady, s: 277954141006005142760672187124679727147013405915 r: 228998983350752111397582948403934722619745721541 m: 21194f72fe39a80c9c20689b8cf6ce9b0e7e52d4
    msg: Yes a Daddy me Snow me are de article dan. s: 1013310051748123261520038320957902085950122277350 r: 1099349585689717635654222811555852075108857446485 m: 1d7aaaa05d2dee2f7dabdc6fa70b6ddab9c051c5
    msg: But in a in an' a out de dance em s: 203941148183364719753516612269608665183595279549 r: 425320991325990345751346113277224109611205133736 m: 6bc188db6e9e6c7d796f7fdd7fa411776d7a9ff
    msg: Aye say where you come from a, s: 502033987625712840101435170279955665681605114553 r: 486260321619055468276539425880393574698069264007 m: 5ff4d4e8be2f8aae8a5bfaabf7408bd7628f43c9
    msg: People em say ya come from Jamaica, s: 1133410958677785175751131958546453870649059955513 r: 537050122560927032962561247064393639163940220795 m: 7d9abd18bbecdaa93650ecc4da1b9fcae911412
    msg: But me born an' raised in the ghetto that I want yas to know, s: 559339368782867010304266546527989050544914568162 r: 826843595826780327326695197394862356805575316699 m: 88b9e184393408b133efef59fcef85576d69e249
    msg: Pure black people mon is all I mon know. s: 1021643638653719618255840562522049391608552714967 r: 1105520928110492191417703162650245113664610474875 m: d22804c4899b522b23eda34d2137cd8cc22b9ce8
    msg: Yeah me shoes a an tear up an' now me toes is a show a s: 506591325247687166499867321330657300306462367256 r: 51241962016175933742870323080382366896234169532 m: bc7ec371d951977cba10381da08fe934dea80314
    msg: Where me a born in are de one Toronto, so s: 458429062067186207052865988429747640462282138703 r: 228998983350752111397582948403934722619745721541 m: d6340bfcda59b6b75b59ca634813d572de800e8f 

    这些消息的签名公钥为:

    y = 2d026f4bf30195ede3a088da85e398ef869611d0f68f0713d51c9c1a3a26c95105d915e2d8cdf26d056b86b8a7b8

        5519b1c23cc3ecdc6062650462e3063bd179c2a6581519f674a61f1d89a1fff27171ebc1b93d4dc57bceb7ae2430

        f98a6a4d83d8279ee65d71c1203d2c96d65ebbf7cce9d32971c3de5084cce04a2e147821

    另外,参数p,q,g与上一题的相同。

    请编程恢复DSA的秘密钥x,它的SHA1 值为:

    ca8f6f7c66fa362d40760d135b763eb8527d3d52

     思路:

      从题目所知道的,p、q、g和第一题一样不变,变的是k的值以及私钥x(显然公钥y也要随着改变)。特点是这十一组数据和签名都有共同的私钥x,但是k并不完全一样,首先寻找规律,发现存在几组数据的r值相同,根据定义 r≡(gk mod p) mod q,说明这几组的k值相同

    下面图中几组是整理的r相同的几组

      

      下面是计算x的推导公式,s1、s2代表的是r值相同的两组(从上图三组中任取一组),这样的好处是,虽然不知到k的取值,但是两个方程两个未知数便可以约去一个k甚至能求出k,并且得到x的取值

       

    代码:

     1 # -*- coding=utf-8 -*-
     2 # py2
     3 import hashlib 
     4 p = 0x800000000000000089e1855218a0e7dac38136ffafa72eda7859f2171e25e65eac698c1702578b07dc2a1076da241c76c62d374d8389ea5aeffd3226a0530cc565f3bf6b50929139ebeac04f48c3c84afb796d61e5a4f9a8fda812ab59494232c7d2b4deb50aa18ee9e132bfa85ac4374d7f9091abc3d015efc871a584471bb1
     5 q = 0xf4f47f05794b256174bba6e9b396a7707e563c5b
     6 g = 0x5958c9d3898b224b12672c0b98e06c60df923cb8bc999d119458fef538b8fa4046c8db53039db620c094c9fa077ef389b5322a559946a71903f990f1f7e0e025e2d7f7cf494aff1a0470f5b64c36b625a097f1651fe775323556fe00b3608c887892878480e99041be601a62166ca6894bdd41a7054ec89f756ba9fc95302291
     7 y = 0x84ad4719d044495496a3201c8ff484feb45b962e7302e56a392aee4abab3e4bdebf2955b4736012f21a08084056b19bcd7fee56048e004e44984e2f411788efdc837a0d2e5abb7b555039fd243ac01f0fb2ed1dec568280ce678e931868d23eb095fde9d3779191b8c0299d6e07bbb283e6633451e535c45513b2d33c99ea17
     8 hash_x=0x0954edd5e0afe5542a4adf012611a91912a3ec16
     9 Hash_M=0xd2d0714f014a9784047eaeccf956520045c45265
    10 r = 548099063082341131477253921760299949438196259240
    11 s = 857042759984254168557880549501802188789837994940
    12 
    13 def fastExpMod(b, e, m):  #快速幂取模函数;b为底数,e为指数,m为模数
    14     result = 1
    15     while e != 0:
    16         if (e&1) == 1:
    17             result = (result * b) % m
    18         e >>= 1
    19         # b, b^2, b^4, b^8, ... , b^(2^n)
    20         b = (b*b) % m
    21     return result
    22 def gcd(a,b):  #求最大公约数函数
    23     while a!=0:
    24         a,b = b%a,a
    25     return b
    26 def findModReverse(a,m):    #这个扩展欧几里得算法求模逆
    27     if gcd(a,m)!=1:
    28         return None
    29     u1,u2,u3 = 1,0,a
    30     v1,v2,v3 = 0,1,m
    31     while v3!=0:
    32         q = u3//v3
    33         v1,v2,v3,u1,u2,u3 = (u1-q*v1),(u2-q*v2),(u3-q*v3),v1,v2,v3
    34     return u1%m
    35 if __name__ == '__main__':
    36     #先恢复k的值,穷举1-65536
    37     for k in range(2**16):
    38         temp=fastExpMod(g,k,p)
    39         temp %=q
    40         if temp == r:
    41             break
    42         else:
    43             pass
    44     print "k=",k    # k= 16575
    45     r_rev=findModReverse(r,q)
    46     print "r^-1=",r_rev #r^-1= 519334352112663596410160066327650448249099314077
    47 
    48     x=(k*s-Hash_M)%q
    49     x=x*r_rev %q
    50     print "x=",x
    51     hex_x=hex(x)[2:-1]
    52     print "hex_x=",hex_x
    53     Hash_x=hashlib.sha1(hex_x).hexdigest()
    54     print "Sha1(x)=",Hash_x
    55     if hash_x==int(Hash_x,16):
    56         print "哈希匹配,求解私钥x正确!"

    运行结果:

    转载于:https://www.cnblogs.com/Higgerw/p/10301482.html

    展开全文
  • 什么是数字签名算法(DSA)

    千次阅读 2014-08-26 22:56:27
    DSA(Digital Signature Algorithm,数字签名算法,用作数字签名标准的一部分),它是另一...DSA算法的安全性基于解离散对数的困难性,这类签字标准具有较大的兼容性和适用性,成为网络安全体系的基本构件之一。 p

    DSA(Digital Signature Algorithm,数字签名算法,用作数字签名标准的一部分),它是另一种公开密钥算法,它不能用作加密,只用作数字签名。DSA使用公开密钥,为接受者验证数据的完整性和数据发送者的身份。它也可用于由第三方去确定签名和所签数据的真实性。DSA算法的安全性基于解离散对数的困难性,这类签字标准具有较大的兼容性和适用性,成为网络安全体系的基本构件之一。


    p是L位长的素数,其中L从512到1024且是64的倍数。


    q是160位长且与p-1互素的因子,其中h是小于p-1并且满足 大于1的任意数。


    x是小于q的数。


    另外,算法使用一个单向散列函数H(m)。标准指定了安全散列算法(SHA)。三个参数p,q和g是公开的,且可以被网络中所有的用户公有。私人密钥是x,公开密钥是y。


    对消息m签名时:


    (1) 发送者产生一个小于q的随机数k。

    (2) 发送者产生:

    r和s就是发送者的签名,发送者将它们发送给接受者。

    (3) 接受者通过计算来验证签名:

    如果v=r,则签名有效。


    DSA签名:


    公开密钥:


    p 512位到1024位的素数

    q 160位长,并与p-1互素的因子

    其中h是小于p-1并且满足 大于1的任意数。


    私人密钥:

    x小于q


    签名:

    k选取小于q的随机数


    验证:

    如果v=r,则签名被验证。

    展开全文
  • DSA是基于整数有限域离散对数难题,其安全性与RSA相比差不多。DSA的一个重要特点是两个素数公开,这样,当使用别人p和q时,即使不知道私钥,你也能确认它们是否是随机产生,还是作了手脚。RSA却做不到。 ...
  • dsa数字签名算法.doc

    2020-08-01 00:13:52
    DSA数字签名算法 1 引言 为了确保数据传输的安全性不得不采取一系列的安全技术如加密技术数字签名身份认证密钥管理防火墙安全协议等其中数字签名就是实现网上交易安全的核心技术之一它可以保证信息传输的保密性数据...
  • DSA数字签名算法

    2017-11-27 03:59:55
    一、DSA概述为了确保数据传输的安全性,不得不采取一系列的安全技术,如加密技术、数字签名、身份认证、密钥管理、防火墙、安全协议等。其中数字签名就是实现网上交易安全的核心技术之一,它可以保证信息传输的保密...
  • DSA和RSA算法的差异

    2009-11-20 19:13:57
    1978年就出现了这种算法...但RSA的安全性一直未能得到理论上的证明。 RSA的安全性依赖于大数分解。公钥和私钥都是两个大素数( 大于 100个十进制位)的函数。据猜测,从一个密钥和密文推断出明文的难度等同于分解两...
  • 源文作者王辉第1章基础...但是加密的安全性依靠密钥保管的安全性,在公开的计算机网络上安全地传送和保管密钥是一个严峻的问题,并且如果在多用户的情况下密钥的保管安全性也是一个问题。 单钥密码体制的代表是美国...
  • 但是加密的安全性依靠密钥保管的安全性,在公开的计算机网络上安全地传送和保管密钥是一个严峻的问题,并且如果在多用户的情况下密钥的保管安全性也是一个问题。 单钥密码体制的代表是美国的DES 1.2. 消...
  • RSA 与 DSA

    2014-11-21 11:01:00
    我们在用 ssh-keygen 生成密钥时,通常会面临是使用RSA还是DSA的选择:RSA or DSA, this is a question!...DSA 的安全性是基于整数有限域离散对数难题。基本上可以认为相同密钥长度的 RSA 算法DSA 算法安全性相...
  • 但是加密的安全性依靠密钥保管的安全性,在公开的计算机网络上安全地传送和保管密钥是一个严峻的问题,并且如果在多用户的情况下密钥的保管安全性也是一个问题。 单钥密码体制的代表是美国的DES
  • 但是加密的安全性依靠密钥保管的安全性,在公开的计算机网络上安全地传送和保管密钥是一个严峻的问题,并且如果在多用户的情况下密钥的保管安全性也是一个问题。 <br />单钥密码体制的代表是美国的DES <br...
  • java 对 安全哈希算法 SHA1 实现

    万次阅读 2015-05-18 22:06:17
    安全哈希算法(Secure Hash Algorithm)主要适用于数字签名标准(Digital Signature Standard DSS)里面定义数字签名算法(Digital Signature Algorithm DSA)。对于长度小于2^64位消息,SHA1会产生一个160位...
  • 但是加密的安全性依靠密钥保管的安全性,在公开的计算机网络上安全地传送和保管密钥是一个严峻的问题,并且如果在多用户的情况下密钥的保管安全性也是一个问题。 单钥密码体制的代表是美国的DES
  • 为了解决电力调度系统的安全性问题,克服传统公钥密码体制证书管理复杂的缺陷,在无双线性对思想的基础上,构造了一种基于 DSA 的无证书数字签名方案。方案利用零知识方式对调度用户身份进行认证,将签名身份与公钥...
  • DSA与RSA

    千次阅读 2018-09-12 17:42:18
    在用 ssh-keygen 生成密钥对时,通常会面临是使用RSA还是DSA的选择:RSA or DSA, this is a question!...DSA 的安全性是基于整数有限域离散对数难题。基本上可以认为相同密钥长度的 RSA 算法DSA ...
  • 安全哈希算法SHA1

    千次阅读 2016-12-11 12:41:33
    安全哈希算法(Secure Hash Algorithm)SHA1主要适用于数字签名标准 (Digital Signature Standard DSS)里面定义数字签名算法(Digital SignatureAlgorithm DSA)。对于长度小于2^64位消息,SHA1会产生一个160...

空空如也

空空如也

1 2 3 4 5 ... 13
收藏数 248
精华内容 99
关键字:

dsa算法的安全性