import json
import sys, os, itertools

sys.path.append(os.path.abspath(os.path.join('..')))
from playcrypt.tools import *
from playcrypt.new_tools import *
from playcrypt.primitives import *

from playcrypt.games.game_ufcma_sign import GameUFCMASign
from playcrypt.simulator.ufcma_sign_sim import UFCMASignSim

def ADD(a,b):
    return a+b
def MULT(a,b):
    return a*b
def INT_DIV(a,N):
    return (a//N, a%N)
def MOD(a,N):
    return a%N
def EXT_GCD(a,N):
    return egcd(a,N)
def MOD_INV(a,N):
    res = modinv(a,N)
    if res == None:
        raise ValueError("Inverse does not exist.")
    return res
def MOD_EXP(a,n,N):
    return exp(a,n,N)

"""
!!!READ THIS FIRST!!!
Please name your collaborator(s) for this assignment. You can also state that
you have worked completely independently. Please refer to the course website
regarding the collaboration policy.

Your response:


"""

"""
Problem 1 [8 points]
Let p be a prime of bit length k >= 8 such that (p - 1)/2 is also prime, and
let g be a generators of the group G = Z_p^*. Le q = p - 1. Consider the
digital signature scheme DS = (K, S, V) whose component algorithms are below,
where the message m is in Z_q^*.
"""

def K():
    x = random_Z_N(q)
    X = MOD_EXP(g, x, p)
    y = random_Z_N(q)
    Y = MOD_EXP(g, y, p)
    return (X, Y), (x, y)

def S(sk, m):
    """
    :param sk: The secret key sk = (x, y) used to sign messages
    :param M: The message to be signed, must be in Z_q^*
    :return: return the signature of message M
    """
    (x, y) = sk
    if EXT_GCD(m, q)[0] != 1:
        return False
    if m > q - 1 or m < 0:
        return False
    z = MOD(y + x * m, q)
    return z

def V(pk, m, z):
    """
    :param pk: The public key pk = (X, Y) used to verify messages
    :param M: The message to be verified, must be in Z_q^*
    :param sig: The signature to be verified
    :return: return 1 if the signature is valid and 0 otherwise
    """
    (X, Y) = pk
    if EXT_GCD(m, q)[0] != 1:
        return 0
    if m > q - 1 or m < 0:
        return 0
    if z > q - 1 or z < 0:
        return 0
    if MOD(Y * MOD_EXP(X, m, p), p) == MOD_EXP(g, z, p):
        return 1
    return 0

"""
Present an O(k^2)-time adversary A making at most two queries to its Sign oracle and
achieving Adv^{uf-cma}_DS(A) = 1.
"""

def A(Sign, pk):
    """
    You must fill in this method. This is the adversary that the problem is
    asking for. It should return a message and a signature.

    :param Sign:  Signing oracle
    :param pk:  Public key pk
    """
    return None, None


if __name__ == '__main__':

    # Sample random parameters
    k = 12
    print('Sampling random parameters of bit length k = %d' % k)
    p = random.randint(2**(k - 1), 2**k)
    while not is_prime(p) or not is_prime((p-1)//2):
        p = random.randint(2**(k - 1), 2**k)
    q = p-1
    g = random_Z_N_star(p)
    while (MOD_EXP(g, (p-1)//2, p) == 1) or (MOD_EXP(g, 2, p) == 1):
        g = random_Z_N_star(p)
    print('p = %d, g = %d' % (p, g))

    game_ufcma = GameUFCMASign(S, V, 0, K)
    sim_ufcma = UFCMASignSim(game_ufcma, A)

    print("The advantage of your adversary A is approx. " + str(sim_ufcma.compute_advantage()))