Homework SourseBUILD A CRYPTO SYSTEM WITH C OR PYTHON PLease be able to run
BUILD A CRYPTO SYSTEM WITH C++ OR PYTHON PLease be able to run the code without errors
To build an RSA crypto system, you first need to find two random primes. Your primes will consist of 7 bits. You will set the first and the last bits to be 1 and randomly choose one-by-one the internal 5 bits. We could have used only 7 bits to store it, but to simplify the program, store it as a standard 32 bit integer, so there will be 25 leading 0 bits.
You may use any pseudorandom routine you like to generate random numbers. Very likely, your programming language has one. To generate a random bit, get a (pseudo-)random number, and extract the least significant bit to be your random bit. Print a line with the line number shown on the left and below that line, for one of the random numbers you got, produce a trace showing how the 5 individual bits were obtained, so show your 5 random numbers and the extracted bit for each.
You will use the variant of the Miller-Rabin algorithm (and not as it is generally presented) to test if your 7-bit number n is a prime. You will pick some random a’s, such that 0 < a < n. You can do it either by a process similar to getting a candidate prime above, or to simplify your program, you can just get a pseudorandom number and “cut it down to size” by computing its remainder modulo n, and discarding it if it is 0. If your number passes the Miller-Rabin test for 20 values of a, you may declare it as prime. For completeness, make sure that one of the n’s turned out not to be a prime number. So, if you immediately find the prime numbers you need, pick any number you know not to be prime and perform the test on it. If the test says it is possibly a prime, look for another number that you know not to be a prime. Print a line with the line number shown on the left and below that line, for one that turned out not to be prime and the a for which the answer was “not prime,” produce a trace.
Print a line with the line number shown on the left and below that line, for one n that turned out to be prime and one a for which the answer was “perhaps prime,” produce a trace. Now, given two primes p and q you found, you will get n = p × q. Note that p and q should be different, so you need to check for this. In a “real” search for large number the probability that p = q is so small that there is no need to check for this, but as you are working with very small numbers, you need to
check for that. Pick a small number to be the public key e. It has to be relatively prime with (n). To check if it is relatively prime and to find a multiplicative inverse to serve as the private key d, use the Extended Euclidean Algorithm, which you will code. If e is not relatively prime with (n), then find another small number. Do not do it randomly, start with 3 and go up until you find an appropriate e. In the extremely unlikely case (which would not happen in a real RSA implementation), that all the values of e you try do not work, just pick another pair of random primes and continue from there. And if the smallest e you find is big which here means bigger than (n) that is also fine for your project.
Print a line with the line number shown on the left and below that line, for the system that Alice (see later) will use, show how you found e, that is show how you used the algorithm on the various candidates for e until you got the right one. (If you are lucky, the first e you tried, worked—this is fine too.). Produce a trace for each e just as we had in class for the Extended Euclidean algorithm. For the value of e found, find the corresponding value of d and normalize it so that it is positive and smaller than (n). (If it happens that d = e, this will be fine too for your project, though of course not in a real RSA system.) Print a line with the line number shown on the left and below that line, list the value of d. So, the public key of Alice, is really the pair n, e and the private key of Alice is n, d; only she knows the latter, more precisely only she knows d. but you need to check for it in your implementation
Print a line with the line number shown on the left and below that line, list the following for Alice, both as integers and as sequences of bits: p,q,n,e,d.
Solution
import random
import math
import argparse
import re
KEY_INT = 100 # define the near max value
def main():
parser = argparse.ArgumentParser(__file__, description=\"RSA Encryption in Python\")
parser.add_argument(\"--generate\", \'-g\', help = \'Generate a Public and private Key\', action=\'store_true\')
parser.add_argument(\"--encode\", \'-e\', help = \'Encode message\', action=\'store\', dest=\'public_key\')
parser.add_argument(\"--decode\", \'-d\', help = \'Decode message\', action=\'store\', dest=\'private_key\')
parser.add_argument(\"--message\", \'-m\', help = \'Encoded or decoded message\', action=\'store\', dest=\'message\')
args=parser.parse_args()
#print if no argument is parsed
if not any([args.generate, args.public_key, args.private_key]):
parser.print_usage()
quit()
#check if g is in argument
elif args.generate and not any(([args.public_key, args.private_key, args.message])):
print_keys()
quit()
# check if encode message is correct
elif all([args.public_key, args.message]) and not args.generate:
print (\"\ Encrypted message\ \ \")
#split the string to get n and e
n, e = re.findall(r\'\\d+\', args.public_key)
print(encrypt(args.message,(n,e)))
print (\"\ === Output written to file ===\")
quit()
# check if decode message is correct
elif all([args.private_key, args.message]) and not args.generate:
print (\"\ Decrypted message\ \ \")
#split the string to get n and d regexp
n, d = re.findall(r\'\\d+\', args.private_key)
try:
print(decrypt(args.message,(n,d)))
except:
print(\"Decoding error!, check key\")
print (\"\ === Output written to file ===\")
quit()
else:
parser.print_help()
quit()
# display the key(private and public)
print_keys()
# get input from user
print (encrypt(65,(1457, 719)))
print (decrypt(486,(1457, 119)))\'\'\'
def miller_rabin_prime(n):
num_trials = 5
assert n >= 2
if n == 2:
return True
if n % 2 == 0:
return False
s = 0
d = n-1
while True:
quotient, remainder = divmod(d, 2)
if remainder == 1:
break
s += 1
d = quotient
assert(2**s * d == n-1) # make sure 2**s*d = n-1
# test whether it is a witness for the compositeness of n
def try_composite(a):
if pow(a, d, n) == 1: # defined as pow(x, y) % z = 1
return False
for i in range(s):
if pow(a, 2**i * d, n) == n-1:
return False
return True # definitely composite n
for i in range(num_trials):
a = random.randrange(2, n)
if try_composite(a):
return False
return True
def compute_pqnt():
# generate primes p and q
try:
p = findAPrime(2, KEY_INT)
while True:
q = findAPrime(2, KEY_INT)
if q != p:
break
except:
raise ValueError
#compute for n
n = p * q
# get the totient
t = (p-1) * (q-1)
#print (t)
# return p, q, n and the totient
return(p, q, n, t)
def findAPrime(a, b):
x = random.randint(a, b)
for i in range(0, int(10 * math.log(x) + 3)):
if miller_rabin_prime(x):
return x
else:
x += 1
raise ValueError
def coprime(a):
while True:
co_p = findAPrime(1, a) # find a prime number
# make surethe gcd is 1
g, x, y = extended_gcd(co_p, a)
# g is the remainder (last)
if co_p < a and g == 1:
break
return co_p
def compute_e(t):
e = coprime(t)
return e
def compute_d(e, t):
d = modinv(e, t)
return d
def extended_gcd(aa, bb):
lastremainder, remainder = abs(aa), abs(bb)
x, lastx, y, lasty = 0, 1, 1, 0
while remainder:
lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder) # get the remainder and quotient
x, lastx = lastx - quotient*x, x
y, lasty = lasty - quotient*y, y
return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)
def modinv(a, m):
g, x, y = extended_gcd(a, m)
if g != 1:
raise ValueError
return x % m
def print_keys():
print (\"\ Public Key (n, e)\")
p, q, n, t = compute_pqnt()
e = compute_e(t)
#public key is printed
print ((n,e))
print (\"\ Private Key (n, d)\")
d = compute_d(e, t)
# private key is printed
print ((n,d))
def encrypt(msg, public_key):
n, e = public_key
n = int(n)
e = int(e)
encrypted = \'\'
for i in range(len(msg)):
# pick each char and convert to ascii
int_msg = ord(msg[i])
encrypted += str(pow(int_msg,e) % n)+ \" \"
# Encoded message written in file
f = open(\'encoded.txt\',\'w\')
f.write(encrypted)
f.close()
return encrypted
def decrypt(msg, private_key):
n, d = private_key
n = int(n)
d = int(d)
decrypted = \'\'
# split each number with space
asc_msg = msg.split(\" \")
for num in asc_msg:
# convert to integer
num = int(num)
try:
# decode back to ascii
decrypted += str(chr(pow(num,d) % n))
except:
# cannot decode this
decrypted += str(\"?\")
# Decoded message written in file
f = open(\'decoded.txt\',\'w\')
f.write(decrypted)
f.close()
return decrypted
if __name__ == \'__main__\':
main()
