in python3/frodokem.py [0:0]
def kem_decaps(self, sk, ct):
"""Decapsulate a ciphertext using a secret key to obtain a shared secret
(FrodoKEM specification, Algorithm 14)"""
# Parse ct = c1 || c2
assert len(ct) == self.len_ct_bytes, "Incorrect ciphertext length"
offset = 0; length = int(self.mbar * self.n * self.D / 8)
c1 = ct[offset:offset+length]
self.__print_intermediate_value("c1", c1)
offset += length; length = int(self.mbar * self.nbar * self.D / 8)
c2 = ct[offset:offset+length]
self.__print_intermediate_value("c2", c2)
# Parse sk = (s || seedA || b, S^T, pkh)
assert len(sk) == self.len_sk_bytes
offset = 0; length = self.len_s_bytes
s = sk[offset:offset+length]
self.__print_intermediate_value("s", s)
offset += length; length = self.len_seedA_bytes
seedA = sk[offset:offset+length]
self.__print_intermediate_value("seedA", seedA)
offset += length; length = int(self.D * self.n * self.nbar / 8)
b = sk[offset:offset+length]
self.__print_intermediate_value("b", b)
offset += length; length = int(self.n * self.nbar * 16 / 8)
Sbytes = bitstring.ConstBitStream(sk[offset:offset+length])
Stransposed = [[0 for j in range(self.n)] for i in range(self.nbar)]
for i in range(self.nbar):
for j in range(self.n):
Stransposed[i][j] = Sbytes.read('intle:16')
self.__print_intermediate_value("S^T", Stransposed)
S = self.__matrix_transpose(Stransposed)
offset += length; length = self.len_pkh_bytes
pkh = sk[offset:offset+length]
self.__print_intermediate_value("pkh", pkh)
# 1. B' = Frodo.Unpack(c1, mbar, n)
Bprime = self.unpack(c1, self.mbar, self.n)
self.__print_intermediate_value("B'", Bprime)
# 2. C = Frodo.Unpack(c2, mbar, nbar)
C = self.unpack(c2, self.mbar, self.nbar)
self.__print_intermediate_value("C", C)
# 3. M = C - B' S
BprimeS = self.__matrix_mul(Bprime, S)
self.__print_intermediate_value("B'S", BprimeS)
M = self.__matrix_sub(C, BprimeS)
self.__print_intermediate_value("M", M)
# 4. mu' = Frodo.Decode(M)
muprime = self.decode(M)
self.__print_intermediate_value("mu'", muprime)
# 5. Parse pk = seedA || b
# (done above)
# 6. seedSE' || k' = SHAKE(pkh || mu', len_seedSE + len_k) (length in bits)
seedSEprime_kprime = self.shake(pkh + muprime, self.len_seedSE_bytes + self.len_k_bytes)
seedSEprime = seedSEprime_kprime[0:self.len_seedSE_bytes]
self.__print_intermediate_value("seedSE'", seedSEprime)
kprime = seedSEprime_kprime[self.len_seedSE_bytes:self.len_seedSE_bytes + self.len_k_bytes]
self.__print_intermediate_value("k'", kprime)
# 7. r = SHAKE(0x96 || seedSE', 2*mbar*n + mbar*nbar*len_chi) (length in bits)
rbytes = self.shake(bytes(b'\x96') + seedSEprime, (2 * self.mbar * self.n + self.mbar * self.mbar) * self.len_chi_bytes)
r = [struct.unpack_from('<H', rbytes, 2*i)[0] for i in range(2 * self.mbar * self.n + self.mbar * self.nbar)]
self.__print_intermediate_value("r", r)
# 8. S' = Frodo.SampleMatrix(r[0 .. mbar*n-1], mbar, n)
Sprime = self.sample_matrix(r[0 : self.mbar * self.n], self.mbar, self.n)
self.__print_intermediate_value("S'", Sprime)
# 9. E' = Frodo.SampleMatrix(r[mbar*n .. 2*mbar*n-1], mbar, n)
Eprime = self.sample_matrix(r[self.mbar * self.n : 2 * self.mbar * self.n], self.mbar, self.n)
self.__print_intermediate_value("E'", Eprime)
# 10. A = Frodo.Gen(seedA)
A = self.gen(seedA)
# 11. B'' = S' A + E'
Bprimeprime = self.__matrix_add(self.__matrix_mul(Sprime, A), Eprime)
self.__print_intermediate_value("B''", Bprimeprime)
# 12. E'' = Frodo.SampleMatrix(r[2*mbar*n .. 2*mbar*n + mbar*nbar-1], mbar, n)
Eprimeprime = self.sample_matrix(r[2 * self.mbar * self.n : 2 * self.mbar * self.n + self.mbar * self.nbar], self.mbar, self.nbar)
self.__print_intermediate_value("E''", Eprimeprime)
# 13. B = Frodo.Unpack(b, n, nbar)
B = self.unpack(b, self.n, self.nbar)
self.__print_intermediate_value("B", B)
# 14. V = S' B + E''
V = self.__matrix_add(self.__matrix_mul(Sprime, B), Eprimeprime)
self.__print_intermediate_value("V", V)
# 15. C' = V + Frodo.Encode(muprime)
Cprime = self.__matrix_add(V, self.encode(muprime))
self.__print_intermediate_value("C'", Cprime)
# 16. (in constant time) kbar = kprime if (B' || C == B'' || C') else kbar = s
# Needs to avoid branching on secret data as per:
# Qian Guo, Thomas Johansson, Alexander Nilsson. A key-recovery timing attack on post-quantum
# primitives using the Fujisaki-Okamoto transformation and its application on FrodoKEM. In CRYPTO 2020.
use_kprime = self.__ctverify(Bprime + C, Bprimeprime + Cprime)
kbar = self.__ctselect(kprime, s, use_kprime)
# 17. ss = SHAKE(c1 || c2 || kbar, len_ss) (length in bits)
ss = self.shake(c1 + c2 + kbar, self.len_ss_bytes)
assert len(ss) == self.len_ss_bytes
return ss