3
$\begingroup$

I am writing an Elliptic Curve Cryptography SDK in pure Swift, and currently I am only using Affine Point and simple Double-and-add. I am soon about to work on a faster solution.

I am asking for help with the fastest known ECC arithmetic. Of course, we have different types of curves, so the answer is probably that some solutions only apply to certain curves (e.g. for Montgomery Curves we can use "Montgomery ladder" which seems fast).

(This question itself probably contains some errors, misunderstandings or inaccuracies, I apologize for that I am quite new to this. Give comments about my question I will correct it and type which corrections I did in an edit.)

Different curves/forms?:

  1. Edwards
  2. Montgomery
  3. Weierstrass
  4. Hessian

Point multiplication algorithms

The wikipedia page about Elliptic Curve Point Multiplication gives a good overview, listing some different algorithms:

  1. Double-and-add
  2. Windowed method
  3. Sliding-window method
  4. w-ary non-adjacent form (wNAF) method
  5. Montgomery ladder (Only for Montgomery curves?)

Coordinate systems

I know that I can use a combination of different coordinate systems:

  1. Affine
  2. Projective
  3. Jacobian (Weighted Projective)
  4. Modified Jacobian
  5. López–Dahab
  6. Chudnovsky Jacobian

Promising papers

The paper Complete addition formulas for prime order elliptic curves by Renes et al from 2015 (download from iacr.org) lists many different algorithms some of which mixes different coordinates systems looks promising.

The paper Fast elliptic curve point multiplication for WSNs by Ravi Kodali from 2013 (download from researchgate.net) proposes a mixture between Projective and Jacobian coordinates in combination with w-ary non-adjacent form (wNAF) method. It shows some promising results.

Does anyone have a reference to a study, implementation of different algorithms or otherwise "truth" about which solution - a set of coordinate systems and algorithms that enables the fastest known Point multiplication for e.g. X25519 (Curve25519) (Montgomery curve) and secp256k1 (Not Montgomery)???

$\endgroup$
  • 1
    $\begingroup$ Implementing a ECC library is certainly a learning experience... and on that basis alone it has value. Keep in mind that the fastest and most secure implementations generally implement the lower-level math in hand-written assembly language so that it can be optimized and also maintain consistent timings. If you want something fast, look at libsodium (there are Swift bindings somewhere). I've some experience here, so if you're looking for a less-optimized example, you might compare to github.com/jadeblaquiere/ecclib (Swift bindings would be very welcome, by the by). $\endgroup$ – jadb Jul 23 '18 at 21:11
  • 2
    $\begingroup$ Are you aware of the issue of timing attacks? ¨Pure (insert high-level language) crypto libraries very often have issues on that (except when they are limited to signature verification, where nothing is secret). $\endgroup$ – fgrieu Jul 23 '18 at 21:54
  • $\begingroup$ @fgrieu Thanks for the concerns. Did you click on the link to my Github page where I clearly state "⚠️ THIS SDK IS NOT SAFE/PRODUCTION READY (YET!) ⚠️"? So yes I am aware :) Right now I am in a learning stage. $\endgroup$ – Sajjon Jul 23 '18 at 23:03
  • $\begingroup$ @jadb thanks, I will have a look! But Instead of linking to your repo, for me it would be incredibly helpful with litterature references to what is know to be "the fastest algorithm(s)" (maybe per curve group basis). If known...? $\endgroup$ – Sajjon Jul 23 '18 at 23:06
  • $\begingroup$ @fgrieu Also do you have any good reference to litterature about prevention of timing attacks. Is it known to have been done in high level languages? E.g. BouncyCastle is written in Java (not as high level as Swift, but almost ;) ) github.com/bcgit/bc-java $\endgroup$ – Sajjon Jul 23 '18 at 23:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.