Изменения

Можно сделать вывод, что должно выполняться 2 требования: <tex>K_{B}^{-}</tex> и <tex>K_{B}^{+}</tex> такие, что <tex>K_{B}^{-}(K_{B}^{+}(m)) = m</tex>, и, зная публичный ключ, человек не должен иметь возможности посчитать приватный. Одним из самых известных алгоритмов является RSA (Rivest-Shamir-Adleman). Это криптографический алгоритм с открытым ключом, который основывается на вычислительной сложности задачи факторизации больших целых чисел. В криптографической системе RSA каждый ключ состоит из пары целых чисел. Каждый участник создает свой открытый и закрытый ключ самостоятельно, при этом эти ключи являются согласованной парой в том смысле, что они являются взаимно обратными, то есть: <tex>\forall</tex> допустимых пар открытого и закрытого ключей <tex>(p, s)</tex> <tex>\exists</tex> соответствующие функции шифрования <tex>E_{p}(x)</tex> и расшифрования <tex>D_{s}(x)</tex> такие, что <tex>\forall</tex> сообщений <tex>m \in M</tex>, где <tex>M</tex> - множество допустимых сообщений, <tex>m = D_{s}(E_{p}(m)) = E_{p}(D_{s}(m))</tex>. RSA-ключи генерируются следующим образом:# Выбираются два различных простых числа <tex>p</tex> и <tex>q</tex> заданного размера (например, 1024 бита каждое).# Вычисляется их произведение <tex>n = p \dot q</tex>, которое называется модулем.# Вычисляется значение функции Эйлера от числа <tex>n</tex>: <tex>\phi (n) = (p - 1) \dot (q - 1)</tex>.# Выбирается целое число <tex>e</tex> <tex>(1 < e < \phi (n))</tex>, взаимно простое со значением функции <tex>\phi (n)</tex>. Обычно в качестве <tex>e</tex> берут простые числа, содержащие небольшое количество единичных бит в двоичной записи, например, простые числа Ферма <tex>17</tex>, <tex>257</tex> или <tex>65537</tex>. Число <tex>e</tex> называется открытой экспонентой.# Выбирается число <tex>d</tex>, мультипликативно обратное к числу <tex>e</tex> по модулю <tex>\phi (n)</tex>, то есть число, удовлетворяющее сравнению: <tex>d \dot e \equiv 1 (mod \phi (n))</tex>. Число <tex>d</tex> называется секретной экспонентой.# Пара <tex>\{e, n\}</tex> публикуется в качестве открытого ключа RSA.# Пара <tex>\{d, n\}</tex> играет роль закрытого ключа RSA и держится в секрете. Теперь, чтобы зашифровать сообщение <tex>m</tex>, нужно посчитать <tex>c = m^{e} mod n</tex>, а чтобы расшифровать - <tex>m = c^{d} mod n</tex>. Однако такая схема не используется на практике по причине того, что она не является практически надежной, так как односторонняя функция является детерминированной. Чтобы избежать такого, используют сеансовый ключ. С помощью RSA шифрования собеседники обмениваются симметричными ключами сессии, и дальше уже общаются с их помощью.