tables.go

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