exp.mx 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  func initGenTable(g *tmat) {
  18  	if genTableReady {
  19  		return
  20  	}
  21  
  22  	genTable[0][0] = tmEye()
  23  	genTable[0][1] = *g
  24  	for j := int32(2); j < 16; j++ {
  25  		tmMul(&genTable[0][j], &genTable[0][j-1], g)
  26  	}
  27  
  28  	for i := int32(1); i < 54; i++ {
  29  		var base tmat
  30  		tmSquare(&base, &genTable[i-1][1])
  31  		tmSquare(&base, &base)
  32  		tmSquare(&base, &base)
  33  		tmSquare(&base, &base)
  34  
  35  		genTable[i][0] = tmEye()
  36  		genTable[i][1] = base
  37  		for j := int32(2); j < 16; j++ {
  38  			tmMul(&genTable[i][j], &genTable[i][j-1], &base)
  39  		}
  40  	}
  41  
  42  	genTableReady = true
  43  }
  44  
  45  // tmFixedExp computes r = SchnorrGen^s using the precomputed table.
  46  // Processes 54 4-bit windows covering the ~213-bit scalar.
  47  func tmFixedExp(r *tmat, s *scalar) {
  48  	*r = tmEye()
  49  
  50  	for i := int32(0); i < 54; i++ {
  51  		limb := i / 16
  52  		bit := uint32((i % 16) * 4)
  53  		nib := int32((s[limb] >> bit) & 0xF)
  54  
  55  		if nib != 0 {
  56  			tmMul(r, r, &genTable[i][nib])
  57  		}
  58  	}
  59  }
  60  
  61  // tmVarExp computes r = base^s for a variable torus matrix.
  62  func tmVarExp(r *tmat, base *tmat, s *scalar) {
  63  	*r = tmEye()
  64  	var b tmat
  65  	b = *base
  66  
  67  	for i := int32(0); i < 4; i++ {
  68  		word := s[i]
  69  		for bit := int32(0); bit < 64; bit++ {
  70  			if word&1 == 1 {
  71  				tmMul(r, r, &b)
  72  			}
  73  			tmSquare(&b, &b)
  74  			word >>= 1
  75  		}
  76  	}
  77  }
  78  
  79  // tmShamirExp computes r = G^a * PK^b where G is the fixed SchnorrGen
  80  // and PK is a variable torus matrix.
  81  //
  82  // Uses separate 4-bit windows with Horner's method (top-down).
  83  func tmShamirExp(r *tmat, a *scalar, pk *tmat, b *scalar) {
  84  	var pkTab [16]tmat
  85  	pkTab[0] = tmEye()
  86  	pkTab[1] = *pk
  87  	for j := int32(2); j < 16; j++ {
  88  		tmMul(&pkTab[j], &pkTab[j-1], pk)
  89  	}
  90  
  91  	*r = tmEye()
  92  
  93  	for i := int32(53); i >= 0; i-- {
  94  		tmSquare(r, r)
  95  		tmSquare(r, r)
  96  		tmSquare(r, r)
  97  		tmSquare(r, r)
  98  
  99  		limb := i / 16
 100  		bit := uint32((i % 16) * 4)
 101  		nibA := int32((a[limb] >> bit) & 0xF)
 102  		nibB := int32((b[limb] >> bit) & 0xF)
 103  
 104  		if nibA != 0 {
 105  			tmMul(r, r, &genTable[0][nibA])
 106  		}
 107  		if nibB != 0 {
 108  			tmMul(r, r, &pkTab[nibB])
 109  		}
 110  	}
 111  }
 112