algorithms for performing diffiehellman key exchange code from algorithmsmathsprimecheck py written by goswamirahul and hai honag dang return true if num is a prime number else return false for positive integer n and given integer a that satisfies gcda n 1 the order of a modulo n is the smallest positive integer k that satisfies pow a k n 1 in other words ak 1 mod n order of certain number may or may not exist if not return 1 exception handeling 1 is the order of of 1 euler s totient function also known as phifunction n counts the number of integers between 1 and n inclusive which are coprime to n two numbers are coprime if their greatest common divisor gcd equals 1 code from algorithmsmathseulertotient py written by goswamirahul euler s totient function or phi function time complexity osqrtn result n for i in range2 intn 0 5 1 if n i 0 while n i 0 n i result result i if n 1 result result n return result def findprimitiverootn exception handeling 0 is the only primitive root of 1 to have order a and n must be relative prime with each other diffiehellman key exchange is the method that enables two entities in here alice and bob not knowing each other to share common secret key through notencrypted communication network this method use the property of oneway function discrete logarithm for example given a b and n it is easy to calculate x that satisfies ab x mod n however it is very hard to calculate x that satisfies ax b mod n for using this method large prime number p and its primitive root a must be given alice determine her private key in the range of 1 p1 this must be kept in secret return randint1 p1 def alicepublickeyaprk a p bob determine his private key in the range of 1 p1 this must be kept in secret return randint1 p1 def bobpublickeybprk a p alice calculate secret key shared with bob with her private key and bob s public key this must be kept in secret return powbpuk aprk p def bobsharedkeyapuk bprk p perform diffiehelmman key exchange if option is not none print explanation of process when option parameter is given option 1 if primecheckp is false printfp is not a prime number p must be large prime number return false try prootlist findprimitiverootp prootlist indexa except valueerror printfa is not a primitive root of p a must be primitive root of p return false aprk aliceprivatekeyp apuk alicepublickeyaprk a p bprk bobprivatekeyp bpuk bobpublickeybprk a p if option 1 printfalice s private key aprk printfalice s public key apuk printfbob s private key bprk printfbob s public key bpuk in here alice send her public key to bob and bob also send his public key to alice ashk alicesharedkeybpuk aprk p bshk bobsharedkeyapuk bprk p print fshared key calculated by alice ashk print fshared key calculated by bob bshk return ashk bshk code from algorithms maths prime_check py written by goswami rahul and hai honag dang return true if num is a prime number else return false for positive integer n and given integer a that satisfies gcd a n 1 the order of a modulo n is the smallest positive integer k that satisfies pow a k n 1 in other words a k 1 mod n order of certain number may or may not exist if not return 1 exception handeling 1 is the order of of 1 euler s totient function also known as phi function ϕ n counts the number of integers between 1 and n inclusive which are coprime to n two numbers are coprime if their greatest common divisor gcd equals 1 code from algorithms maths euler_totient py written by goswami rahul euler s totient function or phi function time complexity o sqrt n for positive integer n and given integer a that satisfies gcd a n 1 a is the primitive root of n if a s order k for n satisfies k ϕ n primitive roots of certain number may or may not be exist if so return empty list returns all primitive roots of n exception handeling 0 is the only primitive root of 1 to have order a and n must be relative prime with each other diffie hellman key exchange is the method that enables two entities in here alice and bob not knowing each other to share common secret key through not encrypted communication network this method use the property of one way function discrete logarithm for example given a b and n it is easy to calculate x that satisfies a b x mod n however it is very hard to calculate x that satisfies a x b mod n for using this method large prime number p and its primitive root a must be given alice determine her private key in the range of 1 p 1 this must be kept in secret alice calculate her public key with her private key this is open to public bob determine his private key in the range of 1 p 1 this must be kept in secret bob calculate his public key with his private key this is open to public alice calculate secret key shared with bob with her private key and bob s public key this must be kept in secret bob calculate secret key shared with alice with his private key and alice s public key this must be kept in secret perform diffie helmman key exchange print explanation of process when option parameter is given p must be large prime number a must be primitive root of p in here alice send her public key to bob and bob also send his public key to alice
import math
from random import randint



def prime_check(num):
    

    if num <= 1:
        return False
    if num == 2 or num == 3:
        return True
    if num % 2 == 0 or num % 3 == 0:
        return False
    j = 5
    while j * j <= num:
        if num % j == 0 or num % (j + 2) == 0:
            return False
        j += 6
    return True



def find_order(a, n):
    if (a == 1) & (n == 1):
        
        return 1
    if math.gcd(a, n) != 1:
        print ("a and n should be relative prime!")
        return -1
    for i in range(1, n):
        if pow(a, i) % n == 1:
            return i
    return -1



def euler_totient(n):
    
    result = n
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            while n % i == 0:
                n //= i
            result -= result // i
    if n > 1:
        result -= result // n
    return result



def find_primitive_root(n):
    
    if n == 1:
        
        return [0]
    phi = euler_totient(n)
    p_root_list = []
    for i in range (1, n):
        if math.gcd(i, n) != 1:
            
            continue
        order = find_order(i, n)
        if order == phi:
            p_root_list.append(i)
    return p_root_list




def alice_private_key(p):
    
    return randint(1, p-1)


def alice_public_key(a_pr_k, a, p):
    
    return pow(a, a_pr_k) % p


def bob_private_key(p):
    
    return randint(1, p-1)


def bob_public_key(b_pr_k, a, p):
    
    return pow(a, b_pr_k) % p


def alice_shared_key(b_pu_k, a_pr_k, p):
    
    return pow(b_pu_k, a_pr_k) % p


def bob_shared_key(a_pu_k, b_pr_k, p):
    
    return pow(a_pu_k, b_pr_k) % p


def diffie_hellman_key_exchange(a, p, option = None):
    
    if option is not None:
        
        option = 1
    if prime_check(p) is False:
        print(f"{p} is not a prime number")
        
        return False
    try:
        p_root_list = find_primitive_root(p)
        p_root_list.index(a)
    except ValueError:
        print(f"{a} is not a primitive root of {p}")
        
        return False

    a_pr_k = alice_private_key(p)
    a_pu_k = alice_public_key(a_pr_k, a, p)

    b_pr_k = bob_private_key(p)
    b_pu_k = bob_public_key(b_pr_k, a, p)

    if option == 1:
        print(f"Alice's private key: {a_pr_k}")
        print(f"Alice's public key: {a_pu_k}")
        print(f"Bob's private key: {b_pr_k}")
        print(f"Bob's public key: {b_pu_k}")

    

    a_sh_k = alice_shared_key(b_pu_k, a_pr_k, p)
    b_sh_k = bob_shared_key(a_pu_k, b_pr_k, p)
    print (f"Shared key calculated by Alice = {a_sh_k}")
    print (f"Shared key calculated by Bob = {b_sh_k}")

    return a_sh_k == b_sh_k