RSA体制

RSA密钥生成

RSA加密方案

基本RSA加密

基本RSA解密

RSA签名方案

基本RSA签名生成

基本RSA签名验证

1977年提出

参考《Introduction to Elliptic Curve Cryptography》、《应用密码学：协议、算法与C源程序》

RSA体制

n：RSAOperation modulo,是两个等长、Secrecy random prime numbersp和q的乘积

e：加密指数,随机选取整数,满足 1 < e < Φ 且 gcd(e,Φ) = 1.（即e与Φ互素）

Φ：(p-1)(q-1)

d: 解密指数,整数,满足 1 < d < Φ 且 ed ≡ 1(mod Φ),此时d可知.（d与n也互素）

已证明：from the public key pair (n, e),计算出私钥 d 等价于从 n factor out p&q.This problem is called the factorization problem of integers（IFP）

注1：gcd(a,b)即ab最大公约数

注2：x ≡ 1(mod Φ),即x对Φ取余,余数为1

注3：e与Φ互素,d与n互素,p与qAfter the key pair is generated, it cannot be leaked.

RSA密钥生成

输入：安全参数 L

输出：RSA公钥对（n, e）, 私钥d

过程：

1、Two prime numbers are randomly chosenp、q,长度皆为 L/2

2、计算n,Φ

3、任意选择 e

4、计算整数 d

5、返回 (n, e) 和 d

RSA加密方案

依据 ≡ m (mod n)

基本RSA加密

输入：公钥对(n, e),明文 m∈[0,n-1]

输出：密文c

过程：

1、计算 c = mod n

2、返回 c

基本RSA解密

输入：公钥对(n, e),d,密文c

输出：铭文m

过程：

1、计算 m = = mod n

2、返回 m

RSA签名方案

依据 ≡ m (mod n),and hash calculations消息m 的摘要 h = H(m).签名计算 s = mod n 

通俗点说,RSAA signature scheme uses a private key to cryptographically sign a message,Use the public key for decryption and signature verification.

h：消息mshort fingerprints.

s：Signer's signature

基本RSA签名生成

输入：RSA公钥(n, e) 、RSA私钥d、明文m

输出：签名s

过程：

1、计算 h = H(m),其中 H is a hash function

2、计算 s = mod n

3、返回s

基本RSA签名验证

输入：(n,e),消息m,签名s

输出：验签通过？

过程：

1、计算 h = H(m)

2、Because the signature verification is calculated s = mod n,则 =  mod n ≡ h mod n,则 h’= mod n 

3、若 h’= h 验签通过