Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

crypto/elliptic: wrong elliptic multiplication in elliptic.go #35419

Closed
ndv opened this issue Nov 7, 2019 · 7 comments

Comments

@ndv
Copy link

@ndv ndv commented Nov 7, 2019

What version of Go are you using (go version)?

$ go version
go version go1.13.3 linux/amd64

C:\Users\dmitr>go version
go version go1.11.4 windows/amd64

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (go env)?

go env Output
$ go env
GO111MODULE=""
GOARCH="amd64"
GOBIN=""
GOCACHE="/home/ubuntu/.cache/go-build"
GOENV="/home/ubuntu/.config/go/env"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPATH="/home/ubuntu"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/home/ubuntu/go"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/home/ubuntu/go/pkg/tool/linux_amd64"
GCCGO="gccgo"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD=""
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build681695391=/tmp/go-build -gno-record-gcc-switches"

What did you do?

Run this program:

package main

import (
	"crypto/elliptic"
	"fmt"
	"math/big"
)

func main() {
	P, _  := new(big.Int).SetString("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 0)
	N, _  := new(big.Int).SetString("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141", 0)
	B, _  := new(big.Int).SetString("0x0000000000000000000000000000000000000000000000000000000000000007", 0)
	Gx, _ := new(big.Int).SetString("0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 0)
	Gy, _ := new(big.Int).SetString("0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8", 0)
	BitSize := 256

	params := &elliptic.CurveParams{P: P,  N: N, B: B, Gx: Gx, Gy: Gy, BitSize: BitSize}

	x, y := params.ScalarBaseMult([]byte{1})
	fmt.Printf("1 * G = (%s, %s)\n", x.Text(16), y.Text(16))

	x, y = params.ScalarBaseMult([]byte{2})
	fmt.Printf("2 * G = (%s, %s)\n", x.Text(16), y.Text(16))
}

Code in playground: https://play.golang.org/p/dWxfm6Jl8sG

What did you expect to see?

See a similar program that uses OpenSSL. Compile and run the sample: gcc mul2.c -lcrypto && ./a.out

1 * G = (79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)
2 * G = (C6047F9441ED7D6D3045406E95C07CD85C778E4B8CEF3CA7ABAC09B95C709EE5, 1AE168FEA63DC339A3C58419466CEAEEF7F632653266D0E1236431A950CFE52A)

What did you see instead?

1 * G = (79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
2 * G = (3818704452a03d52f1ccc4276e45d4a6f70113ae41ae89678517b39616c3ae30, 6555d5e48fe95b0dc5feeaac07ba5d0a467877022a0e1aee64cc77e20b164986)

@mundaym

This comment has been minimized.

Copy link
Member

@mundaym mundaym commented Nov 7, 2019

Can you paste your C example so that people don't have to download the zip to read it? Thanks.

@mundaym mundaym changed the title Wrong elliptic multiplication in elliptic.go crypto/elliptic: wrong elliptic multiplication in elliptic.go Nov 7, 2019
@ndv

This comment has been minimized.

Copy link
Author

@ndv ndv commented Nov 7, 2019

My time is just as valuable as the developers'

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Nov 7, 2019

Yes, your time is just as valuable. But there are very few core Go developers, and there are very many people using Go and reporting issues. If we each put in equal amounts of time, the core Go developers will be even more overwhelmed than they already are. It helps all of us if we can allocate time in a more strategic way. Thanks.

Of course, the very best way to use your time is to analyze and fix the issue yourself. That's how free software moves forwards. (And, to be clear, although I work for Google, @mundaym does not.)

Thanks for reporting the issue.

@ianlancetaylor ianlancetaylor added this to the Go1.14 milestone Nov 7, 2019
@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Nov 7, 2019

ndv added a commit to ndv/kv that referenced this issue Nov 9, 2019
ndv added a commit to ndv/kv that referenced this issue Nov 9, 2019
@magical

This comment has been minimized.

Copy link
Contributor

@magical magical commented Nov 9, 2019

Your base point does not appear to be a valid point on the curve: https://play.golang.org/p/si_d51UZP5n. If that's the case, then I'm not surprised that ScalarBaseMult doesn't work.

@FiloSottile

This comment has been minimized.

Copy link
Member

@FiloSottile FiloSottile commented Nov 9, 2019

Indeed, these don't look like valid parameters, thanks @magical.

@FiloSottile FiloSottile closed this Nov 9, 2019
@magical

This comment has been minimized.

Copy link
Contributor

@magical magical commented Nov 9, 2019

A little more info: I googled the params, and It looks like you are trying to implement the secp256k1 curve. However, that curve uses a=0 whereas elliptic.CurveParams is hardcoded to use a=-3 (which is what the NIST curves use). These are incompatible types of curves, so it's not surprising that it didn't work. I'd suggest using one of the existing third-party libraries that implement secp256k1. Or if possible, choosing a different curve.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
5 participants
You can’t perform that action at this time.