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 (
     8  	"crypto/subtle"
     9  )
    10  
    11  // A dynamic lookup table for variable-base, constant-time scalar muls.
    12  type projLookupTable struct {
    13  	points [8]projCached
    14  }
    15  
    16  // A precomputed lookup table for fixed-base, constant-time scalar muls.
    17  type affineLookupTable struct {
    18  	points [8]affineCached
    19  }
    20  
    21  // A dynamic lookup table for variable-base, variable-time scalar muls.
    22  type nafLookupTable5 struct {
    23  	points [8]projCached
    24  }
    25  
    26  // A precomputed lookup table for fixed-base, variable-time scalar muls.
    27  type nafLookupTable8 struct {
    28  	points [64]affineCached
    29  }
    30  
    31  // Constructors.
    32  
    33  // Builds a lookup table at runtime. Fast.
    34  func (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.
    49  func (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.
    62  func (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.
    76  func (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.
    90  func (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.
   106  func (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).
   122  func (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).
   127  func (v *nafLookupTable8) SelectInto(dest *affineCached, x int8) {
   128  	*dest = v.points[x/2]
   129  }
   130
View as plain text