Number Theoretical Ciphers - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 45

(c) Set y ← z, r ← e , x ← a (q-1)/2 mod p , b ← ax 2 , x ← ax mod p .
(d) If b ≡ 1 (mod p ), then x is the answer, and we stop here.
(e) Find the smallest integer m (greater than or equal to 1) such that b 2 m ≡ 1 (mod p ). If m = r , then
we have a problem, because a is not a quadratic residue of p.
(f) Assign t ← y 2 r-m-1 mod p, y ← t 2 mod p, r ← m mod p, × ← xt mod p, b ← by mod p .
(g) Go back to Step 6d.
(Note that p will never be congruent to 2 or 4 mod p, since that would mean that 2 would be a factor
of p , which is not possible because p is prime.)
After we have represented a message as a point, we can then perform operations on it, similar to a normal
additive or multiplicative group. Instead of using exponentiation by integers, as we did for finite fields over in-
tegers, we will instead use addition on the points, that is, multiplying points by integers.
2.6.3 Elliptic Curve Diffie-Hellman
A very commonly used elliptic curve cryptographic algorithm is the Diffie-Hellman key exchange, but using
elliptic curves instead of normal finite fields.
In this variant, Alice and Bob both agree on an elliptic curve to operate with, over the same finite field (usu-
ally ( p , +, ×), where p is a large prime). They also agree on a particular point, say P. Just as before, they both
choose secret integers a (for Alice) and b (for Bob).
1. Alice sends Bob a P .
2. Bob sends Alice b P.
Since n P is shorthand for “add n copies of P together,” then we know that b(aP) = ba P = ab P and a(bP) =
ab P, so Alice and Bob can both compute ab P. Furthermore, only Alice and Bob can compute these numbers. 4
2.7 Summary
This chapter covered a great deal of material fundamental to cryptography and cryptanalysis.
We studied the basics of probability, which are critical in many types of cryptanalytic attacks. (As we shall
see, many attacks are probabilistic in nature, relying on intricate chains of events to work out.)
We then explored algebra, and number theory, including elliptic curves. This material is critical to public-key
cryptographicalgorithms(suchasRSA)andkeyexchangealgorithms(suchasDiffie-Hellman),whichareoften
based on these simple mathematical constructs. In the next chapter, we also use these concepts with algorithms
designed to compromise public-key cryptographic and key exchange systems.
Exercises
Exercise 1. Write a program to calculate the inverse of a number modulo another number, p, by implementing
the extended Euclidean algorithm.