import os import sys from math import log2 class PartialInteger: def __init__(self): self.bit_length = 0 self.unknowns = 0 self._components = [] def add_known(self, value, bit_length): self.bit_length += bit_length self._components.append((value, bit_length)) return self def add_unknown(self, bit_length): self.bit_length += bit_length self.unknowns += 1 self._components.append((None, bit_length)) return self def get_known_lsb(self): lsb = 0 lsb_bit_length = 0 for value, bit_length in self._components: if value is None: return lsb, lsb_bit_length lsb = lsb + (value << lsb_bit_length) lsb_bit_length += bit_length return lsb, lsb_bit_length def get_known_msb(self): msb = 0 msb_bit_length = 0 for value, bit_length in reversed(self._components): if value is None: return msb, msb_bit_length msb = (msb << bit_length) + value msb_bit_length += bit_length return msb, msb_bit_length def get_known_middle(self): middle = 0 middle_bit_length = 0 for value, bit_length in self._components: if value is None: if middle_bit_length > 0: return middle, middle_bit_length else: middle = middle + (value << middle_bit_length) middle_bit_length += bit_length return middle, middle_bit_length def get_unknown_lsb(self): lsb_bit_length = 0 for value, bit_length in self._components: if value is not None: return lsb_bit_length lsb_bit_length += bit_length return lsb_bit_length def get_unknown_msb(self): msb_bit_length = 0 for value, bit_length in reversed(self._components): if value is not None: return msb_bit_length msb_bit_length += bit_length return msb_bit_length def get_unknown_middle(self): middle_bit_length = 0 for value, bit_length in self._components: if value is None: if middle_bit_length > 0: return middle_bit_length else: middle_bit_length += bit_length return middle_bit_length def matches(self, i): shift = 0 for value, bit_length in self._components: if value is not None and (i >> shift) % (2 ** bit_length) != value: return False shift += bit_length return True def sub(self, unknowns): assert len(unknowns) == self.unknowns i = 0 j = 0 shift = 0 for value, bit_length in self._components: if value is None: # We don't shift here because the unknown could be a symbolic variable i += 2 ** shift * unknowns[j] j += 1 else: i += value << shift shift += bit_length return i def get_known_and_unknowns(self): i_ = 0 o = [] l = [] offset = 0 for value, bit_length in self._components: if value is None: o.append(offset) l.append(bit_length) else: i_ += 2 ** offset * value offset += bit_length return i_, o, l def get_unknown_bounds(self): return [2 ** bit_length for value, bit_length in self._components if value is None] def to_int(self): assert self.unknowns == 0 return self.sub([]) def to_string_le(self, base, symbols="0123456789abcdefghijklmnopqrstuvwxyz"): assert (base & (base - 1)) == 0, "Base must be power of two." assert base <= 36 assert len(symbols) >= base bits_per_element = int(log2(base)) chars = [] for value, bit_length in self._components: assert bit_length % bits_per_element == 0, f"Component with bit length {bit_length} can't be represented by base {base} digits" for _ in range(bit_length // bits_per_element): if value is None: chars.append('?') else: chars.append(symbols[value % base]) value //= base return chars def to_string_be(self, base, symbols="0123456789abcdefghijklmnopqrstuvwxyz"): return self.to_string_le(base, symbols)[::-1] def to_bits_le(self, symbols="01"): assert len(symbols) == 2 return self.to_string_le(2, symbols) def to_bits_be(self, symbols="01"): return self.to_bits_le(symbols)[::-1] def to_hex_le(self, symbols="0123456789abcdef"): assert len(symbols) == 16 return self.to_string_le(16, symbols) def to_hex_be(self, symbols="0123456789abcdef"): return self.to_hex_le(symbols)[::-1] @staticmethod def unknown(bit_length): return PartialInteger().add_unknown(bit_length) @staticmethod def parse_le(digits, base): assert (base & (base - 1)) == 0, "Base must be power of two." assert base <= 36 bits_per_element = int(log2(base)) p = PartialInteger() rc_k = 0 rc_u = 0 value = 0 for digit in digits: if digit is None or digit == '?': if rc_k > 0: p.add_known(value, rc_k * bits_per_element) rc_k = 0 value = 0 rc_u += 1 else: if isinstance(digit, str): digit = int(digit, base) assert 0 <= digit < base if rc_u > 0: p.add_unknown(rc_u * bits_per_element) rc_u = 0 value += digit * base ** rc_k rc_k += 1 if rc_k > 0: p.add_known(value, rc_k * bits_per_element) if rc_u > 0: p.add_unknown(rc_u * bits_per_element) return p @staticmethod def parse_be(digits, base): return PartialInteger.parse_le(reversed(digits), base) @staticmethod def from_bits_le(bits): return PartialInteger.parse_le(bits, 2) @staticmethod def from_bits_be(bits): return PartialInteger.from_bits_le(reversed(bits)) @staticmethod def from_hex_le(hex): return PartialInteger.parse_le(hex, 16) @staticmethod def from_hex_be(hex): return PartialInteger.from_hex_le(reversed(hex)) @staticmethod def from_lsb(bit_length, lsb, lsb_bit_length): assert bit_length >= lsb_bit_length assert 0 <= lsb <= (2 ** lsb_bit_length) return PartialInteger().add_known(lsb, lsb_bit_length).add_unknown(bit_length - lsb_bit_length) @staticmethod def from_msb(bit_length, msb, msb_bit_length): assert bit_length >= msb_bit_length assert 0 <= msb < (2 ** msb_bit_length) return PartialInteger().add_unknown(bit_length - msb_bit_length).add_known(msb, msb_bit_length) @staticmethod def from_lsb_and_msb(bit_length, lsb, lsb_bit_length, msb, msb_bit_length): assert bit_length >= lsb_bit_length + msb_bit_length assert 0 <= lsb < (2 ** lsb_bit_length) assert 0 <= msb < (2 ** msb_bit_length) middle_bit_length = bit_length - lsb_bit_length - msb_bit_length return PartialInteger().add_known(lsb, lsb_bit_length).add_unknown(middle_bit_length).add_known(msb, msb_bit_length) @staticmethod def from_middle(middle, middle_bit_length, lsb_bit_length, msb_bit_length): assert 0 <= middle < (2 ** middle_bit_length) return PartialInteger().add_unknown(lsb_bit_length).add_known(middle, middle_bit_length).add_unknown(msb_bit_length) @staticmethod def lsb_of(i, bit_length, lsb_bit_length): lsb = i % (2 ** lsb_bit_length) return PartialInteger.from_lsb(bit_length, lsb, lsb_bit_length) @staticmethod def msb_of(i, bit_length, msb_bit_length): msb = i >> (bit_length - msb_bit_length) return PartialInteger.from_msb(bit_length, msb, msb_bit_length) @staticmethod def lsb_and_msb_of(i, bit_length, lsb_bit_length, msb_bit_length): lsb = i % (2 ** lsb_bit_length) msb = i >> (bit_length - msb_bit_length) return PartialInteger.from_lsb_and_msb(bit_length, lsb, lsb_bit_length, msb, msb_bit_length) @staticmethod def middle_of(i, bit_length, lsb_bit_length, msb_bit_length): middle_bit_length = bit_length - lsb_bit_length - msb_bit_length middle = (i >> lsb_bit_length) % (2 ** middle_bit_length) return PartialInteger.from_middle(middle, middle_bit_length, lsb_bit_length, msb_bit_length) def attack(n, e, sv, sf): d_bits = [None] * n.bit_length() m = 2 mi = {pow(m, 2 ** i, n): i for i in range(n.bit_length())} for sfi in sf: di0 = pow(sv, -1, n) * sfi % n di1 = sv * pow(sfi, -1, n) % n if di0 in mi: d_bits[mi[di0]] = 0 if di1 in mi: d_bits[mi[di1]] = 1 return PartialInteger.from_bits_le(d_bits) ```

ECC DRAFT