SHARE
TWEET

Untitled

a guest Nov 17th, 2019 59 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top