View source for CryptoReading/4

{{Event
|logo=Norbertgothisbrainmachine2.png
|what=understand crypto ciphers & algorithnms
|who=ptr_
|from=2012/05/18 07:30:00 PM
|till=2012/05/18 11:59:59 PM
|where=HSB
|city=Brussels
|location=50.8730781, 4.3768628
|country=Belgium
|cost=0
}}


= Elliptic Curve Crypto =

LeitMotiv:
* http://phrack.org/issues.html?issue=63&id=3#article


== 101 ==


First it's important to grasp the difference between symmetric and asymmetric crypto.

Symmetric: the 'conventional' way of thinking about enciphering a message ; both Alice and Bob share a key, a secret, unknown to Eve and Everybody Else.  Using this shared secret Alice and Bob can encrypt messages. 

Asymmetric: a scheme pioneered in the 1950s : the key exists in two parts : a message enciphered using one part can be encrypted with the other part, and vice versa... 
Alice and Bob don't share a secret apriori, they can construct a shared secret by doing a little crypto dance together.

== the ground concepts ==

First you need to grasp the concept behind Diffie-Hellman key exchange. 
This video demonstrates the concept effectively : http://www.youtube.com/watch?v=3QnD2c4Xovk 
(btw - these peeps made some other great introductory videos [http://www.youtube.com/user/ArtOfTheProblem ArtOfTheProblem] explaining the basic concepts of crypto) 

The trick to seep through in your braincells  is you can do this same diffie-hellman exchange using different 'number' spaces, as long as they 'behave nicely' and you have a way to count with them.  eg. 1 eurocent coins (maybe something to try next time you do your bookkeeping), mixing color paint, prime modular arithmetic, or other 'finite' fields (galois) and .. points on elliptic curves.

(numbers 'behaving nicely' is investigated in mathematics by the definition of 'groups' and 'fields' -- ah if ever i wouldn't have been sleeping during highschool math courses...)

== public key crypto ==

ok, fine -- we got the idea of DH exchange, but how to use this to generate my public and private key ?  there we need the clever trick called 'elgamal' :  [https://en.wikipedia.org/wiki/ElGamal_encryption wikipedia] 



== play with elliptic curves in SAGE ==

SAGE is an opensource python library, doing a lot of crazy algebraic stuff.
here a small script to generate the necessary parameters & execute a small test:
(too lazy to install it locally? http://sagemath.org/eval.html saved my day)

<pre>

f.<t> =  GF(2^53)
d = t.charpoly('t')

print "poly: ",d
print "      ",d.coeffs()

E = EllipticCurve(f, [1,1,0,0,t^4+t^2+1])
print E

print "order: ",hex(E.order())

base = E.gens()
print "basex: ",hex( base[0][0].integer_representation() )
print "basey: ",hex( base[0][1].integer_representation() )
print "basez: ",hex( base[0][2].integer_representation() )


point = base[0]
priv = 0x15ab45d7bd
print "priv: ",hex(priv)

pub = priv * point
print "pubx: ",hex( pub[0].integer_representation() )
print "puby: ",hex( pub[1].integer_representation() )
print "pubz: ",hex( pub[2].integer_representation() )

k = 0x09f1a7fed8c882

Z = 2 * pub *k
print "Zx: ",hex( Z[0].integer_representation() )
print "Zy: ",hex( Z[1].integer_representation() )
print "Zz: ",hex( Z[2].integer_representation() )

R = point * k
print "Rx: ",hex( R[0].integer_representation() )
print "Ry: ",hex( R[1].integer_representation() )
print "Rz: ",hex( R[2].integer_representation() )

Z = 2 * R * priv
print "Zx: ",hex( Z[0].integer_representation() )
print "Zy: ",hex( Z[1].integer_representation() )
print "Zz: ",hex( Z[2].integer_representation() )

</pre>


a possible (the output of E.gens varies) output of this script is this :

<pre>
poly:  t^53 + t^6 + t^2 + t + 1
       [1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
Elliptic Curve defined by y^2 + x*y = x^3 + x^2 + (t^4+t^2+1) over Finite Field in t of size 2^53
order:  1ffffffe699516
basex:  0xce634494a881
basey:  0x10500ef903a521
basez:  0x1
priv:  15ab45d7bd
pubx:  0xc81fdfee9034c
puby:  0xe108030802008
pubz:  0x1
Zx:  0x1f18d325dc4b42
Zy:  0x95a278f07ecb6
Zz:  0x1
Rx:  0xd0fb25f17cac0
Ry:  0xadf50b2db78fd
Rz:  0x1
Zx:  0x1f18d325dc4b42
Zy:  0x95a278f07ecb6
Zz:  0x1
</pre>


== why? ==

My incentive to investigate this is some vague idea to make electronic keys for our hackerspace (based on ATtiny1634 or something). And just because a decent electronic key needs crypto (don't want to make it too easy to sniff those bits & copy some extra keys, do you?) - plus it's a great opportunity to learn a thing or two (for sure considering this endeavour gets beyond the 'unfinished project' state is very small).

There are decent symmetric ciphers implementations around, targeted to the avr atmega/attiny-platform (http://www.das-labor.org/wiki/AVR-Crypto-Lib/en), but I'm hesitant to use those -- too many curious dudes around waiting for a reason to dump an eeprom... Asymmetric crypto will allow a setup where the door-lock controller (authenticated using pub/privkey) checks  the one-time-pad-token on the key: each time you use the lock your existing token is checked and invalidated, and a new token is written to the key -- so there's no incentive in copying keys.

So been on the lookout for asymmetric (public/private key) algorithms.

As the processor powering the arduino (aka quick and dirty proof of concept)  proves quite limited when doing anything non-obvious -- both the speed (16 MIPS) & memory (2KB) are restrictive, with the additional hurdle of the small register-size (8-bit) & associated compiler types (avr-gcc has 16-bit int) -- grabbing some generic code off the internet-shelf & kick it in place is not a real option.

Luckily [http://www.pittnerovi.com/jiri/hobby/electronics/crypto/ this dude] paved the way adapting the phrack-magazine (issue 63) code for ECC asymmetric crypto to run on these devices.  This implementation compiles fine and sets some all too decent default ECC-related parameters (Curve B-163), calculating correct results.  Alas, it's _way too slow to be of any use.  

So for fun and profit (imagine harvesting all those wasted clock-cycles...) let's generate some weaker but _fast settings. 

  A little endeavour into generating our own ECC parameters 
  (don't use these for any real-life purpose, I'm a noob in these matters)...



== good info ==
* give the finite fields some love and attention: http://libecc.sourceforge.net/reference-manual/group__theory__polynomial.html

== didn't read this yet ==
* http://labs.oracle.com/projects/crypto/CHES_2004.pdf


try it: [[File:ecc-code.tar.gz]]