密码知识教程一

   谈起密码算法,有的人会觉得陌生,但一提起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的缺陷。一般来说只用于少量数据加密。

相关推荐