Modular Arithmetic, Prime Numbers, and a Little Bit of Cryptography

To contact us Click HERE
A three-hour movie begins at 11am. When does it end? In countries like the US that use a twelve hour clock, we say it ends at 2pm, even though 11 + 3 = 14. This is a first example of modular arithmetic, a simple and beautiful generalization of ordinary arithmetic that underlies much of modern cryptography and your ability to safely conduct financial transactions on the web.

One of the first multiplication facts you learn in school is 12 = 3*4. Numbers that can be factored into smaller pieces this way are called composite. Not all numbers are composite; those that are not are called prime. 13 is prime, because if it did have factors, at least one would be smaller than 4 (since 4*4 is 16, which is already too big), yet neither 2 nor 3 works.

Subtle connections between modular arithmetic and prime numbers led to the invention of public key codes, which have all sorts of uses, including allowing people to digitally sign documents and to verify that the documents have not been tampered with during transmission.

Today we are going to start at the beginning and explore how modular arithmetic works and how it connects with prime numbers. By the end you will understand how public key codes perform their magic, all without any math beyond multiplying whole numbers.

In clock arithmetic, also called arithmetic mod 12, any time weadd two numbers and the sum goes over twelve, we subtract twelve fromthe answer to bring it back into the standard range 1..12. Actually,mathematicians prefer to use 0..11 as the standard range, and we willadopt that convention here as well. It just means that when you see 12as the answer, you subtract 12, leaving zero.

For example, 3+4=7 mod 12, just as it does in "ordinary" arithmetic,but 11+4=3 mod 12, because the ordinary sum is 15, and then wesubtract 12, leaving 3.

This sort of thing works even if we add more than two numbers:11+11+11+11 = 8 mod 12, because the ordinary sum is 44, andsubtracting 36 (three repetitions of twelve) leaves 8.

A quick way to do this last result in your head is to think of 11 as-1, so four copies added together is -4, which is also 8. Why doesthis work? Remember that 12 and 0 are the same thing, so starting from12 and subtracting one (to get 11) is the same as starting from zeroand subtracting one (to get -1).

Here is the addition table for arithmetic mod12. Unlike the ordinary version you learned in school, which is just asmall piece of an infinitely large set of addition facts, this tableis complete: the numbers 0..11 are the only ones that are"allowed" in mod 12, so there are no other addition facts to memorize!

Addition Mod 12	0	1	2	3	4	5	6	7	8	9	10	11
0	0	1	2	3	4	5	6	7	8	9	10	11
1	1	2	3	4	5	6	7	8	9	10	11	0
2	2	3	4	5	6	7	8	9	10	11	0	1
3	3	4	5	6	7	8	9	10	11	0	1	2
4	4	5	6	7	8	9	10	11	0	1	2	3
5	5	6	7	8	9	10	11	0	1	2	3	4
6	6	7	8	9	10	11	0	1	2	3	4	5
7	7	8	9	10	11	0	1	2	3	4	5	6
8	8	9	10	11	0	1	2	3	4	5	6	7
9	9	10	11	0	1	2	3	4	5	6	7	8
10	10	11	0	1	2	3	4	5	6	7	8	9
11	11	0	1	2	3	4	5	6	7	8	9	10

The upper left portion of this table should look very familiar; it isthe ordinary addition table for small numbers. Note the symmetries:every diagonal that runs north-east to south-west is constant. Inparticular, the upper right triangle is mirror symmetric to the lowerleft triangle, which means addition is commutative: a+b = b+a,just as for ordinary addition.

I colored all the zero results violet, and all the ones lightblue. These highlight the new feature of modular arithmetic: wherewe would ordinarily have a 12, we put zero, and continue from therewith 1, 2, 3, instead of 13, 14, 15.

As mentioned above, 11+1 = 0 mod 12, so 11 acts like -1. Pairsthat sum to zero that way are called additive inverses. Icolored the zeros violet to help us spot inverses. For instance, inmod 12, the (additive) inverse of 10 is 2, or equivalently, 10 actslike -2 in ordinary arithmetic.

Now let's make a multiplication table mod 12. We find amuch more complicated pattern: look at the jumble of violet cells in the middle!

Multiplication Mod 12	0	1	2	3	4	5	6	7	8	9	10	11
0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	1	2	3	4	5	6	7	8	9	10	11
2	0	2	4	6	8	10	0	2	4	6	8	10
3	0	3	6	9	0	3	6	9	0	3	6	9
4	0	4	8	0	4	8	0	4	8	0	4	8
5	0	5	10	3	8	1	6	11	4	9	2	7
6	0	6	0	6	0	6	0	6	0	6	0	6
7	0	7	2	9	4	11	6	1	8	3	10	5
8	0	8	4	0	8	4	0	8	4	0	8	4
9	0	9	6	3	0	9	6	3	0	9	6	3
10	0	10	8	6	4	2	0	10	8	6	4	2
11	0	11	10	9	8	7	6	5	4	3	2	1

Can you see the pattern here?

As in ordinary arithmetic, multiplying anything by zero gives zero, sothe first row and column are violet. But any combination whose productwould have been 12 (or a higher multiple like 24, 36, 48, 60, etc.) alsoturns into zero, when we work mod 12. So for example, 3*4=0 mod 12,resulting in a violet cell in the table. In fact, all the "extra"violet cells involve a product that produces a 12, like2*6, or a higher multiple, like 6*10.

Despite the jumbled appearance, there is still a mirror symmetry between the upperright and bottom left of the table: multiplication, like addition, iscommutative, meaning order does not matter: 5*7 = 7*5, both inordinary arithmetic and in modular arithmetic, and in general, a*b =b*a regardless of what numbers we use for 'a' and 'b'.

Let's compare this to the multiplication table mod 13. Arithmetic mod13 works the same way as mod 12, except that now the allowed numbersare 0..12, and we subtract 13 as needed to get larger numbers into thestandard range. The addition table has the same nice diagonal patternas in the mod 12 table, so I won't show it again. But themultiplication table mod 13 looks quite different than the mod 12version.

Multiplication Mod 13	0	1	2	3	4	5	6	7	8	9	10	11	12
0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	1	2	3	4	5	6	7	8	9	10	11	12
2	0	2	4	6	8	10	12	1	3	5	7	9	11
3	0	3	6	9	12	2	5	8	11	1	4	7	10
4	0	4	8	12	3	7	11	2	6	10	1	5	9
5	0	5	10	2	7	12	4	9	1	6	11	3	8
6	0	6	12	5	11	4	10	3	9	2	8	1	7
7	0	7	1	8	2	9	3	10	4	11	5	12	6
8	0	8	3	11	6	1	9	4	12	7	2	10	5
9	0	9	5	1	10	6	2	11	7	3	12	8	4
10	0	10	7	4	1	11	8	5	2	12	9	6	3
11	0	11	9	7	5	3	1	12	10	8	6	4	2
12	0	12	11	10	9	8	7	6	5	4	3	2	1

There are no violet cells outside the first row and first column! That isbecause 13 is prime, so there are no combinations a*b that equal13. In fact, because 13 is prime, there are not even any combinationswith a*b equal to a multiple of 13, like 26 or 39, unless either a orb itself is a multiple of 13, and that never happens since 12 is thelargest allowed value.

Moreover, this time every row and column has a light blue 1 in itsomewhere (ignoring the first row and first column, which are just multiplication by zero). Thatis quite interesting. Just as summing to zero gave us a version of"negative" numbers, multiplying to yield one gives us a version of"fractions". If a*b=1, we say that a and b are multiplicative inverses. In ordinary arithmetic, this requires fractions: themultiplicative inverse of 5 is 1/5, which is not a whole number. Inthe mod 12 world, only four numbers had inverses, and they were allself-inverses at that: 1*1=1, 5*5=1, 7*7=1,and 11*11=1. But in mod 13, every number (except zero) has aninverse, and they follow quite a jumbled looking pattern.

For example, the (multiplicative) inverse of 2 is 7, because 2*7=1 mod 13 (normally2*7=14, but subtract 13 to get 1). The inverse of 3 is 9, because 27is one more than 26, which is a multiple of 13. And so on, withoutmuch pattern other than the fact that every row and columnhas exactly one light blue cell.

In fact, the mod 13 multiplication table has a lot in common with a giant Sodokupuzzle: again ignoring the violet row and column, we see that each ofthe numbers 1..12 shows up exactly once in every row and everycolumn. That means that any given row or column isa permutation (i.e. a shuffling or re-ordering) of the numbers1..12. This is quite different from the mod 12 case, where certainnumbers, like 0, showed up far too often, and other numbers, like 1,showed up too infrequently.

Now let's think for a minute about cryptography. A good cipher system must behard to break, but it must also be possible to decode it,otherwise it is useless. This means it must involve permutations, likemultiplication mod 13 does, rather than transformations that"collapse" information, like multiplication mod 12.

To see what I mean, consider the ancient (and way too simple to besecure) Caesar Cipher. This involves permuting the letters of the alphabet byshifting each one forward a set amount, such as by 3 letters. Forexample, we could encrypt "THE EAGLE" as "WKH HDJOH" by moving the T threeletters forward past UV to W, the H three letters forward past IJ toK, the E three letters forward to H, and so on.

Because the Caesar Cipher involves a permutation, it can be decoded byreversing the permutation, i.e. shifting three letters back. Thus Wshifts back to T, K to H, H to E, and so on.

In contrast, consider a "cipher" that encodes consonants as A andvowels as B. We could encrypt "THE EAGLE" as "AAB BBAAB", but we wouldhave a problem if we try to decrypt it. There is no way toknow which consonant any given A stands for, or which vowel anygiven B stands for, except through accidents of English spelling. It is a little tricky thinking up examples, but thanks toRegex Dictionary, using the"regular expression" search pattern

  ^[^aeiou][^aeiou][aeiou]$

we find that AAB could mean TWO or WHO, not just THE. If we count 'y' as aconsonant, AAB could mean BYE, DYE, or LYE. If 'y' is a vowel, itcould mean CRY. And so forth.

So ciphers need to involve permutations. Now, modern ciphersare much more complicated than just shifting individual letters. Computers represent everything as bits (zeros and ones). A message is just along string of bits. Block ciphers like the USGovernment's Advanced Encryption Standard (AES) take 128 (or256 etc.) bit chunks at a time and perform numerous arithmetic andbit-permuting operations on them to mix them up. The user specifiesa key, i.e. a password, which controls which permutationis used, much like the number 3 acted as the "key" in our earlier Caesarcipher example. The recipient ofthe message, who also knows the key, uses it to reverse thepermutations, thereby decoding themessage. A Stick Figure Guide to the Advanced Encryption Standard providesa fun "cartoon" introduction to the details of the permutationalgorithm, if you are curious.

Block ciphers like AES are very efficient and very secure.However, block ciphers have one major drawback. Both the sender andthe recipient of the coded message need to have advanceknowledge of the key - yet the key must be secret to prevent any thirdparty from intercepting, reading, or modifying thetransmission.

Suppose "Alice" wants to buy from a web site that "Bob"runs. She needs the communication encrypted so people cannot find outher credit card number. But she cannot just send Bob an AES key forthem to use to encrypt the session, since the key itself also needs tobe protected!

Enter "public key" codes. These combine modular arithmetic andprime numbers in such a way that Alice and Bob can indeed agree ona secret AES key, even though they have never met and initially haveno shared secret to use as the key.

Security is actually a bit more complicated then just the encryption part. We alsoneed protocols that can for instance prevent "replay attacks",where an eavesdropper who cannot decode your message nonetheless cancopy it and resend the copy at a later time. Think about a messagethat withdraws money from your bank - such as gets transmittedwhenever the bank processes a check you wrote - you don't want someonereplaying that and transferring the money twice, even if they cannotdecode or alter the message directly. Fortunately, once you havegood encryption, you can define appropriate protocols to preventthis (e.g. including a unique transaction number as part of themessage, thus allowing duplicate messages to be detected),so we will focus on the encryption and leave protocols for another discussion.

To understand how public key encryption works, we need onemore arithmetic operation. So far, we have looked at the modular arithmeticversions of the addition table and the multiplication table. Theoperation we need now is raising to a power. Suppose we startwith the number 6 in the mod 13 system. If we multiply it by itself,we are raising it to the second power (squaring it), and we get6*6 = 36 = 10 mod 13, because 26 is a multiple of 13.

Next, let's multiply together three copies of 6. This is calledraising it to the third power, or cubing it. We get 6*6*6 = 8mod 13, because 6*6*6 = 216, and 208 is a multiple of 13. However,there is an easier way to get this result. We already know that 6*6 =10 mod 13, so 6*6*6 is the same as 10*6 = 60 = 8 mod 13, because 52 isa multiple of 13.

We can keep going this way, as shown in the following table. We willuse the notation 6^n to mean n copies of 6 multiplied together, so 6^2= 6*6 and 6^3 = 6*6*6. Just like addition is repeated counting, andmultiplication is repeated addition, raising to a power is just repeatedmultiplication. Here are the powers of 6 in mod 13 arithmetic:

n	1	2	3	4	5	6	7	8	9	10	11	12
6^n mod 13	6	10	8	9	2	12	7	3	5	4	11	1

There is a very special feature to this table: it goes all the way ton=12 before we get a result of 1. That makes 6 a primitive rootof mod 13 arithmetic: in other words, a number whose powers generateall the values (except of course zero).

Not every modular arithmetic has primitive roots. For example, in mod12, if you try raising numbers to powers, you will find that none getvery far. For example, the powers of 2 are 2, 4, 8, but then theyrepeat back to 4, 8, 4, 8, forever. When you think about it,multiplying even numbers together yields even numbers, and since 12 iseven, the result stays even after converting mod 12. So we will neverget 5, or 1, as an answer. But odd numbers also turn out to fail: forexample, 7*7 = 1 mod 12, which means we get a repeating sequence 1, 7,1, 7.

Gauss (a very famous mathematician of the early 1800's) showedthat we can always find a primitive root if we do arithmetic mod pwhere p is a prime, like 13 or 17. For example, 10 is aprimitive root mod 17. It is not the only one; you can verify forinstance that 5 is also a primitive root mod 17, and that 13 is not.

We now know enough to describe the Diffie-Hellmanpublic key code. Alice and Bob agree to use a specific prime number pand a specific primitive root r mod p. These numbers do not need to bekept secret, although the prime p does need to be large: largein the sense that writing p in decimal form might involve 300 digits,rather than just two (as in the case of the primes like 13 or17). They will perform all their arithmetic mod p.

Alice chooses a large random number 'a', and Bob independentlychooses a large random number 'b'. Here large means that 'a' and 'b' areperhaps 100 digits long: smaller than p, but still much larger thanordinary numbers, so their web browser programs will need special codeto do the calculations accurately. Independent means Bob and Alice do not need tocommunicate to make their choices: they each choose on their own, soAlice does not know 'b' and Bob does not know 'a'. Random means the choice isunpredictable to outsiders: it might depend on the timing ofall the keystrokes on their computers over the past day, measured inmicroseconds. As a result, only Alice knows 'a',and only Bob knows 'b', even if someone eavesdrops on theirconversations.

Alice now sends the number r^a mod p to Bob. Bob, at the same time, sendsthe number r^b mod p to Alice. Again, all of this can be done in "plaintext": these are just random looking large numbers, and no harm is done ifsomeone else eavesdrops on them.

Now for the simple but critical fact that makes it all work: (r^a)^b =(r^b)^a, because both sides are just r^(a*b). In other words, orderdoes not matter for repeated exponentiation (just as it does notmatter for multiplication), because both sides are just a*b copies ofr multiplied together. And the same is true even if we work mod p.

Since this point is central, let's do an example for clarity. Consider(5^3)^2. We start inside parentheses with 5^3 = 5*5*5, then wesquare this, which means we multiply it by another copy of 5*5*5. Thusaltogether we have to calculate 5*5*5 * 5*5*5. That is six copies of 5multiplied together, or 5^6. If we reverse the order, and look at(5^2)^3, we get 5*5 inside parentheses; now we cube it, i.e. wemultiply three copies of 5*5 together, forming 5*5 * 5*5 * 5*5, whichagain is just six copies of 5 multiplied together, or 5^6. So we getthe same answer either way.

Because of this, if Alice takes the number r^b mod p she received fromBob, and raises it to the power 'a' (using her own secret number 'a'),she computes r^(a*b) mod p. And if Bob takes the number r^a mod p thathe received from Alice, and raises it to the power 'b' (using his ownsecret number 'b'), he too computes r^(a*b) mod p. This means thatAlice and Bob now share a secret, namely the large and randomlooking integer r^(a*b) mod p.

Alice and Bob can now use this shared secret as their AES key. Nowthey can have an extended conversation encrypting as much informationas they need to complete the purchase process. They don't needpublic key encryption any more; that was just used to provide themwith a shared but secret AES key. That is fortunate, because modulararithmetic on 300 digit numbers is slow compared to using AES toscramble the bits of the real message.

Again, the actual process inside your web browser is a little morecomplicated - there are some additional protocols to ensure that noone replays their communication, or modifies it without theirknowledge - but all of these extra steps are predicated on this basicability to get Alice and Bob to share a secret without in fact havingto communicate it directly.

Why did we need the mod p stuff? Why not just use regular arithmetic?I'm glad you asked. Doing everything mod p is precisely what makes theprocess secure. Suppose we use ordinary arithmetic. Suppose aneavesdropper "Eve" listens in on the conversation. When she receivesr^b, she can reverse the process by taking logarithms: the log base rof the number she received is just 'b', and calculating logarithms iseasy for a computer. Once she knows 'b', she can take the r^a value(which like r^b was sent un-encrypted) and raise it to the power 'b',thereby computing the secret key. Now she will be able to listen toand decode the entire subsequent purchase transaction, since she knowsthe AES key; she can also encrypt her own messages with the same keyand potentially trick Alice and Bob into believing they are legitimate.

What's different when we do this mod p? Only one thing: taking alogarithm mod p turns out to be extremely difficult, even for thefastest known computer algorithms. So, provided no one invents a fastway to solve the discrete logarithm problem (a reasonably safebet, since many smart people have been (unsuccessfully) attempting itfor several decades now, for obvious reasons), the time required tobreak this sort of code grows exponentially in the number ofdigits involved. That is why the prime p needs to be at least 300 digits long,and 'a' and 'b' need to be at least 100 digits long: by using really bignumbers, we can make breaking the code take an arbitrarily long time.

Computers do get faster every year, and a well fundedeavesdropper (like a national government) could run a bunch ofcomputers in parallel to speed up the attempt, butthe process works well enough for now. That's because exponentialgrowth is really fast - as you may recallfrom Powers of Two Back in Time, one can go from a time scale of seconds toa time scale of the age of the universe in just 59 powers of two. Soby using enough digits in p, a, and b, one can literally ensure thatall the computers in the world could not break the code in a millionyears.

Someone might discover a fast algorithm for discretelogarithms. No one knows whether such an algorithm is even possiblefor ordinary computers, let alone how it would work, but a fastalgorithm is known for quantum computers. Fortunately,quantum computers are just in their infancy, and are not yet practicalon a large scale. In addition, there are apparently public key codesthat use tricks for which fast quantum algorithms do not (yet)exist. So at least in the short run, our present systems givereasonable security in theory.

Of course, there are some caveats in practice. There is an almostlimitless number of things that can go wrong "outside the box". Ifyour web browser or the server web site has been compromised in somefashion, e.g. by a computer virus, or by an improperly programmedprotocol, then the communication may be insecure. Or, take the case ofthe recent Iranian capture of an American drone airplane. Accordingto Bruce Schneier's blog onSecurity, Iran did not break the encryption for controlling the drone:instead, they claim they just jammed the drone's access to GPS navigationsignals, which apparently forced it to make an emergencylanding. Similarly, criminals who want to get your bank passwordapparently focus less on trying to break the encryption than onsimpler techniques like sending you "phishing" emails that attempt totrick you into typing your password directly into their fake website.

So there we have it: modular arithmetic and prime numbers areat the heart of our modern "e-commerce" system of secure web sites,thanks largely to the "magic" of public key cryptography. Mathematically,they work extremely well, although staying secure in practice is amuch harder problem!

If you liked this article, you may also like Why are there exactly five Platonic solids?, or perhaps Counting and Number Systems.

Please post questions, comments and other suggestions using the box below, or email me directly at the address mentioned in the Welcome post. Remember that you can sign up for email alerts about new posts by entering your address in the widget on the sidebar. If you prefer, you can follow @ingThruMath on Twitter, where I will tweet about each new post to this blog. The Contents page has a complete list of previous articles in historical order. Now that there are starting to be a lot of articles, you may also want to use the 'Topic' and 'Search' widgets in the side-bar to find other articles of related interest.

I hope you enjoyed this discussion. You can click the "M"button below to email this post to a friend, or the "t" button toTweet it, or the "f" button to share it on Facebook, and so on. Seeyou next time!