#1 楼
首先，数字理论教科书在这里可能会有所帮助。我拥有《数字理论导论》，这将为您提供这个以及许多其他数字理论主题的基础，这些主题都以加密货币形式出现。这不是我最喜欢的书本书写方式，但是涉及的主题非常全面。存在一个称为除法定理的定理，该定理说任何数$ n = pq + r $，约束条件为$ n> q> r \ geq 0 $。简而言之，任何数字$ n $都可以由商$ q $（可能乘以数字$ p $）和余数$ r $来表示。一个例子是说$ 13 = 7 + 6 $-您会意识到，因为$ 13/7 $可以写为“ $ 1 $剩余$ 6 $”。关闭$ 13 \ equiv 6 \ mod 7 $。直观地，模块化算术通常被解释为“您取余数，这就是结果”，这与事实相差不远-实际上，我们说的是$ 7 $和$ 13 $是同一同余类的一部分-也就是说， $ q $和$ r $（$ 7 $和$ 6 $）保持不变，一致性类由所有$ p $的所有$ n $组成。因此，对于$ p = 2 $，$ n = 2 * 7 + 5 = 19 $。因此，$ 19 \ equiv 5 \ mod 7 $（可以随意检查！）。所以，您担心的是在RSA中使用$ \ mod \ phi（n）$-通常给出的表达式是$ de = 1 \ mod \ phi（n）$。我们可以用除法定理形式将其重写为$ de = k \ phi（n）+ 1 $-其中$ k $是上一个示例中的$ p $，但为了避免与素数$ p $形成$ n $。
现在观察您可能已了解的指数-$ x ^ {a + b} = x ^ ax ^ b $和$ x ^ {ab} =（x ^ a）^ b）$如果您不确定，请选择数字示例。现在，加到幂$ de $的消息$ m $是$ m ^ {de} $-但对于$ de $我们已经有了一个不同的表达式-即-$ m ^ {de} = m ^ {k \ phi（n）+ 1} $。然后可以写成$（m ^ {\ phi（n）}）^ k \ times m ^ 1 $。
有一个很好的理由可以使这种形式令人满意-即对费马小定理的Euler-Fermat推广，其中指出：
$$ a ^ {\ phi（n）} = 1 \ mod n $$。
希望您能看到我们操纵代数以获取$ m ^ {\ phi（n）} $绝不是偶然的-因为在$ \ mod n $下，$（m ^ {\ phi（n）}）^ k \ times m ^ 1 $变成$ 1 ^ k \ times m ^ 1 = m $。这就是使RSA像以前那样工作的原因。对私钥的要求是$ de = 1 \ mod \ phi（n）$-或$ de = 1 + k \ phi（n）$。显然，$ k $可以是我们喜欢的任何数字-该关系适用的任何同余类都适用。
两个数字的最小公倍数是最小的可能数，因此这两个数字都将其相除-例如，$ 4 $和$ 6 $的最小公倍数是$ 12 $。在这种情况下，我们观察到$ 4 $除以$ 12 $，$ 6 $也是如此。现在，$ p-1，q-1 $的最小公倍数是一个数字，使得$ p-1 $和$ q-1 $都将它除以-$ \ phi（n）$是这样一个数字首发！但是，（由于雨披），我们可以说它不是最小的数字。为了解释这一点，请考虑$ p $是一个奇数，并且对于某些$ k $，所有奇数都可以写成$ 2k + 1 $的形式。如果我们减去一个，我们剩下的偶数将至少有一个因数$ 2 $。因此，由于$ p-1 $和$ q-1 $都是偶数，并且都具有两个因数，因此它们的乘积（$ \ phi（pq）$）至少具有两个因数$ 2 $，即2至少需要什么。更一般地，最低公倍数的定义使用算术的基本定理来证明，lcm实际上等于每个素数在每个素数的素数展开中提高到的最大乘方的乘积-eurgh，是吗？好吧，让我们来看一下。我之前选择了$ 4 $和$ 6 $-现在的主要展开式是$ 4 = 2 ^ 2 $和$ 6 = 2 \ x 3 $。取每个素数的最大幂，$ 2 ^ 2 \ times 3 = 12 $。但是，如果我们进行了$ 4 \ times6 = 2 ^ 2 \ times 2 \ times 3 = 2 ^ 3 \ times 3 $，我们看到我们获得了额外的不必要的因数$ 2 $。可以再次将Euler-Fermat泛化泛化为Carmichael定理，其中指出： br />其中$ \ lambda（n）$是该表达式为true的最小整数。稍微走弯路-$ \ phi（pq）= \ phi（p）\ phi（q）$，由于$ \ phi（p）= p-1 $，因此我们最终得出了$ \ phi（pq ）=（p-1）（q-1）$。现在，在一般情况下，结果是$ \ lambda（pq）= lcm（\ lambda（p），\ lambda（q））= lcm（p-1，q-1）$。通过与$ \ phi（pq）$的情况相同的推理，$ de = 1 \ mod \ lambda（pq）$允许我们将$ m ^ e $转换回$ \ mod n $下的$ m $。 br />
fgrieu使用了“ Rings”一词-如果您对此感兴趣，我强烈推荐Rings，Fields和Groups，这可能是我读过的最好的数学教科书。它是关于（抽象）代数的，还涵盖了一些数字理论上的要点，但不如纯粹的数字理论教科书那么多。
评论
$ \ begingroup $
注意：$ \ phi（n）$永远不是最小的数（假设n至少具有两个不同的奇数素数，因此$ lcm（p-1，q-1）<（p -1）（q-1）$将始终成立（因为（p-1）和（q-1）都以2为因数）。
$ \ endgroup $
–雨披
2012年2月1日于17:43
$ \ begingroup $
@雨披啊。我将对其进行编辑。我太在意我的解释了，错过了明显的地方。谢谢 ：）
$ \ endgroup $
–user46
2012年2月1日下午17:51
#2 楼
在RSA中，如果满足以下条件，则公钥为$ e $，私钥为$ d $：$ ed = 1 \ mod {\ phi（n）} $
要重新排列：
$ d = e ^ {-1} \ mod {\ phi（n）} $
在公钥系统中，应该这样人们不能从公共密钥计算出私钥。因此，至少应将变量之一保持私有。在上面的等式中，每个人都知道$ e $，每个人都可以计算逆，如果您将$ n $作为模数，那也将众所周知，允许任何人计算$ d $。
使用$ \ phi（n）$作为模数的原因是假定仅给定$ n $很难计算$ \ phi（n）$，但是如果您知道$ p则很容易计算$和$ q $，使得$ n = pq $：$ \ phi（n）=（p-1）（q-1）$。本质上，计算$ \ phi（n）$的最简单方法是将$ n $分解为$ p $和$ q $，然后对其进行计算。 $ \ phi（n）$，但这应该可以帮助您入门。
评论
$ \ begingroup $
自由地扭转了第一句话的含意。另一方面，这是不正确的。请使用$ n = 55 $，$ e = 3 $，$ d = 7 $组成一个有效的RSA密钥，但是使用$ e \ cdot d \ not \ equiv 1 \ pmod {\ phi（n）} $
$ \ endgroup $
–fgrieu♦
2012年2月3日，下午5:57
$ \ begingroup $
为什么没有全等？
$ \ endgroup $
–user5507
2012年2月4日，下午3:31
$ \ begingroup $
@ user5507：$ e \ cdot d \ equiv 1 \ pmod {\ phi（n）} $对于$（n，e，d）$是有效的RSA密钥是足够的，但不是必需的条件。在我上面的反例中，它不成立。当$ n $是不同奇质数$（p，q）$的乘积时，$（n，e，d）$作为有效RSA密钥的充要条件是$ e \ cdot d \ equiv 1 \ pmod {LCM（p-1，q-1）} $，在我的反例中，该等价$ \ pmod {20} $成立。
$ \ endgroup $
–fgrieu♦
2012年2月4日在11:01
#3 楼
通常，人们希望通过解密通过对纯文本进行加密而获得的密文来获取纯文本。 n）$和NOT与$ d = e ^ {-1} \ bmod n $。如果该方法不起作用，安全性问题无关紧要。
评论
直觉是指环$ Z_n $中的计算意味着指数可以被认为是错误的。 $ Z _ {\ varphi（n）} $是指数的更合适的环。带有$ \ lambda（n）= LCM（p-1，q-1）$的$ Z _ {\ lambda（n）} $也可以使用，这就是PKCS＃1的用途。