Регистрация Войти
Рейтинг:2
Andrei Florian avatar Crypto

Докажите, что два перешифрования одной и той же пары Эль-Гамаля имеют одинаковые расшифровки.

флаг br
Andrei Florian

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

Освобождая единственное значение $(r'-r'')\mod(p-1)$, две пары Эль-Гамаля $(х',у')$ и $(х'',у'')$ можно показать, что они имеют те же расшифровки без какой-либо связи или ассоциации с исходной парой Эль-Гамаля. $(х,у)$.

Мне удалось получить значение $(r'-r'')\mod(p-1)$ изложено выше, но я не уверен, как использовать это значение, чтобы доказать, что оба повторных шифрования имеют одинаковое расшифрование.

Спасибо за время,

Андрей.

115
0 + 0
Рейтинг:2
Daniel S avatar Crypto
флаг ru
Daniel S

Записывая в аддитивной записи, предположим, что у нас есть генератор $G$ и открытый ключ $А$. Наши две пары $(x',y')=(M+r'A,r'G)$ и $(x'â, y'')=(M+r'âA, r'ÂG)$. Данный $râ-rââ$, мы можем это проверить $yâ-yââ=(râ-rââ)G$ и $xâ-xââ=(râ-rââ)A$

В мультипликативной записи имеем $ (x , y ) = (MA ^ {r }, G ^ {r }) $ д., мы проверяем, что $yâ/yââ=G^{râ-rââ}$ и $ х / х = А ^ {r -r â } $.

Если бы сообщения были другими, но с тем же эфемерным $г$ значений первая проверка прошла бы, а вторая нет.

0 + 0
Andrei Florian avatar
флаг br
Andrei Florian
Привет, спасибо за ответ и извините за задержку с моей стороны. Я просмотрел предоставленные формулы, и они, кажется, работают, учитывая (x²,yâ²)=(M+râ²A,râ²G). Однако в моем случае (x²,yâ²)=(MA^r', G^r'). Не знаете ли вы, как скорректировать доказательство, чтобы оно соответствовало этому?
0
Ответить
Daniel S avatar
флаг ru
Daniel S
Да, это мультипликативная запись, как во втором абзаце. Я отредактировал, чтобы сделать это более ясным.
1
Ответить
Andrei Florian avatar
флаг br
Andrei Florian
Спасибо за это, извините за беспокойство, я попытался реализовать это с помощью кода (javascript, используя библиотеку jsbn для математических вычислений с большими целыми числами), но я просто не могу заставить его работать. Я пытаюсь решить левую и правую части уравнения, а затем приравнять их, как показано ниже: `const слева = y1.divide(y2);` `const right = g.pow(доказательство);` `console.log(слева.равно(справа));` y1 есть y', y2 есть y'', и доказательство (r'-r''). Всякий раз, когда я возвожу g в степень (r'-r''), я получаю 1, а когда я делю y' на y'', я получаю, что 0 равно y1у2. Вы бы знали, что я делаю неправильно?
0
Ответить
Daniel S avatar
флаг ru
Daniel S
Похоже, вы занимаетесь наивной арифметикой, а не арифметикой по модулю $p$. У вас должно быть `left=(y1*modInverse(y2,p))%p` для подходящей функции modInverse (я не знаю, что встроено в javascript) и `right=modPower(g,proof,p)` для подходящая функция modPower.
1
Ответить
Andrei Florian avatar
флаг br
Andrei Florian
Это было проблемой! Спасибо. Однако я столкнулся с одной проблемой. Я генерирую (r' - r'') как r' - r'' % p. Доказательство работает при условии r'>r'', но не работает иначе, пока я не заменю left=(y1*modInverse(y2, p))%p на left=(y2*modInverse(y1, p))%p. Есть ли способ решить это математически, чтобы я мог заставить r'-r'' работать независимо от неравенства?
0
Ответить
Daniel S avatar
флаг ru
Daniel S
Да. Вместо этого используйте `(r'-r'')%(p-1)`
1
Ответить
Andrei Florian avatar
флаг br
Andrei Florian
Да это оно. Большое спасибо за помощь.
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

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