vendor/github.com/tendermint/ed25519/extra25519/extra25519.go

   1 // Copyright 2013 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package extra25519
   6
   7 import (
   8         "crypto/sha512"
   9
  10         "github.com/tendermint/ed25519/edwards25519"
  11 )
  12
  13 // PrivateKeyToCurve25519 converts an ed25519 private key into a corresponding
  14 // curve25519 private key such that the resulting curve25519 public key will
  15 // equal the result from PublicKeyToCurve25519.
  16 func PrivateKeyToCurve25519(curve25519Private *[32]byte, privateKey *[64]byte) {
  17         h := sha512.New()
  18         h.Write(privateKey[:32])
  19         digest := h.Sum(nil)
  20
  21         digest[0] &= 248
  22         digest[31] &= 127
  23         digest[31] |= 64
  24
  25         copy(curve25519Private[:], digest)
  26 }
  27
  28 func edwardsToMontgomeryX(outX, y *edwards25519.FieldElement) {
  29         // We only need the x-coordinate of the curve25519 point, which I'll
  30         // call u. The isomorphism is u=(y+1)/(1-y), since y=Y/Z, this gives
  31         // u=(Y+Z)/(Z-Y). We know that Z=1, thus u=(Y+1)/(1-Y).
  32         var oneMinusY edwards25519.FieldElement
  33         edwards25519.FeOne(&oneMinusY)
  34         edwards25519.FeSub(&oneMinusY, &oneMinusY, y)
  35         edwards25519.FeInvert(&oneMinusY, &oneMinusY)
  36
  37         edwards25519.FeOne(outX)
  38         edwards25519.FeAdd(outX, outX, y)
  39
  40         edwards25519.FeMul(outX, outX, &oneMinusY)
  41 }
  42
  43 // PublicKeyToCurve25519 converts an Ed25519 public key into the curve25519
  44 // public key that would be generated from the same private key.
  45 func PublicKeyToCurve25519(curve25519Public *[32]byte, publicKey *[32]byte) bool {
  46         var A edwards25519.ExtendedGroupElement
  47         if !A.FromBytes(publicKey) {
  48                 return false
  49         }
  50
  51         // A.Z = 1 as a postcondition of FromBytes.
  52         var x edwards25519.FieldElement
  53         edwardsToMontgomeryX(&x, &A.Y)
  54         edwards25519.FeToBytes(curve25519Public, &x)
  55         return true
  56 }
  57
  58 // sqrtMinusAPlus2 is sqrt(-(486662+2))
  59 var sqrtMinusAPlus2 = edwards25519.FieldElement{
  60         -12222970, -8312128, -11511410, 9067497, -15300785, -241793, 25456130, 14121551, -12187136, 3972024,
  61 }
  62
  63 // sqrtMinusHalf is sqrt(-1/2)
  64 var sqrtMinusHalf = edwards25519.FieldElement{
  65         -17256545, 3971863, 28865457, -1750208, 27359696, -16640980, 12573105, 1002827, -163343, 11073975,
  66 }
  67
  68 // halfQMinus1Bytes is (2^255-20)/2 expressed in little endian form.
  69 var halfQMinus1Bytes = [32]byte{
  70         0xf6, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x3f,
  71 }
  72
  73 // feBytesLess returns one if a <= b and zero otherwise.
  74 func feBytesLE(a, b *[32]byte) int32 {
  75         equalSoFar := int32(-1)
  76         greater := int32(0)
  77
  78         for i := uint(31); i < 32; i-- {
  79                 x := int32(a[i])
  80                 y := int32(b[i])
  81
  82                 greater = (^equalSoFar & greater) | (equalSoFar & ((x - y) >> 31))
  83                 equalSoFar = equalSoFar & (((x ^ y) - 1) >> 31)
  84         }
  85
  86         return int32(^equalSoFar & 1 & greater)
  87 }
  88
  89 // ScalarBaseMult computes a curve25519 public key from a private key and also
  90 // a uniform representative for that public key. Note that this function will
  91 // fail and return false for about half of private keys.
  92 // See http://elligator.cr.yp.to/elligator-20130828.pdf.
  93 func ScalarBaseMult(publicKey, representative, privateKey *[32]byte) bool {
  94         var maskedPrivateKey [32]byte
  95         copy(maskedPrivateKey[:], privateKey[:])
  96
  97         maskedPrivateKey[0] &= 248
  98         maskedPrivateKey[31] &= 127
  99         maskedPrivateKey[31] |= 64
 100
 101         var A edwards25519.ExtendedGroupElement
 102         edwards25519.GeScalarMultBase(&A, &maskedPrivateKey)
 103
 104         var inv1 edwards25519.FieldElement
 105         edwards25519.FeSub(&inv1, &A.Z, &A.Y)
 106         edwards25519.FeMul(&inv1, &inv1, &A.X)
 107         edwards25519.FeInvert(&inv1, &inv1)
 108
 109         var t0, u edwards25519.FieldElement
 110         edwards25519.FeMul(&u, &inv1, &A.X)
 111         edwards25519.FeAdd(&t0, &A.Y, &A.Z)
 112         edwards25519.FeMul(&u, &u, &t0)
 113
 114         var v edwards25519.FieldElement
 115         edwards25519.FeMul(&v, &t0, &inv1)
 116         edwards25519.FeMul(&v, &v, &A.Z)
 117         edwards25519.FeMul(&v, &v, &sqrtMinusAPlus2)
 118
 119         var b edwards25519.FieldElement
 120         edwards25519.FeAdd(&b, &u, &edwards25519.A)
 121
 122         var c, b3, b7, b8 edwards25519.FieldElement
 123         edwards25519.FeSquare(&b3, &b)   // 2
 124         edwards25519.FeMul(&b3, &b3, &b) // 3
 125         edwards25519.FeSquare(&c, &b3)   // 6
 126         edwards25519.FeMul(&b7, &c, &b)  // 7
 127         edwards25519.FeMul(&b8, &b7, &b) // 8
 128         edwards25519.FeMul(&c, &b7, &u)
 129         q58(&c, &c)
 130
 131         var chi edwards25519.FieldElement
 132         edwards25519.FeSquare(&chi, &c)
 133         edwards25519.FeSquare(&chi, &chi)
 134
 135         edwards25519.FeSquare(&t0, &u)
 136         edwards25519.FeMul(&chi, &chi, &t0)
 137
 138         edwards25519.FeSquare(&t0, &b7) // 14
 139         edwards25519.FeMul(&chi, &chi, &t0)
 140         edwards25519.FeNeg(&chi, &chi)
 141
 142         var chiBytes [32]byte
 143         edwards25519.FeToBytes(&chiBytes, &chi)
 144         // chi[1] is either 0 or 0xff
 145         if chiBytes[1] == 0xff {
 146                 return false
 147         }
 148
 149         // Calculate r1 = sqrt(-u/(2*(u+A)))
 150         var r1 edwards25519.FieldElement
 151         edwards25519.FeMul(&r1, &c, &u)
 152         edwards25519.FeMul(&r1, &r1, &b3)
 153         edwards25519.FeMul(&r1, &r1, &sqrtMinusHalf)
 154
 155         var maybeSqrtM1 edwards25519.FieldElement
 156         edwards25519.FeSquare(&t0, &r1)
 157         edwards25519.FeMul(&t0, &t0, &b)
 158         edwards25519.FeAdd(&t0, &t0, &t0)
 159         edwards25519.FeAdd(&t0, &t0, &u)
 160
 161         edwards25519.FeOne(&maybeSqrtM1)
 162         edwards25519.FeCMove(&maybeSqrtM1, &edwards25519.SqrtM1, edwards25519.FeIsNonZero(&t0))
 163         edwards25519.FeMul(&r1, &r1, &maybeSqrtM1)
 164
 165         // Calculate r = sqrt(-(u+A)/(2u))
 166         var r edwards25519.FieldElement
 167         edwards25519.FeSquare(&t0, &c)   // 2
 168         edwards25519.FeMul(&t0, &t0, &c) // 3
 169         edwards25519.FeSquare(&t0, &t0)  // 6
 170         edwards25519.FeMul(&r, &t0, &c)  // 7
 171
 172         edwards25519.FeSquare(&t0, &u)   // 2
 173         edwards25519.FeMul(&t0, &t0, &u) // 3
 174         edwards25519.FeMul(&r, &r, &t0)
 175
 176         edwards25519.FeSquare(&t0, &b8)   // 16
 177         edwards25519.FeMul(&t0, &t0, &b8) // 24
 178         edwards25519.FeMul(&t0, &t0, &b)  // 25
 179         edwards25519.FeMul(&r, &r, &t0)
 180         edwards25519.FeMul(&r, &r, &sqrtMinusHalf)
 181
 182         edwards25519.FeSquare(&t0, &r)
 183         edwards25519.FeMul(&t0, &t0, &u)
 184         edwards25519.FeAdd(&t0, &t0, &t0)
 185         edwards25519.FeAdd(&t0, &t0, &b)
 186         edwards25519.FeOne(&maybeSqrtM1)
 187         edwards25519.FeCMove(&maybeSqrtM1, &edwards25519.SqrtM1, edwards25519.FeIsNonZero(&t0))
 188         edwards25519.FeMul(&r, &r, &maybeSqrtM1)
 189
 190         var vBytes [32]byte
 191         edwards25519.FeToBytes(&vBytes, &v)
 192         vInSquareRootImage := feBytesLE(&vBytes, &halfQMinus1Bytes)
 193         edwards25519.FeCMove(&r, &r1, vInSquareRootImage)
 194
 195         edwards25519.FeToBytes(publicKey, &u)
 196         edwards25519.FeToBytes(representative, &r)
 197         return true
 198 }
 199
 200 // q58 calculates out = z^((p-5)/8).
 201 func q58(out, z *edwards25519.FieldElement) {
 202         var t1, t2, t3 edwards25519.FieldElement
 203         var i int
 204
 205         edwards25519.FeSquare(&t1, z)     // 2^1
 206         edwards25519.FeMul(&t1, &t1, z)   // 2^1 + 2^0
 207         edwards25519.FeSquare(&t1, &t1)   // 2^2 + 2^1
 208         edwards25519.FeSquare(&t2, &t1)   // 2^3 + 2^2
 209         edwards25519.FeSquare(&t2, &t2)   // 2^4 + 2^3
 210         edwards25519.FeMul(&t2, &t2, &t1) // 4,3,2,1
 211         edwards25519.FeMul(&t1, &t2, z)   // 4..0
 212         edwards25519.FeSquare(&t2, &t1)   // 5..1
 213         for i = 1; i < 5; i++ {           // 9,8,7,6,5
 214                 edwards25519.FeSquare(&t2, &t2)
 215         }
 216         edwards25519.FeMul(&t1, &t2, &t1) // 9,8,7,6,5,4,3,2,1,0
 217         edwards25519.FeSquare(&t2, &t1)   // 10..1
 218         for i = 1; i < 10; i++ {          // 19..10
 219                 edwards25519.FeSquare(&t2, &t2)
 220         }
 221         edwards25519.FeMul(&t2, &t2, &t1) // 19..0
 222         edwards25519.FeSquare(&t3, &t2)   // 20..1
 223         for i = 1; i < 20; i++ {          // 39..20
 224                 edwards25519.FeSquare(&t3, &t3)
 225         }
 226         edwards25519.FeMul(&t2, &t3, &t2) // 39..0
 227         edwards25519.FeSquare(&t2, &t2)   // 40..1
 228         for i = 1; i < 10; i++ {          // 49..10
 229                 edwards25519.FeSquare(&t2, &t2)
 230         }
 231         edwards25519.FeMul(&t1, &t2, &t1) // 49..0
 232         edwards25519.FeSquare(&t2, &t1)   // 50..1
 233         for i = 1; i < 50; i++ {          // 99..50
 234                 edwards25519.FeSquare(&t2, &t2)
 235         }
 236         edwards25519.FeMul(&t2, &t2, &t1) // 99..0
 237         edwards25519.FeSquare(&t3, &t2)   // 100..1
 238         for i = 1; i < 100; i++ {         // 199..100
 239                 edwards25519.FeSquare(&t3, &t3)
 240         }
 241         edwards25519.FeMul(&t2, &t3, &t2) // 199..0
 242         edwards25519.FeSquare(&t2, &t2)   // 200..1
 243         for i = 1; i < 50; i++ {          // 249..50
 244                 edwards25519.FeSquare(&t2, &t2)
 245         }
 246         edwards25519.FeMul(&t1, &t2, &t1) // 249..0
 247         edwards25519.FeSquare(&t1, &t1)   // 250..1
 248         edwards25519.FeSquare(&t1, &t1)   // 251..2
 249         edwards25519.FeMul(out, &t1, z)   // 251..2,0
 250 }
 251
 252 // chi calculates out = z^((p-1)/2). The result is either 1, 0, or -1 depending
 253 // on whether z is a non-zero square, zero, or a non-square.
 254 func chi(out, z *edwards25519.FieldElement) {
 255         var t0, t1, t2, t3 edwards25519.FieldElement
 256         var i int
 257
 258         edwards25519.FeSquare(&t0, z)     // 2^1
 259         edwards25519.FeMul(&t1, &t0, z)   // 2^1 + 2^0
 260         edwards25519.FeSquare(&t0, &t1)   // 2^2 + 2^1
 261         edwards25519.FeSquare(&t2, &t0)   // 2^3 + 2^2
 262         edwards25519.FeSquare(&t2, &t2)   // 4,3
 263         edwards25519.FeMul(&t2, &t2, &t0) // 4,3,2,1
 264         edwards25519.FeMul(&t1, &t2, z)   // 4..0
 265         edwards25519.FeSquare(&t2, &t1)   // 5..1
 266         for i = 1; i < 5; i++ {           // 9,8,7,6,5
 267                 edwards25519.FeSquare(&t2, &t2)
 268         }
 269         edwards25519.FeMul(&t1, &t2, &t1) // 9,8,7,6,5,4,3,2,1,0
 270         edwards25519.FeSquare(&t2, &t1)   // 10..1
 271         for i = 1; i < 10; i++ {          // 19..10
 272                 edwards25519.FeSquare(&t2, &t2)
 273         }
 274         edwards25519.FeMul(&t2, &t2, &t1) // 19..0
 275         edwards25519.FeSquare(&t3, &t2)   // 20..1
 276         for i = 1; i < 20; i++ {          // 39..20
 277                 edwards25519.FeSquare(&t3, &t3)
 278         }
 279         edwards25519.FeMul(&t2, &t3, &t2) // 39..0
 280         edwards25519.FeSquare(&t2, &t2)   // 40..1
 281         for i = 1; i < 10; i++ {          // 49..10
 282                 edwards25519.FeSquare(&t2, &t2)
 283         }
 284         edwards25519.FeMul(&t1, &t2, &t1) // 49..0
 285         edwards25519.FeSquare(&t2, &t1)   // 50..1
 286         for i = 1; i < 50; i++ {          // 99..50
 287                 edwards25519.FeSquare(&t2, &t2)
 288         }
 289         edwards25519.FeMul(&t2, &t2, &t1) // 99..0
 290         edwards25519.FeSquare(&t3, &t2)   // 100..1
 291         for i = 1; i < 100; i++ {         // 199..100
 292                 edwards25519.FeSquare(&t3, &t3)
 293         }
 294         edwards25519.FeMul(&t2, &t3, &t2) // 199..0
 295         edwards25519.FeSquare(&t2, &t2)   // 200..1
 296         for i = 1; i < 50; i++ {          // 249..50
 297                 edwards25519.FeSquare(&t2, &t2)
 298         }
 299         edwards25519.FeMul(&t1, &t2, &t1) // 249..0
 300         edwards25519.FeSquare(&t1, &t1)   // 250..1
 301         for i = 1; i < 4; i++ {           // 253..4
 302                 edwards25519.FeSquare(&t1, &t1)
 303         }
 304         edwards25519.FeMul(out, &t1, &t0) // 253..4,2,1
 305 }
 306
 307 // RepresentativeToPublicKey converts a uniform representative value for a
 308 // curve25519 public key, as produced by ScalarBaseMult, to a curve25519 public
 309 // key.
 310 func RepresentativeToPublicKey(publicKey, representative *[32]byte) {
 311         var rr2, v, e edwards25519.FieldElement
 312         edwards25519.FeFromBytes(&rr2, representative)
 313
 314         edwards25519.FeSquare2(&rr2, &rr2)
 315         rr2[0]++
 316         edwards25519.FeInvert(&rr2, &rr2)
 317         edwards25519.FeMul(&v, &edwards25519.A, &rr2)
 318         edwards25519.FeNeg(&v, &v)
 319
 320         var v2, v3 edwards25519.FieldElement
 321         edwards25519.FeSquare(&v2, &v)
 322         edwards25519.FeMul(&v3, &v, &v2)
 323         edwards25519.FeAdd(&e, &v3, &v)
 324         edwards25519.FeMul(&v2, &v2, &edwards25519.A)
 325         edwards25519.FeAdd(&e, &v2, &e)
 326         chi(&e, &e)
 327         var eBytes [32]byte
 328         edwards25519.FeToBytes(&eBytes, &e)
 329         // eBytes[1] is either 0 (for e = 1) or 0xff (for e = -1)
 330         eIsMinus1 := int32(eBytes[1]) & 1
 331         var negV edwards25519.FieldElement
 332         edwards25519.FeNeg(&negV, &v)
 333         edwards25519.FeCMove(&v, &negV, eIsMinus1)
 334
 335         edwards25519.FeZero(&v2)
 336         edwards25519.FeCMove(&v2, &edwards25519.A, eIsMinus1)
 337         edwards25519.FeSub(&v, &v, &v2)
 338
 339         edwards25519.FeToBytes(publicKey, &v)
 340 }