curve.go

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

     1  package x448
     2  
     3  import (
     4  	fp "github.com/cloudflare/circl/math/fp448"
     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  	w[1] = fp.Elt{   // x1 = S
    13  		0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    14  		0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    15  		0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    16  		0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xff,
    17  		0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    18  		0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    19  		0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    20  	}
    21  	fp.SetOne(&w[2]) // z1 = 1
    22  	w[3] = fp.Elt{   // x2 = G-S
    23  		0x20, 0x27, 0x9d, 0xc9, 0x7d, 0x19, 0xb1, 0xac,
    24  		0xf8, 0xba, 0x69, 0x1c, 0xff, 0x33, 0xac, 0x23,
    25  		0x51, 0x1b, 0xce, 0x3a, 0x64, 0x65, 0xbd, 0xf1,
    26  		0x23, 0xf8, 0xc1, 0x84, 0x9d, 0x45, 0x54, 0x29,
    27  		0x67, 0xb9, 0x81, 0x1c, 0x03, 0xd1, 0xcd, 0xda,
    28  		0x7b, 0xeb, 0xff, 0x1a, 0x88, 0x03, 0xcf, 0x3a,
    29  		0x42, 0x44, 0x32, 0x01, 0x25, 0xb7, 0xfa, 0xf0,
    30  	}
    31  	fp.SetOne(&w[4]) // z2 = 1
    32  
    33  	const n = 448
    34  	const h = 2
    35  	swap := uint(1)
    36  	for s := 0; s < n-h; s++ {
    37  		i := (s + h) / 8
    38  		j := (s + h) % 8
    39  		bit := uint((k[i] >> uint(j)) & 1)
    40  		copy(w[0][:], tableGenerator[s*Size:(s+1)*Size])
    41  		diffAdd(&w, swap^bit)
    42  		swap = bit
    43  	}
    44  	for s := 0; s < h; s++ {
    45  		double(&w[1], &w[2])
    46  	}
    47  	toAffine((*[fp.Size]byte)(k), &w[1], &w[2])
    48  }
    49  
    50  // ladderMontgomery calculates a generic scalar point multiplication
    51  // The algorithm implemented is the left-to-right Montgomery's ladder.
    52  func ladderMontgomery(k, xP *Key) {
    53  	w := [5]fp.Elt{}      // [x1, x2, z2, x3, z3] order must be preserved.
    54  	w[0] = *(*fp.Elt)(xP) // x1 = xP
    55  	fp.SetOne(&w[1])      // x2 = 1
    56  	w[3] = *(*fp.Elt)(xP) // x3 = xP
    57  	fp.SetOne(&w[4])      // z3 = 1
    58  
    59  	move := uint(0)
    60  	for s := 448 - 1; s >= 0; s-- {
    61  		i := s / 8
    62  		j := s % 8
    63  		bit := uint((k[i] >> uint(j)) & 1)
    64  		ladderStep(&w, move^bit)
    65  		move = bit
    66  	}
    67  	toAffine((*[fp.Size]byte)(k), &w[1], &w[2])
    68  }
    69  
    70  func toAffine(k *[fp.Size]byte, x, z *fp.Elt) {
    71  	fp.Inv(z, z)
    72  	fp.Mul(x, x, z)
    73  	_ = fp.ToBytes(k[:], x)
    74  }
    75  
    76  var lowOrderPoints = [3]fp.Elt{
    77  	{ /* (0,_,1) point of order 2 on Curve448 */
    78  		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    79  		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    80  		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    81  		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    82  		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    83  		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    84  		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    85  	},
    86  	{ /* (1,_,1) a point of order 4 on the twist of Curve448 */
    87  		0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    88  		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    89  		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    90  		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    91  		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    92  		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    93  		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    94  	},
    95  	{ /* (-1,_,1) point of order 4 on Curve448 */
    96  		0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    97  		0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    98  		0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    99  		0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xff,
   100  		0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
   101  		0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
   102  		0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
   103  	},
   104  }
   105
View as plain text