CoCalc -- blomer

GitHub Repository: jvdsn/crypto-attacks
Path: blob/master/shared/small_roots/blomer_may.py
²⁵⁸⁹ views
1
import logging
2

3
from sage.all import ZZ
4

5
from shared import small_roots
6

7

8
def modular_trivariate(f, N, m, t, X, Y, Z, roots_method="groebner"):
9
    """
10
    Computes small modular roots of a trivariate polynomial.
11
    More information: Blomer J., May A., "New Partial Key Exposure Attacks on RSA" (Section 4)
12
    :param f: the polynomial
13
    :param N: the modulus
14
    :param m: the parameter m
15
    :param t: the parameter t
16
    :param X: an approximate bound on the x roots
17
    :param Y: an approximate bound on the y roots
18
    :param Z: an approximate bound on the z roots
19
    :param roots_method: the method to use to find roots (default: "groebner")
20
    :return: a generator generating small roots (tuples of x, y, and z roots) of the polynomial
21
    """
22
    f = f.change_ring(ZZ)
23
    pr = f.parent()
24
    x, y, z = pr.gens()
25

26
    logging.debug("Generating shifts...")
27

28
    shifts = []
29
    for i in range(m + 1):
30
        for j in range(i + 1):
31
            for k in range(j + 1):
32
                g = x ** (j - k) * z ** k * N ** i * f ** (m - i)
33
                shifts.append(g)
34

35
            for k in range(1, t + 1):
36
                h = x ** j * y ** k * N ** i * f ** (m - i)
37
                shifts.append(h)
38

39
    L, monomials = small_roots.create_lattice(pr, shifts, [X, Y, Z])
40
    L = small_roots.reduce_lattice(L)
41
    polynomials = small_roots.reconstruct_polynomials(L, f, N ** m, monomials, [X, Y, Z])
42
    for roots in small_roots.find_roots(pr, polynomials, method=roots_method):
43
        yield roots[x], roots[y], roots[z]
44

45

46
def modular_bivariate(f, eM, m, t, Y, Z, roots_method="groebner"):
47
    """
48
    Computes small modular roots of a bivariate polynomial.
49
    More information: Blomer J., May A., "New Partial Key Exposure Attacks on RSA" (Section 6)
50
    :param f: the polynomial
51
    :param eM: the modulus
52
    :param m: the parameter m
53
    :param t: the parameter t
54
    :param Y: an approximate bound on the y roots
55
    :param Z: an approximate bound on the z roots
56
    :param roots_method: the method to use to find roots (default: "groebner")
57
    :return: a generator generating small roots (tuples of y and z roots) of the polynomial
58
    """
59
    f = f.change_ring(ZZ)
60
    pr = f.parent()
61
    y, z = pr.gens()
62

63
    logging.debug("Generating shifts...")
64

65
    shifts = []
66
    for i in range(m + 1):
67
        for j in range(i + 1):
68
            g = y ** j * eM ** i * f ** (m - i)
69
            shifts.append(g)
70

71
        for j in range(1, t + 1):
72
            h = z ** j * eM ** i * f ** (m - i)
73
            shifts.append(h)
74

75
    L, monomials = small_roots.create_lattice(pr, shifts, [Y, Z])
76
    L = small_roots.reduce_lattice(L)
77
    polynomials = small_roots.reconstruct_polynomials(L, f, eM ** m, monomials, [Y, Z])
78
    for roots in small_roots.find_roots(pr, polynomials, method=roots_method):
79
        yield roots[y], roots[z]
80

81
Product

Resources

Company
