ref: 2cdc6577ef8a251bf1740439cf5bfc47050dab41
dir: /third_party/boringssl/src/ssl/test/runner/hrss/hrss.go/
package hrss
import (
"crypto/hmac"
"crypto/sha256"
"crypto/subtle"
"encoding/binary"
"io"
"math/bits"
)
const (
PublicKeySize = modQBytes
CiphertextSize = modQBytes
)
const (
N = 701
Q = 8192
mod3Bytes = 140
modQBytes = 1138
)
const (
bitsPerWord = bits.UintSize
wordsPerPoly = (N + bitsPerWord - 1) / bitsPerWord
fullWordsPerPoly = N / bitsPerWord
bitsInLastWord = N % bitsPerWord
)
// poly3 represents a degree-N polynomial over GF(3). Each coefficient is
// bitsliced across the |s| and |a| arrays, like this:
//
// s | a | value
// -----------------
// 0 | 0 | 0
// 0 | 1 | 1
// 1 | 0 | 2 (aka -1)
// 1 | 1 | <invalid>
//
// ('s' is for sign, and 'a' is just a letter.)
//
// Once bitsliced as such, the following circuits can be used to implement
// addition and multiplication mod 3:
//
// (s3, a3) = (s1, a1) × (s2, a2)
// s3 = (s2 ∧ a1) ⊕ (s1 ∧ a2)
// a3 = (s1 ∧ s2) ⊕ (a1 ∧ a2)
//
// (s3, a3) = (s1, a1) + (s2, a2)
// t1 = ~(s1 ∨ a1)
// t2 = ~(s2 ∨ a2)
// s3 = (a1 ∧ a2) ⊕ (t1 ∧ s2) ⊕ (t2 ∧ s1)
// a3 = (s1 ∧ s2) ⊕ (t1 ∧ a2) ⊕ (t2 ∧ a1)
//
// Negating a value just involves swapping s and a.
type poly3 struct {
s [wordsPerPoly]uint
a [wordsPerPoly]uint
}
func (p *poly3) trim() {
p.s[wordsPerPoly-1] &= (1 << bitsInLastWord) - 1
p.a[wordsPerPoly-1] &= (1 << bitsInLastWord) - 1
}
func (p *poly3) zero() {
for i := range p.a {
p.s[i] = 0
p.a[i] = 0
}
}
func (p *poly3) fromDiscrete(in *poly) {
var shift uint
s := p.s[:]
a := p.a[:]
s[0] = 0
a[0] = 0
for _, v := range in {
s[0] >>= 1
s[0] |= uint((v>>1)&1) << (bitsPerWord - 1)
a[0] >>= 1
a[0] |= uint(v&1) << (bitsPerWord - 1)
shift++
if shift == bitsPerWord {
s = s[1:]
a = a[1:]
s[0] = 0
a[0] = 0
shift = 0
}
}
a[0] >>= bitsPerWord - shift
s[0] >>= bitsPerWord - shift
}
func (p *poly3) fromModQ(in *poly) int {
var shift uint
s := p.s[:]
a := p.a[:]
s[0] = 0
a[0] = 0
ok := 1
for _, v := range in {
vMod3, vOk := modQToMod3(v)
ok &= vOk
s[0] >>= 1
s[0] |= uint((vMod3>>1)&1) << (bitsPerWord - 1)
a[0] >>= 1
a[0] |= uint(vMod3&1) << (bitsPerWord - 1)
shift++
if shift == bitsPerWord {
s = s[1:]
a = a[1:]
s[0] = 0
a[0] = 0
shift = 0
}
}
a[0] >>= bitsPerWord - shift
s[0] >>= bitsPerWord - shift
return ok
}
func (p *poly3) fromDiscreteMod3(in *poly) {
var shift uint
s := p.s[:]
a := p.a[:]
s[0] = 0
a[0] = 0
for _, v := range in {
// This duplicates the 13th bit upwards to the top of the
// uint16, essentially treating it as a sign bit and converting
// into a signed int16. The signed value is reduced mod 3,
// yeilding {-2, -1, 0, 1, 2}.
v = uint16((int16(v<<3)>>3)%3) & 7
// We want to map v thus:
// {-2, -1, 0, 1, 2} -> {1, 2, 0, 1, 2}. We take the bottom
// three bits and then the constants below, when shifted by
// those three bits, perform the required mapping.
s[0] >>= 1
s[0] |= (0xbc >> v) << (bitsPerWord - 1)
a[0] >>= 1
a[0] |= (0x7a >> v) << (bitsPerWord - 1)
shift++
if shift == bitsPerWord {
s = s[1:]
a = a[1:]
s[0] = 0
a[0] = 0
shift = 0
}
}
a[0] >>= bitsPerWord - shift
s[0] >>= bitsPerWord - shift
}
func (p *poly3) marshal(out []byte) {
s := p.s[:]
a := p.a[:]
sw := s[0]
aw := a[0]
var shift int
for i := 0; i < 700; i += 5 {
acc, scale := 0, 1
for j := 0; j < 5; j++ {
v := int(aw&1) | int(sw&1)<<1
acc += scale * v
scale *= 3
shift++
if shift == bitsPerWord {
s = s[1:]
a = a[1:]
sw = s[0]
aw = a[0]
shift = 0
} else {
sw >>= 1
aw >>= 1
}
}
out[0] = byte(acc)
out = out[1:]
}
}
func (p *poly) fromMod2(in *poly2) {
var shift uint
words := in[:]
word := words[0]
for i := range p {
p[i] = uint16(word & 1)
word >>= 1
shift++
if shift == bitsPerWord {
words = words[1:]
word = words[0]
shift = 0
}
}
}
func (p *poly) fromMod3(in *poly3) {
var shift uint
s := in.s[:]
a := in.a[:]
sw := s[0]
aw := a[0]
for i := range p {
p[i] = uint16(aw&1 | (sw&1)<<1)
aw >>= 1
sw >>= 1
shift++
if shift == bitsPerWord {
a = a[1:]
s = s[1:]
aw = a[0]
sw = s[0]
shift = 0
}
}
}
func (p *poly) fromMod3ToModQ(in *poly3) {
var shift uint
s := in.s[:]
a := in.a[:]
sw := s[0]
aw := a[0]
for i := range p {
p[i] = mod3ToModQ(uint16(aw&1 | (sw&1)<<1))
aw >>= 1
sw >>= 1
shift++
if shift == bitsPerWord {
a = a[1:]
s = s[1:]
aw = a[0]
sw = s[0]
shift = 0
}
}
}
func lsbToAll(v uint) uint {
return uint(int(v<<(bitsPerWord-1)) >> (bitsPerWord - 1))
}
func (p *poly3) mulConst(ms, ma uint) {
ms = lsbToAll(ms)
ma = lsbToAll(ma)
for i := range p.a {
p.s[i], p.a[i] = (ma&p.s[i])^(ms&p.a[i]), (ma&p.a[i])^(ms&p.s[i])
}
}
func cmovWords(out, in *[wordsPerPoly]uint, mov uint) {
for i := range out {
out[i] = (out[i] & ^mov) | (in[i] & mov)
}
}
func rotWords(out, in *[wordsPerPoly]uint, bits uint) {
start := bits / bitsPerWord
n := (N - bits) / bitsPerWord
for i := uint(0); i < n; i++ {
out[i] = in[start+i]
}
carry := in[wordsPerPoly-1]
for i := uint(0); i < start; i++ {
out[n+i] = carry | in[i]<<bitsInLastWord
carry = in[i] >> (bitsPerWord - bitsInLastWord)
}
out[wordsPerPoly-1] = carry
}
// rotBits right-rotates the bits in |in|. bits must be a non-zero power of two
// and less than bitsPerWord.
func rotBits(out, in *[wordsPerPoly]uint, bits uint) {
if (bits == 0 || (bits & (bits - 1)) != 0 || bits > bitsPerWord/2 || bitsInLastWord < bitsPerWord/2) {
panic("internal error");
}
carry := in[wordsPerPoly-1] << (bitsPerWord - bits)
for i := wordsPerPoly - 2; i >= 0; i-- {
out[i] = carry | in[i]>>bits
carry = in[i] << (bitsPerWord - bits)
}
out[wordsPerPoly-1] = carry>>(bitsPerWord-bitsInLastWord) | in[wordsPerPoly-1]>>bits
}
func (p *poly3) rotWords(bits uint, in *poly3) {
rotWords(&p.s, &in.s, bits)
rotWords(&p.a, &in.a, bits)
}
func (p *poly3) rotBits(bits uint, in *poly3) {
rotBits(&p.s, &in.s, bits)
rotBits(&p.a, &in.a, bits)
}
func (p *poly3) cmov(in *poly3, mov uint) {
cmovWords(&p.s, &in.s, mov)
cmovWords(&p.a, &in.a, mov)
}
func (p *poly3) rot(bits uint) {
if bits > N {
panic("invalid")
}
var shifted poly3
shift := uint(9)
for ; (1 << shift) >= bitsPerWord; shift-- {
shifted.rotWords(1<<shift, p)
p.cmov(&shifted, lsbToAll(bits>>shift))
}
for ; shift < 9; shift-- {
shifted.rotBits(1<<shift, p)
p.cmov(&shifted, lsbToAll(bits>>shift))
}
}
func (p *poly3) fmadd(ms, ma uint, in *poly3) {
ms = lsbToAll(ms)
ma = lsbToAll(ma)
for i := range p.a {
products := (ma & in.s[i]) ^ (ms & in.a[i])
producta := (ma & in.a[i]) ^ (ms & in.s[i])
ns1Ana1 := ^p.s[i] & ^p.a[i]
ns2Ana2 := ^products & ^producta
p.s[i], p.a[i] = (p.a[i]&producta)^(ns1Ana1&products)^(p.s[i]&ns2Ana2), (p.s[i]&products)^(ns1Ana1&producta)^(p.a[i]&ns2Ana2)
}
}
func (p *poly3) modPhiN() {
factora := uint(int(p.s[wordsPerPoly-1]<<(bitsPerWord-bitsInLastWord)) >> (bitsPerWord - 1))
factors := uint(int(p.a[wordsPerPoly-1]<<(bitsPerWord-bitsInLastWord)) >> (bitsPerWord - 1))
ns2Ana2 := ^factors & ^factora
for i := range p.s {
ns1Ana1 := ^p.s[i] & ^p.a[i]
p.s[i], p.a[i] = (p.a[i]&factora)^(ns1Ana1&factors)^(p.s[i]&ns2Ana2), (p.s[i]&factors)^(ns1Ana1&factora)^(p.a[i]&ns2Ana2)
}
}
func (p *poly3) cswap(other *poly3, swap uint) {
for i := range p.s {
sums := swap & (p.s[i] ^ other.s[i])
p.s[i] ^= sums
other.s[i] ^= sums
suma := swap & (p.a[i] ^ other.a[i])
p.a[i] ^= suma
other.a[i] ^= suma
}
}
func (p *poly3) mulx() {
carrys := (p.s[wordsPerPoly-1] >> (bitsInLastWord - 1)) & 1
carrya := (p.a[wordsPerPoly-1] >> (bitsInLastWord - 1)) & 1
for i := range p.s {
outCarrys := p.s[i] >> (bitsPerWord - 1)
outCarrya := p.a[i] >> (bitsPerWord - 1)
p.s[i] <<= 1
p.a[i] <<= 1
p.s[i] |= carrys
p.a[i] |= carrya
carrys = outCarrys
carrya = outCarrya
}
}
func (p *poly3) divx() {
var carrys, carrya uint
for i := len(p.s) - 1; i >= 0; i-- {
outCarrys := p.s[i] & 1
outCarrya := p.a[i] & 1
p.s[i] >>= 1
p.a[i] >>= 1
p.s[i] |= carrys << (bitsPerWord - 1)
p.a[i] |= carrya << (bitsPerWord - 1)
carrys = outCarrys
carrya = outCarrya
}
}
type poly2 [wordsPerPoly]uint
func (p *poly2) fromDiscrete(in *poly) {
var shift uint
words := p[:]
words[0] = 0
for _, v := range in {
words[0] >>= 1
words[0] |= uint(v&1) << (bitsPerWord - 1)
shift++
if shift == bitsPerWord {
words = words[1:]
words[0] = 0
shift = 0
}
}
words[0] >>= bitsPerWord - shift
}
func (p *poly2) setPhiN() {
for i := range p {
p[i] = ^uint(0)
}
p[wordsPerPoly-1] &= (1 << bitsInLastWord) - 1
}
func (p *poly2) cswap(other *poly2, swap uint) {
for i := range p {
sum := swap & (p[i] ^ other[i])
p[i] ^= sum
other[i] ^= sum
}
}
func (p *poly2) fmadd(m uint, in *poly2) {
m = ^(m - 1)
for i := range p {
p[i] ^= in[i] & m
}
}
func (p *poly2) lshift1() {
var carry uint
for i := range p {
nextCarry := p[i] >> (bitsPerWord - 1)
p[i] <<= 1
p[i] |= carry
carry = nextCarry
}
}
func (p *poly2) rshift1() {
var carry uint
for i := len(p) - 1; i >= 0; i-- {
nextCarry := p[i] & 1
p[i] >>= 1
p[i] |= carry << (bitsPerWord - 1)
carry = nextCarry
}
}
func (p *poly2) rot(bits uint) {
if bits > N {
panic("invalid")
}
var shifted [wordsPerPoly]uint
out := (*[wordsPerPoly]uint)(p)
shift := uint(9)
for ; (1 << shift) >= bitsPerWord; shift-- {
rotWords(&shifted, out, 1<<shift)
cmovWords(out, &shifted, lsbToAll(bits>>shift))
}
for ; shift < 9; shift-- {
rotBits(&shifted, out, 1<<shift)
cmovWords(out, &shifted, lsbToAll(bits>>shift))
}
}
type poly [N]uint16
func (in *poly) marshal(out []byte) {
p := in[:]
for len(p) >= 8 {
out[0] = byte(p[0])
out[1] = byte(p[0]>>8) | byte((p[1]&0x07)<<5)
out[2] = byte(p[1] >> 3)
out[3] = byte(p[1]>>11) | byte((p[2]&0x3f)<<2)
out[4] = byte(p[2]>>6) | byte((p[3]&0x01)<<7)
out[5] = byte(p[3] >> 1)
out[6] = byte(p[3]>>9) | byte((p[4]&0x0f)<<4)
out[7] = byte(p[4] >> 4)
out[8] = byte(p[4]>>12) | byte((p[5]&0x7f)<<1)
out[9] = byte(p[5]>>7) | byte((p[6]&0x03)<<6)
out[10] = byte(p[6] >> 2)
out[11] = byte(p[6]>>10) | byte((p[7]&0x1f)<<3)
out[12] = byte(p[7] >> 5)
p = p[8:]
out = out[13:]
}
// There are four remaining values.
out[0] = byte(p[0])
out[1] = byte(p[0]>>8) | byte((p[1]&0x07)<<5)
out[2] = byte(p[1] >> 3)
out[3] = byte(p[1]>>11) | byte((p[2]&0x3f)<<2)
out[4] = byte(p[2]>>6) | byte((p[3]&0x01)<<7)
out[5] = byte(p[3] >> 1)
out[6] = byte(p[3] >> 9)
}
func (out *poly) unmarshal(in []byte) bool {
p := out[:]
for i := 0; i < 87; i++ {
p[0] = uint16(in[0]) | uint16(in[1]&0x1f)<<8
p[1] = uint16(in[1]>>5) | uint16(in[2])<<3 | uint16(in[3]&3)<<11
p[2] = uint16(in[3]>>2) | uint16(in[4]&0x7f)<<6
p[3] = uint16(in[4]>>7) | uint16(in[5])<<1 | uint16(in[6]&0xf)<<9
p[4] = uint16(in[6]>>4) | uint16(in[7])<<4 | uint16(in[8]&1)<<12
p[5] = uint16(in[8]>>1) | uint16(in[9]&0x3f)<<7
p[6] = uint16(in[9]>>6) | uint16(in[10])<<2 | uint16(in[11]&7)<<10
p[7] = uint16(in[11]>>3) | uint16(in[12])<<5
p = p[8:]
in = in[13:]
}
// There are four coefficients left over
p[0] = uint16(in[0]) | uint16(in[1]&0x1f)<<8
p[1] = uint16(in[1]>>5) | uint16(in[2])<<3 | uint16(in[3]&3)<<11
p[2] = uint16(in[3]>>2) | uint16(in[4]&0x7f)<<6
p[3] = uint16(in[4]>>7) | uint16(in[5])<<1 | uint16(in[6]&0xf)<<9
if in[6]&0xf0 != 0 {
return false
}
out[N-1] = 0
var top int
for _, v := range out {
top += int(v)
}
out[N-1] = uint16(-top) % Q
return true
}
func (in *poly) marshalS3(out []byte) {
p := in[:]
for len(p) >= 5 {
out[0] = byte(p[0] + p[1]*3 + p[2]*9 + p[3]*27 + p[4]*81)
out = out[1:]
p = p[5:]
}
}
func (out *poly) unmarshalS3(in []byte) bool {
p := out[:]
for i := 0; i < 140; i++ {
c := in[0]
if c >= 243 {
return false
}
p[0] = uint16(c % 3)
p[1] = uint16((c / 3) % 3)
p[2] = uint16((c / 9) % 3)
p[3] = uint16((c / 27) % 3)
p[4] = uint16((c / 81) % 3)
p = p[5:]
in = in[1:]
}
out[N-1] = 0
return true
}
func (p *poly) modPhiN() {
for i := range p {
p[i] = (p[i] + Q - p[N-1]) % Q
}
}
func (out *poly) shortSample(in []byte) {
// b a result
// 00 00 00
// 00 01 01
// 00 10 10
// 00 11 11
// 01 00 10
// 01 01 00
// 01 10 01
// 01 11 11
// 10 00 01
// 10 01 10
// 10 10 00
// 10 11 11
// 11 00 11
// 11 01 11
// 11 10 11
// 11 11 11
// 1111 1111 1100 1001 1101 0010 1110 0100
// f f c 9 d 2 e 4
const lookup = uint32(0xffc9d2e4)
p := out[:]
for i := 0; i < 87; i++ {
v := binary.LittleEndian.Uint32(in)
v2 := (v & 0x55555555) + ((v >> 1) & 0x55555555)
for j := 0; j < 8; j++ {
p[j] = uint16(lookup >> ((v2 & 15) << 1) & 3)
v2 >>= 4
}
p = p[8:]
in = in[4:]
}
// There are four values remaining.
v := binary.LittleEndian.Uint32(in)
v2 := (v & 0x55555555) + ((v >> 1) & 0x55555555)
for j := 0; j < 4; j++ {
p[j] = uint16(lookup >> ((v2 & 15) << 1) & 3)
v2 >>= 4
}
out[N-1] = 0
}
func (out *poly) shortSamplePlus(in []byte) {
out.shortSample(in)
var sum uint16
for i := 0; i < N-1; i++ {
sum += mod3ResultToModQ(out[i] * out[i+1])
}
scale := 1 + (1 & (sum >> 12))
for i := 0; i < len(out); i += 2 {
out[i] = (out[i] * scale) % 3
}
}
func mul(out, scratch, a, b []uint16) {
const schoolbookLimit = 32
if len(a) < schoolbookLimit {
for i := 0; i < len(a)*2; i++ {
out[i] = 0
}
for i := range a {
for j := range b {
out[i+j] += a[i] * b[j]
}
}
return
}
lowLen := len(a) / 2
highLen := len(a) - lowLen
aLow, aHigh := a[:lowLen], a[lowLen:]
bLow, bHigh := b[:lowLen], b[lowLen:]
for i := 0; i < lowLen; i++ {
out[i] = aHigh[i] + aLow[i]
}
if highLen != lowLen {
out[lowLen] = aHigh[lowLen]
}
for i := 0; i < lowLen; i++ {
out[highLen+i] = bHigh[i] + bLow[i]
}
if highLen != lowLen {
out[highLen+lowLen] = bHigh[lowLen]
}
mul(scratch, scratch[2*highLen:], out[:highLen], out[highLen:highLen*2])
mul(out[lowLen*2:], scratch[2*highLen:], aHigh, bHigh)
mul(out, scratch[2*highLen:], aLow, bLow)
for i := 0; i < lowLen*2; i++ {
scratch[i] -= out[i] + out[lowLen*2+i]
}
if lowLen != highLen {
scratch[lowLen*2] -= out[lowLen*4]
}
for i := 0; i < 2*highLen; i++ {
out[lowLen+i] += scratch[i]
}
}
func (out *poly) mul(a, b *poly) {
var prod, scratch [2 * N]uint16
mul(prod[:], scratch[:], a[:], b[:])
for i := range out {
out[i] = (prod[i] + prod[i+N]) % Q
}
}
func (p3 *poly3) mulMod3(x, y *poly3) {
// (𝑥^n - 1) is a multiple of Φ(N) so we can work mod (𝑥^n - 1) here and
// (reduce mod Φ(N) afterwards.
x3 := *x
y3 := *y
s := x3.s[:]
a := x3.a[:]
sw := s[0]
aw := a[0]
p3.zero()
var shift uint
for i := 0; i < N; i++ {
p3.fmadd(sw, aw, &y3)
sw >>= 1
aw >>= 1
shift++
if shift == bitsPerWord {
s = s[1:]
a = a[1:]
sw = s[0]
aw = a[0]
shift = 0
}
y3.mulx()
}
p3.modPhiN()
}
// mod3ToModQ maps {0, 1, 2, 3} to {0, 1, Q-1, 0xffff}
// The case of n == 3 should never happen but is included so that modQToMod3
// can easily catch invalid inputs.
func mod3ToModQ(n uint16) uint16 {
return uint16(uint64(0xffff1fff00010000) >> (16 * n))
}
// modQToMod3 maps {0, 1, Q-1} to {(0, 0), (0, 1), (1, 0)} and also returns an int
// which is one if the input is in range and zero otherwise.
func modQToMod3(n uint16) (uint16, int) {
result := (n&3 - (n>>1)&1)
return result, subtle.ConstantTimeEq(int32(mod3ToModQ(result)), int32(n))
}
// mod3ResultToModQ maps {0, 1, 2, 4} to {0, 1, Q-1, 1}
func mod3ResultToModQ(n uint16) uint16 {
return ((((uint16(0x13) >> n) & 1) - 1) & 0x1fff) | ((uint16(0x12) >> n) & 1)
//shift := (uint(0x324) >> (2 * n)) & 3
//return uint16(uint64(0x00011fff00010000) >> (16 * shift))
}
// mulXMinus1 sets out to a×(𝑥 - 1) mod (𝑥^n - 1)
func (out *poly) mulXMinus1() {
// Multiplying by (𝑥 - 1) means negating each coefficient and adding in
// the value of the previous one.
origOut700 := out[700]
for i := N - 1; i > 0; i-- {
out[i] = (Q - out[i] + out[i-1]) % Q
}
out[0] = (Q - out[0] + origOut700) % Q
}
func (out *poly) lift(a *poly) {
// We wish to calculate a/(𝑥-1) mod Φ(N) over GF(3), where Φ(N) is the
// Nth cyclotomic polynomial, i.e. 1 + 𝑥 + … + 𝑥^700 (since N is prime).
// 1/(𝑥-1) has a fairly basic structure that we can exploit to speed this up:
//
// R.<x> = PolynomialRing(GF(3)…)
// inv = R.cyclotomic_polynomial(1).inverse_mod(R.cyclotomic_polynomial(n))
// list(inv)[:15]
// [1, 0, 2, 1, 0, 2, 1, 0, 2, 1, 0, 2, 1, 0, 2]
//
// This three-element pattern of coefficients repeats for the whole
// polynomial.
//
// Next define the overbar operator such that z̅ = z[0] +
// reverse(z[1:]). (Index zero of a polynomial here is the coefficient
// of the constant term. So index one is the coefficient of 𝑥 and so
// on.)
//
// A less odd way to define this is to see that z̅ negates the indexes,
// so z̅[0] = z[-0], z̅[1] = z[-1] and so on.
//
// The use of z̅ is that, when working mod (𝑥^701 - 1), vz[0] = <v,
// z̅>, vz[1] = <v, 𝑥z̅>, …. (Where <a, b> is the inner product: the sum
// of the point-wise products.) Although we calculated the inverse mod
// Φ(N), we can work mod (𝑥^N - 1) and reduce mod Φ(N) at the end.
// (That's because (𝑥^N - 1) is a multiple of Φ(N).)
//
// When working mod (𝑥^N - 1), multiplication by 𝑥 is a right-rotation
// of the list of coefficients.
//
// Thus we can consider what the pattern of z̅, 𝑥z̅, 𝑥^2z̅, … looks like:
//
// def reverse(xs):
// suffix = list(xs[1:])
// suffix.reverse()
// return [xs[0]] + suffix
//
// def rotate(xs):
// return [xs[-1]] + xs[:-1]
//
// zoverbar = reverse(list(inv) + [0])
// xzoverbar = rotate(reverse(list(inv) + [0]))
// x2zoverbar = rotate(rotate(reverse(list(inv) + [0])))
//
// zoverbar[:15]
// [1, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1]
// xzoverbar[:15]
// [0, 1, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0]
// x2zoverbar[:15]
// [2, 0, 1, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2]
//
// (For a formula for z̅, see lemma two of appendix B.)
//
// After the first three elements have been taken care of, all then have
// a repeating three-element cycle. The next value (𝑥^3z̅) involves
// three rotations of the first pattern, thus the three-element cycle
// lines up. However, the discontinuity in the first three elements
// obviously moves to a different position. Consider the difference
// between 𝑥^3z̅ and z̅:
//
// [x-y for (x,y) in zip(zoverbar, x3zoverbar)][:15]
// [0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
//
// This pattern of differences is the same for all elements, although it
// obviously moves right with the rotations.
//
// From this, we reach algorithm eight of appendix B.
// Handle the first three elements of the inner products.
out[0] = a[0] + a[2]
out[1] = a[1]
out[2] = 2*a[0] + a[2]
// Use the repeating pattern to complete the first three inner products.
for i := 3; i < 699; i += 3 {
out[0] += 2*a[i] + a[i+2]
out[1] += a[i] + 2*a[i+1]
out[2] += a[i+1] + 2*a[i+2]
}
// Handle the fact that the three-element pattern doesn't fill the
// polynomial exactly (since 701 isn't a multiple of three).
out[2] += a[700]
out[0] += 2 * a[699]
out[1] += a[699] + 2*a[700]
out[0] = out[0] % 3
out[1] = out[1] % 3
out[2] = out[2] % 3
// Calculate the remaining inner products by taking advantage of the
// fact that the pattern repeats every three cycles and the pattern of
// differences is moves with the rotation.
for i := 3; i < N; i++ {
// Add twice something is the same as subtracting when working
// mod 3. Doing it this way avoids underflow. Underflow is bad
// because "% 3" doesn't work correctly for negative numbers
// here since underflow will wrap to 2^16-1 and 2^16 isn't a
// multiple of three.
out[i] = (out[i-3] + 2*(a[i-2]+a[i-1]+a[i])) % 3
}
// Reduce mod Φ(N) by subtracting a multiple of out[700] from every
// element and convert to mod Q. (See above about adding twice as
// subtraction.)
v := out[700] * 2
for i := range out {
out[i] = mod3ToModQ((out[i] + v) % 3)
}
out.mulXMinus1()
}
func (a *poly) cswap(b *poly, swap uint16) {
for i := range a {
sum := swap & (a[i] ^ b[i])
a[i] ^= sum
b[i] ^= sum
}
}
func lt(a, b uint) uint {
if a < b {
return ^uint(0)
}
return 0
}
func bsMul(s1, a1, s2, a2 uint) (s3, a3 uint) {
s3 = (a1 & s2) ^ (s1 & a2)
a3 = (a1 & a2) ^ (s1 & s2)
return
}
func (out *poly3) invertMod3(in *poly3) {
// This algorithm follows algorithm 10 in the paper. (Although note that
// the paper appears to have a bug: k should start at zero, not one.)
// The best explanation for why it works is in the "Why it works"
// section of
// https://assets.onboardsecurity.com/static/downloads/NTRU/resources/NTRUTech014.pdf.
var k uint
degF, degG := uint(N-1), uint(N-1)
var b, c, g poly3
f := *in
for i := range g.a {
g.a[i] = ^uint(0)
}
b.a[0] = 1
var f0s, f0a uint
stillGoing := ^uint(0)
for i := 0; i < 2*(N-1)-1; i++ {
ss, sa := bsMul(f.s[0], f.a[0], g.s[0], g.a[0])
ss, sa = sa&stillGoing&1, ss&stillGoing&1
shouldSwap := ^uint(int((ss|sa)-1)>>(bitsPerWord-1)) & lt(degF, degG)
f.cswap(&g, shouldSwap)
b.cswap(&c, shouldSwap)
degF, degG = (degG&shouldSwap)|(degF & ^shouldSwap), (degF&shouldSwap)|(degG&^shouldSwap)
f.fmadd(ss, sa, &g)
b.fmadd(ss, sa, &c)
f.divx()
f.s[wordsPerPoly-1] &= ((1 << bitsInLastWord) - 1) >> 1
f.a[wordsPerPoly-1] &= ((1 << bitsInLastWord) - 1) >> 1
c.mulx()
c.s[0] &= ^uint(1)
c.a[0] &= ^uint(1)
degF--
k += 1 & stillGoing
f0s = (stillGoing & f.s[0]) | (^stillGoing & f0s)
f0a = (stillGoing & f.a[0]) | (^stillGoing & f0a)
stillGoing = ^uint(int(degF-1) >> (bitsPerWord - 1))
}
k -= N & lt(N, k)
*out = b
out.rot(k)
out.mulConst(f0s, f0a)
out.modPhiN()
}
func (out *poly) invertMod2(a *poly) {
// This algorithm follows mix of algorithm 10 in the paper and the first
// page of the PDF linked below. (Although note that the paper appears
// to have a bug: k should start at zero, not one.) The best explanation
// for why it works is in the "Why it works" section of
// https://assets.onboardsecurity.com/static/downloads/NTRU/resources/NTRUTech014.pdf.
var k uint
degF, degG := uint(N-1), uint(N-1)
var f poly2
f.fromDiscrete(a)
var b, c, g poly2
g.setPhiN()
b[0] = 1
stillGoing := ^uint(0)
for i := 0; i < 2*(N-1)-1; i++ {
s := uint(f[0]&1) & stillGoing
shouldSwap := ^(s - 1) & lt(degF, degG)
f.cswap(&g, shouldSwap)
b.cswap(&c, shouldSwap)
degF, degG = (degG&shouldSwap)|(degF & ^shouldSwap), (degF&shouldSwap)|(degG&^shouldSwap)
f.fmadd(s, &g)
b.fmadd(s, &c)
f.rshift1()
c.lshift1()
degF--
k += 1 & stillGoing
stillGoing = ^uint(int(degF-1) >> (bitsPerWord - 1))
}
k -= N & lt(N, k)
b.rot(k)
out.fromMod2(&b)
}
func (out *poly) invert(origA *poly) {
// Inversion mod Q, which is done based on the result of inverting mod
// 2. See the NTRU paper, page three.
var a, tmp, tmp2, b poly
b.invertMod2(origA)
// Negate a.
for i := range a {
a[i] = Q - origA[i]
}
// We are working mod Q=2**13 and we need to iterate ceil(log_2(13))
// times, which is four.
for i := 0; i < 4; i++ {
tmp.mul(&a, &b)
tmp[0] += 2
tmp2.mul(&b, &tmp)
b = tmp2
}
*out = b
}
type PublicKey struct {
h poly
}
func ParsePublicKey(in []byte) (*PublicKey, bool) {
ret := new(PublicKey)
if !ret.h.unmarshal(in) {
return nil, false
}
return ret, true
}
func (pub *PublicKey) Marshal() []byte {
ret := make([]byte, modQBytes)
pub.h.marshal(ret)
return ret
}
func (pub *PublicKey) Encap(rand io.Reader) (ciphertext []byte, sharedKey []byte) {
var randBytes [352 + 352]byte
if _, err := io.ReadFull(rand, randBytes[:]); err != nil {
panic("rand failed")
}
var m, r poly
m.shortSample(randBytes[:352])
r.shortSample(randBytes[352:])
var mBytes, rBytes [mod3Bytes]byte
m.marshalS3(mBytes[:])
r.marshalS3(rBytes[:])
ciphertext = pub.owf(&m, &r)
h := sha256.New()
h.Write([]byte("shared key\x00"))
h.Write(mBytes[:])
h.Write(rBytes[:])
h.Write(ciphertext)
sharedKey = h.Sum(nil)
return ciphertext, sharedKey
}
func (pub *PublicKey) owf(m, r *poly) []byte {
for i := range r {
r[i] = mod3ToModQ(r[i])
}
var mq poly
mq.lift(m)
var e poly
e.mul(r, &pub.h)
for i := range e {
e[i] = (e[i] + mq[i]) % Q
}
ret := make([]byte, modQBytes)
e.marshal(ret[:])
return ret
}
type PrivateKey struct {
PublicKey
f, fp poly3
hInv poly
hmacKey [32]byte
}
func (priv *PrivateKey) Marshal() []byte {
var ret [2*mod3Bytes + modQBytes]byte
priv.f.marshal(ret[:])
priv.fp.marshal(ret[mod3Bytes:])
priv.h.marshal(ret[2*mod3Bytes:])
return ret[:]
}
func (priv *PrivateKey) Decap(ciphertext []byte) (sharedKey []byte, ok bool) {
if len(ciphertext) != modQBytes {
return nil, false
}
var e poly
if !e.unmarshal(ciphertext) {
return nil, false
}
var f poly
f.fromMod3ToModQ(&priv.f)
var v1, m poly
v1.mul(&e, &f)
var v13 poly3
v13.fromDiscreteMod3(&v1)
// Note: v13 is not reduced mod phi(n).
var m3 poly3
m3.mulMod3(&v13, &priv.fp)
m3.modPhiN()
m.fromMod3(&m3)
var mLift, delta poly
mLift.lift(&m)
for i := range delta {
delta[i] = (e[i] - mLift[i] + Q) % Q
}
delta.mul(&delta, &priv.hInv)
delta.modPhiN()
var r poly3
allOk := r.fromModQ(&delta)
var mBytes, rBytes [mod3Bytes]byte
m.marshalS3(mBytes[:])
r.marshal(rBytes[:])
var rPoly poly
rPoly.fromMod3(&r)
expectedCiphertext := priv.PublicKey.owf(&m, &rPoly)
allOk &= subtle.ConstantTimeCompare(ciphertext, expectedCiphertext)
hmacHash := hmac.New(sha256.New, priv.hmacKey[:])
hmacHash.Write(ciphertext)
hmacDigest := hmacHash.Sum(nil)
h := sha256.New()
h.Write([]byte("shared key\x00"))
h.Write(mBytes[:])
h.Write(rBytes[:])
h.Write(ciphertext)
sharedKey = h.Sum(nil)
mask := uint8(allOk - 1)
for i := range sharedKey {
sharedKey[i] = (sharedKey[i] & ^mask) | (hmacDigest[i] & mask)
}
return sharedKey, true
}
func GenerateKey(rand io.Reader) PrivateKey {
var randBytes [352 + 352]byte
if _, err := io.ReadFull(rand, randBytes[:]); err != nil {
panic("rand failed")
}
var f poly
f.shortSamplePlus(randBytes[:352])
var priv PrivateKey
priv.f.fromDiscrete(&f)
priv.fp.invertMod3(&priv.f)
var g poly
g.shortSamplePlus(randBytes[352:])
var pgPhi1 poly
for i := range g {
pgPhi1[i] = mod3ToModQ(g[i])
}
for i := range pgPhi1 {
pgPhi1[i] = (pgPhi1[i] * 3) % Q
}
pgPhi1.mulXMinus1()
var fModQ poly
fModQ.fromMod3ToModQ(&priv.f)
var pfgPhi1 poly
pfgPhi1.mul(&fModQ, &pgPhi1)
var i poly
i.invert(&pfgPhi1)
priv.h.mul(&i, &pgPhi1)
priv.h.mul(&priv.h, &pgPhi1)
priv.hInv.mul(&i, &fModQ)
priv.hInv.mul(&priv.hInv, &fModQ)
return priv
}