Attempt at using using traits and impls to abstract EC functionality. A PoC. Requires the latest commit of Cairo.
This wouldnt be possible without advanced u256 integer operations built by orizi , u256 literal by greged93 and Shahar Papini for explanation on how to use the trait and impl system. Thank you very much. I couldnt get radix limb operations for modular u256 math to work.
Thank you Cairo team for giving us this language, its design and for building in public.
An impl of NIST-256 or seck256r1 is available and working. One can see the tests to use this implementation
Available:
- key-gen, on curve verification. with respective nist test vectors
- signing and signature verification. need to add NIST test vectors
Issues/Problems to fix:
- Implementations not efficient. Tests will validate this and also gas required for tests. especially during signature verficiation
- egcd is not robust and written assuming primes and not using traits. will remedy this
- No message hashing inside the verification example. The cairo impl used to generate sha256 hashes
- Till i improve the ec add operation itll be difficult. I intend to continue on this and push better impls. i cant run complete sha + verify in a single test. My machine is getting overwhelmed. I dont have enough RAM and Swap. Please add
[ignore]
to tests in sig_ver if problems
For suggestions, suggestions and criticism regarding implementation and design, i would definitely like to hear them and improve from advice. Please raise a PR or One can ping twitter and discord @ 0xspleen#1434
Parameters
Important Resources used
- https://cacr.uwaterloo.ca/hac/about/chap14.pdf
- https://www.bearssl.org/bigint.html
- https://www.math.brown.edu/johsilve/Presentations/WyomingEllipticCurve.pdf
- https://rosettacode.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm#Python
- https://www.cs.uaf.edu/2015/spring/cs463/lecture/02_20_ECC.html
- https://crypto.stanford.edu/pbc/notes/elliptic/group.html
Need to checkout
- https://eprint.iacr.org/2015/1060.pdf .. Fixed steps for computing
Projectitve
Test vectors For Key Pair
- https://csrc.nist.gov/Projects/cryptographic-algorithm-validation-program/digital-signatures TODO: NIST thas some out of range error.. i have not accomodated for it. file: PKV.rsp
For Scalar Mul, They have scalars greater than U256, i havent accounted for them now