► Показать
Шифрование с закрытым кодом это использование отдельных ключей. Скажем вы хотите передать другу число 6371. Берёте случайный набор цифр, например 7259 (он называется ключом), поразрядно прибавляете его к отправляемому сообщению - получаете 3520 (каждая цифра складывается отдельно без добавления единиц справа налево), отправляете другу 3520, тот вычитает из него 7259 и получает ваше сообщение. Ещё раз на всякий случай: когда к отправляемому тексту прибавляется ключ, текст превращается в абракадабру, эту абракадабру вы пересылаете знакомому, тот вычитает ключ из абракадабры и получает исходное сообщение. Всё просто, но если с каждым новым знакомым использовать этот способ шифрования, то вы замучаетесь каждый раз на флешках передавать знакомому ваш ключ.
А вот шифрование с открытым ключом более интересно. Представьте себе, что два человека разговаривают по радио, и кто-то третий их слушает. Эти два говорят на языке который подслушивающий знает, они не договаривались заранее о каком-то шифре, они видят друг друга первый раз. Тем не менее, они сообщают друг другу информацию, который этот подслушивающий узнать не может. Вы можете такое представить? Дальше станет понятно, как это работает.
Шифрование с открытым кодом, которое называется RSA, основано на математическом принципе, что перемножить два числа для компьютера намного проще, чем разложить число на простые множители. В описанном примере, этот подслушивающий в принципе может узнать то что передают другу другу эти собеседники, но для этого ему понадобится компьютер, который проработает миллион лет.
Напишу конкретно как работает RSA-шифрование. Алиса должна передать Бобу целое число, а Ева их подслушивает. Пять примеров:
Боб хочет послать Алисе число 2 (m). Алиса выбирает два случайных простых числа: 2(p) и 3(q). Перемножает их и получает 6 (n). Выбирает случайное число 3(e), оно не совсем любым может быть, Алисе надо кое что посчитать (зная p и q), чтобы его подобрать. Алиса передаёт Бобу числа 6(n) и 3(e). Ещё Алиса вычисляет число 5(d), зная p, q и e. Итого Алиса знает числа p, q, n, e, d, Боб и перехватчик (Ева) знают числа n, e. Боб возводит 2(m) в степень 3(e), получает 8. Берёт остаток от деления 8 на 6(n), это 2. Передаёт этот остаток 2 Алисе. Алиса возводит 2 в степень 5(d), получает 32. Берёт остаток от деления 32 на 6(n), получает 2 т.е. m.
Боб хочет послать Алисе число 3 (m). Алиса выбирает два случайных простых числа: 2(p) и 3(q). Перемножает их и получает 6(n). Выбирает случайное число 3(e), оно не совсем любым может быть. Алиса передаёт Бобу числа 6(n) и 3(e). Ещё Алиса вычисляет число 5(d), зная p, q и e. Итого Алиса знает числа p, q, n, e, d, Ева знает числа n, e. Боб возводит 3(m) в степень 3(e), получает 27. Берёт остаток от деления 27 на 6(n), это 3. Передаёт этот остаток 3 Алисе. Алиса возводит 3 в степень 5(d), получает 243. Берёт остаток от деления 243 на 6(n), получает 3 т.е. m.
Боб хочет послать Алисе число 2 (m). Алиса выбирает два случайных простых числа: 2(p) и 5(q). Перемножает их и получает 10 (n). Выбирает случайное число 3(e), оно не совсем любым может быть. Алиса передаёт Бобу числа 10(n) и 3(e). Ещё Алиса вычисляет число 7(d), зная p, q и e. Итого Алиса знает числа p, q, n, e, d, Ева знает числа n, e. Боб возводит 2(m) в степень 3(e), получает 8. Берёт остаток от деления 8 на 10(n), это 8. Передаёт этот остаток 8 Алисе. Алиса возводит 8 в степень 7(d), получает 2097152. Берёт остаток от деления 2097152 на 10(n), получает 2 т.е. m.
Боб хочет послать Алисе число 2(m). Алиса выбирает два случайных простых числа: 3(p) и 5(q). Перемножает их и получает 15 (n). Выбирает случайное число 3(e), оно не совсем любым может быть. Алиса передаёт Бобу числа 15(n) и 3(e). Ещё Алиса вычисляет число 3(d), зная p, q и e. Итого Алиса знает числа p, q, n, e, d, Ева знает числа n, e. Боб возводит 2(m) в степень 3(e), получает 8. Берёт остаток от деления 8 на 15 (n), это 8. Передаёт этот остаток 8 Алисе. Алиса возводит 8 в степень 3(d), получает 512. Берёт остаток от деления 512 на 15(n), получает 2 т.е. m.
Боб хочет послать Алисе число 3(m). Алиса выбирает два случайных простых числа: 2(p) и 5(q). Перемножает их и получает 10 (n). Выбирает случайное число 11(e), оно не совсем любым может быть. Алиса передаёт Бобу числа 10(n) и 11(e). Ещё Алиса вычисляет число 3(d), зная p, q и e. Итого Алиса знает числа p, q, n, e, d, Ева знает числа n, e. Боб возводит 3(m) в степень 11(e), получает 177147. Берёт остаток от деления 177147 на 10(n), это 7. Передаёт этот остаток 7 Алисе. Алиса возводит 7 в степень 3(d), получает 343. Берёт остаток от деления 343 на 10(n), получает 3 т.е. m.
Я проверял эти вычисления с другими числами, намного большими, всё работает. Ещё раз, в чём принцип: чтобы расшифровать сообщение, Алисе или Еве нужно знать число d. Чтобы вычислить d, надо знать e, p и q (итеративный алгоритм Евклида; говоря точнее, для этого алгоритма надо знать e и произведение (p-1)*(q-1)). Так вот Алиса знает числа p и q, поэтому она может всё сделать быстро, а Ева знает только n, т.е. произведение p на q, и ей сначала надо разложить n на простые множители, что на обычном компьютере займёт миллионы лет, чтобы узнать числа p и q, необходимые для вычисления d (а d необходимо для математического пересчёта отправленного сообщения, как показано выше).
Приведу аналогию, не очень правильную, но вроде легко понятную. Боб хочет передать Алисе число 3. Алиса загадывает два числа, которые в произведении дают число 1000, например 25 и 40. Число 25 она передаёт Бобу. Боб умножает 3 на 25, получает 75, передаёт 75 Алисе. Теперь Ева (кто подслушивает) знает числа 75 и 25, и чтобы получить исходное число, она должна разделить 75 на 25. А Алисе вроде как проще - она знает число 40, и может умножить 75 на 40, получит 3000, и далее просто убирает из 3000 последние 3 нуля, получает 3. Поскольку ей легче сделать умножение чем Еве деление, она получает число 3 чуть раньше чем Ева.
Надо понимать, что в RSA шифровании используются числа размером в 200 байт, и такие два числа современный компьютер перемножает за наносекунду, а вот разлагать такие числа на простые множители компьютер будет миллион лет (современная математика может делать это только перебором).
Далее следующий момент: есть ещё квантовые компьютеры, которые могут быстро разлагать любые числа на простые множители. Говорят, вполне возможно будет сделать квантовый компьютер, который считает быстрее чем кластер из обычных компьютеров размером во всю вселенную - но только для некоторых задач, таких как разложение чисел на простые множители. Квантовые компьютеры могут взламывать RSA шифрование, и говорят что они понемногу уже это делают. Но я в передаче Дерека Миллера (Veritassium) видел изложение математических принципов другого вида шифрования, которое квантовые компьютеры не взломают, по крайней мере пока.
Там используется какой-то подбор векторов в многомерном (тысячемерном) пространстве.
Должен сказать, что приведённый выше алгоритм – большое упрощение. В реальных RSA алгоритмах числа p и q должны быть не простые, а так называемые псевдопростые. Это связано с тем, что если выбрать два случайных числа p и q размером по 200 байт, нет возможности быстро и абсолютно точно проверить, что они являются простыми (для этого надо опять же уметь быстро разлагать их на множители). С реальными RSA алгоритмами всегда есть ничтожно малая, но всё-таки не нулевая вероятность, что числа p и q окажутся “плохими”, и сообщение будет передано с ошибкой даже в случае идеальной связи через интернет.
А вот шифрование с открытым ключом более интересно. Представьте себе, что два человека разговаривают по радио, и кто-то третий их слушает. Эти два говорят на языке который подслушивающий знает, они не договаривались заранее о каком-то шифре, они видят друг друга первый раз. Тем не менее, они сообщают друг другу информацию, который этот подслушивающий узнать не может. Вы можете такое представить? Дальше станет понятно, как это работает.
Шифрование с открытым кодом, которое называется RSA, основано на математическом принципе, что перемножить два числа для компьютера намного проще, чем разложить число на простые множители. В описанном примере, этот подслушивающий в принципе может узнать то что передают другу другу эти собеседники, но для этого ему понадобится компьютер, который проработает миллион лет.
Напишу конкретно как работает RSA-шифрование. Алиса должна передать Бобу целое число, а Ева их подслушивает. Пять примеров:
Боб хочет послать Алисе число 2 (m). Алиса выбирает два случайных простых числа: 2(p) и 3(q). Перемножает их и получает 6 (n). Выбирает случайное число 3(e), оно не совсем любым может быть, Алисе надо кое что посчитать (зная p и q), чтобы его подобрать. Алиса передаёт Бобу числа 6(n) и 3(e). Ещё Алиса вычисляет число 5(d), зная p, q и e. Итого Алиса знает числа p, q, n, e, d, Боб и перехватчик (Ева) знают числа n, e. Боб возводит 2(m) в степень 3(e), получает 8. Берёт остаток от деления 8 на 6(n), это 2. Передаёт этот остаток 2 Алисе. Алиса возводит 2 в степень 5(d), получает 32. Берёт остаток от деления 32 на 6(n), получает 2 т.е. m.
Боб хочет послать Алисе число 3 (m). Алиса выбирает два случайных простых числа: 2(p) и 3(q). Перемножает их и получает 6(n). Выбирает случайное число 3(e), оно не совсем любым может быть. Алиса передаёт Бобу числа 6(n) и 3(e). Ещё Алиса вычисляет число 5(d), зная p, q и e. Итого Алиса знает числа p, q, n, e, d, Ева знает числа n, e. Боб возводит 3(m) в степень 3(e), получает 27. Берёт остаток от деления 27 на 6(n), это 3. Передаёт этот остаток 3 Алисе. Алиса возводит 3 в степень 5(d), получает 243. Берёт остаток от деления 243 на 6(n), получает 3 т.е. m.
Боб хочет послать Алисе число 2 (m). Алиса выбирает два случайных простых числа: 2(p) и 5(q). Перемножает их и получает 10 (n). Выбирает случайное число 3(e), оно не совсем любым может быть. Алиса передаёт Бобу числа 10(n) и 3(e). Ещё Алиса вычисляет число 7(d), зная p, q и e. Итого Алиса знает числа p, q, n, e, d, Ева знает числа n, e. Боб возводит 2(m) в степень 3(e), получает 8. Берёт остаток от деления 8 на 10(n), это 8. Передаёт этот остаток 8 Алисе. Алиса возводит 8 в степень 7(d), получает 2097152. Берёт остаток от деления 2097152 на 10(n), получает 2 т.е. m.
Боб хочет послать Алисе число 2(m). Алиса выбирает два случайных простых числа: 3(p) и 5(q). Перемножает их и получает 15 (n). Выбирает случайное число 3(e), оно не совсем любым может быть. Алиса передаёт Бобу числа 15(n) и 3(e). Ещё Алиса вычисляет число 3(d), зная p, q и e. Итого Алиса знает числа p, q, n, e, d, Ева знает числа n, e. Боб возводит 2(m) в степень 3(e), получает 8. Берёт остаток от деления 8 на 15 (n), это 8. Передаёт этот остаток 8 Алисе. Алиса возводит 8 в степень 3(d), получает 512. Берёт остаток от деления 512 на 15(n), получает 2 т.е. m.
Боб хочет послать Алисе число 3(m). Алиса выбирает два случайных простых числа: 2(p) и 5(q). Перемножает их и получает 10 (n). Выбирает случайное число 11(e), оно не совсем любым может быть. Алиса передаёт Бобу числа 10(n) и 11(e). Ещё Алиса вычисляет число 3(d), зная p, q и e. Итого Алиса знает числа p, q, n, e, d, Ева знает числа n, e. Боб возводит 3(m) в степень 11(e), получает 177147. Берёт остаток от деления 177147 на 10(n), это 7. Передаёт этот остаток 7 Алисе. Алиса возводит 7 в степень 3(d), получает 343. Берёт остаток от деления 343 на 10(n), получает 3 т.е. m.
Я проверял эти вычисления с другими числами, намного большими, всё работает. Ещё раз, в чём принцип: чтобы расшифровать сообщение, Алисе или Еве нужно знать число d. Чтобы вычислить d, надо знать e, p и q (итеративный алгоритм Евклида; говоря точнее, для этого алгоритма надо знать e и произведение (p-1)*(q-1)). Так вот Алиса знает числа p и q, поэтому она может всё сделать быстро, а Ева знает только n, т.е. произведение p на q, и ей сначала надо разложить n на простые множители, что на обычном компьютере займёт миллионы лет, чтобы узнать числа p и q, необходимые для вычисления d (а d необходимо для математического пересчёта отправленного сообщения, как показано выше).
Приведу аналогию, не очень правильную, но вроде легко понятную. Боб хочет передать Алисе число 3. Алиса загадывает два числа, которые в произведении дают число 1000, например 25 и 40. Число 25 она передаёт Бобу. Боб умножает 3 на 25, получает 75, передаёт 75 Алисе. Теперь Ева (кто подслушивает) знает числа 75 и 25, и чтобы получить исходное число, она должна разделить 75 на 25. А Алисе вроде как проще - она знает число 40, и может умножить 75 на 40, получит 3000, и далее просто убирает из 3000 последние 3 нуля, получает 3. Поскольку ей легче сделать умножение чем Еве деление, она получает число 3 чуть раньше чем Ева.
Надо понимать, что в RSA шифровании используются числа размером в 200 байт, и такие два числа современный компьютер перемножает за наносекунду, а вот разлагать такие числа на простые множители компьютер будет миллион лет (современная математика может делать это только перебором).
Далее следующий момент: есть ещё квантовые компьютеры, которые могут быстро разлагать любые числа на простые множители. Говорят, вполне возможно будет сделать квантовый компьютер, который считает быстрее чем кластер из обычных компьютеров размером во всю вселенную - но только для некоторых задач, таких как разложение чисел на простые множители. Квантовые компьютеры могут взламывать RSA шифрование, и говорят что они понемногу уже это делают. Но я в передаче Дерека Миллера (Veritassium) видел изложение математических принципов другого вида шифрования, которое квантовые компьютеры не взломают, по крайней мере пока.
Там используется какой-то подбор векторов в многомерном (тысячемерном) пространстве.
Должен сказать, что приведённый выше алгоритм – большое упрощение. В реальных RSA алгоритмах числа p и q должны быть не простые, а так называемые псевдопростые. Это связано с тем, что если выбрать два случайных числа p и q размером по 200 байт, нет возможности быстро и абсолютно точно проверить, что они являются простыми (для этого надо опять же уметь быстро разлагать их на множители). С реальными RSA алгоритмами всегда есть ничтожно малая, но всё-таки не нулевая вероятность, что числа p и q окажутся “плохими”, и сообщение будет передано с ошибкой даже в случае идеальной связи через интернет.
