1"""Common features for bignum in test generation framework.""" 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 17from abc import abstractmethod 18import enum 19from typing import Iterator, List, Tuple, TypeVar, Any 20from itertools import chain 21 22from . import test_case 23from . import test_data_generation 24from .bignum_data import INPUTS_DEFAULT, MODULI_DEFAULT 25 26T = TypeVar('T') #pylint: disable=invalid-name 27 28def invmod(a: int, n: int) -> int: 29 """Return inverse of a to modulo n. 30 31 Equivalent to pow(a, -1, n) in Python 3.8+. Implementation is equivalent 32 to long_invmod() in CPython. 33 """ 34 b, c = 1, 0 35 while n: 36 q, r = divmod(a, n) 37 a, b, c, n = n, c, b - q*c, r 38 # at this point a is the gcd of the original inputs 39 if a == 1: 40 return b 41 raise ValueError("Not invertible") 42 43def invmod_positive(a: int, n: int) -> int: 44 """Return a non-negative inverse of a to modulo n.""" 45 inv = invmod(a, n) 46 return inv if inv >= 0 else inv + n 47 48def hex_to_int(val: str) -> int: 49 """Implement the syntax accepted by mbedtls_test_read_mpi(). 50 51 This is a superset of what is accepted by mbedtls_test_read_mpi_core(). 52 """ 53 if val in ['', '-']: 54 return 0 55 return int(val, 16) 56 57def quote_str(val: str) -> str: 58 return "\"{}\"".format(val) 59 60def bound_mpi(val: int, bits_in_limb: int) -> int: 61 """First number exceeding number of limbs needed for given input value.""" 62 return bound_mpi_limbs(limbs_mpi(val, bits_in_limb), bits_in_limb) 63 64def bound_mpi_limbs(limbs: int, bits_in_limb: int) -> int: 65 """First number exceeding maximum of given number of limbs.""" 66 bits = bits_in_limb * limbs 67 return 1 << bits 68 69def limbs_mpi(val: int, bits_in_limb: int) -> int: 70 """Return the number of limbs required to store value.""" 71 return (val.bit_length() + bits_in_limb - 1) // bits_in_limb 72 73def combination_pairs(values: List[T]) -> List[Tuple[T, T]]: 74 """Return all pair combinations from input values.""" 75 return [(x, y) for x in values for y in values] 76 77def hex_digits_for_limb(limbs: int, bits_in_limb: int) -> int: 78 """ Retrun the hex digits need for a number of limbs. """ 79 return 2 * (limbs * bits_in_limb // 8) 80 81class OperationCommon(test_data_generation.BaseTest): 82 """Common features for bignum binary operations. 83 84 This adds functionality common in binary operation tests. 85 86 Attributes: 87 symbol: Symbol to use for the operation in case description. 88 input_values: List of values to use as test case inputs. These are 89 combined to produce pairs of values. 90 input_cases: List of tuples containing pairs of test case inputs. This 91 can be used to implement specific pairs of inputs. 92 unique_combinations_only: Boolean to select if test case combinations 93 must be unique. If True, only A,B or B,A would be included as a test 94 case. If False, both A,B and B,A would be included. 95 input_style: Controls the way how test data is passed to the functions 96 in the generated test cases. "variable" passes them as they are 97 defined in the python source. "arch_split" pads the values with 98 zeroes depending on the architecture/limb size. If this is set, 99 test cases are generated for all architectures. 100 arity: the number of operands for the operation. Currently supported 101 values are 1 and 2. 102 """ 103 symbol = "" 104 input_values = INPUTS_DEFAULT # type: List[str] 105 input_cases = [] # type: List[Any] 106 unique_combinations_only = False 107 input_styles = ["variable", "fixed", "arch_split"] # type: List[str] 108 input_style = "variable" # type: str 109 limb_sizes = [32, 64] # type: List[int] 110 arities = [1, 2] 111 arity = 2 112 suffix = False # for arity = 1, symbol can be prefix (default) or suffix 113 114 def __init__(self, val_a: str, val_b: str = "0", bits_in_limb: int = 32) -> None: 115 self.val_a = val_a 116 self.val_b = val_b 117 # Setting the int versions here as opposed to making them @properties 118 # provides earlier/more robust input validation. 119 self.int_a = hex_to_int(val_a) 120 self.int_b = hex_to_int(val_b) 121 if bits_in_limb not in self.limb_sizes: 122 raise ValueError("Invalid number of bits in limb!") 123 if self.input_style == "arch_split": 124 self.dependencies = ["MBEDTLS_HAVE_INT{:d}".format(bits_in_limb)] 125 self.bits_in_limb = bits_in_limb 126 127 @property 128 def boundary(self) -> int: 129 if self.arity == 1: 130 return self.int_a 131 elif self.arity == 2: 132 return max(self.int_a, self.int_b) 133 raise ValueError("Unsupported number of operands!") 134 135 @property 136 def limb_boundary(self) -> int: 137 return bound_mpi(self.boundary, self.bits_in_limb) 138 139 @property 140 def limbs(self) -> int: 141 return limbs_mpi(self.boundary, self.bits_in_limb) 142 143 @property 144 def hex_digits(self) -> int: 145 return hex_digits_for_limb(self.limbs, self.bits_in_limb) 146 147 def format_arg(self, val: str) -> str: 148 if self.input_style not in self.input_styles: 149 raise ValueError("Unknown input style!") 150 if self.input_style == "variable": 151 return val 152 else: 153 return val.zfill(self.hex_digits) 154 155 def format_result(self, res: int) -> str: 156 res_str = '{:x}'.format(res) 157 return quote_str(self.format_arg(res_str)) 158 159 @property 160 def arg_a(self) -> str: 161 return self.format_arg(self.val_a) 162 163 @property 164 def arg_b(self) -> str: 165 if self.arity == 1: 166 raise AttributeError("Operation is unary and doesn't have arg_b!") 167 return self.format_arg(self.val_b) 168 169 def arguments(self) -> List[str]: 170 args = [quote_str(self.arg_a)] 171 if self.arity == 2: 172 args.append(quote_str(self.arg_b)) 173 return args + self.result() 174 175 def description(self) -> str: 176 """Generate a description for the test case. 177 178 If not set, case_description uses the form A `symbol` B, where symbol 179 is used to represent the operation. Descriptions of each value are 180 generated to provide some context to the test case. 181 """ 182 if not self.case_description: 183 if self.arity == 1: 184 format_string = "{1:x} {0}" if self.suffix else "{0} {1:x}" 185 self.case_description = format_string.format( 186 self.symbol, self.int_a 187 ) 188 elif self.arity == 2: 189 self.case_description = "{:x} {} {:x}".format( 190 self.int_a, self.symbol, self.int_b 191 ) 192 return super().description() 193 194 @property 195 def is_valid(self) -> bool: 196 return True 197 198 @abstractmethod 199 def result(self) -> List[str]: 200 """Get the result of the operation. 201 202 This could be calculated during initialization and stored as `_result` 203 and then returned, or calculated when the method is called. 204 """ 205 raise NotImplementedError 206 207 @classmethod 208 def get_value_pairs(cls) -> Iterator[Tuple[str, str]]: 209 """Generator to yield pairs of inputs. 210 211 Combinations are first generated from all input values, and then 212 specific cases provided. 213 """ 214 if cls.arity == 1: 215 yield from ((a, "0") for a in cls.input_values) 216 elif cls.arity == 2: 217 if cls.unique_combinations_only: 218 yield from combination_pairs(cls.input_values) 219 else: 220 yield from ( 221 (a, b) 222 for a in cls.input_values 223 for b in cls.input_values 224 ) 225 else: 226 raise ValueError("Unsupported number of operands!") 227 228 @classmethod 229 def generate_function_tests(cls) -> Iterator[test_case.TestCase]: 230 if cls.input_style not in cls.input_styles: 231 raise ValueError("Unknown input style!") 232 if cls.arity not in cls.arities: 233 raise ValueError("Unsupported number of operands!") 234 if cls.input_style == "arch_split": 235 test_objects = (cls(a, b, bits_in_limb=bil) 236 for a, b in cls.get_value_pairs() 237 for bil in cls.limb_sizes) 238 special_cases = (cls(*args, bits_in_limb=bil) # type: ignore 239 for args in cls.input_cases 240 for bil in cls.limb_sizes) 241 else: 242 test_objects = (cls(a, b) 243 for a, b in cls.get_value_pairs()) 244 special_cases = (cls(*args) for args in cls.input_cases) 245 yield from (valid_test_object.create_test_case() 246 for valid_test_object in filter( 247 lambda test_object: test_object.is_valid, 248 chain(test_objects, special_cases) 249 ) 250 ) 251 252 253class ModulusRepresentation(enum.Enum): 254 """Representation selector of a modulus.""" 255 # Numerical values aligned with the type mbedtls_mpi_mod_rep_selector 256 INVALID = 0 257 MONTGOMERY = 2 258 OPT_RED = 3 259 260 def symbol(self) -> str: 261 """The C symbol for this representation selector.""" 262 return 'MBEDTLS_MPI_MOD_REP_' + self.name 263 264 @classmethod 265 def supported_representations(cls) -> List['ModulusRepresentation']: 266 """Return all representations that are supported in positive test cases.""" 267 return [cls.MONTGOMERY, cls.OPT_RED] 268 269 270class ModOperationCommon(OperationCommon): 271 #pylint: disable=abstract-method 272 """Target for bignum mod_raw test case generation.""" 273 moduli = MODULI_DEFAULT # type: List[str] 274 montgomery_form_a = False 275 disallow_zero_a = False 276 277 def __init__(self, val_n: str, val_a: str, val_b: str = "0", 278 bits_in_limb: int = 64) -> None: 279 super().__init__(val_a=val_a, val_b=val_b, bits_in_limb=bits_in_limb) 280 self.val_n = val_n 281 # Setting the int versions here as opposed to making them @properties 282 # provides earlier/more robust input validation. 283 self.int_n = hex_to_int(val_n) 284 285 def to_montgomery(self, val: int) -> int: 286 return (val * self.r) % self.int_n 287 288 def from_montgomery(self, val: int) -> int: 289 return (val * self.r_inv) % self.int_n 290 291 def convert_from_canonical(self, canonical: int, 292 rep: ModulusRepresentation) -> int: 293 """Convert values from canonical representation to the given representation.""" 294 if rep is ModulusRepresentation.MONTGOMERY: 295 return self.to_montgomery(canonical) 296 elif rep is ModulusRepresentation.OPT_RED: 297 return canonical 298 else: 299 raise ValueError('Modulus representation not supported: {}' 300 .format(rep.name)) 301 302 @property 303 def boundary(self) -> int: 304 return self.int_n 305 306 @property 307 def arg_a(self) -> str: 308 if self.montgomery_form_a: 309 value_a = self.to_montgomery(self.int_a) 310 else: 311 value_a = self.int_a 312 return self.format_arg('{:x}'.format(value_a)) 313 314 @property 315 def arg_n(self) -> str: 316 return self.format_arg(self.val_n) 317 318 def format_arg(self, val: str) -> str: 319 return super().format_arg(val).zfill(self.hex_digits) 320 321 def arguments(self) -> List[str]: 322 return [quote_str(self.arg_n)] + super().arguments() 323 324 @property 325 def r(self) -> int: # pylint: disable=invalid-name 326 l = limbs_mpi(self.int_n, self.bits_in_limb) 327 return bound_mpi_limbs(l, self.bits_in_limb) 328 329 @property 330 def r_inv(self) -> int: 331 return invmod(self.r, self.int_n) 332 333 @property 334 def r2(self) -> int: # pylint: disable=invalid-name 335 return pow(self.r, 2) 336 337 @property 338 def is_valid(self) -> bool: 339 if self.int_a >= self.int_n: 340 return False 341 if self.disallow_zero_a and self.int_a == 0: 342 return False 343 if self.arity == 2 and self.int_b >= self.int_n: 344 return False 345 return True 346 347 def description(self) -> str: 348 """Generate a description for the test case. 349 350 It uses the form A `symbol` B mod N, where symbol is used to represent 351 the operation. 352 """ 353 354 if not self.case_description: 355 return super().description() + " mod {:x}".format(self.int_n) 356 return super().description() 357 358 @classmethod 359 def input_cases_args(cls) -> Iterator[Tuple[Any, Any, Any]]: 360 if cls.arity == 1: 361 yield from ((n, a, "0") for a, n in cls.input_cases) 362 elif cls.arity == 2: 363 yield from ((n, a, b) for a, b, n in cls.input_cases) 364 else: 365 raise ValueError("Unsupported number of operands!") 366 367 @classmethod 368 def generate_function_tests(cls) -> Iterator[test_case.TestCase]: 369 if cls.input_style not in cls.input_styles: 370 raise ValueError("Unknown input style!") 371 if cls.arity not in cls.arities: 372 raise ValueError("Unsupported number of operands!") 373 if cls.input_style == "arch_split": 374 test_objects = (cls(n, a, b, bits_in_limb=bil) 375 for n in cls.moduli 376 for a, b in cls.get_value_pairs() 377 for bil in cls.limb_sizes) 378 special_cases = (cls(*args, bits_in_limb=bil) 379 for args in cls.input_cases_args() 380 for bil in cls.limb_sizes) 381 else: 382 test_objects = (cls(n, a, b) 383 for n in cls.moduli 384 for a, b in cls.get_value_pairs()) 385 special_cases = (cls(*args) for args in cls.input_cases_args()) 386 yield from (valid_test_object.create_test_case() 387 for valid_test_object in filter( 388 lambda test_object: test_object.is_valid, 389 chain(test_objects, special_cases) 390 )) 391 392# BEGIN MERGE SLOT 1 393 394# END MERGE SLOT 1 395 396# BEGIN MERGE SLOT 2 397 398# END MERGE SLOT 2 399 400# BEGIN MERGE SLOT 3 401 402# END MERGE SLOT 3 403 404# BEGIN MERGE SLOT 4 405 406# END MERGE SLOT 4 407 408# BEGIN MERGE SLOT 5 409 410# END MERGE SLOT 5 411 412# BEGIN MERGE SLOT 6 413 414# END MERGE SLOT 6 415 416# BEGIN MERGE SLOT 7 417 418# END MERGE SLOT 7 419 420# BEGIN MERGE SLOT 8 421 422# END MERGE SLOT 8 423 424# BEGIN MERGE SLOT 9 425 426# END MERGE SLOT 9 427 428# BEGIN MERGE SLOT 10 429 430# END MERGE SLOT 10 431