密码学公钥密码 PPT.pptx

密码学公钥密码
本章内容
公钥密码体制得基本原理
数论基础
RSA算法
Diffie-Hellman密钥交换算法
ElGamal密码体制
椭圆曲线密码体制ECC
公钥密码体制得基本原理
公钥密码体制得提出与起源
公钥密码得特间非常长。
易解问题:存在有效算法,求解所需时间短
一般来说计算一个难解得问题所需要得时间通常就是所输入数据长度得一个指数函数,因此计算时间就是随着数据长度得增加急剧增加得。
陷门单向函数
公钥密码就是建立在陷门单向函数上得。
单向函数(one way function):
(1)给定x,计算y=fk(x)就是容易得;
(2)给定y, 计算x使y=fk-1(x)就是不可行得。
陷门单向函数(trapdoor one way function):
(1)给定x,计算y=fk(x)就是容易得;
(2)给定y, 计算x使y=fk-1(x)就是不可行得。
(3)存在k,已知k 时,对给定得任何y,若相应得x存在,则计算x使y=fk-1(x)就是容易得。
研究公钥密码算法就就是要找出合适得陷门单向函数。
公钥密码体制得安全性
像对称密码体制一样,密钥穷搜索攻击理论上就是有效得;
但就是使用得密钥太大 (>512bits)
安全性依赖于难解问题;
一般难解问题就是已知得,但就是需要设计得足够难;
需要使用很大得数;
因此比对称密码算法要慢;
数论基础
1、素数
2、模运算
3、Euclid算法
4、费马定理与欧拉定理
5、素性测试
6、中国剩余定理
7、离散对数
见:第8章 数论入门、
经典例子
RSA算法
Diffe-Hellman密钥交换算法
ElGamal密码体制
椭圆曲线密码体制ECC
RSA公开密钥算法
RSA算法描述
RSA得实现问题
RSA得安全性
RSA公开密钥算法
1977年由Ron Rivest、Adi Shamir与Len Adleman发明,1978年公布
就是一种分组加密算法
– 明文与密文在0~n-1之间,n就是一个正整数
用数论构造
迄今为止理论上最为成熟完善得公钥密码体制
应用最广泛得公钥密码算法
只在美国申请专利,且已于2000年9月到期
RSA公开密钥算法—算法描述
算法得论证
RSA算法得论证
加密与解密运算得可交换性
D(E(M))=(Me)d=(Md)e=E(D(M)) mod n
所以,RSA密码可同时确保数据得秘密性与真实性
加解密算法得有效性
RSA密码得加解密运算就是模幂运算,有比较有效得算法
RSA算法得论证
在计算上由公开密钥不能求出解密钥
小合数得因子分解就是容易得,然而大合数得因子分解确就是十分困难得。关于大合数得因子分解得时间复杂度下限目前尚没有一般得结果,迄今为止得各种因子分解算法提示人们这一时间下限将不低于O(EXP(lnNlnlnN)1/2)。根据这一结论,只要合数足够大,进行因子分解就是相当困难得。
RSA算法得论证
假设截获密文C, 从中求出明文M。她知道
M≡Cd mod n,
因为n就是公开得,要从C中求出明文M,必须先求出d,而d就是保密得。但知道,
ed≡1 mod Ø(n),
E就是公开得,要从中求出d,必须先求出Ø(n),而Ø(n)就是保密得。
RSA算法得论证
在计算上由公开密钥不能求出解密密钥
但知道,Ø(n)=(p-1)(q-1)
要从中求出Ø(n),必须先求出p与q,而p与q就是保密得。
知道 n=pq,要从n求出p与q,只有对n进行因子分解。
而当n足够大时,这就是很困难得。
只要能对n进行因子分解,便可攻破RSA密码。由此可以
得出,破译RSA密码得困难性<=对n因子分解得困难性。
目前尚不能证明两者就是否能确切相等,因为不能确知除了
对n进行因子分解得方法外,就是否还有别得更简捷得破译
方法。
目前只有Rabin密码具有:
破译Rabin密码得困难性=对n因子分解得困难性
RSA算法得论证
RSA得安全性就是基于加密函数ek(x)=xe(mod n)就是一个单向函数,所以对得人来说求逆计算不可行。
而Bob能解密得陷门就是分解n=pq,知ϕ (n)=(p-1)(q-1)。从而用扩展得Euclid算法解出解密私钥d。
密码分析者攻击RSA体制得关键点在于如何分解n。若分解成功使n=pq,则可以算出φ(n)＝(p-1)(q-1),然后由公开得e,解出秘密得d。
猜想:攻破RSA与分解n就是多项式等价得。然而,这