Diffie Hellman Tips (Ch 4)¶

Kahn Academy has a nice series of videos on cryptography, clock arithmetic, and the Diffie-Hellman. If you are feeling at all shaky on these topics, I highly recommend watching the first 4 videos in the series that link takes you to. Even if you think you have it all down, the videos add a little detail that you might find interesting.

Math Tips

Doing clock math on small numbers isn’t too hard - once you learn about it, you should be able to figure out what 20 on a clock size of 7 is (the answer is 6). It is a little bit harder when you are dealing with really large numbers. Here is a tip on how to calculate clock math for large values:

The more formal name for clock math is modulo arithmetic or mod for short. We would write 20 on a clock size of 7 as: $$20 \textrm{ mod } 7$$. You can ask Wolfram Alpha to do that math for you, try typing “20 mod 7” in the box below and hitting enter:

Wolfram Alpha:

The results will include the answer as well as other handy info like other numbers that produce the same answer for the given clock and the clock representation of the answer.

Wolfram Alpha will work even when arbitrarily large numbers are involved. With Diffie-Hellman, the use of exponents means the values involved grow rapidly, but Wolfram Alpha will do just fine calculating something like 23 to the 17th power on a clock size 11. Use ^ to represent exponentiation and type something like “23^17 mod 11” as your input.

Practice Problem

Want to verify you know how to do the calculations from this week’s 9 Algorithms chapter correctly? Try this:

Incidentally, because our clock size is 13, it would be easy to uncover the secret. You simply have to try every number from 0 to 12. On a clock size of 13 you can never have an answer greater than 12. For this reason, when using the algorithm in real life, the clock size needs to be much, much larger.