RSA 签名与验签

背景

由于最近公司组织一些技术分享，有些同学分享过程中，提到一些非对称加密算法，对于公钥和私钥作用的介绍是有些不恰当的地方，比如：

私钥加密，公钥解密

在网上我也搜索了相关内容，发现不少网友，甚至国内大厂以及有些境外的技术文章，都在 RSA 签名的过程中用了私钥加密（encrypt），公钥解密的说法，这种说法可能会方便理解数字签名一些细节，但是对加密和签名这两个不同的概念造成混淆，下面我们会介绍 RSA 以及它在签名和加密的关系，下面的大部分内容是翻译一些参考内容，这些参考内容的链接也会放到文末，大家有兴趣的可以看一下。

RSA 算法

这节会先介绍一下 RSA 算法，但是为了不让我们陷入数学的细节, 我们对部分计算方法进行了抽象。

在 1977 年，Rivest、 Shamir 和 Adelman 这三个人发现了一种算法可以用于加密，称为 RSA 算法：

R(x,k,n) = x^k (mod n)

参数 x、k 和 n 都是整数，它们的值可能非常大。其中 n 在后面的讨论中并不重要，为了方便，我们把它忽略掉，将其简写为 R(x, k)。

随着 RSA 算法，Rivest、Shamir 和 Adelman 这三个人还发现了一种可以选择两种密钥 K 和 k 的方式，可以进行如下计算：

R(R(x,K),k) = x
R(R(x,k),K) = x

这个算法就是说，RSA 算法种可以通过一个密钥 K 来对 x 处理出为 X, 还可以使用另外一个密钥 k, 将 X 还原为 x，反之亦然。这些就是对 RSA 的简绍，至于 k 与 K 是如何生成的我们不属于讨论的重点，暂时不做过多介绍了。

RSA 加密

根据以上 RSA 算法，我们可以通过公钥 K 去建立一个加密方案，然后使用私钥 k 进行解密

    Enc(m; K) = R(m,K)
    Dec(c; k) = R(c,k)

这就是加密一条明文消息 m，通过公钥使用 RSA 算法加密，然后使用私钥解密

以上就是教科书上所介绍的 RSA 加密算法，但实际上这些并不是全部内容，因为使用这种版本的 RSA 算法加密并不安全，将会收到很多攻击，下面举个例子：

• 假设用户 A 发送了两条消息 m1 和 m2, 然后使用公钥 K_A 来加密

    c1 = Enc(m1; K) = R(m1,K) = m1^K (mod n)
    c2 = Enc(m2; K) = R(m2,K) = m2^K (mod n)

• 那么如果 m1 和 m2 是相同的明文消息会发生什么事情呢

    c1 = m^K mod n = c2（两条密文是一致的）

因此，传统的 Dolev-Yao 攻击模型, 可以通过在网络上观察明文 m1 和 m2 的内容以及他们的密文，如果发现某条密文和已知内容的密文是一致的，那么就相当于解密了，一个安全的加密方案是不应该这样的。

对于更多的加密方案可以看看这两本书：

• [D. Boneh, A. Joux, and P. Nguyen. Why Textbook ElGamal and RSA Encryption are Insecure. In Proc. AsiaCrypt, 2000.]
• [J. Katz and Y. Lindell. Introduction to Modern Cryptography, section 10.4. Chapman & Hall/CRC, 2008.]。

为了让这种教科书版本的 RSA 加密更加安全，我们在使用 RSA 算法之前，会对明文信息 m 进行预处理，相应的，我们在使用 RSA 算法后会做一些后处理：

    Enc(m; K) = R(pre(m),K)
    Dec(c; k) = post(R(c,k))

这里有一些预处理和后处理的方案，他们通常会称为填充方案（内部做的不仅是填充，这种命名也稍微有一点不恰当），RSA 里有一种常用的填充方案，叫做最优非对称加密填充 OAEP（optimal asymmetric encryption padding），是由 Bellare 和 Rogaway 在 1994 年发明的，这个方案中，OAEP 预处理通过异或（XOR）对一个不可预知的临时数据（nonce）进行加密散列，来防止以上我们所发现的攻击方式。

下面进一步了解一下 OAEP 的大概内容：

OAEP 预处理函数：

    OAEP-pre(m):
    r = random nonce
    X = (m || 00...0) XOR H(r） // 对 m 填充 0
    Y = r XOR H(X)
    output X || Y

OAEP 后处理函数，用来恢复预处理的数据：

    OAEP-post(m'):
    split m' into X || Y
    r = Y XOR H(X)
    (m || 00...0) = X XOR H(r）
    output m

• 其中 || 符号表示二进制拼接，H 表示密码散列函数，XOR 为异或运算

把这些放到一起，我们就可以得到了 RSA-OAEP 的加密方案：

    Enc(m; K) = R(OAEP-pre(m),K)
    Dec(c; k) = OAEP-post(R(c,k))

RSA-OAEP 对于那些被广泛接受的加密方案安全性定义来说是安全的。当然上面提到的 “教科书式”的 RSA 在这个定义上并不是安全的。

RSA 数字签名

我们可以使用 RSA 函数去尝试建立用一个用公钥 K 验签和一个用私钥 k 签名的数字签名方案

    Sign(m; k) = R(m,k)
    Ver(m; s; K) = R(s,K) == m

签名一条消息 m, 只是根据私钥 k 通过 RSA 函数，生成一个签名 s。验证的话，就是用公钥和签名 s 通过 RSA 函数生成一个结果，然后对比这个结果是否与消息内容相同。

这个简单的方案最主要的问是这样的：RSA 函数不能够容纳比私钥更长的参数，简单来讲如果消息特别的长，是不能直接传给 RSA 函数的。这个问题在加密方案里，是通过块加密的方式来实现，而在签名方案里，我们是通过密码散列函数来实现的

    Sign(m; k) = R(H(m),k)
    Ver(m; s; K) = R(s,K) == H(m)

上面这是教科书上对于 RSA 签名的描述，或多或少整体就是这个样子，你可以认为密码哈希函数 H，在通过 R 函数处理前和处理后都是相等的，这样就可以来验证签名了。在签名中调用 RSA 函数的过程，在不少论坛或者文章中被称为 “加密” 以及 “解密” 在这两个词语上加上引号可以方便大家理解，但是去掉引号就有可能让大家造成混淆，甚至有人会认为使用 RSA 就是，客户端向服务端传输就是公钥加密私钥解密，服务端向客户端传输就是私钥加密公钥解密，这个理解就是错误的了

在签名验签的方案种，其实也是有一个稍复杂一下的预处理和后处理方案，称作 PSS (probabilistic signature scheme)，这个是可以被认为是安全的算法，但是对于上面那种简单方案我也没有听说过有效的攻击方式，有兴趣的可以再了解一下

RSA 加密与 RSA 数字签名

下面复述一下上面的内容，RSA 签名方案在"教科书"中的内容是这样的：

    Enc(m; K) = R(m,K)
    Dec(c; k) = R(c,k)
    Sign(m; k) = R(m,k)
    Ver(m; s; K) = R(s,K) == m

在同样的算法中，这些是实际的实现方案

    Enc(m; K) = R(OAEP-pre(m),K)
    Dec(c; k) = OAEP-post(R(c,k))
    Sign(m; k) = R(H(m),k)
    Ver(m; s; K) = R(s,K) == H(m)

根据上面这些内容，让我们考虑一下 RAS 签名和 RSA 解密。签名算法和解密算法是不是一样的呢？在实际的应用方案中，很显然是不一样的，签名引入了一个哈希函数 H, 解密引入了一个后处理函数 OAEP-post。在签名种 H 是直接应用与消息内容 m 的，然后再执行 RSA 函数。在解密过程中，这个 RSA 函数是先执行的，然后在执行了 OAEP-post 后处理函数。同样的，RSA 验签也是和 RSA 加密显然也是不一样的。

但是，通过另外一种方式来对比 RSA 签名和 RSA 的相似之处：他们都引入了 RSA 函数以及一个私钥 k 作为参数，同样的 RSA 验签和 RSA 加密也同样引入了 RSA 函数以及一个公钥 K 作为参数。这样就可以看到教科书种所阐述的那种算法了。

总结

在教科书的这种抽象的世界里，RSA 签名和 RSA 解密确实是做了同一件事情。但是在现实的实现过程中，他们并不是一样的。因此，永远不要使用现实世界种的 RSA 解密来计算RSA签名。在最好的情况下，这种的实现方式将以自己可以注意到的方式而中断。在最坏的情况下，这将引入攻击者可以利用的漏洞。

还有就是文章开头提到的描述问题，对于很多非对称加密算法中，是无法实现私钥 “加密”，公钥 “解密”。但是由于 RSA 算法特殊性，从数学的定义上来讲是可以实现私钥 “加密”，公钥 “解密”。所以不能错误的将 RSA 泛化，得出任何非对称加密算法都可以作为数字签名算法的错误结论。除了 RSA 加密算法有这种特性以外，ElGamal 加密算法也有这种特性，但并不是一个普遍的现象。从加密的目的上来讲，加密是为了保证数据不被他人发现，而 RSA 中公钥是任何人都可以获得的，也就是说任何人都可以解密私钥加密的内容，本身就违背了加密的作用。所以私钥只能是用于签名，公钥来验签。

参考链接：

https://www.cs.cornell.edu/courses/cs5430/2015sp/notes/rsa_sign_vs_dec.php
https://crypto.stackexchange.com/questions/66770/understanding-public-key-and-private-key
https://crypto.stackexchange.com/questions/2123/rsa-encryption-with-private-key-and-decryption-with-a-public-key
https://blog.csdn.net/taolinke/article/details/6432228
https://copyfuture.com/blogs-details/20200401195558268g4s20sqvd2skzqp