pack.go

Documentation: github.com/cloudflare/circl/sign/dilithium/mode3/internal

     1  package internal
     2  
     3  import (
     4  	"github.com/cloudflare/circl/sign/dilithium/internal/common"
     5  )
     6  
     7  // Writes p with norm less than or equal η into buf, which must be of
     8  // size PolyLeqEtaSize.
     9  //
    10  // Assumes coefficients of p are not normalized, but in [q-η,q+η].
    11  func PolyPackLeqEta(p *common.Poly, buf []byte) {
    12  	if DoubleEtaBits == 4 { // compiler eliminates branch
    13  		j := 0
    14  		for i := 0; i < PolyLeqEtaSize; i++ {
    15  			buf[i] = (byte(common.Q+Eta-p[j]) |
    16  				byte(common.Q+Eta-p[j+1])<<4)
    17  			j += 2
    18  		}
    19  	} else if DoubleEtaBits == 3 {
    20  		j := 0
    21  		for i := 0; i < PolyLeqEtaSize; i += 3 {
    22  			buf[i] = (byte(common.Q+Eta-p[j]) |
    23  				(byte(common.Q+Eta-p[j+1]) << 3) |
    24  				(byte(common.Q+Eta-p[j+2]) << 6))
    25  			buf[i+1] = ((byte(common.Q+Eta-p[j+2]) >> 2) |
    26  				(byte(common.Q+Eta-p[j+3]) << 1) |
    27  				(byte(common.Q+Eta-p[j+4]) << 4) |
    28  				(byte(common.Q+Eta-p[j+5]) << 7))
    29  			buf[i+2] = ((byte(common.Q+Eta-p[j+5]) >> 1) |
    30  				(byte(common.Q+Eta-p[j+6]) << 2) |
    31  				(byte(common.Q+Eta-p[j+7]) << 5))
    32  			j += 8
    33  		}
    34  	} else {
    35  		panic("eta not supported")
    36  	}
    37  }
    38  
    39  // Sets p to the polynomial of norm less than or equal η encoded in the
    40  // given buffer of size PolyLeqEtaSize.
    41  //
    42  // Output coefficients of p are not normalized, but in [q-η,q+η] provided
    43  // buf was created using PackLeqEta.
    44  //
    45  // Beware, for arbitrary buf the coefficients of p might end up in
    46  // the interval [q-2^b,q+2^b] where b is the least b with η≤2^b.
    47  func PolyUnpackLeqEta(p *common.Poly, buf []byte) {
    48  	if DoubleEtaBits == 4 { // compiler eliminates branch
    49  		j := 0
    50  		for i := 0; i < PolyLeqEtaSize; i++ {
    51  			p[j] = common.Q + Eta - uint32(buf[i]&15)
    52  			p[j+1] = common.Q + Eta - uint32(buf[i]>>4)
    53  			j += 2
    54  		}
    55  	} else if DoubleEtaBits == 3 {
    56  		j := 0
    57  		for i := 0; i < PolyLeqEtaSize; i += 3 {
    58  			p[j] = common.Q + Eta - uint32(buf[i]&7)
    59  			p[j+1] = common.Q + Eta - uint32((buf[i]>>3)&7)
    60  			p[j+2] = common.Q + Eta - uint32((buf[i]>>6)|((buf[i+1]<<2)&7))
    61  			p[j+3] = common.Q + Eta - uint32((buf[i+1]>>1)&7)
    62  			p[j+4] = common.Q + Eta - uint32((buf[i+1]>>4)&7)
    63  			p[j+5] = common.Q + Eta - uint32((buf[i+1]>>7)|((buf[i+2]<<1)&7))
    64  			p[j+6] = common.Q + Eta - uint32((buf[i+2]>>2)&7)
    65  			p[j+7] = common.Q + Eta - uint32((buf[i+2]>>5)&7)
    66  			j += 8
    67  		}
    68  	} else {
    69  		panic("eta not supported")
    70  	}
    71  }
    72  
    73  // Writes v with coefficients in {0, 1} of which at most ω non-zero
    74  // to buf, which must have length ω+k.
    75  func (v *VecK) PackHint(buf []byte) {
    76  	// The packed hint starts with the indices of the non-zero coefficients
    77  	// For instance:
    78  	//
    79  	//    (x⁵⁶ + x¹⁰⁰, x²⁵⁵, 0, x² + x²³, x¹)
    80  	//
    81  	// Yields
    82  	//
    83  	//  56, 100, 255, 2, 23, 1
    84  	//
    85  	// Then we pad with zeroes until we have a list of ω items:
    86  	// //  56, 100, 255, 2, 23, 1, 0, 0, ..., 0
    87  	//
    88  	// Then we finish with a list of the switch-over-indices in this
    89  	// list between polynomials, so:
    90  	//
    91  	//  56, 100, 255, 2, 23, 1, 0, 0, ..., 0, 2, 3, 3, 5, 6
    92  
    93  	off := uint8(0)
    94  	for i := 0; i < K; i++ {
    95  		for j := uint16(0); j < common.N; j++ {
    96  			if v[i][j] != 0 {
    97  				buf[off] = uint8(j)
    98  				off++
    99  			}
   100  		}
   101  		buf[Omega+i] = off
   102  	}
   103  	for ; off < Omega; off++ {
   104  		buf[off] = 0
   105  	}
   106  }
   107  
   108  // Sets v to the vector encoded using VecK.PackHint()
   109  //
   110  // Returns whether unpacking was successful.
   111  func (v *VecK) UnpackHint(buf []byte) bool {
   112  	// A priori, there would be several reasonable ways to encode the same
   113  	// hint vector.  We take care to only allow only one encoding, to ensure
   114  	// "strong unforgeability".
   115  	//
   116  	// See PackHint() source for description of the encoding.
   117  	*v = VecK{}         // zero v
   118  	prevSOP := uint8(0) // previous switch-over-point
   119  	for i := 0; i < K; i++ {
   120  		SOP := buf[Omega+i]
   121  		if SOP < prevSOP || SOP > Omega {
   122  			return false // ensures switch-over-points are increasing
   123  		}
   124  		for j := prevSOP; j < SOP; j++ {
   125  			if j > prevSOP && buf[j] <= buf[j-1] {
   126  				return false // ensures indices are increasing (within a poly)
   127  			}
   128  			v[i][buf[j]] = 1
   129  		}
   130  		prevSOP = SOP
   131  	}
   132  	for j := prevSOP; j < Omega; j++ {
   133  		if buf[j] != 0 {
   134  			return false // ensures padding indices are zero
   135  		}
   136  	}
   137  
   138  	return true
   139  }
   140  
   141  // Sets p to the polynomial packed into buf by PolyPackLeGamma1.
   142  //
   143  // p will be normalized.
   144  func PolyUnpackLeGamma1(p *common.Poly, buf []byte) {
   145  	if Gamma1Bits == 17 {
   146  		j := 0
   147  		for i := 0; i < PolyLeGamma1Size; i += 9 {
   148  			p0 := uint32(buf[i]) | (uint32(buf[i+1]) << 8) |
   149  				(uint32(buf[i+2]&0x3) << 16)
   150  			p1 := uint32(buf[i+2]>>2) | (uint32(buf[i+3]) << 6) |
   151  				(uint32(buf[i+4]&0xf) << 14)
   152  			p2 := uint32(buf[i+4]>>4) | (uint32(buf[i+5]) << 4) |
   153  				(uint32(buf[i+6]&0x3f) << 12)
   154  			p3 := uint32(buf[i+6]>>6) | (uint32(buf[i+7]) << 2) |
   155  				(uint32(buf[i+8]) << 10)
   156  
   157  			// coefficients in [0,…,2γ₁)
   158  			p0 = Gamma1 - p0 // (-γ₁,…,γ₁]
   159  			p1 = Gamma1 - p1
   160  			p2 = Gamma1 - p2
   161  			p3 = Gamma1 - p3
   162  
   163  			p0 += uint32(int32(p0)>>31) & common.Q // normalize
   164  			p1 += uint32(int32(p1)>>31) & common.Q
   165  			p2 += uint32(int32(p2)>>31) & common.Q
   166  			p3 += uint32(int32(p3)>>31) & common.Q
   167  
   168  			p[j] = p0
   169  			p[j+1] = p1
   170  			p[j+2] = p2
   171  			p[j+3] = p3
   172  
   173  			j += 4
   174  		}
   175  	} else if Gamma1Bits == 19 {
   176  		j := 0
   177  		for i := 0; i < PolyLeGamma1Size; i += 5 {
   178  			p0 := uint32(buf[i]) | (uint32(buf[i+1]) << 8) |
   179  				(uint32(buf[i+2]&0xf) << 16)
   180  			p1 := uint32(buf[i+2]>>4) | (uint32(buf[i+3]) << 4) |
   181  				(uint32(buf[i+4]) << 12)
   182  
   183  			p0 = Gamma1 - p0
   184  			p1 = Gamma1 - p1
   185  
   186  			p0 += uint32(int32(p0)>>31) & common.Q
   187  			p1 += uint32(int32(p1)>>31) & common.Q
   188  
   189  			p[j] = p0
   190  			p[j+1] = p1
   191  
   192  			j += 2
   193  		}
   194  	} else {
   195  		panic("γ₁ not supported")
   196  	}
   197  }
   198  
   199  // Writes p whose coefficients are in (-γ₁,γ₁] into buf
   200  // which has to be of length PolyLeGamma1Size.
   201  //
   202  // Assumes p is normalized.
   203  func PolyPackLeGamma1(p *common.Poly, buf []byte) {
   204  	if Gamma1Bits == 17 {
   205  		j := 0
   206  		// coefficients in [0,…,γ₁] ∪ (q-γ₁,…,q)
   207  		for i := 0; i < PolyLeGamma1Size; i += 9 {
   208  			p0 := Gamma1 - p[j]                    // [0,…,γ₁] ∪ (γ₁-q,…,2γ₁-q)
   209  			p0 += uint32(int32(p0)>>31) & common.Q // [0,…,2γ₁)
   210  			p1 := Gamma1 - p[j+1]
   211  			p1 += uint32(int32(p1)>>31) & common.Q
   212  			p2 := Gamma1 - p[j+2]
   213  			p2 += uint32(int32(p2)>>31) & common.Q
   214  			p3 := Gamma1 - p[j+3]
   215  			p3 += uint32(int32(p3)>>31) & common.Q
   216  
   217  			buf[i+0] = byte(p0)
   218  			buf[i+1] = byte(p0 >> 8)
   219  			buf[i+2] = byte(p0>>16) | byte(p1<<2)
   220  			buf[i+3] = byte(p1 >> 6)
   221  			buf[i+4] = byte(p1>>14) | byte(p2<<4)
   222  			buf[i+5] = byte(p2 >> 4)
   223  			buf[i+6] = byte(p2>>12) | byte(p3<<6)
   224  			buf[i+7] = byte(p3 >> 2)
   225  			buf[i+8] = byte(p3 >> 10)
   226  
   227  			j += 4
   228  		}
   229  	} else if Gamma1Bits == 19 {
   230  		j := 0
   231  		for i := 0; i < PolyLeGamma1Size; i += 5 {
   232  			// Coefficients are in [0, γ₁] ∪ (Q-γ₁, Q)
   233  			p0 := Gamma1 - p[j]
   234  			p0 += uint32(int32(p0)>>31) & common.Q
   235  			p1 := Gamma1 - p[j+1]
   236  			p1 += uint32(int32(p1)>>31) & common.Q
   237  
   238  			buf[i+0] = byte(p0)
   239  			buf[i+1] = byte(p0 >> 8)
   240  			buf[i+2] = byte(p0>>16) | byte(p1<<4)
   241  			buf[i+3] = byte(p1 >> 4)
   242  			buf[i+4] = byte(p1 >> 12)
   243  
   244  			j += 2
   245  		}
   246  	} else {
   247  		panic("γ₁ not supported")
   248  	}
   249  }
   250  
   251  // Pack w₁ into buf, which must be of length PolyW1Size.
   252  //
   253  // Assumes w₁ is normalized.
   254  func PolyPackW1(p *common.Poly, buf []byte) {
   255  	if Gamma1Bits == 19 {
   256  		p.PackLe16(buf)
   257  	} else if Gamma1Bits == 17 {
   258  		j := 0
   259  		for i := 0; i < PolyW1Size; i += 3 {
   260  			buf[i] = byte(p[j]) | byte(p[j+1]<<6)
   261  			buf[i+1] = byte(p[j+1]>>2) | byte(p[j+2]<<4)
   262  			buf[i+2] = byte(p[j+2]>>4) | byte(p[j+3]<<2)
   263  			j += 4
   264  		}
   265  	} else {
   266  		panic("unsupported γ₁")
   267  	}
   268  }
   269
View as plain text