Что я не понимаю в RSA?

Question

[AlexGenesis]

Здравствуйте, сразу скажу что вопросы довольно хламовые, но я не могу найти на них ответа, так что буду благодарен за помощь.

1. У каждого клиента существует 2 ключа - публичный и приватный?
2. Приватный ключ создаётся на основе публичного ключа твоего или собеседника?
3. В чем проблема для злоумышлиника подделать приватный ключ по известному алгоритму на основе публичного ключа?

Answer 1

[galaxy]

1. У каждого клиента существует 2 ключа - публичный и приватный?

да

2. Приватный ключ создаётся на основе публичного ключа твоего или собеседника?

нет, они генерируются парой

3. В чем проблема для злоумышлиника подделать приватный ключ по известному алгоритму на основе публичного ключа?

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

Comments

[AlexGenesis]

Хорошо, можно тогда уточнить общую картину:
1) Сначала берется 2 простых, разных числа (p, q)
2) Находится произведение n = p * q
3) Находится функция Эйлера pi(n) = (p-1) * (q-1)
4) Затем выбирается открытая экспонента 1 < e < pi(n)
5) Создается публичный ключ {e, n}
? Этапы с 1) - 5) происходят отдельно у каждого клиента или какие-то переменные(p или n например) передаются между клиентами уже на этапе создания публичного ключа
6) Дальше находится закрытая экспонента, которая удовлетворяет следующему тождеству:
d * e = 1 (mod pi(n))
? Правильно ли я понимаю что это равенство гарантирует возможность расшифровки сообщение, так как d теперь определенным образом связана с e
? В этом тождестве что стоит под e, чья это открытая экспонента, или что Вы имели ввиду под "парой"

[galaxy]

AlexGenesis,

Этапы с 1) - 5) происходят отдельно у каждого клиента или какие-то переменные(p или n например) передаются между клиентами уже на этапе создания публичного ключа

отдельно

Правильно ли я понимаю что это равенство гарантирует возможность расшифровки сообщение, так как d теперь определенным образом связана с e

да

В этом тождестве что стоит под e, чья это открытая экспонента, или что Вы имели ввиду под "парой"

того же, что и закрытая

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

[AlexGenesis]

galaxy, А эта "связь" между открытым ключом и закрытым она уникальна для каждого пользователя? Если нет, то в чем тогда проблема третьим лицам имея этот алгоритм и открытый ключ на руках создать закрытый ключ точно таким же образом как это и сделал владелец ключей

[galaxy]

AlexGenesis, уникальна для каждого e и n (экспонента и модуль), в том смысле, что существует единственное d, меньшее n и обратное e по модулю phi(n). Математически принцип, конечно, один и тот же
Проблема - зная n, найти phi(n)

[AlexGenesis]

И что бы уже окончательно забить гвозди, то есть уникальность создания закрытого ключа заключается в уникальности параметров e и n(p, q) для каждого отдельного пользователя? И сложность подделки закрытого ключа заключается в том что третья сторона не знает значение функции Эйлера от n(Ибо это очень сложный и трудоёмкий процесс факторизации), а владелец ключа в свой очередь, так как знает задающию пару (p, q), может с лёгкостью найти значение функции ибо оно будет равнятся (p-1)*(q-1)

[galaxy]

AlexGenesis, да