poly.go 5.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146
  1. // poly.go - Kyber polynomial.
  2. //
  3. // To the extent possible under law, Yawning Angel has waived all copyright
  4. // and related or neighboring rights to the software, using the Creative
  5. // Commons "CC0" public domain dedication. See LICENSE or
  6. // <http://creativecommons.org/publicdomain/zero/1.0/> for full details.
  7. package kyber
  8. import "golang.org/x/crypto/sha3"
  9. // Elements of R_q = Z_q[X]/(X^n + 1). Represents polynomial coeffs[0] +
  10. // X*coeffs[1] + X^2*xoeffs[2] + ... + X^{n-1}*coeffs[n-1].
  11. type poly struct {
  12. coeffs [kyberN]uint16
  13. }
  14. // Compression and subsequent serialization of a polynomial.
  15. func (p *poly) compress(r []byte) {
  16. var t [8]uint32
  17. for i, k := 0, 0; i < kyberN; i, k = i+8, k+3 {
  18. for j := 0; j < 8; j++ {
  19. t[j] = uint32((((freeze(p.coeffs[i+j]) << 3) + kyberQ/2) / kyberQ) & 7)
  20. }
  21. r[k] = byte(t[0] | (t[1] << 3) | (t[2] << 6))
  22. r[k+1] = byte((t[2] >> 2) | (t[3] << 1) | (t[4] << 4) | (t[5] << 7))
  23. r[k+2] = byte((t[5] >> 1) | (t[6] << 2) | (t[7] << 5))
  24. }
  25. }
  26. // De-serialization and subsequent decompression of a polynomial; approximate
  27. // inverse of poly.compress().
  28. func (p *poly) decompress(a []byte) {
  29. for i, off := 0, 0; i < kyberN; i, off = i+8, off+3 {
  30. p.coeffs[i+0] = ((uint16(a[off]&7) * kyberQ) + 4) >> 3
  31. p.coeffs[i+1] = (((uint16(a[off]>>3) & 7) * kyberQ) + 4) >> 3
  32. p.coeffs[i+2] = (((uint16(a[off]>>6) | (uint16(a[off+1]<<2) & 4)) * kyberQ) + 4) >> 3
  33. p.coeffs[i+3] = (((uint16(a[off+1]>>1) & 7) * kyberQ) + 4) >> 3
  34. p.coeffs[i+4] = (((uint16(a[off+1]>>4) & 7) * kyberQ) + 4) >> 3
  35. p.coeffs[i+5] = (((uint16(a[off+1]>>7) | (uint16(a[off+2]<<1) & 6)) * kyberQ) + 4) >> 3
  36. p.coeffs[i+6] = (((uint16(a[off+2]>>2) & 7) * kyberQ) + 4) >> 3
  37. p.coeffs[i+7] = (((uint16(a[off+2] >> 5)) * kyberQ) + 4) >> 3
  38. }
  39. }
  40. // Serialization of a polynomial.
  41. func (p *poly) toBytes(r []byte) {
  42. var t [8]uint16
  43. for i := 0; i < kyberN/8; i++ {
  44. for j := 0; j < 8; j++ {
  45. t[j] = freeze(p.coeffs[8*i+j])
  46. }
  47. r[13*i+0] = byte(t[0] & 0xff)
  48. r[13*i+1] = byte((t[0] >> 8) | ((t[1] & 0x07) << 5))
  49. r[13*i+2] = byte((t[1] >> 3) & 0xff)
  50. r[13*i+3] = byte((t[1] >> 11) | ((t[2] & 0x3f) << 2))
  51. r[13*i+4] = byte((t[2] >> 6) | ((t[3] & 0x01) << 7))
  52. r[13*i+5] = byte((t[3] >> 1) & 0xff)
  53. r[13*i+6] = byte((t[3] >> 9) | ((t[4] & 0x0f) << 4))
  54. r[13*i+7] = byte((t[4] >> 4) & 0xff)
  55. r[13*i+8] = byte((t[4] >> 12) | ((t[5] & 0x7f) << 1))
  56. r[13*i+9] = byte((t[5] >> 7) | ((t[6] & 0x03) << 6))
  57. r[13*i+10] = byte((t[6] >> 2) & 0xff)
  58. r[13*i+11] = byte((t[6] >> 10) | ((t[7] & 0x1f) << 3))
  59. r[13*i+12] = byte(t[7] >> 5)
  60. }
  61. }
  62. // De-serialization of a polynomial; inverse of poly.toBytes().
  63. func (p *poly) fromBytes(a []byte) {
  64. for i := 0; i < kyberN/8; i++ {
  65. p.coeffs[8*i+0] = uint16(a[13*i+0]) | ((uint16(a[13*i+1]) & 0x1f) << 8)
  66. p.coeffs[8*i+1] = (uint16(a[13*i+1]) >> 5) | (uint16(a[13*i+2]) << 3) | ((uint16(a[13*i+3]) & 0x03) << 11)
  67. p.coeffs[8*i+2] = (uint16(a[13*i+3]) >> 2) | ((uint16(a[13*i+4]) & 0x7f) << 6)
  68. p.coeffs[8*i+3] = (uint16(a[13*i+4]) >> 7) | (uint16(a[13*i+5]) << 1) | ((uint16(a[13*i+6]) & 0x0f) << 9)
  69. p.coeffs[8*i+4] = (uint16(a[13*i+6]) >> 4) | (uint16(a[13*i+7]) << 4) | ((uint16(a[13*i+8]) & 0x01) << 12)
  70. p.coeffs[8*i+5] = (uint16(a[13*i+8]) >> 1) | ((uint16(a[13*i+9]) & 0x3f) << 7)
  71. p.coeffs[8*i+6] = (uint16(a[13*i+9]) >> 6) | (uint16(a[13*i+10]) << 2) | ((uint16(a[13*i+11]) & 0x07) << 10)
  72. p.coeffs[8*i+7] = (uint16(a[13*i+11]) >> 3) | (uint16(a[13*i+12]) << 5)
  73. }
  74. }
  75. // Convert 32-byte message to polynomial.
  76. func (p *poly) fromMsg(msg []byte) {
  77. for i, v := range msg[:SymSize] {
  78. for j := 0; j < 8; j++ {
  79. mask := -((uint16(v) >> uint(j)) & 1)
  80. p.coeffs[8*i+j] = mask & ((kyberQ + 1) / 2)
  81. }
  82. }
  83. }
  84. // Convert polynomial to 32-byte message.
  85. func (p *poly) toMsg(msg []byte) {
  86. for i := 0; i < SymSize; i++ {
  87. msg[i] = 0
  88. for j := 0; j < 8; j++ {
  89. t := (((freeze(p.coeffs[8*i+j]) << 1) + kyberQ/2) / kyberQ) & 1
  90. msg[i] |= byte(t << uint(j))
  91. }
  92. }
  93. }
  94. // Sample a polynomial deterministically from a seed and a nonce, with output
  95. // polynomial close to centered binomial distribution with parameter eta.
  96. func (p *poly) getNoise(seed []byte, nonce byte, eta int) {
  97. extSeed := make([]byte, 0, SymSize+1)
  98. extSeed = append(extSeed, seed...)
  99. extSeed = append(extSeed, nonce)
  100. buf := make([]byte, eta*kyberN/4)
  101. sha3.ShakeSum256(buf, extSeed)
  102. p.cbd(buf, eta)
  103. }
  104. // Computes negacyclic number-theoretic transform (NTT) of a polynomial in
  105. // place; inputs assumed to be in normal order, output in bitreversed order.
  106. func (p *poly) ntt() {
  107. hardwareAccelImpl.nttFn(&p.coeffs)
  108. }
  109. // Computes inverse of negacyclic number-theoretic transform (NTT) of a
  110. // polynomial in place; inputs assumed to be in bitreversed order, output in
  111. // normal order.
  112. func (p *poly) invntt() {
  113. hardwareAccelImpl.invnttFn(&p.coeffs)
  114. }
  115. // Add two polynomials.
  116. func (p *poly) add(a, b *poly) {
  117. for i := range p.coeffs {
  118. p.coeffs[i] = barrettReduce(a.coeffs[i] + b.coeffs[i])
  119. }
  120. }
  121. // Subtract two polynomials.
  122. func (p *poly) sub(a, b *poly) {
  123. for i := range p.coeffs {
  124. p.coeffs[i] = barrettReduce(a.coeffs[i] + 3*kyberQ - b.coeffs[i])
  125. }
  126. }