文档介绍：主要内容
公钥密码体制的产生
数论基础
公钥密码体制的基本原理
RSA公钥密码体制
其它公钥密码算法
传统密码体制在应用中的缺陷
密钥管理的麻烦
密钥难以传输
不能提供法律证据
缺乏自动检测密钥泄密的能力
费尔马小定理(Fermat)
如果p是一个素数,a不是p的倍数,
则:ap-1≡1 (mod p)
证明:
设有一整数空间S={1,2,…,p-1}
再设有一函数Ψ(x)=ax(mod p) x∈S
(1)对于任何x∈S,有Ψ(x)∈S
(2)对于x和y(x≠y),有Ψ(x)≠Ψ(y)
(3)根据乘法定理和除法定理
(p-1)!ap-1≡(p-1)! mod p
欧拉函数
Ф(n):小于n且与n互素的正整数的个数
显然,对于素数p,有Ф(p)=p-1
设有两个素数p和q,p ≠q,那么对于n=pq,有: Ф(n)= Ф(pq)= Ф(p)* Ф(q)
=(p-1)*(q-1)
欧拉定理(Euler)
对于任意互素的a和n,有aФ(n) ≡1 mod n
证明:对于整数n,与n互素的数有Ф(n)个:
令这些数为:R={x1, x2, …,x Ф(n) }
用a与R中的每个元素相乘模n,得到集合S:
S ={ax1 mod n, x2 mod n, …,x Ф(n) mod n }
其实S就是R:
(ax1 mod n) R
S中的元素是唯一的
那么:R中各元素相乘就等于S中各元素相乘:
∈
公钥密码体制(Public key system)
公钥密码学与其他密码学完全不同:
公钥算法基于数学函数而不是基于替换和置换
使用两个独立的密钥
公钥密码学的提出是为了解决两个问题:
密钥的分配
数字签名
1976年Diffie和Hellman首次公开提出了公钥密码学的概念,被认为是一个惊人的成就。
公钥密码体制的原理
公钥体制(Public key system) (Diffie和Hellman,1976)
每个用户都有一对选定的密钥(公钥k1;私钥k2),公开的密钥k1可以像电话号码一样进行注册公布。
主要特点:
加密和解密能力分开
多个用户加密的消息只能由一个用户解读,(用于公共网络中实现保密通信)
只能由一个用户加密消息而使多个用户可以解读(可用于认证系统中对消息进行数字签字)。
无需事先分配密钥。
公钥密码体制有4个组成部分
明文:算法的输入,它们是可读信息或数据,用M表示;
密文:算法的输出。依赖于明文和密钥,对给定的消息,不同的密钥产生密文不同。用E表示;
公钥和私钥:算法的输入。这对密钥中一个用于加密,为Ke,此密钥公开;一个用于解密,为Kd,此密钥保密。加密算法执行的变换依赖于密钥;
加密、解密算法
公钥密码体制下的秘密通信
公钥加密体制的特点
加密和解密能力分开
多个用户加密的消息只能由一个用户解读,可用于公共网络中实现保密通信
用私钥加密的消息可以用对应的公钥解密,所以由一个用户加密消息而使多个用户可以解读,可用于认证系统中对消息进行数字签字
无需事先分配密钥
密钥持有量大大减少
提供了对称密码技术无法或很难提供的服务:如与哈希函数联合运用可生成数字签名,可证明的安全伪随机数发生器的构造,零知识证明等