-
Notifications
You must be signed in to change notification settings - Fork 0
/
rsa_encryption.py
148 lines (129 loc) · 4.46 KB
/
rsa_encryption.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
import random
"""Calculates Greatest Common Denominator"""
def find_gcd(a, b):
while b != 0:
a, b = b, a % b
return a
"""Returns the multiplicative inverse of two numbers e and z"""
def mult_inverse(e, z):
d = 0
x1 = 0
x2 = 1
y1 = 1
temp_z = z
while e > 0:
temp1 = temp_z / e
temp2 = temp_z - temp1 * e
temp_z = e
e = temp2
x = x2 - temp1 * x1
y = d - temp1 * y1
x2 = x1
x1 = x
d = y1
y1 = y
if temp_z == 1:
return d + z
"""Checks if the argument num is a prime number"""
def is_prime(num):
if num == 2:
return True
if num < 2 or num % 2 == 0:
return False
for n in xrange(3, int(num**0.5) + 2, 2):
if num % n == 0:
return False
return True
"""Generates a key pair from the two prime numbers provided"""
def generate_keypair(p, q):
n = p * q
z = (p - 1) * (q - 1)
e = random.randrange(1, z)
# Check if the numbers are coprime
g = find_gcd(e, z)
while g != 1:
e = random.randrange(1, z)
g = find_gcd(e, z)
d = mult_inverse(e, z)
# Public key (e, n) and private key (d, n)
return ((e, n), (d, n))
"""RSA Encryption"""
def encrypt(pk, plaintext):
# Unpack the key into it's components
key, n = pk
# Apply RSA algorithm to each character's ASCII value of the plaintext
cipher = [(ord(char) ** key) % n for char in plaintext]
# Return the array of bytes (ciphertext)
return cipher
"""RSA Decryption"""
def decrypt(pk, ciphertext):
# Unpack the key into it's components
key, n = pk
# Reconstruct the plaintext from the ciphertext
plain = [chr((char ** key) % n) for char in ciphertext]
# Combine the characters into a string and return
return ''.join(plain)
if __name__ == '__main__':
print "RSA ENCRYPTION"
menu = {}
menu['1'] = "Test RSA"
menu['2'] = "Encrypt"
menu['3'] = "Decrypt"
menu['4'] = "Exit"
while True:
options = menu.keys()
options.sort()
for entry in options:
print entry, menu[entry]
selection = raw_input("Please Select:")
if selection == '1':
p = int(raw_input("Enter first prime: "))
if not is_prime(p):
while not is_prime(p):
print "", p, " is not prime"
p = int(raw_input("Enter first prime: "))
q = int(raw_input("Enter second prime: "))
if not is_prime(q):
while not is_prime(q):
print "", q, " is not prime"
q = int(raw_input("Enter second prime: "))
print "Generating key pairs"
public, private = generate_keypair(p, q)
print "Public key: ", public, " Private key: ", private
message = raw_input("Enter message to be encrypted: ")
encrypted_msg = encrypt(private, message)
print "ENCRYPTED: "
print ''.join(map(lambda x: str(x), encrypted_msg))
print "Decrypting with public key ", public
print "DECRYPTED:"
print decrypt(public, encrypted_msg)
elif selection == '2':
p = int(raw_input("Enter first prime: "))
if not is_prime(p):
while not is_prime(p):
print "", p, " is not prime"
p = int(raw_input("Enter first prime: "))
q = int(raw_input("Enter second prime: "))
if not is_prime(q):
while not is_prime(q):
print "", q, " is not prime"
q = int(raw_input("Enter second prime: "))
print "Generating key pairs"
public, private = generate_keypair(p, q)
print "Public key: ", public, " Private key: ", private
message = raw_input("Enter message to be encrypted: ")
encrypted_msg = encrypt(private, message)
print "ENCRYPTED: "
print ''.join(map(lambda x: str(x), encrypted_msg))
elif selection == '3':
ciphertxt = raw_input("Enter message to be decrypted: ")
print "Enter the public keys: "
public = map(int, input())
public = tuple(public)
print "Decrypting with public key ", public
print "DECRYPTED:"
print decrypt(public, ciphertxt)
elif selection == '4':
break
else:
print "Unknown Option Selected!"