poly.go 4.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212
  1. // poly.go - NewHope polynomial.
  2. //
  3. // To the extent possible under law, Yawning Angel has waived all copyright
  4. // and related or neighboring rights to newhope, 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 newhope
  8. import (
  9. "encoding/binary"
  10. "git.schwanenlied.me/yawning/chacha20.git"
  11. "golang.org/x/crypto/sha3"
  12. )
  13. const (
  14. // PolyBytes is the length of an encoded polynomial in bytes.
  15. PolyBytes = 1792
  16. shake128Rate = 168 // Stupid that this isn't exposed.
  17. )
  18. type poly struct {
  19. coeffs [paramN]uint16
  20. }
  21. func (p *poly) reset() {
  22. for i := range p.coeffs {
  23. p.coeffs[i] = 0
  24. }
  25. }
  26. func (p *poly) fromBytes(a []byte) {
  27. for i := 0; i < paramN/4; i++ {
  28. p.coeffs[4*i+0] = uint16(a[7*i+0]) | ((uint16(a[7*i+1]) & 0x3f) << 8)
  29. p.coeffs[4*i+1] = (uint16(a[7*i+1]) >> 6) | (uint16(a[7*i+2]) << 2) | ((uint16(a[7*i+3]) & 0x0f) << 10)
  30. p.coeffs[4*i+2] = (uint16(a[7*i+3]) >> 4) | (uint16(a[7*i+4]) << 4) | ((uint16(a[7*i+5]) & 0x03) << 12)
  31. p.coeffs[4*i+3] = (uint16(a[7*i+5]) >> 2) | (uint16(a[7*i+6]) << 6)
  32. }
  33. }
  34. func (p *poly) toBytes(r []byte) {
  35. for i := 0; i < paramN/4; i++ {
  36. // Make sure that coefficients have only 14 bits.
  37. t0 := barrettReduce(p.coeffs[4*i+0])
  38. t1 := barrettReduce(p.coeffs[4*i+1])
  39. t2 := barrettReduce(p.coeffs[4*i+2])
  40. t3 := barrettReduce(p.coeffs[4*i+3])
  41. // Make sure that coefficients are in [0,q]
  42. m := t0 - paramQ
  43. c := int16(m)
  44. c >>= 15
  45. t0 = m ^ ((t0 ^ m) & uint16(c))
  46. m = t1 - paramQ
  47. c = int16(m)
  48. c >>= 15
  49. t1 = m ^ ((t1 ^ m) & uint16(c))
  50. m = t2 - paramQ
  51. c = int16(m)
  52. c >>= 15
  53. t2 = m ^ ((t2 ^ m) & uint16(c))
  54. m = t3 - paramQ
  55. c = int16(m)
  56. c >>= 15
  57. t3 = m ^ ((t3 ^ m) & uint16(c))
  58. r[7*i+0] = byte(t0 & 0xff)
  59. r[7*i+1] = byte(t0>>8) | byte(t1<<6)
  60. r[7*i+2] = byte(t1 >> 2)
  61. r[7*i+3] = byte(t1>>10) | byte(t2<<4)
  62. r[7*i+4] = byte(t2 >> 4)
  63. r[7*i+5] = byte(t2>>12) | byte(t3<<2)
  64. r[7*i+6] = byte(t3 >> 6)
  65. }
  66. }
  67. func (p *poly) discardTo(xbuf []byte) bool {
  68. var x [shake128Rate * 16 / 2]uint16
  69. for i := range x {
  70. x[i] = binary.LittleEndian.Uint16(xbuf[i*2:])
  71. }
  72. for i := 0; i < 16; i++ {
  73. batcher84(x[i:])
  74. }
  75. // Check whether we're safe:
  76. r := int(0)
  77. for i := 1000; i < 1024; i++ {
  78. r |= 61444 - int(x[i])
  79. }
  80. if r>>31 != 0 {
  81. return true
  82. }
  83. // If we are, copy coefficients to polynomial:
  84. for i := range p.coeffs {
  85. p.coeffs[i] = x[i]
  86. }
  87. return false
  88. }
  89. func (p *poly) uniform(seed *[SeedBytes]byte, torSampling bool) {
  90. if !torSampling {
  91. // Reference version, vartime.
  92. nBlocks := 14
  93. var buf [shake128Rate * 14]byte
  94. // h and buf are left unscrubbed because the output is public.
  95. h := sha3.NewShake128()
  96. h.Write(seed[:])
  97. h.Read(buf[:])
  98. for ctr, pos := 0, 0; ctr < paramN; {
  99. val := binary.LittleEndian.Uint16(buf[pos:])
  100. if val < 5*paramQ {
  101. p.coeffs[ctr] = val
  102. ctr++
  103. }
  104. pos += 2
  105. if pos > shake128Rate*nBlocks-2 {
  106. nBlocks = 1
  107. h.Read(buf[:shake128Rate])
  108. pos = 0
  109. }
  110. }
  111. } else {
  112. // `torref` version, every valid `a` is generate in constant time,
  113. // though the number of attempts varies.
  114. const nBlocks = 16
  115. var buf [shake128Rate * nBlocks]byte
  116. // h and buf are left unscrubbed because the output is public.
  117. h := sha3.NewShake128()
  118. h.Write(seed[:])
  119. for {
  120. h.Read(buf[:])
  121. if !p.discardTo(buf[:]) {
  122. break
  123. }
  124. }
  125. }
  126. }
  127. func (p *poly) getNoise(seed *[SeedBytes]byte, nonce byte) {
  128. // The `ref` code uses a uint32 vector instead of a byte vector,
  129. // but converting between the two in Go is cumbersome.
  130. var buf [4 * paramN]byte
  131. var n [8]byte
  132. n[0] = nonce
  133. stream, err := chacha20.NewCipher(seed[:], n[:])
  134. if err != nil {
  135. panic(err)
  136. }
  137. stream.KeyStream(buf[:])
  138. stream.Reset()
  139. for i := 0; i < paramN; i++ {
  140. t := binary.LittleEndian.Uint32(buf[4*i:])
  141. d := uint32(0)
  142. for j := uint(0); j < 8; j++ {
  143. d += (t >> j) & 0x01010101
  144. }
  145. a := ((d >> 8) & 0xff) + (d & 0xff)
  146. b := (d >> 24) + ((d >> 16) & 0xff)
  147. p.coeffs[i] = uint16(a) + paramQ - uint16(b)
  148. }
  149. // Scrub the random bits...
  150. memwipe(buf[:])
  151. }
  152. func (p *poly) pointwise(a, b *poly) {
  153. for i := range p.coeffs {
  154. t := montgomeryReduce(3186 * uint32(b.coeffs[i])) // t is now in Montgomery domain
  155. p.coeffs[i] = montgomeryReduce(uint32(a.coeffs[i]) * uint32(t)) // p.coeffs[i] is back in normal domain
  156. }
  157. }
  158. func (p *poly) add(a, b *poly) {
  159. for i := range p.coeffs {
  160. p.coeffs[i] = barrettReduce(a.coeffs[i] + b.coeffs[i])
  161. }
  162. }
  163. func (p *poly) ntt() {
  164. p.mulCoefficients(&psisBitrevMontgomery)
  165. ntt(&p.coeffs, &omegasMontgomery)
  166. }
  167. func (p *poly) invNtt() {
  168. p.bitrev()
  169. ntt(&p.coeffs, &omegasInvMontgomery)
  170. p.mulCoefficients(&psisInvMontgomery)
  171. }
  172. func init() {
  173. if paramK != 16 {
  174. panic("poly.getNoise() only supports k=16")
  175. }
  176. }