Elliptic curve cryptography an introduction

I am not going to pretend to understand the Math involved in this. I do understand most of the basic concepts. Cryptography is vital to keep communications between two or more parties private and unreadable. I have posted in the past about the Nazi Enigma machine and the various ways the allies went about breaking it.

An Enigma machine was any of a family of related electro-mechanical rotor cipher machines used in the twentieth century for enciphering and deciphering secret messages. Enigma was invented by the German engineer Arthur Scherbius at the end of World War I.[1] Early models were used commercially from the early 1920s, and adopted by military and government services of several countries — most notably by Nazi Germany before and during World War II.[2] Several different Enigma models were produced, but the German military models are the most commonly discussed.
German military texts enciphered on the Enigma machine were first broken by the Polish Cipher Bureau, beginning in December 1932. This success was a result of efforts by three Polish cryptologists, Marian Rejewski, Jerzy Różycki and Henryk Zygalski, working for Polish military intelligence. Rejewski “reverse-engineered” the device, using theoretical mathematics and material supplied by French military intelligence. Subsequently the three mathematicians designed mechanical devices for breaking Enigma ciphers, including the cryptologic bomb. This work was an essential foundation to further work on decrypting ciphers from repeatedly modernized Enigma machines, first in Poland and after the outbreak of war in France and the UK.
On 25 July 1939, in Warsaw, the Poles initiated French and British military intelligence representatives into their Enigma-decryption techniques and equipment, including Zygalski sheets and the cryptologic bomb, and promised each delegation a Polish-reconstructed Enigma. Without these gifts of techniques and technology from Polish military intelligence, decryption of German Enigma messages during World War II at Bletchley Park would not have been possible, as it was based on using mathematical theory and the perfecting of methods, tools and devices — all invented and developed beginning in 1932 by Rejewski, Różycki and Zygalski.[3][4][5] From 1938 onwards, additional complexity was repeatedly added to the Enigma machines, making decryption more difficult and necessitating larger numbers of equipment and personnel—more than the Poles could readily produce. The Polish breakthrough represented a vital basis for the later British continuation and effort.[6] During the war, British cryptologists decrypted a vast number of messages enciphered on Enigma. The intelligence gleaned from this source, codenamed “Ultra” by the British, was a substantial aid to the Allied war effort.[7]
Though Enigma had some cryptographic weaknesses, in practice it was German procedural flaws, operator mistakes, laziness, failure to systematically introduce changes in encipherment procedures, and Allied capture of key tables and hardware that, during the war, enabled Allied cryptologists to succeed.[8][9]
The exact influence of Ultra on the course of the war is debated; an oft-repeated assessment is that decryption of German ciphers advanced the end of the European war by two years.[8][10][11] Winston Churchill told the United Kingdom’s King George VI after World War II: “It was thanks to Ultra that we won the war.”[12]

enigma machine

If you want a good book to read there is the history of code breaking in WW2.. The Bletchley Park Codebreakers.

book

Actual Bletchley Park Website
Bletchley park

fiction book on crypto I enjoyed

cryptonomicon in PDF form entire book

elliptic curve

After a slow start, elliptic curve based algorithms are gaining popularity, and the pace of adoption is accelerating. ECC is now used in a wide variety of applications: the US government uses it to protect internal communications, the Tor project uses it to help assure anonymity, it is the mechanism used to prove ownership of bitcoins, it provides signatures in Apple’s iMessage service, it is used to encrypt DNS information with DNSCurve, and it is the preferred method for authentication for secure Web browsing over SSL/TLS. A growing number of sites use ECC to provide perfect forward secrecy, which is essential for online privacy. First generation cryptographic algorithms like RSA and Diffie-Hellman are still the norm in most arenas, but ECC is quickly becoming the go-to solution for privacy and security online.

If you are accessing an HTTPS version of the Cloudflare blog from a recent enough version of Chrome or Firefox, your browser is using ECC. You can check this yourself. In Chrome, you can click on the lock in the address bar and go to the connection tab to see which cryptographic algorithms were used in establishing the secure connection. Clicking on the lock in Chrome 30 should show the following image.

Meaning?

The elliptic curve discrete logarithm is the hard problem underpinning ECC. Despite almost three decades of research, mathematicians still haven’t found an algorithm to solve this problem that improves upon the naive approach. In other words, unlike with factoring, based on currently understood mathematics, there doesn’t appear to be a shortcut that is narrowing the gap in a trapdoor function based on this problem. This means that for numbers of the same size, solving elliptic curve discrete logarithms is significantly harder than factoring. Since a more computationally intensive hard problem means a stronger cryptographic system, it follows that elliptic curve cryptosystems are harder to break than RSA and Diffie-Hellman.

To visualize how much harder it is to break, Lenstra recently introduced the concept of “Global Security.” You can compute how much energy is needed to break a cryptographic algorithm and compare that with how much water that energy could boil. This is a kind of a cryptographic carbon footprint. By this measure, breaking a 228-bit RSA key requires less energy than it takes to boil a teaspoon of water. Comparatively, breaking a 228-bit elliptic curve key requires enough energy to boil all the water on earth. For this level of security with RSA, you’d need a key with 2,380 bits.

With ECC, you can use smaller keys to get the same levels of security. Small keys are important, especially in a world where more and more cryptography is done on less powerful devices like mobile phones. While multiplying two prime numbers together is easier than factoring the product into its component parts, when the prime numbers start to get very long, even just the multiplication step can take some time on a low powered device. While you could likely continue to keep RSA secure by increasing the key length, that comes with a cost of slower cryptographic performance on the client. ECC appears to offer a better tradeoff: high security with short, fast keys.

article on elliptic curve crypto

Good luck NSA