secp256k1

gistfile1.txt

(ns secp256k1
  (:import (java.util Arrays)
           (java.security MessageDigest)
           (java.nio.charset StandardCharsets)))

(defrecord Point [^BigInteger x ^BigInteger y])

(def infinity (->Point nil nil))

(def ^BigInteger zero BigInteger/ZERO)
(def ^BigInteger one BigInteger/ONE)
(def ^BigInteger two BigInteger/TWO)
(def ^BigInteger three (BigInteger/valueOf 3))
(def ^BigInteger four (BigInteger/valueOf 4))
(def ^BigInteger seven (BigInteger/valueOf 7))

(def ^BigInteger p
  (biginteger 16rFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F))
(def ^BigInteger n
  (biginteger 16rFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141))
(def ^BigInteger e
  (.divide (.add p one) four))

(def G
  (->Point
    (biginteger 16r79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
    (biginteger 16r483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)))

(defn- infinite?
  [p]
  (or (nil? (:x p)) (nil? (:y p))))

(defn add
  [p1 p2]
  (let [^BigInteger x1 (:x p1)
        ^BigInteger y1 (:y p1)
        ^BigInteger x2 (:x p2)
        ^BigInteger y2 (:y p2)
        infinite-p1? (infinite? p1)
        infinite-p2? (infinite? p2)]
    (cond
      (and infinite-p1? infinite-p2?) infinity
      infinite-p1? p2
      infinite-p2? p1
      (and (= x1 x2) (not= y1 y2)) infinity
      :else
      (let [lam (if (and (= x1 x2) (= y1 y2))
                  (.mod
                    (.multiply (.multiply (.multiply three x1) x1)
                      (.modPow (.multiply y2 two) (.subtract p two) p))
                    p)
                  (.mod
                    (.multiply (.subtract y2 y1)
                      (.modPow (.subtract x2 x1) (.subtract p two) p))
                    p))
            x3 (.mod (.subtract (.subtract (.multiply lam lam) x1) x2) p)]
        (->Point x3 (.mod (.subtract (.multiply lam (.subtract x1 x3)) y1) p))))))

(defn mul
  [p ^BigInteger n]
  (loop [i 0 R infinity P p]
    (if (= i 256)
      R
      (recur
        (inc i)
        (if (pos? (.compareTo (.and (.shiftRight n i) one) zero))
          (add R P) R)
        (add P P)))))

(defn sha-256
  ^bytes [^bytes input]
  (let [digest (MessageDigest/getInstance "SHA-256")]
    (.digest digest input)))

(def ^bytes tag-hash
  (sha-256 (.getBytes "BIP0340/challenge" StandardCharsets/UTF_8)))

(defn- biginteger*
  ^BigInteger [^bytes b]
  (BigInteger. 1 b))

(defn- lift-x
  [^BigInteger x]
  (when (and (not (neg? (.signum x))) (neg? (.compareTo x p)))
    (let [^BigInteger c (.mod (.add (.modPow x three p) seven) p)
          ^BigInteger y (.modPow c e p)]
      (when (zero? (.compareTo c (.modPow y two p)))
        (->Point x (if (zero? (.signum (.and y one))) y (.subtract p y)))))))

(defn- ||
  ^bytes [& byte-arrays]
  (let [tuples (mapv vector
                 (concat byte-arrays [nil])
                 (reductions #(+ %1 (alength ^bytes %2)) 0 byte-arrays))
        rv (byte-array (second (peek tuples)))]
    (doseq [[arr offset] (butlast tuples)]
      (System/arraycopy arr 0 rv offset (alength ^bytes arr)))
    rv))

(defn verify
  ;; @see https://bips.xyz/340#verification
  [^bytes public-key ^bytes message ^bytes signature]
  (when (and
          (= 32 (alength ^bytes public-key) (alength ^bytes message))
          (= 64 (alength ^bytes signature)))
    (when-let [P (lift-x (biginteger* public-key))]
      (let [r-bytes (Arrays/copyOfRange signature 0 32)
            r (biginteger* r-bytes)
            s (biginteger* (Arrays/copyOfRange signature 32 64))]
        (when (and
                (< (.compareTo r p) 0)
                (< (.compareTo s n) 0))
          (let [e (.mod
                    (biginteger*
                      (sha-256
                        (|| tag-hash tag-hash r-bytes public-key message))) n)
                R (add (mul G s) (mul P (.subtract n e)))]
            (when
              (and
                (not= R infinity)
                (zero? (.compareTo (.mod ^BigInteger (:y R) two) zero))
                (zero? (.compareTo ^BigInteger (:x R) r)))
              true)))))))

;; example:
;; (verify
;;  (hex-decode "aff9a9f017f32b2e8b60754a4102db9d9cf9ff2b967804b50e070780aa45c9a8")
;;  (hex-decode "2a3a85a53e99af51eb6b3303fb4c902594827f4c9da0a183f743054a9e3d3a33")
;;  (hex-decode "0e049520f7683ab9ca1c3f50243e09c11ace8fcabb0e2fcdd80861b9802d83180ca0bed00f42a032ac780152a3b3a5c01c136a271a7d360379a1f29e13eceb9d"))