阅读排行

OAEP及其在OpenSSL中的实现

1.RSA

RSA是一种经典的公钥密码体制，可以用来做加密或者签名。设RSA的公私钥对为 $(e,n)$ 和 $(d,n)$ ，在RSA加密过程中，使用公钥对消息m进行加密： $c=m^{e} mod\ n$ ；使用私钥对密文c进行解密： $m=c^{d}mod\ n$ 。在签名过程中公钥和私钥的使用顺序是相反的，即使用私钥进行签名，使用公钥验证签名。
但是，上述RSA加密方案存在着易被篡改的问题，假设敌手在密文 $c$ 的传输过程中将 $c$ 随机乘上了一个数（设为 $s$ ），那么消息的接收方最后解密得到的明文将会是 $m\cdot s^{d}mod\ n$ 而不是原先的消息 $m$ ，因此应该在RSA加密中加入一种验证机制。
这种认证可以通过填充机制完成，即通过对消息进行填充使得其满足某种特定的格式。当敌手对密文进行修改时，由于其不知道密文对应的明文，因此修改之后得到的明文符合填充标准的概率是一个很小的数（可以近似看作随机挑选一段字符满足填充格式的概率），这样，填充机制就完成了对消息的验证。
从另一个角度看，在进行RSA加密的过程中需要通过加入随机数使得其满足可证明安全理论中的IND-CPA安全。简单地说，给定两个随机明文 $m_{1}$ 和 $m_{2}$ ，将它们都使用相同的公钥进行加密，并随机的选择一个密文记作 $c$ ，现在我们需要猜测 $c$ 是哪个密文加密的结果，如果在加密过程中不引入随机数，那么只需要将 $m_{1}$ 和 $m_{2}$ 分别使用公钥进行加密即可区分，也就是说，RSA加密的密文和公钥至少泄露了其中1bit的信息，因此我们需要引入随机数进行填充。

2.OAEP：最优非对称加密填充

OAEP是RSA填充的一种模式，在PKCS#1v2.0(PKCS#1标准现在已经升级到2.2版本）中提出，用于取代原先的PKCS#1v1.5版本中的填充机制，其填充过程如下：

2.1输入

在执行填充之前，需要提供两个函数：一个密码学杂凑函数（记作hash）和一个掩码生成函数（ $MGF$ ,mask generation function）;填充时的输入主要包括RSA的公钥 $(e,n)$ 、需要被填充的信息( $M$ )以及一个可选的参数标签（记作L）。
我们将hash函数的输出长度记作 $hLen$ 。

2.2加密过程

检查长度：在标准的执行流程中首先需要对输出缓冲区的长度进行检查，以确定输出缓冲区能够进行M的填充（这个缓冲区的长度一般等于RSA模数的长度）。在PKCS#1v2.2中规定了两方面的检查，
- a)：L的长度不应该大于hash函数的输入限制（比如对于SHA-1而言这个输入限制是 $2^{61}-1$ 字节）。
- b)：输出缓冲区的长度应该最少为 $Len(M)+2hLen+2$ ，也就是说，输入缓冲区至少应该比消息长度长 $(hLen+2)$ 字节。
Encoding：
如上图所示，这一过程可以分为如下步骤：
- a)：若参数中没有提供标签L,则使用一个空字符串作为L,并计算 $lHash=hash(L)$ 。将 $lHash$ 放到内存区域 $DB$ 中， $DB$ 开始于输出缓冲区的第（ $hLen+2$ ）字节，其长度为（ $outlen-1-hLen$ ），记为 $DB\_len$
- b)：对从 $DB[hLen]$ 开始直到 $DB[DB\_len-M\_len]$ 之间的内存区域进行填充，将这段内存中除了最后1字节之外的字节填充为0x00,最后一字节填充为0x01,之后将 $M$ 复制到剩余的内存区域中。
  此时 $DB$ 的结构为：hash||PS||0x01||M,PS的内容全为0x00
- c)：将 $seed$ 填充为随机字符串。
- d)：以 $seed$ 为参数调用 $MGF$ 生成 $DB$ 的掩码，之后使用这个掩码和 $DB$ 按位异或，得到新的 $maskedDB$ 。
- e)：以 $maskedDB$ 为参数调用 $MGF$ 生成 $seed$ 的掩码，之后和 $seed$ 进行按位异或得到 $maskedseed$ 。
- f)：将输出缓冲区的第一字节设为0x00，得到填充之后的消息：0x00|| $masked seed$ || $masked DB$ 。
对密文进行加密：PKCS#1v2.2中提供了三种加密模式，可以选用其中的任意一种。

2.3校验过程

校验过程需要的材料和填充过程是类似的，包括一致的hash函数和 $MGF$ 。

检查长度：
- a) 标签L的长度不应该长于hash算法输入的最大长度。
- b) 密文的长度应该和RSA中模数 $n$ 的长度相一致。
- c) 密文的长度应该长于 $2hLen+2$ 。
对密文进行解密：
采用与加密过程中步骤3)一致的模式对密文进行解密。
对明文进行解码：
- a) 若没有给定L，则设L为一个空字符串，并计算 $lHash=Hash(L)$
- b) 将得到的明文 $m^{‘}$ 拆分为 $Y||maskedSeed||maskedDB$ ,其中 $Y$ 为解密得到的消息的第一字节， $maskedSeed$ 的长度为 $hLen$ ，其余部分为 $maskedDB$
- c) 计算 $seedmask=MGF(maskedDB,hlen)$
- d) 得到 $seed=maskedseed \otimes seedmask$
- e) 计算 $DB$ 的掩码： $DBmask=MGF(seed,LengthOf(M^{‘})-hlen-1)$
- f) 得到 $DB$ ： $DB=maskedDB \otimes DBmask$
- g) 验证 $DB$ 是否符合如下的形式： $DB=lHash||PS||0x01||M$ ，其中 $PS$ 中的每一个字节均为0x00，当以上条件均符合而且明文的第一个字节（ $Y$ ）也为0x00时，将 $M$ 取出作为明文信息，判定OAEP验证成功，解密成功。

3.OpenSSL对OAEP的实现

RSA_padding_add_PKCS1_OAEP_mgf1

该API用于将一个希望使用OAEP进行填充的明文进行处理，并将处理后的明文输出

int RSA_padding_add_PKCS1_OAEP_mgf1(
unsigned char *to, int tlen,//填充后消息存放的内存区域
const unsigned char *from, int flen,//消息本身存放的内存区域
const unsigned char *param, int plen,//参数所在内存
const EVP_MD *md, const EVP_MD *mgf1md)//密码学杂凑算法

检验长度的代码：

if (flen > emlen - 2 * mdlen - 1) {error...}
//其中emlen=tlen-1，确定输出缓冲区（实际上也就是RSA的模数n）的长度符合对明文编码的最基本要求，padding部分至少要有一个0x01.
if (emlen < 2 * mdlen + 1) {error...}
//当emlen-2*mdlen-1<0的时候上面的条件也可能为true,我们应该防止这种情况的发生。

对to的各个部分进行填充

to[0] = 0;//第一字节置为0x00
seed = to + 1;//to[1]作为种子的起始地址
db = to + mdlen + 1;//to[1+mdlen]作为DB的起始地址，也就是说种子的长度为mdlen
//使用hash(param)对DB的前mdlen个字节进行填充，也就是hash(L)
if (!EVP_Digest((void *)param, plen, db, NULL, md, NULL))
    return 0;
//从刚才hash(L)的下一字节开始填充0x00,填充的长度为除了固定的开头0x00,明文及之前的0x01以及seed和hash(L)之外剩余的内存区段长度。
memset(db + mdlen, 0, emlen - flen - 2 * mdlen - 1);
db[emlen - flen - mdlen - 1] = 0x01;
//将Plaintext复制过去
memcpy(db + emlen - flen - mdlen, from, (unsigned int)flen);
if (RAND_bytes(seed, mdlen) <= 0)//生成随机数作为seed
        return 0;
//现在to的内容为：0x00||seed||hash(L)||PS||0x01||Plaintext,其中PS为填充字符串，均为0x00

进行掩码的生成和异或处理

//使用seed生成DB的mask并进行异或
if (PKCS1_MGF1(dbmask, emlen - mdlen, seed, mdlen, mgf1md) < 0)
    return 0;
for (i = 0; i < emlen - mdlen; i++)
        db[i] ^= dbmask[i];
//使用maskedDB生成seed的mask并进行异或
if (PKCS1_MGF1(seedmask, mdlen, db, emlen - mdlen, mgf1md) < 0)
        return 0;
for (i = 0; i < mdlen; i++)
        seed[i] ^= seedmask[i];

RSA_padding_check_PKCS1_OAEP_mgf1

int RSA_padding_check_PKCS1_OAEP_mgf1(
unsigned char *to, int tlen,
const unsigned char *from, int flen,
int num,//多了一个参数，该参数指RSA模数n的长度 
const unsigned char *param,int plen, 
const EVP_MD *md,const EVP_MD *mgf1md)

还是需要先对长度进行检查

//严格的说，应该有num>=flen+1,因为刚才OAEP填充的时候第一字节是0x00
//num必须满足最小长度要求
if (num < flen || num < 2 * mdlen + 2)
        goto decoding_err;

进行掩码的计算

//将from复制到em中，em的长度为num，前面的位被填充为0x00
//为了对抗Mayer在CRYPTO‘01上提出的选择密文攻击，不能让敌手知道第一字节是不是0x00,因此这里需要做一下特殊处理，即使第一字节不是0x00(说明填充肯定不合法)，计算流程也将继续，而不是报错之后跳出
good = constant_time_is_zero(em[0]);
maskedseed = em + 1;
maskeddb = em + 1 + mdlen;
//计算seed的掩码，并将其与maskedseed异或，得到seed
if (PKCS1_MGF1(seed, mdlen, maskeddb, dblen, mgf1md))
        goto cleanup;
for (i = 0; i < mdlen; i++)
        seed[i] ^= maskedseed[i];
//计算DB的掩码，并将其欲maskedDB异或，得到DB
if (PKCS1_MGF1(db, dblen, seed, mdlen, mgf1md))
        goto cleanup;
for (i = 0; i < dblen; i++)
        db[i] ^= maskeddb[i];

对DB中的内容进行验证

//计算标签对应的hash值hash(L)
if (!EVP_Digest((void *)param, plen, phash, NULL, md, NULL))
        goto cleanup;
//将hash(L)和DB中的标签值作比较
good &= constant_time_is_zero(CRYPTO_memcmp(db, phash, mdlen));
//对于之后的padding bytes进行检查
found_one_byte = 0;
for (i = mdlen; i < dblen; i++) {
    unsigned int equals1 = constant_time_eq(db[i], 1);
    unsigned int equals0 = constant_time_is_zero(db[i]);
    one_index = constant_time_select_int(~found_one_byte & equals1,i, one_index);
    found_one_byte |= equals1;
//只有在找到了0x01的情况下，之后的字节才可以不是0x00
//当没找到0x01时出现了非0x00的字节则直接判定验证失败
    good &= (found_one_byte | equals0);
    }
//还有一种极端情况就是后面的字节都是0x00，此时也判定验证失败
    good &= found_one_byte;

之后，one_index之后的字节就是需要被解码的Plaintext了！

PKCS1_MGF1

int PKCS1_MGF1(
unsigned char *mask, long len,//mask的缓冲区
const unsigned char *seed, long seedlen,//用于产生掩码的种子 
const EVP_MD *dgst)//用于产生掩码的杂凑函数

这个函数的执行若干次dgst中的杂凑函数，得到out=hash(seed||cnt)，其中cnt是代表hash函数执行次数的计数器，直到将整个mask填满为止。

4.参考文献

PKCS#1v2.2标准
 OpenSSL项目主页
 对于OAEP的选择密文攻击

文章来自：http://blog.csdn.net/github_35454460/article/details/51862470