Skip to content

Instantly share code, notes, and snippets.

@matthewdowney
Last active January 23, 2021 00:46
Show Gist options
  • Save matthewdowney/410ff9785c622f269f65e4b53e3984b5 to your computer and use it in GitHub Desktop.
Save matthewdowney/410ff9785c622f269f65e4b53e3984b5 to your computer and use it in GitHub Desktop.
Faster Clojure elliptic curve addition for affine points
(defn modular-multiplicative-inverse
"Find x in [0, p) such that (m * x) % p = n"
[n m p]
(let [n (biginteger n)
m (biginteger m)
p (biginteger p)]
(-> (.modInverse m p)
(.multiply n)
(.mod p))))
(defn ec-add
"Elliptic curve addition for two affine points on a curve over the finite
field `p`."
[pa pb p]
(let [^BigInteger ax (biginteger (first pa))
^BigInteger ay (biginteger (second pa))
^BigInteger bx (biginteger (first pb))
^BigInteger by (biginteger (second pb))
p (biginteger p)
;; bigint math
- (fn [^BigInteger x ^BigInteger y] (.subtract x y))
mod (fn [^BigInteger x ^BigInteger y] (.mod x y))
* (fn [^BigInteger x ^BigInteger y] (.multiply x y))]
(let [dx (- ax bx)
_ (assert (not (zero? (mod dx p))) "points have different x coords")
dy (- ay by)
m (modular-multiplicative-inverse dy dx p)
x (mod (- (- (* m m) ax) bx) p)
y (mod (- (* m (- ax x)) ay) p)]
[x y])))
(comment
;;; Example usage:
(def finite-field
3618502788666131213697322783095070105623107215331596699973092056135872020481)
;; Points are affine, i.e. [X, Y]
(def p0
[874739451078007766457464989774322083649278607533249481151382481072868806602
152666792071518830868575557812948353041420400780739481342941381225525861407])
(def p1
[996781205833008774514500082376783249102396023663454813447423147977397232763
1668503676786377725805489344771023921079126552019160156920634619255970485781])
(ec-add p0 p1 finite-field)
;=> [3051458946846273314002590462865941923368261374710240944211475840840846402306
; 2854707340018174591296508682018533417494313071474846329395042104358939271306]
(require 'criterium.core)
(criterium.core/bench (ec-add p0 p1 finite-field))
;Evaluation count : 4796040 in 60 samples of 79934 calls.
; Execution time mean : 12.551386 µs
; Execution time std-deviation : 110.624948 ns
; Execution time lower quantile : 12.479252 µs ( 2.5%)
; Execution time upper quantile : 12.798060 µs (97.5%)
; Overhead used : 6.370572 ns
)
(comment
;; Compare to e.g. bouncycastle (requires [org.bouncycastle/bcprov-jdk15on "1.68"])
(import '(org.bouncycastle.math.ec ECCurve$Fp))
(def curve
(ECCurve$Fp.
(biginteger finite-field)
(biginteger (first p0))
(biginteger (second p0))))
(let [point (.add
(.createPoint ^ECCurve$Fp curve (biginteger (first p0)) (biginteger (second p0)))
(.createPoint ^ECCurve$Fp curve (biginteger (first p1)) (biginteger (second p1))))]
[(-> point .normalize .getAffineXCoord .toBigInteger)
(-> point .normalize .getAffineYCoord .toBigInteger)])
;=> [3051458946846273314002590462865941923368261374710240944211475840840846402306
; 2854707340018174591296508682018533417494313071474846329395042104358939271306]
(criterium.core/bench
(let [point (.add
(.createPoint ^ECCurve$Fp curve (biginteger (first p0)) (biginteger (second p0)))
(.createPoint ^ECCurve$Fp curve (biginteger (first p1)) (biginteger (second p1))))]
[(-> point .normalize .getAffineXCoord .toBigInteger)
(-> point .normalize .getAffineYCoord .toBigInteger)]))
;Evaluation count : 2695440 in 60 samples of 44924 calls.
; Execution time mean : 22.341090 µs
; Execution time std-deviation : 72.378445 ns
; Execution time lower quantile : 22.258946 µs ( 2.5%)
; Execution time upper quantile : 22.561763 µs (97.5%)
; Overhead used : 6.370572 ns
;; It's worth noting that the .normalize call is the expensive part, since
;; addition with Jacobian as opposed to affine coordinates is much faster.
;; This implementation is only faster for operations on _affine_ coordinates.
(criterium.core/bench
(.add
(.createPoint ^ECCurve$Fp curve (biginteger (first p0)) (biginteger (second p0)))
(.createPoint ^ECCurve$Fp curve (biginteger (first p1)) (biginteger (second p1)))))
;Evaluation count : 16967520 in 60 samples of 282792 calls.
; Execution time mean : 3.672510 µs
; Execution time std-deviation : 194.895127 ns
; Execution time lower quantile : 3.531868 µs ( 2.5%)
; Execution time upper quantile : 4.183846 µs (97.5%)
; Overhead used : 6.370572 ns
)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment