У меня есть проблема:
У меня также есть версия этой проблемы для Python здесь:
импортировать json
импортировать sys, os, itertools
sys.path.append(os.path.abspath(os.path.join('..')))
из импорта playcrypt.tools *
из импорта playcrypt.new_tools *
из импорта playcrypt.primitives *
из playcrypt.games.game_bind импортировать GameBIND
из playcrypt.simulator.bind_sim импортировать BINDSim
из playcrypt.games.game_hide импортировать GameHIDE
из playcrypt.simulator.hide_sim импортировать HIDESim
определение ДОБАВИТЬ (а, б):
вернуть а+б
МУЛЬТ (а, б):
вернуть а*б
определение INT_DIV (а, N):
возврат (a//N, a%N)
деф MOD(a,N):
вернуть%N
защита EXT_GCD(a,N):
возврат egcd(a,N)
определение MOD_INV (а, N):
рез = modinv (а, N)
если рез == Нет:
поднять ValueError("Обратное значение не существует")
вернуть разрешение
определение MOD_EXP(a,n,N):
вернуть exp(a,n,N)
"""
Пусть p — простое число битовой длины k >= 8 такое, что (p - 1)/2 также является простым числом. Пусть г,
h — две различные образующие группы G = Z_p^*. Пусть CS = (P, C, V) —
схема фиксации, составляющие алгоритмы которой следующие, где сообщение
M находится в Z_{p-1}:
"""
защита P():
пи = (г, ч)
вернуть пи
определение С (пи, М):
"""
:param pi: общедоступные параметры
:param M: сообщение, которое нужно зафиксировать, элемент Z_{p-1}
:return: вернуть ключ фиксации и отмены
"""
(г, ч) = пи
K = случайное_Z_N (p-1)
А = MOD_EXP (г, К, р)
B = MOD_EXP (ч, М, р)
C_1 = ОСТАТ(А*В, р)
C_2 = MOD(M+K, p-1)
возврат ((C_1, C_2), К)
защита V(пи, С, М, К):
"""
:param pi: общедоступные параметры
:param C: коммит
:param M: сообщение для проверки
:param K: ключ дефиксации
:return: вернуть 1, если открытие допустимо, и 0 в противном случае
"""
(г, ч) = пи
(С_1, С_2) = С
если не 0 <= K < p-1 или не 0 <= M < p-1:
вернуть 0
А = MOD_EXP (г, К, р)
B = MOD_EXP (ч, М, р)
C_1_prime = MOD(A*B, p)
C_2_prime = MOD(M+K, p-1)
если (C_1 == C_1_prime) и (C_2 == C_2_prime):
вернуть 1
еще:
вернуть 0
"""
1. Укажите, что противник A1 за время O(k^3) делает один запрос к своему LR-оракулу и
достижение Adv^{hide}_CS(A1) = 1.
"""
защита A1(lr, пи):
"""
Это противник, что проблема
просить. Он должен вернуть 0 или 1.
:param lr: Оракул, предоставленный игрой HIDE
:param pi: общедоступный параметр pi
"""
проходят
"""
2. Укажите противника A2 с временем O(k) таким, что Adv^{bind}_CS(A2) = 1.
(Подсказка: каково значение g^{(p-1)/2} по модулю p и почему?)
"""
защита A2 (пи):
"""
Это противник, что проблема
просить. Он должен вернуть кортеж (C, M_0, M_1, K_0, K_1).
:param pi: общедоступный параметр pi
"""
возврат ((0, 0), 0, 0, 0, 0)
если __name__ == '__main__':
# Выборка случайных параметров
к = 12
print('Выборка случайных параметров битовой длины k = %d' % k)
p = случайный.randint(2**(k - 1), 2**k)
пока не is_prime(p) или не is_prime((p-1)//2):
p = случайный.randint(2**(k - 1), 2**k)
г = случайная_Z_N_звезда (р)
в то время как (MOD_EXP(g, (p-1)//2, p) == 1) или (MOD_EXP(g, 2, p) == 1):
г = случайная_Z_N_звезда (р)
ч = случайная_Z_N_звезда (р)
в то время как (h == g) или (MOD_EXP(h, (p-1)//2, p) == 1) или (MOD_EXP(h, 2, p) == 1):
ч = случайная_Z_N_звезда (р)
print('p = %d, g = %d, h = %d' % (p, g, h))
game_hide = GameHIDE(P, C)
sim_hide = HIDESim(game_hide, A1)
game_bind = GameBIND(P, V)
sim_bind = BINDSim(game_bind, A2)
print("Преимущество вашего противника A1 примерно " + str(sim_hide.compute_advantage()))
print("Преимущество вашего противника A2 примерно " + str(sim_bind.compute_advantage()))
Совсем запутался, как начать?
