RSA Assumption

RSA 假设由 Rivest、Shamir 和 Adleman 三人于1978年在论文 “A method for obtaining digital signatures and public-key cryptosystems” 中提出，下面给出这个假设的主要内容。

• 运行生成算法：$(N, e, d) \gets GenRSA(1^n)$

  • $N$ 为两个 $n$-bit 的质数（设为 $p$ 和 $q$）的乘积，但 $p$ 和 $q$ 设为秘密值；
  • $gcd(e, \phi(N)) = 1$，其中 $\phi(N)$ 为欧拉函数，若已知 $N$ 的因子则可以很快算出 $\phi(N) = (p-1) \cdot (q-1)$；
  • $ed = 1 \mod \phi(N)$，$d$ 被设置为秘密值。

• RSA 假设：

  • 均匀随机地从 $\mathbb{Z}_N^*$ 中抽取出一个 $y$，并给定$(N, e, y)$；

  • 若仅有公开值，则计算满足 $x^e = y \mod N$ 的 $x$ 是困难的；

  • 若有秘密值 $d$，则 $x$ 可以这样计算：$x = y^d \mod N$，正确性证明如下：

    $$y^d = x^{ed} = x^{k \cdot \phi(N) + 1} = x \mod N$$

    其中第一个等号和第二个等号由定义直接可推出，第三个等号用到了欧拉定理。