scalarmult.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 "sync"
     8  
     9  // basepointTable is a set of 32 affineLookupTables, where table i is generated
    10  // from 256i * basepoint. It is precomputed the first time it's used.
    11  func basepointTable() *[32]affineLookupTable {
    12  	basepointTablePrecomp.initOnce.Do(func() {
    13  		p := NewGeneratorPoint()
    14  		for i := 0; i < 32; i++ {
    15  			basepointTablePrecomp.table[i].FromP3(p)
    16  			for j := 0; j < 8; j++ {
    17  				p.Add(p, p)
    18  			}
    19  		}
    20  	})
    21  	return &basepointTablePrecomp.table
    22  }
    23  
    24  var basepointTablePrecomp struct {
    25  	table    [32]affineLookupTable
    26  	initOnce sync.Once
    27  }
    28  
    29  // ScalarBaseMult sets v = x * B, where B is the canonical generator, and
    30  // returns v.
    31  //
    32  // The scalar multiplication is done in constant time.
    33  func (v *Point) ScalarBaseMult(x *Scalar) *Point {
    34  	basepointTable := basepointTable()
    35  
    36  	// Write x = sum(x_i * 16^i) so  x*B = sum( B*x_i*16^i )
    37  	// as described in the Ed25519 paper
    38  	//
    39  	// Group even and odd coefficients
    40  	// x*B     = x_0*16^0*B + x_2*16^2*B + ... + x_62*16^62*B
    41  	//         + x_1*16^1*B + x_3*16^3*B + ... + x_63*16^63*B
    42  	// x*B     = x_0*16^0*B + x_2*16^2*B + ... + x_62*16^62*B
    43  	//    + 16*( x_1*16^0*B + x_3*16^2*B + ... + x_63*16^62*B)
    44  	//
    45  	// We use a lookup table for each i to get x_i*16^(2*i)*B
    46  	// and do four doublings to multiply by 16.
    47  	digits := x.signedRadix16()
    48  
    49  	multiple := &affineCached{}
    50  	tmp1 := &projP1xP1{}
    51  	tmp2 := &projP2{}
    52  
    53  	// Accumulate the odd components first
    54  	v.Set(NewIdentityPoint())
    55  	for i := 1; i < 64; i += 2 {
    56  		basepointTable[i/2].SelectInto(multiple, digits[i])
    57  		tmp1.AddAffine(v, multiple)
    58  		v.fromP1xP1(tmp1)
    59  	}
    60  
    61  	// Multiply by 16
    62  	tmp2.FromP3(v)       // tmp2 =    v in P2 coords
    63  	tmp1.Double(tmp2)    // tmp1 =  2*v in P1xP1 coords
    64  	tmp2.FromP1xP1(tmp1) // tmp2 =  2*v in P2 coords
    65  	tmp1.Double(tmp2)    // tmp1 =  4*v in P1xP1 coords
    66  	tmp2.FromP1xP1(tmp1) // tmp2 =  4*v in P2 coords
    67  	tmp1.Double(tmp2)    // tmp1 =  8*v in P1xP1 coords
    68  	tmp2.FromP1xP1(tmp1) // tmp2 =  8*v in P2 coords
    69  	tmp1.Double(tmp2)    // tmp1 = 16*v in P1xP1 coords
    70  	v.fromP1xP1(tmp1)    // now v = 16*(odd components)
    71  
    72  	// Accumulate the even components
    73  	for i := 0; i < 64; i += 2 {
    74  		basepointTable[i/2].SelectInto(multiple, digits[i])
    75  		tmp1.AddAffine(v, multiple)
    76  		v.fromP1xP1(tmp1)
    77  	}
    78  
    79  	return v
    80  }
    81  
    82  // ScalarMult sets v = x * q, and returns v.
    83  //
    84  // The scalar multiplication is done in constant time.
    85  func (v *Point) ScalarMult(x *Scalar, q *Point) *Point {
    86  	checkInitialized(q)
    87  
    88  	var table projLookupTable
    89  	table.FromP3(q)
    90  
    91  	// Write x = sum(x_i * 16^i)
    92  	// so  x*Q = sum( Q*x_i*16^i )
    93  	//         = Q*x_0 + 16*(Q*x_1 + 16*( ... + Q*x_63) ... )
    94  	//           <------compute inside out---------
    95  	//
    96  	// We use the lookup table to get the x_i*Q values
    97  	// and do four doublings to compute 16*Q
    98  	digits := x.signedRadix16()
    99  
   100  	// Unwrap first loop iteration to save computing 16*identity
   101  	multiple := &projCached{}
   102  	tmp1 := &projP1xP1{}
   103  	tmp2 := &projP2{}
   104  	table.SelectInto(multiple, digits[63])
   105  
   106  	v.Set(NewIdentityPoint())
   107  	tmp1.Add(v, multiple) // tmp1 = x_63*Q in P1xP1 coords
   108  	for i := 62; i >= 0; i-- {
   109  		tmp2.FromP1xP1(tmp1) // tmp2 =    (prev) in P2 coords
   110  		tmp1.Double(tmp2)    // tmp1 =  2*(prev) in P1xP1 coords
   111  		tmp2.FromP1xP1(tmp1) // tmp2 =  2*(prev) in P2 coords
   112  		tmp1.Double(tmp2)    // tmp1 =  4*(prev) in P1xP1 coords
   113  		tmp2.FromP1xP1(tmp1) // tmp2 =  4*(prev) in P2 coords
   114  		tmp1.Double(tmp2)    // tmp1 =  8*(prev) in P1xP1 coords
   115  		tmp2.FromP1xP1(tmp1) // tmp2 =  8*(prev) in P2 coords
   116  		tmp1.Double(tmp2)    // tmp1 = 16*(prev) in P1xP1 coords
   117  		v.fromP1xP1(tmp1)    //    v = 16*(prev) in P3 coords
   118  		table.SelectInto(multiple, digits[i])
   119  		tmp1.Add(v, multiple) // tmp1 = x_i*Q + 16*(prev) in P1xP1 coords
   120  	}
   121  	v.fromP1xP1(tmp1)
   122  	return v
   123  }
   124  
   125  // basepointNafTable is the nafLookupTable8 for the basepoint.
   126  // It is precomputed the first time it's used.
   127  func basepointNafTable() *nafLookupTable8 {
   128  	basepointNafTablePrecomp.initOnce.Do(func() {
   129  		basepointNafTablePrecomp.table.FromP3(NewGeneratorPoint())
   130  	})
   131  	return &basepointNafTablePrecomp.table
   132  }
   133  
   134  var basepointNafTablePrecomp struct {
   135  	table    nafLookupTable8
   136  	initOnce sync.Once
   137  }
   138  
   139  // VarTimeDoubleScalarBaseMult sets v = a * A + b * B, where B is the canonical
   140  // generator, and returns v.
   141  //
   142  // Execution time depends on the inputs.
   143  func (v *Point) VarTimeDoubleScalarBaseMult(a *Scalar, A *Point, b *Scalar) *Point {
   144  	checkInitialized(A)
   145  
   146  	// Similarly to the single variable-base approach, we compute
   147  	// digits and use them with a lookup table.  However, because
   148  	// we are allowed to do variable-time operations, we don't
   149  	// need constant-time lookups or constant-time digit
   150  	// computations.
   151  	//
   152  	// So we use a non-adjacent form of some width w instead of
   153  	// radix 16.  This is like a binary representation (one digit
   154  	// for each binary place) but we allow the digits to grow in
   155  	// magnitude up to 2^{w-1} so that the nonzero digits are as
   156  	// sparse as possible.  Intuitively, this "condenses" the
   157  	// "mass" of the scalar onto sparse coefficients (meaning
   158  	// fewer additions).
   159  
   160  	basepointNafTable := basepointNafTable()
   161  	var aTable nafLookupTable5
   162  	aTable.FromP3(A)
   163  	// Because the basepoint is fixed, we can use a wider NAF
   164  	// corresponding to a bigger table.
   165  	aNaf := a.nonAdjacentForm(5)
   166  	bNaf := b.nonAdjacentForm(8)
   167  
   168  	// Find the first nonzero coefficient.
   169  	i := 255
   170  	for j := i; j >= 0; j-- {
   171  		if aNaf[j] != 0 || bNaf[j] != 0 {
   172  			break
   173  		}
   174  	}
   175  
   176  	multA := &projCached{}
   177  	multB := &affineCached{}
   178  	tmp1 := &projP1xP1{}
   179  	tmp2 := &projP2{}
   180  	tmp2.Zero()
   181  
   182  	// Move from high to low bits, doubling the accumulator
   183  	// at each iteration and checking whether there is a nonzero
   184  	// coefficient to look up a multiple of.
   185  	for ; i >= 0; i-- {
   186  		tmp1.Double(tmp2)
   187  
   188  		// Only update v if we have a nonzero coeff to add in.
   189  		if aNaf[i] > 0 {
   190  			v.fromP1xP1(tmp1)
   191  			aTable.SelectInto(multA, aNaf[i])
   192  			tmp1.Add(v, multA)
   193  		} else if aNaf[i] < 0 {
   194  			v.fromP1xP1(tmp1)
   195  			aTable.SelectInto(multA, -aNaf[i])
   196  			tmp1.Sub(v, multA)
   197  		}
   198  
   199  		if bNaf[i] > 0 {
   200  			v.fromP1xP1(tmp1)
   201  			basepointNafTable.SelectInto(multB, bNaf[i])
   202  			tmp1.AddAffine(v, multB)
   203  		} else if bNaf[i] < 0 {
   204  			v.fromP1xP1(tmp1)
   205  			basepointNafTable.SelectInto(multB, -bNaf[i])
   206  			tmp1.SubAffine(v, multB)
   207  		}
   208  
   209  		tmp2.FromP1xP1(tmp1)
   210  	}
   211  
   212  	v.fromP2(tmp2)
   213  	return v
   214  }
   215
View as plain text