exp.go raw

   1  package gnarl
   2  
   3  // Exponentiation routines for torus matrices (tmat) and full matrices (mat4).
   4  //
   5  // Fixed-base exponentiation uses a precomputed table for the Schnorr generator.
   6  // 54 windows of 4 bits each (ceil(213/4) = 54 for the ~213-bit scalar Q).
   7  //
   8  // Variable-base uses square-and-multiply.
   9  // Shamir's trick computes G^a * PK^b in one pass for verification.
  10  
  11  // genTable holds precomputed multiples of the Schnorr generator.
  12  // genTable[i][j] = SchnorrGen^(j * 2^(4*i)) for j = 0..15, i = 0..53.
  13  var genTable [54][16]tmat
  14  
  15  var genTableReady bool
  16  
  17  // initGenTable precomputes the fixed-base table for SchnorrGen.
  18  func initGenTable(g *tmat) {
  19  	if genTableReady {
  20  		return
  21  	}
  22  
  23  	genTable[0][0] = tmEye()
  24  	genTable[0][1] = *g
  25  	for j := 2; j < 16; j++ {
  26  		tmMul(&genTable[0][j], &genTable[0][j-1], g)
  27  	}
  28  
  29  	for i := 1; i < 54; i++ {
  30  		var base tmat
  31  		tmSquare(&base, &genTable[i-1][1])
  32  		tmSquare(&base, &base)
  33  		tmSquare(&base, &base)
  34  		tmSquare(&base, &base)
  35  
  36  		genTable[i][0] = tmEye()
  37  		genTable[i][1] = base
  38  		for j := 2; j < 16; j++ {
  39  			tmMul(&genTable[i][j], &genTable[i][j-1], &base)
  40  		}
  41  	}
  42  
  43  	genTableReady = true
  44  }
  45  
  46  // tmFixedExp computes r = SchnorrGen^s using the precomputed table.
  47  // Processes 54 4-bit windows covering the ~213-bit scalar.
  48  func tmFixedExp(r *tmat, s *scalar) {
  49  	*r = tmEye()
  50  
  51  	for i := 0; i < 54; i++ {
  52  		limb := i / 16
  53  		bit := uint((i % 16) * 4)
  54  		nib := int((s[limb] >> bit) & 0xF)
  55  
  56  		if nib != 0 {
  57  			tmMul(r, r, &genTable[i][nib])
  58  		}
  59  	}
  60  }
  61  
  62  // tmVarExp computes r = base^s for a variable torus matrix.
  63  func tmVarExp(r *tmat, base *tmat, s *scalar) {
  64  	*r = tmEye()
  65  	var b tmat
  66  	b = *base
  67  
  68  	for i := 0; i < 4; i++ {
  69  		word := s[i]
  70  		for bit := 0; bit < 64; bit++ {
  71  			if word&1 == 1 {
  72  				tmMul(r, r, &b)
  73  			}
  74  			tmSquare(&b, &b)
  75  			word >>= 1
  76  		}
  77  	}
  78  }
  79  
  80  // tmShamirExp computes r = G^a * PK^b where G is the fixed SchnorrGen
  81  // and PK is a variable torus matrix.
  82  //
  83  // Uses separate 4-bit windows with Horner's method (top-down).
  84  func tmShamirExp(r *tmat, a *scalar, pk *tmat, b *scalar) {
  85  	var pkTab [16]tmat
  86  	pkTab[0] = tmEye()
  87  	pkTab[1] = *pk
  88  	for j := 2; j < 16; j++ {
  89  		tmMul(&pkTab[j], &pkTab[j-1], pk)
  90  	}
  91  
  92  	*r = tmEye()
  93  
  94  	for i := 53; i >= 0; i-- {
  95  		tmSquare(r, r)
  96  		tmSquare(r, r)
  97  		tmSquare(r, r)
  98  		tmSquare(r, r)
  99  
 100  		limb := i / 16
 101  		bit := uint((i % 16) * 4)
 102  		nibA := int((a[limb] >> bit) & 0xF)
 103  		nibB := int((b[limb] >> bit) & 0xF)
 104  
 105  		if nibA != 0 {
 106  			tmMul(r, r, &genTable[0][nibA])
 107  		}
 108  		if nibB != 0 {
 109  			tmMul(r, r, &pkTab[nibB])
 110  		}
 111  	}
 112  }
 113