newhope.go 5.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220
  1. // newhope.go - NewHope interface.
  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 implements a key exchange based on the Ring Learning with
  8. // Errors Problem. It is a mechanical port of the Public Domain implementation
  9. // by Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe.
  10. //
  11. // For more information see:
  12. // https://cryptojedi.org/papers/newhope-20161119.pdf
  13. // https://cryptojedi.org/papers/newhopesimple-20161217.pdf
  14. //
  15. package newhope
  16. import (
  17. "io"
  18. "golang.org/x/crypto/sha3"
  19. )
  20. const (
  21. // SharedSecretSize is the length of a Shared Secret in bytes.
  22. SharedSecretSize = 32
  23. // UpstreamVersion is the version of the upstream package this
  24. // implementation is compatible with.
  25. UpstreamVersion = "20160815"
  26. // RecBytes is the length of the reconciliation data in bytes.
  27. RecBytes = 256
  28. // SendASize is the length of Alice's public key in bytes.
  29. SendASize = PolyBytes + SeedBytes
  30. // SendBSize is the length of Bob's public key in bytes.
  31. SendBSize = PolyBytes + RecBytes
  32. )
  33. // TorSampling enables the constant time generation of the `a` parameter,
  34. // where every successful `a` generation will take the same amount of time.
  35. // Most users will probably not want to enable this as it does come with a
  36. // performance penalty. Alice and Bob *MUST* agree on the sampling method,
  37. // or the key exchange will fail.
  38. var TorSampling = false
  39. func encodeA(r []byte, pk *poly, seed *[SeedBytes]byte) {
  40. pk.toBytes(r)
  41. for i := 0; i < SeedBytes; i++ {
  42. r[PolyBytes+i] = seed[i]
  43. }
  44. }
  45. func decodeA(pk *poly, seed *[SeedBytes]byte, r []byte) {
  46. pk.fromBytes(r)
  47. for i := range seed {
  48. seed[i] = r[PolyBytes+i]
  49. }
  50. }
  51. func encodeB(r []byte, b *poly, c *poly) {
  52. b.toBytes(r)
  53. for i := 0; i < paramN/4; i++ {
  54. r[PolyBytes+i] = byte(c.coeffs[4*i]) | byte(c.coeffs[4*i+1]<<2) | byte(c.coeffs[4*i+2]<<4) | byte(c.coeffs[4*i+3]<<6)
  55. }
  56. }
  57. func decodeB(b *poly, c *poly, r []byte) {
  58. b.fromBytes(r)
  59. for i := 0; i < paramN/4; i++ {
  60. c.coeffs[4*i+0] = uint16(r[PolyBytes+i]) & 0x03
  61. c.coeffs[4*i+1] = uint16(r[PolyBytes+i]>>2) & 0x03
  62. c.coeffs[4*i+2] = uint16(r[PolyBytes+i]>>4) & 0x03
  63. c.coeffs[4*i+3] = uint16(r[PolyBytes+i] >> 6)
  64. }
  65. }
  66. func memwipe(b []byte) {
  67. for i := range b {
  68. b[i] = 0
  69. }
  70. }
  71. // PublicKeyAlice is Alice's NewHope public key.
  72. type PublicKeyAlice struct {
  73. Send [SendASize]byte
  74. }
  75. // PrivateKeyAlice is Alice's NewHope private key.
  76. type PrivateKeyAlice struct {
  77. sk poly
  78. }
  79. // Reset clears all sensitive information such that it no longer appears in
  80. // memory.
  81. func (k *PrivateKeyAlice) Reset() {
  82. k.sk.reset()
  83. }
  84. // GenerateKeyPairAlice returns a private/public key pair. The private key is
  85. // generated using the given reader, which must return random data. The
  86. // receiver side of the key exchange (aka "Bob") MUST use KeyExchangeBob()
  87. // instead of this routine.
  88. func GenerateKeyPairAlice(rand io.Reader) (*PrivateKeyAlice, *PublicKeyAlice, error) {
  89. var a, e, pk, r poly
  90. var seed, noiseSeed [SeedBytes]byte
  91. // seed <- Sample({0, 1}^256)
  92. if _, err := io.ReadFull(rand, seed[:]); err != nil {
  93. return nil, nil, err
  94. }
  95. seed = sha3.Sum256(seed[:]) // Don't send output of system RNG.
  96. // a <- Parse(SHAKE-128(seed))
  97. a.uniform(&seed, TorSampling)
  98. // s, e <- Sample(psi(n, 12))
  99. if _, err := io.ReadFull(rand, noiseSeed[:]); err != nil {
  100. return nil, nil, err
  101. }
  102. defer memwipe(noiseSeed[:])
  103. privKey := new(PrivateKeyAlice)
  104. privKey.sk.getNoise(&noiseSeed, 0)
  105. privKey.sk.ntt()
  106. e.getNoise(&noiseSeed, 1)
  107. e.ntt()
  108. // b <- as + e
  109. pubKey := new(PublicKeyAlice)
  110. r.pointwise(&privKey.sk, &a)
  111. pk.add(&e, &r)
  112. encodeA(pubKey.Send[:], &pk, &seed)
  113. return privKey, pubKey, nil
  114. }
  115. // PublicKeyBob is Bob's NewHope public key.
  116. type PublicKeyBob struct {
  117. Send [SendBSize]byte
  118. }
  119. // KeyExchangeBob is the Responder side of the NewHope key exchange. The
  120. // shared secret and "public key" (key + reconciliation data) are generated
  121. // using the given reader, which must return random data.
  122. func KeyExchangeBob(rand io.Reader, alicePk *PublicKeyAlice) (*PublicKeyBob, []byte, error) {
  123. var pka, a, sp, ep, u, v, epp, r poly
  124. var seed, noiseSeed [SeedBytes]byte
  125. if _, err := io.ReadFull(rand, noiseSeed[:]); err != nil {
  126. return nil, nil, err
  127. }
  128. defer memwipe(noiseSeed[:])
  129. // a <- Parse(SHAKE-128(seed))
  130. decodeA(&pka, &seed, alicePk.Send[:])
  131. a.uniform(&seed, TorSampling)
  132. // s', e', e'' <- Sample(psi(n, 12))
  133. sp.getNoise(&noiseSeed, 0)
  134. sp.ntt()
  135. ep.getNoise(&noiseSeed, 1)
  136. ep.ntt()
  137. epp.getNoise(&noiseSeed, 2)
  138. // u <- as' + e'
  139. u.pointwise(&a, &sp)
  140. u.add(&u, &ep)
  141. // v <- bs' + e''
  142. v.pointwise(&pka, &sp)
  143. v.invNtt()
  144. v.add(&v, &epp)
  145. // r <- Sample(HelpRec(v))
  146. r.helpRec(&v, &noiseSeed, 3)
  147. pubKey := new(PublicKeyBob)
  148. encodeB(pubKey.Send[:], &u, &r)
  149. // nu <- Rec(v, r)
  150. var nu [SharedSecretSize]byte
  151. rec(&nu, &v, &r)
  152. // mu <- SHA3-256(nu)
  153. mu := sha3.Sum256(nu[:])
  154. // Scrub the sensitive stuff...
  155. memwipe(nu[:])
  156. sp.reset()
  157. v.reset()
  158. return pubKey, mu[:], nil
  159. }
  160. // KeyExchangeAlice is the Initiaitor side of the NewHope key exchange. The
  161. // provided private key is obliterated prior to returning.
  162. func KeyExchangeAlice(bobPk *PublicKeyBob, aliceSk *PrivateKeyAlice) ([]byte, error) {
  163. var u, r, vp poly
  164. decodeB(&u, &r, bobPk.Send[:])
  165. // v' <- us
  166. vp.pointwise(&aliceSk.sk, &u)
  167. vp.invNtt()
  168. // nu <- Rec(v', r)
  169. var nu [SharedSecretSize]byte
  170. rec(&nu, &vp, &r)
  171. // mu <- Sha3-256(nu)
  172. mu := sha3.Sum256(nu[:])
  173. // Scrub the sensitive stuff...
  174. memwipe(nu[:])
  175. vp.reset()
  176. aliceSk.Reset()
  177. return mu[:], nil
  178. }