Last active
September 12, 2023 18:47
-
-
Save itzmeanjan/38d506a69073bdeb0933245401f42186 to your computer and use it in GitHub Desktop.
Git Patch for generating Known Answer Tests ( KATs ) from FrodoKEM Reference Implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
diff --git a/FrodoKEM/python3/frodokem.py b/FrodoKEM/python3/frodokem.py | |
index 731cb0e..c701108 100644 | |
--- a/FrodoKEM/python3/frodokem.py | |
+++ b/FrodoKEM/python3/frodokem.py | |
@@ -4,6 +4,7 @@ | |
import bitstring | |
import math | |
+import sys | |
import secrets | |
import struct | |
import warnings | |
@@ -454,7 +455,7 @@ class FrodoKEM(object): | |
A[i][j] = c_i[j] % self.q | |
return A | |
- def kem_keygen(self): | |
+ def kem_keygen(self, fh = sys.stdout): | |
"""Generate a public key / secret key pair (FrodoKEM specification, | |
Algorithm 12)""" | |
# 1. Choose uniformly random seeds s || seedSE || z | |
@@ -463,6 +464,11 @@ class FrodoKEM(object): | |
s = bytes(s_seedSE_z[0:self.len_s_bytes]) | |
seedSE = bytes(s_seedSE_z[self.len_s_bytes : self.len_s_bytes + self.len_seedSE_bytes]) | |
z = bytes(s_seedSE_z[self.len_s_bytes + self.len_seedSE_bytes : self.len_s_bytes + self.len_seedSE_bytes + self.len_z_bytes]) | |
+ | |
+ print(f's = {s.hex()}', file=fh) | |
+ print(f'seedSE = {seedSE.hex()}', file=fh) | |
+ print(f'z = {z.hex()}', file=fh) | |
+ | |
# 2. Generate pseudorandom seed seedA = SHAKE(z, len_seedA) (length in bits) | |
seedA = self.shake(z, self.len_seedA_bytes) | |
self.__print_intermediate_value("seedA", seedA) | |
@@ -500,9 +506,13 @@ class FrodoKEM(object): | |
sk.append(pkh) | |
sk = sk.bytes | |
assert len(sk) == self.len_sk_bytes | |
+ | |
+ print(f'pkey = {pk.hex()}', file=fh) | |
+ print(f'skey = {sk.hex()}', file=fh) | |
+ | |
return (pk, sk) | |
- def kem_encaps(self, pk): | |
+ def kem_encaps(self, pk, fh = sys.stdout): | |
"""Encapsulate against a public key to create a ciphertext and shared secret | |
(FrodoKEM specification, Algorithm 13)""" | |
# Parse pk = seedA || b | |
@@ -513,6 +523,10 @@ class FrodoKEM(object): | |
mu_salt = self.randombytes(self.len_mu_bytes + self.len_salt_bytes) | |
mu = mu_salt[0:self.len_mu_bytes] | |
salt = mu_salt[self.len_mu_bytes:self.len_mu_bytes + self.len_salt_bytes] | |
+ | |
+ print(f'μ = {mu.hex()}', file=fh) | |
+ print(f'salt = {salt.hex()}', file=fh) | |
+ | |
self.__print_intermediate_value("mu", mu) | |
self.__print_intermediate_value("salt", salt) | |
# 2. pkh = SHAKE(pk, len_pkh) | |
@@ -563,6 +577,11 @@ class FrodoKEM(object): | |
ct = c1 + c2 + salt | |
assert len(ct) == self.len_ct_bytes | |
assert len(ss) == self.len_ss_bytes | |
+ | |
+ print(f'ct = {ct.hex()}', file=fh) | |
+ print(f'ss = {ss.hex()}', file=fh) | |
+ print('', file=fh) | |
+ | |
return (ct, ss) | |
def kem_decaps(self, sk, ct): | |
@@ -660,3 +679,36 @@ class FrodoKEM(object): | |
ss = self.shake(c1 + c2 + salt + kbar, self.len_ss_bytes) | |
assert len(ss) == self.len_ss_bytes | |
return ss | |
+ | |
+if __name__ == '__main__': | |
+ KNOWN_ANSWER_TEST_COUNT = 64 | |
+ | |
+ with open('FrodoKEM640_KAT.txt', 'w') as fh: | |
+ frodo640_shake = FrodoKEM("FrodoKEM-640-SHAKE") | |
+ for _ in range(KNOWN_ANSWER_TEST_COUNT): | |
+ (pk, sk) = frodo640_shake.kem_keygen(fh) | |
+ (ct, ss0) = frodo640_shake.kem_encaps(pk, fh) | |
+ ss1 = frodo640_shake.kem_decaps(sk, ct) | |
+ | |
+ assert ss0 == ss1, "[error] Shared secrets don't match for FrodoKEM640-SHAKE" | |
+ print(f'Generated {KNOWN_ANSWER_TEST_COUNT} KATs for FrodoKEM-640-SHAKE, written to FrodoKEM640_KAT.txt') | |
+ | |
+ with open('FrodoKEM976_KAT.txt', 'w') as fh: | |
+ frodo976_shake = FrodoKEM("FrodoKEM-976-SHAKE") | |
+ for _ in range(KNOWN_ANSWER_TEST_COUNT): | |
+ (pk, sk) = frodo976_shake.kem_keygen(fh) | |
+ (ct, ss0) = frodo976_shake.kem_encaps(pk, fh) | |
+ ss1 = frodo976_shake.kem_decaps(sk, ct) | |
+ | |
+ assert ss0 == ss1, "[error] Shared secrets don't match for FrodoKEM976-SHAKE" | |
+ print(f'Generated {KNOWN_ANSWER_TEST_COUNT} KATs for FrodoKEM-976-SHAKE, written to FrodoKEM976_KAT.txt') | |
+ | |
+ with open('FrodoKEM1344_KAT.txt', 'w') as fh: | |
+ frodo1344_shake = FrodoKEM("FrodoKEM-1344-SHAKE") | |
+ for _ in range(KNOWN_ANSWER_TEST_COUNT): | |
+ (pk, sk) = frodo1344_shake.kem_keygen(fh) | |
+ (ct, ss0) = frodo1344_shake.kem_encaps(pk, fh) | |
+ ss1 = frodo1344_shake.kem_decaps(sk, ct) | |
+ | |
+ assert ss0 == ss1, "[error] Shared secrets don't match for FrodoKEM1344-SHAKE" | |
+ print(f'Generated {KNOWN_ANSWER_TEST_COUNT} KATs for FrodoKEM-1344-SHAKE, written to FrodoKEM1344_KAT.txt') | |
diff --git a/eFrodoKEM/python3/efrodokem.py b/eFrodoKEM/python3/efrodokem.py | |
index 07156b2..64b988c 100644 | |
--- a/eFrodoKEM/python3/efrodokem.py | |
+++ b/eFrodoKEM/python3/efrodokem.py | |
@@ -4,6 +4,7 @@ | |
import bitstring | |
import math | |
+import sys | |
import secrets | |
import struct | |
import warnings | |
@@ -448,7 +449,7 @@ class FrodoKEM(object): | |
A[i][j] = c_i[j] % self.q | |
return A | |
- def kem_keygen(self): | |
+ def kem_keygen(self, fh = sys.stdout): | |
"""Generate a public key / secret key pair (FrodoKEM specification, | |
Algorithm 12)""" | |
# 1. Choose uniformly random seeds s || seedSE || z | |
@@ -457,6 +458,11 @@ class FrodoKEM(object): | |
s = bytes(s_seedSE_z[0:self.len_s_bytes]) | |
seedSE = bytes(s_seedSE_z[self.len_s_bytes : self.len_s_bytes + self.len_seedSE_bytes]) | |
z = bytes(s_seedSE_z[self.len_s_bytes + self.len_seedSE_bytes : self.len_s_bytes + self.len_seedSE_bytes + self.len_z_bytes]) | |
+ | |
+ print(f's = {s.hex()}', file=fh) | |
+ print(f'seedSE = {seedSE.hex()}', file=fh) | |
+ print(f'z = {z.hex()}', file=fh) | |
+ | |
# 2. Generate pseudorandom seed seedA = SHAKE(z, len_seedA) (length in bits) | |
seedA = self.shake(z, self.len_seedA_bytes) | |
self.__print_intermediate_value("seedA", seedA) | |
@@ -494,9 +500,13 @@ class FrodoKEM(object): | |
sk.append(pkh) | |
sk = sk.bytes | |
assert len(sk) == self.len_sk_bytes | |
+ | |
+ print(f'pkey = {pk.hex()}', file=fh) | |
+ print(f'skey = {sk.hex()}', file=fh) | |
+ | |
return (pk, sk) | |
- def kem_encaps(self, pk): | |
+ def kem_encaps(self, pk, fh = sys.stdout): | |
"""Encapsulate against a public key to create a ciphertext and shared secret | |
(FrodoKEM specification, Algorithm 13)""" | |
# Parse pk = seedA || b | |
@@ -505,6 +515,9 @@ class FrodoKEM(object): | |
b = pk[self.len_seedA_bytes:] | |
# 1. Choose a uniformly random key mu in {0,1}^len_mu (length in bits) | |
mu = self.randombytes(self.len_mu_bytes) | |
+ | |
+ print(f'μ = {mu.hex()}', file=fh) | |
+ | |
self.__print_intermediate_value("mu", mu) | |
# 2. pkh = SHAKE(pk, len_pkh) | |
pkh = self.shake(pk, self.len_pkh_bytes) | |
@@ -554,6 +567,11 @@ class FrodoKEM(object): | |
ct = c1 + c2 | |
assert len(ct) == self.len_ct_bytes | |
assert len(ss) == self.len_ss_bytes | |
+ | |
+ print(f'ct = {ct.hex()}', file=fh) | |
+ print(f'ss = {ss.hex()}', file=fh) | |
+ print('', file=fh) | |
+ | |
return (ct, ss) | |
def kem_decaps(self, sk, ct): | |
@@ -648,3 +666,36 @@ class FrodoKEM(object): | |
ss = self.shake(c1 + c2 + kbar, self.len_ss_bytes) | |
assert len(ss) == self.len_ss_bytes | |
return ss | |
+ | |
+if __name__ == '__main__': | |
+ KNOWN_ANSWER_TEST_COUNT = 64 | |
+ | |
+ with open('eFrodoKEM640_KAT.txt', 'w') as fh: | |
+ frodo640_shake = FrodoKEM("FrodoKEM-640-SHAKE") | |
+ for _ in range(KNOWN_ANSWER_TEST_COUNT): | |
+ (pk, sk) = frodo640_shake.kem_keygen(fh) | |
+ (ct, ss0) = frodo640_shake.kem_encaps(pk, fh) | |
+ ss1 = frodo640_shake.kem_decaps(sk, ct) | |
+ | |
+ assert ss0 == ss1, "[error] Shared secrets don't match for FrodoKEM640-SHAKE" | |
+ print(f'Generated {KNOWN_ANSWER_TEST_COUNT} KATs for FrodoKEM-640-SHAKE, written to eFrodoKEM640_KAT.txt') | |
+ | |
+ with open('eFrodoKEM976_KAT.txt', 'w') as fh: | |
+ frodo976_shake = FrodoKEM("FrodoKEM-976-SHAKE") | |
+ for _ in range(KNOWN_ANSWER_TEST_COUNT): | |
+ (pk, sk) = frodo976_shake.kem_keygen(fh) | |
+ (ct, ss0) = frodo976_shake.kem_encaps(pk, fh) | |
+ ss1 = frodo976_shake.kem_decaps(sk, ct) | |
+ | |
+ assert ss0 == ss1, "[error] Shared secrets don't match for FrodoKEM976-SHAKE" | |
+ print(f'Generated {KNOWN_ANSWER_TEST_COUNT} KATs for FrodoKEM-976-SHAKE, written to eFrodoKEM976_KAT.txt') | |
+ | |
+ with open('eFrodoKEM1344_KAT.txt', 'w') as fh: | |
+ frodo1344_shake = FrodoKEM("FrodoKEM-1344-SHAKE") | |
+ for _ in range(KNOWN_ANSWER_TEST_COUNT): | |
+ (pk, sk) = frodo1344_shake.kem_keygen(fh) | |
+ (ct, ss0) = frodo1344_shake.kem_encaps(pk, fh) | |
+ ss1 = frodo1344_shake.kem_decaps(sk, ct) | |
+ | |
+ assert ss0 == ss1, "[error] Shared secrets don't match for FrodoKEM1344-SHAKE" | |
+ print(f'Generated {KNOWN_ANSWER_TEST_COUNT} KATs for FrodoKEM-1344-SHAKE, written to eFrodoKEM1344_KAT.txt') |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Overview
You can follow below steps for generating known answer tests (KATs) for {e}FrodoKEM-{640, 976, 1344} ( with SHAKE128 for generation of matrix A ), which can be used with my C++ library implementation of FrodoKEM ( more @ https://github.com/itzmeanjan/frodokem ) for ensuring its functional correctness and conformance with the specification.
Steps
frodokem_kat.patch
into directoryPQCrypto-LWEKE
.