格理论与密码学-2-2-公钥密码体制和哈希函数
目录
2.2.1 公钥密码体制的产生
对称密码算法存在三个主要问题
单向陷门函数的性质
2.2.2 公钥密码体制原理
公钥密码体制的五元组
公钥加密具体步骤
认证过程
公钥密码算法需要满足的条件
2.2.3 Diffie-Hellman密钥交换协议
DiffieHellman密钥交换协议的具体描述
DiffieHellman密钥交换容易受到两种攻击
抵抗离散对数攻击
中间人攻击
2.2.4 RSA密码系统
RSA加密算法
算法2.1 RSA加密算法
算法2.2 RSA数字签名算法
RSA的安全性
重复加密攻击
2.2.5 ElGamal公钥密码体制
算法2.3 ElGamal加密算法
算法2.4 ElGamal数字签名算法
2.3 哈希函数
定义2.2 哈希函数的定义
算法2.5 SHA-1算法
2.2.1 公钥密码体制的产生
对称密码算法存在三个主要问题
一个是通信双方的密钥传输和交换问题
一个是密钥管理问题
一个是无法解决消息认证问题
在对称密码系统中,通信双方可以选择通过另外一条比较安全的信道来交换密钥
然后用这个密钥来加密和解密信息
但是在公网环境下,特别是Internet环境中
很难找到这样的安全信道
另一个难以解决的问题是密钥的管理问题,
如在由n个用户组成的网络中
要使每个用户都能与其他用户进行安全通信,
则总共最少需要n(n-1)/2个密钥
随着用户数n的增长,用户密钥量也会急剧增加
而管理如此庞大的密钥数据也是极其困难的
考虑密码学中要解决的另一个问题——认证
对于解决身份认证问题,对称密码系统尚可发挥一定作用,
但对于解决消息认证问题,对称密码系统则显得无能为力
单向陷门函数的性质
2.2.2 公钥密码体制原理
公钥密码体制的五元组
公钥加密具体步骤
(1)每一个用户产生一对密钥,即公钥和私钥,用来加密和解密消息
(2)每一个用户将公钥存储于公开的可访问文件或目录服务器中,私钥自己秘密保存
(3)若Bob要发送消息M给Alice,则Bob用Alice的公钥对消息进行加密。
(4)Alice收到密文C后,用自己的私钥对C进行解密
由于只有Alice掌握自己的私钥,所以其他接收者均不能解密出该消息
认证过程
(1)Bob用自己的私钥对要发送的消息M加密,并将加密后的消息C发给Alice
(2)Alice收到Bob发送的加密消息C后,用Bob的公钥进行解密,并获得明文信息M。
因为从M得到C是经过Bob的私钥加密得到的,只有Bob拥有其自己的私钥
所以此操作只有Bob才能完成
因此,可以将C作为Bob对消息M的签名
另一方面,任何其他人只要得不到Bob的私钥就无法伪造Bob的签名
因此,以上过程可以实现消息的认证功能。
公钥密码算法需要满足的条件
- 密钥对,即公钥和私钥的产生在计算上是容易实现的
- 发送方A用接收方B的公钥对消息M进行加密并产生密文C,在计算上容易
- 接收方B用自己的私钥对消息C进行解密并获得明文M,在计算上容易
- 敌手由B的公钥去获得B的私钥在计算上不可行
- 敌手由密文C和B的公钥去恢复明文M在计算上不可行的
- 加密算法E和解密算法D是互逆变换的,即
2.2.3 Diffie-Hellman密钥交换协议
Diffie和Hellman在1976年提出的在用户间进行密钥协商的一种协议
其目的是通信双方在不安全的公共信道上协商共享秘密密钥
DiffieHellman密钥交换协议的安全性是基于离散对数问题的难解性
即求模幂运算是相对简单的;而计算离散对数问题是非常困难的
对于大素数,求离散对数在计算上是公认不可行的
DiffieHellman密钥交换协议的具体描述
至此双方完成了密钥共享的过程
由于 a和b都是保密的
所以即使敌手获取了p、g、X、Y
也很难获取Alice与Bob共享的密钥k
因为敌手要通过获得a或b
将面临解离散对数的困难问题
DiffieHellman密钥交换容易受到两种攻击
离散对数攻击、中间人攻击
抵抗离散对数攻击
需要采取以下措施
中间人攻击
DiffieHellman密钥交换协议不支持对协商密钥的认证功能。
处于Alice和Bob通信中间的主动攻击者
能够操纵这个协议的消息以达到成功的攻击
针对 Diffie-Hellman 密钥交换协议的中间人攻击的可能过程如下
在上述过程产生了两个密钥:一个是Alice和Eve之间的,一个是Eve和Bob之间的。如果Alice发送用k1加密的数据给Bob,那么这个数据就会被Eve解密并获取。Eve可以发送一个用k2加密的消息给Bob,他甚至可以改变消息内容发送一个新的消息。Bob被欺骗进而相信消息是来自 Alice的。同样的情况,也可以在另一个方向对Alice发生。
2.2.4 RSA密码系统
RSA加密算法
RSA算法采用了大整数为模的同余指数运算。如果RSA算法选择的大整数为n,则明文(密文)分组的大小应是小于n的非负整数,即如果分组长度由二进制表示时,分组长度要小于等于
算法2.1 RSA加密算法
算法2.2 RSA数字签名算法
RSA的安全性
大整数分解攻击:二次筛法、广义数域筛法
为了保证安全性,对p和q的选择还应该满足
下面逐个说明理由
对(1)的分析如下
对(2)的分析如下
重复加密攻击
2.2.5 ElGamal公钥密码体制
ElGamal公钥密码系统既能用于数据加密,也能用于数字签名
其安全性依赖于解有限乘法群上的离散对数问题的困难性
算法2.3 ElGamal加密算法
算法2.4 ElGamal数字签名算法
2.3 哈希函数
哈希(Hash)函数又称单向散列函数,也称消息摘要,是现代密码学的重要组成部分。哈希函数就是把可变的输入长度串(任何字节串,如文本字符串、Word文档、JPG文件等)转换成固定长度输出值的一种函数。哈希函数的输出数值称为该信息的哈希值,也称为Hash值,其长度取决于所采用的算法,通常在128~256bit。哈希函数可用于数字签名、保证消息的完整性、认证消息的来源,常见的算法有MD5、SHA-1等