1. Введення
1.1. Що таке біт?
Біт є фундаментальною одиницею інформації. Він може приймати значення 0
або 1. Протягом останніх сорока років комп'ютери працюють сбінарнимі даними, то
є з наборами бітів (а не з цифрами від 0 до 9, як це прийнято у людей; можна
сказати, що комп'ютери мають тільки два пальці). Бітипозволяют кодувати цілі
числа, символи, тощо. Вся інформація, що проходить через комп'ютер, перетворюється
в біти.
8 біт утворюють байт; це дає 256 комбінацій і дозволяє кодувати числа від 0
до 255 або символи (включаючи різницю між великими і малими літерами, символи
з наголосами та інші).
1024 байти утворюють один кілобайт (КБ). 1024 використовується замість 1000 так як
1024 є ступенем числа 2, то є "круглим" числом, есліработать по
основи 2. 1024 кілобайт утворюють мегабайт (МБ), або 1048576 байт. 1024
мегабайта утворюють гігабайт (ГБ), або 1073741824 байти. 1024 ГБобразуют терабайт
(ТБ). Подальше множення маловживаних, тому що дорогі з усіх точок
зору. Типова ємність жорстких дисків широко поширених внастоящее час
комп'ютерів складає десять гігабайт. Розвинена мережа може пропускати десять
мегабайт за секунду між двома машинами.
1.2. Що таке криптографічний ключ?
Криптографічні операції, такі як шифрування і підписання даних електронної
цифровим підписом, можуть бути здійснені тільки определенниміліцамі,
що володіють деякими секретами. У минулі століття цим секретом був сам спосіб
перетворення даних. Однак більш раціонально і більше
еффектівноконцентріровать цей секрет у вигляді набору бітів, а сам алгоритм робити
загальнодоступним.
Дійсно, зберігати в таємниці алгоритм проблематично, і, крім того,
необхідна чисельна оцінка його безпеки. Сам факт публікації
алгорітмапозволяет "безкоштовно" отримати визнання його надійності
криптографічним спільнотою.
Ключ, таким чином, є концентрацією секрету, цей набір бітів є
"есенцією" конфіденційності.
1.3. Що таке повний перебір?
Зламати криптосистем, значить зуміти здійснити деякі операції, що вимагають
(в теорії) знання секрету (ключа), не маючи інформації про последнем.Наіболее
повним зломом є злом, в результаті якого стає відомий ключ,
що дає зломщикові ті ж повноваження, що й законному владельцуключа.
Повний перебір є найбільш простим методом цієї точки зору: він полягає в
тому, щоб пробувати всі ключі один за одним до тих пір, поки ненайдется
правильний. Цей метод є найбільш загальним, і може бути распараллелен
(обчислення можуть бути розподілені на багато машин). Крім того, він найбільш
реалістичний: якщо розглядати випадок симетричної системи шифрування (яка
ставить у відповідність блоку, що складається з несколькіхбайтов, другой блок тієї ж
довжини, але перетворений до "нечитабельним" виду за допомогою ключа), досить
перехопити пару откритийтекст/зашифрований текст, тобто блок з кілька
байтів і відповідних їм зашифрованих. Наприклад, якщо передається картинка в
форматі JPG, то началосообщенія представляє собою стандартний заголовок JPG,
формат якого всім добре відомий.
З точки зору статистики, треба перебрати приблизно половину можливих ключів,
перш ніж знайдеться правильний. Якщо довжина ключа становить 56 бітів, це
означає, що в середньому необхідно провести 2 ^ 55 ітерацій, що складе
36028797018963968.
1.4. Чи є повний перебір едінственновозможним методом криптоаналізу?
Ні. Але інші методи сильно залежать від конкретного алгоритму. Деякі,
такіекак лінійний або диференціальний криптоаналіз, вимагають величезного числа пар
відкрита/зашифрований текст, уявляючи, таким чином, чисто
теоретіческійінтерес.
Крім того, існують криптосистеми (зокрема, системи асиметричні,
звані ще "системами з відкритим ключем"), для яких всесочетанія бітів не
утворюють правильного ключа. Типовий приклад - RSA, де ключ представлений великим
числом, отриманим з двох великих простих чісел.Совокупность наборів з 1024
біт, які є двійковій записом цих чисел, набагато менше 2 ^ 1024. Повний
перебір абсурдний в цьому випадку.
1.5. 128-бітний ключ в два рази стійкіше квзлому, ніж 64-бітний?
НІ! Це поширена помилка. Кожен додатковий біт подвоює кількість
можливих ключів і витрати на повний перебір. Ключ довжиною 128 бітявляется в
18446744073709551616 разів більш складним для відбору, в порівнянні з ключем довжиною
64 біта (який вже не назвеш зовсім легким).
1.6. PGP має бути дуже стійкий, так какіспользует ключі 1024 біта.
Стоп! Давайте розберемося! "1024 біт" у PGP - це ключ RSA або DSS, то є ключ
асиметричного алгоритму. Атака методом повного перебору НЕ самийлучшій варіант
в цьому випадку.
Крім того, асиметричні алгоритми щодо повільні, і "всередині" PGP
використовує симетричний алгоритм (історично IDEA, потім CAST) розмір ключа
якого становить 128 біт.
2. Поточне положення справ
2.1. Яка максимальна довжина ключа длясімметрічних криптосистем, яка
піддається програмного злому методомполного перебору?
Відомо, що два ключі по 56 біт були підібрані повним перебором на звичайних
комп'ютерах типу PC. Спеціалізована машина (побудована EFF) допомогла
длявторого ключа, виконавши приблизно третина загального обсягу обчислень.
Ключі були для алгоритму DES. Якісний ПК або робоча станція можуть
перебирати з максимальною швидкістю декількох мільйонів ключів в секунду.
Есліпрінять середню швидкість один мільйон ключів в секунду на машину, то легко
бачити, що для підбору ключа 10000 машин повинні в середньому витратити 42 дні.
Повний перебір ключа довжиною 64 біта для RC5 (для якого складність повного
перебору трохи вище, ніж для DES) в даний час продовжується, і
будетдліться, принаймні, ще кількох років. Нагадуємо, що підбір ключа
розміром 64 бита, є в 256 разів більш трудомістким, ніж підбору ключа довжиною
56 біт.
2.2. Те ж, з використанням спеціальнойаппаратури?
Американська група EFF, інвестувала 250000 $ у створення спеціалізованої
машини під назвою "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) є оцінкою розвитку обчислювальної техніки в часі.
У базовому варіанті він говорить, що для заданої вартості (в шірокомсмисле,
включаючи енергоспоживання, виробництво устаткування, знос, вартість зберігання,
і т.д.) обчислювальна потужність збільшується в 8 разів кожні 3 года.Говоря більш
точно, можна сказати, що через кожні три роки, технологічні досягнення
дозволяють розмістити в 4 рази більше логічних елементів вмікросхеме заданої
вартості, одночасно прискорюючи її швидкодію в 2 рази.
Цей закон чудово підтверджувався протягом останніх 15 років. Слід
відзначити, що центральні мікропроцесори комп'ютерів загального призначення
неповністю слідують з цим законом, тому що вони не можуть так само швидко
збільшити розмір шини даних (з міркувань забезпечення сумісності коду, а
такжепотому, що обчислення, які ці процесори зазвичай виробляють, мають
додаткові обмеження, що роблять непотрібним використання занадто
большіхрегістров).
Це стосується, таким чином, систем, що описуються в термінах логічних
елементів, спеціалізованих на конкретному алгоритмі. Таким чином, це посуті
ASIC (Application Specific Integrated Circuit - спеціалізовані мікросхеми) і
FPGA (Field Programmable Gate Arrays - програмовані логіческіеінтегральние
схеми); тобто Перепрограмміруємая ланцюга, що виконують ті ж завдання, що й ASIC,
але удвічі дорожчі при заданій потужності, однакоявляющіеся багатоцільовими).
3.2. Яка передбачувана вартість полногоперебора з використанням
спеціалізованого обладнання?
Якщо закон Мура буде продовжувати виконуватися (і немає вагомих підстав для
зворотного, тому що він враховує якісні досягнення, а не толькоувеліченіе
точності обробки кремнію), можна досягти машини EFF (чверть мільйона
доларів, для 56 біт за 3 дні) і додавати 3 біта кожні 3 роки (3біта = 2 ^ 3 =
8; що дає в 8 разів більше можливих варіантів ключів).
Зауважимо, що для збереження закон Мура, якісні досягнення повинні
відбуватися досить швидко, тому що є межі у збільшенні
плотностіелементов на кристалі кремнію (уповільнення внаслідок тунельного
ефекту). У ряді розроблюваних методів передбачається здійснити заміну
кремнію наарсенід галію, що дозволить досягти більш високої щільності
елементів, заміну алюмінію міддю, яка дозволяє працювати набагато більше
швидко, построеніеоптіческой логіки (оптичний елемент перемикається
приблизно в 100 разів швидше електронного, але його вартість вище більш ніж в
100 разів).
Таким чином, можна вважати, підібрати повним перебором 128-бітний ключ так само
"легко", як зараз 56-бітний, стане можливим через 72 роки. Етаоценка
є "найкращою", у той час як багато дослідників цієї тематики
вважають, що закон Мура буде виконуватися в кращому випадку ещенесколько років
(дійсно, всі якісні зміни, привнесені за останніх 15 років,
були просто нереалізованими, відомими з 1975 року, і іхзапас майже вичерпаний у
теперішній час).
3.3. А з використанням квантовихкомпьютеров?
Квантові комп'ютери, що реалізуються через суперпозицію станів однієї частинки,
є більш потужної обчислювальної моделлю, ніж машина Тьюринга іпозволяют
здійснити багато операцій (серед яких повний перебір ключів такого
"безмежного" алгоритму, як DES) за субекспоненціальное час.
Квантові комп'ютери дуже спокусливі, але вони не існують. Був побудований
двухбітовий квантовий регістр, але є досить мощниепрепятствія для
побудови машини, здатної зламати DES (головним чином, ініціалізація цього
монстра, яка не може бути распараллелена, і займає, таким чином, 2 ^ n
операцій для ключа n бітів).
Це не має великого значення для іншого типу квантової криптографії, який
служить для "неперехвативаемой" надсилання даних оптичні (використовуючи принцип
невизначеності).
4. Різні чутки
4.1. NSA/DST/інші можуть ламати ключі до128 біт.
Є дуже сильні заперечення проти такого роду висловлювань. Серед
класичних можна виділити одне, що припускає наявність процесора
сенергопотребленіем в 10 разів менше, ніж у класичних (таким могли б
мати у своєму розпорядженні секретні служби, які мають перевагу). Енергетичні витрати
наповнений перебір 128-бітного ключа, якщо їх перевести в теплову форму,
змусили б зникнути під водою Нідерланди в результаті танення полярних льодів.
Що стосується 256-бітових ключів, то якщо припустити, що витрати на аналіз
одного ключа рівні енергії переходу електрона з однієї орбіти атома на іншу, то
кількості великодушно надається Сонцем енергії недостатньо для
здійснення такого перебору за розумний час.
Деякі легко маніпулюють кількістю бітів, легко відносячи 20 біт на
використання надпровідників або оптичних елементів, 20 інших напрімененіе
супер-алгоритмів, і 30 останніх тому що "це вже трохи" (так,
просто помножити на 1 мільярд, це дійсно "трохи").
Нагадаю, що число бітів експоненціально. Це означає, що витрати на перебір
кожних n бітів пропорційні 2 ^ n. Щоб це було легше уявити, нагадаємо,
що:
  64 біта: 18446744073709551616 можливих ключів
  128 біт: 340282366920938463463374607431768211456 можливих ключів
  256 біт:
  115792089237316195423570985008687907853269984665640564039457584007913129639936
  можливих ключів
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 (thomas.pornin @ ens.fr); оригінал:
http://www.dmi.ens.fr/ ~ pornin/faq-cle.html
© Владислав Мяснянкина, переклад на російську мову.
Примітки перекладача.
  Будь ласка, не надсилайте мені зауваження/коментарі за змістом документа. Я
  тільки переклав його. Пишіть безпосередньо автору (французькою або
  англійською мовою) - адреса в заголовку.
  EFF - Electronic Frontier Foundation http://www.eff.org/
  NSA - National Security Agency http://www.nsa.gov/
  DST - Direction de la Sйcuritй du Territoire
  http://www.chez.com/icebreaker/dst/
  Я не знайшов російського терміна для "Permuted Perceptrons Problem" і переклав як
  "завдання зворотного розпізнавання". Якщо є більш правильний переклад - буду
  радий почути. Що це таке можна побачити наприклад на
  http://cgi.dmi.ens.fr/cgi-bin/pointche/papers.html?Po95a (англійською).
  Якщо ви знайдете неточності у використанні термінів або запропонуйте більш
  "милозвучна" варіант їх перекладу, це буде сприйнято з вдячністю.
  Неконструктивна критика і флейм підуть на/dev/null.