The Mod(ular) Squad: Elliptic Curve Cryptography

A few years ago, after a long day (for a fifth grader) of studying long division, my daughter exclaimed that she saw no practical use for remainders. It reminded me of a similar day, sitting in a computer science class on computational complexity, of feeling that there was no practical use for knapsack problems. Both, it turns out, are the basis for many of the cryptography systems in vogue for online security and identity based systems. The exponential complexity that makes a problem intractable also makes it stronger in the face of brute-force attack, and the use of remainders (particularly the Chinese remainder theorem) makes it practically computable. Realizing that Professor Steiglitz was most egregiously correct (back in 1983) when he warned us that large prime numbers were in our futures, remainders, NP-complete problems and computational complexity all go "click" when I'm indulging my eBay habit.

Fast forward a few years: large-scale compute grids enable brute-force attacks against weaker (shorter key length) crypto systems, and increasing the key length to stay one or two hops ahead of the bad guys means additional drains on power, performance and time. Particularly bad things if you're worried about securing a data path to your mobile device, where power and time equal battery life. What's needed is a crypto system that uses shorter key lengths to produce a stronger system, and the click-fitting math this time are elliptic curves, providing a more efficient way to tackle the factoring problems underlying crypto systems. The result - elliptic curve cryptography - is a promising step in making systems more efficient and secure at the same time.

Aside from reading Simon Singh's Fermat's Enigma, which neatly tied together modular forms, elliptic curves, Fermat's Last Theorem, and Princeton University, I am, in the words of Napoleon Dynamite, in the need of some skills. For higher math, bigger invention and practical applications of all of the above, I had Sun Labs Distinguished Engineer Vipul Gupta join me for our Innovating@Sun podcast on Cryptography Breakthroughs. It's the current equivalent of being told that large prime numbers are in your future.

Comments:

Post a Comment:
Comments are closed for this entry.
About

Hal Stern's thoughts on software, services, cloud computing, security, privacy, and data management

Search

Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today