import random

NUM_BITS_SIZE_MESSAGE = 64
NUM_WITNESSES = 100


def keygen(b):
    fix = 2 ** (b // 2 - 1)

    rnd = random.SystemRandom() #uses os.urandom() which is suitable for cryptography and is practical
    p = rnd.getrandbits(b // 2) | fix
    while miller_rabin_primality_testing(p, NUM_WITNESSES) == False:
        p = rnd.getrandbits(b // 2) | fix
    q = rnd.getrandbits(b // 2) | fix
    while miller_rabin_primality_testing(q, NUM_WITNESSES) == False:
        q = rnd.getrandbits(b // 2) | fix
    #At this point, we have two prime numbers (high probability)
    #finding e
    phi_n = (p - 1) * (q - 1)
    while True:
        e = rnd.randint(3, phi_n-1)
        res = xEuclid(e, phi_n)
        if res[0] == 1:
            break
    d = res[1] % phi_n

    n = p * q

    print n.bit_length()
    print p.bit_length()
    print q.bit_length()

    return (n, p, q, e, d)



#FAZER CHECK DO TAMANHO DOS BITS DE N E SE FOR MENOR QUE 64 USAR 64 + random
#usando os bits se calhar
def cipher(msg, n, e):
    print("CIPHER")
    size_msg = len(msg)
    block_size = n.bit_length() #64 min?
    block_pick = block_size - 1 #64 min?
    #if block_size < 64:
        #   block_size = 64

    n_blocks = (size_msg + NUM_BITS_SIZE_MESSAGE) // block_pick
    noise_ammount = block_pick - ((size_msg + NUM_BITS_SIZE_MESSAGE) % block_pick)

    #Check if we are going to need padding (block isnt complete)
    if noise_ammount != 0:
        n_blocks += 1

    #ciphered = pow(convert_list_binary_to_int(msg), e, n) #maybe improve
    #bits = ciphered.bit_length()

    list = []
    #print("Message to code ", ciphered)
    #print("Message to code as binary ", convert_int_to_binary_list(ciphered))
    #print("Message num bits ", ciphered.bit_length())
    #print("Size message ", ciphered.bit_length())
    print("Num blocks =", n_blocks)
    print("block size =", block_size)



    #Size of message to send
    #Add values we know for sure are zeros
    for _ in range(NUM_BITS_SIZE_MESSAGE - size_msg.bit_length()):
        list.append(0)
    append_num_as_bin_to_list(size_msg, list)

    print("List of", len(list), "bits containing size of message ", size_msg)
    print()

    #Message itself
    for i in msg:
        list.append(i)

    #append noise to make even blocks
    #Random noise
    if noise_ammount > 0:
        rnd = random.SystemRandom() #uses os.urandom() which is suitable for cryptography and is practical
        num = rnd.getrandbits(noise_ammount)

        #Add values we know for sure are zeros
        for i in range(noise_ammount - num.bit_length()):
            list.append(0)
        append_num_as_bin_to_list(num, list)

    new_list = [] #LOT OF ZEROS WRONG??
    for i in range(n_blocks):
        #print(list[block_size*i:block_size*(i+1)])
        num_to_cipher = convert_list_binary_to_int(list[block_pick * i:block_pick * (i + 1)])
        ciphered = pow(num_to_cipher, e, n) #maybe improve

        #Add values we know for sure are zeros
        for i in range(block_size - ciphered.bit_length()):
            new_list.append(0)
        append_num_as_bin_to_list(ciphered, new_list)

    print("Random noise ammount =", noise_ammount)

    return new_list


def decipher(msg, n, d):
    print("DECIPHER")
    size_msg = len(msg)
    block_pick = n.bit_length()
    block_size = block_pick-1
    #if block_size < 64:
        #   block_size = 64
    n_blocks = size_msg // block_size
    print("Num blocks =", n_blocks)
    print("block size =", block_size)
    print("block pick =", block_pick)

    firstblock = []
    #first block special
    num_to_decipher = convert_list_binary_to_int(msg[:block_pick])
    deciphered = pow(num_to_decipher, d, n) #maybe improve

    #Add values we know for sure are zeros
    for i in range(block_size - deciphered.bit_length()):
        firstblock.append(0)
    append_num_as_bin_to_list(deciphered, firstblock)

    #extract msg size
    size_msg = convert_list_binary_to_int(firstblock[:NUM_BITS_SIZE_MESSAGE])
    noise_ammount = n_blocks * block_size - size_msg - NUM_BITS_SIZE_MESSAGE

    print("size of msg = ", size_msg)
    print("size of noise=", noise_ammount)
    if size_msg <= block_size-NUM_BITS_SIZE_MESSAGE:
        list = firstblock[NUM_BITS_SIZE_MESSAGE:NUM_BITS_SIZE_MESSAGE+size_msg]#LOT OF ZEROS WRONG??
    else:
        list = firstblock[NUM_BITS_SIZE_MESSAGE:]
        for i in range(1, n_blocks-1):
            num_to_decipher = convert_list_binary_to_int(msg[block_pick * i:block_pick * (i + 1)])
            deciphered = pow(num_to_decipher, d, n) #maybe improve

            #Add values we know for sure are zeros
            for i in range(block_size - deciphered.bit_length()):
                list.append(0)
            append_num_as_bin_to_list(deciphered, list)

        #Last block special as we can have noise
        num_to_decipher = convert_list_binary_to_int(msg[block_pick * (n_blocks-1):])
        deciphered = pow(num_to_decipher, d, n) #maybe improve

        for _ in range(block_size - deciphered.bit_length()):
            list.append(0)
        auxlist = convert_int_to_binary_list(deciphered)
        for i in range(deciphered.bit_length()-noise_ammount):
            list.append(auxlist[i])

    #list.append(meow[:block_size-noise_ammount])

    print("size = ", len(list))
    return list

def append_num_as_bin_to_list(num, list):
    num_bit_length = num.bit_length()

    #Check if a bit is 1 or 0 and append it stating at most significant
    for i in range(num_bit_length - 1, -1, -1):
        copy_num = num
        if copy_num & (2 ** i) == 0:
            list.append(0)
        else:
            list.append(1)

def convert_list_binary_to_int(list):
    result = 0
    for bit in list:
        result = (result << 1) | bit
    return result

def convert_int_to_binary_list(num):
    list = []
    while num != 0:
        list.append(num & 1)
        num >>= 1
    return(list[::-1])

#chheck this and comments
def miller_rabin_primality_testing(n, k):
    if not (n & 1):
        return False

    rnd = random.SystemRandom() #uses os.urandom() which is suitable for cryptography and is practical

    if n < 2:
        return False

    # Decompose (n - 1) to write it as (2 ** r) * d
    # While d is even, divide it by 2 and increase the exponent.
    d = n - 1
    r = 0

    while not (d & 1):
        r += 1
        d >>= 1

    witnesses = []
    a = 1
    # Test k witnesses.
    for _ in range(k):
        # Generate random integer a, where 3 <= a <= (n - 1)
        # a cant be pair
        while not (a & 1) or a in witnesses:
            a = rnd.randint(3, n - 1) #CONFIRMAR
        witnesses.append(a)

        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue

        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == 1:
                return False
            if x == n - 1:
                break
        else:
            return False
    return True

def xEuclid(d, f):
    x1, x2, x3 = 1, 0, f
    y1, y2, y3 = 0, 1, d
    while True:
        if y3 == 0: return (x3, "no inverse")
        if y3 == 1: return (y3, y2)
        q = x3 // y3
        x1, x2, x3, y1, y2, y3 = y1, y2, y3, x1 - (q * y1), x2 - (q * y2), x3 - (q * y3)

"""
#cipher
num_to_cipher = 548624
num_to_cipher_bin = convert_int_to_binary_list(num_to_cipher)
n = 119
e = 5
print("Ciphering", num_to_cipher, "with bin =", num_to_cipher_bin, "and n =", n, "and e =", e)
res = cipher(num_to_cipher_bin, n, e)
#print("Result =", res)


#decipher

#num_to_decipher = 66
#num_to_decipher_bin = convert_int_to_binary_list(num_to_decipher)
#n = 119
#
#print("Deciphering", num_to_decipher, "with bin =", num_to_decipher_bin, "and
#n =", n, "and d =", d)
d = 77
res = decipher(res, n, d)
print("Result =", res)
print()
"""
if __name__ == "__main__":
    msg = convert_int_to_binary_list(9832423 ** 12121)
    keys = keygen(1000)
    #msg = [0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1]
    #msg = [0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1]
    cypheredmsg = cipher(msg, keys[0], keys[3])

    decypheredmsg = decipher(cypheredmsg, keys[0], keys[4])
    print
    print len(msg)
    print msg == decypheredmsg