Subversion Repositories Code-Repo

import random

RSA_Text_1 = [12423,11524,7243,7459,14303,6127,10964,16399,9792,13629,14407,18817,
        18830,13556,3159,16647,5300,13951,81,8986,8007,13167,10022,17213,2264,961,17459,
        4101,2999,14569,17183,15827,12693,9553,18194,3830,2664,13998,12501,18873,12161,
        13071,16900,7233,8270,17086,9792,14266,13236,5300,13951,8850,12129,6091,18110,
        3332,15061,12347,7817,7946,11675,13924,13892,18031,2620,6276,8500,201,8850,
        11178,16477,10161,3533,13842,7537,12259,18110,44,2364,15570,3460,9886,8687,4481,
        1231,7547,11383,17910,12867,13203,5102,4742,5053,15407,2976,9330,12192,56,2471,
        15334,841,13995,17592,13297,2430,9741,11675,424,6686,738,13874,8168,7913,6246,
        14301,1144,9056,15967,7328,13203,796,195,9872,16979,15404,14130,9105,2001,9792,
        14251,1498,11296,1105,4502,16979,1105,56,4118,11302,5988,3363,15827,6928,4191,
        4277,10617,874,13211,11821,3090,18110,44,2364,15570,3460,9886,9988,3798,1158,
        9872,16979,15404,6127,9872,3652,14838,7437,2540,1367,2512,14407,5053,1521,297,
        10935,17137,2186,9433,13293,7555,13618,13000,6490,5310,18676,4782,11374,446,
        4165,11634,3846,14611,2364,6789,11634,4493,4063,4576,17955,7965,11748,14616,
        11453,17666,925,56,4188,18031,9522,14838,7437,3880,11476,8305,5102,2999,18628,
        14326,9175,9061,650,18110,8720,15404,2951,722,15334,841,15610,2443,11056,2186]

RSA_Text_2 = [6340,8309,14010,8936,27358,25023,16481,25809,23614,7135,24996,30590,
        27570,26486,30388,9395,27584,14999,4517,12146,29421,26439,1606,17881,25774,
        7647,23901,7372,25774,18436,12056,13547,7908,8635,2149,1908,22076,7372,8686,
        1304,4082,11803,5314,107,7359,22470,7372,22827,15698,30317,4685,14696,30388,
        8671,29956,15705,1417,26905,25809,28347,26277,7897,20240,21519,12437,1108,
        27106,18743,24144,10685,25234,30155,23005,8267,9917,7994,9694,2149,10042,27705,
        15930,29749,8635,23646,11738,24591,20240,27212,27486,9741,2149,29329,2149,5501,
        14015,30155,18154,22319,27705,20321,23254,13624,3249,5443,2149,16975,16087,
        14600,27705,19386,7325,26277,19554,23614,7553,4734,8091,23973,14015,107,3183,
        17347,25234,4595,21498,6360,19837,8463,6000,31280,29413,2066,369,23204,8425,
        7792,25973,4477,30989]

def RSA_Encrypt(x, b, n):
        '''Encrypts a plaintext x using b and n'''
        return (x**b)%n

def RSA_Decrypt(y, a, n):
        '''Decrypts a ciphertext y using a and n'''
        return (y**a)%n

def PollardRho(N):
        '''Implementation of the Pollard Rho algorithm for factoring primes'''
        if N%2==0:
                        return 2
        x = random.randint(1, N-1)
        y = x
        c = random.randint(1, N-1)
        g = 1
        while g==1:
                        x = ((x*x)%N+c)%N
                        y = ((y*y)%N+c)%N
                        y = ((y*y)%N+c)%N
                        g = GCD(abs(x-y),N)
        return g

def Extended_Euclidian(a, b):
        ''' Takes values a and b and returns a tuple (r,s,t) in the following format:
                r = s * a + t * b where r is the GCD and s and t are the inverses of a and b'''
        t_ = 0
        t = 1
        s_ = 1
        s = 0
        q = int(a/b)
        r = a - q * b
        # print("%d\t= %d * %d + %d" % (a, q, b, r))
        while r > 0:
                temp = t_ - q * t
                t_ = t
                t = temp
                temp = s_ - q * s
                s_ = s
                s = temp
                a = b
                b = r
                q = int(a/b)
                r = a - q * b
                # print("%d\t= %d * %d + %d" % (a, q, b, r))
        r = b
        return (r, s, t)

def GCD(q,N):
        '''Returns the multiplicative inverse of a and b'''
        ret = Extended_Euclidian(q,N)
        return ret[0]

def Inverse(a, b):
        '''Returns the multiplicative inverse of a mod b'''
        ret = Extended_Euclidian(a,b)
        if (ret[1] < 0):
                inv = ret[1] + b
        else:
                inv = ret[1]
        return inv

def Decrypt(n):
        '''Decodes an encoding where n = a * 26^2 + b * 26 + c'''
        a = int(n / 676)
        n = n - (a * 676)
        b = int(n / 26)
        n = n - (b * 26)
        c = n
        return (a, b, c)

if __name__ == '__main__':
        n = 31313
        b = 4913
        p = PollardRho(n)                       # Factor n to find a prime
        q = int(n / p)                          # Find the other prime
        phi = (q - 1) * (p - 1)         # Calculate Phi(n)
        a = Inverse(b, phi)                     # Calculate the decrypting exponent a
        print("N = %d, p = %d, q = %d, phi = %d, a = %d, b = %d" % (n, p, q, phi, a, b))

        # Decrypt the message
        for entry in RSA_Text_2:
                enc = Decrypt(RSA_Decrypt(entry, a, n))
                print("%c%c%c" % (chr(enc[0]+65), chr(enc[1]+65), chr(enc[2]+65)), end='')
        print()