含模指数的密码系统

Question

在我的初级数论课程中，我正在学习“密码学入门”一章，其中我正在研究涉及模幂运算的密码系统。

这本教科书(大卫·伯顿写的)说：

希望隐藏信息的用户可以从选择一个(大)素p作为加密模开始，选择一个正整数2

有人能为我澄清最后一行(斜体字)吗？可能，通过举例说明为什么不可能区分M和它的大整数同余模p。当M大于p时会发生什么？

Answer 1

有人能为我澄清最后一行(斜体字)吗？

好的，下面是一个非常简单的例子，说明什么会出错。

对于一个非常简单的例子，让我们考虑p=11 (比他们指定的更小，但是它的作用相同，并且使计算更简单)和k=3。

假设我们想加密消息m=2；我们要加密的是计算m^k \bmod p，在本例中是2^3 \bmod 11 = 8 \bmod 11 = 8。然后，在后面的文本中，他们将解释如何解密。

但是，为了回答您的问题，假设我们试图加密消息m=13。在这种情况下，我们将计算13^3 \bmod 11 = 2197 \bmod 11 = 8。也就是说，我们得到了与m=2完全相同的密文；这意味着如果我们得到密文8，我们将无法判断原始m是2还是13 (默认情况下，我们假设它小于p，即m=2)。

事实证明，这种加密方法总是以与m+p完全相同的方式处理任何D17；因此，如果我们得到一条大于p的消息，则始终会有一条较小的消息以同样的方式加密。

顺便提一句，当我计算m^k \bmod p时，我把它写成m^k，然后应用\bmod p操作。该方法适用于这些小玩具实例，但在实际情况下，我们将m^k转化为一系列模乘和平方运算，并在每次乘法/平方后应用模运算。这与你的问题无关--我只是试图预测未来可能的混乱根源。