Hello. I'm wondering why n needs to be a prime number. I was thinking it was because this was going to produce a list of all completely unique modulus values. But as you can see, there are repeats. So why does it need to be a prime number? Why not a large number that isn't prime?
+Logan Armagost If n is prime, you can reach every modulus result. You may get some repeats, but you will reach every result. If n is not prime, you may not reach every modulus result.You can get stuck in loops. For example, take clock with 7 numbers, 0 through 6. Start at point 0. Take 4 steps around the clock and you'll be at 4. Then another 4 and you'll be at 1. Then another 4 to get to 5. Eventually, you will have landed at every point on the clock. Now take a clock with 8 numbers, 0 through 7. Start at point 0. Take 4 steps around the clock, and you will be at point 4. Take another four steps, and you will be at point 0. No matter how many circuits you take (eg, no matter how many times you take 4 to higher and higher powers) you will only bounce between 0 and 4.
+Logan Armagost We stop at x = n-1 because of Fermats Little Theorem. a raised to n-1 is congruent to 1 mod n. So a raised to n is the same as a^(n-1) * a^1. a^n-1 is congruent with 1, so a^(n-1) * a^1 = 1*a^1 = a. You don't go any higher than a^(n-1) because you'll loop back around to a^1
Is the A correct answer? x_a = dlog(y_A, g, q); Where x_a is the secret exponent of A since g^x_a congruent to y_A mod q. key = mod(y_B, x_a, q); Where key is D-H shared key g^(x_a x_b) since y_B congrent to g^x_b mod q, raise both side with power of x_a gives y_B^x_a is congruent to (g^x_b)^x_a which is g^(x_a x_b) mod q. Finally the adversary gets the shared key for symmetric encryption.
Hello. I'm wondering why n needs to be a prime number. I was thinking it was because this was going to produce a list of all completely unique modulus values. But as you can see, there are repeats. So why does it need to be a prime number? Why not a large number that isn't prime?
+Logan Armagost Also, why do we stop at x raised to the n-1?
+Logan Armagost If n is prime, you can reach every modulus result. You may get some repeats, but you will reach every result. If n is not prime, you may not reach every modulus result.You can get stuck in loops.
For example, take clock with 7 numbers, 0 through 6. Start at point 0. Take 4 steps around the clock and you'll be at 4. Then another 4 and you'll be at 1. Then another 4 to get to 5. Eventually, you will have landed at every point on the clock.
Now take a clock with 8 numbers, 0 through 7. Start at point 0. Take 4 steps around the clock, and you will be at point 4. Take another four steps, and you will be at point 0. No matter how many circuits you take (eg, no matter how many times you take 4 to higher and higher powers) you will only bounce between 0 and 4.
+Logan Armagost We stop at x = n-1 because of Fermats Little Theorem. a raised to n-1 is congruent to 1 mod n. So a raised to n is the same as a^(n-1) * a^1.
a^n-1 is congruent with 1, so a^(n-1) * a^1 = 1*a^1 = a.
You don't go any higher than a^(n-1) because you'll loop back around to a^1
because the power of something to zero equals to 1
and ln(1) is undefined
Thank you for clear explanation.
Is the A correct answer?
x_a = dlog(y_A, g, q);
Where x_a is the secret exponent of A since g^x_a congruent to y_A mod q.
key = mod(y_B, x_a, q);
Where key is D-H shared key g^(x_a x_b) since y_B congrent to g^x_b mod q, raise both side with power of x_a gives y_B^x_a is congruent to (g^x_b)^x_a which is g^(x_a x_b) mod q.
Finally the adversary gets the shared key for symmetric encryption.
Thanks this was really helpful!
That text showing over your hand while you write is giving dizzyness!
who created the Discrete log problem?? making a schooltext about DLP and cant find anything about the history...
The ones that did figure it out are probably on the NSA's payroll