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

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 біт:

можливих ключів.

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.