文档介绍：公钥密码系统
一、基本概念
二、RSA
三、基于离散对数的公钥系统
四、椭圆曲线公钥体制
一、基本概念
对称密码体制的缺陷
公钥密码学思想
安全性
1 对称密码体制的缺陷
public-key/two-key/asymmetric 包括两个密钥:
公开密钥(a public-key), 可以被任何人知道, 用于加密或验证签名
私钥( private-key), 只能被消息的接收者或签名者知道,用于解密或签名
公钥与私钥不同,但又相互对应,并且由公钥不能推导出对应的私钥。
加密或验证签名者不能解密密文或生成签名.
选择某种算法(可以公开)能做到:用公钥加密的数据只有使用与该公钥配对的私钥才能解密。
基本概念(续)
公钥加密算法的核心——单向陷门函数,即从一个方向求值是容易的。但其逆向计算却很困难,从而在实际上成为不可行。
,如果对任意给定的,计算,使得是容易计算的,但对于任意给定的,计算,使得是难解的,即求的逆函数是难解的,则称是一个单向函数。
基本概念(续)
, 是与有关的一个参数。对于任意给定的,计算,使得是容易的。如果当不知参数时,计算的逆函数是难解的,但当知道参数时,计算函数的逆函数是容易的,则称是一个单向陷门函数,参数称为陷门。
2公钥密码学思想
{M,C,K,EK,DK},且满足如下的条件:
;
;
3. 密钥空间K是一个可能密钥的有限集;
={K1,K2} ∈K,都对应一个加密算法EK1 ∈ E, EK1:M→C和解密算法DK2 ∈ D,DK2:C → M,满足对于任意的m ∈ M,都有c= EK1(m),m= DK2(c)=DK2(EK1(m))=m;
,在已知E的情况下推出D是计算上不可能的;
对每一个k∈ K,函数EK1和DK2都是多项式时间可计算的函数。EK1是一个公开函数,K1 称作公钥;而DK2是一个秘密函数,K2称作私钥,由用户秘密地保存。
由私钥及其他密码信息容易计算出公开密钥(a polynomial time (P-time) problem)
由公钥及算法描述,计算私钥是难的(an NP-time problem)
因此,公钥可以发布给其他人(wishing municate securely with its owner )
密钥分配问题不是一个容易的问题(the key distribution problem )
依赖于足够大的困难性差别
类似对称算法,穷搜索在理论上是能够破解公钥密码 exhaustive search
但实际上,密钥足够长(>512bits),计算上不可行。一般基于一些已知的困难问题(hard problem)
要求足够大的密钥长度(>512 bits)
多为大数运算,导致加密速度比对称算法慢
二、RSA
简介
RSA算法内容
RSA 参数选择
RSA理论
举例