modular.go

Documentation: github.com/cloudflare/circl/sign/ed25519

     1  package ed25519
     2  
     3  import (
     4  	"encoding/binary"
     5  	"math/bits"
     6  )
     7  
     8  var order = [paramB]byte{
     9  	0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58,
    10  	0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14,
    11  	0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    12  	0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10,
    13  }
    14  
    15  // isLessThan returns true if 0 <= x < y, and assumes that slices have the same length.
    16  func isLessThan(x, y []byte) bool {
    17  	i := len(x) - 1
    18  	for i > 0 && x[i] == y[i] {
    19  		i--
    20  	}
    21  	return x[i] < y[i]
    22  }
    23  
    24  // reduceModOrder calculates k = k mod order of the curve.
    25  func reduceModOrder(k []byte, is512Bit bool) {
    26  	var X [((2 * paramB) * 8) / 64]uint64
    27  	numWords := len(k) >> 3
    28  	for i := 0; i < numWords; i++ {
    29  		X[i] = binary.LittleEndian.Uint64(k[i*8 : (i+1)*8])
    30  	}
    31  	red512(&X, is512Bit)
    32  	for i := 0; i < numWords; i++ {
    33  		binary.LittleEndian.PutUint64(k[i*8:(i+1)*8], X[i])
    34  	}
    35  }
    36  
    37  // red512 calculates x = x mod Order of the curve.
    38  func red512(x *[8]uint64, full bool) {
    39  	// Implementation of Algs.(14.47)+(14.52) of Handbook of Applied
    40  	// Cryptography, by A. Menezes, P. van Oorschot, and S. Vanstone.
    41  	const (
    42  		ell0   = uint64(0x5812631a5cf5d3ed)
    43  		ell1   = uint64(0x14def9dea2f79cd6)
    44  		ell160 = uint64(0x812631a5cf5d3ed0)
    45  		ell161 = uint64(0x4def9dea2f79cd65)
    46  		ell162 = uint64(0x0000000000000001)
    47  	)
    48  
    49  	var c0, c1, c2, c3 uint64
    50  	r0, r1, r2, r3, r4 := x[0], x[1], x[2], x[3], uint64(0)
    51  
    52  	if full {
    53  		q0, q1, q2, q3 := x[4], x[5], x[6], x[7]
    54  
    55  		for i := 0; i < 3; i++ {
    56  			h0, s0 := bits.Mul64(q0, ell160)
    57  			h1, s1 := bits.Mul64(q1, ell160)
    58  			h2, s2 := bits.Mul64(q2, ell160)
    59  			h3, s3 := bits.Mul64(q3, ell160)
    60  
    61  			s1, c0 = bits.Add64(h0, s1, 0)
    62  			s2, c1 = bits.Add64(h1, s2, c0)
    63  			s3, c2 = bits.Add64(h2, s3, c1)
    64  			s4, _ := bits.Add64(h3, 0, c2)
    65  
    66  			h0, l0 := bits.Mul64(q0, ell161)
    67  			h1, l1 := bits.Mul64(q1, ell161)
    68  			h2, l2 := bits.Mul64(q2, ell161)
    69  			h3, l3 := bits.Mul64(q3, ell161)
    70  
    71  			l1, c0 = bits.Add64(h0, l1, 0)
    72  			l2, c1 = bits.Add64(h1, l2, c0)
    73  			l3, c2 = bits.Add64(h2, l3, c1)
    74  			l4, _ := bits.Add64(h3, 0, c2)
    75  
    76  			s1, c0 = bits.Add64(s1, l0, 0)
    77  			s2, c1 = bits.Add64(s2, l1, c0)
    78  			s3, c2 = bits.Add64(s3, l2, c1)
    79  			s4, c3 = bits.Add64(s4, l3, c2)
    80  			s5, s6 := bits.Add64(l4, 0, c3)
    81  
    82  			s2, c0 = bits.Add64(s2, q0, 0)
    83  			s3, c1 = bits.Add64(s3, q1, c0)
    84  			s4, c2 = bits.Add64(s4, q2, c1)
    85  			s5, c3 = bits.Add64(s5, q3, c2)
    86  			s6, s7 := bits.Add64(s6, 0, c3)
    87  
    88  			q := q0 | q1 | q2 | q3
    89  			m := -((q | -q) >> 63) // if q=0 then m=0...0 else m=1..1
    90  			s0 &= m
    91  			s1 &= m
    92  			s2 &= m
    93  			s3 &= m
    94  			q0, q1, q2, q3 = s4, s5, s6, s7
    95  
    96  			if (i+1)%2 == 0 {
    97  				r0, c0 = bits.Add64(r0, s0, 0)
    98  				r1, c1 = bits.Add64(r1, s1, c0)
    99  				r2, c2 = bits.Add64(r2, s2, c1)
   100  				r3, c3 = bits.Add64(r3, s3, c2)
   101  				r4, _ = bits.Add64(r4, 0, c3)
   102  			} else {
   103  				r0, c0 = bits.Sub64(r0, s0, 0)
   104  				r1, c1 = bits.Sub64(r1, s1, c0)
   105  				r2, c2 = bits.Sub64(r2, s2, c1)
   106  				r3, c3 = bits.Sub64(r3, s3, c2)
   107  				r4, _ = bits.Sub64(r4, 0, c3)
   108  			}
   109  		}
   110  
   111  		m := -(r4 >> 63)
   112  		r0, c0 = bits.Add64(r0, m&ell160, 0)
   113  		r1, c1 = bits.Add64(r1, m&ell161, c0)
   114  		r2, c2 = bits.Add64(r2, m&ell162, c1)
   115  		r3, c3 = bits.Add64(r3, 0, c2)
   116  		r4, _ = bits.Add64(r4, m&1, c3)
   117  		x[4], x[5], x[6], x[7] = 0, 0, 0, 0
   118  	}
   119  
   120  	q0 := (r4 << 4) | (r3 >> 60)
   121  	r3 &= (uint64(1) << 60) - 1
   122  
   123  	h0, s0 := bits.Mul64(ell0, q0)
   124  	h1, s1 := bits.Mul64(ell1, q0)
   125  	s1, c0 = bits.Add64(h0, s1, 0)
   126  	s2, _ := bits.Add64(h1, 0, c0)
   127  
   128  	r0, c0 = bits.Sub64(r0, s0, 0)
   129  	r1, c1 = bits.Sub64(r1, s1, c0)
   130  	r2, c2 = bits.Sub64(r2, s2, c1)
   131  	r3, _ = bits.Sub64(r3, 0, c2)
   132  
   133  	x[0], x[1], x[2], x[3] = r0, r1, r2, r3
   134  }
   135  
   136  // calculateS performs s = r+k*a mod Order of the curve.
   137  func calculateS(s, r, k, a []byte) {
   138  	K := [4]uint64{
   139  		binary.LittleEndian.Uint64(k[0*8 : 1*8]),
   140  		binary.LittleEndian.Uint64(k[1*8 : 2*8]),
   141  		binary.LittleEndian.Uint64(k[2*8 : 3*8]),
   142  		binary.LittleEndian.Uint64(k[3*8 : 4*8]),
   143  	}
   144  	S := [8]uint64{
   145  		binary.LittleEndian.Uint64(r[0*8 : 1*8]),
   146  		binary.LittleEndian.Uint64(r[1*8 : 2*8]),
   147  		binary.LittleEndian.Uint64(r[2*8 : 3*8]),
   148  		binary.LittleEndian.Uint64(r[3*8 : 4*8]),
   149  	}
   150  	var c3 uint64
   151  	for i := range K {
   152  		ai := binary.LittleEndian.Uint64(a[i*8 : (i+1)*8])
   153  
   154  		h0, l0 := bits.Mul64(K[0], ai)
   155  		h1, l1 := bits.Mul64(K[1], ai)
   156  		h2, l2 := bits.Mul64(K[2], ai)
   157  		h3, l3 := bits.Mul64(K[3], ai)
   158  
   159  		l1, c0 := bits.Add64(h0, l1, 0)
   160  		l2, c1 := bits.Add64(h1, l2, c0)
   161  		l3, c2 := bits.Add64(h2, l3, c1)
   162  		l4, _ := bits.Add64(h3, 0, c2)
   163  
   164  		S[i+0], c0 = bits.Add64(S[i+0], l0, 0)
   165  		S[i+1], c1 = bits.Add64(S[i+1], l1, c0)
   166  		S[i+2], c2 = bits.Add64(S[i+2], l2, c1)
   167  		S[i+3], c3 = bits.Add64(S[i+3], l3, c2)
   168  		S[i+4], _ = bits.Add64(S[i+4], l4, c3)
   169  	}
   170  	red512(&S, true)
   171  	binary.LittleEndian.PutUint64(s[0*8:1*8], S[0])
   172  	binary.LittleEndian.PutUint64(s[1*8:2*8], S[1])
   173  	binary.LittleEndian.PutUint64(s[2*8:3*8], S[2])
   174  	binary.LittleEndian.PutUint64(s[3*8:4*8], S[3])
   175  }
   176
View as plain text