密码学基础 -- RSASSA-PSS盐值长度大揭秘

盐值长度选择的疑惑
PSS填充解读
PSS盐值长度推导
小结

1. 盐值长度选择的疑惑

RSA签名有两种填充方式：PKCSV1.5和PSS。

其中，PSS （Probabilistic Signature Scheme）是RFC 3447中定义的一种签名方案。它比PKCSV1.5更复杂，且有安全性证明。这是RSA签名的推荐填充算法，但要注意PSS不能用于RSA。

在python/Cryptography库中，签名具体代码实现如下：

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding
message = b"A message I want to sign"
signature = private_key.sign(               message,          
padding.PSS(                  mgf=padding.MGF1(hashes.SHA256()),                  salt_length=padding.PSS.MAX_LENGTH                  
),          
hashes.SHA256())

其中，填充模式选择PSS，而PSS需要输入参数，分别是：

mgf：生成掩码的函数，目前仅支持MGF1，函数内部使用Hash算法为SAH256（也可选择其他hash算法）；
salt_length：盐值长度，推荐选择DIGEST_LENGTH和MAX_LENGTH。
那么这个DIGEST_LENGTH和MAX_LENGTH应该如何理解呢？我们还是需要从标准中找寻答案。

2. PSS填充解读

之前讲过关于RSA加密、签名对原始数据进行编码的细节，这里再次回顾一下PSS的encode步骤，也有了很多新的问题。

我们知道签名就是用私钥进行加密，公式为 s = m^d mod n，其中，这个m就是上图中编码后的EM。EM的来源按如下步骤进行：

判断原始数据message长度是否超过Hash函数的限制长度，如超出了直接停止，签名失败；如没有则进行第2步；
对原始数据M做摘要计算，得到mHash，长度为hLen；
如果 emLen < hLen + sLen + 2，直接停止，签名失败；否则进行第4步。（出现了第一个问题：这个公式是哪里来的？）
根据sLen长度生成随机数作为盐值Salt，sLen = 0，Salt就为空；
拼接 M* = Pad1 || mHash || Salt，其中Pad1 = 8个0x00；
再次对M*做同样摘要计算，得到H；
生成PAD2，长度为emLen-sLen-hLen-2，值统一填充为0x00，pad2长度可能为0；
拼接DB = Pad2 || 0x1 || Salt，dbLen = emLen - hLen - 1；
利用MGF对M*的Hash(H)做计算，一般MGF使用的Hash函数与签名使用的一致，得到dbMask，长度等于dbLen；
maskedDB = DB ⊕ dbMask；
设置maskedDB最左边的(8*emLen - emBits)位为0；
拼接 EM = maskedDB || H || 0x bc，最后签名s = EM^d mod n

在上述步骤里，盐值长度sLen，其实是作为输入参数给进来的，那为什么python库还有长度限制呢？

这得从RSA公式说起，s = m^d mod n，m必须小于模数n。在模运算中，任何数的任意次幂再对同一个数取模，结果都不会超过这个数；如果m大于模数n，那么m可以表示为m = k* n + r，k是非负整数，此时m^d mod n = (k*n + r)^d mod n。
由于k*n是n的倍数，任何n的倍数模n都等于0，故m^d mod n = r^d mod n，这意味着形如 k* n + r的m值在签名后都会得到相同结果 r^d mod n。
假设模数 n = 7，私钥指数 d = 3，
假设 m1 = 2，签名 s = 2^3 mod 7 = 1；
假设 m2 = 9，签名 s = 9^3 mod 7 = (1*7 + 2)^3 mod 7 = 1
假设 m3 = 16，签名 s = 16^3 mod 7 = (2*7 + 2)^ 3 mod 7 = 1
这显然是不合理的，不同数据居然有同样的签名，因此m必须小于n

有了这个理论限制，在PSS填充时盐值长度其实就有限制了。

3. PSS盐值长度推导

首先我们明确，在构建EM(Encode Message)时最后一个Byte固定为0xbc，因此emLen = modBit/8 - 1，同时为了避免所谓的“填充攻击”（padding oracle attacks，攻击者可能会尝试利用编码消息的边界条件来提取加密信息），实际参与到PSS编码的bit长度为modBit - 1。

为什么在Step 3 要求emLen > hLen + sLen + 2?

我们从结果反推，EM = maskedDB || H || 0x bc ，其中H的长度 = hLen，maskedDB长度 = pad2Len + 1(0x01) + sLen。

以边界情况为例，假设pad2Len = 0，那么整体EM长度就为hLen + sLen + 2(0x01 和0xbc两个字节)。

那么sLen = DIGEST_SIZE\ MAX_SIZE为对EM结果造成什么影响？我们继续推演。

假设现在采用RSA1024-SHA512进行签名，选用DIGEST_SIZE，模数长度1024，SHA512 的hLen = 512，sLen = 512 ，这种情况下emLen = 1024/8 < 512/8 + 512/8+ 2，按理说就没有办法继续编码签名了，那假设我非要这么搞呢？在代码里也可以重新构建sLen，只需要做个判断，

   if (emlen >= (hlen + hlen + 2)) {        
   slen = hlen;    
   } else {        
   slen = emlen - hlen - 2;    
   }

假设RSA1024-SHA512, emLen = 1024/8 = 128, hLen = 512/8 = 64, 如果sLen = hLen，则emLen < hLen + sLen + 2，所以这种情况用DIGEST_SIZE是错误的，sLen = emLen - hLen - 2= 128 - 64 - 2 = 62，自动转为了MAX_SIZE，这是特殊情况。
假设RSA2048-SHA512, sLen = Hash Size，hLen = 512/8 = 64, emLen = 256 > hLen+hLen+2，sLen= hLen = 64，这时候DIGEST_SIZE就有效了，在第五步拼接M*的时候，M*Len = 8(PAD1Len) + mHash(64)+sLen(64)，由于sLen为64，HLen = 64，maskedDBLen = 256 - 64 -1 = 191，从而可以推导出Pad2Len = 191 - 64（sLen） - 1(0x01) = 126，故DB = 0x00(126个) || 0x01 || Salt(64个)。
假设RSA2048-SHA512，选用MAX_SIZE；这种情况下，sLen = emLen - hLen - 2 = 256-64-2 = 190 bytes，从而Pad2Len = 256(emLen) - 64(Hlen) - 1(0xbc) - 1(0x01) -190(sLen) = 0，也满足step7。