1"""Framework classes for generation of bignum core test cases.""" 2# Copyright The Mbed TLS Contributors 3# SPDX-License-Identifier: Apache-2.0 4# 5# Licensed under the Apache License, Version 2.0 (the "License"); you may 6# not use this file except in compliance with the License. 7# You may obtain a copy of the License at 8# 9# http://www.apache.org/licenses/LICENSE-2.0 10# 11# Unless required by applicable law or agreed to in writing, software 12# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 13# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14# See the License for the specific language governing permissions and 15# limitations under the License. 16 17import random 18 19from typing import Dict, Iterator, List, Tuple 20 21from . import test_case 22from . import test_data_generation 23from . import bignum_common 24 25class BignumCoreTarget(test_data_generation.BaseTarget): 26 #pylint: disable=abstract-method, too-few-public-methods 27 """Target for bignum core test case generation.""" 28 target_basename = 'test_suite_bignum_core.generated' 29 30 31class BignumCoreShiftR(BignumCoreTarget, test_data_generation.BaseTest): 32 """Test cases for mbedtls_bignum_core_shift_r().""" 33 count = 0 34 test_function = "mpi_core_shift_r" 35 test_name = "Core shift right" 36 37 DATA = [ 38 ('00', '0', [0, 1, 8]), 39 ('01', '1', [0, 1, 2, 8, 64]), 40 ('dee5ca1a7ef10a75', '64-bit', 41 list(range(11)) + [31, 32, 33, 63, 64, 65, 71, 72]), 42 ('002e7ab0070ad57001', '[leading 0 limb]', 43 [0, 1, 8, 63, 64]), 44 ('a1055eb0bb1efa1150ff', '80-bit', 45 [0, 1, 8, 63, 64, 65, 72, 79, 80, 81, 88, 128, 129, 136]), 46 ('020100000000000000001011121314151617', '138-bit', 47 [0, 1, 8, 9, 16, 72, 73, 136, 137, 138, 144]), 48 ] 49 50 def __init__(self, input_hex: str, descr: str, count: int) -> None: 51 self.input_hex = input_hex 52 self.number_description = descr 53 self.shift_count = count 54 self.result = bignum_common.hex_to_int(input_hex) >> count 55 56 def arguments(self) -> List[str]: 57 return ['"{}"'.format(self.input_hex), 58 str(self.shift_count), 59 '"{:0{}x}"'.format(self.result, len(self.input_hex))] 60 61 def description(self) -> str: 62 return 'Core shift {} >> {}'.format(self.number_description, 63 self.shift_count) 64 65 @classmethod 66 def generate_function_tests(cls) -> Iterator[test_case.TestCase]: 67 for input_hex, descr, counts in cls.DATA: 68 for count in counts: 69 yield cls(input_hex, descr, count).create_test_case() 70 71class BignumCoreCTLookup(BignumCoreTarget, test_data_generation.BaseTest): 72 """Test cases for mbedtls_mpi_core_ct_uint_table_lookup().""" 73 test_function = "mpi_core_ct_uint_table_lookup" 74 test_name = "Constant time MPI table lookup" 75 76 bitsizes = [ 77 (32, "One limb"), 78 (192, "Smallest curve sized"), 79 (512, "Largest curve sized"), 80 (2048, "Small FF/RSA sized"), 81 (4096, "Large FF/RSA sized"), 82 ] 83 84 window_sizes = [0, 1, 2, 3, 4, 5, 6] 85 86 def __init__(self, 87 bitsize: int, descr: str, window_size: int) -> None: 88 self.bitsize = bitsize 89 self.bitsize_description = descr 90 self.window_size = window_size 91 92 def arguments(self) -> List[str]: 93 return [str(self.bitsize), str(self.window_size)] 94 95 def description(self) -> str: 96 return '{} - {} MPI with {} bit window'.format( 97 BignumCoreCTLookup.test_name, 98 self.bitsize_description, 99 self.window_size 100 ) 101 102 @classmethod 103 def generate_function_tests(cls) -> Iterator[test_case.TestCase]: 104 for bitsize, bitsize_description in cls.bitsizes: 105 for window_size in cls.window_sizes: 106 yield (cls(bitsize, bitsize_description, window_size) 107 .create_test_case()) 108 109 110class BignumCoreAddAndAddIf(BignumCoreTarget, bignum_common.OperationCommon): 111 """Test cases for bignum core add and add-if.""" 112 count = 0 113 symbol = "+" 114 test_function = "mpi_core_add_and_add_if" 115 test_name = "mpi_core_add_and_add_if" 116 input_style = "arch_split" 117 unique_combinations_only = True 118 119 def result(self) -> List[str]: 120 result = self.int_a + self.int_b 121 122 carry, result = divmod(result, self.limb_boundary) 123 124 return [ 125 self.format_result(result), 126 str(carry) 127 ] 128 129 130class BignumCoreSub(BignumCoreTarget, bignum_common.OperationCommon): 131 """Test cases for bignum core sub.""" 132 count = 0 133 input_style = "arch_split" 134 symbol = "-" 135 test_function = "mpi_core_sub" 136 test_name = "mbedtls_mpi_core_sub" 137 138 def result(self) -> List[str]: 139 if self.int_a >= self.int_b: 140 result = self.int_a - self.int_b 141 carry = 0 142 else: 143 result = self.limb_boundary + self.int_a - self.int_b 144 carry = 1 145 return [ 146 self.format_result(result), 147 str(carry) 148 ] 149 150 151class BignumCoreMLA(BignumCoreTarget, bignum_common.OperationCommon): 152 """Test cases for fixed-size multiply accumulate.""" 153 count = 0 154 test_function = "mpi_core_mla" 155 test_name = "mbedtls_mpi_core_mla" 156 157 input_values = [ 158 "0", "1", "fffe", "ffffffff", "100000000", "20000000000000", 159 "ffffffffffffffff", "10000000000000000", "1234567890abcdef0", 160 "fffffffffffffffffefefefefefefefe", 161 "100000000000000000000000000000000", 162 "1234567890abcdef01234567890abcdef0", 163 "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", 164 "1234567890abcdef01234567890abcdef01234567890abcdef01234567890abcdef0", 165 ( 166 "4df72d07b4b71c8dacb6cffa954f8d88254b6277099308baf003fab73227f" 167 "34029643b5a263f66e0d3c3fa297ef71755efd53b8fb6cb812c6bbf7bcf17" 168 "9298bd9947c4c8b14324140a2c0f5fad7958a69050a987a6096e9f055fb38" 169 "edf0c5889eca4a0cfa99b45fbdeee4c696b328ddceae4723945901ec02507" 170 "6b12b" 171 ) 172 ] # type: List[str] 173 input_scalars = [ 174 "0", "3", "fe", "ff", "ffff", "10000", "ffffffff", "100000000", 175 "7f7f7f7f7f7f7f7f", "8000000000000000", "fffffffffffffffe" 176 ] # type: List[str] 177 178 def __init__(self, val_a: str, val_b: str, val_s: str) -> None: 179 super().__init__(val_a, val_b) 180 self.arg_scalar = val_s 181 self.int_scalar = bignum_common.hex_to_int(val_s) 182 if bignum_common.limbs_mpi(self.int_scalar, 32) > 1: 183 self.dependencies = ["MBEDTLS_HAVE_INT64"] 184 185 def arguments(self) -> List[str]: 186 return [ 187 bignum_common.quote_str(self.arg_a), 188 bignum_common.quote_str(self.arg_b), 189 bignum_common.quote_str(self.arg_scalar) 190 ] + self.result() 191 192 def description(self) -> str: 193 """Override and add the additional scalar.""" 194 if not self.case_description: 195 self.case_description = "0x{} + 0x{} * 0x{}".format( 196 self.arg_a, self.arg_b, self.arg_scalar 197 ) 198 return super().description() 199 200 def result(self) -> List[str]: 201 result = self.int_a + (self.int_b * self.int_scalar) 202 bound_val = max(self.int_a, self.int_b) 203 bound_4 = bignum_common.bound_mpi(bound_val, 32) 204 bound_8 = bignum_common.bound_mpi(bound_val, 64) 205 carry_4, remainder_4 = divmod(result, bound_4) 206 carry_8, remainder_8 = divmod(result, bound_8) 207 return [ 208 "\"{:x}\"".format(remainder_4), 209 "\"{:x}\"".format(carry_4), 210 "\"{:x}\"".format(remainder_8), 211 "\"{:x}\"".format(carry_8) 212 ] 213 214 @classmethod 215 def get_value_pairs(cls) -> Iterator[Tuple[str, str]]: 216 """Generator to yield pairs of inputs. 217 218 Combinations are first generated from all input values, and then 219 specific cases provided. 220 """ 221 yield from super().get_value_pairs() 222 yield from cls.input_cases 223 224 @classmethod 225 def generate_function_tests(cls) -> Iterator[test_case.TestCase]: 226 """Override for additional scalar input.""" 227 for a_value, b_value in cls.get_value_pairs(): 228 for s_value in cls.input_scalars: 229 cur_op = cls(a_value, b_value, s_value) 230 yield cur_op.create_test_case() 231 232 233class BignumCoreMontmul(BignumCoreTarget, test_data_generation.BaseTest): 234 """Test cases for Montgomery multiplication.""" 235 count = 0 236 test_function = "mpi_core_montmul" 237 test_name = "mbedtls_mpi_core_montmul" 238 239 start_2_mpi4 = False 240 start_2_mpi8 = False 241 242 replay_test_cases = [ 243 (2, 1, 1, 1, "19", "1", "1D"), (2, 1, 1, 1, "7", "1", "9"), 244 (2, 1, 1, 1, "4", "1", "9"), 245 ( 246 12, 1, 6, 1, ( 247 "3C246D0E059A93A266288A7718419EC741661B474C58C032C5EDAF92709402" 248 "B07CC8C7CE0B781C641A1EA8DB2F4343" 249 ), "1", ( 250 "66A198186C18C10B2F5ED9B522752A9830B69916E535C8F047518A889A43A5" 251 "94B6BED27A168D31D4A52F88925AA8F5" 252 ) 253 ), ( 254 8, 1, 4, 1, 255 "1E442976B0E63D64FCCE74B999E470CA9888165CB75BFA1F340E918CE03C6211", 256 "1", "B3A119602EE213CDE28581ECD892E0F592A338655DCE4CA88054B3D124D0E561" 257 ), ( 258 22, 1, 11, 1, ( 259 "7CF5AC97304E0B63C65413F57249F59994B0FED1D2A8D3D83ED5FA38560FFB" 260 "82392870D6D08F87D711917FD7537E13B7E125BE407E74157776839B0AC9DB" 261 "23CBDFC696104353E4D2780B2B4968F8D8542306BCA7A2366E" 262 ), "1", ( 263 "284139EA19C139EBE09A8111926AAA39A2C2BE12ED487A809D3CB5BC558547" 264 "25B4CDCB5734C58F90B2F60D99CC1950CDBC8D651793E93C9C6F0EAD752500" 265 "A32C56C62082912B66132B2A6AA42ADA923E1AD22CEB7BA0123" 266 ) 267 ) 268 ] # type: List[Tuple[int, int, int, int, str, str, str]] 269 270 random_test_cases = [ 271 ("2", "2", "3", ""), ("1", "2", "3", ""), ("2", "1", "3", ""), 272 ("6", "5", "7", ""), ("3", "4", "7", ""), ("1", "6", "7", ""), ("5", "6", "7", ""), 273 ("3", "4", "B", ""), ("7", "4", "B", ""), ("9", "7", "B", ""), ("2", "a", "B", ""), 274 ("25", "16", "29", "(0x29 is prime)"), ("8", "28", "29", ""), 275 ("18", "21", "29", ""), ("15", "f", "29", ""), 276 ("e2", "ea", "FF", ""), ("43", "72", "FF", ""), 277 ("d8", "70", "FF", ""), ("3c", "7c", "FF", ""), 278 ("99", "b9", "101", "(0x101 is prime)"), ("65", "b2", "101", ""), 279 ("81", "32", "101", ""), ("51", "dd", "101", ""), 280 ("d5", "143", "38B", "(0x38B is prime)"), ("3d", "387", "38B", ""), 281 ("160", "2e5", "38B", ""), ("10f", "137", "38B", ""), 282 ("7dac", "25a", "8003", "(0x8003 is prime)"), ("6f1c", "3286", "8003", ""), 283 ("59ed", "2f3f", "8003", ""), ("6893", "736d", "8003", ""), 284 ("d199", "2832", "10001", "(0x10001 is prime)"), ("c3b2", "3e5b", "10001", ""), 285 ("abe4", "214e", "10001", ""), ("4360", "a05d", "10001", ""), 286 ("3f5a1", "165b2", "7F7F7", ""), ("3bd29", "37863", "7F7F7", ""), 287 ("60c47", "64819", "7F7F7", ""), ("16584", "12c49", "7F7F7", ""), 288 ("1ff03f", "610347", "800009", "(0x800009 is prime)"), ("340fd5", "19812e", "800009", ""), 289 ("3fe2e8", "4d0dc7", "800009", ""), ("40356", "e6392", "800009", ""), 290 ("dd8a1d", "266c0e", "100002B", "(0x100002B is prime)"), 291 ("3fa1cb", "847fd6", "100002B", ""), ("5f439d", "5c3196", "100002B", ""), 292 ("18d645", "f72dc6", "100002B", ""), 293 ("20051ad", "37def6e", "37EEE9D", "(0x37EEE9D is prime)"), 294 ("2ec140b", "3580dbf", "37EEE9D", ""), ("1d91b46", "190d4fc", "37EEE9D", ""), 295 ("34e488d", "1224d24", "37EEE9D", ""), 296 ("2a4fe2cb", "263466a9", "8000000B", "(0x8000000B is prime)"), 297 ("5643fe94", "29a1aefa", "8000000B", ""), ("29633513", "7b007ac4", "8000000B", ""), 298 ("2439cef5", "5c9d5a47", "8000000B", ""), 299 ("4de3cfaa", "50dea178", "8CD626B9", "(0x8CD626B9 is prime)"), 300 ("b8b8563", "10dbbbac", "8CD626B9", ""), ("4e8a6151", "5574ec19", "8CD626B9", ""), 301 ("69224878", "309cfc23", "8CD626B9", ""), 302 ("fb6f7fb6", "afb05423", "10000000F", "(0x10000000F is prime)"), 303 ("8391a243", "26034dcd", "10000000F", ""), ("d26b98c", "14b2d6aa", "10000000F", ""), 304 ("6b9f1371", "a21daf1d", "10000000F", ""), 305 ( 306 "9f49435ad", "c8264ade8", "174876E7E9", 307 "0x174876E7E9 is prime (dec) 99999999977" 308 ), 309 ("c402da434", "1fb427acf", "174876E7E9", ""), 310 ("f6ebc2bb1", "1096d39f2a", "174876E7E9", ""), 311 ("153b7f7b6b", "878fda8ff", "174876E7E9", ""), 312 ("2c1adbb8d6", "4384d2d3c6", "8000000017", "(0x8000000017 is prime)"), 313 ("2e4f9cf5fb", "794f3443d9", "8000000017", ""), 314 ("149e495582", "3802b8f7b7", "8000000017", ""), 315 ("7b9d49df82", "69c68a442a", "8000000017", ""), 316 ("683a134600", "6dd80ea9f6", "864CB9076D", "(0x864CB9076D is prime)"), 317 ("13a870ff0d", "59b099694a", "864CB9076D", ""), 318 ("37d06b0e63", "4d2147e46f", "864CB9076D", ""), 319 ("661714f8f4", "22e55df507", "864CB9076D", ""), 320 ("2f0a96363", "52693307b4", "F7F7F7F7F7", ""), 321 ("3c85078e64", "f2275ecb6d", "F7F7F7F7F7", ""), 322 ("352dae68d1", "707775b4c6", "F7F7F7F7F7", ""), 323 ("37ae0f3e0b", "912113040f", "F7F7F7F7F7", ""), 324 ("6dada15e31", "f58ed9eff7", "1000000000F", "(0x1000000000F is prime)"), 325 ("69627a7c89", "cfb5ebd13d", "1000000000F", ""), 326 ("a5e1ad239b", "afc030c731", "1000000000F", ""), 327 ("f1cc45f4c5", "c64ad607c8", "1000000000F", ""), 328 ("2ebad87d2e31", "4c72d90bca78", "800000000005", "(0x800000000005 is prime)"), 329 ("a30b3cc50d", "29ac4fe59490", "800000000005", ""), 330 ("33674e9647b4", "5ec7ee7e72d3", "800000000005", ""), 331 ("3d956f474f61", "74070040257d", "800000000005", ""), 332 ("48348e3717d6", "43fcb4399571", "800795D9BA47", "(0x800795D9BA47 is prime)"), 333 ("5234c03cc99b", "2f3cccb87803", "800795D9BA47", ""), 334 ("3ed13db194ab", "44b8f4ba7030", "800795D9BA47", ""), 335 ("1c11e843bfdb", "95bd1b47b08", "800795D9BA47", ""), 336 ("a81d11cb81fd", "1e5753a3f33d", "1000000000015", "(0x1000000000015 is prime)"), 337 ("688c4db99232", "36fc0cf7ed", "1000000000015", ""), 338 ("f0720cc07e07", "fc76140ed903", "1000000000015", ""), 339 ("2ec61f8d17d1", "d270c85e36d2", "1000000000015", ""), 340 ( 341 "6a24cd3ab63820", "ed4aad55e5e348", "100000000000051", 342 "(0x100000000000051 is prime)" 343 ), 344 ("e680c160d3b248", "31e0d8840ed510", "100000000000051", ""), 345 ("a80637e9aebc38", "bb81decc4e1738", "100000000000051", ""), 346 ("9afa5a59e9d630", "be9e65a6d42938", "100000000000051", ""), 347 ("ab5e104eeb71c000", "2cffbd639e9fea00", "ABCDEF0123456789", ""), 348 ("197b867547f68a00", "44b796cf94654800", "ABCDEF0123456789", ""), 349 ("329f9483a04f2c00", "9892f76961d0f000", "ABCDEF0123456789", ""), 350 ("4a2e12dfb4545000", "1aa3e89a69794500", "ABCDEF0123456789", ""), 351 ( 352 "8b9acdf013d140f000", "12e4ceaefabdf2b2f00", "25A55A46E5DA99C71C7", 353 "0x25A55A46E5DA99C71C7 is the 3rd repunit prime(dec) 11111111111111111111111" 354 ), 355 ("1b8d960ea277e3f5500", "14418aa980e37dd000", "25A55A46E5DA99C71C7", ""), 356 ("7314524977e8075980", "8172fa45618ccd0d80", "25A55A46E5DA99C71C7", ""), 357 ("ca14f031769be63580", "147a2f3cf2964ca9400", "25A55A46E5DA99C71C7", ""), 358 ( 359 "18532ba119d5cd0cf39735c0000", "25f9838e31634844924733000000", 360 "314DC643FB763F2B8C0E2DE00879", 361 "0x314DC643FB763F2B8C0E2DE00879 is (dec)99999999977^3" 362 ), 363 ( 364 "a56e2d2517519e3970e70c40000", "ec27428d4bb380458588fa80000", 365 "314DC643FB763F2B8C0E2DE00879", "" 366 ), 367 ( 368 "1cb5e8257710e8653fff33a00000", "15fdd42fe440fd3a1d121380000", 369 "314DC643FB763F2B8C0E2DE00879", "" 370 ), 371 ( 372 "e50d07a65fc6f93e538ce040000", "1f4b059ca609f3ce597f61240000", 373 "314DC643FB763F2B8C0E2DE00879", "" 374 ), 375 ( 376 "1ea3ade786a095d978d387f30df9f20000000", 377 "127c448575f04af5a367a7be06c7da0000000", 378 "47BF19662275FA2F6845C74942ED1D852E521", 379 "0x47BF19662275FA2F6845C74942ED1D852E521 is (dec) 99999999977^4" 380 ), 381 ( 382 "16e15b0ca82764e72e38357b1f10a20000000", 383 "43e2355d8514bbe22b0838fdc3983a0000000", 384 "47BF19662275FA2F6845C74942ED1D852E521", "" 385 ), 386 ( 387 "be39332529d93f25c3d116c004c620000000", 388 "5cccec42370a0a2c89c6772da801a0000000", 389 "47BF19662275FA2F6845C74942ED1D852E521", "" 390 ), 391 ( 392 "ecaa468d90de0eeda474d39b3e1fc0000000", 393 "1e714554018de6dc0fe576bfd3b5660000000", 394 "47BF19662275FA2F6845C74942ED1D852E521", "" 395 ), 396 ( 397 "32298816711c5dce46f9ba06e775c4bedfc770e6700000000000000", 398 "8ee751fd5fb24f0b4a653cb3a0c8b7d9e724574d168000000000000", 399 "97EDD86E4B5C4592C6D32064AC55C888A7245F07CA3CC455E07C931", 400 ( 401 "0x97EDD86E4B5C4592C6D32064AC55C888A7245F07CA3CC455E07C931" 402 " is (dec) 99999999977^6" 403 ) 404 ), 405 ( 406 "29213b9df3cfd15f4b428645b67b677c29d1378d810000000000000", 407 "6cbb732c65e10a28872394dfdd1936d5171c3c3aac0000000000000", 408 "97EDD86E4B5C4592C6D32064AC55C888A7245F07CA3CC455E07C931", "" 409 ), 410 ( 411 "6f18db06ad4abc52c0c50643dd13098abccd4a232f0000000000000", 412 "7e6bf41f2a86098ad51f98dfc10490ba3e8081bc830000000000000", 413 "97EDD86E4B5C4592C6D32064AC55C888A7245F07CA3CC455E07C931", "" 414 ), 415 ( 416 "62d3286cd706ad9d73caff63f1722775d7e8c731208000000000000", 417 "530f7ba02ae2b04c2fe3e3d27ec095925631a6c2528000000000000", 418 "97EDD86E4B5C4592C6D32064AC55C888A7245F07CA3CC455E07C931", "" 419 ), 420 ( 421 "a6c6503e3c031fdbf6009a89ed60582b7233c5a85de28b16000000000000000", 422 "75c8ed18270b583f16d442a467d32bf95c5e491e9b8523798000000000000000", 423 "DD15FE80B731872AC104DB37832F7E75A244AA2631BC87885B861E8F20375499", 424 ( 425 "0xDD15FE80B731872AC104DB37832F7E75A244AA2631BC87885B861E8F20375499" 426 " is (dec) 99999999977^7" 427 ) 428 ), 429 ( 430 "bf84d1f85cf6b51e04d2c8f4ffd03532d852053cf99b387d4000000000000000", 431 "397ba5a743c349f4f28bc583ecd5f06e0a25f9c6d98f09134000000000000000", 432 "DD15FE80B731872AC104DB37832F7E75A244AA2631BC87885B861E8F20375499", "" 433 ), 434 ( 435 "6db11c3a4152ed1a2aa6fa34b0903ec82ea1b88908dcb482000000000000000", 436 "ac8ac576a74ad6ca48f201bf89f77350ce86e821358d85920000000000000000", 437 "DD15FE80B731872AC104DB37832F7E75A244AA2631BC87885B861E8F20375499", "" 438 ), 439 ( 440 "3001d96d7fe8b733f33687646fc3017e3ac417eb32e0ec708000000000000000", 441 "925ddbdac4174e8321a48a32f79640e8cf7ec6f46ea235a80000000000000000", 442 "DD15FE80B731872AC104DB37832F7E75A244AA2631BC87885B861E8F20375499", "" 443 ), 444 ( 445 "1029048755f2e60dd98c8de6d9989226b6bb4f0db8e46bd1939de560000000000000000000", 446 "51bb7270b2e25cec0301a03e8275213bb6c2f6e6ec93d4d46d36ca0000000000000000000", 447 "141B8EBD9009F84C241879A1F680FACCED355DA36C498F73E96E880CF78EA5F96146380E41", 448 ( 449 "0x141B8EBD9009F84C241879A1F680FACCED355DA36C498F73E96E880CF78EA5F96146" 450 "380E41 is 99999999977^8" 451 ) 452 ), 453 ( 454 "1c5337ff982b3ad6611257dbff5bbd7a9920ba2d4f5838a0cc681ce000000000000000000", 455 "520c5d049ca4702031ba728591b665c4d4ccd3b2b86864d4c160fd2000000000000000000", 456 "141B8EBD9009F84C241879A1F680FACCED355DA36C498F73E96E880CF78EA5F96146380E41", 457 "" 458 ), 459 ( 460 "57074dfa00e42f6555bae624b7f0209f218adf57f73ed34ab0ff90c000000000000000000", 461 "41eb14b6c07bfd3d1fe4f4a610c17cc44fcfcda695db040e011065000000000000000000", 462 "141B8EBD9009F84C241879A1F680FACCED355DA36C498F73E96E880CF78EA5F96146380E41", 463 "" 464 ), 465 ( 466 "d8ed7feed2fe855e6997ad6397f776158573d425031bf085a615784000000000000000000", 467 "6f121dcd18c578ab5e229881006007bb6d319b179f11015fe958b9c000000000000000000", 468 "141B8EBD9009F84C241879A1F680FACCED355DA36C498F73E96E880CF78EA5F96146380E41", 469 "" 470 ), 471 ( 472 ( 473 "2a462b156180ea5fe550d3758c764e06fae54e626b5f503265a09df76edbdfbf" 474 "a1e6000000000000000000000000" 475 ), ( 476 "1136f41d1879fd4fb9e49e0943a46b6704d77c068ee237c3121f9071cfd3e6a0" 477 "0315800000000000000000000000" 478 ), ( 479 "2A94608DE88B6D5E9F8920F5ABB06B24CC35AE1FBACC87D075C621C3E2833EC90" 480 "2713E40F51E3B3C214EDFABC451" 481 ), ( 482 "0x2A94608DE88B6D5E9F8920F5ABB06B24CC35AE1FBACC87D075C621C3E2833EC" 483 "902713E40F51E3B3C214EDFABC451 is (dec) 99999999977^10" 484 ) 485 ), 486 ( 487 ( 488 "c1ac3800dfb3c6954dea391d206200cf3c47f795bf4a5603b4cb88ae7e574de47" 489 "40800000000000000000000000" 490 ), ( 491 "c0d16eda0549ede42fa0deb4635f7b7ce061fadea02ee4d85cba4c4f709603419" 492 "3c800000000000000000000000" 493 ), ( 494 "2A94608DE88B6D5E9F8920F5ABB06B24CC35AE1FBACC87D075C621C3E2833EC90" 495 "2713E40F51E3B3C214EDFABC451" 496 ), "" 497 ), 498 ( 499 ( 500 "19e45bb7633094d272588ad2e43bcb3ee341991c6731b6fa9d47c4018d7ce7bba" 501 "5ee800000000000000000000000" 502 ), ( 503 "1e4f83166ae59f6b9cc8fd3e7677ed8bfc01bb99c98bd3eb084246b64c1e18c33" 504 "65b800000000000000000000000" 505 ), ( 506 "2A94608DE88B6D5E9F8920F5ABB06B24CC35AE1FBACC87D075C621C3E2833EC90" 507 "2713E40F51E3B3C214EDFABC451" 508 ), "" 509 ), 510 ( 511 ( 512 "1aa93395fad5f9b7f20b8f9028a054c0bb7c11bb8520e6a95e5a34f06cb70bcdd" 513 "01a800000000000000000000000" 514 ), ( 515 "54b45afa5d4310192f8d224634242dd7dcfb342318df3d9bd37b4c614788ba13b" 516 "8b000000000000000000000000" 517 ), ( 518 "2A94608DE88B6D5E9F8920F5ABB06B24CC35AE1FBACC87D075C621C3E2833EC90" 519 "2713E40F51E3B3C214EDFABC451" 520 ), "" 521 ), 522 ( 523 ( 524 "544f2628a28cfb5ce0a1b7180ee66b49716f1d9476c466c57f0c4b23089917843" 525 "06d48f78686115ee19e25400000000000000000000000000000000" 526 ), ( 527 "677eb31ef8d66c120fa872a60cd47f6e10cbfdf94f90501bd7883cba03d185be0" 528 "a0148d1625745e9c4c827300000000000000000000000000000000" 529 ), ( 530 "8335616AED761F1F7F44E6BD49E807B82E3BF2BF11BFA6AF813C808DBF33DBFA1" 531 "1DABD6E6144BEF37C6800000000000000000000000000000000051" 532 ), ( 533 "0x8335616AED761F1F7F44E6BD49E807B82E3BF2BF11BFA6AF813C808DBF33DBF" 534 "A11DABD6E6144BEF37C6800000000000000000000000000000000051 is prime," 535 " (dec) 10^143 + 3^4" 536 ) 537 ), 538 ( 539 ( 540 "76bb3470985174915e9993522aec989666908f9e8cf5cb9f037bf4aee33d8865c" 541 "b6464174795d07e30015b80000000000000000000000000000000" 542 ), ( 543 "6aaaf60d5784dcef612d133613b179a317532ecca0eed40b8ad0c01e6d4a6d8c7" 544 "9a52af190abd51739009a900000000000000000000000000000000" 545 ), ( 546 "8335616AED761F1F7F44E6BD49E807B82E3BF2BF11BFA6AF813C808DBF33DBFA1" 547 "1DABD6E6144BEF37C6800000000000000000000000000000000051" 548 ), "" 549 ), 550 ( 551 ( 552 "6cfdd6e60912e441d2d1fc88f421b533f0103a5322ccd3f4db84861643ad63fd6" 553 "3d1d8cfbc1d498162786ba00000000000000000000000000000000" 554 ), ( 555 "1177246ec5e93814816465e7f8f248b350d954439d35b2b5d75d917218e7fd5fb" 556 "4c2f6d0667f9467fdcf33400000000000000000000000000000000" 557 ), ( 558 "8335616AED761F1F7F44E6BD49E807B82E3BF2BF11BFA6AF813C808DBF33DBFA1" 559 "1DABD6E6144BEF37C6800000000000000000000000000000000051" 560 ), "" 561 ), 562 ( 563 ( 564 "7a09a0b0f8bbf8057116fb0277a9bdf3a91b5eaa8830d448081510d8973888be5" 565 "a9f0ad04facb69aa3715f00000000000000000000000000000000" 566 ), ( 567 "764dec6c05a1c0d87b649efa5fd94c91ea28bffb4725d4ab4b33f1a3e8e3b314d" 568 "799020e244a835a145ec9800000000000000000000000000000000" 569 ), ( 570 "8335616AED761F1F7F44E6BD49E807B82E3BF2BF11BFA6AF813C808DBF33DBFA1" 571 "1DABD6E6144BEF37C6800000000000000000000000000000000051" 572 ), "" 573 ) 574 ] # type: List[Tuple[str, str, str, str]] 575 576 def __init__( 577 self, val_a: str, val_b: str, val_n: str, case_description: str = "" 578 ): 579 self.case_description = case_description 580 self.arg_a = val_a 581 self.int_a = bignum_common.hex_to_int(val_a) 582 self.arg_b = val_b 583 self.int_b = bignum_common.hex_to_int(val_b) 584 self.arg_n = val_n 585 self.int_n = bignum_common.hex_to_int(val_n) 586 587 limbs_a4 = bignum_common.limbs_mpi(self.int_a, 32) 588 limbs_a8 = bignum_common.limbs_mpi(self.int_a, 64) 589 self.limbs_b4 = bignum_common.limbs_mpi(self.int_b, 32) 590 self.limbs_b8 = bignum_common.limbs_mpi(self.int_b, 64) 591 self.limbs_an4 = bignum_common.limbs_mpi(self.int_n, 32) 592 self.limbs_an8 = bignum_common.limbs_mpi(self.int_n, 64) 593 594 if limbs_a4 > self.limbs_an4 or limbs_a8 > self.limbs_an8: 595 raise Exception("Limbs of input A ({}) exceeds N ({})".format( 596 self.arg_a, self.arg_n 597 )) 598 599 def arguments(self) -> List[str]: 600 return [ 601 str(self.limbs_an4), str(self.limbs_b4), 602 str(self.limbs_an8), str(self.limbs_b8), 603 bignum_common.quote_str(self.arg_a), 604 bignum_common.quote_str(self.arg_b), 605 bignum_common.quote_str(self.arg_n) 606 ] + self.result() 607 608 def description(self) -> str: 609 if self.case_description != "replay": 610 if not self.start_2_mpi4 and self.limbs_an4 > 1: 611 tmp = "(start of 2-MPI 4-byte bignums) " 612 self.__class__.start_2_mpi4 = True 613 elif not self.start_2_mpi8 and self.limbs_an8 > 1: 614 tmp = "(start of 2-MPI 8-byte bignums) " 615 self.__class__.start_2_mpi8 = True 616 else: 617 tmp = "(gen) " 618 self.case_description = tmp + self.case_description 619 return super().description() 620 621 def result(self) -> List[str]: 622 """Get the result of the operation.""" 623 r4 = bignum_common.bound_mpi_limbs(self.limbs_an4, 32) 624 i4 = bignum_common.invmod(r4, self.int_n) 625 x4 = self.int_a * self.int_b * i4 626 x4 = x4 % self.int_n 627 628 r8 = bignum_common.bound_mpi_limbs(self.limbs_an8, 64) 629 i8 = bignum_common.invmod(r8, self.int_n) 630 x8 = self.int_a * self.int_b * i8 631 x8 = x8 % self.int_n 632 return [ 633 "\"{:x}\"".format(x4), 634 "\"{:x}\"".format(x8) 635 ] 636 637 def set_limbs( 638 self, limbs_an4: int, limbs_b4: int, limbs_an8: int, limbs_b8: int 639 ) -> None: 640 """Set number of limbs for each input. 641 642 Replaces default values set during initialization. 643 """ 644 self.limbs_an4 = limbs_an4 645 self.limbs_b4 = limbs_b4 646 self.limbs_an8 = limbs_an8 647 self.limbs_b8 = limbs_b8 648 649 @classmethod 650 def generate_function_tests(cls) -> Iterator[test_case.TestCase]: 651 """Generate replay and randomly generated test cases.""" 652 # Test cases which replay captured invocations during unit test runs. 653 for limbs_an4, limbs_b4, limbs_an8, limbs_b8, a, b, n in cls.replay_test_cases: 654 cur_op = cls(a, b, n, case_description="replay") 655 cur_op.set_limbs(limbs_an4, limbs_b4, limbs_an8, limbs_b8) 656 yield cur_op.create_test_case() 657 # Random test cases can be generated using mpi_modmul_case_generate() 658 # Uses a mixture of primes and odd numbers as N, with four randomly 659 # generated cases for each N. 660 for a, b, n, description in cls.random_test_cases: 661 cur_op = cls(a, b, n, case_description=description) 662 yield cur_op.create_test_case() 663 664 665def mpi_modmul_case_generate() -> None: 666 """Generate valid inputs for montmul tests using moduli. 667 668 For each modulus, generates random values for A and B and simple descriptions 669 for the test case. 670 """ 671 moduli = [ 672 ("3", ""), ("7", ""), ("B", ""), ("29", ""), ("FF", ""), 673 ("101", ""), ("38B", ""), ("8003", ""), ("10001", ""), 674 ("7F7F7", ""), ("800009", ""), ("100002B", ""), ("37EEE9D", ""), 675 ("8000000B", ""), ("8CD626B9", ""), ("10000000F", ""), 676 ("174876E7E9", "is prime (dec) 99999999977"), 677 ("8000000017", ""), ("864CB9076D", ""), ("F7F7F7F7F7", ""), 678 ("1000000000F", ""), ("800000000005", ""), ("800795D9BA47", ""), 679 ("1000000000015", ""), ("100000000000051", ""), ("ABCDEF0123456789", ""), 680 ( 681 "25A55A46E5DA99C71C7", 682 "is the 3rd repunit prime (dec) 11111111111111111111111" 683 ), 684 ("314DC643FB763F2B8C0E2DE00879", "is (dec)99999999977^3"), 685 ("47BF19662275FA2F6845C74942ED1D852E521", "is (dec) 99999999977^4"), 686 ( 687 "97EDD86E4B5C4592C6D32064AC55C888A7245F07CA3CC455E07C931", 688 "is (dec) 99999999977^6" 689 ), 690 ( 691 "DD15FE80B731872AC104DB37832F7E75A244AA2631BC87885B861E8F20375499", 692 "is (dec) 99999999977^7" 693 ), 694 ( 695 "141B8EBD9009F84C241879A1F680FACCED355DA36C498F73E96E880CF78EA5F96146380E41", 696 "is (dec) 99999999977^8" 697 ), 698 ( 699 ( 700 "2A94608DE88B6D5E9F8920F5ABB06B24CC35AE1FBACC87D075C621C3E283" 701 "3EC902713E40F51E3B3C214EDFABC451" 702 ), 703 "is (dec) 99999999977^10" 704 ), 705 ( 706 "8335616AED761F1F7F44E6BD49E807B82E3BF2BF11BFA6AF813C808DBF33DBFA11" 707 "DABD6E6144BEF37C6800000000000000000000000000000000051", 708 "is prime, (dec) 10^143 + 3^4" 709 ) 710 ] # type: List[Tuple[str, str]] 711 primes = [ 712 "3", "7", "B", "29", "101", "38B", "8003", "10001", "800009", 713 "100002B", "37EEE9D", "8000000B", "8CD626B9", 714 # From here they require > 1 4-byte MPI 715 "10000000F", "174876E7E9", "8000000017", "864CB9076D", "1000000000F", 716 "800000000005", "800795D9BA47", "1000000000015", "100000000000051", 717 # From here they require > 1 8-byte MPI 718 "25A55A46E5DA99C71C7", # this is 11111111111111111111111 decimal 719 # 10^143 + 3^4: (which is prime) 720 # 100000000000000000000000000000000000000000000000000000000000000000000000000000 721 # 000000000000000000000000000000000000000000000000000000000000000081 722 ( 723 "8335616AED761F1F7F44E6BD49E807B82E3BF2BF11BFA6AF813C808DBF33DBFA11" 724 "DABD6E6144BEF37C6800000000000000000000000000000000051" 725 ) 726 ] # type: List[str] 727 generated_inputs = [] 728 for mod, description in moduli: 729 n = bignum_common.hex_to_int(mod) 730 mod_read = "{:x}".format(n) 731 case_count = 3 if n < 5 else 4 732 cases = {} # type: Dict[int, int] 733 i = 0 734 while i < case_count: 735 a = random.randint(1, n) 736 b = random.randint(1, n) 737 if cases.get(a) == b: 738 continue 739 cases[a] = b 740 if description: 741 out_description = "0x{} {}".format(mod_read, description) 742 elif i == 0 and len(mod) > 1 and mod in primes: 743 out_description = "(0x{} is prime)" 744 else: 745 out_description = "" 746 generated_inputs.append( 747 ("{:x}".format(a), "{:x}".format(b), mod, out_description) 748 ) 749 i += 1 750 print(generated_inputs) 751 752# BEGIN MERGE SLOT 1 753 754class BignumCoreExpMod(BignumCoreTarget, bignum_common.ModOperationCommon): 755 """Test cases for bignum core exponentiation.""" 756 symbol = "^" 757 test_function = "mpi_core_exp_mod" 758 test_name = "Core modular exponentiation (Mongtomery form only)" 759 input_style = "fixed" 760 montgomery_form_a = True 761 762 def result(self) -> List[str]: 763 # Result has to be given in Montgomery form too 764 result = pow(self.int_a, self.int_b, self.int_n) 765 mont_result = self.to_montgomery(result) 766 return [self.format_result(mont_result)] 767 768 @property 769 def is_valid(self) -> bool: 770 # The base needs to be canonical, but the exponent can be larger than 771 # the modulus (see for example exponent blinding) 772 return bool(self.int_a < self.int_n) 773 774# END MERGE SLOT 1 775 776# BEGIN MERGE SLOT 2 777 778# END MERGE SLOT 2 779 780# BEGIN MERGE SLOT 3 781 782class BignumCoreSubInt(BignumCoreTarget, bignum_common.OperationCommon): 783 """Test cases for bignum core sub int.""" 784 count = 0 785 symbol = "-" 786 test_function = "mpi_core_sub_int" 787 test_name = "mpi_core_sub_int" 788 input_style = "arch_split" 789 790 @property 791 def is_valid(self) -> bool: 792 # This is "sub int", so b is only one limb 793 if bignum_common.limbs_mpi(self.int_b, self.bits_in_limb) > 1: 794 return False 795 return True 796 797 # Overriding because we don't want leading zeros on b 798 @property 799 def arg_b(self) -> str: 800 return self.val_b 801 802 def result(self) -> List[str]: 803 result = self.int_a - self.int_b 804 805 borrow, result = divmod(result, self.limb_boundary) 806 807 # Borrow will be -1 if non-zero, but we want it to be 1 in the test data 808 return [ 809 self.format_result(result), 810 str(-borrow) 811 ] 812 813class BignumCoreZeroCheckCT(BignumCoreTarget, bignum_common.OperationCommon): 814 """Test cases for bignum core zero check (constant flow).""" 815 count = 0 816 symbol = "== 0" 817 test_function = "mpi_core_check_zero_ct" 818 test_name = "mpi_core_check_zero_ct" 819 input_style = "variable" 820 arity = 1 821 suffix = True 822 823 def result(self) -> List[str]: 824 result = 1 if self.int_a == 0 else 0 825 return [str(result)] 826 827# END MERGE SLOT 3 828 829# BEGIN MERGE SLOT 4 830 831# END MERGE SLOT 4 832 833# BEGIN MERGE SLOT 5 834 835# END MERGE SLOT 5 836 837# BEGIN MERGE SLOT 6 838 839# END MERGE SLOT 6 840 841# BEGIN MERGE SLOT 7 842 843# END MERGE SLOT 7 844 845# BEGIN MERGE SLOT 8 846 847# END MERGE SLOT 8 848 849# BEGIN MERGE SLOT 9 850 851# END MERGE SLOT 9 852 853# BEGIN MERGE SLOT 10 854 855# END MERGE SLOT 10 856