IDEA (шифр): відмінності між версіями
[перевірена версія] | [перевірена версія] |
мНемає опису редагування |
Іванко1 (обговорення | внесок) м →Криптостойкость: replaced: до теперішнього часу → досі за допомогою AWB |
||
Рядок 418: | Рядок 418: | ||
[[Файл:PES IDEA.png|міні|ліворуч|200пкс| Структури алгоритмів PES і IDEA]] |
[[Файл:PES IDEA.png|міні|ліворуч|200пкс| Структури алгоритмів PES і IDEA]] |
||
У тій же книзі, що вийшла в [[1996]] року, Брюс Шнайер відгукнувся про IDEA так: «Мені здається, це найкращий і надійний блоковий алгоритм, опублікований |
У тій же книзі, що вийшла в [[1996]] року, Брюс Шнайер відгукнувся про IDEA так: «Мені здається, це найкращий і надійний блоковий алгоритм, опублікований дотепер». |
||
В алгоритмі IDEA використовує 64-бітові блоки. Довжина блоку повинна бути достатньою, щоб приховати статистичні характеристики вихідного повідомлення. Але зі збільшенням розміру блоку експоненціально зростає складність реалізації криптографічного алгоритму. В алгоритмі IDEA використовується 128-бітний ключ. Довжина ключа повинна бути досить великою, щоб запобігти можливості перебору ключа. Для розкриття 128-бітного ключа повним перебором ключів за умови, що відомий відкритий і відповідний йому зашифрований текст, потрібно <math> 2 ^ {128} </math> (порядку <math> 10 ^ {38} </math>) шифрування . При такій довжині ключа IDEA вважається досить безпечним. Висока крипостійкість IDEA забезпечується також такими характеристиками: |
В алгоритмі IDEA використовує 64-бітові блоки. Довжина блоку повинна бути достатньою, щоб приховати статистичні характеристики вихідного повідомлення. Але зі збільшенням розміру блоку експоненціально зростає складність реалізації криптографічного алгоритму. В алгоритмі IDEA використовується 128-бітний ключ. Довжина ключа повинна бути досить великою, щоб запобігти можливості перебору ключа. Для розкриття 128-бітного ключа повним перебором ключів за умови, що відомий відкритий і відповідний йому зашифрований текст, потрібно <math> 2 ^ {128} </math> (порядку <math> 10 ^ {38} </math>) шифрування . При такій довжині ключа IDEA вважається досить безпечним. Висока крипостійкість IDEA забезпечується також такими характеристиками: |
Версія за 19:22, 10 листопада 2012
Розробники | Швейцарська фірма Ascom |
---|---|
Уперше оприлюднений | 1991 р. |
Раундів | 8,5 |
Тип | модифікована мережа Фейстеля |
IDEA (англ. International Data Encryption Algorithm, міжнародний алгоритм шифрування даних) — симетричний блочний алгоритм шифрування даних, запатентований швейцарською фірмою Ascom. Відомий тим, що застосовувався в пакеті програм шифрування PGP. У листопаді 2000року IDEA був представлений в якості кандидата в проекті NESSIE в рамках програми Європейської комісії IST (англ. Information Societes Technology, інформаційні громадські технології).
Історія
Першу версію алгоритму розробили в 1990році Лай Сюецзя (Xuejia Lai) і Джеймс Мессі (James Massey) зі Швейцарського інституту ETH Zürich (за контрактом з Hasler Foundation, яка пізніше влилася в Ascom-Tech AG) в якості заміни DES (англ. Data Encryption Standard, стандарт шифрування даних) і назвали її PES (англ. Proposed Encryption Standard, запропонований стандарт шифрування). Потім, після публікації робіт Біхамом і Шаміра по диференціальному криптоанализу PES, алгоритм був поліпшений з метою посилення криптостійкості і названий IPES (англ. Improved Proposed Encryption Standard, покращений запропонований стандарт шифрування). Через рік його перейменували в IDEA (англ. International Data Encryption Algorythm).
Опис
Так як IDEA використовує 128-бітний ключ і 64-бітний розмір блоку, відкритий текст розбивається на блоки по 64 біт. Якщо таке розбиття неможливо, останній блок доповнюється різними способами певною послідовністю біт. Для уникнення витоку інформації про кожному окремому блоці використовуються різні режими шифрування. Кожен вихідний незашифрований 64 — біт ний блок ділиться на чотири подблока по 16 біт кожен, так як всі алгебраїчні операції, що використовуються в процесі шифрування, відбуваються над 16-бітними числами. Для шифрування і розшифрування IDEA використовує один і той же алгоритм.
Фундаментальним нововведенням в алгоритмі є використання операцій з різних алгебраїчних груп, а саме:
- Додавання по модулю
- Множення по модулю
- Побітове виключає АБО (XOR).
Ці три операції несумісні в тому сенсі, що:
- Ніякі дві з них не задовольняють дистрибутивному закону, тобто
- Ніякі дві з них не задовольняють асоціативному закону, тобто
Застосування цих трьох операцій ускладнює криптоаналіз IDEA в порівнянні з DES, який базується виключно на операції виключає АБО, а також дозволяє відмовитися від використання S-блоків і таблиць заміни. IDEA є модифікацією мережі Фейстел.
Генерація ключів
З 128-бітного ключа для кожного з восьми раундів шифрування генерується по шість 16-бітних подключів, а для вихідного перетворення генерується чотири 16-бітних підключа. Всього буде потрібно 52 = 8 x 6 + 4 різних подключів по 16 біт кожен. Процес генерації п'ятдесяти двох 16-бітних ключів полягає в наступному:
- Насамперед, 128-бітний ключ розбивається на вісім 16-бітних блоків. Це будуть перші вісім подключів по 16 біт кожен —
- Потім цей 128-бітний ключ циклічно зсувається вліво на 25 позицій, після чого новий 128-бітний блок знову розбивається на вісім 16-бітних блоків. Це вже наступні вісім подключів по 16 біт кожен —
- Процедура циклічного зсуву і розбивки на блоки триває до тих пір, поки не будуть згенеровані всі 52 16-бітних підключа.
Номер раунда | Підключі |
---|---|
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
выходное преобразование |
Структура алгоритму IDEA показана на малюнку. Процес шифрування складається з восьми однакових раундів шифрування і одного вихідного перетворення. Вихідний незашифрований текст ділиться на блоки по 64 біта. Кожен такий блок ділиться на чотири підблока по 16 біт кожен. На малюнку ці підблоки позначені , , , . У кожному раунді використовуються свої підключі згідно з таблицею підключів. Над 16-бітними підключами і підблока незашифрованого тексту проводяться наступні операції:
- Множення по модулю = 65537, причому замість нуля використовується
- Додавання по модулю
- Побітове виключає АБО
В кінці кожного раунду шифрування є чотири 16-бітних підблока, які потім використовуються як вхідні підблоки для наступного раунду шифрування. Вихідна перетворення являє собою скорочений раунд, а саме, чотири 16-бітних подблока на виході восьмого раунду і чотири відповідних підключа піддаються операціям:
- Множення по модулю
- Додавання по модулю
Після виконання вихідного перетворення конкатенація підблоків , , і представляє собою зашифрований текст. Потім береться наступний 64-бітний блок незашифрованого тексту і алгоритм шифрування повторюється. Так продовжується до тих пір, поки не зашифрують всі 64-бітові блоки вихідного тексту.
Математичний опис
- Блок відкритого тексту розміром 64 біт ділиться на чотири рівні подблока розміром по 16 біт
- Для кожного раунду обчислюються:
Результатом виконання восьми раундів будуть наступні чотири подблока
- Виконується вихідна перетворення :
Результатом виконання вихідного перетворення є зашифрований текст
Розшифровка
Метод обчислення, що використовується для розшифровки тексту по суті такий же, як і при його шифруванні. Єдина відмінність полягає в тому, що для розшифровки використовуються інші підключі. У процесі розшифровки підключі повинні використовуватися у зворотному порядку. Перший і четвертий підключі i-го раунду розшифровки виходять з першого і четвертого підключа (10-i)-го раунду шифрування мультиплікативною інверсією. Для 1-го та 9-го раундів другий і третій підключи розшифровки виходять з другого і третього подключів 9-го і 1-го раундів шифрування аддитивною інверсією. Для раундів з 2-го по 8-й другий і третій підключі розшифровки виходять з третього і другого подключів з 8-го по 2-й раундів шифрування аддитивною інверсією. Останні два підключа i-го раунду розшифровки рівні останніх двох підключів (9-i)-го раунду шифрування. Мультиплікативна інверсія підключа K позначається 1 / K і . Так як — просте число, кожне ціле не дорівнює нулю K має унікальну мультипликативну інверсію по модулю . Адитивна інверсія підключа K позначається-K і .
Номер раунда | Підключі |
---|---|
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
вихідне перетворення |
Приклад
Для зручності числа представляємо в шістнадцятковому вигляді.
Приклад шифрування
В якості 128-бітного ключа використовуємо K = (0001,0002,0003,0004,0005,0006,0007,0008), а в якості 64-бітного відкритого тексту M = (0000,0001, 0002,0003)
Раунд | Раундові ключі | Значення блоків даних | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
— | — | — | — | — | — | - | 0000 | 0001 | 0002 | 0003 |
1 | 0001 | 0002 | 0003 | 0004 | 0005 | 0006 | 00f0 | 00f5 | 010a | 0105 |
2 | 0007 | 0008 | 0400 | 0600 | 0800 | 0a00 | 222f | 21b5 | f45e | e959 |
3 | 0c00 | 0e00 | 1000 | 0200 | 0010 | 0014 | 0f86 | 39be | 8ee8 | 1173 |
4 | 0018 | 001c | 0020 | 0004 | 0008 | 000c | 57df | ac58 | c65b | ba4d |
5 | 2800 | 3000 | 3800 | 4000 | 0800 | 1000 | 8e81 | ba9c | f77f | 3a4a |
6 | 1800 | 2000 | 0070 | 0080 | 0010 | 0020 | 6942 | 9409 | e21b | 1c64 |
7 | 0030 | 0040 | 0050 | 0060 | 0000 | 2000 | 99d0 | c7f6 | 5331 | 620e |
8 | 4000 | 6000 | 8000 | a000 | c000 | e001 | 0a24 | 0098 | ec6b | 4925 |
9 | 0080 | 00c0 | 0100 | 0140 | - | - | 11fb | ed2b | 0198 | 6de5 |
Приклад розшифровки
В якості 128-бітного ключа використовуємо K = (0001,0002,0003,0004,0005,0006,0007,0008), а в якості 64-бітного зашифрованого тексту C = (11fb, ed2b, 0198,6 de5)
Раунд | Раундові ключі | Значення блоків даних | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
1 | fe01 | ff40 | ff00 | 659a | c000 | e001 | d98d | d331 | 27f6 | 82b8 |
2 | fffd | 8000 | a000 | cccc | 0000 | 2000 | bc4d | e26b | 9449 | a576 |
3 | a556 | ffb0 | ffc0 | 52ab | 0010 | 0020 | 0aa4 | f7ef | da9c | 24e3 |
4 | 554b | ff90 | e000 | fe01 | 0800 | 1000 | ca46 | fe5b | dc58 | 116d |
5 | 332d | c800 | d000 | fffd | 0008 | 000c | 748f | 8f08 | 39da | 45cc |
6 | 4aab | ffe0 | ffe4 | c001 | 0010 | 0014 | 3266 | 045e | 2fb5 | b02e |
7 | aa96 | f000 | f200 | ff81 | 0800 | 0a00 | 0690 | 050a | 00fd | 1dfa |
8 | 4925 | fc00 | fff8 | 552b | 0005 | 0006 | 0000 | 0005 | 0003 | 000c |
9 | 0001 | fffe | fffd | c001 | - | - | 0000 | 0001 | 0002 | 0003 |
Апаратна реалізація
Апаратна реалізація має перед програмної наступні переваги:
- Істотне підвищення швидкості шифрування за рахунок використання паралелізму при виконанні операцій
- Менше енергоспоживання
Перша реалізація алгоритму IDEA на інтегральній схемі (англ. Very Large Scale Integration) була розроблена і верифікована Лаем, Мессі і Мерфі в 1992 рік у з використанням технологічного процесу 1,5 мкм і технології КМОП Швидкість шифрування даного пристрою складала 44 Мб / сек.
В 1994 рік у Карігером, Бонненбергом, Зіммерманом та ін було розроблено пристрій VINCI. Швидкість шифрування даної реалізації IDEA становила 177 Мб / сек при тактовій частоті 25 МГц, техпроцес 1,2 мкм. Це було перше напівпровідниковий пристрій, який вже могло застосовуватися для шифрування в реальному часі в таких високошвидкісних мережних протоколах, як ATM (англ. Asynchronous Transfer Mode, асинхронний спосіб передачі даних) або FDDI (англ. Fiber Distributed Data Interface, розподілений волоконний інтерфейс даних). Швидкість 177 Мб / сек була досягнута завдяки використанню досить витонченої схеми конвеєр ної обробки і чотирьох звичайних помножувачів по модулю . У пристрої також використовуються два односпрямованих високошвидкісних 16-бітних порту даних. Ці порти забезпечують постійну завантаженість блоків шифрування.
Криптостойкость
Алгоритм IDEA з'явився в результаті незначних модифікацій алгоритму PES. На малюнку наведено структури обох алгоритмів, і видно, що змін не так вже й багато:
- Множення подблока з другим підключимо раунду замінено складанням
- Складання подблока з четвертим підключимо раунду замінено на множення
- Змінений зрушення подблоков в кінці раунду
Один з найбільш відомих у світі криптологів Брюс Шнайер у своїй книзі «Прикладна криптографія» зауважив: «… дивно, як такі незначні зміни можуть привести до настільки великим відмінностей».
У тій же книзі, що вийшла в 1996 року, Брюс Шнайер відгукнувся про IDEA так: «Мені здається, це найкращий і надійний блоковий алгоритм, опублікований дотепер».
В алгоритмі IDEA використовує 64-бітові блоки. Довжина блоку повинна бути достатньою, щоб приховати статистичні характеристики вихідного повідомлення. Але зі збільшенням розміру блоку експоненціально зростає складність реалізації криптографічного алгоритму. В алгоритмі IDEA використовується 128-бітний ключ. Довжина ключа повинна бути досить великою, щоб запобігти можливості перебору ключа. Для розкриття 128-бітного ключа повним перебором ключів за умови, що відомий відкритий і відповідний йому зашифрований текст, потрібно (порядку ) шифрування . При такій довжині ключа IDEA вважається досить безпечним. Висока крипостійкість IDEA забезпечується також такими характеристиками:
- Заплутування — шифрування залежить від ключа складним і заплутаним чином
- Розсіювання — кожен біт незашифрованого тексту впливає на кожен біт зашифрованого тексту
Лай Сюецзя (Xuejia Lai) і Джеймс Мессі (James Massey) провели ретельний аналіз IDEA з метою з'ясування його криптостойкости до диференціальному криптоанализу . Для цього ними було введено поняття марківського шифру і продемонстровано, що стійкість до диференціального криптоаналізу може бути промодельована і оцінена кількісно. Лінійних або алгебраїчних слабкостей у IDEA виявлено не було. Спроба взлому за допомогою криптоаналізу з пов'язаними ключами, проведена Біхамом (Biham), також не увінчалася успіхом[1].
Існують успішні атаки, що застосовуються до IDEA з меншим числом раундів (повний IDEA має 8.5 раундів). Успішною вважається атака, якщо взлом шифру з її допомогою вимагає меншої кількості операцій, ніж при повному переборі ключів. Метод розкриття Віллі Майера (Willi Meier) виявився ефективніше взлому повним перебором ключів тільки для IDEA з 2 раундами
Методом «зустріч посередині» був взломаний IDEA з 4,5 раундами. Для цього потрібне знання всіх блоків відкритих текстів і складність аналізу становить операцій. Краща атака на 2007 рік застосовна до всіх ключам і може зламати IDEA з 6-ма раундами.
Слабкі ключі
Існують великі класи слабких ключів. Слабкі вони в тому сенсі, що існують процедури, що дозволяють визначити, чи відноситься ключ до даного класу, а потім і сам ключ. В даний час відомі наступні:
- слабких до диференціальному криптоанализу ключів. Приналежність до класу можна обчислити за операцій за допомогою підібраного відкритого тексту. Автори даної атаки запропонували модифікацію алгоритму IDEA. Дана модифікація полягає в заміні подключів на відповідні , де r — номер раунду шифрування. Точне значення a не критично. Наприклад при (в шістнадцятковій системі числення) дані слабкі ключі виключаються.
- слабких до лінійного диференціального криптоаналізу ключів. Приналежність до даного класу з'ясовується за допомогою тесту на пов'язаних ключах.
- слабких ключів було знайдено з використанням методу бумеранга (англ. boomerang attack), запропонованого Девідом Вагнером ( David Wagner). Тест на приналежність до даного класу виконується за операцій і потребують елементів пам'яті .
Існування таких великих класів слабких ключів не впливає на практичну крипостійкість алгоритму IDEA, тому що повне число всіх можливих ключів одно .
Примітки
- ↑ E. Biham, personal communication, 1993
Посилання
- RSA FAQ on Block Ciphers (англ.). Процитовано 6 ноября 2008.
- SCAN entry for IDEA (англ.). Архів оригіналу за 28 січня 2012. Процитовано 6 ноября 2008.
- IDEA Applet (нім.). Архів оригіналу за 1 лютого 2012. Процитовано 6 ноября 2008.
- Erläuterung und Schaubild zum Verfahren (нім.). Архів оригіналу за 28 січня 2012. Процитовано 6 ноября 2008.