Improved the model:

 * added CRT support
 * fixed bug in systolic array when operand width is not a multiple of array width

2 files changed, 132 insertions, 15 deletions

diff --git a/test/format_test_vectors.py b/test/format_test_vectors.py
index dd8670d..21b9262 100644
--- a/test/format_test_vectors.py
+++ b/test/format_test_vectors.py
@@ -79,6 +79,46 @@ def read_secret(key):
 	openssl_secret = openssl_secret.replace(" ", "")	
 	return openssl_secret
 
+#
+# read part of private key from file
+#
+def read_prime1(key):
+	openssl_command = ["openssl", "rsa", "-in", key + ".key", "-noout", "-text"]
+	openssl_stdout = subprocess.check_output(openssl_command).decode("utf-8")
+	openssl_secret = string_between(openssl_stdout, "prime1", "prime2")
+	openssl_secret = openssl_secret.replace(":", "")
+	openssl_secret = openssl_secret.replace("\n", "")
+	openssl_secret = openssl_secret.replace(" ", "")	
+	return openssl_secret
+def read_prime2(key):
+	openssl_command = ["openssl", "rsa", "-in", key + ".key", "-noout", "-text"]
+	openssl_stdout = subprocess.check_output(openssl_command).decode("utf-8")
+	openssl_secret = string_between(openssl_stdout, "prime2", "exponent1")
+	openssl_secret = openssl_secret.replace(":", "")
+	openssl_secret = openssl_secret.replace("\n", "")
+	openssl_secret = openssl_secret.replace(" ", "")	
+	return openssl_secret
+
+#
+# read prive exponent from file
+#
+def read_exponent1(key):
+	openssl_command = ["openssl", "rsa", "-in", key + ".key", "-noout", "-text"]
+	openssl_stdout = subprocess.check_output(openssl_command).decode("utf-8")
+	openssl_secret = string_between(openssl_stdout, "exponent1", "exponent2")
+	openssl_secret = openssl_secret.replace(":", "")
+	openssl_secret = openssl_secret.replace("\n", "")
+	openssl_secret = openssl_secret.replace(" ", "")	
+	return openssl_secret
+def read_exponent2(key):
+	openssl_command = ["openssl", "rsa", "-in", key + ".key", "-noout", "-text"]
+	openssl_stdout = subprocess.check_output(openssl_command).decode("utf-8")
+	openssl_secret = string_between(openssl_stdout, "exponent2", "coefficient")
+	openssl_secret = openssl_secret.replace(":", "")
+	openssl_secret = openssl_secret.replace("\n", "")
+	openssl_secret = openssl_secret.replace(" ", "")	
+	return openssl_secret
+
 # 
 # https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
 #
@@ -99,13 +139,19 @@ def modinv(a, m):
 #
 # format one test vector
 #
-def format_c_header(f, key, n, m, d, s):
+def format_c_header(f, key, n, m, d, s, p, q, dp, dq, mp, mq):
 
 		# write all numbers in vector
-	format_c_array(f, n, "#define N_" + str(key) + " \\\n")
-	format_c_array(f, m, "#define M_" + str(key) + " \\\n")
-	format_c_array(f, d, "#define D_" + str(key) + " \\\n")
-	format_c_array(f, s, "#define S_" + str(key) + " \\\n")
+	format_c_array(f, n,  "#define N_"  + str(key) + " \\\n")
+	format_c_array(f, m,  "#define M_"  + str(key) + " \\\n")
+	format_c_array(f, d,  "#define D_"  + str(key) + " \\\n")
+	format_c_array(f, s,  "#define S_"  + str(key) + " \\\n")
+	format_c_array(f, p,  "#define P_"  + str(key) + " \\\n")
+	format_c_array(f, q,  "#define Q_"  + str(key) + " \\\n")
+	format_c_array(f, dp, "#define DP_" + str(key) + " \\\n")
+	format_c_array(f, dq, "#define DQ_" + str(key) + " \\\n")
+	format_c_array(f, mp, "#define MP_" + str(key) + " \\\n")
+	format_c_array(f, mq, "#define MQ_" + str(key) + " \\\n")
 
 #
 # calculate Montgomery factor
@@ -274,20 +320,43 @@ if __name__ == "__main__":
 	for key in keys:
 	
 			# prepare all the numbers
-		modulus = int(read_modulus(key), 16)		# read number n from .key file
-		message = int(read_message(key), 16)		# read number m from .txt file
-		secret  = int(read_secret(key),  16)		# read number d from .key file
-		signature = pow(message, secret, modulus)	# calculate signature
+		modulus = int(read_modulus(key), 16)			# read number n from .key file
+		message = int(read_message(key), 16)			# read number m from .txt file
+		secret  = int(read_secret(key),  16)			# read number d from .key file
+		signature = pow(message, secret, modulus)		# calculate signature
+		prime1 = int(read_prime1(key), 16)				# read p
+		prime2 = int(read_prime2(key), 16)				# read q
+		exponent1 = int(read_exponent1(key), 16)		# read dp
+		exponent2 = int(read_exponent2(key), 16)		# read dq
+		message1 = pow(message, exponent1, prime1)		# calculate mp = m ^ dp mod p
+		message2 = pow(message, exponent2, prime2)		# calculate mq = m ^ dq mod q
+		coefficient = modinv(prime2, prime1)			# calculate
+
+			# do CRT to make sure everything is correct
+		h = coefficient * (message1 - message2) % prime1
+		crt = message2 + h * prime2
 		
 			# print all the numbers
 		print("key = " + key)
-		print("  modulus   = " + hex(modulus))
-		print("  message   = " + hex(message))
-		print("  secret    = " + hex(secret))
-		print("  signature = " + hex(signature))
-
+		print("  modulus     = " + hex(modulus))
+		print("  message     = " + hex(message))
+		print("  secret      = " + hex(secret))
+		print("  signature   = " + hex(signature))
+		print("  prime1      = " + hex(prime1))
+		print("  prime2      = " + hex(prime2))
+		print("  exponent1   = " + hex(exponent1))
+		print("  exponent2   = " + hex(exponent2))
+		print("  message1    = " + hex(message1))
+		print("  message2    = " + hex(message2))
+		print("  coefficient = " + hex(coefficient))
+		print("  crt         = " + hex(crt))
+		
+			# check
+		if crt != signature:
+			raise Exception("Error, crt != signature (?)")			
+			
 			# format numbers and write to file
-		format_c_header(file_h, key, modulus, message, secret, signature)
+		format_c_header(file_h, key, modulus, message, secret, signature, prime1, prime2, exponent1, exponent2, message1, message2)
 		format_verilog_include(file_v, key, modulus, message)
 
 
diff --git a/test/modexp_fpga_model_vectors.h b/test/modexp_fpga_model_vectors.h
index d889ada..622b16c 100644
--- a/test/modexp_fpga_model_vectors.h
+++ b/test/modexp_fpga_model_vectors.h
@@ -20,6 +20,30 @@
 	 0xa76b945b, 0x49a3f645, 0x76801499, 0xb98e6a16, \
 	 0xd2467b6a, 0x75b7d614, 0x0fff0fde, 0xb31d1819}
 
+#define P_384 \
+	{0xe9ac4cf6, 0x03b2d80a, 0x7f1d091e, 0x49d5f1a0, \
+	 0xac2ae4ff, 0xbf9bf375}
+
+#define Q_384 \
+	{0xc1468f3e, 0xc6909231, 0x5a4d74ba, 0x477b303f, \
+	 0x4b2e10d1, 0x1f44e815}
+
+#define DP_384 \
+	{0x69b6c286, 0x95fbc613, 0x51988034, 0x8cb0d684, \
+	 0x9aff38e4, 0x9ef9ddb5}
+
+#define DQ_384 \
+	{0x1eda82b7, 0x84bf4377, 0x39712ff7, 0x24be179f, \
+	 0xa302c190, 0x80ab6159}
+
+#define MP_384 \
+	{0x9e163bb5, 0x35e718cb, 0xcde52b7b, 0x5db8552b, \
+	 0x46a300e0, 0x34f91e6b}
+
+#define MQ_384 \
+	{0x7b01a724, 0x90f0d5f9, 0x9e237ce5, 0x6d31fd28, \
+	 0x4ecb9dad, 0x58bf366a}
+
 #define N_512 \
 	{0xef78b4ed, 0xaee1cc78, 0x659b9935, 0x39d5f5e1, \
 	 0xa47c2b29, 0x5a38e8c4, 0x85e2b846, 0xa354614f, \
@@ -44,3 +68,27 @@
 	 0xfd1e029d, 0xfe887387, 0x4312635f, 0xb2b54b8d, \
 	 0x5d3b379e, 0x161eaa4f, 0xedfd932b, 0x780f0203}
 
+#define P_512 \
+	{0xfedea889, 0x97cfdb79, 0xcca87074, 0xe5abcda1, \
+	 0x3be201c4, 0xc416fd15, 0xf2130931, 0x61ff5937}
+
+#define Q_512 \
+	{0xf0889147, 0x5aa60f93, 0xb9927d86, 0x8f795c5c, \
+	 0x8e98dcf2, 0xad3aad74, 0x9441583a, 0x967dce41}
+
+#define DP_512 \
+	{0x2504d437, 0xfffbe9e5, 0xfc0aef22, 0x9b8563bd, \
+	 0xaa83fe3b, 0xc53b8d91, 0x15731c5f, 0xb6db2eeb}
+
+#define DQ_512 \
+	{0xd3265fba, 0x2eb65638, 0x4d106ec7, 0x000dfe69, \
+	 0x75f87505, 0x47d299d0, 0x1c115cdd, 0x599ca8c1}
+
+#define MP_512 \
+	{0x23359955, 0xcad299b6, 0x049bb248, 0x3828b6a5, \
+	 0x74c85825, 0x7dd8e109, 0x07edbda9, 0x4980c2c9}
+
+#define MQ_512 \
+	{0x8578120b, 0x91f4ca9e, 0x371d3e70, 0x0005bb89, \
+	 0xd31ed864, 0x477bd9cf, 0x65a1f03b, 0x606d3bc8}
+