CCg08NY9

1import random
2import codecs
3import math
4import sys
5
6
7def prime(n): # Проверка на простое число
8     d = 2
9     while d ** 2 <= n and n % d != 0:
10        d += 1
11     if d ** 2 > n:
12        return True
13     else:
14        return False
15
16
17def mutprime(num1, num2): # Проверка на взаимнопростые числа
18     if math.gcd(num1, num2) == 1:
19        return True
20     return False
21
22
23def fact(eu): # Факторизация
24     i = 2
25     f = []
26     while prime(eu) == False:
27        if eu % i == 0 and prime(i) == True:
28            eu = eu / i
29            if i not in f:
30                f.append(i)
31        else:
32            i += 1
33     f.append(eu)
34     return f
35
36
37def fastpow(g, b, p): # Быстрое возведение в степень
38     if b == 0:
39        return 1
40     if b % 2 == 1:
41        return (g * fastpow(g, b - 1, p)) % p
42     d = fastpow(g, b / 2, p)
43     return (d ** 2) % p
44
45
46def primeroot(p1, g1): # Проверка на первообразный корень по модулю
47     if mutprime(p1, g1) == True:
48         euler = p - 1
49         count = 0
50         f = fact(euler)
51         print(f)
52         # г в степени п-1 делить на каждый из простых множителей числа п-1 и по
53        модулю п
54         for i in range(len(f)):
55             if fastpow(g1, euler / f[i], p1) != 1:
56                count += 1
57        else:
58                return False
59        if count == len(f):
60            return True
61     return False
62
63
64print("enter p")
65p = int(input())
66if prime(p) == False:
67     print("p isn't prime number")
68     sys.exit()
69print("enter g")
70g = int(input())
71if primeroot(p, g) == False:
72    print("g isn't prime root")
73else:
74    a = random.randint(1, p - 1)
75    b = random.randint(1, p - 1)
76    print("privet keys (randoms): а={0}, b={1}".format(a, b))
77    A = fastpow(g, a, p)
78    B = fastpow(g, b, p)
79     '''
80    file = codecs.open('1.txt', 'r', 'utf-8')
81    B =int(file.read())
82     '''
83    print("public keys: A={0}, B={1}".format(A, B))
84    secret_key = fastpow(g, a * b, p)
85    secret_key_a = fastpow(B, a, p)
86    secret_key_b = fastpow(A, b, p)
87    print("secret keys: S={0}, key_a={1}, key_b={2}".format(secret_key,secret_key_a, secret_key_b))