密码学简介（一）

楼主^#

更多发布于：2011-12-09 05:56

[] 1


	本文简单介绍密码编码学领域的一些基本原理，基本算法和基本理念。仅针对原先对此领域无甚了解的朋友做入门之用。加密解密是信息安全领域的基本技术，加解密系统中的基本概念从下面这张常规加密的简化模型中就可以知道个大概。图片：37_3710_bbe45bdc4ca8534.gif 从图中可以看出，明文输入在密钥K1的作用之下，通过加密算法（如DES）转换成密文，于是可以发送给通信的接收方；接收方则可以通过解密算法以及密钥K2将密文恢复成明文。注意通信内容经加密后，可采用公共通道（如互联网）传输。还应注意密钥在加解密系统中起着关键作用，密钥本身当然不能直接通过公共通道来传输，需要通信双方事先约定，通过其它安全通道或安全机制来传送。而围绕着K1和K2，加解密算法可分为两大类，一类叫对称加密，另一类叫非对称加密。对称加密最基本的加密算法，如上面提到的DES，以及其它一些，比如AES、IDEA、RC5、RC2，CAST-128，Blowfish等，都是对称加密算法。对称加密的“对称”指的是加密过程和解密过程所用的密钥是相同的，或者，可以很容易地相互推导出来。如果对某种算法（如DES）的细节感兴趣，可以看看《密码编码学与网络安全》或《应用密码学》等专业书籍。或者看看wiki上的介绍（如DES，AES），或者看看图片也行。但不要被这些图片吓着，这些算法并不十分“复杂”，只是十分“麻烦”。麻烦可以增加破解的难度，而“复杂”则会增加安全性分析的难度。多数对称加密算法就连算法本身都是对称的，即完全一样的算法（甚至完全一样的模式）同时用于加密和解密。基本理念在加密解密领域，有一项重要的理念叫“轻算法，重密钥”，意思是说算法应该公开，但密钥要保存好。算法公开，全世界的人都可以帮你分析它的安全性，帮你找漏洞，并试图破解它。如果这样还是破解不了，那就说明你的算法基本是安全的，要破解它理论上只能通过“暴力穷举”之类的方法。而暴力穷举的难度直接取决于密钥的长度。这样，只要密钥足够长，你便可以有信心。www.atcpu.com 反过来想，为什么不“轻密钥，重算法”呢？至少有一个方面是显然的：密钥的选择余地更大——64bit的密钥就可以有2的64次方种组合，约为1.8 * 10¹⁹。而对于好的算法，我们能有这么多选择么？ 10¹⁹是个什么概念呢？做个计算，假设你有1000台服务器组成的集群，每台服务器上有8个CPU，每个CPU有4个核且时钟频率为2G，再假设处理器可以在1000个时钟周期内完成某个密钥的计算及判定。如此，要穷举64bit的密钥空间也得9年时间。不过，现代对称加密算法好多都采用128位的密钥了。一种古老的加密算法是把英语中的26个字母分别替换成另一个字母，这种就过于简单了，甚至穷举都很容易，更何况还有基于字母概率的破解方法（比如在正常的英文文本中字母“e”出现的频率最高，看过福尔摩斯探案集的朋友对此或许还有印象。）指标判断一个加密算法的好坏有许多指标，除去实现细节方面的以外，至少还有两项指标值得了解： 1. 雪崩效应所谓雪崩效应，就是明文和密钥哪怕只有1bit的改变，都会让生成的密文产生很大的变化。这显然有助于抵抗各种基于微小变化的差分分析。 2. 结构及运算简单算法本身要很“麻烦”，但算法使用的运算要尽量简单，这有利于安全性分析，有利于加密解密的效率。这样的算法甚至用硬件实现都方便。非对称加密与对称加密不同，非对称加密中加密和解密的密钥是不同的，且从某个密钥推导出另一个密钥被认为十分困难。非对称加密算法中一般会有一个私有密钥KR和一个公开密钥KU。两个密钥不同且难以相互导出。非对称算法的主要用途有：加密/解密、数字签名和密钥交换等。由于非对称加密的效率远低于对称加密，因此实际中常用的模式是使用非对称算法为通信双方传输或协商一个临时秘钥。然后双方通过这个密钥使用性能更高的对称加密算法来通信。注意协商出来的密协可以是临时的。这在为密钥分配提供了很大便利。如果没有这样的机制，可以想象一下，密钥的分配和保存是多么严重的问题：密钥可以保障通信的安全，那谁又来保障密钥的安全？还记得谍战片里的“XX年XX刻本《康熙字典》”吗？一旦被敌人知道了密钥就是这本字典，以及哪天使用哪一页，后果就可想而知了…… 细心的朋友会问：那非对称加密本身使用的密钥又如何传输呢？别忘了非对称加密中至少有一个密钥可以不用告诉别人，所以这样做是相对安全的。而实际的密钥协商机制通常会使用非对称算法的某种变形，比这还要灵巧。甚至可以在互不信任的双方之间协商临时密钥。 RSA 说到非对称加密，便自然会讲到RSA算法。在信息安全领域，RSA算法是具有划时代意义的重大发明。它是由麻省理工学院的Ron Rivest、AdiShamir和LenAdleman于1977年研制并于1978年首次发表的一种算法。（怎么这么多1978？intel发布8086开启X86纪元也是1978……） RSA算法的原理不难理解，但要介绍它还是需要一点点数论基础，所以我们不打算在这里讨论它的细节了。只说明一点，它的安全性依赖于大整数素因子分解的难度，即已知两个大素数p和q的乘积n，想要反推出p和q是十分困难的。椭圆曲线（ECC）椭圆曲线算法是另一种非对称加密算法。它由于能以更短的密钥长度（意味着更少的运算量）提供与RSA相当的安全强度而备受青眯。注意椭圆曲线并非椭圆。而且一类三次方程所对应的曲线。椭圆曲线密码算法基于一种人为定义的有趣运算。首先，定义无穷远点O，并作为加法的单位元。然后基于有限域上的椭圆曲线，定义一种加法。比如在下面的图a中，直线与椭圆曲线相交成三点，J，K，L，我们定义J + K + L = O，J + K = -L。特别地，与X轴垂直的直线交曲线于两点时，如下面的图b，我们定义这两点之和为O，如果一点为J，另一点即为-J。图片：37_3710_a74943387d20a7c.gif 当直线与曲线在某点相切且另一点相交时，如下面的图a，我们定义J + J + L = O，即2J = -L。特别地，如果与X轴垂直的直线与曲线相切于一点，如下面的图b，我们定义2J = O。图片：37_3710_4d8795b46331fb0.gif 图片来源：http://www.tataelxsi.com/whitepapers/ECC_Tut_v1_0.pdf?pdf_id=public_key_TEL.pdf，略有PS。然后，我们定义：3L = 2L + L = L + L + L，4L ＝ 3L + L，依此类推…… 而椭圆曲线算法基于的难题是：已知整数k和点P，计算Q = kP较为容易；而已知Q和P，要反推k则困难得多