Рейтинг:0

Расшифровка зашифрованного текста в криптосистеме Эль-Гамаля

флаг fr

Я изучаю компьютерные науки, в настоящее время работаю над проблемой в криптографии (практическая задача, но застрял в математической части).

По сути, предположим, что мы получили сообщение, зашифрованное с помощью криптосистемы Эль-Гамаля, и наша цель — расшифровать и полностью восстановить сообщение.

Исходный открытый текст представляет собой последовательность $p_1p_2\ldots p_m$. Нам дают хешированную версию открытого ключа SHA256.$(г^с)$ (так $s$ является закрытым ключом и $g^s$ общественный). Для шифрования сказано, что $r_1$ значение выбирается равномерно случайным образом, а затем для некоторого заданного значения $u\in\mathbb{Z}_q$, $r_i=u^{i-1}r_1$ для всех оставшихся $я$с. Затем зашифрованный текст $c_i=(g^{r_i},p_ig^{r_is})_{i\in[m]}$.

В целом нам дается $р$, $q$, $г$, $u$, хешированный открытый ключ $Ч$ и зашифрованный текст $c_i$ как кортеж.

У меня проблема в том, что я действительно не понимаю, какие вычисления мы должны сделать, чтобы восстановить всю исходную последовательность. Один из помощников сказал мне найти $p_i$, а затем использовать их для расшифровки шифра, но я не понимаю, к чему это меня приведет. $г$неизвестны, и даже если мы знаем $ г ^ {r_i} $, так как нам даны довольно большие значения, мы не можем вычислить лог.

Честно говоря, я немного потерялся (у меня нет огромного опыта в алгебре), поэтому, если у кого-то есть совет о том, что мне делать, я был бы очень признателен.

Спасибо :)

yacovm avatar
флаг us
Но разве закрытый ключ не $s$? Нельзя ли поднять $g^{r_i}$ до $s$, как в обычной схеме?
seboll13 avatar
флаг fr
@yacovm yes $s$ — закрытый ключ, но мы его не знаем, поэтому не можем с ним выполнять какие-то вычисления. Думаю, лучшим решением было бы найти способ узнать $r_1$, но я не знаю, как это сделать.
kelalaka avatar
флаг in
Не могли бы вы сначала прочитать https://en.wikipedia.org/wiki/ElGamal_encryption, а затем рассказать нам, где вы потерпели неудачу?
yacovm avatar
флаг us
Так вы пытаетесь расшифровать, не зная закрытого ключа? Это задание?
seboll13 avatar
флаг fr
Кажется, я начинаю думать, что в постановке задачи упущены некоторые важные элементы (хотя это не так). Действительно @yacovm у нас нет доступа к закрытому ключу $s$. У нас есть доступ только к хешу $g^s$. ТА сказал нам угадать несколько $p_i$, но я не совсем понимаю, как это сделать.
seboll13 avatar
флаг fr
@kelalaka Я предполагаю, что в нашем сценарии мы должны действовать немного иначе, чем реальный процесс дешифрования, отчасти поэтому я запутался: p
fgrieu avatar
флаг ng
Каков размер $p$, в битах или десятичных цифрах? Если это достаточно мало, могут быть атаки. Кроме того, является ли $(p-1)/2$ простым или составным с нетривиальными множителями?
seboll13 avatar
флаг fr
@fgrieu $p$ — это степень двойки, если быть точным, это $2^{1024}$, то есть 309 цифр. Если я не ошибаюсь, $(p-1)/2$ не простое число. Я думаю, что я близок к чему-то, но вычисления по модулю всегда довольно сложны.
fgrieu avatar
флаг ng
Если $p$ — большая степень двойки, то оно не простое, а $(p-1)/2$ не может быть простым. Вы уверены в этом?
fgrieu avatar
флаг ng
Не обращая внимания на то, что вы сказали о $p$: я думаю, что суть проблемы в том, что $r_i$ не случайны, как должны. Просто чтобы убедиться, что мы правильно поняли уравнения: вы должны быть в состоянии проверить, что $g^{r_i}=(g^{r_1})^{(u^{i-1})}\bmod p$ (обратите внимание, что $g^{r_i}$ — первая часть зашифрованных текстов). Теперь сделайте что-то подобное со второй частью зашифрованных текстов, и вы сможете получить все $p_i/p_1\bmod p$. А потом..
seboll13 avatar
флаг fr
@fgrieu Я уверен, что p не простое число (это тривиально), и почти уверен, что (p-1)/2 простое. Я буду изучать то, что вы говорите. Но для уточнения: $r_1$ является случайным, $u$ также (равномерно случайным в $\mathbb{Z}_q$, а все остальные $r_i$âs генерируются на основе $r_1$ и предшествующего $u $ Так что трюк, который я считаю, заключается в том, чтобы каким-то образом найти $r_i$ и пойти дальше оттуда.
Рейтинг:0
флаг tr

Вы должны попытаться найти $r_{1}$. Для этого попытайтесь увидеть, есть ли связь между $с_{я}$ и $c_{j}$, в основном между $g^{r_{i}}$ и $g^{r_{j}}$. Может быть, вы можете найти $с$ такой, что $g^{c}=g^{r_{i}}/g^{r_{j}}$. Затем вы можете вычислить $г^{с}$

seboll13 avatar
флаг fr
Спасибо за ваш ответ :) да, это была моя главная цель, на самом деле здесь достаточно найти один $r_i$, потому что оттуда мы можем легко найти $r_1$ и все остальное. Но вычисления по модулю довольно сложны, поэтому я делаю все возможное, чтобы поработать над этим и найти решение.

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

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