对教科书式RSA的CCA攻击

密码学

目标

Programming assignment. You are given an oracle-access to a function dec(c) that inverts the RSA N,d function: on input c it computes m = c^d mod N for all but one ciphertext. We call this ciphertext a challenge-ciphertext c∗. The parameters (N, e, d, c∗ ) are fixed. You’ll find all public parameters in the file ‘params.txt‘. Your task is to decrypt the challenge c*.

任务简述:给定解密oracle $dec(\cdot)$，其可对$C^*$以外的所有密文进行解密操作($dec(C) = C^d \ mod \ N)$.现要求通过某种方法,求出$C^*$对应的明文$M^*$.($e,N$与目标密文$C^*$已给出).

过程

1. 构造一个新的密文$C'= 2 \times C^* (mod \ N)$
2. 用$dec(\cdot)$求解$C'$对应的"明文"$M'( = 2^d \times (C^*)^d = 2^d M^* \mod N)$.(实际上该明文可能不是良构的,没关系)
3. 用$dec(\cdot)$求解$2$对应的"明文" $t (= 2^d \ mod \ N)$.
4. 计算 $t^{-1} \ mod \ N$.
5. 计算 $M^* = M' \times t^{-1} \ mod \ N$.得到$C^*$对应的明文$M^*$

关于CCA攻击

以上是对教科书式的RSA(RSA原语)进行选择密文攻击的一个实例.而其中的oracle在现实中并不是不存在的.实际上,密码学家们提出CCA的概念就是为了对现实某些攻击的抽象.一个很现实的例子是:美国密码学家截获了日本军方的一些密文,虽然他们无法解密,但他们通过了对密文进行修改,发送到日本军方,然后发现他们有了一些动作(比如军队移动等).虽然这个例子中并没有提到密文的解密,但是,很显然日方的动作已经告诉了美军很多东西了.

其实由上面的一个例子不难发现,想要抗选择密文攻击,一个重要的操作便是:对"不合法"的密文进行拒绝.也就是说,当接收方收到一个不合法的密文时,它会把密文拒绝掉(注意,解密oracle是从解密函数中抽出来的,因此解密oracle也会拒绝掉不合法的明文),然后再保证,攻击者以极小的概率构造出一个合法的密文即可.这是一种构造抗CCA的协议的思路.

现在公钥密码协议的构造无一不要求抗CCA攻击,尤其是基于离散对数问题和大整数分解问题假设(比如CDH,DDH,RSA假设)的协议.许多基于这些假设的抗CCA的协议已经被构造出来,甚至还出现了一些通用构造模型.基于格难问题的抗CCA协议也陆续被提出来.总之,抗CCA是密码学协议中十分重要的一个性质.