Длина ключа та її повний перебор

Длина ключа та її повний перебір Зміст 1. Запровадження 1.1. Що таке біт? 1.2. Що таке криптографічний ключ? 1.3. Що таке повний перебір? 1.4. Чи є повний перебір єдино можливим методом криптоанализа? 1.5. 128-битный ключ вдвічі сталіший до злому, ніж 64-битный? 1.6. PGP має бути дуже стійкий, оскільки використовує ключі 1024 біта. 2. Поточне стан справ 2.1. Яка максимальна довжина ключа для симетричних криптосистем, яка піддається програмному злому методом повного перебору? 2.2. І це, з допомогою спеціальної апаратури? 2.3. Щодо несиметричних криптосистем? 2.4. Що щодо «кавника «Шаміра?

· 3. Те, що можливим у майбутньому.

3.1. Що таке закон Мура? 3.2. Яка гадана вартість повного перебору з використанням спеціалізованого устаткування? 3.3. А використанням квантових комп’ютерів?

· 4. Різні чутки.

4.1. NSA/DST/другие можуть ламати ключі до 128 біт. 4.2. NSA/DST/другие мають квантовими комп’ютерами. 4.3. NSA/DST/другие досягли методів криптоанализа, недоступних іншим. 4.4. Я працюю на NSA/DST/других і тому намагаюся переконати громадськість, що 128-битное шифрування надійно. 1. Запровадження 1.1. Що таке біт?

Бит є фундаментальної одиницею інформації. Він може приймати значення 0 чи 1. Протягом сорока останніх комп’ютери працюють із бінарними даними, тобто із наборами бітов (а чи не з цифрами від 0 до 9, як це заведено люди; можна сказати, що комп’ютери мають лише 2 пальця). Біти дозволяють кодувати цілі числа, символи, тощо. Уся інформація, через комп’ютер, перетворюється на біти.

8 біт утворюють байт; це справді дає 256 комбінацій і дозволяє кодувати числа від 0 до 255 чи символи (включаючи відмінність між прописними і рядковими літерами, символи з надстрочными знаками та інші).

1024 байта утворюють один кілобайтів (кБ). 1024 використовується замість 1000 оскільки 1024 є ступенем числа 2, тобто «круглим «числом, якщо працювати по підставі 2. 1024 кілобайта утворюють мегабайт (МБ), чи 1 048 576 байт. 1024 мегабайта утворюють гігабайтів (держбезпеки), чи 1 073 741 824 байта. 1024 держбезпеки утворюють терабайт (ТБ). Подальше множення малоупотребительно, т.к. дорога від усіх точок зору. Типова ємність жорстких дисків дуже поширених в час комп’ютерів становить десять гігабайтів. Розвинена мережу може пропускати десять мегабайтів в секунду між двома машинами.

1.2. Що таке криптографічний ключ?

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

Действительно, зберігати таємно алгоритм проблематично, та, крім того, необхідна чисельна оцінка його безпеки. Сам факт публікації алгоритму дозволяє «безплатно «здобути визнання його надійності криптографічним співтовариством.

Ключ, в такий спосіб, є концентрацією секрету, цей набір бітов є «есенцією «конфіденційності.

1.3. Що таке повний перебір?

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

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

С погляду статистики, треба перебрати приблизно половину можливих ключів, як знайдеться правильний. Якщо довжина ключа становить 56 бітов, це, що у середньому необхідно провести 2⁵⁵ ітерацій, що становитиме 36 028 797 018 963 968.

1.4. Чи є повний перебір єдино можливим методом криптоанализа?

Нет. А інші методи сильно залежить від конкретного алгоритму. Деякі, такі як лінійний чи диференціальний криптоанализ, вимагають величезної кількості пар открытый/зашифрованный текст, представляючи, в такий спосіб, суто теоретичне інтерес.

Кроме того, існують криптосистемы (зокрема, системи асиметричні, звані ще «системами з відкритою ключем »), яким усе поєднання бітов не утворюють правильного ключа. Типовий приклад — RSA, де ключ представлений великою кількістю, отриманими із двох великих простих чисел. Сукупність наборів з 1024 біт, що є двоичной записом цих чисел, набагато менше 2^1024. Повний перебір абсурдний у разі.

1.5. 128-битный ключ вдвічі сталіший до злому, ніж 64-битный?

НЕТ! Це помилка. Кожен додатковий біт подвоює кількість можливих ключів та експлуатаційні витрати на повний перебір. Ключ довжиною 128 біт в 18 446 744 073 709 551 616 раз складнішим для добору, проти ключем довжиною 64 біта (які вже назвати не можна зовсім легким).

1.6. PGP має бути дуже стійкий, оскільки використовує ключі 1024 біта.

Стоп! Спробуймо розібратися! «1024 біт «в PGP — це ключ RSA чи DSS, тобто ключ асиметричного алгоритму. Атака методом повного перебору не самий найкращий варіант у разі.

Кроме того, асиметричні алгоритми щодо повільні, і «всередині «PGP використовує симетричний алгоритм (історично IDEA, потім CAST) розмір ключа якого складають 128 бит.

2. Поточне стан справ 2.1. Яка максимальна довжина ключа для симетричних криптосистем, яка піддається програмному злому методом повного перебору?

Известно, що дві ключа по 56 біт було повним перебором на звичайних комп’ютерах типу PC. Спеціалізована машина (побудована EFF) допомогла для другого ключа, виконавши приблизно третину загального обсягу обчислень.

Ключи для алгоритму DES. Якісний ПК чи робоча станція можуть перебирати з максимальною швидкістю мільйонів ключів в секунду. Якщо прийняти середню швидкість 1 млн ключів в секунду на машину, то то зрозуміло, що з добору ключа 10 000 машин мають у середньому затратити 42 дня.

Полный перебір ключа довжиною 64 біта для RC5 (котрій складність повного перебору трохи вища, ніж для DES) нині триває, і буде тривати, по крайнього заходу, ще кілька років. Нагадуємо, що добір ключа розміром 64 біта, в 256 раз більш трудомістким, ніж добір ключа довжиною 56 бит.

2.2. І це, з допомогою спеціальної апаратури?

Американская група EFF, інвестувала 250 000 $ для створення спеціалізованої машини під назвою «Deep crack «(«глибокий зламування »), котра може перебрати все ключі алгоритму DES приблизно три дні. У ній використано спеціалізовані процесори, які неможливо застосувати з метою, відмінних зламування DES (зокрема, вона нічого «не знають «про RC5).

Все інші машини тієї самої роду — в галузі чуток. DES використовується вже з більш 20 років, і можна припустити, що, мабуть, машині EFF передували інші прототипи, розроблювані секретними службами. У кожному разі, скоро уже виповнилося 15 років його періодично згадуються принципи побудови такий машини.

2.3. Щодо несиметричних криптосистем?

В принципі, є дві математичні завдання, використовувані в асиметричних шифрах: факторизация і дискретне логарифмирование. RSA використовує першу, DSS другу. Інші згадувані завдання (варіації попередніх, використання еліптичних кривих, завдання про укладанні ранця, мінімізація мережі (завдання комівояжера), зворотне розпізнавання (permuted perceptrons problem — див. примітки) щодо рідко використовують у справжнє час.

Рекорд факторизации датується 22-ым серпня 1999: число розміром 155 десяткових цифр (512 біт) було факторизовано шість місяців обчислень на парку приблизно з 600 машин, деякі з них може бути квалифицированны як «бики «(зокрема Cray з 2 держбезпеки пам’яті). Застосовані алгоритми значно більше складні, ніж повний перебір, і потребують великої кількості оперативної пам’яті із хорошою швидкістю доступу.

Дискретное логарифмирование менш досліджувана, з його зламування здійснено менше інвестицій, ніж факторизацию. Рекорд — порядку 95 десяткових цифр.

2.4. Що щодо «кавника «Шаміра?

Представленный на Eurocrypt «99 у Празі (початку травня 1999), цей апарат прискорює фізичними засобами дослідження гладких чисел (тобто отриманих твором лише маленьких простих чисел), які отримують зазвичай методом решета. Ці числа є основою кількох алгоритмів факторизации і рішень завдання дискретного логарифмирования.

Сам апарат ще побудований, описані лише його принципи. Існують технічні проблеми для реалізації прототипу (Arjen Lenstra висловив деякі заперечення, із якими Adi Shamir погодився).

По якоїсь спільної думки, його дозволило б факторизовать число приблизно 600 біт, із засобами, що дозволило встановити рекорд в 465 біт (в лютому 1999), коли всі проблеми у реалізації вирішені. Відзначено, що решето зайняло приблизно 60% часу для рекорду в 512 біт.

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

3. Те, що можливим у майбутньому 3.1. Що таке закон Мура?

Закон Мура (Moore) є оцінкою розвитку обчислювальної техніки у часі. У базовому варіанті він говорить, що з заданої вартості (у широкому сенсі, включаючи енергоспоживання, виробництво устаткування, знос, вартість зберігання, тощо.) обчислювальна потужність збільшується увосьмеро кожні 3 року. Говорячи точніше, можна сказати, що за щотри року, технологічні досягнення дозволяють в 4 рази більше логічних елементів в мікросхемі заданої вартості, одночасно прискорюючи її швидкодія вдвічі.

Этот закон чудово підтверджувався впродовж останніх 15 років. Слід зазначити, що центральні мікропроцесори комп’ютерів загального призначення не повністю йдуть цим законом, оскільки вони можуть як і швидко збільшити розмір шини даних (з міркувань зворотної сумісності коду, і навіть оскільки обчислення, що ці процесори зазвичай виробляють, мають додаткових обмежень, які роблять непотрібним використання дуже великих регістрів).

Это стосується, в такий спосіб, систем, описуваних в термінах логічних елементів, спеціалізованих на конкретному алгоритмі. Отже, це з суті ASIC (Application Specific Integrated Circuit — спеціалізовані мікросхеми) і FPGA (Field Programmable Gate Arrays — программируемые логічні інтегральні схеми); тобто перепрограммируемые ланцюга, виконують такі завдання, як і ASIC, але вдвічі дорожчі при заданої потужності, проте є багатоцільовими).

3.2. Яка гадана вартість повного перебору з допомогою спеціалізованого устаткування?

Если закон Мура продовжуватиме виконуватися (і є вагомих підстав щодо зворотного, оскільки враховуючи якісні досягнення, Не тільки збільшення точності обробки кремнію), можна досягнути машини EFF (чверть мільйони доларів, для 56 біт за 3 дня) і додавати 3 біта кожні 3 року (3 біта = 2³ = 8; що дозволяє увосьмеро більше можливих варіантів ключів).

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

Таким чином, вважатимуться, підібрати повним перебором 128-битный ключ як і «легко », як тепер 56-битный, можна буде через 72 року. Ця оцінка є «найкращою », тоді як багато дослідників цієї тематики вважають, що довгоочікуваний Закон Мура виконуватиметься у разі ще кілька років (справді, все якісних змін, привнесені за останніх 15 років, були просто нереалізованими, відомими з 1975 року, та його запас майже вичерпаний нині).

3.3. А використанням квантових комп’ютерів?

Квантовые комп’ютери, реалізовані через суперпозицію станів однієї частки, є як потужної обчислювальної моделлю, ніж машина Тьюринга і дозволяють здійснити багато операцій (серед яких повний перебір ключів такого «безмежного «алгоритму, як DES) за субэкспоненциальное час.

Квантовые комп’ютери дуже привабливі, але вони існують. Побудували двухбитовый квантовий регістр, але є досить потужні перепони на шляху побудови машини, здатної зламати DES (переважно, ініціалізація цього монстра, вона може бути распараллелена, і, в такий спосіб, 2^n операцій для ключа n бітов).

Это немає великого значення іншому типу квантову криптографію, який є для «неперехватываемой «передачі по оптоволокну (використовуючи принцип невизначеності Гейзенберга).

4. Різні чутки 4.1. NSA/DST/другие можуть ламати ключі до 128 біт.

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

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

Некоторые легко маніпулюють кількістю бітов, легко відносячи 20 біт використання надпровідників чи оптичних елементів, 20 інших на застосування суперэффективных алгоритмів, і 30 останніх оскільки «то це вже трохи «(так, просто помножимо на 1 мільярд, ця справді «трохи »).

Напомню, що кількість бітов експоненціально. Це означає, що видатки перебір кожних n бітов пропорційні 2^n. Щоб це були легше уявити, нагадаємо, що:

64 біта: 18 446 744 073 709 551 616 можливих ключів 128 біт: 340 282 366 920 938 463 463 374 607 431 768 211 456 можливих ключів 256 біт: 115 792 089 237 316 195 423 570 985 008 687 907 853 269 984 665 640 564 039 457 584 007 913 129 639 936 можливих ключів 4.2. NSA/DST/другие мають квантовими комп’ютерами.

Очень малоймовірно. Якщо так, то технологічні досягнення випереджають всіх, як мінімум, років на 10. Інакше кажучи, вони мали б тоді такий просунутої технологією, що саме ідея подальшої боротьби було б абсурдом.

Некоторые згадують можливість отримання позаземної технології, або через Людей в Чорному, або безпосередньо через Phil Zimmerman, їх посла в цій планеті. Як вважають інші джерела, квантовим комп’ютером мала цивілізація Атлантів (звісно, Атлантида було затоплено саме внаслідок перебору ключа «класичними «методами, див. вище).

Сталкиваясь із будь-якими проявами абсурду, і дилетантства у цій галузі, хочеться порадити триматися подалі від такого роду спекуляцій, ніж матиму вигляд клоуна. Якщо хочеться оцінити що можуть зробити NSA, треба дати їй 3 року часу у відповідно до закону Мура і добрий бюджет. Це дозволить зробити завдання за 64 бітами розв’язуваної. 80 біт залишаться недосяжними.

4.3. NSA/DST/другие досягли методів криптоанализа, недоступних іншим.

NSA (від імені Don Coppersmith) оголосив 1987 року, що знали вже у 1977 про диференціальному криптоанализе, оприлюдненому Бихамом і Шамиром (E. Biham, A. Shamir) саме тут 1987 року. Алгоритм DES, розроблений 1977, спеціально захищений від такої атаки.

Тем щонайменше, уточнимо, що ця атака вимагає величезної кількості пар открытый/зашифрованный текст, і у будь-якому разі, нереальна. З іншого боку, DES не був захищений проти лінійного криптоанализа, відкритого в 1993 Matsui, що обмежує наукову перевагу NSA 15 роками. Нарешті, цей останній засіб криптоанализа також нереальний, т.к. вимагає 64 ТБ відомого відкритого тексту, що у кілька десятків мільйонів разів перевищує обсяг Біблії.

Подобные чутки ходили також про факторизацию, дискретне логарифмирование і засоби від прищів. Легко можна зустріти такі чутки згадках про міжнародних змовах лиходіїв, які хочуть знати все про у світі.

В будь-якому разі, з певного моменту, набагато дешевше встановити відеокамеру у вашій офісі, ніж змушувати «молотити «квантовий комп’ютер. Чи знаєте Ви, що відновлення зображення Вашого монітора можливе з дистанції 100 метрів? Це ж стосується й сигналів клавіатури, коли ви друкуєте. Треба мати добре спроектированную сітку Фарадея, щоб захищатися від рівня цього. Шифрування дозволяє визначити захищений канал між двома точками, але з захищає самі точки.

4.4. Я працюю на NSA/DST/других і тому намагаюся переконати громадськість, що 128-битное шифрування надійно.

Niark niark niark. Я ошуканець, правда?

© Автор: Thomas Pornin ([email protected]); оригінал: internet.

(c)Владислав Мяснянкин, переклад російською язык.

Примітки перекладача. Будь ласка, не надсилайте мені замечания/комментарии за змістом документа. Я перевів його. Пишіть безпосередньо автору (на французькому чи англійській) — адресу в заголовку. EFF — Electronic Frontier Foundation internet NSA — National Security Agency internet DST — Direction de la Sйcuritй du Territoire internet Не знайшов російського терміна для «Permuted Perceptrons Problem «і перевів як «завдання зворотного розпізнавання ». Якщо є правильніший переклад — ж охоче почути. Що це таке можна подивитися наприклад на internet (англійською). Якщо ви хоч знайдете неточності у вживанні термінів чи запропонуйте більш «благозвучний «варіант їх перекладу, це завжди буде сприйнято з вдячністю. Неконструктивна критика і флейм погодяться витримувати /dev/null.