SharedSigning.sagewsOpen in CoCalc
#Простейший алгоритм цифровой подписи
#Задаем параметры системы
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("Подпись не верна")
Подпись верна