0%

现代密码学(五)公钥密码

介绍公钥密码学。

公钥密码理论

公钥算法主要有三类

  • 密钥分配
  • 公钥加密
  • 签名算法

DH密钥交换

  • 选定素数p和本原元a
  • A选定,计算
  • B选定,计算
  • 公开
  • A计算
  • B计算

RSA

算法流程

  • 选择两个大素数p和q
  • 计算
  • 随机选择加密密钥e,满足
  • 求解解密密钥d,满足
  • 公开,保存

原理如下

RSA实际上是一种单表代换

RSA的安全性取决于计算的困难性,但分解模未必是攻击RSA的最佳方法。

RSA需要计算大指数模幂,可以用中国剩余定理CRT来加速。

对于方程组

有唯一解

Rabin公钥密码体制

有两个困难数学问题

  • 二次剩余问题:给定奇合数n和整数a,难以判断a是n的二次剩余。
  • 模n的平方根问题:在n的分解未知情况下,难以求解n的平方根。

Rabin体制利用求解平方根的困难性构造了一种安全公钥体制。

首先选定两个形如4k+3的素数p和q,以n=pq作为公钥。

加密过程

解密首先计算

利用中国剩余定理,可以得到四个解,必有一个与M相同。

Rabin体制的安全性等价于大整数分解,但是对选择密文攻击不安全。

与RSA相比,Rabin只需要一次乘法运算,但解密时更困难。

El Gamal

基于离散对数,但增加了消息长度(2倍)。

首先选定大素数p和本原元g,计算

发送者选择随机数k,计算消息密钥

之后计算密文对

解密时先计算密钥再计算明文

对于公钥密码的攻击

可以对RSA发动弱参数攻击

  • 共模攻击
  • 低加密指数攻击

可以对Rabin发动选择密文攻击