Last active
January 23, 2021 00:46
-
-
Save matthewdowney/410ff9785c622f269f65e4b53e3984b5 to your computer and use it in GitHub Desktop.
Faster Clojure elliptic curve addition for affine points
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(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