- Understand the basic math concepts behind modular arithmetic
- Apply this concept to server authentication
- Warm up your brains, have fun (with MATH!)
Today we're going to enact a metaphor for auth inspired by The Russian Postal Problem
Form groups and try to solve the problem. (If you've seen this one already, you can give hints, but please don't give it away.)
Remember remainders from division? That's what modular arithmetic is all about. In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value, also knows as the modulus.
Let's see what that looks like on the white board...
Note: This is an excellent video, with two gotchas. First, the narrator says "forty-two" when the display shows "46" several times. (46 is correct.) Second, there is a moment when 16^54 mod 17 is converted to 3^(24*54) mod 17 without explanation. This can be simplified and proven more easily using 3^6 and 3^8. Let's do that now...
Suppose Alice chose 6 as her random number. She would perform the equation:
3^6 mod 17 ≡ 15 and send 15 to Bob.
Suppose too that Bob chose 8 as his random number. He would perform the equation:
3^8 mod 17 ≡ 16, and send 16 to Alice.
Now Alice can start with Bob's public key (16) and raise to the exponent of her secret key:
16^6 mod 17 ≡ 1
Bob does the same by raising Alice's public key by his secret:
15^8 mod 17 ≡ 1
Now they both know the password, but Eve cannot determine it, because she does not know Alice's 6 or Bob's 8
The simplified math can be hacked in a reasonable amount of time, but if the secret key was (for example) a 40-digit hexidecimal value, it would take a long, long time.
Modular math can also be illustrated with a clock:
For positive numbers, move clockwise. (For negative numbers, move counter-clockwise.) Now we can see how 3^3 mod 17 ≡ 10
- Developers begin with the simplified algorithm
3^n mod 7as the "shared secret" - Each developer selects a random number
n-- this is your "secret key" -- don't share it. - Perform the calculation
3^n mod 7and share only the remainder. This is your "public key" - Take your partner's public key and raise it to your secret key.
- Did you get the same, new remainder?
17 and 7 are prime numbers. One of these will be our prime modulus. The primitive root of a number is one that has no factors in common where, if you raise the root by any exponent, the modulus will return a different value, until the sequence repeats itself.
| primitive root |
exponent | value | mod 17 | mod 7 |
|---|---|---|---|---|
| 3 | 1 | 3 | 3 | 3 |
| 3 | 2 | 9 | 9 | 2 |
| 3 | 3 | 27 | 10 | 6 |
| 3 | 4 | 81 | 13 | 4 |
| 3 | 5 | 243 | 5 | 5 |
| 3 | 6 | 729 | 15 | 1 |
| 3 | 7 | 2,187 | 11 | 3 |
| 3 | 8 | 6,561 | 16 | 2 |
| 3 | 9 | 19,683 | 14 | 6 |
| 3 | 10 | 59,049 | 8 | 4 |
| 3 | 11 | 177,147 | 7 | 5 |
| 3 | 12 | 531,441 | 4 | 1 |
| 3 | 13 | 1,594,323 | 12 | 3 |
| 3 | 14 | 4,782,969 | 2 | 2 |
| 3 | 15 | 14,348,907 | 6 | 6 |
| 3 | 16 | 43,046,721 | 1 | 4 |
| 3 | 17 | 129,140,163 | 3 | 5 |
| 3 | 18 | 387,420,489 | 9 | 1 |
| 3 | 19 | 1,162,261,467 | 10 | 3 |
- What is modular math and how does it work?
- How does bcrypt use modular math?
All content is licensed under a CCBYNCSA 4.0 license. All software code is licensed under GNU GPLv3. For commercial use or alternative licensing, please contact [email protected].