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 5package extra25519 6 7import "gitlab.com/yawning/obfs4.git/internal/edwards25519" 8 9// sqrtMinusAPlus2 is sqrt(-(486662+2)) 10var sqrtMinusAPlus2 = edwards25519.FieldElement{ 11 -12222970, -8312128, -11511410, 9067497, -15300785, -241793, 25456130, 14121551, -12187136, 3972024, 12} 13 14// sqrtMinusHalf is sqrt(-1/2) 15var sqrtMinusHalf = edwards25519.FieldElement{ 16 -17256545, 3971863, 28865457, -1750208, 27359696, -16640980, 12573105, 1002827, -163343, 11073975, 17} 18 19// halfQMinus1Bytes is (2^255-20)/2 expressed in little endian form. 20var halfQMinus1Bytes = [32]byte{ 21 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, 22} 23 24// feBytesLess returns one if a <= b and zero otherwise. 25func feBytesLE(a, b *[32]byte) int32 { 26 equalSoFar := int32(-1) 27 greater := int32(0) 28 29 for i := uint(31); i < 32; i-- { 30 x := int32(a[i]) 31 y := int32(b[i]) 32 33 greater = (^equalSoFar & greater) | (equalSoFar & ((x - y) >> 31)) 34 equalSoFar = equalSoFar & (((x ^ y) - 1) >> 31) 35 } 36 37 return int32(^equalSoFar & 1 & greater) 38} 39 40// UnsafeBrokenScalarBaseMult computes a curve25519 public key from a private 41// key and also a uniform representative for that public key. Note that this 42// function will fail and return false for about half of private keys. 43// See http://elligator.cr.yp.to/elligator-20130828.pdf. 44func UnsafeBrokenScalarBaseMult(publicKey, representative, privateKey *[32]byte) bool { 45 var maskedPrivateKey [32]byte 46 copy(maskedPrivateKey[:], privateKey[:]) 47 48 maskedPrivateKey[0] &= 248 49 maskedPrivateKey[31] &= 127 50 maskedPrivateKey[31] |= 64 51 52 var A edwards25519.ExtendedGroupElement 53 edwards25519.GeScalarMultBase(&A, &maskedPrivateKey) 54 55 var inv1 edwards25519.FieldElement 56 edwards25519.FeSub(&inv1, &A.Z, &A.Y) 57 edwards25519.FeMul(&inv1, &inv1, &A.X) 58 edwards25519.FeInvert(&inv1, &inv1) 59 60 var t0, u edwards25519.FieldElement 61 edwards25519.FeMul(&u, &inv1, &A.X) 62 edwards25519.FeAdd(&t0, &A.Y, &A.Z) 63 edwards25519.FeMul(&u, &u, &t0) 64 65 var v edwards25519.FieldElement 66 edwards25519.FeMul(&v, &t0, &inv1) 67 edwards25519.FeMul(&v, &v, &A.Z) 68 edwards25519.FeMul(&v, &v, &sqrtMinusAPlus2) 69 70 var b edwards25519.FieldElement 71 edwards25519.FeAdd(&b, &u, &edwards25519.A) 72 73 var c, b3, b7, b8 edwards25519.FieldElement 74 edwards25519.FeSquare(&b3, &b) // 2 75 edwards25519.FeMul(&b3, &b3, &b) // 3 76 edwards25519.FeSquare(&c, &b3) // 6 77 edwards25519.FeMul(&b7, &c, &b) // 7 78 edwards25519.FeMul(&b8, &b7, &b) // 8 79 edwards25519.FeMul(&c, &b7, &u) 80 q58(&c, &c) 81 82 var chi edwards25519.FieldElement 83 edwards25519.FeSquare(&chi, &c) 84 edwards25519.FeSquare(&chi, &chi) 85 86 edwards25519.FeSquare(&t0, &u) 87 edwards25519.FeMul(&chi, &chi, &t0) 88 89 edwards25519.FeSquare(&t0, &b7) // 14 90 edwards25519.FeMul(&chi, &chi, &t0) 91 edwards25519.FeNeg(&chi, &chi) 92 93 var chiBytes [32]byte 94 edwards25519.FeToBytes(&chiBytes, &chi) 95 // chi[1] is either 0 or 0xff 96 if chiBytes[1] == 0xff { 97 return false 98 } 99 100 // Calculate r1 = sqrt(-u/(2*(u+A))) 101 var r1 edwards25519.FieldElement 102 edwards25519.FeMul(&r1, &c, &u) 103 edwards25519.FeMul(&r1, &r1, &b3) 104 edwards25519.FeMul(&r1, &r1, &sqrtMinusHalf) 105 106 var maybeSqrtM1 edwards25519.FieldElement 107 edwards25519.FeSquare(&t0, &r1) 108 edwards25519.FeMul(&t0, &t0, &b) 109 edwards25519.FeAdd(&t0, &t0, &t0) 110 edwards25519.FeAdd(&t0, &t0, &u) 111 112 edwards25519.FeOne(&maybeSqrtM1) 113 edwards25519.FeCMove(&maybeSqrtM1, &edwards25519.SqrtM1, edwards25519.FeIsNonZero(&t0)) 114 edwards25519.FeMul(&r1, &r1, &maybeSqrtM1) 115 116 // Calculate r = sqrt(-(u+A)/(2u)) 117 var r edwards25519.FieldElement 118 edwards25519.FeSquare(&t0, &c) // 2 119 edwards25519.FeMul(&t0, &t0, &c) // 3 120 edwards25519.FeSquare(&t0, &t0) // 6 121 edwards25519.FeMul(&r, &t0, &c) // 7 122 123 edwards25519.FeSquare(&t0, &u) // 2 124 edwards25519.FeMul(&t0, &t0, &u) // 3 125 edwards25519.FeMul(&r, &r, &t0) 126 127 edwards25519.FeSquare(&t0, &b8) // 16 128 edwards25519.FeMul(&t0, &t0, &b8) // 24 129 edwards25519.FeMul(&t0, &t0, &b) // 25 130 edwards25519.FeMul(&r, &r, &t0) 131 edwards25519.FeMul(&r, &r, &sqrtMinusHalf) 132 133 edwards25519.FeSquare(&t0, &r) 134 edwards25519.FeMul(&t0, &t0, &u) 135 edwards25519.FeAdd(&t0, &t0, &t0) 136 edwards25519.FeAdd(&t0, &t0, &b) 137 edwards25519.FeOne(&maybeSqrtM1) 138 edwards25519.FeCMove(&maybeSqrtM1, &edwards25519.SqrtM1, edwards25519.FeIsNonZero(&t0)) 139 edwards25519.FeMul(&r, &r, &maybeSqrtM1) 140 141 var vBytes [32]byte 142 edwards25519.FeToBytes(&vBytes, &v) 143 vInSquareRootImage := feBytesLE(&vBytes, &halfQMinus1Bytes) 144 edwards25519.FeCMove(&r, &r1, vInSquareRootImage) 145 146 edwards25519.FeToBytes(publicKey, &u) 147 edwards25519.FeToBytes(representative, &r) 148 return true 149} 150 151// q58 calculates out = z^((p-5)/8). 152func q58(out, z *edwards25519.FieldElement) { 153 var t1, t2, t3 edwards25519.FieldElement 154 var i int 155 156 edwards25519.FeSquare(&t1, z) // 2^1 157 edwards25519.FeMul(&t1, &t1, z) // 2^1 + 2^0 158 edwards25519.FeSquare(&t1, &t1) // 2^2 + 2^1 159 edwards25519.FeSquare(&t2, &t1) // 2^3 + 2^2 160 edwards25519.FeSquare(&t2, &t2) // 2^4 + 2^3 161 edwards25519.FeMul(&t2, &t2, &t1) // 4,3,2,1 162 edwards25519.FeMul(&t1, &t2, z) // 4..0 163 edwards25519.FeSquare(&t2, &t1) // 5..1 164 for i = 1; i < 5; i++ { // 9,8,7,6,5 165 edwards25519.FeSquare(&t2, &t2) 166 } 167 edwards25519.FeMul(&t1, &t2, &t1) // 9,8,7,6,5,4,3,2,1,0 168 edwards25519.FeSquare(&t2, &t1) // 10..1 169 for i = 1; i < 10; i++ { // 19..10 170 edwards25519.FeSquare(&t2, &t2) 171 } 172 edwards25519.FeMul(&t2, &t2, &t1) // 19..0 173 edwards25519.FeSquare(&t3, &t2) // 20..1 174 for i = 1; i < 20; i++ { // 39..20 175 edwards25519.FeSquare(&t3, &t3) 176 } 177 edwards25519.FeMul(&t2, &t3, &t2) // 39..0 178 edwards25519.FeSquare(&t2, &t2) // 40..1 179 for i = 1; i < 10; i++ { // 49..10 180 edwards25519.FeSquare(&t2, &t2) 181 } 182 edwards25519.FeMul(&t1, &t2, &t1) // 49..0 183 edwards25519.FeSquare(&t2, &t1) // 50..1 184 for i = 1; i < 50; i++ { // 99..50 185 edwards25519.FeSquare(&t2, &t2) 186 } 187 edwards25519.FeMul(&t2, &t2, &t1) // 99..0 188 edwards25519.FeSquare(&t3, &t2) // 100..1 189 for i = 1; i < 100; i++ { // 199..100 190 edwards25519.FeSquare(&t3, &t3) 191 } 192 edwards25519.FeMul(&t2, &t3, &t2) // 199..0 193 edwards25519.FeSquare(&t2, &t2) // 200..1 194 for i = 1; i < 50; i++ { // 249..50 195 edwards25519.FeSquare(&t2, &t2) 196 } 197 edwards25519.FeMul(&t1, &t2, &t1) // 249..0 198 edwards25519.FeSquare(&t1, &t1) // 250..1 199 edwards25519.FeSquare(&t1, &t1) // 251..2 200 edwards25519.FeMul(out, &t1, z) // 251..2,0 201} 202 203// chi calculates out = z^((p-1)/2). The result is either 1, 0, or -1 depending 204// on whether z is a non-zero square, zero, or a non-square. 205func chi(out, z *edwards25519.FieldElement) { 206 var t0, t1, t2, t3 edwards25519.FieldElement 207 var i int 208 209 edwards25519.FeSquare(&t0, z) // 2^1 210 edwards25519.FeMul(&t1, &t0, z) // 2^1 + 2^0 211 edwards25519.FeSquare(&t0, &t1) // 2^2 + 2^1 212 edwards25519.FeSquare(&t2, &t0) // 2^3 + 2^2 213 edwards25519.FeSquare(&t2, &t2) // 4,3 214 edwards25519.FeMul(&t2, &t2, &t0) // 4,3,2,1 215 edwards25519.FeMul(&t1, &t2, z) // 4..0 216 edwards25519.FeSquare(&t2, &t1) // 5..1 217 for i = 1; i < 5; i++ { // 9,8,7,6,5 218 edwards25519.FeSquare(&t2, &t2) 219 } 220 edwards25519.FeMul(&t1, &t2, &t1) // 9,8,7,6,5,4,3,2,1,0 221 edwards25519.FeSquare(&t2, &t1) // 10..1 222 for i = 1; i < 10; i++ { // 19..10 223 edwards25519.FeSquare(&t2, &t2) 224 } 225 edwards25519.FeMul(&t2, &t2, &t1) // 19..0 226 edwards25519.FeSquare(&t3, &t2) // 20..1 227 for i = 1; i < 20; i++ { // 39..20 228 edwards25519.FeSquare(&t3, &t3) 229 } 230 edwards25519.FeMul(&t2, &t3, &t2) // 39..0 231 edwards25519.FeSquare(&t2, &t2) // 40..1 232 for i = 1; i < 10; i++ { // 49..10 233 edwards25519.FeSquare(&t2, &t2) 234 } 235 edwards25519.FeMul(&t1, &t2, &t1) // 49..0 236 edwards25519.FeSquare(&t2, &t1) // 50..1 237 for i = 1; i < 50; i++ { // 99..50 238 edwards25519.FeSquare(&t2, &t2) 239 } 240 edwards25519.FeMul(&t2, &t2, &t1) // 99..0 241 edwards25519.FeSquare(&t3, &t2) // 100..1 242 for i = 1; i < 100; i++ { // 199..100 243 edwards25519.FeSquare(&t3, &t3) 244 } 245 edwards25519.FeMul(&t2, &t3, &t2) // 199..0 246 edwards25519.FeSquare(&t2, &t2) // 200..1 247 for i = 1; i < 50; i++ { // 249..50 248 edwards25519.FeSquare(&t2, &t2) 249 } 250 edwards25519.FeMul(&t1, &t2, &t1) // 249..0 251 edwards25519.FeSquare(&t1, &t1) // 250..1 252 for i = 1; i < 4; i++ { // 253..4 253 edwards25519.FeSquare(&t1, &t1) 254 } 255 edwards25519.FeMul(out, &t1, &t0) // 253..4,2,1 256} 257 258// UnsafeBrokenRepresentativeToPublicKey converts a uniform representative 259// value for a curve25519 public key, as produced by UnsafeBrokenScalarBaseMult, 260// to a curve25519 public key. 261func UnsafeBrokenRepresentativeToPublicKey(publicKey, representative *[32]byte) { 262 var rr2, v, e edwards25519.FieldElement 263 edwards25519.FeFromBytes(&rr2, representative) 264 265 edwards25519.FeSquare2(&rr2, &rr2) 266 rr2[0]++ 267 edwards25519.FeInvert(&rr2, &rr2) 268 edwards25519.FeMul(&v, &edwards25519.A, &rr2) 269 edwards25519.FeNeg(&v, &v) 270 271 var v2, v3 edwards25519.FieldElement 272 edwards25519.FeSquare(&v2, &v) 273 edwards25519.FeMul(&v3, &v, &v2) 274 edwards25519.FeAdd(&e, &v3, &v) 275 edwards25519.FeMul(&v2, &v2, &edwards25519.A) 276 edwards25519.FeAdd(&e, &v2, &e) 277 chi(&e, &e) 278 var eBytes [32]byte 279 edwards25519.FeToBytes(&eBytes, &e) 280 // eBytes[1] is either 0 (for e = 1) or 0xff (for e = -1) 281 eIsMinus1 := int32(eBytes[1]) & 1 282 var negV edwards25519.FieldElement 283 edwards25519.FeNeg(&negV, &v) 284 edwards25519.FeCMove(&v, &negV, eIsMinus1) 285 286 edwards25519.FeZero(&v2) 287 edwards25519.FeCMove(&v2, &edwards25519.A, eIsMinus1) 288 edwards25519.FeSub(&v, &v, &v2) 289 290 edwards25519.FeToBytes(publicKey, &v) 291} 292