SharedAuthentication .sagewsOpen in CoCalc
import random
#2879.74 202 feb
#Протокол Фиата-Шамира
#УЦ генерирует большие простые числа, держит их в секрете
p = next_prime(randint(2**5, 2**10))
q = next_prime(randint(2**5, 2**10))
#Рассчитывает модуль системы, публиует его
n = p*q
print("n = " + repr(n))
n = 486853
#Участник A рассчитывает свой секретный ключ
sk = randint(1, n - 1)
sk
while (gcd(sk, n) != 1):
    sk = randint(1, n - 1)
#Рассчитывает свой открытый ключ, публикует его
pk = pow(sk, -2, n)
print("pk = " + repr(pk))
269618 pk = 147511
#Участник А хочет доказать участнику B свою подлинность.
#Для этого он вычисляет заявку
r = randint(1, n - 1)
r
gamma = pow(r, 2, n)
#И отправляет ее участнику B
print("Witness: " + repr(gamma))
14682 Witness: 372098
#Участник B посылает запрос участнику A
x = randint(0, 1)
print("Challenge: " +repr(x))
Challenge: 1
#Участник A вычисляет ответ и отправляет его участнику B
y = r*pow(sk, x, n) % n
print("Response: " + repr(y))
Response: 416586
#Участник B проверяет ответ и принимает решение о том, пройдена ли проверка
if (pow(y, 2, n) * pow(pk, x, n) % n == gamma):
    print("Ответ верный")
else:
    print("Ошибка, ответ неверный")
Ответ верный
#Далее эта процедура повторяется еще t-1 раз, где t - параметр безопасности. Вероятность обмана после этого всего 1/2^t.
#################################
#################################
#################################
#################################
#Протокол Фейга-Фиата-Шамира
#УЦ генерирует большие простые числа, держит их в секрете
p = next_prime(randint(2**256, 2**300))
q = next_prime(randint(2**256, 2**300))
#Рассчитывает модуль системы, публиует его
n = p*q
print("n = " + repr(n))
#Также УЦ выбирает параметры безопасности k и t:
k = 5
t = 4
print("k = " + repr(k) + "; t = " + repr(t))
n = 1629356049781768489367892699487972790637416392691375703452756040201754724436706707994521069745666865210241247989324743099080504461001368404829406418514836054806732807655348649541811 k = 5; t = 4
#Участник A рассчитывает свой секретный ключ
sk = [n]*k
for i in range(len(sk)):
    while (gcd(sk[i], n) != 1):
        sk[i] = randint(1, n - 1)
#Рассчитывает свой открытый ключ, публикует его
pk = [0]*k
for i in range(len(sk)):
    pk[i] = pow(sk[i], 2, n)
print("pk = " + repr(pk))
pk = [63835447363689861081491963895406140047747095991771306948774385601222706292811444276824988169124014618258559302615277968823101399214937185261032629728213435670299087142360556468141, 772160521801652879024912360672700801036619151645887555093357642965159303149444521704881654989139504525399551574049959848737737540471960208561379443751502774944670072176413447175519, 45844617000093876203564383220758342753066545577516957142480057403873675325400854957488090196251501247311730730809110876797117630509598534661650016603653410740110189714032990633844, 1449367072039279390659842203713853071979887595400517654115375814335051565340591805064761868255220876377879532976807785825990054577783072555033489391665898417658835706798826822412335, 950159110172408674771624255413753996018334800491384243390713905274973792775672726241642268471474074544574533479970588264650104922060057761705820698958025433000392244930106589102877]
#Участник А хочет доказать участнику B свою подлинность. Протокол доказательства будет состоять из t раундов
for i in range(t):
    #Для этого он вычисляет заявку
    r = randint(1, n - 1)
    x = pow(r, 2, n)
    #И отправляет ее B
    print("Witness " + repr(i) + ": " + repr(x))
    #Участник B создает запрос и отправляет его A
    e = [randint(0, 1) for j in range(k)]
    print("Challenge " + repr(i) + ": " + repr(e))
    #A вычисляет ответ и отправляе B
    y = r
    for j in range(k):
        y = y * pow(sk[i], e[i], n) % n
    print("Response " + repr(i) + ": " + repr(y))
    #B проверяет ответ
    res = x
    for j in range(k):
        res = res * pow(pk[i], e[i], n) % n
    if pow(y, 2, n) == res:
        print("Ответ верный")
    else:
        print("Ошибка! Ответ неверный")
        break
Witness 0: 1452039084459842718534858222694238727868771011770944581788307676319440066222202686616438705577108679181548554558499416318819833873835499350511676364718249340874272816690982882246452 Challenge 0: [0, 1, 1, 0, 1] Response 0: 1549650089778517162721363781435488426411180702019262645320516049804174714389256112760476979149127393436117208436629769570399625054303873026136426852589399788513438441733468324543814 Ответ верный Witness 1: 823666594193584984587875986415367891579788996740077165370138029102492184468477616458697604874320656532196018419575425199915830916852514386789589455384146929551124028115230884769845 Challenge 1: [1, 0, 1, 1, 1] Response 1: 957479901475459749051843846040681989784957602148463389533448833352007061682762713843684750521705899717779109862420350151671744593441013212002730142507718077470816608821538999291282 Ответ верный Witness 2: 395162890238898787754542565069175592172649351247489712266774024197012317946097217160476776959877348710810313413576622170760296817038381945975544857873862463836029642146178739758543 Challenge 2: [0, 0, 1, 1, 1] Response 2: 898992564669507879931345472894774177799861386541729549300227668675937130224364237692882922386159443703374625342612371947452651334560642591975030128631098009012849321378229624352695 Ответ верный Witness 3: 560628755040169129950375976207673207405024548398467301084296941122968221073818923713524658440305708325988457973677638207672043589860388123618190761487008123653395514692521216750700 Challenge 3: [0, 1, 0, 1, 1] Response 3: 1401071734970457927977754127761103257329552242277903886599580787304380536972714431945472930771729495098688130795855604535676211053829605126683424256300427020972985990376142964194199 Ответ верный
#################################
#################################
#################################
#################################
#Протокол Шнорра
#УЦ генерирует параметры системы
# generated = False
# p = 0
# g = 0
# q = 0
# p = next_prime(randint(2**5, 2**10))
# while (not generated):
#     p = next_prime(p)
#     factors = list(factor(p))
#     for x in factors:
#         if x[0] > 2**1:
#             F = GF(p)
#             for j in F:
#                 if j !=0 and j.order() == x:
#                     q = x
#                     g = j
#                     generated = True
#                     break
#             if generated:
#                 break
p = 48731
q = 443
g = 11444
t = 4
print("p = " + repr(p) + "\nq = " + repr(q) + "\ng = " + repr(g) + "\nt = " + repr(t))
p = 48731 q = 443 g = 11444 t = 4
#Участник A генерирует свою пару ключей
sk = randint(1, q-1)
pk = pow(g, -sk, p)
#И публикует открытый ключ
print("pk = " + repr(pk))
pk = 42309
#A отправляет заявку
r = randint(1, q-2)
gamma = pow(g, r, p)
print("Witness: " + repr(gamma))
Witness: 28787
#B делает запрос
x = randint(0, 2**t - 1)
print("Challenge: " + repr(x))
Challenge: 15
#A вычисляет ответ и отправляе B
y = r + sk*x % q
print("Response: " + repr(y))
Response: 759
#B проверяет ответ
res = pow(g, y, p) * pow(pk, x, p) % p
if gamma == res:
    print("Ответ верный")
else:
    print("Ошибка! Ответ неверный")
Ответ верный
#Безопасность протокола зависит от параметра t и сложность вскрытия примерно равна 2**t. Таким образом в зависимости от размера t возможно использование нескольких раундов протокола.
#################################
#################################
#################################
#################################
#Протокол Брикелла-МакКарли
#Задание и публикация параметров системы
p = next_prime(randint(2**20, 2**25))
k = 3
t = 5
q = 0
w = 0
while (q == 0 or w == 0):
    factors = list(factor(p-1))
    q = 0
    for x in factors:
        if x[0] >= 2**k and x[0]*x[0] % (p-1) != 0:
            q = x[0]
            break
    if (q == 0):
        p = next_prime(p)
    else:
        for x in factors:
            if x[0] >= 2**k and x[0] != q:
                w = x[0]
                break
g = 0
for x in GF(p):
    if x != 1 and pow(x, q, p) == 1:
        g = x
        break
print("p = " + repr(p) + "\ng = " + repr(g) + "\nk = " + repr(k) + "\nt = " + repr(t))
p = 8492249 g = 11461 k = 3 t = 5
#Генерация ключей абонента A
sk = randint(2, p)
pk = pow(g, -sk, p)
print("pk = " + repr(pk))
pk = 2711408
#Рабочий этап алгоритма, A доказывает B свою подлинность
#Для этого он вычисляет заявку
r = randint(1, p)
x = pow(g, r, p)
#И отправляет ее B
print("Witness: " + repr(x))
#Участник B создает запрос и отправляет его A
e = randint(1, 2^t - 1)
print("Challenge: " + repr(e))
#A вычисляет ответ и отправляе B
y = (r + sk*e) % (p-1)
print("Response: " + repr(y))
#B проверяет ответ
res = pow(g, y, p) * pow(pk, e, p) % p
if x == res:
    print("Ответ верный")
else:
    print("Ошибка! Ответ неверный")
Witness: 226174 Challenge: 20 Response: 2564473 Ответ верный
q = next_prime(2^1023)
while not is_prime(2*q + 1):
    q = next_prime(q)
q
521