[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 * 1185.
Давайте подивимося, що наша наступна величина до буде.
Що ж, схоже, у нас є 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 взагалі. [Сміх]
На всіх.