《密码学的新方向》阅读笔记

《密码学的新方向》读书笔记2016.051学院电子信息工程学院班级通信1306班学号13272053姓名卢文涛指导老师毕红军信息安全技术研究性专题阅读报告《密码学的新方向》读书笔记2016.052目录PartⅠ文章简介.................................................................................3一、简介及摘要..............................................................................3二、常规密码体制..........................................................................3三、公钥密码体制..........................................................................4四、单向认证.................................................................................7五、问题的相关性和陷门..............................................................7六、计算复杂度..............................................................................8七、历史回顾.................................................................................8PartⅡ个人感想.................................................................................9《密码学的新方向》读书笔记2016.053《密码学的新方向》读书笔记PartⅠ文章简介一、简介及摘要本文讨论了当代密码学的两个发展方向：加密和认证。随着远程通信的发展，特别是计算机网络的发展，密码学面临着两大难题：可靠的密钥传输通道问题，和如何提供与书面签名等效的认证体系。为了解决这些问题，文中提出了公钥密码算法和公钥分配算法，并且把公钥密码算法经过变换成为一个单向认证算法，来解决有效认证问题。此外还讨论了密码学中各种问题之间的相互关系，陷门问题，计算复杂性问题，最后回顾了密码学发展的历史。二、常规密码体制密码学问题包括加密和认证，而认证又可分为消息认证和身份认证。作者简单介绍了使用一般密码系统进行通信时信息的流动（如图一）。它包含三部分：发送方，接收方和攻击者。接着，作者介绍了算法的无条件安全与计算性安全，三种攻击法，即唯密文攻击、已知明文攻击、选择明文攻击。并给出了密码学的一个定义：研究解决保密和认证这两类安全问题的“数学”方法的学科。根据Shannon的理论，无条件安全的算法是存在的，但由于其密钥过长而不实用，这也是发展计算上安全的算法的原因。《密码学的新方向》读书笔记2016.054三、公钥密码体制公钥密码体制包括：公钥密码算法和公钥分配算法。公钥密码算法有利于实现认证机制，而公钥分配算法更接近于实现。公钥密码算法是指定义在有限信息空间{M}上的，基于算法{kE}和{kD}的可逆变换：Ek：{M}DK：{M}算法必须满足下列条件：⑴对任给K∈{K}，kE是kD的互逆变换;⑵对任意的K∈{K}和，用kE和kD进行加密和解密是容易计算的;⑶对几乎所有的K∈{K}，从kE推出kD在计算上是不可行的；⑷对任意的K∈{K}，从K计算kE和kD是可行的性质；⑶保证了我们可以公开而不损害的安全性，这样才保证了公钥密码算法的安全性。因此，公钥密码算法可以分为两部分：加密算法和解密算法。利用加密算法推导解密算法是计算不可行的，反之亦然。⑷确保了在对加密和解密函数没有限制的条件下，计算这两个函《密码学的新方向》读书笔记2016.055数的可行性。实际运用中，公钥加密工具必须包含一个随机数生成器用来生成K，利用K计算Ek和Dk。接着，作者举了个例子，以加密二值n维向量为例，加密算法是乘一个n*n可逆矩阵，解密则乘其逆矩阵，所需运算时间为n2。此可逆矩阵可通过对单位矩阵做一系列的行和列的初等变换得到，而其逆矩阵是经过逆序的行和列的逆变换得到。但是矩阵求逆只需要n3的时间，密码分析者用时与正常解密用时之比是n。虽然这个例子并不实用，但对解释公钥密码算法是有用的。一个更实用的方法是利用机器语言的难懂性，把加密算法编译成机器语言公布，而解密算法保密，分析者要理解机器语言的全部运算过程是很困难的，所以要破解是困难的，当然此算法必须足够的复杂以免通过输入和输出对来破解。作者建议使用一种新的密钥分配算法，这种新算法的有效性依赖于计算有限域中离散对数的困难性。具体算法如下：令q是一个素数，有限域为GF（q）。计算Y=αXmodq，其中1≤X≤q−1(4)其中α是GF（q）上的一个固定本原元。然后计算X：X=logαYmodq，其中1≤Y≤q−1(5)不难得出由X计算Y是较容易的，约需要2×log2q次乘法运算[6,pp.398-422]；例如，X=18，则Y=a18(((a2)2)2)2×a2(6)然而用Y计算X是困难的。对于某些精心选定了的q，采用最快的《密码学的新方向》读书笔记2016.056算法也需要q1/2次运算[7,pp.9,575-576],[8]。此密码算法的安全性是建立在求对数模q的运算困难性上的。如果能找到一种求对数模q计算量是随着log2q增长的算法，那么这种加密算法就是无效的。每一个用户，从[1,,2,q−1]中随机的选一个Xi，计算出YiYi=aXimodq(7)并将Yi公布，Xi保密。那么当用户i和j通信时，使用Kij=αXiXjmodq(8)作为他们的公共密钥。此密钥用户i通过公布的Yi得到，即Kij=YjXimodq(9)=(aXj)Ximodq(10)=aXjXi=aXjXimodq(11)用户j的计算Kij同理。Kij=YiXjmodq(12)对于第三方要获得此密钥就必须计算Kij=Yj(logαYi)modq(13)如果logaYj容易计算，那么Kij就容易计算，那么这个系统就会轻易被破解掉。我们没有证据说明即使logaYj被轻易计算出，这个系统也是安全的。也没有证据说明能够在不知道Xi和Xj的情况下，能够计算出Kij。《密码学的新方向》读书笔记2016.057四、单向认证现有的认证体系只能保证不被第三方冒名顶替，但不能解决发送者和接收者之间的冲突，为此引入单向函数的概念，即对定义域中的任意x，f(x)是容易计算的，但对几乎所有的值域中的y，求满足y=f(x)的x在计算上是不可行的。例如已知多项式p(x)和x0，求y0=p(x0)是容易的，但若已知y0求出x0是困难的。值得注意的是，这里的计算上不可逆与数学中的不可逆是完全不同的。公钥密码算法可用来产生一个真正的单向认证体系。当用户A要发信息M给用户B时，他用其保密的解密密钥AD”解密”M并传给B，B收到时用A公布的加密密钥AE”加密”此消息从而得到信息M。因为解密密钥是保密的，只有A发送的消息才具有这样的性质，从而确认此信息来源于A，也就建立了一个单向认证体系。LeslieLamport提出另一种单向信息认证方法就不在这里详细赘述了。五、问题的相关性和陷门1.一个对已知明文攻击安全的密码算法能产生一个单向函数。设是这样的一个算法，取P=P0，考虑映射f：定义为f(x)=)(0PSX，则f是一个单向函数，因为要由f(x)得到x和已知明文攻击是等价的。Evans还提出过另一种方法，他用的映射是f(x)=)(XSX，这增加了破解的难度，但这个单向函数却破坏了对已知明文攻击安全的要求。2.一个公钥密码算法可用来产生一个单向认证体系。这一点在Ⅳ《密码学的新方向》读书笔记2016.058中已经讨论过了。3.一个陷门密码算法可用来产生一个公钥分配算法。所谓陷门密码算法是指只有知道陷门信息才能正确还原明文，不掌握陷门信息要破解出明文在计算上是不可行的。比如A要和B建立公共私钥，A任选一个密钥，用B公布的含有陷门信息的加密密钥加密之，并将密文发送给B，B由保密的陷门信息解密得到此密钥，于是A和B建立了公共的私钥。不难发现公钥密码算法是一个陷门单向函数。六、计算复杂度现代密码算法的安全性是基于计算上的不可行性，因此就有必要对计算复杂度进行研究。在确定型图灵机上可用多项式时间求解的问题定义为P类复杂度，在非确定型图灵上可用多项式时间求解的问题定义为NP类复杂度，显然P∈NP。Karp还定义了一个NP完全集，即如果NP完全集中的任何一个问题属于P类，则NP中的所有问题都属于P。现在大多数的加密算法用的是NP完全集中的问题。关于密码分析的难度有如下定理：一个加密和解密算法若是能在P时间内完成的，那么密码分析的难度不会大于NP时间。七、历史回顾保密是密码学的核心。在早期的密码学中，我们混淆了密码系统中什么该保密，什么不该保密。像凯撒密码（它的加密过程是将26个英文字母循环后移3位，即A变为D，B变E，等等）之类的密码《密码学的新方向》读书笔记2016.059系统，安全性是依赖于算法过程的保密性的。随着电报机[2，p.191]的发明,出现了使用特殊密钥的密码系统，它与一般密码系统差别在于：前者容许将其算法泄露，比如，即使不小心将加密工具泄露，那么只需将密钥换成一个新密钥就可以了。Kerchoffs[2，p.235]在1881就提出了这个观点，即泄露一个密码系统的加密方法不影响系统的安全性。大约在1960年，可以抵御已知明文攻击的密码系统就已经在实际中应用了，这样就无须对以前的信息保密了，减轻了用户负担。公钥密码系统是减少保密内容的系统的自然延续。PartⅡ个人感想首先，我们先做一个简单的背景了解。本片文章写于1976年，作者是美国著名的密码学家Diffie和Hellman。关于作者，我们必须着重介绍一下。WhitfieldDiffie和MartinE.Hellman是世界著名的密码技术与安全技术专家，被业界公认为信息技术安全事物的权威人士。本文讲的就是现在十分流行的Diffie-Hellman密钥交换协议/算法。这是一种确保共享KEY安全穿越不安全网络的方法，这个机制的巧妙在于需要安全通信的双方可以用这个方法确定对称密钥。然后可以用这个密钥进行加密和解密。但是注意，这个密钥交换协议/算法只能用于密钥的交换，而不能进行消息的加密和解密。双方确定要用的密钥后，要使用其他对称密钥操作加密算法实际加密和解密消息。上过毕老师安全课的同学读到这里可能会笑了，这么简单的思想，毕老师上课早就讲过了，这篇文章写得有什么值得称道的。但是大家《密码学的新方向》读书笔记2016.0510不要忘了，这可是1976年，这个年代，随着计算机和通信技术的发展，用户对信息的安全存储、安全处理和安全传输的需求越来越迫切。特别地，随着Internet的广泛应用，以及个人通信、多媒体通信、办公自动化、电子邮件、电子自动转账支付系统和自动零售业务网的建立与实现，信息的安全保护问题就显得更加重要。而传统密码体制对于解决这一问题，则显得有些乏力。在传统密码体制（又称“对称密钥密码体制”）中，用于加密的密钥和用于解密的密钥完全相同。这种体制所使用的加密算法比较简单，而且高效快速、密钥简短、破译困难，但是存在着密钥传送和保管的问题。例如：甲方与乙方通讯，用同一个密钥加密与解密。首先，将密钥分发出去是一个难题，在不安全的网络上分发密钥显然是不合适的；另外，如果甲方和乙方之间任何一人将密钥泄露，那么大家都要重新启用新的密钥。基于这种时代背景，作者提出的公钥密码体制就显得弥足珍贵了，毕竟，划时代的事情可不是那么容易做到的。其实，文