​聊聊密码学中的Padding

前言

用过RSA做加解密的同学一定曾经被RSA的各种Padding所困扰过。NoPadding、PKCS1Padding、OAEPPadding，有的地方说不要用NoPadding，要用PKCS1Padding；有的地方却说PKCS1Padding不安全，要用OAEPPadding...

为什么要有Padding？Padding又是起什么作用？这就得从加密说起。

块加密中的Padding

我们常用的AES、DES等对称加密算法都是基于固定长度的块。比如AES的块大小就固定是16字节。对超过16字节的数据进行加解密时，就需要使用各种分组模式对数据进行分组处理组合。

然而并不是所有的数据都是16字节的整数倍长，因此会经常出现最后一个块不能被填满的场景。加密过的块一定是16字节的整数倍，那如何让解密方能够知道原始数据具体有多长就是个问题了。

有人可能会说这有什么麻烦的，原始数据的最前面贴个length不就行了。

如果需求本身只是把数据填充到指定长度，并保留原始数据的长度本身并不复杂，人们也提出过各种各样的方案。光维基百科里就列出了这么多中方法。

方法多并不是什么好事，大家都用同样的方法才能减少各种对接沟通成本。因此(RFC 5652)http://tools.ietf.org/html/rfc5652#section-6.3中规定了PKCS#7Padding流程，这个流程简单描述就是

末尾填充的每个字节均为填充长度

即如果Padding长度为5，那解密数据尾部就是05 05 05 05 05，即5个05

如果Padding长度为1，那解密数据尾部就是01，即1个01

那如果原始数据正好就是16呢？因为PKCS#7规定Padding必须存在，因此即使原始数据是16的整数倍，也需要在末尾追加16字节的Padding，即正好追加一个块，这个块每个字节都是0x10

当然还有Padding大于255的场景，不过这种场景很少就不再这里细说了。

RSA中的Padding

因为对称加密中的常用的Padding方式基本只有一种那就是PKCS#7。所以通常使用中不会出什么问题。让人困扰的一般都是RSA的Padding。

为什么RSA的Padding总是让人绞尽脑汁呢？因为RSA的Padding不只是Padding。为什么这么说呢？我们上面提到过，Padding最初只是用来填充数据到指定长度。但是在RSA中这个问题复杂化了。

对于常见的对称加密方案中，通常存在下面几个元素

• 加密算法 比如AES
• 分组模式/AEAD模式 比如CBC/GCM
• 密钥
• iv/nonce 随机数

Padding只是作用于分组模式中的小小的一部分，辅助将原始数据填充到指定长度。有的分组方式（比如CTR）甚至不需要Padding。

而RSA通常不会加密特别长的数据，因此没有分组模式的概念，对于RSA来说Padding是分组模式和随机数的合。即RSA的Padding包含了将数据填充到RSA密钥位数的长度的方法，还有填充随机数到RSA原文的方法。

我们知道RSA算法的本质就是大数运算

m^e ≡ c (mod n)
c^d ≡ c (mod n)

其中m是原文，c是密文

如果使用原始的RSA做加解密操作，则并不包含随机数，相同的密文会生成相同的明文。同时由于大部分情况下m相比n小很多，甚至m^e都比n要小，这时候很容易通过枚举倍数破解明文。

因此RSA加解密算法很需要有效的Padding算法将明文填充到足够长保证不容易被暴力破解，同时也需要加入随机因子保证密文的随机性。

PKCS1-v1.5 Padding

根据RFC 3447描述PKCS1-V1.5 Padding

EM = 0x00 || 0x02 || PS || 0x00 || M

其中EM是填充过的消息，M是原文，PS是随机数 长度为RSA len - 3 - M len

方法很简单也很直观。

如果也和对称加密一样大家都用这个Padding方案，那也就不会有各种各样RSA的Padding问题了

然而 PKCS1 Padding存在漏洞

RSA-OAEP和RSASSA-PSS

为了解决PKCS1 Padding的各种问题

人们又针对签名和加密场景分别提出了RSA-OAEP和RSASSA-PSS这两种Padding方案

根据RFC 8017描述 Padding的生成过程相当复杂，有12步。其中包含了生成hash并填充到原文中

这里就不具体描述了

尾声

扯了这么久，估计大家可能还是没搞懂到底有多少种Padding，分别用在什么场景。

总之今后协议对接的场景多注意Padding这个信息就好。