（九）RSA

非对称加密——RSA

全称Rivest-Shamir-Adleman，是第一个公钥加密方案。公钥加密方案使用两个密钥：一个是公共密钥，也称公钥，用来加密；另一个是秘密密钥，也称私钥，用来解密。

RSA除了用来加密，也可以用于实现数字签名。公钥用来验证签名，私钥用来数字签名。

工作原理

前提知识：群

在数学中，群是一组元素的组合，这些元素之间定义了数学规则。

一个集合要想构成群，必须满足群公理：

封闭性：对于群中任意两个元素x和y，它们的乘积x×y必须也是该群中的一个元素。

结合律：对群中的任意元素x、y和z，都有(x×y)×z=x×(y×z)。

单位元：该集合中存在一个元素e，使得集合中的任一元素x与之相乘（包括左乘和右乘）的结果都等于x本身，即e×x=x×e=x。

逆元：对群中任意元素x，都可以找到一个元素y，使得x×y=y×x=e。

例如，全体非零整数模一个素数p后所得到的所有不同的余数组成的集合，也即取值范围在1到p-1之间的一组非零整数所构成的集合，记为。

例如p=5时，Z={1,2,3,4}，在群中，所有的运算最后都会mod 5，例如3×2=1而不是6，如果是6那么就超出了群的范围。

RSA的数学原理

RSA将加密的明文看作1到n–1之间的正整数，其中n是一个被称为模数的大数。RSA只对小于n且与n互素的数起作用。当这些数相乘时，产生满足同样条件（小于n且与n互素）的另一个数。在数学上，这些数构成一个群，记为，也称为整数模n所构成的乘法群。

当n不是素数时，要求群中所含元素的个数，需要使用欧拉totitent函数，记为φ(n)。函数φ(n)给出了与n互素的数的个数，也就是群中所含元素的个数。如果n是m个素数的乘积，即，n=p1×p2×...×pm

那么群中的元素个数如下：

φ(n)=(p1-1)×(p2-1)×(p3-1)×...×(pm-1)，φ(n)也叫群的阶。

RSA只处理由两个大素数的乘积构成的大数n，记为n=p×q。根据φ(n)函数，可以知道包含φ(n)=(p–1)(q–1)个元素，展开得φ(n)=n-p-q+1或φ(n)=(n+1)-(p+q)，说明1和n-1之间除了(p+q)个数以外的所有数都属于群，这(n+1)-(p+q)个数在RSA操作中都是“有效数”。

陷门置换

RSA陷门置换是RSA加密和RSA签名的核心算法。给定模数n和数e（也叫公开指数），RSA陷门置换将群中的数x通过y=x^e mod n变换为群中的另一个数y。使用RSA陷门置换进行加密，模数n和指数e构成了RSA的公钥。

从y反推出x，需要用另一个数d，称为陷门，计算方式如下：

d是RSA私钥的一部分（也叫秘密指数）。d并不能任意取值，它是恰好满足与e相乘后模φ(n)等于1的数，因此对于任何的数x，都有x^(ed) mod n=x。也就是必须有ed mod φ(n)=1 ，才能得到x^(ed)=x^1=x，这样可通过d正确地解密消息。

密钥生成

前提知识——扩展欧几里得算法

是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式：ax+by=gcd(a,b). gcd代表返回两个数的最大公约数的函数。

生成密钥对过程

公钥包括模数n和公开指数e，私钥指秘密指数d。数p和q（即满足pq=n的两个大素数）与乘法群阶φ(n)也必须是秘密的，它们通常也被看作私钥的一部分。

过程如下（以n的长度为2048为例）：

1.先随机选择两个素数p和q，p、q ∈(0,2^1024)

2.计算n=p×q，计算φ(n)=(p-1)×(q-1)

3.随机选择素数e，e<φ(n)。

4.使用扩展欧几里得算法生成秘密指数d

5.验证ed mod φ(n) = 1

6.加密计算y=x^e mod n 

7.解密计算x=y^d mod n

RSA加密

通常，RSA与对称加密方案结合使用。具体使用时，RSA用于加密对称密钥，而对称加密方案（如AES等）用于加密消息。

直接加密

直接使用RSA加密有个问题，对同一密文加密两次，两次的结果是一样的，更危险的是，现在给定两个密文y1=(x1)^e mod n和y2=(x2)^e mod n，可以计算y1×y2=(x1)^e×(x2)^e mod n=(x1×x2)^e mod n，这就得到了x1×x2的密文，攻击者从原有的密文中构造出了新的有效密文，从而可以使的攻击者推测一些内部结构，RSA变得不安全。不要使用这种方式。

RSA-OAEP

当需要使用RSA加密时，应该使用最优非对称加密填充（OAEP），该方案在调用RSA函数之前，先在消息中填充额外的数据和随机数来创建一个与模数同样规模的比特字符串。

OAEP使用了伪随机数发生器（PRNG），通过使加密具有概率性来保证密文的不可区分性和不可扩展性。只要RSA函数和PRNG是安全的，同时哈希函数不太弱，OAEP就可以被证明是安全的。

 工作原理

加密过程：

1.准备对称密钥K、PRNG、OAEP所定义的h字节的常量H、两个哈希函数Hash1和Hash2，m字节长的模数n（n小于2^8m）。

2.编码消息M=H || 00...00 || 01 || K，M的中间用0x00填充，直到M的长度达到8m。

3.生成一个h字节的随机字符串R，令M=M⊕Hash1(R)，R=R⊕Hash2(M)。

4.计算P=00 || M || R  （P为m字节）。

5.计算x=P mod n。

6.计算密文y=x^e mod n。

解密过程：

1.x=y^d mod n，得到P，继而得到M和R。

2.计算初始M=M⊕Hash1(R⊕Hash2(M))。

3.验证M=H || 00...00 || 01 || K，得到H和K。

实际中，一般取m=256字节（对于2048比特的RSA）和h=32字节（使用SHA-256作为Hash2）。这样M中还剩下m–h–1=223字节，并且其中至多有m–2h–2=190字节可用于K（“–2”是因为M中的01字节）。因此，Hash1的哈希值将由m–h–1=223字节组成。

RSA签名

数字签名可以使与特定数字签名绑定的私钥持有者在某一消息上签名，并保证该签名的权威性。因为除了私钥持有者之外没有人知道秘密指数d，所以攻击者无法从某个值x计算签名y=x^d mod n，但是任何人都可以使用公开指数e来验证y^e mod n=x是否成立。该验证签名可以在法庭上用于证明私钥持有者确实签署了某个特定的消息，这个不可否认的属性被称为不可否认性。

直接签名

通过直接计算y=x^d mod n对消息x进行签名，但这在重放攻击面前不安全。

例如0^d mod n=0，1^d mod n=1 ... (n–1)^d mod n=n–1，无论私钥d如何取值，攻击者都可以在d未知的情况下伪造0、1或n–1。

盲攻击 

假设现在有消息M，攻击者需要在M不可能被第三方主动签名的情况下得到第三方对M的签名。

步骤：

1.首先找到某个值R，它满足条件——R^e×M mod n是一条攻击者会在知情情况下主动签名的一条消息。

2.攻击者将说服（欺骗）被攻击者对消息R^e×M进行签名并显示该签名S，S=(R^eM)^d mod n。

3.有了S，可以推导出M^d。

(R^e×M)^d=R^(ed)×M^d

又R^(ed)=R，S=(R^eM)^d=R×M^d，S/R=M^d.

由此得到M^d，即M的签名。

PSS签名

全称为RSA概率签名方案，它使消息签名更加安全。

PSS并不作用于消息本身，而是对消息的哈希值起作用。只要哈希函数可以抵抗碰撞攻击，Hash(M)的签名就是安全的。

签名过程

消息M的PSS签名过程如下（其中h是Hash1的输出长度）： 

1．使用PRNG选取r字节随机字符串R。

2．形成编码消息M'=0000000000000000 || Hash1(M) || R，该编码消息的长度为h+r+8字节（开头有8个00字节）。

3．通过H=Hash1(M')计算出h字节的字符串H。

4．令L=00...00||01||R，其中填充的00字节使得L的长度恰好为m–h–1字节（模数的字节长度m减去哈希长度h再减去1）。

5．令L=L⊕Hash2(H)，从而完成L的更新。

6．将m字节的字符串P=L || H || BC转换为小于n的数x。字节BC是在H之后附加的固定值。

7．计算x^d mod n以获得签名。

要验证消息M的签名，需要先计算Hash1(M)，并使用公开指数e从签名中得到L和H，然后得到M'，并在上述每个步骤中检查填充的正确性。

实际上，随机字符串R（在RSA-PSS标准中被称为盐）通常与哈希值一样长。例如，如果选取n=2048比特并选择SHA-256作为哈希函数，则值L的长度为m–h–1=256–32–1=223字节，而随机字符串R通常为32字节。

FDH签名 

全域哈希签名。

签名过程：

x=Hash(M)

签名y=x^d mod n。

验签过程：

x=y^e mod n

x与Hash(M)比较。