密码学简介及初等数论在密码学中的重要应用

基本信息

书名:算法数论

作者:裴定一,祝跃飞

出版社：科学出版社有限责任公司

出版日期：2016-12-01

ISBN：9787030453327

字数：293000

页码：228

版次：31

装帧：平装

开本：16开

商品重量：

编辑推荐

内容提要

《算法数论（第二版）》论述了算法数论的基本内容，其中涉及同余式、二次剩余、特征、连分数、代数数域、椭圆曲线、素性检验、大整数因子分解算法、椭圆曲线上的离散对象、超椭圆曲线、格理论等分支，也介绍了这些知识在密码学中的一些应用目《算法数论（第二版）》的特点是内容涉及面广，在有限的篇幅内，包含了必要的预备知识和数学证明，尽可能形成一个比较完整的体系。

\begin{eqnarray}&\underline{\hspace{10cm}}&\\&\underline{\hspace{10cm}}\\&\underline{\hspace{10cm}}&\\&\underline{\hspace{10cm}}&\end{eqnarray}

密码学在现实生活中越来越重要，本文简单介绍了密码学与RSA公钥密码系统及初等数论在密码学中的重要应用，主要内容摘自《应用密码学》一书。

\qquad 早期的密码学研究密写和非法解密问题，至今已有几千年的历史。人类有记载的通信密码始于公元前400年。D.Kahn搜集整理两次世界大战的历史资料，出版的《破密者》一书中对那个年代密码学在军事、外交方面的辉煌成绩（如1940-1945年间英国成功破译德国的ENIGMA密码机报文，1940年美国成功解密日本的紫密机）有较为详细的介绍。在电报发明以后，商业方面对密码学的兴趣主要集中在密码本的编制上；到20世纪初集中在与机械和电动机械加密机的设计和制造上。信息技术的发展迅速改变了这一切，随着计算机和通信技术的迅猛发展，大量敏感信息要通过公共通信设施或计算机网络进行交换。Internet web的广泛应用大大促进了电子商务和电子政务。大量个人信息（如信用卡卡号、银行账号等）需要保密，密码学的应用已经不仅仅局限在政治、军事、外交等领域，它的商业和社会价值日益显著，与人们的日常生活愈加密切相关。

\qquad 密码学领域实际上已被当作应用数学和计算机科学的一个分支。数学理论在当前的密码学研究中发挥着重要作用，其中包括数论、群论、组合逻辑、复杂性理论、遍历理论及信息论。对于计算机科学家而言，密码学与操作系统、数据库、计算机网络联系非常紧密。密码学的理论和技术已经得到迅速的发展。

编辑推荐（1）以自底向上的方式介绍：从密码学到网络安全，再到案例研究。（2）涵盖了*新内容：IEEE 802.11安全、Elgamal加密、云安全以及Web服务安全。（3）对加密法、数字签名、SHA-3算法的介绍进行了改进。（4）通过案例研究，帮助读者掌握相关内容的实际应用。（5）全书提供了丰富的编程题、练习题、多项选择题、与案例研究，有利于加深读者对所学知识的理解和掌握：■ 150道编程题■ 160道练习题■ 170道多选题■ 530幅插图■ 10个案例研究内容简介（1）以自底向上的方式介绍：从密码学到网络安全，再到案例研究。 （2）涵盖了*新内容：IEEE 802.11安全、Elgamal加密、云安全以及Web服务安全。 （3）对加密法、数字签名、SHA-3算法的介绍进行了改进。 （4）通过案例研究，帮助读者掌握相关内容的实际应用。 （5）全书提供了丰富的编程题、练习题、多项选择题、与案例研究，有利于加深读者对所学知识的理解和掌握： ■ 150道编程题 ■ 160道练习题 ■ 170道多选题 ■ 530幅插图 ■ 10个案例研究

\qquad 密码学用于军事和外交方面保护通信信息已经有几千年的历史，早期密码学是一门艺术，是技巧和经验的综合体。1949年 C.E.Shannon发表文章”Communication Theory of Secrecy System“，使得密码学成为一门科学，该文把信息论引入密码学，用统计的观点对信息、密码源、接收密文进行数学描述和定量分析。同时他也提出设计密码的基本观点，它们构成”私钥密码学“的理论基础。Shannon在文章中引入不确定性、剩余度、唯一解距离作为安全性的测度，并假设敌手有无限计算能力能够充分利用信源的全部统计知识。如果对手有无限计算资源也不能攻破的密码系统称之为无条件保密的。如果对于每个明文M和密文C都有 P(M)=P(M|C) ，即发送M的概率和它在已知C的条件下M被发送的概率相同，那么截获密文C对确定明文毫无帮助，这时称该密码系统是完全保密的。Shannon证明了： \qquad

\qquad (1)在完全保密系统中，不同密钥的个数大于等于所有可能的明文数；

\qquad (2)在一个密码系统中明文数、密文数、密钥数都相等，则该密码系统完全保密的充要条件是一个密钥只加密一个明文（一次一密），而且所有密钥都是等概率的。

\qquad 1976年W.Diffie和M.E.Hellman发表”密码学的新方向“一文，开创了公钥密码学新纪元。它使得从发送端到接收端进行保密通信不再需要密钥传送，从而公钥密码学不仅可以用于保密，还可以用于认证。

\qquad 现代密码学的特点是：

\qquad (1)有坚实的理论基础，已经形成一门新的学科；

\qquad (2)对密码学公开地研究；

\qquad (3)应用于社会各个方面，如金融、商业等行业；

\qquad (4)破译密码系统归结为求解数学的难解问题。

\qquad 经过几百年的密码学研究积累了丰富的经验和成果，总结起来指导密码学研究和发展的几条经验是：

\qquad (1)不应该低估对手的能力；

\qquad (2)只有密码分析者才能评价一个密码体制的安全性。每个设计安全密码体制的机构也应该有破译”认为是安全的密码体制“的任务；

\qquad (3)对手知道所用的密码体制；

\qquad (4)表面上的复杂性可能是虚假的，虽然它们可能给密码编码者一种安全性的错觉；

\qquad (5)由于人自身的弱点，会发生密码错误和其他违反安全纪律的情况，判断一类方法的安全性时，必须考虑这一点。

内容简介

　　《初等数论及其应用（原书第6版）》是数论课程的经典教材，自出版以来，深受读者好评，被美国加州大学伯克利分校、伊利诺伊大学、得克萨斯大学等数百所名校采用。　　《初等数论及其应用（原书第6版）》以经典理论与现代应用相结合的方式介绍了初等数论的基本概念和方法，内容包括整除、同余、二次剩余、原根以及整数的阶的讨论和计算。　　《初等数论及其应用（原书第6版）》特色：　　经典理论与现代应用相结合。通过增强实例和练习，将数论的应用引入了更高的境界，同时更新并扩充了对密码学这一热点论题的讨论。　　内容与时俱进。不仅融合了新的研究成果和新的理论，而且还补充介绍了相关的人物传记和历史背景知识。　　习题安排别出心裁。书中提供三类习题：第一类是由易到难的普通习题，第二类是富有挑战的计算和研究题，第三类是程序设计题。这使得读者能够将数学理论与编程技巧实践联系起来。此外，本书在上一版的基础上对习题进行了大量更新和修订。

\qquad 1976年Diffie和Hellman的文章引入了公钥密码学的概念，它给出一种新的有创造性的密钥交换的方法。这种方法的安全性基于离散对数问题的难解性。虽然当时他们并没有具体实现这种公钥加密方案，但是想法非常清晰，引起了密码学界的广泛兴趣。1978年出现第一个RSA公钥加密和签名方案，它是基于大整数素因子分解难解问题。虽然20世纪80年代关于大整数素因子分解方法有很大进展，但是人们仍然认为RSA是安全的。1985年又出现一个基于离散对数问题的ElGamal公钥加密方案。

\qquad 公钥加密方案 E_e 和解密方案 D_d 中，对于每对加密密钥 e 和解密密钥 d ，其中加密密钥（公钥）公开为大家共享，而解密密钥（私钥）只为一个实体私有， A 和 B 要进行保密通信， A 使用 B 的公钥将明文加密得到的密文发送给 B ， B 使用自己的私钥将密文解密恢复成明文。如果从公钥计算私钥在计算上是不容易的，那么公钥加密方案是安全的。如果对手 C 伪装成 B ，把 B 的公钥 e_B 偷换成 C 的公钥 e_C ，那么 A 加密后发送给 B 的密文，对手 C 能顺利解密。这样对于 B 的公钥 e_B 必须实施数据源认证，以保证该公钥的真实性。若公钥加密方案是可逆的，即对所有消息 m ， D_d(E_e(m))=E_e(D_d(m)) ，那么解密方案 D_d 可以作为签名方案。

\qquad 公钥加密的优点：

\qquad （1）大型网络中每个用户需要的密钥数量少；

\qquad （2）对管理公钥的可信第三方的信任程度要求不高而且是离线的；

\qquad （3）只有私钥是保密的，而公钥只要保证它的真实性。

\qquad 公钥加密的缺点：

\qquad （1）多数公钥加密比对称密钥加密的速度要慢几个数量级；

\qquad （2）公钥加密方案的密钥长度比对称加密的密钥要长；

\qquad （3）公钥加密方案没有被证明是安全的。

\qquad 公钥密码的观点是Diffie和Hellman于1976年在他们的论文”密码学的新方向“一文中首次提出来的。他们指明了实现在某些已知的数学难解问题上建立密码的具体途径。随后Rivest，Shamir和Adleman于1977年提出了第一个比较完善的RSA公钥密码系统。这三位科学家荣获2002年度图灵奖，以表彰他们在算法方面的突出贡献。该算法允许不曾联系的两个个体间进行保密通信。RSA既可以用于保密也可以用于签名。目前该算法已广泛用于Internet和银行信用卡安全系统。

\qquad 公钥密码系统是计算复杂性理论发展的必然产物。私钥（对称）密码系统的缺陷之一是通信双方在进行保密通信之前需要通过安全通道传送密钥。这点在实际中是非常困难的。而公钥密码系统可使通信双方无须事先传送密钥就可以建立保密通信。公钥密码系统的出现为解决私钥密码系统的密钥分配问题开辟了一条宽广的道路。

\qquad 在公钥密码系统中每个实体都有自己的公钥和相应的私钥。在安全系统中已知公钥推算出私钥在计算上是困难的。公钥密码系统的加密变换和解密变换分别用 E 和 D 表示。任何实体 B 要向实体 A 发送信息 m 的步骤如下：

\qquad （1）实体 B 首先获得实体 A 的公钥 e_A 的拷贝（authentic copy）；

\qquad （2） 实体 B 计算密文 c=E_{e_A}(m) 并发送给实体 A ；

\qquad （3）实体 A 使用自己的私钥 d_A ，计算 m=D_{d_A}(c) 解密密文，恢复出明文 m 。

这里公钥不需要保密，但要保证它的真实性，即 e_A 确实是实体 A 掌握的私钥 d_A 所对应的公钥。提供真实的公钥比安全地分配密钥实现起来要容易得多。这是公钥密码系统的主要优点。

\qquad 公钥密码系统的主要目的是提供保密性，它不能提供数据源认证（data origin authentication）和数据完整性（data integrity）。数据源认证是指：指定的数据是在以前的某个时间确实是由真正的源创建的。数据完整性是指：真正的源创建该数据后经过传输或储存没有发生改变。数据源认证和数据完整性要由其它技术来提供（如消息认证码、数字签名）。

\qquad 从本质上来看，公钥密码比私钥密码（如DES、IDEA、RC5等）加密的速度要慢。粗略地说，公钥加密算法RSA硬件实现比分组加密算法DES硬件实现的速度慢1500倍，而软件实现的速度要慢100倍。通常公钥密码用在：

\qquad （1）传送密钥，以后用该密钥作为私钥密码系统的密钥来加密大量数据。

\qquad （2）在数据完整性和认证中使用。

\qquad （3）加密少量数据。

\qquad 公钥解密也可以提供认证保证（如：在实体认证协议、带认证的密钥建立协议等）。公钥加密中必须有办法让发送消息的人得到想要发送到的那个人的公钥的真实拷贝，否则就会受到伪装攻击。在实践中有很多方法分发真实的公钥，如：使用可信的公共文件，使用在线可信服务器，使用离线服务器和认证。

\qquad 从抽象的观点来看，公钥密码系统是一种单向陷门函数。我们说一个函数是单向函数（one way function）是指：对它的定义域中的任意元素都容易计算其函数值，反过来对值域中的几乎所有元素确定它的原像都是不可行的。如果掌握某些辅助信息就容易由值域元素确定它的原像，那么这种单向函数叫做单向陷门函数（trapdoor one way function）。这里辅助信息就是陷门。例如： p 和 q 是两个大素数， n=p\cdot q ， e 是正整数，则：\color{red}{\boxed{f:\mathbb{Z_n}\rightarrow\mathbb{Z_n},\qquad f(x)\equiv x^e (mod n)}} 是单向陷门函数，其陷门是 \color{red}{\boxed{d\equiv e^{-1}(mod \varphi(n))}}

编辑推荐　　数论经典入门教材*新版，面向非数学专业，讲解生动有趣，注重数学思维的培养

内容简介　　本书讲述了有关数论大量有趣的知识，以及数论的一般方法和应用，循序渐进地启发读者用数学方法思考问题，此外还介绍了目前数论研究的某些前沿课题。本书采用轻松的写作风格，引领读者进入美妙的数论世界，不断激发读者的好奇心，并通过一些精心设计的习题来培养读者的探索精神与创新能力。

\qquad RSA是使用最广泛的公钥密码系统，它可以用在保密性和数字签名上。1976年Diffie和Hellman提出公钥密码系统的思想，1977年由Rivest，Shamir和Adleman首次实现了著名的RSA密码系统，它的安全性基于大整数素因子分解的困难性上。

\qquad 下面主要介绍RSA加密/解密算法、实现过程及安全性分析、RSA算法实现时要注意的问题及有关算法（平方-乘积算法及素性测试算法）。

\qquad 每个实体有自己的公钥 (n,e) 及私钥 p,q,d ，其中 p,q 是两个大素数， n=p\cdot q ， e\cdot d\equiv1(\bmod \varphi(n)) ，显然 e 应该满足 gcd(e,\varphi(n))=1 。实体 B 加密消息 m ，将密文在公开信道上传送给实体 A ，实体 A 接到密文后对其解密，具体算法如下：

\qquad 加密算法：

\qquad 实体 B 做如下操作：

\qquad （1）得到实体 A 的真实公钥 (n,e) ；

\qquad （2）把消息表示成整数 m,0\leq m\leq n-1

\qquad （3）使用平方-乘积算法，计算 C=E_k(m)\equiv m^e\bmod n ；

\qquad （4）将密文 C 发送给实体 A 。

\qquad 解密算法：

\qquad 实体 A 接收到密文 C ，使用自己的私钥 d 计算 m=D_k(C)\equiv C^d\bmod n,m\in\mathbb{Z}_n

\qquad 下面证明：对任何 m\in\mathbb{Z}_n ，有 D_k(E_k(m))=m 。

\qquad 这里要证明 D_k(E_k(m))\equiv m^{ed}\bmod n\equiv m 。首先证明 m^{ed}\equiv m\bmod p 对 p|m ，显然有 m^{ed}\equiv m\equiv 0\bmod p 。当 gcd(m,p)=1 时，由Fermat定理知， m^{p-1}\equiv 1\bmod p ，从而有：

m^{ed}\equiv m\cdot (m^{p-1})^{\upsilon(q-1)}\equiv m\bmod p ，同理可以推出 m^{ed}\equiv m\bmod q 。最后得到 m^{ed}\equiv m\bmod n

\qquad 1、密钥生成：

\qquad 每个实体 A 建立自己的RSA公钥和相应的私钥：

\qquad （1）生成两个大的随机素数 p\text{和}q ， p\ne q 并且它们的位长大体相同（素数生成具体方法见 \S5.4 ）；

\qquad （2）计算 n=p\cdot q,\varphi(n)=(p-1)(q-1) ；

\qquad （3）选择随机数 e,0