RSA是否适用于任何消息M？

#1 楼

是的，（教科书）RSA适用于\ {0 \ dots n-1 \} $中的任何消息$ M \，在某种意义上，解密过程可以恢复原始消息；那就是$ \ left（（M ^ e \ bmod n）^ d \ bmod n \ right）= M $。为此，我们需要假设$ p \ ne q $，这是RL Rivest，A。Shamir和L. Adleman的“获取数字签名和公钥密码系统的方法”中未正式陈述的要求，但在压倒性的情况下确实如此给定建议生成$ p $和$ q $的方法，并且由于$ p $和$ q $的长度相差几位数，因此遵循建议时始终为true。

一个简单的证明是考虑$ Z = \ left（M ^ e \ right）^ dM $;通过使用费马小定理和$ e，d，p，q $之间的假定关系来显示$ Z \ equiv 0 \ pmod p $和$ Z \ equiv 0 \ pmod {q} $（请参见下面的补充内容）；然后，由于$ p $和$ q $是截然不同的素数，除以$ Z $，它们的乘积$ n $除以$ Z $；因此$ Z \ equiv 0 \ pmod {n} $。 QED，谢谢KG

注意：通常，$ M ^ e \ equiv M \ pmod {n} $不成立。

注意：如果$ p = q $ ，密码系统是完全不安全的。独立地，通过加密和解密来修改$ p $的非零倍数的那些稀有$ M $。


添加另一个问题：我们要显示$ Z \ equiv0 \ pmod p $，即$ \ left（M ^ e \ right）^ dM \ equiv 0 \ pmod p $，即$ M ^ {e \ cdot d} \ equiv M \ pmod p $。由于$ d $和$ e $是大于$ 1 $的整数，因此如果$ M \ equiv0 \ pmod p $;成立。仅在$ M \ not \ equiv0 \ pmod p $时才有必要证明这一点，我们在以下假设。

原始的RSA文章使用$ e \ cdot d \ equiv1 \ pmod {\ phi（n）} $构造$ d $和$ e $，其中$ \ phi $是欧拉totient，也称为$ \ varphi $；尽管现代的RSA展示，包括RSA Security的PKCS＃1，经常使用$ e \ cdot d \ equiv1 \ pmod {\ lambda（n）} $，其中$ \ lambda $是Carmichael函数。我们假设$ p $和$ q $是不同的素数，因此$ \ phi（n）=（p-1）\ cdot（q-1）$和$ \ lambda（n）= \ operatorname {lcm}（ p-1，q-1）$。因此，$ p-1 $将$ \ phi（n）$和$ \ lambda（n）$相除，并且对于$ d $和$ e $的任一种构造，它都认为$ e \ cdot d \ equiv1 \ pmod {{p -1）} $。由于$ e $和$ d $是大于$ 1 $的整数，因此它存在一个正整数$ k $，其中$ e \ cdot d = k \ cdot（p-1）+ 1 $。

因此我们可以将$ M ^ {e \ cdot d} $写为$ M ^ {k \ cdot（p-1）+1} = \ left（M ^ {p-1} \ right）^ k \ cdot M $。费马的Little Therorem所著，由于$ p $是质数，而$ M \ not \ equiv0 \ pmod p $是质数，因此它持有$ M ^ {p-1} \ equiv1 \ pmod p $。随之而来的是$ M ^ {e \ cdot d} \ equiv M \ pmod p $。


以下注释：RSA有时以$ \ Bbb {Z} _n ^ *表示。 $因为：


早期版本的Rivest，Shamir和Adleman的论文就这样做了。 br />删除了$ n $的任何假设，从而使证明更简单；相比之下，我们需要一个无平方的$ n $才能使RSA在$ \ Bbb {Z} _n $中工作。

#2 楼

根据中国剩余定理，只要RSA对模$ p $和对模qq起作用，RSA便“起作用”。即$（M ^ e）^ d = M $模$ p $和模$ q $。如果$ M $不是$ p $的质数，则$ p $除以$ M $（因为$ p $是质数）；在这种情况下，该等式变为$ 0 = 0 $，成立。

即使它对任何$ M $都不起作用，也不会有问题，因为在1到1之间找到了和$ n-1 $而不是$ n $的质数等效于分解$ n $，分解$ n $意味着非常困难。但是无论如何，RSA仍然适用于这些整数。

#3 楼

是的，RSA适用于每一个M。请记住费马小定理：

$ x ^ p = x \ mod p $（对于所有$ x $和所有素数$ p $）。

归纳法可以简单地扩展一下：

$ a = 1 \ mod p-1 $意味着$ x ^ a = x \ mod p $（对于所有$ x $和所有素元$ p $）。

现在，我们知道$ d $和$ e $之间的关系是：

$ d·e = 1 \ mod lcm（p- 1，q-1）$

因为$ p-1 $是$ lcm（p-1，q-1）$的因数，所以这意味着

$ d· e = 1 \ mod p-1 $

，因此

$ M ^ {d·e} = M \ mod p $$

对称，这也意味着

$ M ^ {d·e} = M \ mod q $

，因此，根据中国剩余定理（并且$ p $和$ q $是相对质数）：

$ M ^ {d·e} = M \ mod p·q $

$ \ blacksquare $

#4 楼

我在Udacity的示例中找到了一个很好的解释，因此我将对帖子进行一些修改和格式化。 />素数$ p_1 = 11 $，$ p_2 = 13 $ $ N = p_1 \ times p_2 = 143 $
$ \ phi（N）=（p_1-1）\ times（p_2-1）= 120 $
$ e = 7 $ //被选择为$ \ phi（N）$的质数，因此它具有反函数
$ d = 103 $ //从$ e $和$ \ phi（ N）$通过扩展的欧几里德算法
$ e \ times d = 721 = 6 \ times \ phi（N）+1 = 1 \ pmod {\ phi（N）} $

对于任何$ i \ in [0,142] $，$ i ^ {721} \ pmod {143} = i $都会发生。这是一件好事，因为否则解密将无法正常工作。 pmod {N} $-并从等式中消除这些力量，您自己便会拥有$ x $。

对于像$ 26 $这样的具有模数公因子的数字，加密/解密碰巧在此示例中起作用：$ 26 ^ {721} \ pmod {143} = 26 \ pmod {143} $。但这不能用欧拉定理来解释，因为$ gcd（26,143）= 13 $。

那为什么工作呢？应该行吗？ RSA要求它起作用吗？

忘掉Euler定理-它看起来很有希望，但在这种情况下是死胡同。
我们将使用Fermat的小定理。
我们还需要使用以下事实
$ a \ equiv b \ pmod {p_1} $和$ a \ equiv b \ pmod {p_2} \ Rightarrow a \ equiv b \ pmod {p_1 \ times p_2} $。让我们将其称为事实X。
请记住，$ e \ times d = 1 \ pmod {\ phi {N}} \ Leftrightarrow e \ times d-1 = k \ times（p_1-1）\ times（p_2- 1）\ Leftrightarrow e \ times d -1 = 6（11-1）（13-1）$。
方程的$（p_1-1）$和$（p_2-1）$部分将是

$ m ^ {ed} = m ^ {ed-1} \ times m = m ^ {k（p1-1）（p2-1））\ times $
如果$ m \ equiv 0 \ pmod {p_1} $，则Fermat的小定理不适用。但是$ m ^ {ed} \ equiv 0 \ pmod {p_1} $。
例如：$ 22 \ equiv 0 \ pmod {11} $。 $ 22 ^ {721} \ equiv 0 \ pmod {11} $。
如果$ m \ neq 0 \ pmod {p_1} $，则Fermat确实适用（我们在这里使用$ \ pmod {p_1} $ ）：
$ m ^ {ed} = m ^ {k（p_1-1）（p_2-1）} \ times m = {m ^ {（p_1-1）}）^ {k（p_2-1 }} \ times m = 1 ^ {k（p_2−1）} m = m $。
以上两种情况得出的结果是$ m ^ {ed} \ equiv m \ pmod {p_1} $。
对$ p_2 $应用相同的推理。
然后使用上面的FACT X来显示$ m ^ {ed} \ equiv m \ pmod {p_1 \ times p_2} $。

回到示例：

$ m ^ {ed} = m \ times m ^ {ed−1} = m \ times m ^ {720} = m \次m ^ {6 \次10 \次12} = m \次（m ^ {10}）^ {72} = m \次（m ^ {12}）^ {60} $。
$ gcd（m，11）= 1 $，则费马证明，采用$ m ^ {ed} \ pmod {11} $就像乘以$ 1 $。如果$ gcd（m，11）\ neq 1 $，则乘以$ 0 \ pmod {11} $并以零结尾。

与mod 13类似。

然后FACT X将两者结合起来，表明使用$ m ^ {ed} $会使消息保持不变$ \ pmod {11 \ times 13} $。

#5 楼

即使明文$ x $不能与$ p $或$ q $成对互质，RSA仍然可以像宣传的那样工作。原因如下：

$ p $和$ q $是质数，因此，鉴于$ x
假设$ x \ equiv 0 \ pmod p $。如果与$ 0 $ mod $ q $一致，则仍然适用以下内容，只需切换分配给两个素数的名称。

$ x ^ k \ equiv 0 \ pmod p $ for $ k> 0 $，即$ x ^ k \ equiv x \ pmod p $。

$$
\开始{align *}
x ^ {1+ z \ phi（n）}和\ equiv x ^ {1+ z \ phi（p）\ phi（q）} \\
＆\ equiv x ^ 1 \ cdot x ^ {\ phi（q）\ phi（p）z} \\
＆\ equiv x \ pmod q
\ end {align *}
$$$

将这两个方程与中国剩余定理结合使用，得出纯文本$ x $。