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