cryptography - 模运算

Question

我是密码学和模算术的新手。所以，我敢肯定这是一个愚蠢的问题，但我无能为力。

如何从      pow( a , q ) = 1 (mod p )计算a ， 其中p和q是已知的？我没有得到“1 (mod p )”部分，它等于 1，不是吗？如果是这样，那么“mod p ”是关于什么的？ 这是否与      pow( a , -q ) (mod p ) = 1 相同？

Answer 1

(mod p) 部分不是指右手边，而是指等号：它表示模 p、pow(a,q) 和 1 相等。例如，“模 10、246126 和 7868726 相等”（它们也都等于 6 模 10）：如果两个数 x 和 y 在除以 p 时具有相同的余数，则它们模 p 相等，或者等效地，如果p 除以 xy。

由于您似乎是从编程的角度来看，另一种说法是 pow(a,q)%p=1，其中“%”是用多种语言实现的“余数”运算符（假设 p>1 ）。

您应该阅读有关模块化算术的维基百科文章，或任何基本数论书籍（甚至是密码学书籍，因为它可能会介绍模块化算术）。

To answer your other question: there is no general formula for finding such an a (to the best of my knowledge) in general. Assuming that p is prime, and using Fermat's little theorem to reduce q modulo p-1, and assuming that q divides p-1 (or else no such a exists), you can produce such an a by taking a primitive root of p and raising it to the power (p-1)/q. [And more generally, when p is not prime, you can reduce q modulo φ(p), then assuming it divides φ(p) and you know a primitive root (say r) mod p, you can take r to the power of φ(p)/q, where φ is the totient function -- this comes from Euler's theorem.]

Answer 2

一点也不傻，因为这是公钥加密的基础。您可以在http://home.scarlet.be/~ping1339/congr.htm#The-equation-a%3Csup%3Ex 找到一个很好的讨论。

PKI 通过选择p和q较大且相对优质的方式工作。一个（比如p）成为您的私钥，另一个（q）是您的公钥。如果攻击者猜测p，给定aq（加密的消息）和q（您的公钥），则加密被“破坏”。

所以，回答你的问题：

aq= 1 个模组p

这意味着aq是一个除以 时余数为 1 的数字p。我们不关心商的整数部分，所以我们可以这样写：

aq/ p= n+ 1/p

对于 的任何整数值n。如果我们将等式两边都乘以p，我们有：

aq= np+ 1

解决a我们有：

a= ( np+1) ^1/q

最后一步是找到 的值，n该值生成 的原始值 a。除了反复试验之外，我不知道有任何方法可以做到这一点——这等同于“蛮力”尝试破解加密。