| Hosted by CoCalc | Download
#Простейший алгоритм цифровой подписи #Задаем параметры системы p = next_prime(2**512) q = next_prime(2**512 + 2**256) n = p*q phi = (p-1)*(q-1)
#Определяем ключи e = 65537 d = pow(e, -1, phi)
#Пользователь A публикует открытый ключ print(n, e)
(179769313486231590772930519078902473361797697894230657273430081157732675805502515650800778031342685000608576382426650243675906465425555674530873481592165113550026672087096385218852090143011078094501538315451057488366235256443849371457544103074132158615850022581027136881515050196403045352966622945220856139471, 65537)
#Пользователь A пописывает сообщение и отправляет сообщение с подписью пользователю B message = 1488 signed_message = pow(message, d, n) print(message) print(signed_message)
1488 50920423128934498333961695541500066042826520109016247673964194243874420070930764435143382755292356199252587440405041033486248597708300118168159216761512572263048718951698392907639311563637369282534553271280625450885985468527154358911340279578509640975458457813521468602860932086928229144942679449300876405956
#Пользователь В проверяет подписанное сообщение new_message = pow(signed_message, e, n) if new_message == message: print("Подпись верна") else: print("Подпись не верна")
Подпись верна
################### ################### ###################
import random
#Практический алгоритм цифровой подписи #Банк задает свои ключи и рассылает пользователям P = next_prime(2**1024) Q = next_prime(2**1024 + 2**256) N = P*Q PHI = (P-1)*(Q-1) E = next_prime(randint(2, PHI/2)) D = pow(E, -1, PHI) print("N = " + repr(N)) print("E = " + repr(E))
N = 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756182653958727804968634432126506764476120118100386074475419245777099931146505020360229996526688497686702574001484920775448640824129293499723972737217783905914724004472471754578210097686417653084952167535757127048897711754283368046405939988230504173810366388928215800956417364913724196912776166894836947229274370788948248722981212164447491276306126569495930161089188275264534013453464107227 E = 5350868146578789309334897396415574869498177935100748863286037674207277315366198503388923615674081816055206777016096372882039524353759006778454522229887825030078698822183034984569397255608024467263198638092198838414070680992637889005137571763404931105621459705731426375465388443042761834759454602526568715339240897522893579675389023242750283052131559337373764359545341691620179016668970372679651204604533274230069706265323006526238204642813416974331084682747354751335886103763544317273195154371883132196892325840639724314493446815290732348271071101919959728672010791490858908721798765612462646967118424581384309324803
#Пользователь А задает свои ключи и рассылает их p = next_prime(2**512) q = next_prime(2**512 + 2**256) n = p*q phi = (p-1)*(q-1) e = next_prime(randint(2, phi/2)) d = pow(e, -1, phi) print("n_A = " + repr(n)) print("e_A = " + repr(e))
n_A = 179769313486231590772930519078902473361797697894230657273430081157732675805502515650800778031342685000608576382426650243675906465425555674530873481592165113550026672087096385218852090143011078094501538315451057488366235256443849371457544103074132158615850022581027136881515050196403045352966622945220856139471 e_A = 22416468858994591332812176797923264529743567600840131100368106729967536557454558736336130372564508546687490696379671294940776262237972455474617557786417664479691872482690424871727691657119145530441700150264919819385148441989961873715712405727513509300957888621355395885978039642336575564407142684653713884447
#Пользователь А подписывает сообщение и отправляет его вместе с подписью банку message = 41 message_x = int(pow(message, d, n)) signed_message = pow(message_x, E, N) print(message) print(signed_message)
41 24991441131222318934362200188110646426820533155443296266891238611718707792357459329893057161661092463329449922999661473862612311062133873149181842043701196086230001921763563238009966878928638016916764750035741663076926232183954489142245988808456981602409265188513670491177340545112968947342184883540517268750385559487491208473272310108574231261309594812760697464437223613265344147571133546032156118544479665421353661199624645713159520455223647818757317473520279924865129395447827950497521374766921598678775741720308075111371441715557140072875815663475405481308676079111134224166112127330120817142422094791920683127923
#Банк проверяет подписанное сообщение y = int(pow(signed_message, D, N)) new_message = pow(y, e, n) if new_message == message: print("Подпись верна") else: print("Подпись не верна")
Подпись верна
################### ################### ###################
#Алгоритм разложения n на простые делители при известных e, d #Задаем параметры системы p = next_prime(2**128) q = next_prime(2**128 + 2**21) n = p*q phi = (p-1)*(q-1) e = 65537 d = pow(e, -1, phi)
def factor_n(n, e, d): while (True): g = randint(2, n) while (g == p or g == q): g = randint(2, n) g = pow(g, 1, n) gcd_g_n = gcd(g, n) if (gcd_g_n != 1): return(gcd_g_n) k = int(e) * int(d) - 1 t = 0 k_factors = list(factor(k)) if (k_factors[0][0] == 2): t = k_factors[0][1] for i in range (1, t+1): y = pow(g, k/(2^i), n) if (y == n - 1): break if (y != 1): return(gcd(int(y-1), int(n)))
s = factor_n(n, e, d) s == p s == q
True False
#4.1 def ex4_1(e, n): factors = list(factor(n)) print(factor(n)) d = pow(e, -1, (factors[0][0]-1)*(factors[1][0]-1)) print("d = " + repr(d))
ex4_1(7, 3007) ex4_1(19, 2059) ex4_1(17, 3127)
31 * 97 d = 823 29 * 71 d = 619 53 * 59 d = 2129
#4.2 n = 3007 e = 7 m = 101 print("Encrypted message 1: " + repr(pow(m, e, n))) n = 3127 e = 17 m = 61 print("Encrypted message 2: " + repr(pow(m, e, n)))
Encrypted message 1: 2513 Encrypted message 2: 3101
#4.3 n = 3007 d = 823 x = 69 print("Message 1: " + repr(pow(x, d, n))) n = 3127 d = 2129 x = 95 print("Message 2: " + repr(pow(x, d, n)))
Message 1: 174 Message 2: 1952
#4.4 n = 17201 phi = 16932 p, q = var('p', 'q') sol = solve([p*q == n, (p-1)*(q-1) == phi], p, q) print(sol[0][0], sol[0][1])
(p == 103, q == 167)
103*167 == n
True
n = 18419 phi = 18144 sol = solve([p*q == n, (p-1)*(q-1) == phi], p, q) print(sol[0][0], sol[0][1])
(p == 163, q == 113)
163*113 == n
True
#4.5 P = 17 Q = 23 N = P*Q PHI = (P-1)*(Q-1) E = 53 D = pow(E, -1, PHI) print("D = " + repr(D)) p = 11 q = 19 n = p*q phi = (p-1)*(q-1) e = 31 d = pow(e, -1, phi) print("d = " + repr(d))
D = 93 d = 151
#4.6 message = 61 message_x = int(pow(message, d, n)) signed_message = pow(message_x, E, N) print(signed_message)
177
message = 82 message_x = int(pow(message, d, n)) signed_message = pow(message_x, E, N) print(signed_message)
372
#4.7 message = 67 signed_message= 272 y = int(pow(signed_message, D, N)) new_message = pow(y, e, n) if new_message == message: print("Подпись верна") else: print("Подпись не верна")
Подпись верна
message = 17 signed_message= 201 y = int(pow(signed_message, D, N)) new_message = pow(y, e, n) if new_message == message: print("Подпись верна") else: print("Подпись не верна")
Подпись не верна
message = 72 signed_message= 349 y = int(pow(signed_message, D, N)) new_message = pow(y, e, n) if new_message == message: print("Подпись верна") else: print("Подпись не верна")
Подпись верна
#4.8 P = 19 Q = 37 N = P*Q PHI = (P-1)*(Q-1) E = 43 D = pow(E, -1, PHI) print("D = " + repr(D)) p = 23 q = 13 n = p*q phi = (p-1)*(q-1) e = 47 d = pow(e, -1, phi) print("d = " + repr(d))
D = 211 d = 191
#4.9 message = 50 message_x = int(pow(message, d, n)) signed_message = pow(message_x, E, N) print(signed_message)
466
message = 27 message_x = int(pow(message, d, n)) signed_message = pow(message_x, E, N) print(signed_message)
367
#4.10 message = 39 signed_message= 57 y = int(pow(signed_message, D, N)) new_message = pow(y, e, n) if new_message == message: print("Подпись верна") else: print("Подпись не верна")
Подпись не верна
message = 74 signed_message= 48 y = int(pow(signed_message, D, N)) new_message = pow(y, e, n) if new_message == message: print("Подпись верна") else: print("Подпись не верна")
Подпись верна