Source code for pvss.qr

"""
Quadratic residues modulo safe prime p
"""

from __future__ import annotations

import hmac
from dataclasses import dataclass
from fractions import Fraction
from functools import cached_property
from typing import Optional, Union, cast

from asn1crypto.algos import DHParameters
from asn1crypto.core import Asn1Value, Integer
from asn1crypto.pem import unarmor
from gmpy2 import invert, is_prime, legendre, mpz, powmod

from .asn1 import ImgGroupValue
from .groups import ImageGroup, ImageValue, PgvOrInt
from .pvss import Pvss, SystemParameters
from .zq import ZqGroup, ZqValue


[docs]def create_qr_params(pvss: Pvss, params: Union[int, str, bytes]) -> bytes: """ Create and set QR parameters. If params is str or a bytes, assume it's a diffie-hellman parameter file such as created by "openssl dhparam 4096", either DER or PEM encoded. Args: pvss: Pvss object with public values params: if int, must be a safe prime, otherwise must be a DH params file with a safe prime. Returns: DER encoded QR system parameters. """ if not isinstance(params, int): if isinstance(params, str): params = params.encode() if params[0] != 0x30: # DER encoding of "Sequence" starts with 0x30. So it's probably PEM. params = unarmor(bytes(params))[2] params = int(cast(Integer, DHParameters.load(bytes(params))["p"])) result = QrParameters.create(pvss, params).der pvss.set_params(result) return result
class QrParameters(SystemParameters): """ Quadratic residues modulo p. """ ALGO = "qr_mod_p" @cached_property def pre_group(self) -> ZqGroup: return ZqGroup(mpz(self.img_group.len)) @cached_property def img_group(self) -> QrGroup: """ Create image group singleton """ return QrGroup(mpz(int(cast(Integer, self.asn1["parameters"])))) def _make_gen(self, seed: str) -> QrValue: """ Deterministic pseudo-random function to generate a group element. """ key = seed.encode() p = self.img_group.p bits = p.bit_length() * 2 dig = self.der tmp = bytearray() while len(tmp) * 8 < bits: dig = hmac.digest(key, dig, "sha256") tmp.extend(dig) # Square to get a quadratic residue value = powmod(int.from_bytes(tmp, "big"), 2, p) # Check for bad value. 0 is no group element at all. 1 is the neutral element. if value in {0, 1}: # Try again with new seed. This happening is extremely unlikely. return self._make_gen(seed + "_") return self.img_group(value) @dataclass(frozen=True) class QrGroup(ImageGroup): """ Multiplicative group of Quadratic Residues modulo safe prime p """ p: mpz def __post_init__(self) -> None: if not is_prime(self.p): raise ValueError("p not prime") if not is_prime(self.len): raise ValueError("(p - 1) / 2 not prime") def __call__(self, value: Union[int, mpz, Integer, Asn1Value]) -> QrValue: if isinstance(value, (int, mpz)): value %= self.p if value == 0: raise ValueError("0 not in group") return QrValue(self, value) if isinstance(value, ImgGroupValue): value = value.chosen if not isinstance(value, Integer): raise TypeError(type(value)) value = mpz(int(value)) if not 1 <= value < self.p: raise ValueError("Not a valid group element") if legendre(value, self.p) != 1: raise ValueError("Not a valid group element") return QrValue(self, value) @cached_property def len(self) -> int: return int(self.p // 2) def __repr__(self) -> str: """ Outputs a representation of this group. Returns: Representation of this group """ return f"QrGroup({self.p})" @dataclass(frozen=True) class QrValue(ImageValue): """ Elements of QrGroup. The value is always in [1, p). """ group: QrGroup value: mpz @property def asn1(self) -> ImgGroupValue: """ Convert to ASN.1 Integer type """ return ImgGroupValue({"QrValue": Integer(int(self))}) def __int__(self) -> int: """ Returns: Value of self as a native python integer """ return int(self.value) def __mul__(self, other: ImageValue) -> QrValue: """ Implement the group operation a * b. Args: other: Second operand Returns: Product of `self` and `other` """ if not isinstance(other, QrValue): return NotImplemented return self.group(self.value * other.value) def __pow__( self, other: Union[PgvOrInt, Fraction], modulo: Optional[int] = None ) -> QrValue: """ Implement a ** b and pow(a, b). If b is a Fraction c/d, compute a ** (c * (d^-1)) Args: other: exponent modulo: Not supported, must be None Returns: `self` raised to the power of `other` """ if modulo is not None: raise Exception("Modulo not supported") if isinstance(other, int): return self.group(powmod(self.value, other, self.group.p)) if isinstance(other, ZqValue): if other.group.len != self.group.len: raise TypeError("incompatible groups") return self.group(powmod(self.value, int(other), self.group.p)) if isinstance(other, Fraction): tmp = powmod(self.value, other.numerator, self.group.p) if other.denominator != 1: tmp = powmod(tmp, invert(other.denominator, self.group.len), self.group.p) return self.group(tmp) return NotImplemented def __repr__(self) -> str: """ Outputs a representation of this value. Returns: Representation of this value """ return f"{self.group}({int(self)})"