decrypt_message.py

import sys
import numpy as np

cipher_text = '0010010011001101101111110010101010011111001011001110000110111000110011000000111000110100111110001010010011010010011111000100001101011110110110110000110100110010011000110000001111101010010000001100001010100100111100010011011010101111001101011110101111001100111010010010000100001000111111010100010110110100001101000101010000111110010110010101110111111111001101011110000111101010011011110010001110110111001001001000010111100100100101010000000110000010100100110000011110000000100111001010101011000000010000100111110001010100111101010111100000110101110111001101110100001000010011101110110100110111101100100100001101011001101000110100100111100000110100100001010111100000000101011011000011101110110001101001100101111000011000111110000011011001101001111011111011110000110000001001100010011000111011111001101101101111100011000000101001011000110101111000000100111111000000111101011110000011110011010001001000010100101111011000000010110001011011010001001011101001011111010100010011000111110110110101001101011011010010110000110111000010'

e=65537

def extended_euclides(a,b):
    s = 0
    old_s = 1
    t = 1
    old_t = 1
    r = b
    old_r = a
    while r!=0:
        q = old_r//r
        old_r,r = r,old_r-q*r
        old_t,t = t,old_t-q*t
        old_s,s = s,old_s-q*s
    return old_s%b, old_r

def modular_inverse(a,b):
    mod_inv, _ = extended_euclides(a,b)
    return mod_inv

def gcd(a,b):
    _, gcd_ = extended_euclides(a,b)
    return gcd_

def lcm(a,b):
    return (a*b)//gcd(a,b)

def carmichael(a,b):
    return lcm(a-1,b-1)

def num_to_bits(n,nbits=1024):
    return ''.join( '1' if (2**i) & n else '0' for i in range(nbits-1,-1,-1))

def bits_to_string(bits):
    num_bits = len(bits)
    if num_bits % 8 != 0:
        raise("num bits must be multiple of 8")
    return ''.join(chr(int(bits[i:i+8],2)) for i in range(0,num_bits,8))

#Include communication with server
def get_r_from_us(A_in,N_in):
    N=73437805505125745549278816801905040909523197681623562738904362379225783510669318621881633054041568886957437149703786851927811745674882293655790295648189479828112370997411972466379763283177500744092181886421043348732375163155125073261411417063223502095210135335525215950405227228567023220433032115195922640419
    A=1337133713371337
    if A==A_in and N==N_in:
        r_ret = 36718902752562872774639408400952520454761598840811781369452181189612891755334659310940816527020784443478718574851893425963905872837441146827895147824094730480455785727591759961599606570387556023662130693750873273715604994800886937528399327005450565738587226829285222501684139471038692332036716591686427476972
        return True,r_ret
    else:
        print("Liar! Those are not the right values!")
        return False,0

if __name__=='__main__':
    A_in = int(sys.argv[1])
    N_in = int(sys.argv[2])

    right,r = get_r_from_us(A_in, N_in)

    if right:
        p = gcd(pow(A_in,r//2,N_in)+1,N_in)
        q = gcd(pow(A_in,r//2,N_in)-1,N_in)
        d = modular_inverse(e,carmichael(p,q))
        decrypted = pow(int(cipher_text,2),d,N_in)
        print(bits_to_string(num_to_bits(decrypted)))