Регистрация Войти
Рейтинг:15
zabop avatar Crypto

Существует ли протокол асимметричного шифрования, который предоставляет произвольное количество, казалось бы, несвязанных открытых ключей для одного закрытого ключа?

флаг cn
zabop

Я ищу протокол шифрования со следующими свойствами.

  • Алиса имеет закрытый ключ $х$. Используя этот закрытый ключ, она выбирает открытый ключ $р$ соответствующий этому закрытому ключу. Она сообщает Бобу об этом открытом ключе. Затем Боб использует этот открытый ключ для шифрования сообщения Алисе.
  • Позже Алиса снова хочет получить сообщение. Она создает открытый ключ $q$ с использованием тем же закрытый ключ $х$. Затем Боб использует этот открытый ключ для шифрования сообщения для Алисы.
  • Боб не должен быть в состоянии сделать вывод из $р$ & $q$ что два открытых ключа $р$ и $q$ были сгенерированы с использованием одного и того же закрытого ключа $х$.
  • Алисе не нужно иметь более 1 закрытого ключа.
  • Протокол должен позволять Алисе создавать произвольное количество открытых ключей, если им разрешено быть произвольно длинными.

Существует ли такой протокол?

1587
2 + 2
флаг za
hanshenrik
для фактической реализации проверьте биткойн-клиент Electrum, он создает один закрытый ключ, который можно использовать для создания любого количества открытых биткойн-ключей/кошельков/адресов.
1
Ответить
флаг jp
Ajedi32
[BIP32] (https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki) делает это. См. также https://crypto.stackexchange.com/q/22274/21238.
2
Ответить
Рейтинг:15
Yehuda Lindell avatar Crypto
флаг us
Yehuda Lindell

Такая схема может быть создана в общем виде следующим образом. Позволять $(Генеральный,Enc,Декабрь)$ быть схемой шифрования с открытым ключом, и пусть $F$ быть псевдослучайной функцией. Тогда «главный» закрытый ключ схемы является симметричным ключом. $к$ для ПРФ. Чтобы сгенерировать новый открытый ключ, выберите случайный $\ро$ (или если у вас есть состояние, используйте счетчик) и вычислите случайность $r \leftarrow F_k(\rho)$. Затем используйте $г$ (и соответствующий генератор псевдослучайных чисел, если необходимо) для создания новой пары ключей $(pk,sk) \leftarrow Gen(r)$. Чтобы убедиться, что расшифровка возможна, вам нужно знать $г$ или же $\ро$, так что ты можешь сделать $\ро$ часть открытого ключа. В качестве альтернативы, если вы сохраняете состояние, дешифратор может хранить все $\ро$или $г$, а затем просто попробуйте их все (используя метод избыточности и схему безопасности CCA, чтобы узнать, когда вы добьетесь успеха).

0 + 6
DannyNiu avatar
флаг vu
DannyNiu
$\rho$ может быть частью открытого ключа, чтобы можно было быстро идентифицировать соответствующий закрытый ключ.
0
Ответить
Yehuda Lindell avatar
флаг us
Yehuda Lindell
@DannyNiu Действительно, я написал это в ответе.
0
Ответить
Bobson avatar
флаг us
Bobson
Между прочим, эта схема работает и для симметричного шифрования с учетом обычных различий между симметричным и асимметричным шифрованием. A и B должны были бы предварительно поделиться базовым ключом, но любой посередине не смог бы сказать, используют ли какие-либо два сообщения одну и ту же базу.
0
Ответить
флаг sa
K.G.
Для обычных симметричных криптосистем обычно уже трудно отличить шифротексты от случайности, поэтому они уже удовлетворяют этому.
0
Ответить
Nat avatar
флаг de
Nat
Будет ли безопасным совместное использование $r$ в открытом ключе? Кажется, это должно быть $\rho .$
0
Ответить
Yehuda Lindell avatar
флаг us
Yehuda Lindell
Сожалею; ты прав. Это должно быть совместное использование $\rho$, а не $r$. Я исправлю это.
0
Ответить
Рейтинг:5
avatar Crypto
флаг sa
K.G.

Чтобы дополнить общий ответ, вот конкретная конструкция, основанная на Эль-Гамале.

Эль-Гамаль на основе группы $G$ порядка $р$ с генератором $г$ имеет открытый ключ $у = г^а$, куда $а$ является закрытым ключом.

Чтобы создать новый открытый ключ, выберите случайное число $s$ и вычислить $(и,в)$ как $и=г^с$ и $v=y^s$.

Шифровать $м$ с $(и,в)$, выберите случайное число $г$ и вычислить $(х,ш)$ как $ х = и ^ г $ и $w = v^r м$.

Расшифровать $(х,ш)$, вычислить $wx^{-a}$.

Согласно предположению DDH, $(и,в)$ неотличим от случайной пары, так что это хорошо. Легко показать, что схема безопасна при DDH.

Упражнение для читателя. Полезно выяснить, почему эта схема по существу представляет собой всего лишь схему Эль-Гамаля.

Расширения более полезных пространств сообщений тривиальны с использованием стандартных методов.

Эта схема (с некоторыми дополнительными приемами) использовалась для создания теоретически лучшего вредоносного ПО. (Насколько мне известно, он никогда не использовался для создания настоящих вредоносных программ.)

0 + 0
флаг Moldova
Admin
Этот вопрос на других языках:

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

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