RSA与强RSA假设

Question

RSA假设：

给出随机生成的RSA模n，指数r和随机z \in \mathbb{Z}_n^{*}，找到y，使得y^r=z。

强RSA假设：

给出随机选择的RSA模n和随机z \in \mathbb{Z}_n^{*}，找出r>1和y \in \mathbb{Z}_n^{*}这样的y^r=z。

在强RSA假设中，人们通常说"r可以依赖于z，而在通常的RSA假设中，r可以独立于z“。

在某种程度上依赖z是什么意思？怎样才能达到这样的依赖呢？如果有人能解释这件事我很感激。

即使将一些值替换为n、z等，也会很好，并将帮助我更好地理解。

提前谢谢。

Answer 1

什么是"r可以以依赖z的方式选择“？

一种打破强RSA假设的假设算法\mathcal A_2用RSA密钥生成过程生成的n输入1 1 (n,z)，并输出2 2 (r,y)，使得y^r\equiv z\pmod n成为r中唯一的约束r>1。与一种假设的\mathcal A_1算法相比，该算法打破了RSA假设，该算法使用RSA密钥生成过程生成的(n,r)输入1 1 (n,r,z)，并输出2 2 y，从而使y^r\equiv z\pmod n。

这种区别使得问题不同:假设的算法\mathcal A_2将r构建为r\gets n，这对破解RSA没有明显的作用，因为标准的RSA密钥生成过程从未使用对r的选择。同样，如果\mathcal A_2生成r的函数是z，例如r\gets2\,\lfloor z/7\rfloor+3，因为r与由RSA密钥生成过程生成的r相匹配的概率非常低。

另一方面，我们可以将\mathcal A_1类的假设算法转化为\mathcal A_2类，例如反复尝试增量奇数r\ge3，将(n,r,z)提交给用作子程序的\mathcal A_1，如果在一定时间内输出y，则将(r,y)作为\mathcal A_2的输出。

因此，强RSA假设(即不存在算法2 \mathcal A_2)并不比RSA假设(即不存在算法2 \mathcal A_1)更弱。这些不同的概念是名副其实的！

将可以作为n比特大小的安全参数和随机算法的随机输入进行隐式表示。

2在时间多项式w.r.t内具有不消失的成功概率。安全参数。

它是由C.C. Cocks密码系统使用，早于RSA，并被认为同样安全。