p224_sqrt.mx raw

   1  // Copyright 2022 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 nistec
   6  
   7  import (
   8  	"crypto/internal/fips140/nistec/fiat"
   9  	"sync"
  10  )
  11  
  12  var p224GG *[96]fiat.P224Element
  13  var p224GGOnce sync.Once
  14  
  15  // p224SqrtCandidate sets r to a square root candidate for x. r and x must not overlap.
  16  func p224SqrtCandidate(r, x *fiat.P224Element) {
  17  	// Since p = 1 mod 4, we can't use the exponentiation by (p + 1) / 4 like
  18  	// for the other primes. Instead, implement a variation of Tonelli–Shanks.
  19  	// The constant-time implementation is adapted from Thomas Pornin's ecGFp5.
  20  	//
  21  	// https://github.com/pornin/ecgfp5/blob/82325b965/rust/src/field.rs#L337-L385
  22  
  23  	// p = q*2^n + 1 with q odd -> q = 2^128 - 1 and n = 96
  24  	// g^(2^n) = 1 -> g = 11 ^ q (where 11 is the smallest non-square)
  25  	// GG[j] = g^(2^j) for j = 0 to n-1
  26  
  27  	p224GGOnce.Do(func() {
  28  		p224GG = &[96]fiat.P224Element{}
  29  		for i := range p224GG {
  30  			if i == 0 {
  31  				p224GG[i].SetBytes([]byte{0x6a, 0x0f, 0xec, 0x67,
  32  					0x85, 0x98, 0xa7, 0x92, 0x0c, 0x55, 0xb2, 0xd4,
  33  					0x0b, 0x2d, 0x6f, 0xfb, 0xbe, 0xa3, 0xd8, 0xce,
  34  					0xf3, 0xfb, 0x36, 0x32, 0xdc, 0x69, 0x1b, 0x74})
  35  			} else {
  36  				p224GG[i].Square(&p224GG[i-1])
  37  			}
  38  		}
  39  	})
  40  
  41  	// r <- x^((q+1)/2) = x^(2^127)
  42  	// v <- x^q = x^(2^128-1)
  43  
  44  	// Compute x^(2^127-1) first.
  45  	//
  46  	// The sequence of 10 multiplications and 126 squarings is derived from the
  47  	// following addition chain generated with github.com/mmcloughlin/addchain v0.4.0.
  48  	//
  49  	//	_10      = 2*1
  50  	//	_11      = 1 + _10
  51  	//	_110     = 2*_11
  52  	//	_111     = 1 + _110
  53  	//	_111000  = _111 << 3
  54  	//	_111111  = _111 + _111000
  55  	//	_1111110 = 2*_111111
  56  	//	_1111111 = 1 + _1111110
  57  	//	x12      = _1111110 << 5 + _111111
  58  	//	x24      = x12 << 12 + x12
  59  	//	i36      = x24 << 7
  60  	//	x31      = _1111111 + i36
  61  	//	x48      = i36 << 17 + x24
  62  	//	x96      = x48 << 48 + x48
  63  	//	return     x96 << 31 + x31
  64  	//
  65  	var t0 = &fiat.P224Element{}
  66  	var t1 = &fiat.P224Element{}
  67  
  68  	r.Square(x)
  69  	r.Mul(x, r)
  70  	r.Square(r)
  71  	r.Mul(x, r)
  72  	t0.Square(r)
  73  	for s := 1; s < 3; s++ {
  74  		t0.Square(t0)
  75  	}
  76  	t0.Mul(r, t0)
  77  	t1.Square(t0)
  78  	r.Mul(x, t1)
  79  	for s := 0; s < 5; s++ {
  80  		t1.Square(t1)
  81  	}
  82  	t0.Mul(t0, t1)
  83  	t1.Square(t0)
  84  	for s := 1; s < 12; s++ {
  85  		t1.Square(t1)
  86  	}
  87  	t0.Mul(t0, t1)
  88  	t1.Square(t0)
  89  	for s := 1; s < 7; s++ {
  90  		t1.Square(t1)
  91  	}
  92  	r.Mul(r, t1)
  93  	for s := 0; s < 17; s++ {
  94  		t1.Square(t1)
  95  	}
  96  	t0.Mul(t0, t1)
  97  	t1.Square(t0)
  98  	for s := 1; s < 48; s++ {
  99  		t1.Square(t1)
 100  	}
 101  	t0.Mul(t0, t1)
 102  	for s := 0; s < 31; s++ {
 103  		t0.Square(t0)
 104  	}
 105  	r.Mul(r, t0)
 106  
 107  	// v = x^(2^127-1)^2 * x
 108  	v := (&fiat.P224Element{}).Square(r)
 109  	v.Mul(v, x)
 110  
 111  	// r = x^(2^127-1) * x
 112  	r.Mul(r, x)
 113  
 114  	// for i = n-1 down to 1:
 115  	//     w = v^(2^(i-1))
 116  	//     if w == -1 then:
 117  	//         v <- v*GG[n-i]
 118  	//         r <- r*GG[n-i-1]
 119  
 120  	var p224MinusOne = (&fiat.P224Element{}).Sub(&fiat.P224Element{}, (&fiat.P224Element{}).One())
 121  
 122  	for i := 96 - 1; i >= 1; i-- {
 123  		w := (&fiat.P224Element{}).Set(v)
 124  		for j := 0; j < i-1; j++ {
 125  			w.Square(w)
 126  		}
 127  		cond := w.Equal(p224MinusOne)
 128  		v.Select(t0.Mul(v, &p224GG[96-i]), v, cond)
 129  		r.Select(t0.Mul(r, &p224GG[96-i-1]), r, cond)
 130  	}
 131  }
 132