Проблема вычисления дискретного логарифма с использованием кода Python

У меня есть набор логарифмов L1, L2 и L3, который я получил из статьи "Ультра-безопасная система спонтанного обмена ключами между маршрутизаторами" (2015), здесь. Цель этой статьи - надежно разделить ключ между Алисой и Бобом. Например, Алиса отправила K = 46 Бобу. Боб получил ключ от Алисы. Ключ может быть представлен как:

Ключ должен быть разделен с использованием трехэтапного процесса. L1: Алиса Бобу. L2: Боб Алисе. L3: Алиса Бобу. Уравнения:

Боб может оценить ключ, используя:

Это результат для уравнений:

Учитывая значение alpha = 5, x = 15 и p = 97. После того, как я реализовал это в Python, я получил неправильный результат, который не совпадает с результатом в таблице:

a=5
x=15
p=97
i1=0.958478
i2=4.238835

L1=a**(x+i1)%p
L2=a**(x+i1+i2)%p
L3=a**(x+i2)%p
K=L3*(a**(-i2))

print ("L1",L1)
print ("L2",L2)
print ("L3",L3)
print ("K",K)

Которые дают этот результат:

L1 55.596893310546875
L2 2.15625
L3 68.87890625
K 0.07503566293789979

Другая проблема заключается в том, что я пытался вычислить его вручную, но результат все еще не совпадает с результатом в таблице. Я надеюсь, что кто-нибудь может мне помочь. Спасибо.

Ответ 1

Конечно, при вычислении L2 Боб не будет иметь доступа к Алисе i1, и Алиса не сможет использовать i2 для вычисления L3. Однако для воспроизведения этих результатов это не имеет большого значения.

Насколько я могу судить, трудности, с которыми вы сталкиваетесь, не являются вашими собственными силами. Похоже, проблема в том, что конкретный алгоритм невероятно чувствителен к входным данным i1 и i2, и авторы решили предоставлять их только с ограниченной точностью. Я проиллюстрирую, используя ваш пример кода, изменяя только i1 и i2 вокруг значений, которые вы предоставили, так что они все еще округляются до заданных значений (первая строка в таблице 1 статьи),

       i1         i2           L1         L2           L3           K
0.9584775  4.2388345  50.82189941  44.171875  14.53515625  0.01583440
0.9584776  4.2388346  32.36941528  66.515625  62.78515625  0.06839727
0.9584777  4.2388347  13.92065430   6.187500  14.59765625  0.01590248
0.9584778  4.2388348  92.47598267  55.687500  64.30078125  0.07004834
0.9584779  4.2388349  74.03457642  21.765625  17.72656250  0.01931106
0.9584780  4.2388350  55.59689331   2.156250  68.87890625  0.07503566  # your result
0.9584781  4.2388351  37.16333008  92.375000  23.59765625  0.02570693
0.9584782  4.2388352  18.73303223   2.171875  76.20312500  0.08301453
0.9584783  4.2388353   0.30642700  23.296875  32.37109375  0.03526457
0.9584784  4.2388354  78.88394165  57.234375  86.42578125  0.09415091

Вывод кажется ясным: данные, приведенные в статье, кажутся недостаточными для воспроизведения результатов. Я предлагаю вам связаться с авторами и попытаться получить их код, данные и любые другие материалы, которые они могут иметь в отношении этой публикации.

Ответ 2

Указанный вами документ немного размыт. Пример, приведенный ниже, охватывает нефиксированные точки.

Вы не разделяете gm,pm если хотите (как статическое определение или таблица).

Работа, которую вы делаете, важнее алгоритма. Не перепутайте basic и improved условия.

am=5 #Secret key of A node
bm=9 #Secret key of B node
gm=15 #Shared Base Number
pm=97 #Shared Modulos

A = (gm^am)%p #Shared key from A
B = (gm^bm)%p #Shared key from B

Ka = (A^bm) %p #Calculate Key wit A node Answer
Kb = (B^am)%p  #Calculate Key wit B node Answer

print "Shared Key A:",A,"Shared Key B:",B
print "Node A key :",Ka,"Node B key :",Kb

NUMSA = [[i,(am**i)%p] for i in range(p) if i > 0]
NUMSB = [[i,(bm**i)%p] for i in range(p) if i > 0]


print NUMSA #ALL Numbers and means for A node
print NUMSB #ALL Numbers and means for B node

Что поэт хотел сказать здесь? Мне не нравится такая интерпретация.

Что ты понимаешь?

Я надеюсь, что это помогает.

Ответ 3

Не зная слишком много о криптовалютах, я бы предположил, что таблица в статье показывает округленные значения, т.е. не воспроизводится простым копированием значений, которые там записаны.
В качестве теста вы можете легко оставить первые 6 цифр i1 и i2 такими, как они есть в вашем примере скрипта, но добавьте несколько случайных цифр - и вы увидите, что с каждым новым Variation ваши значения Lx будут переключаться между от того, что таблица показывает, до очень близко.

Пример:

import numpy as np

a=5
x=15
p=97
i1=0.958478
i2=4.238835

np.random.seed(1234)

for _ in range(3):
    i1 += np.random.random()/1e7
    i2 += np.random.random()/1e7

    print(i1)
    print(i2)

    L1=a**(x+i1)%p
    L2=a**(x+i1+i2)%p
    L3=a**(x+i2)%p
    K=L3*(a**(-i2))

    print ("L1",L1)
    print ("L2",L2)
    print ("L3",L3)

    print()


# 0.9584780191519451
# 4.238835062210877
# L1 89.90701293945312
# L2 6.828125
# L3 63.7265625

# 0.9584780629247189
# 4.238835140746736
# L1 56.760833740234375
# L2 91.6875
# L3 53.03515625

# 0.9584781409222998
# 4.238835168005997
# L1 28.248016357421875
# L2 73.265625
# L3 77.52734375

Ответ 4

хорошо, я нашел ошибку:

(a^(x+i2) % p) * a^(-i2) != a^(x+i2 -i2) % p по модулю
Кроме того, вам не нужно 4 способа обмена, если a, x и p известны и если они неизвестны, они не могут отправлять сообщения.

Ответ 5

Я получил тот же ответ, что и вы, после того, как попробовал в Python, Java и сделал это с помощью калькулятора и бумаги (дольше, чем мне хотелось бы признать). Я написал одному из авторов статьи по электронной почте в надежде получить от них ответ. Если они ответят, я отредактирую этот ответ, чтобы включить их ответ! Пожалуйста, обновите свой оригинальный пост, если вы сами разберетесь, мне интересно, что я делаю неправильно.

Ответ 6

Мой знакомый друг по математике помог мне понять, что пошло не так. Ответы, которые вы получили, верны. Проблема со значениями, которые авторы дали для i1 и i2.

Одно дополнительное десятичное число полностью меняет результат операции mod p в этой части:

L1 = a ** (x + i1)% p В случае, если i1 равно 0,958478, на выходе получается: 55,596893310546875

Теперь, если вы добавите хотя бы один дополнительный 1 к концу значения для i1, что приведет к i1 0,9584781, выходное значение этого же уравнения станет совершенно другим числом: 37.163330078125

Если вы сравните алгоритм, чтобы определить, что K = L3 * a ** (-i2), используя заданный i2 из 4.238835, вы также быстро обнаружите, что результат не равен 46. Начальное значение K, рассчитанное с алгоритмом (a ** x)% p, равным 46, так что то, что вышеупомянутый алгоритм должен был оценить. Вместо этого результат этого уравнения с заданными значениями равен 0,05102662974.

Мой друг выдвинул теорию, основанную на том факте, что авторы сказали, что они используют Matlab. Matlab имеет функцию, которая позволяет пользователю ограничивать отображаемые десятичные разряды. Десятичные числа по-прежнему ведут себя в соответствии с их фактическим значением, но их представление на экране усекается до указанного десятичного знака. Для большинства операций это вполне нормально и окажет незначительное влияние на результаты расчетов. Тем не менее, при выполнении операции модуля, один 1, даже в младшем значащем десятичном знаке числа, может изменить все число.

Таким образом, мы предполагаем, что фактические значения i1 и i2 были усечены их настройками отображения в Matlab. Это не изменит правильности алгоритма, а также не помешает ему оценить правильное значение переменной K в конце операции. Все результаты использования полных десятичных значений i1 и i2 будут отображаться. Однако это также сделало бы невозможным воспроизведение всего процесса для кого-либо, используя те же цифры, которые Matlab показал нашим авторам во время расчета.