Алиса и Боб

[Mikle1990]

Я тут всего начитался и мне показалось, что я понял суть. Но оказывается, что не до конца.

Алгоритм с открытым ключом.
Алиса имеет пару (алгоритм1+открытый ключ) и (алгоритм2+закрытый ключ)
т.е. 2 алгоритма и 2 ключа.
Она объявляет всем свой (алгоритм1+открытый ключ), и держит в тайне (алгоритм2+закрытый ключ).

Боб хочет переслать Алисе сообщение. Он берёт (алгоритм1+открытый ключ) и зашифровывает сообщение M - получает C.
Далее он берёт это C и отправляет Алисе.
C поступает Алисе и она, используя (алгоритм2+закрытый ключ), получает M.

Я всё никак не могу понять, какая связь между алгоритм1 и алгоритм2? Почему это не одно и тоже?

Т.е. связь такова, что текст зашифрованный (алгоритмом1+открытый ключ), можно расшифровать только (алгоритмом2+закрытый ключ)?
Алиса держит в тайне не только ключ, но и алгоритм дешифрации?
Т.е. когда говорят про закрытый ключ, то имеют ввиду не только ключ, но и алгоритм дешифрации?

[Xaositect]

Нет, алгоритм дешифровки открыт, секретным должен быть только ключ (прагматика этого такова: если противник узнал ключ, то его можно поменять, замена же алгоритма вообще говоря может быть сопряжена со значительными трудностями, например, алгоритм может быть реализован "в железе").

Формально, асимметричная система состоит из (вообще говоря, вероятностного) алгоритма шифрования $E$, алгоритма дешифрования $D$ и вероятностного алгоритма генерации ключей $G$. Все алгоритмы всем известны.

В начале Алиса создает случайную пару ключей $k_{\textrm{private}}, k_{\textrm{public}} \leftarrow G$ и публикует публичный ключ.
Для шифрования сообщения $m$ Боб использует алгоритм шифрования: $c \leftarrow E(m, k_{\textrm{private}})$. Для дешифрования Алиса использует алгоритм дешифрования со своим приватным ключом: $m = D(c, k_{\textrm{public}})$.

Требование корректности: $D(E(m, k_{\textrm{private}}), k_{\textrm{public}})=m$, криптографическое требование - по обозримому набору пар $(m, c)$ должно быть сложно взломать некий не встречающийся в этом наборе шифртекст $c'$.

[Mikle1990]

Получается, что у Алисы есть 2 алгоритма:
1) Шифрования (Она им не пользуется. Пользуются только те, кто отправляет ей сообщения)
2) Дешифрации (Она, и только она, им пользуется).

Также Алиса имеет 2 ключа:
1) Открытый (Она им не пользуется. Пользуются только те, кто отправляет ей сообщения) - применяется в шифровании.
2) Закрытый (Она, и только она, им пользуется) - применяется в дешифрации.

Боб хочет отправить сообщение Алисе. У него 2 варианта:
1. Использовать открытый ключ Алисы и её алгоритм шифрования.
Алиса для расшифровки будет использовать свой алгоритм Дешифрации вместе с закрытым ключём.
2. Использовать закрытый ключ Алисы и её алгоритм шифрования.
Алиса для расшифровки будет использовать свой алгоритм Дешифрации вместе с открытым ключём.

Что касательно Боба, то у него есть свои алгоритмы и свои ключи отличные от тех, что есть у Алисы.

Цитата:

Все алгоритмы всем известны.

Если так, то почему в учебнике написано: "...По аналогии(секретный) алгоритм дешифрации, параметризованный персональным ключом Алисы, мы будем обозначать $D_{A}$."?
Получается что либо Вы не правы, либо в учебники имеется ввиду тот случай, когда алгоритм становится секретным в силу того, что автор подписал к нему "параметризованный персональным ключом".

И у меня ещё вопрос назрел. По идеи, ведь у Боба и Алисы могут быть одинаковые алгоритмы и ключи? Т.е. для того, чтобы передавать друг другу сообщения, они будут использовать один и тот же: открытый ключ, закрытый ключ, алгоритм шифровки и алгоритм дешифрации. Да?

[arseniiv]

Mikle1990 в сообщении #630884 писал(а):

Боб хочет отправить сообщение Алисе. У него 2 варианта:
1. Использовать открытый ключ Алисы и её алгоритм шифрования.
Алиса для расшифровки будет использовать свой алгоритм Дешифрации вместе с закрытым ключём.
2. Использовать закрытый ключ Алисы и её алгоритм шифрования.
Алиса для расшифровки будет использовать свой алгоритм Дешифрации вместе с открытым ключём.

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

Xaositect, у вас в формулах перепутались $k_{\textrm{private}}$ и $k_{\textrm{public}}$.

[Maslov]

Mikle1990 в сообщении #630884 писал(а):

Если так, то почему в учебнике написано: "...По аналогии(секретный) алгоритм дешифрации, параметризованный персональным ключом Алисы, мы будем обозначать $D_{A}$."?
Получается что либо Вы не правы, либо в учебники имеется ввиду тот случай, когда алгоритм становится секретным в силу того, что автор подписал к нему "параметризованный персональным ключом".

Там имеется в виду, что алгоритмы шифрования $E$ и дешифрации $D$ общеизвестны, но для их применения на вход необходимо подать два параметра: ключ $K$ и текст $P$. Другими словами, алгоритм дешифрации RSA является функцией двух аргументов: ключа и зашифрованного текста. Если "частично применить" его к секретному ключу, то получится функция одного аргумента (текста), но эта функция уже будет секретной.
В том же учебнике ранее написано:

Э.Таненбаум в книге "Компьютерные сети писал(а):

Такая нотация предполагает, что $E$ и $D$ являются просто математическими функциями. Они в действительности таковыми и являются. Единственная хитрость состоит в том, что обе эти функции имеют по два параметра, один из которых (ключ) мы написали не в виде аргумента, а в виде нижнего индекса, чтобы отличать его от сообщения.

Mikle1990 в сообщении #630884 писал(а):

По идеи, ведь у Боба и Алисы могут быть одинаковые алгоритмы и ключи? Т.е. для того, чтобы передавать друг другу сообщения, они будут использовать один и тот же: открытый ключ, закрытый ключ, алгоритм шифровки и алгоритм дешифрации. Да?

А смысл? Если они могут заранее обменяться ключами, то проще использовать какой-нибудь симметричный алгоритм с закрытым ключом. Идея RSA состоит в том, что кто угодно, используя только общедоступную информацию, может зашифровать сообщение для Боба, причем расшифровать его сможет только Боб. И в обратную сторону: Боб может подписать свое сообщение таким образом, что кто-угодно, используя только общедоступную информацию, может убедиться, что именно Боб является его автором.

[Mikle1990]

Получается, что у Алисы есть
$E_{A}$, которая состоит из открытого ключа $+$ ф-ция1.
$D_{A}$, которая состоит из закрытого ключа $+$ ф-ция2.
Всё, что я выделил зелёным цветом, известно всем участникам?

[Maslov]

Для того чтобы отправить Бобу сообщение, расшифровать которое сможет только он, Алисе нужно иметь:
1. Общеизвестную функцию (программу) шифрования $E$, принимающую на входе ключ и открытый текст и выдающую на выходе зашифрованный текст.
2. Общеизвестный открытый ключ Боба

Для того чтобы прочитать (расшифровать) сообщение Алисы, Боб должен иметь
1. Общеизвестную функцию (программу) дешифрации $D$, принимающую на входе ключ и зашифрованный текст и выдающую на выходе расшифрованный текст.
2. Собственный закрытый ключ.

Для того чтобы приложить к сообщению, отправляемому Бобу, свою цифровую подпись (позволяющую Бобу убедиться, что именно Алиса является автором сообщения), Алиса должна иметь:
1. Общеизвестную функцию (программу) шифрования $E$.
2. Общеизвестную функцию (программу) $H$, вычисляющую дайджест сообщения.
3. Собственный закрытый ключ.

Для того чтобы проверить, что автором полученного сообщения является именно Алиса, Боб должен иметь:
1. Общеизвестную функцию (программу) дешифрации $D$.
2. Общеизвестную функцию (программу) $H$, вычисляющую дайджест сообщения.
3. Открытый ключ Алисы.

Все компоненты RSA, кроме закрытого ключа Боба и закрытого ключа Алисы, являются общеизвестными.

[Mikle1990]

Maslov, спасибо.
Остальным тоже спасибо