密码知识教程一

谈起密码算法，有的人会觉得陌生，但一提起PGP，大多数网上朋友都很熟悉，它是一个工具软件，向认证中心注册后就可以用它对文件进行加解密或数字签名，PGP所采用的是RSA算法，以后我们会对它展开讨论。密码算法的目的是为了保护信息的保密性、完整性和安全性，简单地说就是信息的防伪造与防窃取，这一点在网上付费系统中特别有意义。密码学的鼻祖可以说是信息论的创始人香农，他提出了一些概念和基本理论，论证了只有一种密码算法是理论上不可解的，那就是 One Time Padding，这种算法要求采用一个随机的二进制序列作为密钥，与待加密的二进制序列按位异或，其中密钥的长度不小于待加密的二进制序列的长度，而且一个密钥只能使用一次。其它算法都是理论上可解的。如DES算法，其密钥实际长度是56比特，作2^56次穷举，就肯定能找到加密使用的密钥。所以采用的密码算法做到事实上不可解就可以了，当一个密码算法已知的破解算法的时间复杂度是指数级时，称该算法为事实上不可解的。顺便说一下，据报道国外有人只用七个半小时成功破解了DES算法。密码学在不断发展变化之中，因为人类的计算能力也像摩尔定律提到的一样飞速发展。作为第一部分，首先谈一下密码算法的概念。 
　　 密码算法可以看作是一个复杂的函数变换，C = F M, Key ),C代表密文，即加密后得到的字符序列，M代表明文即待加密的字符序列，Key表示密钥，是秘密选定的一个字符序列。密码学的一个原则是“一切秘密寓于密钥之中”，算法可以公开。当加密完成后，可以将密文通过不安全渠道送给收信人，只有拥有解密密钥的收信人可以对密文进行解密即反变换得到明文，密钥的传递必须通过安全渠道。目前流行的密码算法主要有DESRSA，IDEA，DSA等，还有新近的Liu氏算法，是由华人刘尊全发明的。密码算法可分为传统密码算法和现代密码算法，传统密码算法的特点是加密和解密必须是同一密钥，如DES和IDEA等；现代密码算法将加密密钥与解密密钥区分开来，且由加密密钥事实上求不出解密密钥。这样一个实体只需公开其加密密钥(称公钥，解密密钥称私钥)即可，实体之间就可以进行秘密通信，而不象传统密码算法似的在通信之前先得秘密传递密钥，其中妙处一想便知。因此传统密码算法又称对称密码算法(Symmetric Cryptographic Algorithms )，现代密码算法称非对称密码算法或公钥密码算法( Public-Key Cryptographic Algorithms )，是由Diffie 和Hellman首先在1976年的美国国家计算机会议上提出这一概念的。按照加密时对明文的处理方式，密码算法又可分为分组密码算法和序列密码算法。分组密码算法是把密文分成等长的组分别加密，序列密码算法是一个比特一个比特地处理，用已知的密钥随机序列与明文按位异或。当然当分组长度为1时，二者混为一谈。这些算法以后我们都会具体讨论。 
　　 RSA算法 
　　 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的缺陷。一般来说只用于少量数据加密。