密码学——第7章 公钥密码数学基础

密钥管理
对称算法需要额外安全信道 公钥
证书中心
混合密码体制
公钥算法用于签名和认证 用公钥算法传输会话密钥 用会话密钥/对称算法加密批量(bulk)数据
32
Γ
В
作业：用RSA 加密解密
p=3,q=11,e=7,M=5 p=5,q=11,e=3,M=9 如果：e=31,n=3599,d=? c=10,e=5,n=35,M能够求出吗？
Γ
В
简单例子
n＝pq＝ φ(n)＝请练习
任务：对明文 M=19 加密
选中两个素数 p＝7，q＝17 n＝pq＝119 φ(n)＝(p-1)(q-1)＝6×16＝96
选取整数1<e< φ(n)与φ(n) 互素：e＝5 求e的逆元d：ed≡1 mod φ(n) 请练习 d=77
计算 C=Me(mod n)=? 其中M=19 请练习 c=66 计算 M1=Cd(mod n)=? 请练习
对称算法一般几十兆字节/秒 1024位RSA解密约100多次/秒(加密快10倍以上)
只用来传递会话密钥
(假设A已经有B的公钥KeB) A发起和B的通信 A产生会话密钥Ks，并用KeB加密后传给B B能用自己的私钥KdB解开 他人不会知道Ks
31
Γ
В 对称算法 vs. 公钥算法
安全性 速度
典型相差1000倍
33
Γ
5
Γ
В
密码学革命
1976年 Diffie和Hellman针对上述问题提出 年 和 针对上述问题提出 了一种方法， 了一种方法，它是密码学的一次革命
6
Γ
В
公钥密码体制介绍
7
Γ
В
公钥密码体制特点
仅根据密码算法和加密密钥来确定解密密钥在 仅根据密码算法和加密密钥来确定解密密钥在 密码算法 来确定解密密钥 计算上是不可行的。 计算上是不可行的。 两个密钥中的任何一个可以用来加密，另一个 两个密钥中的任何一个可以用来加密， 用来解密。 用来解密。 有6个组成部分：明文、加密算法、公钥、 个组成部分：明文、加密算法、公钥、 个组成部分 私钥、密文、 私钥、密文、解密算法

公钥密码学的数学基础公钥密码学是一种采用数学方法来确保数据安全的技术，主要用于加密通信和认证。

它涉及大量的数学原理和技术，例如数论、代数、密码、编码和其他一些有关计算机安全的理论和技术。

数论中的基本概念有素数、素数的分解、欧拉函数、离散对数问题和乘法原理等。

素数的性质可用来设计公钥密码系统。

欧拉函数是一个估算不同数字的素数因子的强大工具，它可以帮助安全系统进行更复杂的加密和认证。

离散对数问题和乘法原理是两种重要的数学理论，它们可以用来破译和解决古典的公钥密码。

代数是一门研究属性和关系的数学学科。

代数在公钥密码学中也得到了广泛应用，特别是在密码变换和基于椭圆曲线加密中。

在密码变换中，代数学家们提出了许多算法，如Rijndael、Twofish 和AES，以帮助用户安全地加密和解密数据。

基于椭圆曲线加密利用椭圆曲线上的点来进行加密和解密，而这里面也用到了许多代数的原理。

密码学主要涉及密码分析和安全性评估。

密码分析是一种利用统计加密算法来评估和攻击加密系统的技术。

它旨在检测密码系统中潜在的漏洞，并尽可能地破解密码。

安全性评估是一种对加密系统进行合理测试和评估的方法，以确定其是否可以抵御恶意攻击和其他威胁。

编码是一种用来表示数据的技术，它可以帮助保护数据免受攻击和窃取。

为了确保编码技术的安全性，一般使用许多复杂的数学原理。

例如，RSA算法就是一种基于大整数的加密算法，它可以非常有效地加密信息。

最后，公钥密码学还涉及计算机安全的一些理论和技术，如访问控制、身份验证和安全协议等。

计算机安全的目的是保护用户的数据和信息安全，因此它也涉及各种安全算法和技术，以解决面临的安全挑战。

公钥密码学的理论基础公钥密码学的理论基础—单向函数1976年，Diffie W.和Hellman M.E.在他们的《密码学的新方向》一文中提出了公钥密码的概念。

随后，在1978年，Rivest R.L.，Shamir A.和Adleman L.M.在其文《实现数字签名和公钥密码体制的一种方法》中最先提出了一种可行的实现方法，这就是我们现在广泛使用的RSA 体制。

RSA体制的提出真正使得互不相识的通信双方在一个不安全的信道上进行安全通信最终成为可能，也是我们今天CA服务的源泉。

然而，人们很少关心当前幸福生活的背后有一位默默的奉献者—单向函数。

单向和陷门单向函数的概念是公钥密码学的核心，可以说公钥密码体制的设计就是陷门单向函数的设计。

那么什么是单向函数？什么是陷门单向函数？他们的密码学意义何在？本文试图作一个初浅的介绍。

1 单向函数给定任意两个集合X和Y。

函数f：X Y 称为单向的，如果对每一个x属于X，很容易计算出函数f(x)的值，而对大多数y属于Y，要确定满足y=f(x)的x是计算上困难的(假设至少有这样一个x存在)。

注意，不能将单向函数的概念与数学意义上的不可逆函数的概念混同，因为单向函数可能是一个数学意义上可逆或者一对一的函数，而一个不可逆函数却不一定是单向函数。

目前，还没有人能够从理论上证明单向函数是存在的。

单向函数存在性的证明将意味着计算机科学中一个最具挑战性的猜想P=NP，即NP完全问题的解决，而关于NP完全性的理论却不足以证明单向函数的存在。

有幸的是，现实中却存在几个单向函数的“候选”。

说他们是“候选”，是因为他们表现出了单向函数的性质，但还没有办法从理论上证明它们一定是单向函数。

一个最简单的、大家熟知的“侯选”单向函数就是整数相乘。

众所周知，不管给定两个多大的整数，我们很容易计算出它们的乘积，而对于一个300位左右的十进制整数，即使已知它是两个大小差不多(150位左右的十进制数)的素数之积，用世界上计算能力最强的计算机，也没有办法在一个合理的时间内分解出构成这个整数的两个素数因子来。

公钥(加密密钥):e 私钥(解密密钥):d
2
一、公钥密码原理
一、公钥密码原理
一、公钥密码原理
一、公钥密码原理
一、公钥密码原理
二、数论知识
3
二、数论知识
二、数论知识
二、数论知识
二、数论知识
二、数论知识
4
二、数论知识
二、数论知识
3版P96，四版P86
二、数论知识
二、数论知识
Fermat定理
二、数论知识
一、公密码原理
Bob的 公钥环
Mike Joy
Ted Alice
Alice的公钥
Alice的私钥
传输密文
明文输入 加密算法，如RSA 图4-1 通信保密
解密算法 明文输出
一、公钥密码原理
(2) 数字签名：将私钥作为加密密钥，公钥 作为解密密钥，可实现由一个用户对数据加密 而使多个用户解读。如图4-2所示，Bob用私 钥对明文进行加密并发布，Alice收到密文后 用Bob公布的公钥解密。由于Bob的私钥只有 Bob本人知道，因此，Alice看到的明文肯定是 Bob发出的，从而实现了数字签名。
(3) 密钥交换：通信双方交换会话密钥，以 加密通信双方后续连接所传输的信息。每次逻 辑连接使用一把新的会话密钥，用完就丢弃。
一、公钥密码原理
Alice的 公钥环
Bob的私钥
Mike Joy
Ted Bob
Bob的公钥
传输密文
明文输入 加密算法，如RSA
解密算法 明文输出
图4-2 数字签名
一、公钥密码原理
Tel : 029-88202600 Email : jjmu@
mujianjun88@
第六讲 RSA公钥密码体制