README
¶
Ekliptic
This package provides primitives for elliptic curve cryptographic operations on the secp256k1 curve, with zero dependencies and excellent performance. It provides both Affine and Jacobian interfaces for elliptic curve operations. Aims to facilitate performant low-level operations on secp256k1 without overengineering or kitchen-sink syndrome.
ALPHA STATE
This library is not finished, stable, or audited - depend on it at your own peril!
API Reference
Elliptic-whah?
Elliptic curve cryptography is a relatively new field of asymmetric public-key cryptography. An elliptic curve is just a cubic equation of a particular form. The secp256k1 curve, for example, is $y^{2}=x^3+7$. To make this curve equation useful, we first define an addition operation that 'adds' two $x,y$ points on the curve to produce a third point also on the curve. From that, you can create a multiplication operation to multiply a 2D point by some 1D (scalar) number, by simply adding the point to itself many times.
It just so happens that due to the particular properties of elliptic curves, if you multiply some publicly known point by a secret number, that operation is extremely hard to reverse, and you end up with another point that is mathematically related to the secret number. Functions that are easy to compute but hard to reverse are a fundamental building block of cryptography, and people started to realize you could use this feature of elliptic curve equations as a basis for new public-key cryptosystems, like RSA, but using much smaller numbers in a 2D space.
The unique one-way function of elliptic curve cryptography is base point multiplication over a finite field, (the 'finite field' part means all coordinate values are taken modulo some large prime number). A base point is a publicly known $(x, y)$ point, often called the generator point $G$, which all parties agree upon. The private key in this cryptosystem is a scalar number $k$ which is multiplied with the base point. The point resulting from base point multiplication $P$ becomes the public key. $P$ and $G$ are capitalized to denote that they are 2D points, while $k$ is a lone positive integer. Base point multiplication is written mathematically as
$$P = k G$$
Point multiplication is believed to be hard to undo: There's no way to quickly compute $k$ if you only know $P$ and $G$. The only known way to efficiently perform $P \div G$ would be to run Shor's Algorithm on a quantum computer that can operate with at least $6\cdot \log_2(k)$ qubits. This currently doesn't exist, so at least for now, elliptic curve cryptography provides a safe way to sign/verify and encrypt/decrypt information asymetrically.
Down Sides
Elliptic curve cryptography does have some down sides - Primarily, from the complexity involved in implementing it safely. To perform elliptic curve cryptography, someone needs to design an elliptic curve with its various parameters in a secure way, which requires highly adept and experienced cryptographers. This makes users vulnerable to malicious design by those with the specialized knowledge needed to produce such curves. Compared to a simpler system like RSA, where there are no 'magic numbers' involved, ECC predicates the safety of the system not only on the security of the algorithms and in-code implementations, but also on the ethical integrity of curve designers, who are far fewer, and more tightly centralized.
Thankfully, the secp256k1 curve was designed in a non-random 'nothing up my sleeve' fashion, which helps to reduce the risk that it was designed with a backdoor in mind. This is why it has become such a popular curve. Satoshi chose to use secp256k1 for Bitcoin for that same reason (among others).
Why not RSA?
Primarily, for performance. Elliptic curves offer a way to perform cryptography faster for the same degree of security.
A 256-bit elliptic curve key provides roughly the same degree of security as a 2048-bit RSA key. But for normal 'happy path' operations where you're not trying attack the cryptosystem, elliptic curve operations are vastly faster, simply due to the size of the numbers involved. It's easier to multiply $5 \cdot 9$ than to multiply $555 \cdot 999$.
Consider this simple benchmark which compares 256-bit ECC and 2048-bit RSA private and public key generation:
func BenchmarkGenerateKeys_Ekliptic(b *testing.B) {
var privateKey *big.Int
var publicKey struct{ x, y big.Int }
for i := 0; i < b.N; i++ {
privateKey, _ = ekliptic.RandomScalar(rand.Reader)
ekliptic.MultiplyBasePoint(privateKey, &publicKey.x, &publicKey.y)
}
}
func BenchmarkGenerateKeys_RSA(b *testing.B) {
for i := 0; i < b.N; i++ {
rsa.GenerateKey(rand.Reader, 2048)
}
}
goos: linux
goarch: amd64
pkg: t
cpu: Intel(R) Core(TM) i7-6500U CPU @ 2.50GHz
BenchmarkGenerateKeys_Ekliptic-4 1530 711021 ns/op 242393 B/op 2833 allocs/op
BenchmarkGenerateKeys_RSA-4 8 138256984 ns/op 1874108 B/op 5019 allocs/op
Golang's standard library crypto/rsa package takes between between 0.1 to 0.25 seconds to generate an RSA key pair of that size. Ekliptic takes less than a millisecond to generate an ECC key pair of equivalent security. For activities like web-browsing, ephemeral key pairs are constantly being generated to negotiate TLS-encrypted connections. The faster you can generate session keys and verify certificates, the faster you can open TLS connections, and the faster you can browse.
Examples
Find fully validated examples in examples_test.go.
Deriving a public key from a private key:
privateKey, _ := new(big.Int).SetString("c370af8c091812ef7f6bfaffb494b1046fb25486c9873243b80826daef3ec583", 16)
x, y := ekliptic.MultiplyBasePoint(privateKey)
fmt.Println("Public key:")
fmt.Printf(" x: %x\n", x)
fmt.Printf(" y: %x\n", y)
// output:
// Public key:
// x: 76cd66c6cca75278ff408ce67290537367719154ae2b96448327fe4033ddcfc7
// y: 35663ecbb64397bb9bd79155a1e6b138c2fb8fa1f11355f8e9e97ddd88a78e49
Deriving a Diffie-Hellman shared-secret:
alicePriv, _ := new(big.Int).SetString("94a22a406a6977c1a323f23b9d7678ad08e822834d1df8adece84e30f0c25b6b", 16)
bobPriv, _ := new(big.Int).SetString("55ba19100104cbd2842999826e99e478efe6883ac3f3a0c7571034321e0595cf", 16)
var alicePub, bobPub struct{ x, y *big.Int }
// derive public keys
alicePub.x, alicePub.y = ekliptic.MultiplyBasePoint(alicePriv)
bobPub.x, bobPub.y = ekliptic.MultiplyBasePoint(bobPriv)
// Alice gives Bob her public key, Bob derives the secret
bobSharedKey, _ := ekliptic.MultiplyAffine(alicePub.x, alicePub.y, bobPriv, nil)
// Bob gives Alice his public key, Alice derives the secret
aliceSharedKey, _ := ekliptic.MultiplyAffine(bobPub.x, bobPub.y, alicePriv, nil)
fmt.Printf("Alice's derived secret: %x\n", aliceSharedKey)
fmt.Printf("Bob's derived secret: %x\n", bobSharedKey)
// output:
// Alice's derived secret: 375a5d26649704863562930ded2193a0569f90f4eb4e63f0fee72c4c05268feb
// Bob's derived secret: 375a5d26649704863562930ded2193a0569f90f4eb4e63f0fee72c4c05268feb
Signing and verifying a message with ECDSA.
import (
cryptorand "crypto/rand"
mathrand "math/rand"
"github.com/kklash/ekliptic"
)
randReader := mathrand.New(mathrand.NewSource(1))
key, _ := ekliptic.RandomScalar(randReader)
// This could also come from RFC6979 (github.com/kklash/rfc6979)
nonce, _ := cryptorand.Int(randReader, ekliptic.Secp256k1_CurveOrder)
hashedMessage := sha256.Sum256([]byte("i love you"))
hashedMessageInt := new(big.Int).SetBytes(hashedMessage[:])
r, s := ekliptic.SignECDSA(key, nonce, hashedMessageInt)
fmt.Printf("r: %x\n", r)
fmt.Printf("s: %x\n", s)
var pub struct{ x, y *big.Int }
pub.x, pub.y = ekliptic.MultiplyBasePoint(key)
valid := ekliptic.VerifyECDSA(hashedMessageInt, r, s, pub.x, pub.y)
fmt.Printf("valid: %v\n", valid)
// output:
//
// r: 4a821d5ec008712983929de448b8afb6c24e5a1b97367b9a65b6220d7f083fe3
// s: 381d053be61243d950865d7b8eb6b5ba48fbabfe7fda81af3183a184a02f5d51
// valid: true
Uncompressing a public key.
compressedKey, _ := hex.DecodeString("030000000000000000000000000000000000000000000000000000000000000001")
publicKeyX := new(big.Int).SetBytes(compressedKey[1:])
evenY, oddY := ekliptic.Weierstrass(publicKeyX)
var publicKeyY *big.Int
if compressedKey[0]%2 == 0 {
publicKeyY = evenY
} else {
publicKeyY = oddY
}
fmt.Println("uncompressed key:")
fmt.Printf("x: %.64x\n", publicKeyX)
fmt.Printf("y: %.64x\n", publicKeyY)
// output:
// uncompressed key:
// x: 0000000000000000000000000000000000000000000000000000000000000001
// y: bde70df51939b94c9c24979fa7dd04ebd9b3572da7802290438af2a681895441
Ekliptic exports a struct type Curve, which satisfies the elliptic.Curve interface. You can use this in other libraries anywhere elliptic.Curve is accepted. For instance, to sign and verify data with crypto/ecdsa:
d, _ := new(big.Int).SetString("18e14a7b6a307f426a94f8114701e7c8e774e7f9a47e2c2035db29a206321725", 16)
pubX, pubY := ekliptic.MultiplyBasePoint(d)
key := &ecdsa.PrivateKey{
D: d,
PublicKey: ecdsa.PublicKey{
Curve: new(ekliptic.Curve),
X: pubX,
Y: pubY,
},
}
hashedMessage := sha256.Sum256([]byte("i love you"))
r, s, err := ecdsa.Sign(rand.Reader, key, hashedMessage[:])
if err != nil {
panic("failed to compute signature: " + err.Error())
}
if ecdsa.Verify(&key.PublicKey, hashedMessage[:], r, s) {
fmt.Println("verified ECDSA signature using crypto/ecdsa")
}
// output:
// verified ECDSA signature using crypto/ecdsa
Blinding a hidden value for multi-party computation:
// Alice: input parameters
s, _ := new(big.Int).SetString("2fc9374cad648e33f78dd294578dd960281e05744b27faa1ffe1e7175bd6901d", 16)
aX, _ := new(big.Int).SetString("8bf20851cc16007dbf3df0c109dc016b360ca0f729f368ea38c385ceeffaf3cf", 16)
aY, _ := new(big.Int).SetString("a0c7bd73154c02cc5e002c3a4f876158a4276c185ef859df589675a92c745e3a", 16)
// Bob: input parameters
r, _ := new(big.Int).SetString("825e7984ae7843f9c13371d9a54143a465b1e2d278e67de1ca713127e40a52f1", 16)
// Alice: blind the input with secret s send the result B to Bob.
// B = s * A
bX, bY := ekliptic.MultiplyAffine(aX, aY, s, nil)
// Bob: receive A, blind it again with secret r and return result C to Alice.
// C = r * B = r * s * G
cX, cY := ekliptic.MultiplyAffine(bX, bY, r, nil)
// Alice: unblind C with the inverse of s:
// s⁻¹ * C = s⁻¹ * r * s * G = r * G
sInv := ekliptic.InvertScalar(s)
mX, mY := ekliptic.MultiplyAffine(cX, cY, sInv, nil)
expectedX, expectedY := ekliptic.MultiplyAffine(aX, aY, r, nil)
if !ekliptic.EqualAffine(mX, mY, expectedX, expectedY) {
fmt.Println("did not find expected unblinded point")
return
}
fmt.Println("found correct unblinded point q * h * G")
// output:
// found correct unblinded point q * h * G
Hacking on Ekliptic
| Command | Usage |
|---|---|
go test |
Run unit tests. |
go test -bench=. |
Run benchmarks. |
go test -bench=. -benchmem |
Run benchmarks with memory profile. |
go generate |
Regenerate precomputed base point products. |
Test Vectors
Test vectors stored in test_vectors can be verified using third-party libraries to double check that this library is working correctly.
| Validates against | Command to run |
|---|---|
paritytech/libsecp256k1 (Rust) |
cargo run --manifest-path ./test_vectors/validate_rs/{Cargo.toml,} |
cslashm/ECPy (Python) |
pip3 install --user ECPy && python3 test_vectors/validate.py |
Performance Optimizations
Memory
All methods use and accept golang-native big.Int structs for math operations. big.Int structs can be re-used when the values they hold are no longer required. This is why you'll see patterns like this if you read Ekliptic's code:
e := a.Mul(a, three)
a = nil
In the above example, a is no longer needed, so we reclaim its memory as a new variable to avoid allocating an entirely new big.Int struct for e.
Jacobian Points
This library offers support for both affine and Jacobian point math. Affine coordinates are 'normal' two-dimensional coordinates, $x$ and $y$, which unambiguously describes a point on the plane. Jacobian coordinates are a three-dimensional representation of an affine point, $x_a,y_a$, in terms of three variables: $x_j,y_j,z$ such that:
$$x_a = \frac{x_j}{z^2}$$
$$y_a = \frac{y_j}{z^3}$$
This relationship means there are an absurdly large number of possible Jacobian coordinate triplets which describe the same affine point. Each affine coordinate is basically converted into a ratio of $x:z$ and $y:z$, thus proportional ratios simplify to the same affine point.
Why would we want to represent points this way? Elliptic curve multiplication - a critical primitive for almost any elliptic-curve cryptography - involves performing many addition operations in a row. That's what multiplication means, after all. When you add two affine $(x, y)$ points together in an elliptic curve, you have to perform some finite field division, AKA modular inversion, to get a result back in affine form. Modular inversion is a very expensive operation compared to multiplication. Instead of dividing after every addition operation, you can defer the division until the end of the multiplication sequence, by accumulating in the divisor coordinate $z$. After the multiplication operation is done, the point can be converted back to affine, or used for new EC operations, as needed.
To demonstrate, notice how expensive a naive affine multiplication is compared to a Jacobian multiplication:
BenchmarkMultiplyJacobi-6 675 1757329 ns/op 727070 B/op 5060 allocs/op
BenchmarkMultiplyAffine-6 679 1782691 ns/op 728819 B/op 5084 allocs/op
BenchmarkMultiplyAffineNaive-6 442 2480711 ns/op 545915 B/op 9147 allocs/op
ekliptic.MultiplyJacobi and ekliptic.MultiplyAffine both use Jacobian math for multiplication operations under the hood. ekliptic.MultiplyAffineNaive is a naive implementation which uses affine addition and doubling instead of Jacobian math. It should be used for demonstrative purposes only.
Precomputation
You can improve point multiplication performance significantly by precomputing a table of products of a point $P$ which you plan to multiply frequently. Precomputation means calculating $2^{4i}jP$ for $0 <= i <= 63$ and $0 <= j <= 15$. This table is indexable by $i$ and $j$. When using a precomputed table with a multiplication, ekliptic uses the windowed method. This speeds up multiplication of a fixed point often by a factor of 5x-10x, and saves a lot of memory allocations.
BenchmarkMultiplyJacobi-6 241 4859994 ns/op 1229138 B/op 9382 allocs/op
BenchmarkMultiplyJacobi_Precomputed-6 2578 590604 ns/op 144339 B/op 1372 allocs/op
The secp256k1 base point $G$ is multiplied very frequently, so ekliptic ships with a precomputed table for $G$ ready to go. This table is used to speed up ekliptic.MultiplyBasePoint. The source code file containing the table is auto-generated, triggered by go generate.
Precomputed tables for custom points can be constructed using ekliptic.NewPrecomputedTable function.
Other Performance Notes
- We have a special implementation which checks for Jacobi point validity without costly affine conversion.
- Golang's
big.Inthas some operations which are more costly than others. For example, doingn.Exp(n, two, P)is more costly than doingn.Mul(n, n); modCoordinate(n). This holds for squaring and cubing, but exponents beyond 3 require.Expfor the best performance.
Thanks!
I wrote this library as a learning exercise. Thanks a ton to the following people and their amazing guides, with which I followed along and learned from.
Many test vectors in this package were either duplicated from, generated by, or derived from other Elliptic Curve Crypto implementations:
paulmillr/noble-secp256k1btcsuite/btcec(note: they use a different algorithm to add jacobians, but it works out to the same affine coordinates at the end. I modified a few of their test fixtures' jacobian ratios.)
Donations
If you're interested in supporting development of this package, show your love by dropping me some Bitcoins!
bc1qhct3hwt5pjmu75d2fldwd477vhwmthuqvmh03s
Documentation
¶
Overview ¶
Package ekliptic provides primitives for cryptographic operations on the secp256k1 curve, with zero dependencies and excellent performance. It provides both Affine and Jacobian interfaces for elliptic curve operations. Aims to facilitate performant low-level operations on secp256k1 without overengineering or kitchen-sink syndrome.
Index ¶
- Variables
- func AddAffine(x1, y1 *big.Int, x2, y2 *big.Int) (x3, y3 *big.Int)
- func AddJacobi(x1, y1, z1 *big.Int, x2, y2, z2 *big.Int) (x3, y3, z3 *big.Int)
- func DoubleAffine(x1, y1 *big.Int) (x3, y3 *big.Int)
- func DoubleJacobi(x1, y1, z1 *big.Int) (x3, y3, z3 *big.Int)
- func EqualAffine(x1, y1 *big.Int, x2, y2 *big.Int) bool
- func EqualJacobi(x1, y1, z1 *big.Int, x2, y2, z2 *big.Int) bool
- func InvertScalar(d *big.Int) *big.Int
- func IsOnCurveAffine(x, y *big.Int) bool
- func IsOnCurveJacobi(x, y, z *big.Int) bool
- func IsValidScalar(d *big.Int) bool
- func MultiplyAffine(x1, y1 *big.Int, k *big.Int, precomputedTable PrecomputedTable) (x2, y2 *big.Int)
- func MultiplyAffineNaive(x1, y1 *big.Int, k *big.Int) (x2, y2 *big.Int)
- func MultiplyBasePoint(k *big.Int) (x, y *big.Int)
- func MultiplyJacobi(x1, y1, z1 *big.Int, k *big.Int, precomputedTable PrecomputedTable) (x2, y2, z2 *big.Int)
- func Negate(y *big.Int) *big.Int
- func RandomScalar(random io.Reader) (*big.Int, error)
- func SignECDSA(d, k, z *big.Int) (r, s *big.Int)
- func SubAffine(x1, y1 *big.Int, x2, y2 *big.Int) (x3, y3 *big.Int)
- func SubJacobi(x1, y1, z1 *big.Int, x2, y2, z2 *big.Int) (x3, y3, z3 *big.Int)
- func ToAffine(x, y, z *big.Int)
- func VerifyECDSA(z *big.Int, r, s *big.Int, pubX, pubY *big.Int) bool
- func Weierstrass(x *big.Int) (evenY, oddY *big.Int)
- type Curve
- func (_ *Curve) Add(x1, y1, x2, y2 *big.Int) (x3, y3 *big.Int)
- func (_ *Curve) Double(x1, y1 *big.Int) (x3, y3 *big.Int)
- func (_ *Curve) IsOnCurve(x, y *big.Int) bool
- func (c *Curve) Params() *elliptic.CurveParams
- func (_ *Curve) ScalarBaseMult(k []byte) (x2, y2 *big.Int)
- func (_ *Curve) ScalarMult(x1, y1 *big.Int, k []byte) (x2, y2 *big.Int)
- type PrecomputedTable
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ( // The parameters of the secp256k1 elliptic curve. Secp256k1_B = seven Secp256k1_P = hexint("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F") Secp256k1_CurveOrder = hexint("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141") // Secp256k1_GeneratorX and Secp256k1_GeneratorY describe the secp256k1 // generator point, used for deriving public keys from private keys. Secp256k1_GeneratorX = hexint("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798") Secp256k1_GeneratorY = hexint("483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8") // Secp256k1_CurveOrderHalf is half of Secp256k1_CurveOrder (rounded down). Secp256k1_CurveOrderHalf = new(big.Int).Rsh(Secp256k1_CurveOrder, 1) )
Functions ¶
func AddAffine ¶
AddAffine adds two affine points on the secp256k1 curve:
P1 + P2 = P3 (x1, y1) + (x2, y2) = (x3, y3)
It returns the resulting affine point (x3, y3).
We incorporate the standard affine addition and doubling formulas:
if P1 == P2: m = (3 * x1² + a) / (2 * y1) else: m = (y2 - y1) / (x2 - x1) x3 = m² - x1 - x2 y3 = m * (x1 - x3) - y1
This function does not check point validity - it assumes you are passing valid points on the secp256k1 curve.
func AddJacobi ¶
AddJacobi adds two Jacobian coordinate points on the secp256k1 curve:
P1 + P2 = P3 (x1, y1, z1) + (x2, y2, z2) = (x3, y3, z3)
It returns the resulting Jacobian point (x3, y3, z3).
We use the "add-1998-cmo-2" addition formulas.
https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-add-1998-cmo-2
Z1Z1 = Z1² Z2Z2 = Z2² U1 = X1*Z2Z2 U2 = X2*Z1Z1 S1 = Y1*Z2*Z2Z2 S2 = Y2*Z1*Z1Z1 H = U2-U1 HH = H² HHH = H*HH r = S2-S1 V = U1*HH X3 = r²-HHH-2*V Y3 = r*(V-X3)-S1*HHH Z3 = Z1*Z2*H
This function does not check point validity - it assumes you are passing valid points on the secp256k1 curve.
func DoubleAffine ¶
m = (3*x1²+a) / (2*y1) x3 = m² - x1 - x2 y3 = m(x1-x3) - y1
func DoubleJacobi ¶
DoubleJacobi doubles a Jacobian coordinate point on the secp256k1 curve, using the "dbl-2009-l" doubling formulas.
http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-dbl-2009-l
A = X1² B = Y1² C = B² D = 2*((X1+B)²-A-C) E = 3*A F = E² X3 = F-2*D Y3 = E*(D-X3)-8*C Z3 = 2*Y1*Z1
func EqualAffine ¶
EqualAffine tests the equality of two affine points.
func EqualJacobi ¶
EqualJacobi tests whether two Jacobian points are equivalent to the same affine point, without the performance penalty of actually converting both points to affine format. It returns true if:
x2 * z1² == x1 * z2² y2 * z1³ == y1 * z2³
Affine coordinates are calculated as:
Ax1 = x1 / z1² Ax2 = x2 / z2² Ay1 = y1 / z1³ Ay2 = y2 / z2³
Thus, we can re-arrange operations to avoid costly division, and determine if the x-coordinate matches:
Ax1 = Ax2 x2 / z2² = x1 / z1² (x2 * z1²) / z2² = x1 x2 * z1² = x1 * z2²
Same for the y-coordinate:
Ay1 = Ay2 (y2 * z1³) / z2³ = y1 y2 * z1³ = y1 * z2³
This approach provides a 5x speedup compared to affine conversion.
func InvertScalar ¶
InvertScalar returns d⁻¹: the multiplicative inverse of the given scalar value d, modulo the curve order N:
d * d⁻¹ = 1 mod N
Multiplying any point A by both d and d⁻¹ will return the same point A:
d * A * d⁻¹ = A
Example ¶
InvertScalar is useful for reversibly blinding a value you don't want to reveal. Alice can blind any point A with some random scalar s to produce a blinded point B:
B = s * A
B can then be blinded by another party Bob, with their own secret r:
C = r * B
Alice can then unblind C by inverting their secret s:
M = s⁻¹ * C M = s⁻¹ * (r * s * A) M = r * A
Alice now knows r * A without knowing r, having revealed neither A nor the final result M to Bob.
package main
import (
"fmt"
"math/big"
"github.com/kklash/ekliptic"
)
func main() {
// Alice: input parameters
s, _ := new(big.Int).SetString("2fc9374cad648e33f78dd294578dd960281e05744b27faa1ffe1e7175bd6901d", 16)
aX, _ := new(big.Int).SetString("8bf20851cc16007dbf3df0c109dc016b360ca0f729f368ea38c385ceeffaf3cf", 16)
aY, _ := new(big.Int).SetString("a0c7bd73154c02cc5e002c3a4f876158a4276c185ef859df589675a92c745e3a", 16)
// Bob: input parameters
r, _ := new(big.Int).SetString("825e7984ae7843f9c13371d9a54143a465b1e2d278e67de1ca713127e40a52f1", 16)
// Alice: blind the input with secret s send the result B to Bob.
// B = s * A
bX, bY := ekliptic.MultiplyAffine(aX, aY, s, nil)
// Bob: receive A, blind it again with secret r and return result C to Alice.
// C = r * B = r * s * G
cX, cY := ekliptic.MultiplyAffine(bX, bY, r, nil)
// Alice: unblind C with the inverse of s:
// s⁻¹ * C = s⁻¹ * r * s * G = r * G
sInv := ekliptic.InvertScalar(s)
mX, mY := ekliptic.MultiplyAffine(cX, cY, sInv, nil)
expectedX, expectedY := ekliptic.MultiplyAffine(aX, aY, r, nil)
if !ekliptic.EqualAffine(mX, mY, expectedX, expectedY) {
fmt.Println("did not find expected unblinded point")
return
}
fmt.Println("found correct unblinded point q * h * G")
}
Output: found correct unblinded point q * h * G
func IsOnCurveAffine ¶
IsOnCurveAffine determines if the affine point at (x, y) is a valid point on the secp256k1 curve. It checks for equality using the Weierstrass curve equation:
y² = x³ + ax + b
func IsOnCurveJacobi ¶
IsOnCurveJacobi determines if the jacobian point at (x, y, z) is a valid point on the secp256k1 curve. If z is nil, it is assumed to be 1, meaning x and y are affine coordinates. It uses the Weierstrass curve equation to determine whether the given point is valid:
y² = x³ + ax + b
Since a = 0 in secp256k1, we can simplify this to
y² = x³ + b
When using Jacobian coordinates, x and y are expressed as ratios with respect to z:
x = x / z² y = y / z³
Substituting and simplifying, we arrive at a much cleaner equation we can easily solve:
(y/z³)² = (x/z²)³ + b y²/z⁶ = x³/z⁶ + b y² = x³ + z⁶b
This approach is 2.5x more performant than converting a Jacobian point to affine coordinates first, because it does not require modular inversion to arrive at a result.
func IsValidScalar ¶
IsValidScalar returns true if the given integer is a valid secp256k1 scalar (private key), i.e. a number in the range [1, N-1] where N is the secp256k1 curve order.
func MultiplyAffine ¶
func MultiplyAffine( x1, y1 *big.Int, k *big.Int, precomputedTable PrecomputedTable, ) (x2, y2 *big.Int)
MultiplyAffine multiplies the given affine point (x1, y1) by the scalar value k in constant time.
If a PrecomputedTable is passed, MultiplyAffine will use the windowed multiplication method for fast computation. Otherwise, it will use the Montgomery Ladder algorithm.
It returns the resulting affine point (x2, y2).
Callers can construct and pass a PrecomputedTable which massively boosts performance of a MultiplyAffine call, at the cost of a larger up-front computational investment to build the precomputations. If a you plan to multiply the same point several times, precomputing is definitely worthwhile.
MultiplyAffine uses MultiplyJacobi under the hood, as it is about 30% faster than performing affine addition.
Example ¶
Construct an ECDH shared secret.
package main
import (
"fmt"
"math/big"
"github.com/kklash/ekliptic"
)
func main() {
alicePriv, _ := new(big.Int).SetString("94a22a406a6977c1a323f23b9d7678ad08e822834d1df8adece84e30f0c25b6b", 16)
bobPriv, _ := new(big.Int).SetString("55ba19100104cbd2842999826e99e478efe6883ac3f3a0c7571034321e0595cf", 16)
var alicePub, bobPub struct{ x, y *big.Int }
// derive public keys
alicePub.x, alicePub.y = ekliptic.MultiplyBasePoint(alicePriv)
bobPub.x, bobPub.y = ekliptic.MultiplyBasePoint(bobPriv)
// Alice gives Bob her public key, Bob derives the secret
bobSharedKey, _ := ekliptic.MultiplyAffine(alicePub.x, alicePub.y, bobPriv, nil)
// Bob gives Alice his public key, Alice derives the secret
aliceSharedKey, _ := ekliptic.MultiplyAffine(bobPub.x, bobPub.y, alicePriv, nil)
fmt.Printf("Alice's derived secret: %x\n", aliceSharedKey)
fmt.Printf("Bob's derived secret: %x\n", bobSharedKey)
}
Output: Alice's derived secret: 375a5d26649704863562930ded2193a0569f90f4eb4e63f0fee72c4c05268feb Bob's derived secret: 375a5d26649704863562930ded2193a0569f90f4eb4e63f0fee72c4c05268feb
func MultiplyAffineNaive ¶
MultiplyAffineNaive multiplies the given affine point by the scalar value k, using the Montgomery Ladder algorithm in constant-time.
This naive implementation uses affine doubling and addition under the hood, which is not desirable. It is made available only as a demonstration of how much faster Jacobian math is for elliptic curve multiplication operations. You should be using MultiplyAffine instead.
func MultiplyBasePoint ¶
MultiplyBasePoint multiplies the secp256k1 generator base point by the given integer k, and returns the resulting affine point (x, y). This uses a precomputed table for the secp256k1 base point to speed up multiplications.
This function is used to derive the public key for a private key k, among other uses.
Example ¶
Generate a public key from a private key.
package main
import (
"fmt"
"math/big"
"github.com/kklash/ekliptic"
)
func main() {
privateKey, _ := new(big.Int).SetString("c370af8c091812ef7f6bfaffb494b1046fb25486c9873243b80826daef3ec583", 16)
x, y := ekliptic.MultiplyBasePoint(privateKey)
fmt.Println("Public key:")
fmt.Printf(" x: %x\n", x)
fmt.Printf(" y: %x\n", y)
}
Output: Public key: x: 76cd66c6cca75278ff408ce67290537367719154ae2b96448327fe4033ddcfc7 y: 35663ecbb64397bb9bd79155a1e6b138c2fb8fa1f11355f8e9e97ddd88a78e49
func MultiplyJacobi ¶
func MultiplyJacobi( x1, y1, z1 *big.Int, k *big.Int, precomputedTable PrecomputedTable, ) (x2, y2, z2 *big.Int)
MultiplyJacobi multiplies the given Jacobian point (x1, y1, z1) by the scalar value k in constant time.
It returns the resulting Jacobian point (x2, y2, z2).
Callers can construct and pass a PrecomputedTable which massively boosts performance of a MultiplyJacobi call, at the cost of a larger up-front computational investment to build the precomputations. If a you plan to multiply the same point several times, precomputing is definitely worthwhile.
If a PrecomputedTable is passed, MultiplyJacobi will use the windowed multiplication method for fast computation. Otherwise, it will use the Montgomery Ladder algorithm.
MultiplyJacobi checks and panics if the given point you are multiplying is not actually on the secp256k1 curve, as this could leak private data about the scalar value k.
func Negate ¶
Negate returns the additive inverse of the given Y-coordinate modulo the curve prime modulus P. This can be used to negate a point, because:
(x, y) + (x, -y) = 0
y is expected to be within range [0, P-1].
func RandomScalar ¶
RandomScalar securely generates a random scalar value from the given source of randomness. Ensures the distribution of possible scalars is uniformly distributed from [1..N-1].
Use this function to generate private keys.
func SignECDSA ¶
SignECDSA signs a message hash z using the private key d, and a random (or deterministically derived) nonce k. It returns the resulting signature parts r and s.
Both the nonce k and the private key d should be generated with equal probability distribution over the range [1, Secp256k1_CurveOrder). SignECDSA panics if k or d is not within this range.
Example ¶
Sign a message digest.
package main
import (
cryptorand "crypto/rand"
"crypto/sha256"
"fmt"
"math/big"
mathrand "math/rand"
"github.com/kklash/ekliptic"
)
func main() {
randReader := mathrand.New(mathrand.NewSource(1))
key, _ := ekliptic.RandomScalar(randReader)
// This could also come from RFC6979 (github.com/kklash/rfc6979)
nonce, _ := cryptorand.Int(randReader, ekliptic.Secp256k1_CurveOrder)
hashedMessage := sha256.Sum256([]byte("i love you"))
hashedMessageInt := new(big.Int).SetBytes(hashedMessage[:])
r, s := ekliptic.SignECDSA(key, nonce, hashedMessageInt)
fmt.Printf("r: %x\n", r)
fmt.Printf("s: %x\n", s)
var pub struct{ x, y *big.Int }
pub.x, pub.y = ekliptic.MultiplyBasePoint(key)
valid := ekliptic.VerifyECDSA(hashedMessageInt, r, s, pub.x, pub.y)
fmt.Printf("valid: %v\n", valid)
}
Output: r: 4a821d5ec008712983929de448b8afb6c24e5a1b97367b9a65b6220d7f083fe3 s: 381d053be61243d950865d7b8eb6b5ba48fbabfe7fda81af3183a184a02f5d51 valid: true
func SubAffine ¶
SubAffine subtracts two affine points on the secp256k1 curve:
P1 - P2 = P3 (x1, y1) - (x2, y2) = (x3, y3)
It returns the resulting affine point (x3, y3).
This function does not check point validity - it assumes you are passing valid points on the secp256k1 curve.
func SubJacobi ¶
SubJacobi subtracts two Jacobian coordinate points on the secp256k1 curve:
P1 - P2 = P3 (x1, y1, z1) - (x2, y2, z2) = (x3, y3, z3)
It returns the resulting Jacobian point (x3, y3, z3).
This function does not check point validity - it assumes you are passing valid points on the secp256k1 curve.
func ToAffine ¶
Jacobian coordinates are a three-dimensional representation of a 2d (affine) point, (Ax, Ay), in terms of three variables: (x, y, z) such that:
Ax = x / z² Ay = y / z³
ToAffine converts the given jacobian coordinates to affine coordinates, normalizing x and y, and setting z = 1. This is an expensive operation, as it involves modular inversion of z to perform finite field division.
func VerifyECDSA ¶
VerifyECDSA returns true if the given signature (r, s) is a valid signature on message hash z from the given public key (pubX, pubY). Note that non-canonical ECDSA signatures (where s > N/2) are acceptable.
func Weierstrass ¶
Weierstrass solves the Weierstrass form elliptic curve equation for y, given an affine value of x:
y² = x³ + ax + b mod P
...where a = 0, b = 7 and P is Secp256k1_P - the secp256k1 curve constants.
It returns the two possible values of y: an even value and an odd value. You could also call this function "GetYValues(x)". This is useful for uncompressing public keys, which in secp256k1 often supply only the-x coordinate, and maybe a specifier indicating whether the y-coordinate is even or odd.
Returns two nil values if x is not a valid coordinate on the secp256k1 curve. Returns two zero values if x is zero.
Example ¶
Find possible Y-coordinates for an X. Used to uncompress a public key, where you may only have the full X-coordinate of the public key.
package main
import (
"encoding/hex"
"fmt"
"math/big"
"github.com/kklash/ekliptic"
)
func main() {
compressedKey, _ := hex.DecodeString("030000000000000000000000000000000000000000000000000000000000000001")
publicKeyX := new(big.Int).SetBytes(compressedKey[1:])
evenY, oddY := ekliptic.Weierstrass(publicKeyX)
var publicKeyY *big.Int
if compressedKey[0]%2 == 0 {
publicKeyY = evenY
} else {
publicKeyY = oddY
}
fmt.Println("uncompressed key:")
fmt.Printf("x: %.64x\n", publicKeyX)
fmt.Printf("y: %.64x\n", publicKeyY)
}
Output: uncompressed key: x: 0000000000000000000000000000000000000000000000000000000000000001 y: bde70df51939b94c9c24979fa7dd04ebd9b3572da7802290438af2a681895441
Types ¶
type Curve ¶
type Curve struct {
// contains filtered or unexported fields
}
Curve satisfies crypto/elliptic.Curve using the secp256k1 curve paramters.
Example ¶
package main
import (
"crypto/ecdsa"
"crypto/rand"
"crypto/sha256"
"fmt"
"math/big"
"github.com/kklash/ekliptic"
)
func main() {
d, _ := new(big.Int).SetString("18e14a7b6a307f426a94f8114701e7c8e774e7f9a47e2c2035db29a206321725", 16)
pubX, pubY := ekliptic.MultiplyBasePoint(d)
key := &ecdsa.PrivateKey{
D: d,
PublicKey: ecdsa.PublicKey{
Curve: new(ekliptic.Curve),
X: pubX,
Y: pubY,
},
}
hashedMessage := sha256.Sum256([]byte("i love you"))
r, s, err := ecdsa.Sign(rand.Reader, key, hashedMessage[:])
if err != nil {
panic("failed to compute signature: " + err.Error())
}
if ecdsa.Verify(&key.PublicKey, hashedMessage[:], r, s) {
fmt.Println("verified ECDSA signature using crypto/ecdsa")
}
}
Output: verified ECDSA signature using crypto/ecdsa
func (*Curve) IsOnCurve ¶
IsOnCurve reports whether the given (x,y) lies on the curve. Satisfies elliptic.Curve. Note: The elliptic.Curve interface requires that infinity is NOT on the curve.
func (*Curve) Params ¶
func (c *Curve) Params() *elliptic.CurveParams
Params returns the parameters for the curve. Satisfies elliptic.Curve.
func (*Curve) ScalarBaseMult ¶
ScalarBaseMult returns k*G, where G is the base point of the group and k is an integer in big-endian form. Satisfies elliptic.Curve.
type PrecomputedTable ¶
PrecomputedTable is a table in the form of a 2d slice, holding precomputed multiplications of a point P. Each entry in the table is the product of P and some multiple of a power of 2.
The table is laid out like this:
0 1 2 3 4 ... 15 ----------------------- 2^0 |* * * * * ... * 2^4 |* * * * * ... * 2^8 |* * * * * ... * 2^16 |* * * * * ... * ... |* * * * * ... * 2^252|* * * * * ... *
Each row i of the table holds the multiplications of the point, doubled 4i times. i should be less than 64.
Each column j of the table holds the doublings of the point, multiplied j times. j should be less than 16.
Indexing the table like so:
table[i][j]
...Looks up the following precomputed point multiplication:
2^(4i) * j * P
func NewPrecomputedTable ¶
func NewPrecomputedTable(x, y *big.Int) PrecomputedTable
NewPrecomputedTable computes a PrecomputedTable used for speeding up multiplications of a fixed affine point (x, y).
Source Files
¶
Directories
¶
| Path | Synopsis |
|---|---|
|
genprecompute precomputes a base-point table for the secp256k1 generator point, and writes it as generated code to a given output file.
|
genprecompute precomputes a base-point table for the secp256k1 generator point, and writes it as generated code to a given output file. |