密码学非对称密码体制(1).ppt

第六章 非对称密码体制
《信息安全技术》
.
1
概述
对称密码体制的缺陷
密钥的安全传递比较困难
n个用户多点通信所需密钥数为n(n-1)/2个
难以提供对主动攻击的抗击
公钥（非对称）密码体制的基本思想
Whitfield Diffie和Martin Hellman在1976年首先提出：用公开的密钥（公钥）加密，用与之对应的不公开的密钥（私钥）解密。
公钥密码体制提出的标志性文献──密码学的新方向：
and , New Directions in Cryptography, IEEE Transaction on Information Theory, -, Nov 1976, -654
.
2
例：程嘉要传送密信给雷蕾，用雷蕾的公钥对明文进行加密，然后通过公共信道将密文传送给雷蕾，雷蕾用的与自己的公钥对应的私钥（只有雷蕾自己知道）解密得到明文。康威企图知道密信内容，截获到密文，虽然他也知道加密所用的公钥，但他无法通过公钥倒推出相应的私钥，当然就不可能解密出明文。
.
3
对公钥密码体制的要求
（1）参与方B容易通过计算产生一对密钥（公开密钥KUb和私有密钥KRb）。
（2）在知道公钥和待加密报文M的情况下，对于发送方A，很容易通过计算产生对应的密文：C=EKUb(M)
（3）接收方B使用私钥容易通过计算解密所收到的密文C以便恢复原来的明文：
M=DKRb(C)=DKRb (EKUb(M))
（4）攻击者即使知道公钥KUb，要确定其对应的私钥KRb在计算上是不可行的。
（5）攻击者即使知道公钥KUb和密文C，要想恢复原来的明文M在计算上也是不可行的。
（6）加密和解密函数可以以两个次序中的任何一个来使用:M=DKRb(EKUb(M)) （机密性）
或M=EKUb(DKRb(M)) （数字签名）
.
4
单向陷门函数
公钥密码体制必须设计一个满足下列条件的函数f：
正向易算性──由消息x和密钥pk 容易计算y=fpk(x)
反向不可算性──在不知道密钥sk的情况下，由任意的y倒过来计算x =f-1sk(y)都是不可行的
陷门依赖性──如果给定另一密钥sk，则f-1(y)是可以计算的， sk 与pk配对，相当于陷门。
满足1、2的函数称为单向函数
满足1、2、3的函数被称为带陷门的单向函数
.
5
.
6
公钥密码体制的特点
无需密钥的安全传递
n个用户仅需n个“公钥-私钥”对
支持对主动攻击的抗击
安全性基于带陷门的单向函数
加密、解密速度比DES、AES等分组密码体制慢
可用于对称密钥的交换
.
7
数论背景——欧拉函数与欧拉定理
欧拉数
设正整数n，则欧拉数φ(n)定义为小于n且与n互素的正整数的个数（特殊地，φ(1)=1 ）。
例如：φ(6)=2(小于6且与6互素的是1和5); φ(7)=6(1,2,3,4,5,6); φ(11)=10(1~10)
素数的欧拉数
对于素数p ，其欧拉数φ(p)=p-1(1~p-1)
欧拉数的初等性质
当p、q都是素数时，
φ(pq)=φ(p)φ(q)=(p-1) (q-1)
例： φ(15)=φ(3)φ(5)=2*4=8(1,2,4,7,8,11,13,14)
.
8
当e与m互素，则存在正整数d，使得
ed=1 (mod m)
称d是e关于模m的乘法逆元（简称“模乘逆元”或“模逆元”），记作e-1
例如：设m=13，
则5*8=40=3*13+1=1 (mod 13)
故 5-1=8
欧拉定理
假设m、n互素，则mφ(n)=1 (mod n)
例如：设m=13，n=7，
则136=4826809=689544*7+1=1 (mod 7)
.
9
费马小定理──欧拉定理的推论
设p与m互素，且p是素数，则
m p-1=1 (mod p)（因为φ(p)=p-1）
基础定理──RSA的理论基础
设n是两个不同的素数p、q之积，x是小于n的非负整数，k是非负整数，则有：
x kφ(n) +1=x (mod n)
.
10