csidh.go

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

     1  package csidh
     2  
     3  import (
     4  	"io"
     5  )
     6  
     7  // 511-bit number representing prime field element GF(p)
     8  type fp [numWords]uint64
     9  
    10  // Represents projective point on elliptic curve E over GF(p)
    11  type point struct {
    12  	x fp
    13  	z fp
    14  }
    15  
    16  // Curve coefficients
    17  type coeff struct {
    18  	a fp
    19  	c fp
    20  }
    21  
    22  type fpRngGen struct {
    23  	// working buffer needed to avoid memory allocation
    24  	wbuf [64]byte
    25  }
    26  
    27  // Defines operations on public key
    28  type PublicKey struct {
    29  	fpRngGen
    30  	// Montgomery coefficient A from GF(p) of the elliptic curve
    31  	// y^2 = x^3 + Ax^2 + x.
    32  	a fp
    33  }
    34  
    35  // Defines operations on private key
    36  type PrivateKey struct {
    37  	fpRngGen
    38  	// private key is a set of integers randomly
    39  	// each sampled from a range [-5, 5].
    40  	e [PrivateKeySize]int8
    41  }
    42  
    43  // randFp generates random element from Fp.
    44  func (s *fpRngGen) randFp(v *fp, rng io.Reader) {
    45  	mask := uint64(1<<(pbits%limbBitSize)) - 1
    46  	for {
    47  		*v = fp{}
    48  		_, err := io.ReadFull(rng, s.wbuf[:])
    49  		if err != nil {
    50  			panic("Can't read random number")
    51  		}
    52  
    53  		for i := 0; i < len(s.wbuf); i++ {
    54  			j := i / limbByteSize
    55  			k := uint(i % 8)
    56  			v[j] |= uint64(s.wbuf[i]) << (8 * k)
    57  		}
    58  
    59  		v[len(v)-1] &= mask
    60  		if isLess(v, &p) {
    61  			return
    62  		}
    63  	}
    64  }
    65  
    66  // cofactorMul helper implements batch cofactor multiplication as described
    67  // in the ia.cr/2018/383 (algo. 3). Returns tuple of two booleans, first indicates
    68  // if function has finished successfully. In case first return value is true,
    69  // second return value indicates if curve represented by cofactor 'a' is
    70  // supersingular.
    71  // Implementation uses divide-and-conquer strategy and recursion in order to
    72  // speed up calculation of Q_i = [(p+1)/l_i] * P.
    73  // Implementation is not constant time, but it operates on public data only.
    74  func cofactorMul(p *point, a *coeff, halfL, halfR int, order *fp) (bool, bool) {
    75  	var Q point
    76  	var r1, d1, r2, d2 bool
    77  	if (halfR - halfL) == 1 {
    78  		// base case
    79  		if !p.z.isZero() {
    80  			tmp := fp{primes[halfL]}
    81  			xMul(p, p, a, &tmp)
    82  
    83  			if !p.z.isZero() {
    84  				// order does not divide p+1 -> ordinary curve
    85  				return true, false
    86  			}
    87  
    88  			mul512(order, order, primes[halfL])
    89  			if isLess(&fourSqrtP, order) {
    90  				// order > 4*sqrt(p) -> supersingular curve
    91  				return true, true
    92  			}
    93  		}
    94  		return false, false
    95  	}
    96  
    97  	// perform another recursive step
    98  	mid := halfL + ((halfR - halfL + 1) / 2)
    99  	mulL, mulR := fp{1}, fp{1}
   100  	// compute u = primes_1 * ... * primes_m
   101  	for i := halfL; i < mid; i++ {
   102  		mul512(&mulR, &mulR, primes[i])
   103  	}
   104  	// compute v = primes_m+1 * ... * primes_n
   105  	for i := mid; i < halfR; i++ {
   106  		mul512(&mulL, &mulL, primes[i])
   107  	}
   108  
   109  	// calculate Q_i
   110  	xMul(&Q, p, a, &mulR)
   111  	xMul(p, p, a, &mulL)
   112  
   113  	d1, r1 = cofactorMul(&Q, a, mid, halfR, order)
   114  	d2, r2 = cofactorMul(p, a, halfL, mid, order)
   115  	return d1 || d2, r1 || r2
   116  }
   117  
   118  // groupAction evaluates group action of prv.e on a Montgomery
   119  // curve represented by coefficient pub.A.
   120  // This is implementation of algorithm 2 from ia.cr/2018/383.
   121  func groupAction(pub *PublicKey, prv *PrivateKey, rng io.Reader) {
   122  	var k [2]fp
   123  	var e [2][primeCount]uint8
   124  	done := [2]bool{false, false}
   125  	A := coeff{a: pub.a, c: one}
   126  
   127  	k[0][0] = 4
   128  	k[1][0] = 4
   129  
   130  	for i, v := range primes {
   131  		t := (prv.e[uint(i)>>1] << ((uint(i) % 2) * 4)) >> 4
   132  		if t > 0 {
   133  			e[0][i] = uint8(t)
   134  			e[1][i] = 0
   135  			mul512(&k[1], &k[1], v)
   136  		} else if t < 0 {
   137  			e[1][i] = uint8(-t)
   138  			e[0][i] = 0
   139  			mul512(&k[0], &k[0], v)
   140  		} else {
   141  			e[0][i] = 0
   142  			e[1][i] = 0
   143  			mul512(&k[0], &k[0], v)
   144  			mul512(&k[1], &k[1], v)
   145  		}
   146  	}
   147  
   148  	for {
   149  		var P point
   150  		var rhs fp
   151  		prv.randFp(&P.x, rng)
   152  		P.z = one
   153  		montEval(&rhs, &A.a, &P.x)
   154  		sign := rhs.isNonQuadRes()
   155  
   156  		if done[sign] {
   157  			continue
   158  		}
   159  
   160  		xMul(&P, &P, &A, &k[sign])
   161  		done[sign] = true
   162  
   163  		for i, v := range primes {
   164  			if e[sign][i] != 0 {
   165  				cof := fp{1}
   166  				var K point
   167  
   168  				for j := i + 1; j < len(primes); j++ {
   169  					if e[sign][j] != 0 {
   170  						mul512(&cof, &cof, primes[j])
   171  					}
   172  				}
   173  
   174  				xMul(&K, &P, &A, &cof)
   175  				if !K.z.isZero() {
   176  					xIso(&P, &A, &K, v)
   177  					e[sign][i] = e[sign][i] - 1
   178  					if e[sign][i] == 0 {
   179  						mul512(&k[sign], &k[sign], primes[i])
   180  					}
   181  				}
   182  			}
   183  			done[sign] = done[sign] && (e[sign][i] == 0)
   184  		}
   185  
   186  		modExpRdc512(&A.c, &A.c, &pMin1)
   187  		mulRdc(&A.a, &A.a, &A.c)
   188  		A.c = one
   189  
   190  		if done[0] && done[1] {
   191  			break
   192  		}
   193  	}
   194  	pub.a = A.a
   195  }
   196  
   197  // PrivateKey operations
   198  
   199  func (c *PrivateKey) Import(key []byte) bool {
   200  	if len(key) < len(c.e) {
   201  		return false
   202  	}
   203  	for i, v := range key {
   204  		c.e[i] = int8(v)
   205  	}
   206  	return true
   207  }
   208  
   209  func (c PrivateKey) Export(out []byte) bool {
   210  	if len(out) < len(c.e) {
   211  		return false
   212  	}
   213  	for i, v := range c.e {
   214  		out[i] = byte(v)
   215  	}
   216  	return true
   217  }
   218  
   219  func GeneratePrivateKey(key *PrivateKey, rng io.Reader) error {
   220  	for i := range key.e {
   221  		key.e[i] = 0
   222  	}
   223  
   224  	for i := 0; i < len(primes); {
   225  		_, err := io.ReadFull(rng, key.wbuf[:])
   226  		if err != nil {
   227  			return err
   228  		}
   229  
   230  		for j := range key.wbuf {
   231  			if int8(key.wbuf[j]) <= expMax && int8(key.wbuf[j]) >= -expMax {
   232  				key.e[i>>1] |= int8((key.wbuf[j] & 0xF) << uint((i%2)*4))
   233  				i = i + 1
   234  				if i == len(primes) {
   235  					break
   236  				}
   237  			}
   238  		}
   239  	}
   240  	return nil
   241  }
   242  
   243  // Public key operations
   244  
   245  // reset removes key material from PublicKey.
   246  func (c *PublicKey) reset() {
   247  	for i := range c.a {
   248  		c.a[i] = 0
   249  	}
   250  }
   251  
   252  // Assumes key is in Montgomery domain.
   253  func (c *PublicKey) Import(key []byte) bool {
   254  	if len(key) != numWords*limbByteSize {
   255  		return false
   256  	}
   257  	for i := 0; i < len(key); i++ {
   258  		j := i / limbByteSize
   259  		k := uint64(i % 8)
   260  		c.a[j] |= uint64(key[i]) << (8 * k)
   261  	}
   262  	return true
   263  }
   264  
   265  // Assumes key is exported as encoded in Montgomery domain.
   266  func (c *PublicKey) Export(out []byte) bool {
   267  	if len(out) != numWords*limbByteSize {
   268  		return false
   269  	}
   270  	for i := 0; i < len(out); i++ {
   271  		j := i / limbByteSize
   272  		k := uint64(i % 8)
   273  		out[i] = byte(c.a[j] >> (8 * k))
   274  	}
   275  	return true
   276  }
   277  
   278  func GeneratePublicKey(pub *PublicKey, prv *PrivateKey, rng io.Reader) {
   279  	pub.reset()
   280  	groupAction(pub, prv, rng)
   281  }
   282  
   283  // Validate returns true if 'pub' is a valid cSIDH public key,
   284  // otherwise false.
   285  // More precisely, the function verifies that curve
   286  //
   287  //	y^2 = x^3 + pub.a * x^2 + x
   288  //
   289  // is supersingular.
   290  func Validate(pub *PublicKey, rng io.Reader) bool {
   291  	// Check if in range
   292  	if !isLess(&pub.a, &p) {
   293  		return false
   294  	}
   295  
   296  	// Check if pub represents a smooth Montgomery curve.
   297  	if pub.a.equal(&two) || pub.a.equal(&twoNeg) {
   298  		return false
   299  	}
   300  
   301  	// Check if pub represents a supersingular curve.
   302  	for {
   303  		var P point
   304  		A := point{pub.a, one}
   305  
   306  		// Randomly chosen P must have big enough order to check
   307  		// supersingularity. Probability of random P having big
   308  		// enough order is very high, as proven by W.Castryck et
   309  		// al. (ia.cr/2018/383, ch 5)
   310  		pub.randFp(&P.x, rng)
   311  		P.z = one
   312  
   313  		xDbl(&P, &P, &A)
   314  		xDbl(&P, &P, &A)
   315  
   316  		done, res := cofactorMul(&P, &coeff{A.x, A.z}, 0, len(primes), &fp{1})
   317  		if done {
   318  			return res
   319  		}
   320  	}
   321  }
   322  
   323  // DeriveSecret computes a cSIDH shared secret. If successful, returns true
   324  // and fills 'out' with shared secret. Function returns false in case 'pub' is invalid.
   325  // More precisely, shared secret is a Montgomery coefficient A of a secret
   326  // curve y^2 = x^3 + Ax^2 + x, computed by applying action of a prv.e
   327  // on a curve represented by pub.a.
   328  func DeriveSecret(out *[64]byte, pub *PublicKey, prv *PrivateKey, rng io.Reader) bool {
   329  	if !Validate(pub, rng) {
   330  		return false
   331  	}
   332  	groupAction(pub, prv, rng)
   333  	pub.Export(out[:])
   334  	return true
   335  }
   336
View as plain text