Tag Archives: cryptology

Secrecy in Plain SIght

Security is a vastly important facet of our day to day lives.  It is so ubiquitous, few people recognize that they use it every day. However, if you ever visit a webpage that has “https” in the URL, you are using secure technology.  Most of the early security protocols require that two parties have a secret exchanged between them.  Unfortunately, if someone is listening to the key exchange, they can easily decrypt all of the messages sent between the two parties.  You may find yourself asking, “But isn’t there some better way to exchange secrets?” You’d be right!

The method is called Diffie-Hellman key exchange, and it relies heavily on modular arithmetic.  The amazing thing about this protocol is that the two parties, Alice and Bob (in keeping with the cryptographic tradition of keeping names simple) can even publish their communications in the newspaper.  Anyone can be listening to these two exchange their keys.

Here’s how it works:

First, Alice and Bob pick two numbers, p and g.  P is a prime number, and g is a primitive root mod p.  A primitive root mod p has a very special property, namely that every number that is coprime with p is congruent to some power of g[1].  For example, if we pick p=5, 3 is a primitive root mod p because:
1,2,3,4 are relatively prime to 5.
30 ≡ 1 mod 5
31 ≡ 3 mod 5
32 ≡ 4 mod 5
33 ≡ 2 mod 5

As you can see, each number that is relatively prime to 5 is represented by some power of 3.  Therefore, 3 is a suitable primitive root mod 5.

For this example, Alice and Bob will decide on p=17 and g = 7.  They can pick these numbers from a well-known list.  What’s more, they can even display these numbers in public.  These will form the foundation of their key.  Next, Alice and Bob both pick their own numbers and keep them secret.  We’ll call Alice’s secret number a, and Bob’s number b. (Original, right?)

Next, Alice determines ga mod p, and Bob determines gb mod p.  We’ll call these c and d, respectively.  Now, Alice and Bob will exchange their values.  Again, this can take place in the open.
Now, Alice has d, and Bob has c.  Next, Alice performs da mod p, and Bob performs ca mod p.  This has the net effect of giving both Alice and Bob the same number.  They are now both in possession of gab mod p.  What’s more, any attacker could have watched the entire exchange, and wouldn’t have gotten anything out of it.

caption

Secrecy in Plain Sight. Image: A.J. van Hinck, via Wikimedia Commons.

Back to the example:

Alice chooses 3 as her secret number.
Bob chooses 5 as his.
Alice’s transport number is 73 mod 17 ≡ 3
Bob’s transport number is 75 mod 17 ≡ 11
Alice gets 11, and performs 113 mod 17 ≡ 5
Bob gets 3 and performs 35 mod 17 ≡ 5

Alice and Bob now have the same number, which they can use for regular cryptography.  Obviously, in a real situation, Alice and Bob would have chosen much larger numbers, but this suffices for an example.

This is the foundation of cryptography – relying on operations that are easy to perform, but are nearly impossible to reverse.  In this case, exponentiation can be performed on a computer in a reasonable amount of time.  It’s not the fastest algorithm, but it’s far faster than performing the reverse of a modulo operation.  (Incidentally, that problem is called a discrete logarithm, and there is currently no way that it can be done in a reasonable amount of time.)

You may wonder, “I really want to steal nuclear secrets!  Is there some way that I can still eavesdrop on people using Diffie-Hellman?”  You’d be right!  Diffie-Hellman is vulnerable to what is known as a “man-in-the-middle” attack.  This is difficult, as it requires being present at the time the keys are exchanged.  However, the attack is simple.  All that needs to be done is that some attacker Eve (short for eavesdropper) intercepts Alice and Bob’s messages.  When Alice sends Bob her key, Eve steals it, and substitutes her own key.  Bob then responds, and Eve steals his response.  She then gives her own key to Alice.  Now, there are two unbreakable passwords, and Eve has both of them.  However, there is a limitation: Eve needs to be present for the entire conversation, or Alice and Bob will immediately know something is wrong.  This is because the key that Alice has is not compatible with the key Bob has.  Suddenly, all of their communication will be reduced to gibberish, and they will know that they are compromised.  However, it is possible for Eve to hijack their conversation, leaving none the wiser.

We may ask, why not use RSA?  Well, we do!  If we combine RSA with Diffie-Hellman, we gain protection against eavesdroppers and hijackers.  Diffie-Hellman is faster than RSA and can encode larger messages than RSA.  (The messages sent by RSA are limited in size, lest it become easy to crack.)  In addition, using these two approaches combined gives us the ultimate goal of cryptography:  Perfect Forward Secrecy!  If the secret numbers used by Alice and Bob are discarded, nobody can read the messages exchanged between the two, ever.  That’s right, 30 years down the line, when someone digs up Alice’s old machine out of some attic in Nebraska, they won’t be able to read the messages she shared with Bob.  This is the real advantage of Diffie-Hellman, and the reason that it will likely remain in use for a very long time.

Sources:

[1] http://en.wikipedia.org/wiki/Primitive_root_modulo_n

[2] http://en.wikipedia.org/wiki/Diffie–Hellman_key_exchange

My Top Secret Messages to Maryam Mirzakhani

If you’re anything like me, you need to send TOP SECRET messages all the time.

Just the other day, I was working on a really hard problem set for my History of Math class, so I decided to ask my good friend Maryam Mirzakhani to do it for me. This, of course, went against my University’s cheating policy, so I needed to be sure that my message was encrypted securely enough that my resourceful and mathematically gifted professor Evelyn Lamb couldn’t read my message and fail me for cheating.

full_res

Luckily, by the grace of modular arithmetic, I was able to have a quick exchange with Maryam just in time to hand in my assignment undetected. Below I’ll discuss the rad encryption algorithm Maryam and I used to exchange messages, and the clever but unfortunately unsuccessful algorithms my suspicious professor tried to discover our ploy.

RSA
We decided to encrypt with RSA and pay homage to the best public-key cryptosystem around. RSA is an asymmetric algorithm, which means that the keys of the sender and the receiver are completely independent. Maryam and I needed to independently complete the steps below to exchange encrypted messages.

1) I chose 2 extremely large prime numbers p and q.
I went with my favorite primes, 61 and 11.
2) Set my modulus to be n = p * q, and held on to a value I’ll call ϕ(n) = (p-1)*(q-1)
So for me, n = 11*61 = 671, and ϕ(n) = 10*60 = 160.
3) Chose the exponent “e” for my public key
The number e just needs to be coprime with ϕ(n), a common choice is 216 + 1 = 65,537 but 3 is sometimes just as good a choice.
I chose e = 7, just because I happen to like 7.
4) Found my private key exponent, “d” as the multiplicative inverse of e mod ϕ(n).
That is, find d such that d*e = 1 (mod ϕ(n)).
Normally, you can do this using the extended Euclidean Algorithm.
But I instead used the coveted Wolfram-Alpha algorithm, and found that d = 23.

After these steps Maryam and I each had a public and private key- you can think of these as keys that interchangeably lock and unlock the message. Anyone listening in (like Professor Lamb) can see each of our public keys- this is what allows strangers on the internet to securely exchange messages.

The public key consists of n and e, and the private key is d. My public key was (n = 187, e = 7) and my private key was d = 23 (but don’t tell Professor Lamb!) Maryam broadcast her public key, which was (n = 779167, e = 17).

I want to encrypt my message:
Hi Mimi! How great is the weather in California? Hey, I have a favor to ask…

First I converted the letters in my message into numbers by some publicly known agreed upon encoding, and broke my message into chunks so that the value of each chunk was less than Maryam’s public key value n, again with a publicly agreed upon scheme:
720 010 500 077 001 050 010 900 105 000 330 007 200 111…

I then encoded each chunk into the cypher-text c using Maryam’s public key (n = 779167, e = 17) as: c = me (mod n)
So specifically, c1 = 72017 (mod 779167)
c2 = 1017 (mod 779167) and so on.

I sent these encoded cypher-text chunks to Maryam, who then used her private key d to decode them into the message that I wrote:
m = cd (mod n)

This is because I encoded the cypher-text as c = me (mod n), so when Maryam computed cd, she had actually computed (me)d (mod n) = med (mod n). Recall that Maryam very carefully chose e and d so that e*d = 1 (mod ϕ(n)). This means, thanks to Fermat’s Little Theorem, that med (mod n) is the same as m1 (mod n). Excellent news, this is just my original message! Thanks, modular arithmetic!

We could now securely exchange messages, and for even more security I even left a signature in my message so that Maryam could be sure the message actually came from me.

But not so fast! Professor Lamb noticed that Maryam and I were exchanging mysterious messages, so she took a stab at decoding them.

Pollard’s p-1 Algorithm
RSA is a secure algorithm because it is very difficult to factor large numbers.

Recall that when I sent Maryam a message, I encoded the message m into cypher-text c using her public key (n and e) as:
c = me (mod n)
and she decoded the message using her private key d as:
cd = med (mod n) = m (mod n)
This is secure because, if you remember back to how Maryam chose e and d,
e*d = 1 (mod ϕ(n))

This means that for Professor Lamb to decode the message that I sent to Maryam, she needed to find d. To find d, she needed to know what ϕ(n) = (p-1)*(q-1) was, because you need to know the modulus before you can find the inverse of an element, and to find ϕ(n) she needed to figure out p and q. Therefore, the only thing standing between me and expulsion for cheating is the fact that it’s very hard to factor very large numbers. Notice, however, that all the other information is publicly available- c, e and n can be viewed by everyone.

Professor Lamb decided to try Pollard’s p-1 algorithm to factor Maryam’s public key modulus, n = 779167. She first decided to try the algorithm on a smaller, more manageable number, so she tried n = 5917. Here’s what she did:

1. She chose a positive number B.
Professor Lamb liked the number 5, so she set B = 5.

2. Computed m as the least-common multiple of the positive integers less than B.
m = lcm(1, 2, 3, 4, 5) = 60

3. Set a = 2.
Easiest step ever.

4. Found x = am – 1 (mod N) and g = gcd(x, N)
x = 260 – 1 (mod 5917) = 3417 (mod 5917)
g = gcd(3417, 5917) = 61

5. If g isn’t equal to 1 or N, then you’re done!
Professor Lamb found that 61 was a prime factor of 5917! Slick!

6. Otherwise, add 1 to a and try again. If you’ve already tried 10 times, just give up.
Luckily she didn’t need to use this step, but for a lot of different n’s she probably would have.

Feeling triumphant and confident in Pollard’s p-1 algorithm, Professor Lamb turned to Maryam’s public key modulus, n = 779167. The first 3 steps were the exact same as before, and for step 4 she found:
x = 260 -1 (mod 779167) = 710980
g = gcd(710980, 779167) = 1

Drat! Professor Lamb then had to proceed to step 6, increased a to 3 and try again:
x = 360 -1 (mod 779167) = 592846
g = gcd(592846, 779167) = 1

Double drat! Professor Lamb continued this for approximately 10 steps, and then gave up. (Really I should just be glad that she didn’t try to factor my public key modulus n = 187. Our encryption would have been much more secure if I had chosen much larger primes!)

Luckily for me, Maryam and I chose a secure encryption algorithm. RSA is set up so that to decode the message, you need to know the prime factors p and q of the modulus n. You need p and q so that you can find the inverse of the public key mod (p-1)(q-1), and these public and private key exponents work to encode and decode the message because of Fermat’s Little Theorem.

Professor Lamb tried to decode our secret messages by factoring Maryam’s public key modulus with Pollard’s p-1 algorithm, but unfortunately it did not yield a prime factor. Because finding large prime factors is such a difficult problem, Professor Lamb wasn’t able to read our secret messages, and I got an A on my homework.

Obvious disclaimers!

– I obviously didn’t ask Maryam Mirzakani to do my Math History homework. She’s an incredibly intelligent lady, working on much, much more difficult things, and apparently getting awesome results.

– I obviously don’t endorse cheating and Professor Lamb’s homework is not too difficult. It is just difficult enough 🙂

– Even though I motivated the need for privacy in my silly article with my desire to keep my professor from finding out I was cheating, privacy is obviously very important for a wide range of reasons(possible hyperlink?), and is equally important to protect people who don’t have anything to hide.

– The ascii art image of Maryam Mirzakani is obvious very cool! It was made by my very talented friend Tobin Yehle, who wrote a neat program to translate photos into ascii art.

Cryptography: A modern use for modular arithmetic

The common analogy used to describe modular arithmetic is fairly simple. All one has to do is look at an analog clock. For example, if it’s 11 AM and you want to know what time it will be in four hours, we instinctively know the answer is 3 PM. This is modular arithmetic, i.e. 11+4 = 3 mod 12. This is an important concept in the technology driven world we live in. Any time a product is purchased on the internet, cryptography comes into play. The remainder of this paper (pun most definitely intended) will describe how ancient modular arithmetic plays a very important role in today’s society.

History of modular arithmetic

The first known publication of modular arithmetic was in the 3rd century B.C.E, in the book Elements, written by Euclid. Within his book, he not only formalized the fundamentals of arithmetic, but also proved it. In what is known as Euclids Lemma, he states that if a prime number divides the product of two different numbers (x and y), then the prime number must also divide one of the numbers (either x or y), but it could also be both. Between the 3rd and 5th centuries a paper publish by Sun Tzu describes a modular arithmetic process known as the Chinese remainder theorem. This theorem is essentially the basis for modern RSA encryption schemes that are present on every banking/e-commerce website. It uses a congruent set of keys to produce the same numerical value. Imagine if there was a lock on a door that two differently cut keys could unlock and open, this is essentially how Chinese remainder theorem works.

Modern modular arithmetic

Oil painting of mathematician and philosopher Carl Friedrich Gauss by G. Biermann (1824-1908). Public Domain.

Oil painting of mathematician and philosopher Carl Friedrich Gauss by G. Biermann (1824-1908). Public Domain.

The modular arithmetic that we use today was discovered by Carl Friedrich Gauss in 1801.

Gauss is famous for numerous discoveries across a wide variety of fields in science and mathematics. Gauss’s proposition, from his book Disquisitiones Arithmeticae, defines modular arithmetic by saying that any integer N belongs to a single residue-class when divided by a number M. The residue-class is represented by the remainder, which can be from 0 to M-1. The remainder is obtained by dividing N by M. Given this fact, Gauss notices that two numbers that differ by a multiple of M are in the same residue-class. He then discusses the role of negative numbers in modular arithmetic. The following is an excerpt from his book:

“The modulus m is usually positive, but there’s no great difficulty in allowing negative moduli  (classes modulo m and -m are the same).  For a zero modulus, there would be infinitely many residue classes, each containing only one element.  [This need not be disallowed.]”

Modular Arithmetic’s Role Today

RSA encryption is named after those who invented it, Ron Rivest, Adi Shamir, and Leonard Adleman (RSA is obtained from their last names). RSA is the process by which information can be passed between two parties without another individual being able to intercept the message. Burt Kaliski has been one of the major contributors to RSA encryption since the 1980’s. I would like to start off with a passage from Burt Kaliski’s paper titled “The Mathematics of the RSA Public-Key Cryptosystem”:

“Sensitive data exchanged between a user and a Web site needs to be encrypted to prevent it from being disclosed to or modified by unauthorized parties. The encryption must be done in such a way that decryption is only possible with knowledge of a secret decryption key. The decryption key should only be known by authorized parties.”

This is a high level description of how RSA encryption works. It is also called public-key encryption, because anyone can obtain a copy of the encryption key it is publically available, but the decryption key cannot be obtained. This makes RSA encryption a secure way of passing data between an individual and a web site.

Simplified view of RSA encryption. Public Domain.

Simplified view of RSA encryption. Public Domain.

Performing this calculation (encrypting and decrypting text) is fairly simple. With a basic understanding of modular arithmetic it can be accomplished. First a public and private key must be produced by following the steps below:

  1. Generate large prime numbers, p and q (these should be hundreds of digits)
  2. Compute the modulus n, n = p×q
  3. Compute the totient, totient = (p-1)×(q-1)
  4. Choose an “e” > 1 that is co-prime to the totient
  5. Choose a “d” such that d×e = 1 mod totient

Once those steps have been completed, a public key (n, e) and a private key (n, d) have been generated. The public key can be distributed to anyone, but the private key must be kept safe. It’s easy to see that without the modular arithmetic this algorithm would be easy to discern. One could generate pairs of random numbers until a pair is found that when multiplied together, would equal the modulus n found in step two above. From there, it would be easy to find all numbers co-prime to the totient in step three. Modular arithmetic then comes into play, because it allows infinite pairs of numbers to satisfy the constraint listed in step five, but it would not allow the user to decrypt the message. In other words, 11+4 = 3 mod 12, but also 11+16 = 3 mod 12. This makes it impossible to determine what the original number was (it could be 4 or it could be 16, or any other multiple of 12).

Once the keys have been generated it is easy to encrypt and decrypt text. To encrypt a message “m,” given the public key (n,e) generated above:

C = me mod n

“C” is then the encrypted message that gets passed to the other party.

To decrypt the message “C” created above, all that is required is the inverse of the operation to encrypt:

M = cd mod n

Let’s do an example to illustrate the instructions listed above (note: we will be using small prime factors because the math is simpler).

  1. Select a p and q that are prime
    1. P = 11
    2. Q = 3
  2. The modulus n is then equal to P×Q = 11×3 = 33
  3. Computing the totient to be equal to (p-1)×(q-1) = (11-1)(3-1) = 20
  4. To select an “e” we must find a number that is coprime to 20
    1. The smallest value that is coprime to 20 is 3 because 3 is the smallest number that cannot divide 20 evenly, so “e” = 3
  5. Now we need to find “d”, d=e^(-1) mod [(p-1)×(q-1)]
    1. Using the Euclidian Algorithm we get d = 7

Now let’s say we want to encrypt the message “4.” To do this we need to know the public key, which in our case is (n=33, e=3).  All we have to do is compute:

 C = 43 mod 33 = 31

We can pass 31 (c=31) along to the website, which will then decrypt it using the private key (33, 7):

 M = 317 mod 33 = 4

Our message has been successfully “passed” from one place to another.

Thoughts

Without the work from previous mathematicians, this process would not be possible. Modular arithmetic plays a crucial role in our everyday lives and we don’t even notice it. I think it’s an amazing mathematical concept and provides a deep insight into the world of number theory. Even today there are computers constantly trying to figure out how to factor large prime numbers without success. I don’t know if RSA encryption will stand the test of time, but for now it’s the best we’ve got.

References

http://en.wikipedia.org/wiki/Cryptography#History_of_cryptography_and_cryptanalysis

http://www.britannica.com/EBchecked/topic/920687/modular-arithmetic

http://mathworld.wolfram.com/ChineseRemainderTheorem.html

http://www.mathaware.org/mam/06/Kaliski.pdf

http://www.numericana.com/answer/modular.htm#modulo

http://en.wikipedia.org/wiki/Carl_Friedrich_Gauss

http://mathworld.wolfram.com/EuclidsLemma.html