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