Original:http://www.queen.clara.net/pgp/art6.html

Принципи сучасної криптографії

Nat Queen

[Примітка. Це дещо модифікована версія статті, яка спочатку з’явилася у випуску журналу Archive за грудень 2010 року.]

Коли я в минулому році почав готувати розмову на цю тему для групи користувачів Midlands, першою моєю думкою було базуватися на статті, яку я написав для Archive 17: 3 в 2003 році. Однак я швидко зрозумів, що потрібна стара стаття щоб оновитись, і я додав новий матеріал. Ця стаття - це розширена версія розмови, яку я виголосив.

Основні поняття та термінологія

У криптографії, як і в будь-якому науковому предметі, важлива точність, і це стосується, зокрема, термінології, яку мирянин часто неправильно використовує. Прикладом цього є плутанина між термінами криптографія та криптологія, які часто використовуються як взаємозамінні в популярній писемності.

Криптологія - це більш широкий предмет, що складається з двох галузей: криптографія, наука про створення захищених криптосистем для перетворення даних у форму, нерозбірливу для несанкціонованих осіб, і криптоаналіз, наука про "напади" на криптосистеми з метою "зламати" їх чи принаймні виявити їх слабкі сторони.

Коли криптоаналіз виявляє слабкі місця в криптосистемах, криптографи створюють більш безпечні криптосистеми. І навпаки, у міру того, як криптосистеми стають сильнішими, криптоаналітики намагаються виявити більш потужні методи їх атаки. Таким чином, криптографія та криптоаналіз є взаємодоповнюючими.

Метою криптографії є ​​перетворення будь-яких даних у первісному вигляді, що називається простим текстом, у незрозумілу форму, відому як шифротекст . Цей процес називається шифруванням . Зворотний процес відновлення простого тексту з шифротексту називається дешифруванням . У популярній писемності часто можна зустріти (неправильні) терміни «кодування» та «декодування», але технічно вони мають зовсім інші значення і не повинні використовуватися в сучасному контексті.

Важливо розуміти, що відкритий текст не обов'язково повинен бути текстовим повідомленням. Це може бути комп’ютерний файл, що представляє будь-який тип дати - зображення, базу даних тощо.

Будь-яка конкретна криптосистема заснована на конкретних алгоритмах шифрування та дешифрування. Алгоритм - це просто обчислювальна процедура, яка дотримується певного набору правил. Важливим загальним принципом сучасної криптографії, відомим як принцип Керкхоффа, є те, що алгоритми, що визначають криптосистему, повинні бути загальновідомими. Лише тоді криптосистема може бути критично проаналізована експертами, щоб користувачі могли мати в ній впевненість.

Точний спосіб шифрування простого тексту за допомогою певного алгоритму залежить від секретного ключа, який на практиці є просто деякою великою кількістю. Під принципом Керкхоффа полягає в тому, що безпека шифрування покладається на секретний ключ, а не на якийсь секретний алгоритм шифрування. Зрозуміти це легко за допомогою наступної аналогії: Не існує секретів того, як працює комбінований замок - його механізм призначений для відкриття блокування, коли набирається певна послідовність номерів, - але заблокований замок безпечний, оскільки є як правило, понад мільйон можливих комбінацій ("клавіш").

Сучасні криптосистеми можна класифікувати в основному на два основні типи: симетричні криптосистеми з відкритим ключем. Вони будуть описані нижче.

Симетрична криптографія

Симетрична (або секретний ключ) криптосистема - це та, яка використовує той самий ключ для шифрування та дешифрування. Це аналогічно тому, що ви використовуєте один і той же ключ, щоб заблокувати або розблокувати вхідні двері вашого будинку.

Зазвичай симетричне шифрування виконується за допомогою блочного шифру, який є методом шифрування, який ділить простий текст на блоки певної фіксованої довжини і перетворює кожен блок за певним алгоритмом для отримання блоку шифротексту. Той самий алгоритм і той самий ключ використовуються для дешифрування, який відтворює початковий простий текст. Це проілюстровано на рисунку 1:

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

Важливим прикладом ітераційного блочного шифру є Розширений стандарт шифрування (AES), який у 2000 році був обраний Національним інститутом стандартів та технологій (NIST) у США як заміна на старіший DES (стандарт шифрування даних), який зараз вважається незахищеним.

Шифр AES працює з блоками 128 біт і дозволяє розміру ключів 128, 192 або 256 біт. Залежно від того, який із трьох ключових розмірів використовується, існує 10, 12 або 14 раундів. Уряд США оголосив AES прийнятним для захисту секретної інформації до "секретної інформації", коли використовується з найбільшим розміром ключів (тобто AES-256).

Цей шифр, як і декілька інших, які зараз мають загальне використання, захищений від усіх відомих методів криптоаналізу. Зокрема, не існує відомого способу розтріскування, який є більш ефективним, ніж "груба сила", тобто тестування всіх можливих клавіш до тих пір, поки не буде знайдена потрібна, що, в свою чергу, не під силу будь-якій відомій технології. Саме це робить шифр сильним, і це дозволяє нам отримати кількісну оцінку його міцності.

Щоб зрозуміти, наскільки сильний такий шифр, давайте оцінимо, скільки часу знадобиться, використовуючи грубу силу, щоб зламати AES-128. Зі 128-розрядними клавішами кількість можливих клавіш становить 2 128, що приблизно становить 3 × 10 38 . (Якщо ви не знаєте, як перетворити потужність 2 математично на потужність 10, більшість сучасних калькуляторів можуть це зробити для вас.) Це колосальне число, але нам все одно потрібне припущення про наявну обчислювальну потужність для того, щоб прийти до визначеної оцінки.

Будьмо щедрі і припустимо, для певності, що ми можемо використовувати 10 10 (тобто 10 мільярдів) комп’ютерів, кожен тестуючи 10 10 клавіш в секунду, так що ми можемо протестувати 10 20 клавіш за секунду. Тоді час, необхідний для тестування всіх можливих ключів, становитиме (3 × 10 38 ) / 10 20 = 3 × 10 18 секунд, що становить приблизно 10 11 (тобто 100 мільярдів) років. За даними сучасної космології, це довше відомого віку Всесвіту, 13,7 мільярдів років. Якщо бути справедливим, в середньому знадобиться лише половина цього часу, щоб знайти потрібний ключ.

Зауважте, що жорстока сила, застосована таким чином, дозволить визначити лише один конкретний ключ. Він не передбачає способу розтріскування шифру в цілому, тобто це не метод справжнього криптоаналізу.

З кожним додатковим бітом довжини клавіші кількість можливих клавіш подвоюється. Припустимо, наприклад, що ми використовуємо ключі з 256 бітами замість 128. Скільки часу знадобиться тоді, щоб зламати зашифроване повідомлення, при тих же припущеннях про наявну обчислювальну потужність? Використовуючи той самий метод, що і вище, залишається читачеві вправу перевірити, чи відповідає відповідь приблизно 3 × 10 49 років. Це приблизно на 300 трлн трлн трильйонів разів довше, ніж для 128-бітного ключа, який, напевно, погодитесь, є досить хорошою безпекою!

Криптографія з відкритим ключем

Симетрична криптографія має один серйозний недолік, відомий як ключова проблема розподілу. Оскільки один і той же ключ використовується як для шифрування, так і для розшифровки, дві сторони, які бажають безпечно спілкуватися, повинні якось прийняти взаємно узгоджений ключ перед обміном будь-якими повідомленнями. Звичайно, це можливо, якщо вони зустрічаються заздалегідь особисто. Але якщо дві сторони з різних куточків світу не можуть зустрітися, як вони можуть обмінятися секретним ключем? У деяких випадках вони можуть захотіти обмінятися лише одним повідомленням. Усі доступні форми електронного зв’язку можуть перехоплюватися підслуховувачами. Якщо у обох сторін був якийсь захищений канал зв'язку для обміну секретним ключем, вони могли б також використовувати його для обміну самим повідомленням!

Криптографія з відкритим ключем акуратно вирішує цю загадку. У криптографії з відкритим ключем кожен користувач має унікальну пару ключів: відкритий ключ та секретний ключ .

Загальнодоступний ключ може широко розголошуватися і використовуватися будь-ким для надсилання зашифрованого повідомлення власнику цього ключа, приблизно так само, як більшість людей публікує свій телефонний номер у загальнодоступному каталозі, щоб дозволити іншим звертатися до них. Наприклад, мій відкритий ключ доступний з мого особистого веб-сайту, і кожен, хто знає моє ім’я та / або адресу електронної пошти, також може завантажити його з різних відкритих серверів ключів в Інтернеті.

Секретний ключ зберігається суворо таємно і його власник може (тільки) використовувати для розшифрування повідомлень, призначених саме для цієї особи. На практиці секретний ключ зберігається сильно зашифрованим у комп'ютері користувача за допомогою симетричного шифру. Лише власник секретного ключа може розблокувати його, ввівши таємну парольну фразу, коли програма шифрування вимагає цього ключа, після чого він негайно повторно шифрується автоматично.

Загальна схема криптографії відкритого ключа проілюстрована на рисунку 2:

Тут Боб надсилає захищене повідомлення Алісі. У таких прикладах звичайно використовувати певні імена, починаючи з A, B або C, як потрібно, і я також дотримуюся популярної (несексистської!) Конвенції, що відправник вважається чоловіком, а одержувачем - жінкою.

Таким чином, Боб зашифровує відкритий ключ Аліси відкритим ключем (PK), і отриманий шифротекст може передаватися через незахищений канал, наприклад електронну пошту. Аліса розшифровує шифротекст своїм секретним ключем (SK), щоб відновити оригінальний відкритий текст. Ніхто більше не може цього зробити, бо ніхто більше не має доступу до секретного ключа Аліси.

Тут проста корисна проста аналогія. Відкритий ключ схожий на замок із комбінацією - його може заблокувати кожен. Секретний ключ схожий на комбінацію, необхідну для відкриття замка - це може зробити лише його власник.

Щоб така схема працювала, необхідно виконати кілька умов:

Відправник та одержувач повинні використовувати однакові (загальнодоступні) алгоритми шифрування / дешифрування. Користувачі (точніше, їх програмне забезпечення для шифрування) повинні мати можливість генерувати випадкові пари ключів (PK та SK) досить ефективно, хоча це потрібно робити лише один раз, оскільки кожен користувач може продовжувати використовувати одну і ту ж пару ключів. Процеси шифрування та дешифрування повинні бути обчислювально ефективними. СК повинен розшифрувати будь-яке повідомлення, зашифроване з ПК. І нарешті, обчислення СК з пізнання ПК має бути нездійсненним. Ця остання вимога - це те, що робить криптосистему надійною.

Оскільки СК повинен повернути дію ПК, ці дві клавіші повинні бути чітко пов'язані математично. На перший погляд може здатися парадоксальним те, що на практиці неможливо змінити дію відкритого ключа шляхом виведення секретного ключа.

Основна математична ідея, яка робить таку криптосистему можливою, відома як одностороння функція, яка займається перешкодою . Одностороння функція - це правило провести обчислення, яке є простим, але обернене якого важко обчислити. Терміни "легкий" і "важкий" тут мають дуже конкретне технічне значення. Грубо кажучи, обчислення є "важким", якщо (і лише якщо) час, необхідний комп'ютеру для виконання обчислення, збільшується в експоненціальній залежності від розміру вхідного числа.

Прикладом односторонньої функції є множення двох великих простих чисел. Навіть якщо цифри мають по кілька сотень цифр у кожному, сучасний комп'ютер може обчислити їх добуток менше ніж за секунду, припускаючи, звичайно, що він забезпечений спеціальними процедурами для роботи з дуже великими числами. Однак, якщо надати лише добуток двох таких великих простих чисел і попросити відновити два фактори, жоден відомий комп'ютер не зможе вирішити цю проблему менш ніж за мільйон років. Математики, як правило, вважають, що це справді "важка" проблема в технічному розумінні, хоча на сьогодні немає суворих доказів.

Функція трапорта - це одностороння функція, обернена повернення якої стає простою для обчислення, коли відома певна додаткова інформація. Як простий приклад, якщо сума двох простих чисел у наведеному вище прикладі відома, то знайти два окремих простих числа стає легко (справді тривіально). Це так, тому що легко знайти два числа, якщо їх сума і добуток відомі, оскільки кожен, хто знає елементарну алгебру, може легко перевірити.

Усі криптосистеми з відкритим ключем базуються на конкретних односторонніх функціональних заходах, включаючи пояснену трохи вище. У будь-якій такій криптосистемі секретний ключ виконує функцію просвітки - спеціальної інформації, яка дає змогу змінити процес шифрування.

Без значно більшої кількості математики недоцільно пояснювати, як саме можна створювати пару відкритих та секретних ключів. Насправді це залежить від конкретної криптосистеми, яка використовується. Однак простий приклад із двома простими числами, поясненими вище, повинен переконати читача в тому, що функціонування односторонніх функцій для виходу на вулицю реально можливо.

Криптографія з відкритим ключем реалізується у двох типах комп'ютерної програми: PGP (що означає досить гарне конфіденційність) та GnuPG (що означає Гвардію конфіденційності GNU, іноді також називається GPG). Це світовий стандарт безпечної електронної пошти. PGP було оригінальним програмним забезпеченням, а GnuPG був розроблений пізніше, але вони, як правило, сумісні, і існують версії для всіх основних операційних систем.

Подвійна система

Впровадження криптовалюти з відкритим ключем у PGP та GnuPG не так просто, як може запропонувати попередня дискусія. Це тому, що вони використовують подвійну систему, яка включає як симетричну, так і криптографію з відкритим ключем. Основна причина цього ускладнення полягає в тому, що симетрична криптографія набагато ефективніша, ніж криптографія з відкритим ключем, і це має значні наслідки для часу обчислення, необхідного для обробки довгого повідомлення. Подвійна система працює наступним чином:

Припустимо, ще раз, що Боб хоче надіслати захищене повідомлення Алісі. Потім Боб зашифровує повідомлення M за допомогою симетричного шифру з випадковим чином сформованим одноразовим ключем K для отримання шифротексту M ' . У той же час він шифрує ключ K за допомогою криптосистеми з відкритим ключем, відкритим ключем Аліси, для отримання зашифрованого ключа K ' . Потім Боб посилає і М ', і К' Алісі. Це безпечно навіть через незахищений канал, як-от електронна пошта.

Аліса просто перевертає процес, щоб прочитати повідомлення. Вона спочатку розшифровує K ', використовуючи її секретний ключ, щоб отримати оригінальний ключ K для симетричного шифру. Потім вона використовує цей ключ K для розшифрування шифротексту M ', щоб отримати оригінальне повідомлення M. Звичайно, обидві сторони повинні використовувати для цього однакові дві криптосистеми.

PGP або GnuPG подбає про все це автоматично. На практиці користувачі не повинні турбуватися про деталі процесів шифрування та дешифрування. Програмне забезпечення Боба буде налаштоване на використання конкретних криптосистем за замовчуванням (які він може змінити за бажанням). Його файл "відкритих ключів" міститиме відкриті ключі всіх його кореспондентів, і йому потрібно лише вказати, кому зашифроване повідомлення має бути надіслане. Програмне забезпечення Аліси автоматично розпізнає, які криптосистеми використовувались для шифрування повідомлення Боба, і їй потрібно лише ввести свою таємну парольну фразу, щоб програма могла розблокувати її (зашифрований) секретний ключ, щоб розшифрувати повідомлення Боба. PGP або GnuPG дозволяє користувачам робити все це без особливих зусиль.

Подвійна система має ряд переваг. Як вже було сказано, криптографія з відкритим ключем є менш ефективною, ніж симетрична криптографія. Однак, оскільки криптосистема відкритого ключа використовується лише для шифрування ключа для симетричного шифру, який має фіксовану довжину (як правило, між 128 і 256 бітами), сучасний комп'ютер може це зробити дуже швидко, незалежно від того, наскільки триває фактичне повідомлення є.

Подвійна система також означає, що одне і те ж повідомлення може бути зашифровано для декількох одержувачів дуже ефективно. Він шифрується лише один раз одноразовим ключем K, як обговорювалося вище, і відправник шифрує цей ключ по черзі відкритим ключем кожного одержувача. Потім весь набір зашифрованих ключів K ' надсилається одночасно всім одержувачам, і їх програмне забезпечення автоматично вибирає відповідний зашифрований ключ K' у кожному випадку. Таким чином, зашифрувати повідомлення настільки ж просто одночасно для декількох одержувачів, як і надіслати їм загальну електронну пошту за допомогою будь-якого поштового клієнта. Відправник просто вказує, яким одержувачам пошта повинна бути зашифрована, а програмне забезпечення PGP або GnuPG піклується про все.

Цікавим наслідком подвійної системи є те, що якщо одне і те ж повідомлення шифрується неодноразово, шифрування буде кожного разу різним, оскільки для симетричного шифру кожен раз використовується новий випадково сформований одноразовий ключ.

Програмне забезпечення PGP та GnuPG

Існують як комерційні, так і безкоштовні версії PGP. Останньою версією Windows, наприклад, є PGP 10. Однак, лише RPC 2 перенесено до ОС RISC, і ця версія старіння зараз досить обмежена для безпечного спілкування з рештою світу, оскільки вона дозволяє лише один конкретний набір алгоритмів шифрування, тоді як більш сучасні версії PGP працюють з кількома різними алгоритмами, які стали більш популярними.

Усі версії GnuPG є безкоштовними та відкритими, без обмежень щодо їх використання. Вони навіть можуть вільно використовуватися для комерційних цілей. Порт RISC OS GnuPG є досить сучасним, тому рекомендується для користувачів ОС RISC. GnuPG (як і старий PGP 2) - це лише програма командного рядка, і деяким людям важко запам’ятати правильні команди. Однак це не є реальною проблемою, оскільки для GnuPG є прекрасні передні кінці (як і для PGP 2).

Інформацію про PGP та GnuPG для ОС RISC, самого програмного забезпечення та зручних для користувача передніх кінців можна отримати з мого веб-сайту за адресою http://www.queen.clara.net/pgp/acorn.html, де відвідувачі також можуть знайти путівники та навчальні посібники для початківців.

Деякі популярні клієнти електронної пошти (наприклад, Messenger Pro і Pluto) мають зручні для користувача варіанти безпечної електронної пошти за допомогою PGP або GnuPG. Використання цих варіантів досить інтуїтивно зрозуміле. Я закликаю всіх користувачів RISC OS прийняти GnuPG і переконати всіх своїх кореспондентів використовувати PGP або GnuPG, якщо вони ще не роблять цього. Навіщо надсилати електронну пошту як простий текст, коли на шифрування чи розшифрування типового повідомлення потрібно не більше секунди, і ви можете бути впевнені, що ваше листування повністю приватне?


Естонська переклад цієї сторінки (надана Каролін Лохмус)

Російський переклад цієї сторінки (надається ResumeCoversCV)

Переклад цієї сторінки в Пенджабі (надається Bydiscountcodes )