现代密码学-学习心得

通信0805邹引08211132密码学(Cryptology)一词源自希腊语“krypto's”及“logos”两词，意思为“隐藏”及“消息”。它是研究信息系统安全保密的科学。其目的为两人在不安全的信道上进行通信而不被破译者理解他们通信的内容。从几千年前到1949年，密码学还没有成为一门真正的科学，而是一门艺术。密码学专家常常是凭自己的直觉和信念来进行密码设计，而对密码的分析也多基于密码分析者（即破译者）的直觉和经验来进行的。1949年，美国数学家、信息论的创始人Shannon,ClaudeElwood发表了《保密系统的信息理论》一文，它标志着密码学阶段的开始。同时以这篇文章为标志的信息论为对称密钥密码系统建立了理论基础，从此密码学成为一门科学。由于保密的需要，这时人们基本上看不到关于密码学的文献和资料，平常人们是接触不到密码的。1967年Kahn出版了一本叫做《破译者》的小说，使人们知道了密码学。20世纪70年代初期，IBM发表了有关密码学的几篇技术报告，从而使更多的人了解了密码学的存在。但科学理论的产生并没有使密码学失去艺术的一面，如今，密码学仍是一门具有艺术性的科学。1976年，Diffie和Hellman发表了《密码学的新方向》一文，他们首次证明了在发送端和接收端不需要传输密钥的保密通信的可能性，从而开创了公钥密码学的新纪元。该文章也成了区分古典密码和现代密码的标志。1977年，美国的数据加密标准（DES）公布。这两件事情导致了对密码学的空前研究。从这时候起，开始对密码在民用方面进行研究，密码才开始充分发挥它的商用价值和社会价值，人们才开始能够接触到密码学。这种转变也促使了密码学的空前发展。最早的加密技术，当属凯撒加密法了。秘密金轮，就是加解密的硬件设备可以公用，可以大量生产，以降低硬件加解密设备的生产与购置成本。破译和加密技术从来就是共存的，彼此牵制，彼此推进。错综复杂的加解密演算法都是为了能够超越人力执行能力而不断演变的。Kerckhoffs原则、Shannon的完美安全性、DES算法、Rijndael算法……<<NewDirectionsinCryptography>>一文，正如密码学的里程碑，伫立在密码学者不断探索的道路上，作为一种跨越，作为一种象征。文章大致翻译：一、摘要：随着远程通信的发展，特别是计算机网络的发展，密码学面临着两大难题：⒈可靠密钥的传输通道问题。⒉如何提供与手写签名等效的认证体系。为了解决这些问题，文中提出了公钥密码算法和公钥分配算法，并且把公钥密码算法经过变换成为一个单向认证算法，来解决有效认证问题。此外还讨论了密码学中各种问题之间的相互关系，陷门问题，计算复杂性问题，最后回顾了密码学发展的历史。

二、常规密码体系：这一部分主要介绍了密码学的一些基本知识，如密钥、加密、解密，算法的无条件安全与计算性安全，三种攻击法，即唯密文攻击、已知明文攻击、选择明文攻击。需要指出的是，本文给出了密码学的一个定义：研究解决保密和认证这两类安全问题的“数学”方法的学科。还有一点需要指出的是，根据Shannon的理论：无条件安全的算法是存在的，但由于其密钥过长而不实用，这也是发展计算上安全的算法的原因。

三、公钥密码学：公钥密码学主要包括两部分：公钥密码算法和公钥分配算法。公钥密码算法是指定义在有限信息空间{M}上的，基于算法{Ek}和{Dk}的可逆变换

Ek：{M}->{M}

Dk：{M}->{M}

满足下列条件：

⑴对任给K∈{K}，Ek是Dk的互逆变换

⑵对任意的K∈{K}和M∈{M}，用Ek和Dk进行加密和解密是容易计算的

⑶对几乎所有的K∈{K}，从Ek推出Dk在计算上是不可行的

⑷对任意的K∈{K}，从K计算Ek和Dk是可行的

这里K是用以产生Ek和Dk的随机数。性质⑶保证了可公开Ek而不损害Dk的安全性，这样才保证了公钥密码算法的安全性。

以加密二值n维向量为例，加密算法是乘一个n×n可逆矩阵，解密则乘其逆矩阵，所需运算时间为n2。此可逆矩阵可通过对单位矩阵做一系列的行和列的初等变换得到，而其逆矩阵是经过逆序的行和列的逆变换得到。但是矩阵求逆只需要n3的时间，密码分析者用时与正常解密用时之比是n。虽然这个例子并不实用，但对解释公钥密码算法是有用的。一个更实用的方法是利用机器语言的难懂性，把加密算法编译成机器语言公布，而解密算法保密，分析者要理解机器语言的全部运算过程是很困难的，所以要破解是困难的，当然此算法必须足够的复杂以免通过输入和输出对来破解。

公钥分配算法是基于求对数再取模计算上的困难。令q是一个素数，在有限域GF(q)上任取q，计算Y=ax*mod（q），其中a是GF(q)上的一个固定基元。则

X=loga【Y*mod（q）】。不难得出由X计算Y是较容易的，约需要计算2×log2q次乘法；然而从Y得出X是困难的，因为需q/2次运算。这样对每一个用户，从[1，2，…，q-1]中随机的选一个q，计算出Yi=aXi*modq，并将Yi公布，Xi保密。那么当用户i和j通信时，使用Kij=aXiXj*modq作为他们的公共密钥。此密钥用户i通过j公布的Yj得到，即Kij=YjXi*modq=(aXj)Xi*modq=aXiXj*modq得到。用户j的计算同理。对于第三方要获得此密钥就必须计算，而这在计算上是不可行的，从而达到了在公共信道上分配私钥的效果。四、单向认证：现有的认证体系只能保证不被第三方冒名顶替，但不能解决发送者和接收者之间的冲突，为此引入单向函数的概念，即对定义域中的任意x，f(x)是容易计算的，但对几乎所有的值域中的y，求满足y=f(x)的x在计算上是不可行的。例如已知多项式p(x)和x，求y=p(x)是容易的，但若已知y求出x是困难的。值得注意的是，这里的计算上不可逆与数学中的不可逆是完全不同的（数学上的不可逆可能是有多个原像）。

公钥密码算法可用来产生一个真正的单向认证体系。当用户A要发信息M给用户B时，他用其保密的解密密钥解密“M”并传给B，B收到时用A公布的加密密钥“加密”此消息从而得到信息M。因为解密密钥是保密的，只有A发送的消息才具有这样的性质，从而确认此信息来源于A，也就建立了一个单向认证体系。

LeslieLamport还提出另一种单向信息认证方法，它是应用在k维二值空间上的单向函数f到其自身的映射来实现的。若发送者发送N比特的信息m，他要产生2N个随机k维二值向量x1,X1，x2，X2，……xn,Xn,并保密，随后把这些向量在f下的像y1，Y1，y2，Y2，……yn,Yn，发送给接收者。当发送信息m=(m1,m2,…,mN)时，m1=0发送x1，m1=1发送X1，依次类推。接收者把收到的信息用f映射之，若为y1则m1=0，Y1则m1=1，如此下去便得到了m。由于函数f的单向性，接收者无法从y推出x，因此就无法改动接收到的任何收据。当然在N比较大时这种方法的额外开销是很大的，为此有必要引入单向映射g，用来把N比特的信息映射成n比特(n约为50)，但这里要求g有比一般的单向函数更强的性质。

五、问题的相关性和陷门：⒈一个对已知明文攻击安全的密码算法能产生一个单向函数。设:{P}->{K}是这样的一个算法，取P=P0。考虑映射f：{K}->{C}定义为f(x)=Sx(P0)，则f是一个单向函数，因为要由f(x)得到x和已知明文攻击是等价的(即已知P=P0和SK(P0)求不出K)。Evans还提出过另一种方法，他用的映射是f(x)=Sx(X)，这增加了破解的难度，但这个单向函数却破坏了对已知明文攻击安全的要求。

⒉一个公钥密码算法可用来产生一个单向认证体系。这一点在（四）中已经讨论过了。

⒊一个陷门密码算法可用来产生一个公钥分配算法。所谓陷门密码算法是指只有知道陷门信息才能正确还原明文，不掌握陷门信息要破解出明文在计算上是不可行的。比如A要和B建立公共私钥，A任选一个密钥，用B公布的含有陷门信息的加密密钥加密之，并将密文发送给B，B由保密的陷门信息解密得到此密钥，于是A和B建立了公共的私钥。不难发现公钥密码算法是一个陷门单向函数。

六、计算复杂度：现代密码算法的安全性是基于计算上的不可行性，因此就有必要对计算复杂度进行研究。在确定型图灵机上可用多项式时间求解的问题定义为P类复杂度，在非确定型图灵上可用多项式时间求解的问题定义为NP类复杂度，显然NP包括P。Karp还定义了一个NP完全集，即如果NP完全集中的任何一个问题属于P类，则NP中的所有问题都属于P。现在大多数的加密算法用的是NP完全集中的问题。关于密码分析的难度有如下定理：一个加密和解密算法若是能在P时间内完成的，那么密码分析的难度不会大于NP时间。七、历史回顾：

密码学的发展经历了早期的加密过程保密，到60年代对明文攻击安全的算法，到现在算法公开的基于计算复杂度的算法，可见其发展趋势是秘密性越来越弱的。并且随着许多曾经被证明为安全的算法被相继攻破，密码安全性的分析也经历了早期的纯数学证明到后来的密码分析攻击，再到计算复杂度分析。这里还有一个有趣的现象就是密码分析方法大多是由专业人事发现的，而密码算法则主要是由非专业人员提出的。对于这篇经典之作，我的认知显得很是粗陋。要想真正读通这篇巨作，恐怕自己还需要修炼些时日。但是，加密解密已经渗入到如今这个电子化信息化的生活中来，又无时无刻不在感受着密码学带来的快感。信息安全技术作为一门综合学科，它涉及信息论、计算机科学和密码学等多方面知识，研究计算机系统和通信网络内信息的保护方法以实现系统内信息的安全、保密、真实和完整。21世纪是信息时代，信息的传递在人们日常生活中变得非常重要。如：电子商务，电子邮件，电子政务，银行证券等，无时无刻不在影响着人们的生活。这样信息安全问题也就成了最重要的问题之一。在信息交换中，“安全”是相对的，