1// Copyright (c) 2019 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 edwards25519 6 7import ( 8 "crypto/subtle" 9) 10 11// A dynamic lookup table for variable-base, constant-time scalar muls. 12type projLookupTable struct { 13 points [8]projCached 14} 15 16// A precomputed lookup table for fixed-base, constant-time scalar muls. 17type affineLookupTable struct { 18 points [8]affineCached 19} 20 21// A dynamic lookup table for variable-base, variable-time scalar muls. 22type nafLookupTable5 struct { 23 points [8]projCached 24} 25 26// A precomputed lookup table for fixed-base, variable-time scalar muls. 27type nafLookupTable8 struct { 28 points [64]affineCached 29} 30 31// Constructors. 32 33// Builds a lookup table at runtime. Fast. 34func (v *projLookupTable) FromP3(q *Point) { 35 // Goal: v.points[i] = (i+1)*Q, i.e., Q, 2Q, ..., 8Q 36 // This allows lookup of -8Q, ..., -Q, 0, Q, ..., 8Q 37 v.points[0].FromP3(q) 38 tmpP3 := Point{} 39 tmpP1xP1 := projP1xP1{} 40 for i := 0; i < 7; i++ { 41 // Compute (i+1)*Q as Q + i*Q and convert to a projCached 42 // This is needlessly complicated because the API has explicit 43 // receivers instead of creating stack objects and relying on RVO 44 v.points[i+1].FromP3(tmpP3.fromP1xP1(tmpP1xP1.Add(q, &v.points[i]))) 45 } 46} 47 48// This is not optimised for speed; fixed-base tables should be precomputed. 49func (v *affineLookupTable) FromP3(q *Point) { 50 // Goal: v.points[i] = (i+1)*Q, i.e., Q, 2Q, ..., 8Q 51 // This allows lookup of -8Q, ..., -Q, 0, Q, ..., 8Q 52 v.points[0].FromP3(q) 53 tmpP3 := Point{} 54 tmpP1xP1 := projP1xP1{} 55 for i := 0; i < 7; i++ { 56 // Compute (i+1)*Q as Q + i*Q and convert to affineCached 57 v.points[i+1].FromP3(tmpP3.fromP1xP1(tmpP1xP1.AddAffine(q, &v.points[i]))) 58 } 59} 60 61// Builds a lookup table at runtime. Fast. 62func (v *nafLookupTable5) FromP3(q *Point) { 63 // Goal: v.points[i] = (2*i+1)*Q, i.e., Q, 3Q, 5Q, ..., 15Q 64 // This allows lookup of -15Q, ..., -3Q, -Q, 0, Q, 3Q, ..., 15Q 65 v.points[0].FromP3(q) 66 q2 := Point{} 67 q2.Add(q, q) 68 tmpP3 := Point{} 69 tmpP1xP1 := projP1xP1{} 70 for i := 0; i < 7; i++ { 71 v.points[i+1].FromP3(tmpP3.fromP1xP1(tmpP1xP1.Add(&q2, &v.points[i]))) 72 } 73} 74 75// This is not optimised for speed; fixed-base tables should be precomputed. 76func (v *nafLookupTable8) FromP3(q *Point) { 77 v.points[0].FromP3(q) 78 q2 := Point{} 79 q2.Add(q, q) 80 tmpP3 := Point{} 81 tmpP1xP1 := projP1xP1{} 82 for i := 0; i < 63; i++ { 83 v.points[i+1].FromP3(tmpP3.fromP1xP1(tmpP1xP1.AddAffine(&q2, &v.points[i]))) 84 } 85} 86 87// Selectors. 88 89// Set dest to x*Q, where -8 <= x <= 8, in constant time. 90func (v *projLookupTable) SelectInto(dest *projCached, x int8) { 91 // Compute xabs = |x| 92 xmask := x >> 7 93 xabs := uint8((x + xmask) ^ xmask) 94 95 dest.Zero() 96 for j := 1; j <= 8; j++ { 97 // Set dest = j*Q if |x| = j 98 cond := subtle.ConstantTimeByteEq(xabs, uint8(j)) 99 dest.Select(&v.points[j-1], dest, cond) 100 } 101 // Now dest = |x|*Q, conditionally negate to get x*Q 102 dest.CondNeg(int(xmask & 1)) 103} 104 105// Set dest to x*Q, where -8 <= x <= 8, in constant time. 106func (v *affineLookupTable) SelectInto(dest *affineCached, x int8) { 107 // Compute xabs = |x| 108 xmask := x >> 7 109 xabs := uint8((x + xmask) ^ xmask) 110 111 dest.Zero() 112 for j := 1; j <= 8; j++ { 113 // Set dest = j*Q if |x| = j 114 cond := subtle.ConstantTimeByteEq(xabs, uint8(j)) 115 dest.Select(&v.points[j-1], dest, cond) 116 } 117 // Now dest = |x|*Q, conditionally negate to get x*Q 118 dest.CondNeg(int(xmask & 1)) 119} 120 121// Given odd x with 0 < x < 2^4, return x*Q (in variable time). 122func (v *nafLookupTable5) SelectInto(dest *projCached, x int8) { 123 *dest = v.points[x/2] 124} 125 126// Given odd x with 0 < x < 2^7, return x*Q (in variable time). 127func (v *nafLookupTable8) SelectInto(dest *affineCached, x int8) { 128 *dest = v.points[x/2] 129} 130