[Powered by Google Translate] [RSA]
[Rob Боуден] [Tommy MacWilliam] [Harvard University]
[Это CS50.] [CS50.TV]
Давайте взглянем на RSA, широко используемый алгоритм шифрования данных.
Алгоритмы шифрования, как Цезаря и Виженера шифры не очень безопасно.
С шифр Цезаря, злоумышленнику нужно только попробовать 25 различных ключей
чтобы получить текст сообщения.
В то время как шифр Виженера является более безопасной, чем шифр Цезаря
из-за большего пространства поиска для ключей, если злоумышленник
знает, что длина ключа в шифра Виженера,
что может быть определено с помощью анализа закономерностей в зашифрованный текст,
Шифр Виженера не намного более безопасным, чем шифр Цезаря.
RSA, с другой стороны, не уязвимы для атак подобного.
Шифр Цезаря и Виженера Шифр ​​использовать тот же ключ
для шифрования и расшифровки сообщений.
Это свойство делает эти шифры алгоритмы симметричного ключа.
Основная проблема с симметричным ключом Алгоритмы
является то, что они полагаются на одной шифрование и отправка сообщений
и тот, получения и расшифровки сообщения
к уже договорились заранее на ключ, то они будут использовать.
Но у нас есть немного проблем с запуском здесь.
Как 2 компьютера, которые хотят общаться создании секретного ключа между ними?
Если ключ должен быть тайным, то нам нужен способ для шифрования и дешифрования ключа.
Если все мы имеем, является симметричным ключом
Затем мы только возвращаемся к той же проблеме.
RSA, с другой стороны, использует пару ключей,
один для шифрования, а другой для расшифровки.
Одна из них называется открытым ключом, а другой закрытым ключом.
Открытый ключ используется для шифрования сообщений.
Как можно догадаться по его названию, мы можем поделиться нашим открытым ключом с
кого мы хотим без ущерба для безопасности зашифрованное сообщение.
Сообщения шифруются с помощью открытого ключа
могут быть расшифрованы только с помощью соответствующего закрытого ключа.
В то время как вы можете поделиться своим открытым ключом, вы всегда должны иметь личные секретный ключ.
и только закрытый ключ может быть использован для расшифровки сообщений
если 2 пользователи хотят, чтобы отправить сообщения, зашифрованные RSA
вперед и назад, как пользователи должны иметь свои собственные государственные и частные пары ключей.
Сообщения от пользователей с 1 по пользователь 2
использовать только пара ключей пользователя 2, и сообщений от пользователей 2 к пользователю 1
использовать только пара ключей пользователя 1.
Дело в том, что есть 2 отдельные ключи для шифрования и расшифровки сообщений
RSA делает асимметричных ключей алгоритма.
Нам не нужно, чтобы зашифровать открытым ключом для того, чтобы отправить его на другой компьютер
С ключевым является общественным любом случае.
Это означает, что RSA не имеют тот же проблема запуска
как симметричный ключ алгоритма.
Так что, если я хочу отправить сообщение с помощью шифрования RSA
Робу, я в первую очередь необходимо открытого ключа Роба.
Для генерации пары ключей, Роб необходимо выбрать 2 больших простых чисел.
Эти цифры будут использоваться как в открытых и закрытых ключей,
но открытый ключ будет использовать только продукт этих 2 номера,
Не сами числа.
Как только я зашифровал сообщение, используя открытый ключ Роба
Я могу отправить сообщение Роб.
Для компьютера, факторинг чисел является трудной задачей.
Открытый ключ, помните, использовали продукт из 2 простых чисел.
Этот продукт должен то есть только 2 фактора,
которые, случается, цифры, которые составляют закрытый ключ.
Для того, чтобы расшифровать сообщение, RSA будет использовать этот секретный ключ
или числа перемножаются в процессе создания открытого ключа.
Потому что это вычислительно трудно разложить число
использовать в открытых ключей в 2 чисел, используемых в закрытый ключ
это трудно для злоумышленника, чтобы выяснить закрытого ключа
, которые будут необходимы для расшифровки сообщения.
Теперь давайте войдем в некоторых низком уровне детали RSA.
Давайте сначала посмотрим, как мы можем генерировать пары ключей.
Во-первых, нам нужно 2 простых числа.
Мы называем эти 2 числа р и ц.
Для того, чтобы подобрать р и д, на практике мы будем генерировать псевдослучайно
больших количествах, а затем использовать тест для определения является ли
эти цифры, вероятно, простое.
Мы можем держать генерации случайных чисел снова и снова
до тех пор пока у нас есть 2 простых чисел, мы можем использовать.
Вот давайте выберем р = 23 и Q = 43.
Помните, что на практике, р и д должна быть гораздо большем количестве.
Насколько мы знаем, чем больше число, тем труднее
для взлома зашифрованных сообщений.
Но это также более дорогим для шифрования и расшифровки сообщений.
Сегодня это часто рекомендуется, чтобы р и д по крайней мере 1024 бит,
который ставит каждый номер в более чем 300 десятичных цифр.
Но мы выберем этих небольших количествах для этого примера.
Теперь мы умножим р и д вместе, чтобы получить 3-й номер,
который мы будем называть п.
В нашем случае N = 23 * 43, = 989.
Мы N = 989.
Далее мы умножим р - 1 с д - 1
чтобы получить 4-й номер, который мы будем называть м.
В нашем случае М = 22 * ​​42, = 924.
Мы имеем т = 924.
Теперь нам нужно число е, что является относительно простым с м
и менее метров.
Два числа, взаимно простые или взаимно
если только положительное целое число, которое делит их обоих равномерно 1.
Иными словами, наибольший общий делитель е и т
должна быть 1.
На практике, это общие для электронного быть простым числом 65537
тех пор, пока это число не оказаться фактором м.
Для наших ключей, мы выберем е = 5
С 5 взаимно простое с 924.
Наконец, мы должны будем еще один номер, который мы будем называть г.
D должно быть некоторое значение, которое удовлетворяет уравнению де = 1 (той т).
Это м мод означает мы будем использовать то, что называется модулярной арифметики.
В модульной арифметики, когда рядом оказывается выше некоторого верхняя граница
она будет обернуть обратно к 0.
Часы, например, использует модульную арифметику.
Через минуту после 1:59, например, 2:00,
Не 1:60.
Минутная стрелка была обернута вокруг до 0
при достижении верхней границы 60.
Таким образом, мы можем сказать, 60 это эквивалентно 0 (мода 60)
и 125 эквивалентно 65 эквивалентно 5 (мода 60).
Наш открытый ключ будет электронной пары и п
где в данном случае е-5 и п 989.
Наш частный ключ будет пара г и н,
которая в нашем случае составляет 185 и 989.
Обратите внимание, что наши оригинальные простых р и д не появляются
в любом месте нашей частной или государственной ключи.
Теперь, когда у нас есть пара ключей, давайте посмотрим, как мы можем зашифровать
и расшифровать сообщение.
Я хочу послать сообщение Роб,
так что он будет один для создания этого ключа.
Тогда я спрошу Rob за его открытый ключ, который я буду использовать
Для шифрования сообщения, чтобы отправить его.
Помните, что это совершенно нормально для Роба поделиться своим открытым ключом со мной.
Но это не было бы хорошо, чтобы поделиться своим закрытым ключом.
Я не имею никакого представления, что его закрытый ключ.
Мы можем разбить наши сообщения м на несколько кусков
Все меньше п, а затем зашифровать каждый из этих кусков.
Мы будем шифровать строку CS50, которые мы можем разбить на 4 кусков,
по одному в письме.
Для того, чтобы зашифровать свое послание, мне нужно, чтобы преобразовать его в
своего рода числового представления.
Давайте объединить ASCII значения с символами в моем сообщении.
Для того, чтобы зашифровать данное сообщение м.
Мне нужно вычислить с = м к е (той п).
Но м должно быть меньше, чем п,
или же полное сообщение не может быть выражено по модулю п.
Мы можем разбить м на несколько кусков, каждый из которых меньше, чем п,
и шифровать каждый из этих кусков.
Шифрование каждый из этих кусков, мы получаем c1 = 67 до 5 (мод 989)
который = 658.
Для нашего второго блока мы имеем 83 до 5 (мод 989)
который = 15.
Для нашего третьего блока у нас есть 53 до 5 (мод 989)
который = 799.
И, наконец, для нашего последний кусок у нас есть 48 до 5 (мод 989)
который = 975.
Теперь мы можем написать за эти зашифрованные значения Роб.
Здесь вы идете, Роб.
В то время как наши сообщения в полете, давайте еще раз посмотрим
на то, как мы получили, что значение D.
Наш номер D, необходимый для удовлетворения 5D = 1 (той 924).
Это делает г мультипликативного обратного из 5 по модулю 924.
Учитывая, 2 целых чисел, а, б, расширенный алгоритм Евклида
может быть использован, чтобы найти наибольший общий делитель этих 2 целых чисел.
Это также даст нам 2 других номера, х и у,
, что удовлетворяет уравнению ах + Ьу = наибольший общий делитель а и Ь.
Как это нам поможет?
Ну, подключив е = 5 для
и т = 924 для б
Мы уже знаем, что эти числа взаимно просты.
Их наибольший общий делитель равен 1.
Это дает нам 5x + 924y = 1
или 5x = 1 - 924y.
Но если мы заботимся только о все по модулю 924
Затем можно опустить - 924y.
Вспомните часы.
Если минутная стрелка на 1, а затем ровно в 10 часов пройдет,
мы знаем, что минутная стрелка все равно будет на 1.
Здесь начинаются с 1, а затем обернуть вокруг именно у раза,
таким образом, мы все еще будем в 1.
У нас есть 5x = 1 (той 924).
И вот эта х так же, как г мы искали прежде,
Таким образом, если мы используем расширенный алгоритм Евклида
чтобы получить это число х, это число мы должны использовать как наша г.
Теперь давайте запустим расширенный алгоритм Евклида для = 5
и B = 924.
Мы будем использовать метод, называемый таблицей метод.
Наша таблица будет иметь 4 колонки, х, у, г, а к.
Наш стол начинается с 2 ряда.
В первом ряду у нас есть 1, 0, то наше значение, которое является 5,
и наша вторая строка 0, 1, и наше значение б, который является 924.
Стоимость 4-го столбца, к, будет результат
деления значения D в строке выше его значение D
на той же строке.
У нас есть 5 деленное на 924 = 0 с некоторым остатком.
Это означает, что мы имеем к = 0.
Теперь стоимость каждой другой клетке будет значение ячейки 2 ряда выше
минус значение строки над ним к раз.
Давайте начнем с D в 3-м ряду.
У нас есть 5 - 924 * 0 = 5.
Далее мы имеем 0 - 1 * 0, равная 0
и 1 - 0 * 0, что составляет 1.
Не слишком плохо, так что давайте перейдем к следующей строке.
Во-первых, нам нужно наше значение к.
924 делим на 5 = 184 с некоторым остатком,
таким образом, наши значения для К 184.
Сейчас 924 - 5 * 184 = 4.
1 - 0 * 184 1 и 0 - 1 * 184 -184.
Ладно, давайте сделаем следующую строку.
Наши значение к будет 1, так как
5 делится на 4 = 1 с некоторым остатком.
Давайте заполним в других колонках.
5 - 4 * 1 = 1.
0 - 1 * 1 = -1.
И 1 - 184 * 1 185.
Давайте посмотрим, что наша следующая величина к будет.
Что ж, похоже, у нас есть 4 разделен на 1, что на 4.
В этом случае, когда мы делением на 1 такой, что к равно
Значение D в приведенной выше строке означает, что мы сделали с нашим алгоритмом.
Мы видим здесь, что мы имеем х = 185, у = -1 в последнем ряду.
Давайте теперь вернемся к нашей первоначальной цели.
Мы сказали, что значение х в результате выполнения этого алгоритма
будет мультипликативным обратным (той б).
Это означает, что 185 является мультипликативным обратным 5 (мод 924)
Это означает, что у нас есть значение 185 для г.
Тот факт, что D = 1 в последней строке
проверяет, что е было взаимно просто с м.
Если бы это было не 1, то мы должны были бы выбрать новый электронный.
Теперь давайте посмотрим, если Роб получил мое сообщение.
Когда кто-то посылает мне зашифрованное сообщение
тех пор, как я держал мой закрытый ключ тайну
Я единственный, кто может расшифровать сообщение.
Для расшифровки блока с I можно вычислить исходное сообщение
равно кусок в г Мощность (той п).
Помните, что г и п от моего закрытого ключа.
Чтобы получить полное сообщение из кусков мы расшифровать каждый кусок
и объединить результаты.
Точно, как обеспечивается безопасность RSA?
Правда, мы не знаем.
Безопасность на основе, как долго это займет злоумышленнику взломать сообщение
зашифрованные с RSA.
Помните, что злоумышленник имеет доступ к вашим открытым ключом,
который содержит е и п.
Если злоумышленнику удается разложить п на своих 2 простых числа, р и д,
тогда она могла бы рассчитывать D с помощью расширенного алгоритма Евклида.
Это дает ей секретный ключ, который может быть использован для расшифровки сообщения.
Но как быстро мы можем разложить целые числа?
Опять же, мы не знаем.
Никто не нашел быстрый способ сделать это,
Это означает, что данный достаточно больших п
потребуется злоумышленнику нереально долго
на множители числа.
Если кто-то показал быстрый способ факторизации целых чисел
RSA будет нарушена.
Но даже если целочисленной факторизации по сути своей медленной
RSA алгоритм может еще есть какой-то изъян в нем
, что позволяет легко расшифровки сообщений.
Никто не нашел и показал такой изъян не менее,
но это не означает, что не существует.
В теории, кто-то может быть там читать все данные, зашифрованные с RSA.
Там другая немного вопрос конфиденциальности.
Если Томми шифрует некоторые сообщения, используя мой открытый ключ
и злоумышленник шифрует сообщение, используя тот же мой открытый ключ
Злоумышленник увидит, что 2 сообщения идентичны
и, следовательно, знаем, что Томми зашифрованы.
Для того, чтобы предотвратить это, сообщения, как правило, дополняются случайными битами
Перед зашифрованы так, что то же самое сообщение, зашифрованное
несколько раз будет выглядеть по-разному тех пор, как обивка на сообщение разные.
Но помню, как мы должны разделить сообщения на куски
так, чтобы каждый кусок меньше, чем п?
Padding куски означает, что мы, возможно, придется разделить вещи
в еще более кусков, так как мягкий кусок должен быть меньше, чем л.
Шифрование и дешифрование являются относительно дорогими с RSA,
и поэтому нуждаются, чтобы разбить сообщение на множество кусков может быть очень дорогостоящим.
Если большой объем данных должен быть зашифрован и расшифрован
мы можем объединить преимущества симметричного ключа Алгоритмы
с теми RSA, чтобы получить безопасность и эффективность.
Хотя мы не будем вдаваться в это здесь,
AES является симметричным ключом, алгоритм, как Виженера и Цезаря шифры
но гораздо сложнее взломать.
Конечно, мы не можем использовать AES без создания общего секретного ключа
между 2 системами, и мы увидели проблемы с этим раньше.
Но теперь мы можем использовать RSA для установления общего секретного ключа между 2 системами.
Мы будем называть компьютер отправки данных отправителя
и компьютера получения данных приемником.
Приемник имеет пару ключей RSA и посылает
открытый ключ отправителя.
Отправитель генерирует ключ AES,
шифрует его с помощью открытого ключа RSA приемника,
и отправляет ключ AES в приемник.
Приемник расшифровывает сообщение с помощью своего закрытого ключа RSA.
И отправитель и получатель теперь есть ключ AES между ними.
AES, который является гораздо быстрее шифрования и дешифрования, чем RSA,
Теперь можно использовать для шифрования больших объемов данных и отправить их на приемник,
кто может расшифровать, используя тот же ключ.
AES, который является гораздо быстрее шифрования и дешифрования, чем RSA,
Теперь можно использовать для шифрования больших объемов данных и отправить их на приемник,
кто может расшифровать, используя тот же ключ.
Мы просто нуждались RSA для передачи общего ключа.
Нам больше не нужно использовать RSA вообще.
Похоже, я получил сообщение.
Это не имеет значения, если кто читал, что на бумажный самолетик, прежде чем я поймал его
потому что я единственный с закрытым ключом.
Давайте расшифровка каждого из кусков в сообщении.
Первый кусок, 658, мы поднимаем до уровня Д власть, которая составляет 185,
мод п, что 989, равна 67,
которая является буква С в ASCII.
Теперь, на втором блоке.
Второй блок имеет значение 15,
которые мы поднимаем на 185-й власти,
мод 989, а это равно 83
которая является письме S в ASCII.
Теперь в третий кусок, который имеет значение 799, мы поднимаем до 185,
мод 989, а это равно 53,
которая является значение символа 5 в ASCII.
Теперь за последний кусок, который имеет значение 975,
мы поднимаем до 185, мод 989,
а это равно 48, что значение символа 0 в ASCII.
Меня зовут Боб Боуден, и это CS50.
[CS50.TV]
RSA вообще.
RSA вообще. [Смех]
На всех.