ECDSA by Golang

ecdsa.go

package main

import (
    "fmt"
    "math"
    "math/big"
    mrand "math/rand"
    "crypto/rand"
)

var (
    ZERO = big.NewInt(0)
    ONE = big.NewInt(1)
    TWO = big.NewInt(2)
    THREE = big.NewInt(3)

    O = Point{ZERO, ONE, true}
)

type Point struct {
    x *big.Int
    y *big.Int
    isUnit bool
}

type EllipticCurve struct {
    A *big.Int
    B *big.Int
    modulus *big.Int
}

func (p Point) Xy() (*big.Int, *big.Int){
    return p.x, p.y
}

func make_divlist(n *big.Int) []int {
    div := []int{}
    for ; n.Cmp(ONE) != 0; {
        t := 0
        if r := new(big.Int).Mod(n, TWO); r.Cmp(ONE) == 0 {
            n.Sub(n, ONE)
            div = append(div, 0)
        }
        for ;; {
            if r := new(big.Int).Mod(n, TWO); r.Cmp(ONE) == 0 {
                break
            }
            n.Div(n, TWO)
            t = t + 1
        }
        div = append(div, t)
    }
    return div
}

func Str2Int(str string, base int) *big.Int {
    n, ok := new(big.Int).SetString(str, base)
    if !ok {
        panic("UWAAAAAAAAAAA")
    }
    return n
}

func bool2int(b bool) int {
    if b {
        return 1
    } else {
        return 0
    }
}

func Point2Str(p Point) string {
    str := fmt.Sprintf("(%d, %d; %d)", p.x, p.y, bool2int(!p.isUnit))
    return str
}


func add(a, b, modulus *big.Int) *big.Int {
    r := new(big.Int).Add(a, b)
    r.Mod(r, modulus)
    return r
}
func mul(a, b, modulus *big.Int) *big.Int {
    r := new(big.Int).Mul(a, b)
    r.Mod(r, modulus)
    return r
}
func sub(a, b, modulus *big.Int) *big.Int {
    r := new(big.Int).Sub(a, b)
    r.Mod(r, modulus)
    return r
}
func expMod(a, b, modulus *big.Int) *big.Int {
    r := new(big.Int).Exp(a, b, modulus)
    return r
}
func invmod(a, n *big.Int) *big.Int {
    r := new(big.Int).ModInverse(a, n)
    return r
}

func (ec EllipticCurve) PrintCurve() {
    fmt.Printf("[+] EC: y^2 = x^3 + %dx + %d  OVER Zmod(%d)\n",
        ec.A, ec.B, ec.modulus)
}

func (ec EllipticCurve) IsExist(P Point) bool {
    l := expMod(P.y, TWO, ec.modulus)
    r1 := expMod(P.x, THREE, ec.modulus)
    r2 := mul(ec.A, P.x, ec.modulus)
    r := add(add(r1, r2, ec.modulus), ec.B, ec.modulus)
    return l.Cmp(r) == 0
}

func cmpPoint(P, Q Point) bool {
    return (P.x.Cmp(Q.x) == 0) && (P.y.Cmp(Q.y) == 0)
}

func (ec EllipticCurve) PointAdd(P, Q Point) Point {
    if cmpPoint(P, Q) {
        return ec.PointDoubling(P)
    }
    if P.x.Cmp(Q.x) == 0 {
        return O
    }
    if P.isUnit {
        return Q
    }
    if Q.isUnit {
        return P
    }

    lmd := mul(sub(Q.y, P.y, ec.modulus),
                invmod(sub(Q.x, P.x, ec.modulus), ec.modulus), ec.modulus)
    x3 := sub(sub(expMod(lmd, TWO, ec.modulus), P.x, ec.modulus), Q.x, ec.modulus)
    y3 := sub(mul(lmd, sub(P.x, x3, ec.modulus), ec.modulus), P.y, ec.modulus)

    return Point{x3, y3, false}
}

func (ec EllipticCurve) PointDoubling(P Point) Point {
    if P.y.Cmp(ZERO) == 0 {
        return O
    }

    lmd := mul(add(mul(
                    THREE, expMod(P.x, TWO, ec.modulus), ec.modulus),
                ec.A, ec.modulus),
            invmod(mul(TWO, P.y, ec.modulus), ec.modulus), ec.modulus)
    x3 := sub(sub(expMod(lmd, TWO, ec.modulus), P.x, ec.modulus), P.x, ec.modulus)
    y3 := sub(mul(lmd, sub(P.x, x3, ec.modulus), ec.modulus), P.y, ec.modulus)

    return Point{x3, y3, false}
}
func (ec EllipticCurve) Point_xP(x *big.Int, p Point) Point {
    base_p := Point{p.x, p.y, p.isUnit}
    n := new(big.Int).SetBytes(x.Bytes()) // Not to change 'x' (address) value

    div := make_divlist(n)
    for idx := len(div)-1; idx >= 0; idx-- {
        if div[idx] == 0 {
            p = ec.PointAdd(p, base_p)
        } else {
            for i := 0; i < div[idx]; i++ {
                p = ec.PointDoubling(p)
            }
        }
    }
    return p
}

func (ec EllipticCurve) VerifySignature(r, s, e, n *big.Int, G, Q Point) bool {
    w := invmod(s, n)
    u1 := mul(e, w, n)
    u2 := mul(r, w, n)
    V := ec.PointAdd(ec.Point_xP(u1, G), ec.Point_xP(u2, Q))
    //fmt.Println("[+] (x2, y2):", Point2Str(V))
    return V.x.Cmp(r) == 0
}

func (ec EllipticCurve) Sign(e, d, n *big.Int, G Point) (*big.Int, *big.Int) {
    k, _ := rand.Int(rand.Reader, n)
    R := ec.Point_xP(k, G)
    fmt.Println("[+] (x1, y1) = [k]G:", Point2Str(R))
    r, _ := R.Xy()
    s := mul(invmod(k, n), add(e, mul(r, d, n), n), n)
    fmt.Printf("[+] Signature (r, s): (%d, %d)\n", r, s)
    return r, s
}

func main() {
    seed, _ := rand.Int(rand.Reader, big.NewInt(math.MaxInt64))
    mrand.Seed(seed.Int64())

    a := Str2Int("1461501637330902918203684832716283019653785059324", 10)
    b := Str2Int("163235791306168110546604919403271579530548345413", 10)
    p := Str2Int("1461501637330902918203684832716283019653785059327", 10)

    n := Str2Int("1461501637330902918203687197606826779884643492439", 10)

    EC := EllipticCurve{a, b, p}
    EC.PrintCurve()
    fmt.Printf("[+] Order n: %d\n", n)

    gx := Str2Int("598833001378563909320556562387727035658124457364", 10)
    gy := Str2Int("456273172676936625440583883939668862699127599796", 10)
    G := Point{gx, gy, false}
    fmt.Println("[+] Base Point G:", Point2Str(G))

    e := big.NewInt(114514)
    d, _ := rand.Int(rand.Reader, n)
    Q := EC.Point_xP(d, G)
    fmt.Println("[+] Q:", Point2Str(Q))

    // Signature
    r, s := EC.Sign(e, d, n, G)

    // Verify
    result := EC.VerifySignature(r, s, e, n, G, Q)
    fmt.Println("[+] Result of Validation:", result)
}

/* Result
[+] EC: y^2 = x^3 + 1461501637330902918203684832716283019653785059324x + 163235791306168110546604919403271579530548345413  OVER Zmod(1461501637330902918203684832716283019653785059327)
[+] Order n: 1461501637330902918203687197606826779884643492439
[+] Base Point G: (598833001378563909320556562387727035658124457364, 456273172676936625440583883939668862699127599796; 1)
[+] Q: (1318554549494287053262111889551717941864435764704, 774913702255831683088947980115102387079046540064; 1)
[+] (x1, y1) = [k]G: (14720556083127095776185015913013094871320904184, 1309589383310116814904719221984241551042131580757; 1)
[+] Signature (r, s): (14720556083127095776185015913013094871320904184, 659541053434319655488085229293369617127403102972)
[+] Result of Validation: true
*/