Python

Question needed solving is at bottom

#Function implementing the Extended Euclidean Algorithmimport mathdef egcd(a,b):        # b must not be zero otherwise the concept of gcd will fail    #base case    if a==0:        return [b,1,0,0]    #initial conditions    old_s=1    s=0    old_t=0    t=1    old_r=a    r=b    list_qoutients=[] #create a list of qoutients        while True:        q=old_r//r #qoutient        list_qoutients.append(q) #append q to the list_qoutients        #tuple style assign        old_r,r=r,old_r-(q*r)        old_s,s=s,old_s-(q*s)        old_t,t=t,old_t-(q*t)                if r==0:            # the qoutient will be the one obtained at iteration just before            # r becomes zero             # we are not returning the qoutient obtained at iteration             #where r becomes 0            #that is the second last element of the list            #list_qoutients            return [old_r,old_s,old_t,list_qoutients[-2]]        assert egcd(72,7)==[1,-3,31,3]assert egcd(24,30)==[6,-1,1,1]

# find_d

def find_d(k,e):

return egcd(k,e)[2]

assert find_d(72,7) == 31

assert find_d(1449000,7907) == 643043

#Key Set

def keyset(p, q, e):

n=p*q

#?(n) = (p-1)(q-1)

pi_n=(p-1)*(q-1)

d=find_d(pi_n,e)

return [n, e, d]

[n, e, d] = keyset(1381,1051,7907)

assert [n, e, d] == [1451431, 7907, 643043]

#Encryption

import math

M = 'hello there secret friend'

# required method

def encrypt(message, e, n):

# create an empty list

C = []

# loop through each character in message

for char in message:

# find ordinal value of character (ASCII integer value), find its power e mod n and append it to C

C.append(pow(ord(char), e, n))

# return the list

return C

# test code

cipher = encrypt(M, e, n)

assert cipher == [1041244, 739369, 892978, 892978, 799576, 304346, 1398703, 1041244, 739369, 38960, 739369, 304346,

642935, 739369, 1079616, 38960, 739369, 1398703, 304346, 360690, 38960, 722667, 739369, 462214,

282605]

NEEDED

decryption:

Create a function that when given an array of integers produced by the encrypt function, returns the original message.

Python Tip: To convert from the integer output of ord, use chr.

Python Tip: To convert from an array of characters to a string, try "".join(theArray).

Python Tip: To concatenate strings 'abc' and 'def', try 'abc' + 'def'

Python Tip: To raise a big number a to a large power b and then return the result mod c, use pow(a,b,c). This is much faster than (a**b)%c.

Please don't copy from other answers! They are incorrect. Will downvote

#Decryption

def decrypt(cipher, d, n):

# TODO: implement decrypt + decode

return decrypted_message

message = decrypt(cipher, d, n)

assert message == M

def decrypt (cipher, d, n): # TODO: implement decrypt + decode return decrypted_message message = decrypt(cipher, d, n) assert message == M