error_correction.go 3.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135
  1. // error_correction.go - NewHope key exchange error correction.
  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 "gitlab.com/yawning/chacha20.git"
  9. func abs(v int32) int32 {
  10. mask := v >> 31
  11. return (v ^ mask) - mask
  12. }
  13. func f(v0, v1 *int32, x int32) int32 {
  14. // The`ref` code uses uint32 for x, but none of the values ever get large
  15. // enough for that, and that would be cast-tastic due to Go being Go.
  16. // Next 6 lines compute t = x/PARAM_Q
  17. b := x * 2730
  18. t := b >> 25
  19. b = x - t*paramQ
  20. b = (paramQ - 1) - b
  21. b >>= 31
  22. t -= b
  23. r := t & 1
  24. xit := t >> 1
  25. *v0 = xit + r // v0 = round(x/(2*PARAM_Q))
  26. t--
  27. r = t & 1
  28. *v1 = (t >> 1) + r
  29. return abs(x - ((*v0) * 2 * paramQ))
  30. }
  31. func g(x int32) int32 {
  32. // Next 6 lines compute t = x/(4 *PARAMQ)
  33. b := x * 2730
  34. t := b >> 27
  35. b = x - t*(paramQ*4)
  36. b = (paramQ * 4) - b
  37. b >>= 31
  38. t -= b
  39. c := t & 1
  40. t = (t >> 1) + c // t = round(x/(8*PARAM_Q))
  41. t *= 8 * paramQ
  42. return abs(t - x)
  43. }
  44. func llDecode(xi0, xi1, xi2, xi3 int32) int16 {
  45. t := g(xi0)
  46. t += g(xi1)
  47. t += g(xi2)
  48. t += g(xi3)
  49. t -= 8 * paramQ
  50. t >>= 31
  51. return int16(t & 1)
  52. }
  53. func (c *poly) helpRec(v *poly, seed *[SeedBytes]byte, nonce byte) {
  54. var v0, v1, vTmp [4]int32
  55. var k int32
  56. var rand [32]byte
  57. var n [8]byte
  58. n[7] = nonce
  59. stream, err := chacha20.New(seed[:], n[:])
  60. if err != nil {
  61. panic(err)
  62. }
  63. stream.KeyStream(rand[:])
  64. stream.Reset()
  65. defer memwipe(rand[:])
  66. for i := uint(0); i < 256; i++ {
  67. rBit := int32((rand[i>>3] >> (i & 7)) & 1)
  68. vTmp[0], vTmp[1], vTmp[2], vTmp[3] = int32(v.coeffs[i]), int32(v.coeffs[256+i]), int32(v.coeffs[512+i]), int32(v.coeffs[768+i])
  69. // newhope-20151209 - New version of the reconciliation.
  70. k = f(&v0[0], &v1[0], 8*vTmp[0]+4*rBit)
  71. k += f(&v0[1], &v1[1], 8*vTmp[1]+4*rBit)
  72. k += f(&v0[2], &v1[2], 8*vTmp[2]+4*rBit)
  73. k += f(&v0[3], &v1[3], 8*vTmp[3]+4*rBit)
  74. k = (2*paramQ - 1 - k) >> 31
  75. vTmp[0] = ((^k) & v0[0]) ^ (k & v1[0])
  76. vTmp[1] = ((^k) & v0[1]) ^ (k & v1[1])
  77. vTmp[2] = ((^k) & v0[2]) ^ (k & v1[2])
  78. vTmp[3] = ((^k) & v0[3]) ^ (k & v1[3])
  79. c.coeffs[0+i] = uint16((vTmp[0] - vTmp[3]) & 3)
  80. c.coeffs[256+i] = uint16((vTmp[1] - vTmp[3]) & 3)
  81. c.coeffs[512+i] = uint16((vTmp[2] - vTmp[3]) & 3)
  82. c.coeffs[768+i] = uint16((-k + 2*vTmp[3]) & 3)
  83. }
  84. for i := range vTmp {
  85. vTmp[i] = 0
  86. }
  87. }
  88. func rec(key *[32]byte, v, c *poly) {
  89. var tmp, vTmp, cTmp [4]int32
  90. for i := range key {
  91. key[i] = 0
  92. }
  93. for i := uint(0); i < 256; i++ {
  94. vTmp[0], vTmp[1], vTmp[2], vTmp[3] = int32(v.coeffs[i]), int32(v.coeffs[256+i]), int32(v.coeffs[512+i]), int32(v.coeffs[768+i])
  95. cTmp[0], cTmp[1], cTmp[2], cTmp[3] = int32(c.coeffs[i]), int32(c.coeffs[256+i]), int32(c.coeffs[512+i]), int32(c.coeffs[768+i])
  96. tmp[0] = 16*paramQ + 8*vTmp[0] - paramQ*(2*cTmp[0]+cTmp[3])
  97. tmp[1] = 16*paramQ + 8*vTmp[1] - paramQ*(2*cTmp[1]+cTmp[3])
  98. tmp[2] = 16*paramQ + 8*vTmp[2] - paramQ*(2*cTmp[2]+cTmp[3])
  99. tmp[3] = 16*paramQ + 8*vTmp[3] - paramQ*(cTmp[3])
  100. key[i>>3] |= byte(llDecode(tmp[0], tmp[1], tmp[2], tmp[3]) << (i & 7))
  101. }
  102. for i := 0; i < 4; i++ {
  103. tmp[i] = 0
  104. vTmp[i] = 0
  105. cTmp[i] = 0
  106. }
  107. }