谈起密码算法，有的人会觉得陌生，但一提起PGP，大多数网上朋友都很熟悉，它是一个工具软件，向认证中心注册后就可以用它对文件进行加解密或数字签名，PGP所采用的是RSA算法，以后我们会对它展开讨论。

    密码算法的目的是为了保护信息的保密性、完整性和安全性，简单地说就是信息的防伪造与防窃取，这一点在网上付费系统中特别有意义。密码学的鼻祖可以说是信息论的创始人香农，他提出了一些概念和基本理论，论证了只有一种密码算法是理论上不可解的，那就是One Time Padding，这种算法要求采用一个随机的二进制序列作为密钥，与待加密的二进制序列按位异或，其中密钥的长度不小于待加密的二进制序列的长度，而且一个密钥只能使用一次。其它算法都是理论上可解的。如DES算 法，其密钥实际长度是56比特，作2^56次穷举，就肯定能找到加密使用的密钥。所以采用的密码算法做到事实上不可解就可以了，当一个密码算法已知的破解算法的时间复杂度是指数级时，称该算法为事实上不可解的。顺便说一下，据报道国外有人只用7个半小时成功破解了DES算法。密码学在不断发展变化之中，因为人类的计算能力也像摩尔定律提到的一样飞速发展。作为第一部分，首先谈一下密码算法的概念。密码算法可以看作是一个复杂的函数变换，C = F( M, Key ),C代表密文，即加密后得到的字符序列，M代表明文即待加密的字符序列，Key表示密钥，是秘密选定的一个字符序列。密码学的一个原则是“一切秘密寓于密钥之中”，算法可以公开。当加密完成后，可以将密文通过不安全渠道送给收信人，只有拥有解密密钥的收信人可以对密文进行解密即反变换得到明文，密钥的传递必须通过安全渠道。目前流行的密码算法主要有DES，RSA，IDEA，DSA等，还有新近的Liu氏算法，是由华人刘尊全发明的。

    密码算法可分为传统密码算法和现代密码算法，传统密码算法的特点是加密和解密必须是同一密钥，如DES和IDEA等；现代密码算法将加密密钥与解密密钥区分开来，且由加密密钥事实上求不出解密密钥。这样一个实体只需公开其加密密钥(称公钥，解密密钥称私钥)即可，实体之间就可以进行秘密通信，而不象传统密码算法似的在通信之前先得秘密传递密钥，其中妙处一想便知。因此传统密码算法又称对称密码算法(Symmetric Cryptographic Algorithms )，现代密码算法称非对称密码算法或公钥密码算法( Public-Key Cryptographic Algorithms )，是由Diffie 和Hellman首先在1976年的美国国家计算机会议上提出这一概念的。按照加密时对明文的处理方式，密码算法又可分为分组密码算法和序列密码算法。分组密码算法是把密文分成等长的组分别加密，序列密码算法是一个比特一个比特地处理，用已知的密钥随机序列与明文按位异或。当然，当分组长度为1时，二者混为一谈。

　 返回

公钥密码算法

数字签名

    数字签名技术主要解决如下问题：
       1)，设实体A经过通信信道向实体B发送一段信息，则B必须知道它在
           离开A后是否被修改过。
       2)，信息经过存储信道也如此。当经存储后读出前，必须能判断是否有
           其他实体对其进行了非法修改。
       3)，实体A和B进行信息交换时，双方必须能对对方的身份进行鉴别，
           以保证他们收到的信息都是由确认的实体发来的。
       4)，信息接收方不能对接收信息篡改，也不能否认他收到的信息。有时
           他还应向发送方明确表示已收到发送的信息。
       5)，信息接收方应能检测出是否为过时的信息，或是某种信息的重发。
       6)，发送方不能否认已发信息。若发生争执，必须能进行公正的判决。
    采取数字签名( Digital Signature )与认证( Authentication )技术是解决上述问题的有效手段。
    数字签名作为解决上述问题的一种手段，这就要求它必须具有以下性质：
        1，签名不可伪造。
        2，签名是可信的。
        3，签名不可重用。签名是被签文档的一部分，只对这一特定文档有效。
        4，被签文档不可变更。一旦被签名，内容不可更改，否则签名失效。
        5，签名不能抵赖。签名和被签文档是一种物理存在，签名者不能否认。
    因此，这就给采用的数字签名算法和应用协议提出了要求。近些年来，人们在这一领域作了大量工作。
    基于对称密码体制( Symmetric Cryptosystem )和仲裁者( Arbitrator )的数字签名。 假设用于签名的算法是理想的，这种方案可以满足上述1 到 5 的要求。但它具有以下不足之处：系统严重依赖于仲裁者的安全性和正确性；由于系统中任何一次签名信息传输都需要仲裁者的参与，而且他的加解密过程是耗时的，故他会成为系统的瓶颈。
    基于公钥体制( Public-Key Cryptography )的数字签名。 自从1976年Diffie 和Hellman 提出公钥思想后，采用公钥算法就成为数字签名的理想选择。假设用于签名的算法是理想的，这种方案也可以满足上述 1 到 5 的要求。目前主要有两类算法：一类是既能用于数字签名又可用于数据加密的，如RSA算法等；另一类只能用于数字签名不可用于数据加密，如DSA算法等。
    RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA 的安全性依赖于大素数的分解，但并没有从理论上证明破译RSA的难度于大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何。RSA的缺点主要有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n 至少也要 600 bits 以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。另外，还有其它不同类型的能同时用于数字签名和加密的公钥算法，如ElGamal算法等，它们的安全程度与RSA 很接近，速度也较慢。
     DSA 是一种仅能用于数字签名的密码算法，它是 Schnorr 和ElGamal签名算法的变种。DSA的安全性比RSA要好一些，但不能用于加密和密钥分配，若在防伪系统中应用，还得使用别的加密算法。其速度要慢于RSA，而且密钥太小，它的密钥在512 bits 到1024 bits 之间可变。DSA由美国 NSA 开发，是美国作为数据加密标准( DSS )提出的。还有一些数字签名算法，但未被人们所广泛接受。目前，RSA算法在国外已成了事实上的标准。    
 

　 返回

RSA算法

　  年就出现了这种算法，它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也很流行。算法的名字以发明者的名字命名：Ron Rivest, Adi Shamir 和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 ，其中 <= n, s 尽可能的大。对应的密文是：

ci = mi^e ( mod n ) ( a )

解密时作如下计算：

mi = ci^d ( mod n ) ( b )

    RSA 可用于数字签名，方案是用 ( a ) 式签名， ( b ) 式验证。具体操作时考虑到安全性和 m信息量较大等因素，一般是先作 HASH 运算。

    RSA 的安全性。 RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解 RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前， RSA 的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解多个十进制位的大素数。因此，模数n 必须选大一些，因具体适用情况而定。

    RSA的速度。 由于进行的都是大数计算，使得RSA最快的情况也比DES慢上倍，无论是软件还是硬件实现。速度一直是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采用比特长的密钥，其他实体使用比特的密钥。

  返回

---

 

ElGamal算法

    ElGamal算法既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。
    密钥对产生办法。首先选择一个素数p，两个随机数, g 和x，g, x < p, 计算 y = g^x  ( mod p )，则其公钥为 y, g 和p。私钥是x。g和p可由一组用户共享。
    ElGamal用于数字签名。被签信息为M，首先选择一个随机数k, k与 p - 1互质，计算

a  =  g^k  ( mod  p )

    再用扩展 Euclidean 算法对下面方程求解b：

M  =  xa + kb ( mod p - 1 )

    签名就是( a, b )。随机数k须丢弃。
    验证时要验证下式：

y^a * a^b  ( mod  p )  =  g^M ( mod  p )

    同时一定要检验是否满足1<= a < p。否则签名容易伪造。
    ElGamal用于加密。被加密信息为M，首先选择一个随机数k，k与 p - 1互质，计算

a  =    g^k   ( mod  p )
b  =   y^k M  ( mod  p )

    ( a, b )为密文，是明文的两倍长。解密时计算

M  =  b / a^x  ( mod  p ) 

    ElGamal签名的安全性依赖于乘法群(IFp)* 上的离散对数计算。素数p必须足够大，且p-1至少包含一个大素数因子以抵抗Pohlig & Hellman算法的攻击。M一般都应采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证g对于p-1的大素数因子不可约。D.Bleichenbacher在“Generating ElGamal Signatures Without Knowing the Secret Key”中提到了一些攻击方法和对策。ElGamal的一个不足之处是它的密文成倍扩张。

    美国的DSS(Digital Signature Standard)的DSA(Digital Signature Algorithm)算法是经ElGamal算法演变而来。

  返回

---

 

DSS/DSA算法

    Digital Signature Algorithm (DSA)是Schnorr和ElGamal签名算法的变种，被美国NIST作为DSS(Digital Signature Standard)。算法中应用了下述参数：
      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算法却作不到。

  返回

---

 

密码学论文< /STRONG>

 

  返回

---

 

密码学链结

 

  返回

---

 

密码学书籍

 

 返回

---

 

攻击PKZIP的加密算法

 A Known Plaintext Attack on the PKZIP Stream Cipher ,Postscript format,zip compressed.

 

 

 返回

---

web hosting • domain names
web design • online games