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

Question

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

Это мой образ мышления:

Hello зашифрован открытым ключом, становится %/))=. Затем закрытый ключ расшифровывает сообщение. Но поскольку ключи разные, результирующее сообщение может отличаться от того, что было отправлено - &#(($, Например.

Конечно, я знаю, что алгоритм шифрования / дешифрования, используемый в реальной жизни, отличается, но вопрос понятен. Как ключи сделаны так, что один может только зашифровать, а другой - только расшифровать, при этом оба имеют достаточно информации, чтобы они были совместимы друг с другом? Это алгоритм, который этим занимается?

Answer 1

Криптография с открытым ключом была впервые описана У. Диффи и М. Хеллманом в их новаторской статье « Новые направления в криптографии » (1976), в которой они предположили, что такая система будет основана на функции лазейки . Такую гипотетическую функцию было бы легко вычислить, но эффективное вычисление обратного ей потребовало бы дополнительной информации, которая могла бы быть закрытым ключом. (Статья довольно короткая, и ее стоит прочитать целиком, редко 11-страничная статья вносит такой вклад в эту область.)

Как упоминалось в другом ответе, один пример такой функции может быть основан на проблеме целочисленной факторизации: легко умножить два простых числа, но нет эффективного (классического) алгоритма для поиска факторизации продукта. Позже Ривест, Шамир и Адлеман изобрели первый алгоритм с открытым ключом, основанный на этом простом факте.

Короче можно взять пару (N, e) быть открытым ключом, где - произведение двух очень больших простых чисел и, и e обычно представляет собой небольшую простую константу, например 65537. Тогда вы можете найти такое, что:

      cipher = plaintext ^ e mod N
plaintext = cipher ^ d mod N

Это закрытый ключ. Хитрость в том, что для того, чтобы найти такие d, вам нужно знать факторизацию N, т.е. p и q, что очень сложно решить. Вы можете прочитать более подробную информацию по ссылке RSA выше.

Answer 2

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

Давайте использовать модуль, n = 143 с открытым ключом, e = 7, и закрытым ключом, d = 43. В том, как определяются эти числа, есть некоторая «магия», и для обеспечения реальной безопасности их должно быть много , намного больше. Проблема здесь в том, что 143 является частью открытого ключа, и он достаточно мал, чтобы легко разложить на простые числа 11 и 13, которые являются волшебными ингредиентами, ведущими к закрытому ключу.

Мы можем зашифровать числа [0, n) с помощью этой пары ключей, поэтому мы заменим цифры 0–25 на буквы A–Z.

Шифрование RSA: c = m ^e mod n, где m - это «сообщение», наша закодированная буква, а c - зашифрованный текст для этой буквы. Зашифруем «HELO» по буквам.

• H -> 7: 7⁷ мод 143 = 6
• E -> 4: 4⁷ мод 143 = 82
• L -> 11:11 ⁷ мод 143 = 132
• O -> 14:14 ⁷ мод 143 = 53

Расшифровка RSA: m = c^d mod n

• 6 ⁴³ мод 143 = 7 -> H
• 82 ⁴³ мод 143 = 4 -> E
• 132 ⁴³ мод 143 = 11 -> L
• 53 ⁴³ мод 143 = 14 -> O

Итак, вы можете видеть, что открытый ключ 7 отличается от закрытого ключа 43, но они работают вместе с модулем 143 при модульном возведении в степень, чтобы обеспечить обратимое преобразование.

Вот «волшебство», которое использовалось для создания пары ключей, которые работают вместе.

1. Выберите два простых числа: p = 11, q = 13
2. Вычислить модуль: n = pxq = 143
3. Вычислите totient: λ(n) = lcm(p - 1, q - 1) = lcm(10, 12) = 60
4. Выберите открытый ключ e, который взаимно прост с λ(n): e = 7
5. Определить закрытый ключ d: d = e^-1 mod λ(n) = 43

Answer 3

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

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

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

Например, если я скажу 91, не сразу очевидно, что он состоит из 7 и 13, и если вы попытаетесь разделить 91 на что-нибудь еще, вы не получите целочисленного ответа.

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

Том Скотт довольно хорошо объясняет это в этом видео: https://www.youtube.com/watch?v=CINVwWHlzTY