文档介绍：公钥密码体系
杭州电子科技大学
计算机安全与保密
对称算法的不足
密钥必须通过某一信道协商,对这个信道的安全性的要求比正常的传送消息的信道的安全性要高
公钥密码背景
公钥密码体制的特点:
加密密钥与解密密钥在本质上是不同的,即已知一个密钥并不能轻易地求出另一个密钥。
不需要增加分发密钥的额外信道。
公钥密码体制的要求:
产生一对密钥是计算可行的
已知公钥和明文,产生密文是计算可行的
接收方利用私钥来解密密文是计算可行的
对于攻击者,利用公钥来推断私钥是计算不可行的
已知公钥和密文,恢复明文是计算不可行的
(可选)加密和解密的顺序可交换
求离散对数问题
y=gx mod p
若给出p,g,y求x称为求离散对数问题
因子分解问题
n=pq
若给定n,求p,q称为因子分解问题
背包问题
给定一个有限个自然数序列集合B=(b1,b2,……,bn)及二进制数序列x=(x1,x2,……,xn),S= x1 b1 + x2 b2 +……+ xn bn
给定B,S,求x序列,称为求背包问题
单向陷门函数:
单向陷门函数是满足下列条件的函数f:
给定x,计算y=f(x)是容易的;
给定y, 计算x使x=f-1(y)是不可行的;
存在陷门t,已知t时,对给定的任何y,若相应的原象x存在,则计算x是容易的。
通过陷门单向函数建立公钥密码
f(x)是单向陷门函数,陷门为t。那么设计公钥密码系统时f(x)作为公钥,陷门t作为私钥,任何人都可将明文m利用公钥f(x)加密得到密文y=f(m),而任何人不知道私钥即陷门,由密文y都无法求出m,因为f(x)是单向的,但拥有私钥,便可容易求出m
RSA公钥密码体制
1 、1977年由Rivest、Shamir和 Adleman发明并于1978年公布。
2 、应用最广泛的公钥密码算法
3 、只在美国申请专利,且已于2000年9月到期