RSA 算法

算法1.1 RSA密钥对生成

输入：安全参数l.

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

1、随机选择两个素数p和q,p和q的长度同为l/2

2、计算n=pq和z=(p-1)(q-1)

3、任意选择整数e，e满足1<e<z，且gcd(e,z)=1

4、计算整数d,d满足1<d<z,且ed=1 (mod z).

5、返回(n,e,d)

算法1.2 基本RSA加密

输入：RSA公钥（n,e）,明文m属于[0,n-1]

输出：密文c

1、计算c=m^e mod n

2、返回m

算法1.3 基本RSA解密

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

输出：明文m

1、计算m=c^d mod n

2、返回m

算法1.4 基本RSA签名生成

输入：RSA公钥（n,e）,RSA私钥d,消息m.

输出：签名s.

1、计算h=H(m)

2、计算s=h^d mod n

3、返回s.

算法1.5 基本RSA签名验证

输入：RSA公钥(n,e)，消息m,签名s.

输出：接受或拒接签名

1、计算h=H(m)

2、计算h'=s^e mod n.

3、若h=h',则返回‘接受签名’，否则返回‘不接受签名’