Guest User

Untitled

a guest
Nov 17th, 2019
61
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import random
  2.  
  3. def gcd(a: int, b: int):
  4.     while (b):
  5.         a, b = b, a % b
  6.     return a
  7.  
  8.  
  9. def is_prime(n):
  10.     return 1 == gcd(n, 1)
  11.  
  12.  
  13. def get_p():
  14.     p = random.randint(500000, 3000000)
  15.     while not is_prime(p):
  16.         p = random.randint(500000, 3000000)
  17.     return p
  18.  
  19.  
  20. def get_q(p):
  21.     x = 2
  22.     q = 0
  23.     while x < p - 1:
  24.         if (p - 1) % x == 0:
  25.             if is_prime(x):
  26.                 q = x
  27.         x += 1
  28.     return q
  29.  
  30.  
  31. def get_a(p, q):
  32.     a = 2
  33.     while a < p - 1:
  34.         if pow(a, q, p) == 1:
  35.             break
  36.         a += 1
  37.     return a
  38.  
  39.  
  40. p = get_p()
  41. q = get_q(p)
  42. a = get_a(p, q)
  43. print(p, q, a)
  44.  
  45. def get_H(message):
  46.     H = 0
  47.     for i in range(len(message)):
  48.         H = H + bin(ord(message[i])).count('1')
  49.     return H
  50.  
  51.  
  52. def check(p, q, a):
  53.     k = random.randint(2, q - 1)
  54.     x = random.randint(2, q - 1)
  55.  
  56.     y = pow(a, x, p)
  57.     print("Введите сообщение")
  58.     message = input()
  59.  
  60.     H = get_H(message)
  61.     if H % p == 0:
  62.         H = 1
  63.  
  64.     while True:
  65.         k = random.randint(2, q - 1)
  66.         r1 = pow(a, k, p) % q
  67.         if r1 == 0:
  68.             continue
  69.         s = (x * r1 + k * H) % q
  70.         if s != 0:
  71.             break
  72.  
  73.     print(f'Сгенерированные r1 = {r1}, s = {a}')
  74.  
  75.     v = pow(H, q - 2, q)
  76.     z1 = (s * v) % q
  77.     z2 = ((q - r1) * v) % q
  78.     u = ((pow(a, z1) * pow(y, z2)) % p) % q
  79.  
  80.     print(f'Вычисленное u = {u}')
  81.  
  82.     if u == r1:
  83.         print('OK')
  84.         return
  85.     print('Подпись недействительна')
  86.  
  87.  
  88. check(p, q, a)
RAW Paste Data