MatsumotoImaiAExample.py

#!/usr/bin/sage
# -*- coding: utf-8 -*-

from __future__ import absolute_import, print_function
from sage.all import *
import copy as cp

from .helpers.sage_extensions import random_value, random_invertible_matrix

from .helpers.AffineTransformation import AffineTransformation
from .helpers.PrivateKey import PrivateKey
from .helpers.PrivateKey import PublicKey
from .helpers.EncryptionScheme import EncryptionScheme


class MatsumotoImaiAExample(EncryptionScheme):
    """Matsumoto Imai Scheme A implementation"""

    def phi(self, polynomail_a):
        return polynomail_a.list()

    def phi_inv(self, vector_a):  # -> b::Polynomial
        return self.extension_field(vector_a)

    def __init__(self, finite_field, n, keyfile=None):
        self.finite_field = finite_field
        self.n = n

        # generate or load private & public key
        if keyfile is not None:
            self.private_key = PrivateKey(None, None, None, keyfile)
            self.public_key = self.private_key.generate_public_key()
        else:
            # self.generate_keys()
            self.generate_example_keys()

    def generate_example_keys(self):
        k = self.finite_field
        (a,) = k.gens()
        n = 3

        ring = PolynomialRing(k, 'x')
        (x,) = ring.gens()
        gx = x**3 + x + 1

        (self.theta, self.theta_invers) = (2, 26)

        ML1 = matrix(k, [[a**2, a, a], [a, 1, 0], [1, 0, 1]])
        yL1 = vector(k, [0, 1, a])
        T = AffineTransformation(ML1, yL1)

        ML2 = matrix(k, [[1, 0, a], [0, 1, a], [1, a, 0]])
        yL2 = vector(k, [a, a**2, a**2])
        S = AffineTransformation(ML2, yL2)

        multivariate_ring = PolynomialRing(k, 'x1, x2, x3', n)
        extension_field = PolynomialRing(
            multivariate_ring, 't').quotient_ring(gx, 'T')
        self.extension_field = extension_field
        multi_vars = multivariate_ring.gens()

        Sx = list(S(vector(multi_vars)))

        pre_F = self.phi_inv(Sx)  # <- phi_invers

        # Now the MAGIC happens
        # post_F = self.F(pre_F)

        post_F = extension_field("1 + (a + 1)*x1 + (a)*x2 + x3 + x1*x2 + (a)*x1*x3 + (a + 1)*x2*x3 + ((a) + (a)*x1 + x2 + (a + 1)*x3 + x1^2 + (a + 1)*x1*x2 + x2^2 + x2*x3)*T + ((a + 1) + (a + 1)*x1 + (a)*x2 + (a)*x3 + x1^2 + x1*x2 + (a)*x1*x3 + (a + 1)*x2^2 + (a)*x2*x3 + (a + 1)*x3^2)*T^2")

        SPTx = T(vector(post_F.list()))

        Pr = T.inverse(vector(post_F.list()))
        self.private_key = PrivateKey(S, Pr, T)
        self.public_key = PublicKey(SPTx)

    def invert_MQ(self, msg):
        X = self.phi_inv(list(msg))
        return vector(self.phi(X**self.theta_invers))