Reporting — 18 December 2015

by

Walker Rowe

There has been much talk lately about the inability of the US and other governments to read encrypted ISIS and Al Qaeda messages.  Here we explain, in the simplest possible terms, why that is the case.  It’s all based on a 2,000 year old math problem that no one has yet solved. And the irony of this is that the software used for encryption was built by engineers who were working under US Department of Defense contracts. So the American military has funded the development of weapons that are now being launched against it.

Of course the government can plug directly into Whatsapp and other applications to read encrypted traffic.  But if the terrorists simply don’t use Whatsapp, but use their own computers, then the NSA cannot read their encrypted messages, unless they have a spy inside of ISIS (Which we hope they do.).

The software to encrypt data is free to download. One version of it is right here.  Anyone can read it, so they can check that the NSA has not tapped into it before they use it themselves.

Here we give an overview of how encryption works so that you can see that no intelligence agency can defeat it when ISIS moves their communications off Whatsapp and installs it on their own server.

Encryption is based on prime numbers and the difficulty of figuring out if a number is prime.  Prime numbers are numbers like 1,3,5,7, … that are divisible only by themselves and 1.  For example 6 is not prime because 6=2×3.

The Greek mathematician Euclid first looked at this problem 2,000 years ago.  Then in the 17th, 18th, and 19th centuries the best mathematicians in history, Gauss, Euler, Fermat, and Poincaré, all tried to solve this problem.  While they came up with some very clever algorithms that work some of the time, they do not work all of the time.  In fact, the best that the mathematicians can do is determine whether a number is probably prime.

Encryption works by multiplying two very large prime numbers together and using that as the key to encrypt data.  If you can figure out what one of those numbers is then you automatically know the other.

For example, if your message is “Meet me in Jihad.” that can be turned into a string of numbers, say, “123.”  Then you pick any two prime numbers, say 3 and 5 and multiple them together, 3×5=15. Then you pick some algorithm, and apply that to 123 and 15 to create another number.  For example your algorithm could just multiple the the numbers together 123×15=1845.  Now “1845” is the encrypted format of “Meet me in Jihad.”  No one can read that unless they can figure out the key used to generate that number and knows the algorithm.

All the algorithms used to generate the encrypted message are well known.  That’s not a secret.  Most systems use the RSA one or AES.  RSA was created in 1978 based on research done at Princeton and other places in the 1940s.  But knowing the algorithm does not help at all.

The NSA nor any mathematician in 2,000 years has been able to figure out what is the key without guessing every possibility, which takes to long to be practical.  Mathematicians have done that and have shown that that can take more than 2 years on even the fastest computers.

So faced with this problem, the NSA proceeds like this:

Suppose the hackers have used the number 15, as in our example, as the key.  The NSA then tries all possible numbers less than 15 to look for one that divides 15:

1: No. It is not necessary to check that one.

2: You skip that one too as 15 is not even.

3: That one works because 15/3=5.  So 15=3×5.  So the encryption key is either 3 or 5. Just try both of them and all the algorithms we know and see which reveals the message.  (What if the terrorists made their own algorithm? Mathematicians would quickly crack any new algorithm as there are no more secrets in that field of mathematics. Or they would know that someone had developed a new algorithm and then quickly pick it apart.)

But that is a simple example.  Encryption works using extremely large numbers that take computers hours, day, or even years to attack.  For example a team working at Princeton cracked a 1024 bit (I will explain what a bit is in a second.) number using hundreds of computers wired together.  It took 2 years.

A bit is how a computer stores numbers.  A bit is either a 0 or 1. Every number can be represented as bits.  For example 1,2, and 3 are 001, 011, and 111 respectively.

Most web sites, like Twitter, use 2048 bit numbers to encrypt the data going there and coming back.  Not even Google Sheets or Microsoft Excel can handle a number so large.  Try it for yourself. Go into Google sheets and write “=power(2,2048)” and it will give an error.

The largest number that Google Sheets can handle is with 10 with 30 zeros which is written 10^30.  This is 2 raised to the 1,000 power or 2^1000.  The number of atoms in the universe is only 10^80. How big do you think 2^2048 is? (Hint:  Read Jorge Borges short story “Tower of Babel” to understand that.)

So, what can the NSA do when faced with a number like?:

1010010101010100101011111110101010101010101010101001111111111111111110111001010110011111111111111110010101101010101010101001010100101011111101011010101010111110000001010101010101010101111111100001111111111111110101010101010101001010101001010101010010101010101001

It would take their computers years to churn through all the numbers less than this number to find which one is a prime number. (Actually they only need to check up the square root of the number, which is sort of hard to see unless you observe that 2*3=6 is also 3*2=6.)

But encryption can be defeated if the NSA goes around it, which is what they do. They can go to Google, Facebook, Whatsapp, and all the other tech companies and plug directly into those computers.  A computer has to decrypt a message in order to read it.  So at some point the memory of the computer will say “Meet me in Jihad.” in clear text, which anyone can read.

But the problem is even if the NSA taps into Whatsapp, ISIS and other terrorists can simple download and install encryption software. For example, they can use Torchat. which is right here, and run that on the Tor encrypted network. That too was developed by the Department of Defense.  It is right here.

Tor not only uses this prime-number encryption to encrypt messages, it bounces the traffic all around the world to hide where the users are located by hiding their IP address.  The US government requests its employees to use Tor when they travel overseas to protect their messages from spying.

A hacker can read the Tor source code, so they would see if the NSA had put a backdoor in there.  If they did they would simply delete that part. Then they can take that code and give it to their army of terrorists to install on their computers or cell phones.  There is no way that the NSA can tap into that unless one of the ISIS people reading that reads it to the NSA, i.e., a spy on the inside.

So do you see why the NSA cannot hack ISIS encrypted traffic? They can do it at Whatsapp, if Facebook lets them, which you know they will.  But Allah Kaboom Akbar can simply download Euclid’s 2,000 year old math problem and use that to foil the intelligence agencies.

All of this is fact. If anyone had figured out how to determine whether a number is prime (meaning how to factor the product of two prime numbers) it would make international news that no government agency could contain.  That person would win the Fields Medal, which is the Nobel Prize for mathematicians.

Note: Here is a much more complicated way of explaining all of this with an actual example.

 

Share

About Author

(2) Readers Comments

  1. RSA, which relies on factoring the product of 2 huge primes, is used in key exchanges more than actual encryption. It’s way too slow and the primes needed to be “safe” now are up to like 4000 bits. It’s also been broken by a hybrid quantum/classical algorithm just waiting for a quantum computer with sufficient q-bits. Elliptic curve is the most secure method in use today, and is strong enough, given the right curve, with 192-bit keys. The multivariate quadratic problem is even newer, supposedly NP complete given the right public key polynomial, and quantum computer safe. though it still needs more vetting. It’s the fastest and simplest of the lot to implement, too. No huge integers are needed.

    • I’ve got the read up on the ecc. I think an ecc in mathematics is in the realm of number theory so it has something to do with prime numbers. Meaning it’s still based on that basic problem of having to churn through trying to find prime factors.

Leave a Reply

Your email address will not be published. Required fields are marked *


nine × = 27