当前位置：文档之家 › 第四章公开密钥密码体制

第四章公开密钥密码体制

  • 格式：ppt
  • 大小：746.00 KB
  • 文档页数：25

下载文档原格式

  / 25

合集下载

第4章公钥密码体制

第4章公钥密码体制

密钥
为公钥。 不再需要， 以n，e为公钥。私密钥为d。(p, q不再需要， 可以销毁。 可以销毁。)
RSA算法在计算上的可行性
加密和解密
无论是加密还是解密都需要计算某个整数的模n 整数次幂，即C=Me mod n、M=Cd mod n。但不 、 需要先求出整数的幂再对n取模，而可利用模运 算的性质： (a mod n) * (b mod n)= (a*b) mod n 对于Me mod n，可先求出M1 mod n，M2 mod n， M4 mod n……，再求Me mod n
RSA算法 RSA算法
RSA Algorithm
概况
MIT三位年轻数学家, 1979年发现了一种用数 论构造双钥的方法，称作MIT 体制 MIT体制 MIT 体制，后来被 广泛称之为RSA体制 RSA体制 RSA体制。 它既可用于加密、又可用于数字签字。 RSA算法的安全性基于数论中大整数分解的 困难性。 迄今为止理论上最为成熟完善的公钥密码体 制，该体制已得到广泛的应用。
公钥密码体制有4个组成部分
明文：算法的输入，它们是可读信息或数据，用M 表示； 密文：算法的输出。依赖于明文和密钥，对给定的 消息，不同的密钥产生密文不同。用E表示； 公钥和私钥：算法的输入。这对密钥中一个用于加 密，为Ke，此密钥公开；一个用于解密，为Kd，此 密钥保密。加密算法执行的变换依赖于密钥； 加密、解密算法
选p=7，q=17。 求n=p×q=119，φ(n)=(p-1)(q-1)=96。 取e=5，满足1<e<φ(n)，且gcd(φ(n),e)=1。确 定满足d·e=1 mod 96且小于96的d，因为 77×5=385=4×96+1，所以d为77。 因此公开钥为{5，119}，秘密钥为{77，119}。 设明文m=19，则由加密过程得密文为 C=195 mod 119≡2476099 mod 119=66 解密为6677mod 119=19

网络安全技术 第4章

网络安全技术 第4章

对称密钥密码体制（1）

对称密码体制是从传统的简单换位发展而来的。其主 要特点是：加解密双方在加解密过程中要使用完全相 同或本质上等同（即从其中一个容易推出另一个）的 密钥，即加密密钥与解密密钥是相同的。所以称为传 统密码体制或常规密钥密码体制，也可称之为私钥、 单钥或对称密码体制。其通信模型如图4.2所示。
本章主要内容
1 2 3 4 5

密码技术概述 加密方法 密钥与密码破译方法 常用信息加密技术介绍 数据压缩
4.1 密码技术概述

密码技术包括密码算法设计、密码分析、安全 协议、身份认证、消息确认、数字签名、密钥 管理、密钥托管等。可以说密码技术是保护大 型通信网络上传输信息的惟一实现手段，是保 障信息安全的核心技术。它不仅能够保证机密 性信息的加密，而且能完成数字签名、身份验 证、系统安全等功能。所以，使用密码技术不 仅可以保证信息的机密性，而且可以保证信息 的完整性和准确性，防止信息被篡改、伪造和 假冒。
三种加密方式



链路加密方式：把网络上传输的数据报文的每一位进行加密。不但对数 据报文正文加密，而且把路由信息、校验和等控制信息全部加密。所以， 当数据报文传输到某个中间节点时，必须被解密以获得路由信息和校验 和，进行路由选择、差错检测，然后再被加密，发送给下一个节点，直 到数据报文到达目的节点为止。目前一般网络通信安全主要采这种方式。 节点对节点加密方式：为了解决在节点中数据是明文的缺点，在中间节 点里装有用于加、解密的保护装置，即由这个装置来完成一个密钥向另 一个密钥的变换。因而，除了在保护装置里，即使在节点内也不会出现 明文。但是这种方式和链路加密方式一样，有一个共同的缺点：需要目 前的公共网络提供者配合，修改他们的交换节点，增加安全单元或保护 装置。 端对端加密方式：为了解决链路加密方式和节点对节点加密方式的不足， 人们提出了端对端加密方式，也称面向协议加密方式。在这种方式中， 由发送方加密的数据在没有到达最终目的地——接受节点之前不被解密。 加密解密只是在源节点和目的节点进行。因此，这种方式可以实现按各 通信对象的要求改变加密密钥以及按应用程序进行密钥管理等，而且采 用此方式可以解决文件加密问题。这一方法的优点是：网络上的每个用 户可有不同的加密关键词，并且网络本身不需增添任何专门的加密设备； 缺点是每个系统必须有一个加密设备和相应的软件（管理加密关键词） 或者每个系统必须自己完成加密工作，当数据传输率是按兆位/秒的单位 计算时，加密任务的计算量是很大的。

信息安全概论课后答案

信息安全概论课后答案

四45五3六57十4十一34十二47没做“信息安全理论与技术"习题及答案教材:《信息安全概论》段云所，魏仕民，唐礼勇，陈钟，高等教育出版社第一章概述（习题一,p11)1.信息安全的目标是什么?答:信息安全的目标是保护信息的机密性、完整性、抗否认性和可用性；也有观点认为是机密性、完整性和可用性，即CIA(Confidentiality，Integrity，Availability)。

机密性（Confidentiality)是指保证信息不被非授权访问;即使非授权用户得到信息也无法知晓信息内容，因而不能使用完整性(Integrity）是指维护信息的一致性，即信息在生成、传输、存储和使用过程中不应发生人为或非人为的非授权簒改。

抗否认性（Non—repudiation)是指能保障用户无法在事后否认曾经对信息进行的生成、签发、接收等行为,是针对通信各方信息真实同一性的安全要求.可用性(Availability）是指保障信息资源随时可提供服务的特性.即授权用户根据需要可以随时访问所需信息。

2.简述信息安全的学科体系。

解：信息安全是一门交叉学科,涉及多方面的理论和应用知识.除了数学、通信、计算机等自然科学外，还涉及法律、心理学等社会科学.信息安全研究大致可以分为基础理论研究、应用技术研究、安全管理研究等。

信息安全研究包括密码研究、安全理论研究；应用技术研究包括安全实现技术、安全平台技术研究；安全管理研究包括安全标准、安全策略、安全测评等.3. 信息安全的理论、技术和应用是什么关系？如何体现？答：信息安全理论为信息安全技术和应用提供理论依据。

信息安全技术是信息安全理论的体现,并为信息安全应用提供技术依据。

信息安全应用是信息安全理论和技术的具体实践.它们之间的关系通过安全平台和安全管理来体现。

安全理论的研究成果为建设安全平台提供理论依据.安全技术的研究成果直接为平台安全防护和检测提供技术依据.平台安全不仅涉及物理安全、网络安全、系统安全、数据安全和边界安全，还包括用户行为的安全,安全管理包括安全标准、安全策略、安全测评等。

第04章 密码学原理

第04章 密码学原理

57 10 63 14
49 2 55 6
41 59 47 61
33 51 39 53
25 43 31 45
17 35 23 37
9 27 15 29
1 19 7 21
58 11 62 13
50 3 54 5
42 60 46 28
34 52 38 20
26 44 30 12
18 36 22 4
第4章 网络安全密码学基本理论
密码学是一门研究信息安全保护的科学。它最早可追溯到 几千年前，主要用于军事和外交通信。随着网络与信息技术的 发展，密码学的应用不再局限于军事、政治、外交领域，而是 逐步应用于社会各个领域，例如电子商务、个人安全通信、网 络安全管理等。 密码学的发展可大致划分为四个阶段：
第4章 网络安全密码学基本理论 第一个阶段：从古代到1949年。该时期的密码学没有数学
第4章 网络安全密码学基本理论 4.1.2 密码学基本概念
密码学，是保护明文的秘密以防止攻击者获知的科学。
密码分，析学是在不知道密钥的情况下识别出明文的科学。
明文，是指需要采用密码技术进行保护的消息。
密文，是指用密码技术处理“明文”后的结果，通常称为加
密消息。
第4章 网络安全密码学基本理论
将明文变换成密文的过程称作加密(encryption)。 其逆过程，即由密文恢复出原明文的过程称作解密
道交换密钥，以保证发送消息或接收消息时能够有供使用的密钥。
第4章 网络安全密码学基本理论
加密
解密
明文
密文
密文
明文
图4-1 私钥密码体制原理示意图
第4章 网络安全密码学基本理论 密钥分配和管理是极为重要的问题。 为了保证加密消息的安全，密钥分配必须使用安全途径， 例如由专门人员负责护送密钥给接收者。 同时，消息发送方和接收方都需要安全保管密钥，防止非 法用户读取。 另外的问题是密钥量。由于加密和解密使用同一个密钥， 因此，与不同的接收者进行加密通信时，需要有几个不同的密

第四章公钥密码体制

第四章公钥密码体制

RSA公钥密码算法（续）
如果A要发送信息M给B，A和B之间用以 下方式进行通信： 计算密文 C = EK p (M ) →发送C给B→从A 接收C→计算明文 M = DKs (C) . 一般要求p，q为安全质数，现在商用的 安全要求为n的长度不少于1024位 。
B
B
RSA公钥密码算法（续）
算法的安全性分析 1. 如果密码分析者能分解 n 的因子 p 和 q ，他就可以 求出φ (n ) 和解密的密钥 d ，从而能破译RSA，因此破 译RSA不可能比因子分解难题更困难。 2. 如果密码分析者能够不对 n 进行因子分解而求得，则 可以根据 de ≡ 1 mod φ (n ) 求得解密密钥 d ，从而破译RSA。因为 2 p + q = n − φ (n ) + 1 p − q = ( p + q) − 4n 所以知道φ (n ) 和 n 就可以容易地求得 p 和 q ，从而成 功分解 n ，因此，不对 n 进行因子分解而直接计算 φ (n ) 并不比对 n 进行因子分解更容易。
椭圆曲线算法
1985年Koblitz和Miller提出在密码学中应用椭 圆曲线的思想，使其成为构造公开密钥密码系 统的一个有利工具。其安全性是基于椭圆曲线 上的离散对数计算的困难性。 优点：椭圆曲线上离散对数的计算要比有限域 上离散对数的计算更困难。与RSA相比，椭圆 曲线密码体制能用较短的密钥达到较强的安全 性，这样实现上能节省系统资源。
RSA公钥密码算法
RSA是Rivet，Shamir和Adleman于1978年在美 国麻省理工学院研制出来的，它是一种比较典 型的公开密钥加密算法。 基础 大数分解和素性检测——将两个大素数相乘在 计算上很容易实现，但将该乘积分解为两个大 素数因子的计算量是相当巨大的，以至于在实 际计算中是不能实现的。

现现代密码学 8讲RSA

现现代密码学 8讲RSA

m=D (c)=DSKB (EPKB(m))
•从公开钥PKB和密文c要推出明文m或解密钥SKB在计算上是
不可行的。
•由于任一用户都可用用户B的公开钥PKB 向他发送机密消息，
因而密文c不具有认证性。
2019/9/23
4
公钥密码认证体制
发送者A m
c 加密算法
解密算法
密码分析员
SK’A m 接收者B
若计算函数时间是an的倍数，则为不可能做到 的。
2019/9/23
8
陷门单向函数
单向函数是求逆困难的函数，而单向陷门函 数(Trapdoor one-way function)，是在不知 陷门信息下求逆困难的函数，当知道陷门信 息后，求逆是易于实现的。
陷门单向函数是一族可逆函数fk，满足
mk(n)≡1 mod q，
例题
① 选p=7，q=17。 ② 求n=p×q=119，φ(n)=(p-1)(q-1)=96。 ③ 取e=5，满足1<e<φ(n)，且gcd(φ(n),e)=1。 ④ 确定满足d·e=1 mod 96且小于96的d，因为
77×5=385=4×96+1，所以d为77 ⑤ 公开钥为{5，119}，秘密钥为{77}。 ⑥ 设明文m=19，则由加密过程得密文为 c≡195 mod 119≡2476099 mod 119≡66 ⑦ 解密为6677mod 119≡19
收方B用自己的秘密钥对密文c解密在计算上是容易的。
敌手由密文c和B的公开密钥恢复明文在计算上是不可 行的。
敌手由密文c和B的公开密钥恢复秘密密钥在计算上是 不可行的
加解密次序可换，即EPKB[DSKB(m)]=DSKB[EPKB(m)] ,不 是对任何算法都做此要求。

信息安全概论第四章公钥密码体制

信息安全概论第四章公钥密码体制

14
Diffie-Hellman密钥交换算法 密钥交换算法
Diffie和Hellman在其里程碑意义的文章中， 虽然给出了密码的思想，但是没有给出真正意 义上的公钥密码实例，也既没能找出一个真正 带陷门的单向函数 然而，他们给出单向函数的实例，并且基于此 提出Diffie-Hellman密钥交换算法
13
常用的公开密钥算法
公钥算法的种类很多，具有代表性的三种密码： 公钥算法的种类很多，具有代表性的三种密码： 基于整数分解难题（IFP）的算法体制 基于整数分解难题（IFP）的算法体制(RSA) 基于离散对数难题（DLP）算法体制 基于离散对数难题（DLP）算法体制(ElGamal) 基于椭圆曲线离散对数难题（ ECDLP ） 的算法体制 基于椭圆曲线离散对数难题 （ ECDLP） (ECC)
3
4.1 公钥密码体制的基本原理
对称算法的不足
（1）密钥管理量的困难 传统密钥管理：两两分别用一个密钥时， 传统密钥管理：两两分别用一个密钥时，则n个用户需 C(n,2)=n(n-1)/2个密钥 当用户量增大时， 个密钥， 要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空 间急剧增大。 间急剧增大。如: n=100 时， C(100,2)=4,995 n=5000时 n=5000时， C(5000,2)=12,497,500 （2）密钥必须通过某一信道协商，对这个信道的安全 密钥必须通过某一信道协商， 性的要求比正常的传送消息的信道的安全性要高
7
公开密钥密码的重要特性
฀
加密与解密由不同的密钥完成 Y: X: Y = EKU(X) X = DKR(Y) = DKR(EKU(X))
加密: X฀ 解密: Y฀
฀ 知道加密算法,从加密密钥得到解密密钥在计算上 , 是不可行的 ฀ 两个密钥中任何一个都可以用作加密而另一个用 作解密(不是必须的) X = DKR(EKU(X))

非对称密码体制-第四章网络09

非对称密码体制-第四章网络09

11
4.2.1 RSA算法 算法
2、加密过程 、 的公钥： （1）在公钥库中查得用户 的公钥：PU={e, n}； ）在公钥库中查得用户U的公钥 ； 使得0≤mi<n，i=1， （2）将明文分组 ）将明文分组m=m1m2…mr，使得 ， ， 2，… ，r； ， ； （3）对明文分组 i作加密变换： ）对明文分组m 作加密变换： ci=E(mi) ≡ mie mod n， i=1，2，… ，r n， i=1，2， 传送给用户U。 （4）将密文 1 c2…cr传送给用户 。 ）将密文c 3、解密过程 、 （1）先对每组密文做解密变换： ）先对每组密文做解密变换： mi=D(ci) ≡cid mod n （2）合并分组得到明文 ）合并分组得到明文m=m1m2…mr。
12
图4-3 RSA算法 算法
选取大素数p和q 令n=p*q,计算φ(n)
随机选取整数e 由e*d≡1(mod φ(n))计算d
将（n，e）作为公钥公开 将（p,q，d）作为私钥保密
用公钥加密 ci=E(mi)≡(mie mod n)
用私钥解密 mi=D(ci)≡(cid mod n)
13
【例4-1】选择素数： p=47 和 q=71，求出RSA 】选择素数： ，ห้องสมุดไป่ตู้出 算法的公钥和私钥。 算法的公钥和私钥。
2
4.1 公钥密码体制的基本概念
Diffie和Hellmna于1976年在《密码学的新方向》中 和 年在《 于 年在 密码学的新方向》 首次提出了公钥密码的观点， 首次提出了公钥密码的观点，即为每个用户分配两 个相互匹配又相互独立的密钥，其中： 匹配又相互独立的密钥 个相互匹配又相互独立的密钥，其中： 一个密钥被公开，称为公开密钥（公钥）， ），用于 一个密钥被公开，称为公开密钥（公钥），用于 加密， 加密， 另一个密钥被保密，称为私有密钥（私钥）， ），用 另一个密钥被保密，称为私有密钥（私钥），用 解密。 于解密。 所有用户的公钥均登记在类似电话号码簿的密钥本 当要给用户A发送加密信息时 发送加密信息时， 上。当要给用户 发送加密信息时，需要在密码本上 查找A用户的公钥 然后加密信息，并发给用户A。 用户的公钥， 查找 用户的公钥，然后加密信息，并发给用户 。 用户A接收到密文之后 接收到密文之后， 用户 接收到密文之后，用自己的私钥进行解密即可 得到明文。 得到明文。 1977年由 年由Rivest（李维斯特）、 ）、Shamir（沙米尔） 年由 （李维斯特）、 （沙米尔） 和Adleman（埃德曼）共同提出了第一个公钥密码 （埃德曼） 算法（ 密码体制）， 算法（即RSA密码体制），是公钥密码中最优秀的 密码体制），是公钥密码中最优秀的 加密算法，被誉为密码学发展史上的里程碑之一。 里程碑之一 加密算法，被誉为密码学发展史上的里程碑之一。 此后， 此后，人们基于不同的计算问题提出了大量的公钥 密码算法。 密码算法。

现代密码学杨波课后习题讲解

现代密码学杨波课后习题讲解
n n ， (abmod 2 ) (abdiv2 ) ( ab mod 2 ) ( abdiv 2 ) n ab mod (2 1) n n n n n ( abmod 2 ) ( abdiv 2 ) ， ( ab mod 2 ) ( abdiv 2 ) 2 1
习题
习题
3.设 n=4,n=f(a1,a2,a3,a4)=a1⊕a4⊕1⊕a2a3，初始状态为 (a1,a2,a3,a4)=(1,1,0,1)，求此非线性反馈移位寄存器的输出 序列及周期。
解：列出该非线性反馈移位寄存器 的状态列表和输出列（如右图）： a5 111 0 1
a6 111 0 1
n n
注意：(ab mod 2n)相当于 ab 的 n 个有效最低位，(ab div 2n) 是 ab 右移 n 位。 IDEA：明文、分组、密钥、8轮迭代（不是传统的feistel）、 输出变换
习题
习题
习题
第四章 公钥密码
习题
1.证明以下关系： (1) (a mod n) (b mod n), 则a b mod n (2) a b mod n, 则b a mod n (3) a b mod n, b c mod n, 则a c mod n 解：（1）设 a mod n ra , b mod n rb ，由题意得 ra rb ，且存在 整数 j , k ，使得 a jn ra , b kn rb , 可得 a b ( j k )n, 即n | (a b), 证得 a b mod n
1
1 1 1 1 0 1 c3c2c1 010 101 1 1 0
由此可得密钥流的递推关系为：

信息安全概论课后答案

信息安全概论课后答案

四45五3六57十4十一34十二47没做“信息安全理论与技术”习题及答案教材：《信息安全概论》段云所，魏仕民，唐礼勇，陈钟，高等教育出版社第一章概述（习题一，p11）1.信息安全的目标是什么？答：信息安全的目标是保护信息的机密性、完整性、抗否认性和可用性；也有观点认为是机密性、完整性和可用性，即CIA(Confidentiality,Integrity,Availability)。

机密性（Confidentiality）是指保证信息不被非授权访问；即使非授权用户得到信息也无法知晓信息内容，因而不能使用完整性（Integrity）是指维护信息的一致性，即信息在生成、传输、存储和使用过程中不应发生人为或非人为的非授权簒改。

抗否认性（Non-repudiation）是指能保障用户无法在事后否认曾经对信息进行的生成、签发、接收等行为，是针对通信各方信息真实同一性的安全要求。

可用性（Availability）是指保障信息资源随时可提供服务的特性。

即授权用户根据需要可以随时访问所需信息。

2.简述信息安全的学科体系。

解：信息安全是一门交叉学科，涉及多方面的理论和应用知识。

除了数学、通信、计算机等自然科学外，还涉及法律、心理学等社会科学。

信息安全研究大致可以分为基础理论研究、应用技术研究、安全管理研究等。

信息安全研究包括密码研究、安全理论研究；应用技术研究包括安全实现技术、安全平台技术研究；安全管理研究包括安全标准、安全策略、安全测评等。

3. 信息安全的理论、技术和应用是什么关系？如何体现？答：信息安全理论为信息安全技术和应用提供理论依据。

信息安全技术是信息安全理论的体现，并为信息安全应用提供技术依据。

信息安全应用是信息安全理论和技术的具体实践。

它们之间的关系通过安全平台和安全管理来体现。

安全理论的研究成果为建设安全平台提供理论依据。

安全技术的研究成果直接为平台安全防护和检测提供技术依据。

平台安全不仅涉及物理安全、网络安全、系统安全、数据安全和边界安全，还包括用户行为的安全，安全管理包括安全标准、安全策略、安全测评等。

05_密码学基础(四)_公开密钥密码算法

05_密码学基础(四)_公开密钥密码算法

密钥分配
使用对称密码算法 保密通信双方需共享密钥：A&B，B&C，C&A N个用户集需要N(N-1)/2个共享密钥 共享密钥需要经常更换，更换方式有

A选择密钥并手工传递给B 第三方C选择密钥分别手工传递给A,B 用A,B原有共享密钥传送新密钥 与A,B分别有共享密钥的第三方C传送新密钥给A和/ 或B
数论简介
欧拉定理 表述1： 将Z/(n）表示为 Zn，其中n=pq; p,q为素数且相异。 若Z*n={g∈ Zn|gcd(g,n)=1}，易见Z*n为(n)阶的乘 法群，且有 g(n)1(mod n)，而 (n)=(p-1)(q-1)。 表述2： 若整数g和n互素，则g(n) ≡1(mod n)；其中(n)为比 n小，但与n互素的正整数个数, 称为(n)的欧拉函数 表述3： 给定两个素数p和q，以及两个整数m、n，使得n=pq ，且0<m<n，对于任意整数k下列关系成立，
公钥密码学的历史


76年Diffie和Hellman发表了“密码学的新方向 ”，奠定了公钥密码学的基础 公钥技术是二十世纪最伟大的思想之一

改变了密钥分发的方式 可以广泛用于数字签名和身份认证服务

78年，RSA算法 PKI
公钥加密模型
公开密钥的加密
公开密钥密码的重要特性 加密与解密由不同的密钥完成 加密: X –>Y：Y = EKU(X) 解密: Y –>X: X = DKR(Y) = DKR(EKU(X)) 知道加密算法，从加密密钥得到解密密钥在计算上是 不可行的； 两个密钥中任何一个都可以用作加密而另一个用作解 密 X = DKR(EKU(X)) = EKU(DKR(X))

第4讲 公钥密码体制

第4讲 公钥密码体制

3.优点

密钥管理
加密密钥是公开的；
解密密钥需要妥善保存； 在当今具有用户量大、消息发送方与接收方具有明显的信息不对称
特点的应用环境中表现出了令人乐观的前景。
新用户的增加只需要产生一对公共/私有密钥。

数字签名和认证
只有解密密钥能解密，只有正确的接收者才拥有解密密钥。
缺点：公共密钥系统的主要弱点是加密和解密速度慢。
欧拉定理
如a 和 n 是互素的整数，则有：
a f( n ) 1 mod n
等价形式：
a
f ( n) +1
a mod n
欧拉定理推论： 有两个素数 p 和 q, 令 n = pq , 对任意整数 t 和a (0<a<n), 有下列等式成立：
a tφ(n) +1 = a mod n
其中：φ(n) = (p-1)(q-1)。

( a 1 , a 2 , , a n )
。
同余式 ：设n是一个正整数，a , b Z 如果 a mod n b mod n， 则称a和b模n同余，记作：a b (mod
元：设a Z ，如果存在
n
x Z n 满足 x a 0 (mod n )，则称
法；
目前被认为安全的Knapsack型公钥密码算法Chor-Rivest。

Diffie-Hellman、RSA和DSA是三种最常用的公钥算法。
Diffie-Hellman仅适用于密钥交换。 RSA算法适用于数字签名和数据加密。 DSA算法仅适用于数字签名。

ECC具有发展前途，可用于密钥交换、数字签名、数据加密。
扩展的欧几里德算法举例

应用密码学第4章序列密码体制

应用密码学第4章序列密码体制

第4章 序列密码体制
发生器的周期必须非常长，要比密钥更换之前发生器所
能输出的位的长度还要长得多。如果其周期比明文还要短， 那么明文的不同部分将用同样的加密——这是一个严重的弱 点。如果密码分析者熟悉这样的一批明文，他就可以恢复出 密钥流，然后恢复出更多的明文。即使分析者仅有密文，他 也可以用同一密钥流加密的不同部分密文相异或得到明文跟 明文的异或。这只是一个有非常长密钥的单一异或运算罢了。 周期需要多长取决于应用。用于加密连续T1连接通信 的密钥发生器每天加密237比特。那么它的周期应该比这个 数大几个数量级，尽管密钥每天都要更换。如果周期足够长， 你仅仅需要每周甚至每月才更换密钥一次。
第4章 序列密码体制
第4章 序列密码体制
4.1 密码学中的随机数 4.2 序列密码的概念及模型 4.3 线性反馈移位寄存器 4.4 非线性序列简介
4.5 常用的序列密码 密码学中的随机数
为什么在密码学中要讨论随机数的产生？因为许多密码 系统的安全性都依赖于随机数的生成，例如DES加密算法中 的密钥，RSA加密和数字签名中的素数。所有这些方案都需 要足够长度并且要“随机”的数，即使得任何特定值被选中
第4章 序列密码体制
4.1.4 伪随机数的评价标准
如果一序列产生器是伪随机的，它应有下面的性质： （1）看起来是随机的，表明它可以通过所有随机性统计
检验。
现在有许多统计测试。它们采用了各种形式，但共同思路 是它们全都以统计方式检查来自发生器的数据流，尝试发现数
据是否是随机的。
确保数据流随机性的最广为人知的测试套件就是 GeorgeMarsaglia的DIEHARD软件包（请参阅 /pub/diehard/）。另一个适合此类测试的 合理软件包是pLab（请参阅http://random.mat.sbg.ac.at/tests/）。

网络安全 公钥密码系统

网络安全 公钥密码系统

Alice 产生随机数 x 计算 X＝a x mod p
Bob
X
计算 k＝Y x mod p
Y
产生随机数 y 计算 Y＝a y mod p 计算 k ′＝X y mod p
Diffie-Hellman密钥交换，第一个公 钥算法，但只能用于密钥交换
第4章 公钥密码系统
4.1 RSA密码系统 密码系统
– 多用户网络中的密钥数目膨胀问题，共需协商和保存n(n-1)/2个密钥 – 密钥分发问题，如何通过不安全线路传输初始化密钥
公钥密码系统基于陷门单向函数：在不知道陷门信息（某些保密信 息）情况下求逆困难，而在知道陷门信息时易于求逆的函数。
第4章 公钥密码系统 基于对称密码学的DES的ECB(Electronic Codebook)模式 • 将明文M分成64位的分组pi • 对各分组用给定的密钥K进行加密，得密文分组：ci=DESK(pi) • 将各密文分组按顺序连接起来即得到明文的密文 • 为拥有共享密钥的双方在通信中加/解密数据
第4章 公钥密码系统
4.2 Diffie-Hellman密钥交换 密钥交换
4.2.1 Diffie-Hellman算法 Diffie-Hellman算法： 1976年，第一个公开密钥算法，用于 密钥分配，其安全性基于计算离散对数的困难性。 离散对数： 素数p的本原根(Primitive Root)：能生成1～p−1所有数的一个 数，如果a为p的本原根，则a mod p，a2 mod p，…，ap−1 mod p两 两互不相同，构成1～p−1的全体数的一个排列。 对于任意数b及素数p的本原根a，可以找到一个惟一的指数i， 满足： b = ai mod p, 0≤i≤p−1 称指数i为以a为底模p的b的离散对数，i = logab( mod p) 。 由a、i、p计算b，简单；由a、 b 、p计算i，极其困难。

公开密钥密码体系

公开密钥密码体系

公开密钥密码体系
在公开密钥密码体制中，加密密钥（即公开密钥）PK是公开信息，而解密密钥（即秘密密钥）SK是需要保密的。

加密算法E和解密算法D也都是公开的。

虽然秘密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK。

与传统的加密方法不同，该技术采用两个不同的密钥来对信息加密和解密，它也称为非对称式加密方法。

每个用户有一个对外公开的加密算法E和对外保密的解密算法D，它们须满足条件：
1、D是E的逆，即D[E（X）]=X。

2、E和D都容易计算。

3、由E出发去求解D十分困难。

从上述条件可看出，公开密钥密码体制下，加密密钥不等于解密密钥。

加密密钥可对外公开，使任何用户都可将传送给此用户的信息用公开密钥加密发送，而该用户唯一保存的私人密钥是保密的，也只有它能将密文复原、解密。

虽然解密密钥理论上可由加密密钥推算出来，但这种算法设计在实际上是不可能的，或者虽然能够推算出，但要花费很长的时间而成为不可行的。

所以将加密密钥公开也不会危害密钥的安全。

数学上的单向陷门函数的特点是一个方向求值很容易，但其逆向计算却很困难。

许多形式为Y=f（x）的函数，对于给定的自变量x值，很容易计算出函数Y的值；而由给定的Y值，在很多情况下依照函数关系f(x）计算x值十分困难。

例如，两个大素数p和q相乘得到乘积n比较容易计算，但从它们的乘积n分解为两个大素
数p和q则十分困难。

如果n为足够大，当前的算法不可能在有效的时间内实现。

公开密钥密码

公开密钥密码
密保真。
二、公开密钥密码的基本工作方式
• 设 M为明文，C为密文，E为公开密钥密
码的加密算法，D为解密算法，Ke 为公开
的加密钥，Kd为保密的解密钥，每个用户
都分配一对密钥，而且将所有用户的公开
的加密钥Ke存入共享的密钥库PKDB。
二、公开密钥密码的基本工作方式
1、确保数据秘密性：A
M
B
发方：
①A首先查PKDB，查到B的公开的加密钥
预处理和调整运算。一次性计算Y=AB mod
n并不划算。
• 适合：RSA等密码中多次的模乘计算。
三、RSA公开密钥密码
4、对RSA公开密钥密码的主要攻击
穷举攻击：穷举所有可能的私钥
数学攻击：

因式分解攻击

参数的选取不当造成的攻击

选择密文攻击

共模攻击

小指数攻击
计时攻击
RSA公钥加密的攻击—因子分解

Wiener在1990年指出，当d<n1/4时，从e
和n可以很容易求出密钥d
RSA公钥加密的攻击—计时攻击

思想：利用指数中某一位为0或者为1时，
硬件加密速度不同
四、ELGamal公钥密码
1、基本情况：
①ELGamal密码是除了RSA密码之外最有代表
性的公开密钥密码。
②RSA密码建立在大合数分解的困难性之上。
于是有，M φ(q) ＝1 mod q 。
进一步有，M t(p-1)φ(q) ＝1 mod q。
因为q是素数，φ(q)＝（q-1），所以t(p-1)φ(q)
＝tφ(n)，所以有
M tφ(n) ＝1 mod q。
三、RSA公开密钥密码

第四章-公钥密码体制

第四章-公钥密码体制
(p-1)! = 12…(p-1) [(a mod p)(2a mod p)…((p-1)a mod p)] mod p [a2a…(p-1)a] mod p [ap-1(p-1)!] mod p 注意到(p-1)!与p互素,因此定理成立.
• 推论: p素数,a是任意整数,则: ap a mod p
– M kφ(n)+1=M mod n
RSA算法举例（1）
p = 53，q = 61，n = pq = 3233， φ(n)＝52x60 = 3120 令d = 791，则e = 71 令m = RE NA IS SA NC E 即m = 1704 1300 0818 1800 1302 0426 170471 mod 3233 = 3106，…， C = 3106 0100 0931 2691 1984 2927
欧拉定理
• 证明： • R={x1,x2,…,x(n)}为所有小于n且与n互素的正整数,考虑集 合 • S={(ax1mod n), (ax2mod n),…, (ax(n) mod n)} • (aximod n)与n互素 • (aximod n)两两不等: • (aximod n) = (axjmod n) ximod n = xjmod n • S有(n)个元素 • 故S也是所有小于n且与n互素的正整数,因此S=R,从而 xi=(aximod n)((axi)) mod n • (a(n) xi) mod n • 注意到xi 与n互素,从而得到结论.
费马(Fermat)定理
• 若p是素数，a是正整数，且gcd(a,p)=1，则ap1≡1mod p • 证明：考虑集合{1,2,…,p-1},对每个数乘以a,得到 集合{a mod p,2a mod p,…,(p-1)a mod p},对于p, 后者两两不同且都在1与p-1之间,因此两个集合相 同,于是:
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

单向函数的例子
例1 令f为n阶多项式 y＝f(x)＝x n + an-1 xn-1 + …+ a1 x + a0 mod p 例2 求离散对数问题——EIG
amal体制的数学基础
y＝gx mod p (素数p、q，p-1 | q，整数g，1<g<p-1) 例3 因子分解问题 ————RSA体制的理论基础 例4 背包问题(Knapsack Problem)——背包体制的理论基钥少，便于管理。 ② 密钥分配简单。 ③ 可以实现数字签名。 （2）缺点：加密、解密处理速度较慢；密钥位数要求多。
图1.3 对称密码模型
图1.4 非对称密码模型
§2 单向函数与单向陷门函数
定义1 单向函数（OneFunction） 定义1：单向函数（One-way Function）
第4章 公开密钥密码体制
Asymmetric Encryption
第4章 公开密钥密码体制
§1 非对称密码体制特点 §2 单向函数与单向陷门函数 §3 公开密钥算法RSA §4 其他公开密钥密码体制
公开密钥密码算法的特征
（1）非对称性 非对称性：DSK(EPK(m))=m，但DPK(EPK(m))≠m 非对称性 （2）可交换性 可交换性：DPK(ESK(m))=m 可交换性 （3）PK和SK容易在计算机上成对生成，但不能用已知的PK导出SK。 （4）密码安全性依赖算法和SK。
一“可逆”函数F若满足下列二条件，则F称为单向陷门函数。
∈ （1）对于任x F定义域，可以很容易算出F(x)＝y。
（2）对于几乎所有属于F值域的任一y，则在计算上除非获得 陷门，否则不可能求出x，使得x＝F-1(y)，F-1(y)为F的反函数。但 若有一额外数据z（称为陷门），则可以很容易求出x＝F-1(y)。
Euler定理 Euler定理
若a和m互素，则 a ( m ) ≡ 1(mod m)
R、A、S
RSA体制 体制
（1） 密钥生成 ① ② ③ 选取两个保密的大素数p 选取两个保密的大素数p和q 计算n 计算n＝p×q，n公开 随机选取一整数e 满足gcd（ 随机选取一整数e，满足gcd（e，ψ(n)）＝1，e公开 gcd ψ(n)）＝1 ）＝ 计算d，满足 ≡1 ≡1（ ψ(n)）， ），d 计算 ，满足ed≡1（mod ψ(n)），d保密 （2）加密过程 ① ② ③ 将明文分组。 将明文分组。 加密变换： 加密变换：
C i ≡ M ie mod n
将密文组连缀并发送出去： 将密文组连缀并发送出去：C＝C1C2…Ci.… C
（3） 解密过程 解密变换： ① 解密变换：
②
M i ≡ C id mod n
将明文组合并： 将明文组合并：M＝M1M2…Mi.… M
一函数f 若满足下列二条件，则f 称为单向函数。 （1）对于任x f 定义域，可以很容易算出f (x)＝y。 ∈ （2）对于几乎所有(Almost All)属于f 值域的任一y，则在计算 上不可能(Computationally Infeasible)求出x使得 y＝f -1（x）。
定义2 单向陷门函数（OneFunction） 定义2：单向陷门函数（One-way Trapdoor Function）
n
s＝
∑x b
i =1
i i
已给有限个自然数序列集合B＝(b1，b2，…，bn)， 及二进制序列x=(x1，x2，…，xn)，且xi∈{0, 1}
§3 公开密钥算法RSA
大数分解难题
若已给两个大素数p及q，欲求出其乘积n＝pq，则只需要 一次乘法。但若已给n，欲分解n求得确实的p及q，称为因 子分解问题(Factorization Problem, FAC)。