curve.go

Documentation: github.com/cloudflare/circl/dh/x25519

     1  package x25519
     2  
     3  import (
     4  	fp "github.com/cloudflare/circl/math/fp25519"
     5  )
     6  
     7  // ladderJoye calculates a fixed-point multiplication with the generator point.
     8  // The algorithm is the right-to-left Joye's ladder as described
     9  // in "How to precompute a ladder" in SAC'2017.
    10  func ladderJoye(k *Key) {
    11  	w := [5]fp.Elt{} // [mu,x1,z1,x2,z2] order must be preserved.
    12  	fp.SetOne(&w[1]) // x1 = 1
    13  	fp.SetOne(&w[2]) // z1 = 1
    14  	w[3] = fp.Elt{   // x2 = G-S
    15  		0xbd, 0xaa, 0x2f, 0xc8, 0xfe, 0xe1, 0x94, 0x7e,
    16  		0xf8, 0xed, 0xb2, 0x14, 0xae, 0x95, 0xf0, 0xbb,
    17  		0xe2, 0x48, 0x5d, 0x23, 0xb9, 0xa0, 0xc7, 0xad,
    18  		0x34, 0xab, 0x7c, 0xe2, 0xee, 0xcd, 0xae, 0x1e,
    19  	}
    20  	fp.SetOne(&w[4]) // z2 = 1
    21  
    22  	const n = 255
    23  	const h = 3
    24  	swap := uint(1)
    25  	for s := 0; s < n-h; s++ {
    26  		i := (s + h) / 8
    27  		j := (s + h) % 8
    28  		bit := uint((k[i] >> uint(j)) & 1)
    29  		copy(w[0][:], tableGenerator[s*Size:(s+1)*Size])
    30  		diffAdd(&w, swap^bit)
    31  		swap = bit
    32  	}
    33  	for s := 0; s < h; s++ {
    34  		double(&w[1], &w[2])
    35  	}
    36  	toAffine((*[fp.Size]byte)(k), &w[1], &w[2])
    37  }
    38  
    39  // ladderMontgomery calculates a generic scalar point multiplication
    40  // The algorithm implemented is the left-to-right Montgomery's ladder.
    41  func ladderMontgomery(k, xP *Key) {
    42  	w := [5]fp.Elt{}      // [x1, x2, z2, x3, z3] order must be preserved.
    43  	w[0] = *(*fp.Elt)(xP) // x1 = xP
    44  	fp.SetOne(&w[1])      // x2 = 1
    45  	w[3] = *(*fp.Elt)(xP) // x3 = xP
    46  	fp.SetOne(&w[4])      // z3 = 1
    47  
    48  	move := uint(0)
    49  	for s := 255 - 1; s >= 0; s-- {
    50  		i := s / 8
    51  		j := s % 8
    52  		bit := uint((k[i] >> uint(j)) & 1)
    53  		ladderStep(&w, move^bit)
    54  		move = bit
    55  	}
    56  	toAffine((*[fp.Size]byte)(k), &w[1], &w[2])
    57  }
    58  
    59  func toAffine(k *[fp.Size]byte, x, z *fp.Elt) {
    60  	fp.Inv(z, z)
    61  	fp.Mul(x, x, z)
    62  	_ = fp.ToBytes(k[:], x)
    63  }
    64  
    65  var lowOrderPoints = [5]fp.Elt{
    66  	{ /* (0,_,1) point of order 2 on Curve25519 */
    67  		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    68  		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    69  		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    70  		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    71  	},
    72  	{ /* (1,_,1) point of order 4 on Curve25519 */
    73  		0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    74  		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    75  		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    76  		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    77  	},
    78  	{ /* (x,_,1) first point of order 8 on Curve25519 */
    79  		0xe0, 0xeb, 0x7a, 0x7c, 0x3b, 0x41, 0xb8, 0xae,
    80  		0x16, 0x56, 0xe3, 0xfa, 0xf1, 0x9f, 0xc4, 0x6a,
    81  		0xda, 0x09, 0x8d, 0xeb, 0x9c, 0x32, 0xb1, 0xfd,
    82  		0x86, 0x62, 0x05, 0x16, 0x5f, 0x49, 0xb8, 0x00,
    83  	},
    84  	{ /* (x,_,1) second point of order 8 on Curve25519 */
    85  		0x5f, 0x9c, 0x95, 0xbc, 0xa3, 0x50, 0x8c, 0x24,
    86  		0xb1, 0xd0, 0xb1, 0x55, 0x9c, 0x83, 0xef, 0x5b,
    87  		0x04, 0x44, 0x5c, 0xc4, 0x58, 0x1c, 0x8e, 0x86,
    88  		0xd8, 0x22, 0x4e, 0xdd, 0xd0, 0x9f, 0x11, 0x57,
    89  	},
    90  	{ /* (-1,_,1) a point of order 4 on the twist of Curve25519 */
    91  		0xec, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    92  		0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    93  		0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    94  		0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f,
    95  	},
    96  }
    97
View as plain text