|
| 1 | +# Copyright (c) 2010 Russell Dias |
| 2 | +# Licensed under the MIT licence. |
| 3 | +# http://www.inversezen.com |
| 4 | +# |
| 5 | +# This is an implementation of the RSA public key |
| 6 | +# encryption written in Python by Russell Dias |
| 7 | + |
| 8 | +__author__ = 'Russell Dias // inversezen.com' |
| 9 | +# Py3k port done by Senthil (senthil@uthcode.com) |
| 10 | +__date__ = '05/12/2010' |
| 11 | +__version__ = '0.0.1' |
| 12 | + |
| 13 | +import random |
| 14 | +from math import log |
| 15 | + |
| 16 | +def gcd(u, v): |
| 17 | + """ The Greatest Common Divisor, returns |
| 18 | + the largest positive integer that divides |
| 19 | + u with v without a remainder. |
| 20 | + """ |
| 21 | + while v: |
| 22 | + u, v = u, u % v |
| 23 | + return u |
| 24 | + |
| 25 | +def eec(u, v): |
| 26 | + """ The Extended Eculidean Algorithm |
| 27 | + For u and v this algorithm finds (u1, u2, u3) |
| 28 | + such that uu1 + vu2 = u3 = gcd(u, v) |
| 29 | +
|
| 30 | + We also use auxiliary vectors (v1, v2, v3) and |
| 31 | + (tmp1, tmp2, tmp3) |
| 32 | + """ |
| 33 | + (u1, u2, u3) = (1, 0, u) |
| 34 | + (v1, v2, v3) = (0, 1, v) |
| 35 | + while (v3 != 0): |
| 36 | + quotient = u3 // v3 |
| 37 | + tmp1 = u1 - quotient * v1 |
| 38 | + tmp2 = u2 - quotient * v2 |
| 39 | + tmp3 = u3 - quotient * v3 |
| 40 | + (u1, u2, u3) = (v1, v2, v3) |
| 41 | + (v1, v2, v3) = (tmp1, tmp2, tmp3) |
| 42 | + return u3, u1, u2 |
| 43 | + |
| 44 | +def stringEncode(string): |
| 45 | + """ Brandon Sterne's algorithm to convert |
| 46 | + string to long |
| 47 | + """ |
| 48 | + message = 0 |
| 49 | + messageCount = len(string) - 1 |
| 50 | + |
| 51 | + for letter in string: |
| 52 | + message += (256**messageCount) * ord(letter) |
| 53 | + messageCount -= 1 |
| 54 | + return message |
| 55 | + |
| 56 | +def stringDecode(number): |
| 57 | + """ Convert long back to string |
| 58 | + """ |
| 59 | + |
| 60 | + letters = [] |
| 61 | + text = '' |
| 62 | + integer = int(log(number, 256)) |
| 63 | + |
| 64 | + while(integer >= 0): |
| 65 | + letter = number // (256**integer) |
| 66 | + letters.append(chr(letter)) |
| 67 | + number -= letter * (256**integer) |
| 68 | + integer -= 1 |
| 69 | + for char in letters: |
| 70 | + text += char |
| 71 | + |
| 72 | + return text |
| 73 | + |
| 74 | +def split_to_odd(n): |
| 75 | + """ Return values 2 ^ k, such that 2^k*q = n; |
| 76 | + or an odd integer to test for primiality |
| 77 | + Let n be an odd prime. Then n-1 is even, |
| 78 | + where k is a positive integer. |
| 79 | + """ |
| 80 | + k = 0 |
| 81 | + while (n > 0) and (n % 2 == 0): |
| 82 | + k += 1 |
| 83 | + n >>= 1 |
| 84 | + return (k, n) |
| 85 | + |
| 86 | +def prime(a, q, k, n): |
| 87 | + if pow(a, q, n) == 1: |
| 88 | + return True |
| 89 | + elif (n - 1) in [pow(a, q*(2**j), n) for j in range(k)]: |
| 90 | + return True |
| 91 | + else: |
| 92 | + return False |
| 93 | + |
| 94 | +def miller_rabin(n, trials): |
| 95 | + """ |
| 96 | + There is still a small chance that n will return a |
| 97 | + false positive. To reduce risk, it is recommended to use |
| 98 | + more trials. |
| 99 | + """ |
| 100 | + # 2^k * q = n - 1; q is an odd int |
| 101 | + (k, q) = split_to_odd(n - 1) |
| 102 | + |
| 103 | + for trial in range(trials): |
| 104 | + a = random.randint(2, n-1) |
| 105 | + if not prime(a, q, k, n): |
| 106 | + return False |
| 107 | + return True |
| 108 | + |
| 109 | +def get_prime(k): |
| 110 | + """ Generate prime of size k bits, with 50 tests |
| 111 | + to ensure accuracy. |
| 112 | + """ |
| 113 | + prime = 0 |
| 114 | + while (prime == 0): |
| 115 | + prime = random.randrange(pow(2,k//2-1) + 1, pow(2, k//2), 2) |
| 116 | + if not miller_rabin(prime, 50): |
| 117 | + prime = 0 |
| 118 | + return prime |
| 119 | + |
| 120 | +def modular_inverse(a, m): |
| 121 | + """ To calculate the decryption exponent such that |
| 122 | + (d * e) mod phi(N) = 1 OR g == 1 in our implementation. |
| 123 | + Where m is Phi(n) (PHI = (p-1) * (q-1) ) |
| 124 | +
|
| 125 | + s % m or d (decryption exponent) is the multiplicative inverse of |
| 126 | + the encryption exponent e. |
| 127 | + """ |
| 128 | + g, s, t = eec(a, m) |
| 129 | + if g == 1: |
| 130 | + return s % m |
| 131 | + else: |
| 132 | + return None |
| 133 | + |
| 134 | +def key_gen(bits): |
| 135 | + """ The public encryption exponent e, |
| 136 | + can be an artibrary prime number. |
| 137 | +
|
| 138 | + Obviously, the higher the number, |
| 139 | + the more secure the key pairs are. |
| 140 | + """ |
| 141 | + e = 17 |
| 142 | + p = get_prime(bits) |
| 143 | + q = get_prime(bits) |
| 144 | + d = modular_inverse(e, (p-1)*(q-1)) |
| 145 | + return p*q,d,e |
| 146 | + |
| 147 | +def write_to_file(e, d, n): |
| 148 | + """ Write our public and private keys to file |
| 149 | + """ |
| 150 | + public = open("publicKey", "w") |
| 151 | + public.write(str(e)) |
| 152 | + public.write("\n") |
| 153 | + public.write(str(n)) |
| 154 | + public.close() |
| 155 | + |
| 156 | + private = open("privateKey", "w") |
| 157 | + private.write(str(d)) |
| 158 | + private.write("\n") |
| 159 | + private.write(str(n)) |
| 160 | + private.close() |
| 161 | + |
| 162 | + |
| 163 | +if __name__ == '__main__': |
| 164 | + bits = input("Enter the size of your key pairs, in bits: ") |
| 165 | + |
| 166 | + n, d, e = key_gen(int(bits)) |
| 167 | + |
| 168 | + #Write keys to file |
| 169 | + write_to_file(e, d, n) |
| 170 | + |
| 171 | + print("Your keys pairs have been saved to file") |
| 172 | + |
| 173 | + m = input("Enter the message you would like to encrypt: ") |
| 174 | + |
| 175 | + m = stringEncode(m) |
| 176 | + encrypted = pow(m, e, n) |
| 177 | + |
| 178 | + print("Your encrypted message is: %s" % encrypted) |
| 179 | + decrypted = pow(encrypted, d, n) |
| 180 | + message = stringDecode(decrypted) |
| 181 | + print("You message decrypted is: %s" % message) |
0 commit comments