2007-05-30 ---------- 1. Elliptic curve cryptosystems: (*) Some EC crypto history: Introduced in 1985 by Neal Koblitz and Victor Miller independently Koblitz is a professor in math here at UW. --> Show Koblitz's paper (*) NSA intro: First -- NSA is the National Security Agency. Their Mission Statement is: "The ability to understand the secret communications of our foreign adversaries while protecting our own communications -- a capability in which the United States leads the world -- gives our nation a unique advantage." When it comes to crypto, they really really know what they are talking about. (They are also the countries single largest employer of mathematicians, so you might work for them one day.) --> http://www.nsa.gov/ia/industry/crypto_elliptic_curve.cfm "For protecting both classified and unclassified National Security information, the National Security Agency has decided to move to elliptic curve based public key cryptography. [...] The Cryptographic Modernization Initiative in the US Department of Defense aims at replacing almost 1.3 million existing equipments over the next 10 years. Most of these needs will be satisfied with a new generation of cryptographic equipment that uses elliptic curve cryptography for key management and digital signatures." -- NSA "While at current security levels elliptic curves do not offer significant benefits over existing public key algorithms, as one scales security upwards over time to meet the evolving threat posed by eavesdroppers and hackers with access to greater computing resources, elliptic curves begin to offer dramatic savings over the old, first generation techniques." -- the NSA (*) The elliptic curve discrete log problem. Algorithmic attacks on it seem to be not as good as on (Z/pZ)^*. "However, unlike the RSA and Diffie-Hellman cryptosystems that slowly succumbed to increasingly strong attack algorithms, elliptic curve cryptography has remained at its full strength since it was first presented in 1985." -- the NSA (*) Describe Diffie-Hellman ECC on elliptic curve. One agrees on a key using it, then uses AES or some other symmetric cipher to secure the resulting communications. Do an example. (*) The NSA again: "To use RSA or Diffie-Hellman to protect 128-bit AES keys one should use 3072-bit parameters: three times the size in use throughout the Internet today. The equivalent key size for elliptic curves is only 256 bits. One can see that as symmetric key sizes increase the required key sizes for RSA and Diffie-Hellman increase at a much faster rate than the required key sizes for elliptic curve cryptosystems. Hence, elliptic curve systems offer more security per bit increase in key size than either RSA or Diffie-Hellman public key systems." Also, at this size ECC is *TEN TIMES FASTER* than using RSA/Diffie-Hellman. (*) Show the certicom (Canadian company) website: -- the ECC conference "simply the best: --> http://www.certicom.com -- challenge dlogs. --> http://www.certicom.com/index.php?action=res,ecc_challenge -- java demo of point arithmetic (*) Point counting: -- That E(Z/pZ) is "often" smooth was exactly what made the elliptic curve factorization method work. Likewise p-1 is "often" smooth, in which case dlog in (Z/pZ)^* would be easy, since then (Z/pZ)^* product of small groups. -- But if E(Z/pZ) is smooth, then its easy to solve dlog on E!! -- Fortunately, one can compute the cardinality of E(Z/pZ) *surprisingly* quickly, by computing #E(Z/pZ) mod ell for many small primes ell and using the Chinese remainder theorem. (This SEA algorithm is tricky and involves lots of surprising extra structure.) -- Example: sage: E = EllipticCurve([1,2,3,4,5]) sage: time n = E.sea(next_prime(2^359)) # better do 256 bit? (just over 2 minutes!) (n = 1174271291386916613944740298394668513687841274454159935082506569996730478679362265463248629898408225692994640) sage: is_prime(n//2) False But hard to factor... But don't use that prime! (*) ECC Patents (according to Wikipedea): --> http://en.wikipedia.org/wiki/ECC_patents NSA: "Despite the many advantages of elliptic curves and despite the adoption of elliptic curves by many users, many vendors and academics view the intellectual property environment surrounding elliptic curves as a major roadblock to their implementation and use." * Apple Computer holds a patent on efficient implementation of ECC over GF(p) where p is close to a power of 2. * Certicom holds a patent on efficient GF(2^n) multiplication in normal basis representation. * Certicom holds patents which cover the MQV (Menezes, Qu, and Vanstone) key agreement technique. * Certicom holds patent (U.S. Patent 6,141,420 ) on techniques for compressing elliptic curve point representations. * According to the NSA, Certicom holds over 130 patents relating to elliptic curves and public key cryptography in general[1]. NSA paid $25 million to Certicom in order to use ECC in their new "Suite B". (*) Something like RSA that can be used for sending messages to a person that posts a public key that works on an elliptic curve? Yes, ElGamal! But there are actually problems with this... 1. Nikita chooses a prime p, E over Z/pZ, and B in E(Z/pZ), and a random integer n, and publishes her public key: (p, E, B, n*B) 2. Michael encodes a message as an element P in E(Z/pZ); he then computes a random integer r and the points r*B and P+r*(n*B). He sends (r*B, P+r*(n*B)) to Nikita. 3. Nikita can determine P, because she can compute r*(n*B) = n*(r*B) since she knows n. She finds that P = (P+r*(n*B)) - r*(n*B). NOTE: This *is* just Diffie-Hellman, somewhat delayed. The message is encrypted by adding the Diffie-Hellman secret key r*n*B, which both Nikita and Michael can compute, to the message. The trick is -------------- 2. Questions about your projects? * Reminder: I have office hours tomorrow (4-6pm). * Reminder: Now is the time to finish up your projects, as you'll be totally done with Math 480 on Friday.