Tag Archives: cryptography

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

Advertisements

The Diffie-Hellman Key Exchange

Scenario:

Let’s say we have a crowded room of people. Anyone in the room can talk to anyone else, but when they do, everyone else in the room can hear them. If you wanted to exchange secret information with another person, anyone could lean in, listen, and steal your secrets. So maybe you think about the possibility of using a cipher of some kind to mangle your message to the effect that only the person the message was meant for could unscramble it and understand its meaning. The obvious problem with this idea is that you would first have to tell the person the key to your cipher, and you would be back to square one. Anyone could listen, hear the key, and decrypt the messages for themselves. What if I were to tell you, however, that there is a way for two people in the room to each shout a special message and from there be able to encrypt all of their future messages with a secure unbreakable cipher that nobody else could possibly figure out? By the end of this post, you will see how this is possible. Some of you may already know where this is going and for those who don’t, allow me to introduce the magic that is known as the Diffie-Hellman Key Exchange.

Introduction:

What is now known as the Diffie-Hellman Key Exchange was first published by the scheme’s namesakes Whitfield Diffie and Martin Hellman in 1976. Much later, it became known that the British signals intelligence agency, GCHQ, had developed the same scheme as early as 1975. Up until this point it was agreed upon in the cryptography community that the only way to establish a secure cipher between two communication points was to first exchange a cipher key in private. To be able to subjugate the need for this initial private meeting was a really big deal, especially given the implications it has for the Internet (computers communicating across long physical distances). To compare to the above example, the internet can easily be described as the largest crowded room of people ever. I am now more than 300 words into this post without tying it to any subject material from our class, however. It’s time to talk about the mathematical techniques that make this all possible.

Modular arithmetic in the context of cryptography:

I think it was really fortunate that we had a lesson in class on the beginnings of modular arithmetic. As a computer scientist, it has opened up a huge realm of blog post topics that I can speak about from a knowledgeable perspective due to so many CS topics relying on the techniques of modular operations. My favorite layman’s description of modular arithmetic is taking a number of hours, and translating them onto a clock. A clock, of course, only has 12 possible positions for the hour hand to fall under. So given a measurement of time that is greater than 12, what are we to do? Anyone can see how 10 hours measured on a clock would point the hour hand to the number 10. Likewise it’s easy to understand how 22 hours would wrap around and also point the hour hand at the number 10. Our brains have gotten good at automatically doing the modular arithmetic in this situation. In terms of math, all we are doing is dividing our number by 12 and then taking the remainder. 22 / 12 = 1 remainder 10. We would define this by saying 22 mod 12 = 10. Without really thinking about it, using these simple techniques, we have created a mechanism that is both necessary and perfect for cryptography and almost all modern forms of ciphering messages. Modular arithmetic provides us the functions we need to create something that is really easy to calculate in one direction, but is impossible to calculate in the other direction. Given the number 10, is there any way to tell what number of hours we had originally? It could be 10, it could be 22, it could be 34, or it could be any multiple of 12 with an added 10.

Diffie-Hellman Key Exchange example:

So how does the Diffie-Hellman key exchange actually work? Lets lay the key equations out first.

Now these are a lot of terms that mean nothing now, but I will define them as we go. Lets walk through the steps of the exchange:

      1. The numbers g and p are predefined numbers and known by everyone. For security’s sake and deeper reasons I won’t go into, g and p should be prime.
        • For our example, lets use the common values for this problem: g = 5 and p = 23
      2. Each party involved chooses a secret number they will keep private.
        • Lets say that A chooses their number to be a = 6, and B chooses b = 15.
      3. Party A then computes their shared value to be equal to Sa = ga mod p.
        • In this example ga mod p = 56 mod 23 = 8
      4. Party B then computes their shared value to be equal to Sb = gb mod p.
        • In this example gb mod p = 515 mod 23 = 19
      5. The parties involved now shout their shared values Sa and Sb to each other, not caring if anyone hears.
        • A shouts their number 8 to B, and B shouts their number 19 to A.
      6. Now we take into account the equations above. Each party now calculates the final shared secret, SS, using SS = Sba mod pfor party A, and SS = Sab mod p for party B.
        • Party A computes the value: SS = Sba mod p = 196 mod 23 = 2
        • Party B computes the value: SS = Sab mod p = 815  mod 23 = 2
        • Now both parties have a shared secret SS = 2 that they were able to compute and never send over the wire!

These are a lot of numbers to try and make sense of. The picture of why this works is very unclear. My favorite example of why this works that is easier to understand is one to do with colors and mixtures of paint, the diagram for which comes from a professor by the name of A.J. Han Vinck at the University of Duisburg-Essen.

caption

Image: A.J. Han Vinck

If we can convince ourselves that raising one number to the power power of a second number and then taking the modulus of that number is similar to mixing two colors of paint together, this example makes a lot of sense. We see that we start out with everyone knowing a common paint color. This would be our values of g and p. Both Alice and Bob then choose a secret color. These would be a and b from our above example. They then mix the color of paint they are going to send over the wire. These are the light orange and blue colors we see going over public transport and from our example, we know them as Sa and Sb. On the other side of the transport, the respective parties add their own secret colors to the mixture they received from the other. In the end, the exact same ingredients have been added to both parties mixture of paint so intuitively the end result is the same. As a third party, even if you knew about the two colors of paint that were publicly shared, you could never separate out those colors and know what the secret colors of Alice and Bob were. You would never be able to construct the all important final color.

Once there is a secret established between the two parties, they can use the key in a wide variety of ciphers including just using it to mangle a single message (known as a one time pad). The practical uses of Diffie-Hellman have a few restrictions on the numbers g, p, a, and b in order to keep the keys unbreakable. For instance, the number p must be a very large prime number. With these proper requirements in place though, you can find this trick employed all over the internet. Versions of it are included in almost all “secure” or “encrypted” network connections.

source material: Color scheme image: A.J. Han Vinck, University of Duisburg-Essen SVG version: Flugaal – A.J. Han Vinck, Introduction to public key cryptography, p. 16

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 – Keeping Our Online Secrets Safe Since the 90s

ElectronicMediaPieChart

A breakdown of time Americans spend with electronic media. Image: Courtesy of http://www.statista.com/chart/1971/electronic-media-use, Felix Richter

We live in an era where the internet is king. Between our cellphones, tablets, game consoles, laptops, and other devices, the average American adult (18+) spends 11 hours per day ingesting electronic media in some way, shape, or form.  I’m sure we can all admit that on a weekly basis we access or create data that we don’t necessarily want the public to see. Whether it be our bank account or credit card information, our Facebook interactions, our emails, our tweets, our PayPal activity, or even our browsing history. That being said, I’m sure some of us take our internet privacy for granted; but how exactly does are internet privacy remain… private? The answer is simple: modular arithmetic. More specifically, cryptographic algorithms.

A History of Cryptography

Cryptography dates back to Egyptian scribes in 1900 B.C., and it was first used in their hieroglyphs. The Egyptians presumably wanted hide the content of their hieroglyphs from others, and they used very basic cryptography to do so. As you can imagine, this whole “keeping a message’s content safe” idea would become widely popular as mankind become more and more intelligent. The Romans, specifically Julius Caesar himself, created the first truly math-oriented cryptography. He used it primarily to protect messages of military significance. Caesar’s cryptographical ideas would later be used to build out modern day cryptography.

There are two main types of cryptography widely used across the web today: symmetric-key encryption, and asymmetric-key encryption (we’ll go into details later, I promise!). Both of these types of encryption rely on modular arithmetic. We must give credit where credit is due. Friedrich Gauss (1777-1855), birthed modular arithmetic in 1801. Believe it or not, this famous mathematician made most of his breakthroughs in his twenties! For those that aren’t familiar with modular arithmetic, here’s a timeless example (pun intended, wait for it…).  The length of a linear line can have a start and end point, or it can go on to infinity in either direction. In modular arithmetic, the length of a “circular” number line is called the modulus. To actually do the arithmetic, consider this example: Take a regular clock (see, here’s the pun!), consisting of the numbers 1-12 . Clocks measure time on a 12 hour time table before starting back over at 1. The modulus for a 12-hour clock is 12 because it has 12 different numbers for the number of hours. To actually do the arithmetic, take this for example: It’s 8PM and we want to add 9 hours (8 + 9 mod 12). 8 +9 equals 17, however when using a modulus of 12, our number line wraps back around after counting to 12. For this we would count forward from 8 – ie. 8, 9 ,10, 11, 12, 1, 2, 3, 4, 5. So, (8 + 9 mod 12) = 5 AM in this case.

Caesar Cipher

CaesarCipher

A basic Caesar Cipher using a left shift of 3. Image: Matt_Crypto, via Wikimedia Commons.

As I said above, the Caesar cipher has acted as a building block for some of our modern day cryptography. Caesar’s main encryption step is incorporated in some of the more complex schemes we still rely on today. However, the Caesar cipher can be easily broken, or decrypted (more on this soon!). This particular cipher is concerned with the alphabet. The theory behind it is replacing each letter in the alphabet with a different letter some fixed number of positions down the alphabet (this is reffered to as the shift). For instance, with a shift of 3, A would replace D, and B would replace E.

Original: ABCDEFGHIJKLMNOPQRSTUVWXYZ

Cipher:   XYZABCDEFGHIJKLMNOPQRSTUVW

This can be represented mathematically using modular arithmetic. The encryption of any letter ‘x” by a shift ‘n’ can be described as follows:

Encryption:

E(x) = (x + n) mod 26

Decryption:

D(x) = (x – n) mod 26

Brute-Force Attacking:

This cipher is extremely easy to break. There are only 26 possible shifts (26 different english letters). When taking a brute-force approach, it’s only a matter of varying through the different shifts until the message is decrypted. In fact, this process could be optimized by analyzing the encrypted string, finding frequently used letters and associating them with common vowels. That way, you could brute force using intelligent shifts. However, this approach would have to be modified when switching between languages.

Cryptography Online

As promised, I will explain the two types of internet cryptography. First, we have symmetric-key cryptography. This is based on the concept that both communicating parties share the same key for encryption as well as decryption. This key is mathematically applied to a numerical equivalent of the data each party is encrypting/decrypting. It is imperative that this key is kept secret. If another party finds out what the key is, none of the encrypted data is safe anymore. Symmetric-key cryptography uses either stream ciphers (encrypt the numerical representation of the data one digit at a time.), or block ciphers (taking blocks of digits, and encrypting them as a whole). Symmetric-key algorithms have an advantage over asymmetric in that they require less computational power.

AsymmetricCrypto

Asymmetric-Key encryption. Anyone can encrypt data using the public key, but the data only be decrypted with the private key. Image: Dave Gothenburg, via Wikimedia Commons.

As for Asymmetric-key cryptography (aka public-key cryptography) we use a slightly different approach. This cryptosystem implements both a private and public key. The public key is used to do the encryption (just like symmetric key cryptography), but the private key is used to do the decryption. The word “asymmetric” stems from the different keys performing opposite functions. This type of cryptosystem is more user friendly, and requires less administration. This is why public-key cryptography is widely implemented across the web.

The RSA Cryptosystem

The RSA cryptosystem is one of the most practical applications of modular mathematics we see today. In fact, if you look at your browser’s address bar right now and you see an “https” at the beginning of your URL, you’re more than likely relying on an RSA encryption to keep your data secure. RSA was created was created in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT. As far as cryptosystems are concerned, RSA in particular is one of the most straightforward to visualize mathematically. This algorithm consists of three parts: key generation, encryption, and decryption. I will be walking through a widely-used example using 3, and 11. Not only does this process use Gauss’s modular arithmetic, it also uses Euler’s totient function φ(n). (A function that counts the totatives of n – the positive integers less than or equal to n that are relatively prime to n.)

Generating the key is the most confusing part, but here’s a somewhat simplified version (don’t get nauseous!):

  1. Randomly pick 2 prime numbers p and q : p=3 q=11
  2. Calculate the modulus : n = p * q  ->   3 * 11 = 33
  3. Calculate the totient φ(n)  : z = (p – 1) * (q – 1) -> ( 3 – 1) * (11 – 1) = 20
  4. Choose a prime number k, such that k is co-prime to z : k=7
  5. n and k become the public key
  6. Calculate the private key : k * j = 1 mod z | 7 * j = 1 mod 20
  7. In the previous step, we’re only interested in the remainder. Since we’re working with small numbers here, we can say –> 21/20 gives us “some number” with a remainder of 1. Therefore – 7 * j = 21 -> j = 3
  8. j becomes the private key

After the public and private keys are generated, encryption and decryption become easy!  Given P is the data we’d like to encrypt and E is the encrypted message we want to generate:

P^k = E (mod n)  – When P (data we’d like to encrypt) = “14”  We get: 14^7 = E mod 33  So E=20

Given E is the encrypted data we’ve received, and P is the data we want to decrypt:

E^j = P ( mod n) – 20^3 = P mod 33  So P = 14

This proves RSA works!

Does the RSA Cryptosystem Really Keep Me Safe?

Theoretically, a hacker could factor the modulus “n”  in the steps above. Given the ability to recover the prime factors p and q an attacker can compute the “secret exponent” “d” from the public key (n, e). Once the hacker has this “secret exponent”, they can decrypt all data sent with its matching public key. RSA keeps us safe from hackers because there is no known algorithm (The NSA probably has one!) that can factor these large integers in a timely manner. In fact, the largest known number ever factored was 768 bits (232 digits!) long, and this was done with a supercomputer using a state-of-the-art implementation. If that doesn’t make you feel safe enough, RSA keys are typically 1024 to 2048 bits (617 digits!) long, so we don’t need to worry about our data getting hijacked. However it is recommended that we use a value of n that is at least 2048 bits long to ensure the encryption is never cracked.

Sources:

http://en.wikipedia.org/wiki/RSA_(cryptosystem)

http://blogs.ams.org/mathgradblog/2014/03/30/rsa/

http://www.studentpulse.com/articles/41/a-brief-history-of-cryptography

http://www.ti89.com/cryptotut/mod_arithmetic.htm

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

http://cunymathblog.commons.gc.cuny.edu/

How and Why RSA works:

https://www.youtube.com/watch?v=wXB-V_Keiu8

Code Breaking: Bletchley Park and Bill Tutte

While brainstorming ideas for a blog post, I found myself wondering if math has ever directly saved lives. After looking into many options, I ran into a story about a place called Bletchley Park. It was known as the Fortress of Secrets and was said to have saved millions of lives yet didn’t even appear on any map. Nicknamed ‘Station X,’ it was solely designated for breaking codes, specifically ciphers. In World War II, direct communication between leaders and various units around the world was a big problem. These orders/war plans were coded and broadcast via wireless radio, but because they could be so easily intercepted, they became increasingly vulnerable. The solution to this problem was the cipher machine. Adopted in 1926, the Germans’ answer was called the Enigma.

A Lorenz machine. Image: Public domain, via Wikimedia Commons.

A Lorenz machine. Image: Public domain, via Wikimedia Commons.

The Enigma was thought by the Germans to be unbreakable and safe for them to use. Its code was especially hard to crack because each time a key was pressed, its internal wiring was changed. In light of this, the British started to recruit brilliant mathematicians to engage in a battle to learn the enemy’s secrets. The Enigma machine required 6 people to operate, so Hitler ordered even more security. Thus, the Tunny cipher machine was born (also known as the Lorenz Machine). This machine generated code with its 12 wheels and only required two operators to send and receive information. To function, it would first apply two keys, encoding the message twice. The first cipher used 5 wheels with, the second used another 5, and then 2 additional wheels would cause a stutter of random letters that would try to throw off unauthorized decoders. Each wheel had a different number of spokes or choices on it which resulted in 23*26*29*31*37*41*43*47*51*53*59*61 = 1.6 million billion possible combinations!

Here is an example of coding one letter into another: The initial letter is “A,” and the cipher code is “K.” They would be “added up,” and if the corresponding symbol was different, then you would mark down an “x.” Inversely, if it was the same, then you would mark down a *. Here we can see A being coded into the letter N:

A= x x * * *

K= x x x x *

———————–

* * x x * = N

The code’s downfall began with the Germans’ overconfidence in the Tunny machine. A 4000 character message was sent, but the receiver didn’t quite get it, so a re-send was requested. The sender failed to change the wheel settings and re-sent the 4000 character message but it was slightly different. This provided Bletchley with a data set with which he could attempt to crack the code. John Tiltman, a mathematician who led the research department at Bletchley, initially worked on this break but passed it onto Bill Tutte.

Bill began by putting the 4000 word message into columns and made a rectangle out of it. He then looked for repetitions/patterns. Every 23 characters there was a rotation, but he then thought maybe it was 25. So he tried to multiply 23*25 to see if the pattern extends along that but it was inconclusive. But the pattern did extend along 574. He then thought maybe it was 41 as that is the prime number of 574. Resonance occurring after 41 strokes made him deduce that the first wheel had 41 spokes. He then went to the next wheel and so forth. Bill Tutte managed to diagnose how the machine worked without ever actually seeing the machine.

He also worked out a statistical mathematical method of breaking the Tunny code, called the “1+2 – break in method.” To use this decoding method required a massive amount of number-crunching and checking. This is where his co-worker Thomas Flower’s brilliance came into play. He conceptualized Bill Tutte’s method and produced one of the first computers, The Colossus, the world’s first semi-programmable computer completely invented from scratch. With this cracked code—and the computer to help crack it—huge battles were won. It is widely credited with turning the tide of the entire war.

World War II is estimated to have cost 10 million lives per year. Cracking the Tunny code was said to have shortened the war by at least two full years! However, everything involving these machines and ciphers had to be kept secret. The brilliant men involved could not publicly get credit for their achievements for quite some time. Eventually, the secrets were declassified, and Bill Tutte was awarded a membership of the Royal Society. In 1987, he finally signed his name in the Royal Society book where his signature lies alongside those of Isaac Newton, Charles Darwin, Winston Churchill.

Sources:

BBC Documentary: http://vimeo.com/31185786

http://www.bletchleypark.org.uk/content/hist/worldwartwo/enigma.rhtm

http://www.bbc.com/news/uk-england-suffolk-29064159

http://www.english-heritage.org.uk/bletchleypark

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