ECC is one of the most complex AND computationally intensive encryption routines, due to the nature of Elliptic Curves. ECC is based upon solving the discreet logarithm problem and that in itself requires a very high level of knowledge of mathematics.
I'd recommend strongly that you try something simpler first, or implement what you're trying to do in 16 or 32-bit on a normal PC architecture and then convert it to 8 bit for the Arduino.
If you haven't written cryptography algorithms before I would be very impressed if you manage to pull this off within 12 months with an Arduino.
Sorry to put a downer on this idea, but you have to start small and work your way up - jumping in at the deep end and drowning is the best way to put someone off swimming.
If you're determined to do this, try implementing first ElGamal encryption, or the Digital Signature Algorithm (DSA), which both use discreet logarithms.
- Tim