Golang Hash Password to CurveWe can hash a password onto an elliptic curve. With this Bob will hash his password to an elliptic curve point. Alice then passes a challenge to Bob, and he will return a masked value back, and which Alice can check that he knows his password. |
Outline
Bob first takes this password (pwd) and take a hash of it:
\(h=H(pwd)\)
We then convert \(h\) to a x-point (\(x\)), and try to fit onto an elliptic curve \((x,y)\), and then incrementing \(x\) up until we get a point that is on the curve. The gives us the hashed point \((pkx,pky)\). This point can then be registered with Alice for the seed of his password:
\(P=(pkx,pky)\)
When Bob wants to login, Alice sends him a random value (\(r\)) and asks him to mask his password by sending back:
\(L=rP\)
This is the point \(P\) added to itself \(r\) times (P+P+ ... +P). Bob passes this back, and Alice performs the operation of:
\(R = r^{-1} L \pmod p\)
We thus find the inverse of \(r \mod p\), and multiply it with the \(L\) point. The point (\(R\)) should then match the password hash value that Bob registered (P).An intruder could find out the point that Bob has registered, but because it is difficult to determine the value of \(h\), it will not be easy for Eve to determine
A sample run is:
Password: abc Hash to point: 95017883689903263263412437934895862529149298257614557298284005734876875048308 61433049493608443686329451970034081715042206578701532908334510179548401320619 Random value: 100744741463562276901487354539524967185255486670144893236967491661792699544457 Masked: 66968489052222159410273282624824899566726664000799114608156879464886044766100 95020879848341971820418321248547925592982068187581203731552863736303952405161 Unmasked: 95017883689903263263412437934895862529149298257614557298284005734876875048308 61433049493608443686329451970034081715042206578701532908334510179548401320619
The following code is based on this [code]:
package main import ( "crypto/elliptic" "crypto/rand" "crypto/sha256" "fmt" "math/big" "flag" ) var ( c = elliptic.P256() k = new(big.Int).SetBytes([]byte{164, 98, 192, 51, 205, 206, 226, 85, 22, 79, 248, 231, 248, 171, 160, 1, 248, 166, 173, 240, 47, 68, 92, 163, 33, 118, 150, 220, 69, 51, 98}) ) var one = new(big.Int).SetInt64(1) // A invertible implements fast inverse mod Curve.Params().N type invertible interface { // Inverse returns the inverse of k in GF(P) Inverse(k *big.Int) *big.Int } func randScalar(c elliptic.Curve) (k *big.Int, err error) { params := c.Params() k, err = rand.Int(rand.Reader, params.N) return } func fermatInverse(k, N *big.Int) *big.Int { two := big.NewInt(2) nMinus2 := new(big.Int).Sub(N, two) return new(big.Int).Exp(k, nMinus2, N) } func tryPoint(r []byte) (x, y *big.Int) { hash := sha256.Sum256(r) x = new(big.Int).SetBytes(hash[:]) x3 := new(big.Int).Mul(x, x) x3.Mul(x3, x) threeX := new(big.Int).Lsh(x, 1) threeX.Add(threeX, x) x3.Sub(x3, threeX) x3.Add(x3, c.Params().B) y = x3.ModSqrt(x3, c.Params().P) return } func increment(counter []byte) { for i := len(counter) - 1; i >= 0; i-- { counter[i]++ if counter[i] != 0 { break } } } func HashIntoCurvePoint(r []byte) (x, y *big.Int) { t := make([]byte, 32) copy(t, r) x, y = tryPoint(t) for y == nil || !c.IsOnCurve(x, y) { increment(t) x, y = tryPoint(t) } return } func main() { flag.Parse() args := flag.Args() pwd:=args[0] hash := sha256.Sum256([]byte(pwd)) pkx, pky := HashIntoCurvePoint(hash[:]) // Convert password hash into elliptic curve point. fmt.Println("Password: ", pwd) fmt.Println("\nHash to point:\t", pkx, pky) r, _ := randScalar(c) // Random value to mask password x, y := c.ScalarMult(pkx, pky, r.Bytes()) // Calculate point on elliptic curve fmt.Println("\nRandom value:\t", r) fmt.Println("\nMasked:\t", x, y) rInv := fermatInverse(r, c.Params().N) // rInv = r ^-1 x1, y1 := c.ScalarMult(x, y, rInv.Bytes()) fmt.Println("\nUnmasked:\t", x1, y1) }
The HashIntoCurvePoint method will take the x,y point of the hash, and then increment the x point to see if there is a valid point on the elliptic curve. This is tested with tryPoint().