Modular arithmetic
I am new to cryptography and modular arithmetic. So I'm sure this is a stupid question, but I can't help it.
How to calculate a from
pow (a, q ) = 1 (mod p )
where p and q are known? I don't get the "1 (mod p )" part, it is equal to 1, right? If so, what is "mod p "?
Is this the same as pow (a, -q ) (mod p ) = 1?
source to share
The (mod p) part refers not to the right side, but to the equal sign: it says that mod p, pow (a, q) and 1 are equal. For example, "modulo 10, 246126 and 7868726 are equal" (and they are both 6 modulo 10): two numbers x and y are equal modulo p if they have the same remainder when divided by p, or equivalently if p divides xy.
Since you seem to be coming from a programming perspective, another way of saying is pow (a, q)% p = 1, where "%" is the remainder operator, implemented in multiple languages (assuming p> 1).
You should read the Wikipedia article on Modular Arithmetic or any book on elementary number theory (or even a book on cryptography as it will likely introduce modular arithmetic).
To answer your other question, there is no general formula for finding such a (as far as I know) in general. Assuming p is simple, and using Fermat's little theorem to decrease q modulo p-1, and assuming that q divides p-1 (or it doesn't exist), you can create such a by taking the primitive root p and lifting it by cardinality (p-1) / q, [And more generally, when p is not prime, you can decrease q modulo? phi; (p) and then assume that it divides? phi; (p) and you know the primitive root (say r) mod p, you can take r in (p) / q where & phis; function totient - This comes from Euler's theorem . ]
source to share
Not completely stupid as this is the basis for public key encryption. You can find a great discussion on this at http://home.scarlet.be/~ping1339/congr.htm#The-equation-a%3Csup%3Ex.
PKI works by choosing p
and q
, large and relatively simple . One (say p
) becomes your private key and the other ( q
) is your public key. The encryption is "broken" if the attacker guesses p
it given a
q
(encrypted message) and q
(your public key).
So, to answer your question:
a
q
= 1 modp
This means that a
q
is the number leaving a remainder of 1 when divided by p
. We don't need the whole part of the quotient, so we can write:
a
q
/p
=n
+ 1 /p
for any integer value n
. If we multiply both sides of the equation by p
, we have:
a
q
=np
+ 1
For the solution a
we have:
a
= (np
+1) 1 /q
The last step is to find the value n
that generates the original value a
. I don't know how to do this other than trial and error, which is the equivalent of brute force trying to break the encryption.
source to share