Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

RC5


зображення

План:


Введення

RC5 (Ron's Code 5 або Rivest's Cipher 5) - це блоковий шифр, розроблений Роном Рівестом з компанії RSA Security Inc. з перемінним кількістю раундів, довжиною блоку і довжиною ключа. Це розширює сферу використання та спрощує перехід на більш сильний варіант алгоритму.


1. Опис

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

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

Шифрування за алгоритмом RC5 складається з двох етапів. Процедура розширення ключа і безпосередньо шифрування. Для розшифровки виконується спочатку процедура розширення ключа, а потім операції, зворотні процедурі шифрування.


1.1. Параметри

Т.к. алгоритм RC5 має змінні параметри, то для специфікації алгоритму з конкретними параметрами прийнято позначення RC5-W/R/b, де

  • W - половина довжини блоку в бітах, можливі значення 16, 32 і 64. Для ефективної реалізації величину W рекомендують брати рівним машинному слову. Наприклад, для 32-бітових платформ оптимальним буде вибір W = 32, що відповідає розміру блоку 64 біта.
  • R - число раундів, можливі значення від 0 до 255. Збільшення числа раундів забезпечує збільшення рівня безпеки шифру. Так, при R = 0 інформація шифруватися не буде. Також алгоритм RC5 використовує таблицю розширених ключів розміру 2 (R +1) слів, яка виходить з ключа заданого користувачем.
  • b - довжина ключа в байтах, можливі значення від 0 до 255.

1.2. Розширення ключа


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

  • Генерація констант
  • Розбиття ключа на слова
  • Побудова таблиці розширених ключів
  • Перемішування

1.2.1. Генерація констант

Для заданого параметра W генерує дві псевдовипадкові величини використовуючи дві математичні константи: e ( експонента) і f ( Золотий перетин).

~ Q_w \ leftarrow \ textrm {Odd} ((f-2) \ cdot 2 ^ w)
~ P_w \ leftarrow \ textrm {Odd} ((e-1) \ cdot 2 ^ w) ,

де \ Textrm {Odd} () - Це округлення до найближчого непарного цілого.

Для w = 16, 32, 64 вийдуть наступні константи:

  • ~ P_ {16} = \ texttt {1011011111100001} _2 = \ texttt {B7E1} _ {16}
  • ~ Q_ {16} = \ texttt {1001111000110111} _2 = \ texttt {9E37} _ {16}
  • ~ P_ {32} = \ texttt {10110111111000010101000101100011} _2 = \ texttt {B7E15163} _ {16}
  • ~ Q_ {32} = \ texttt {10011110001101110111100110111001} _2 = \ texttt {9E3779B9} _ {16}
  • ~ P_ {64} = \ texttt {B7E151628AED2A6B} _ {16}
  • ~ Q_ {64} = \ texttt {9E3779B97F4A7C15} _ {16}

1.2.2. Розбиття ключа на слова

На цьому етапі відбувається копіювання ключа K_0 \ dots K_ {255} в масив слів L_0 ... L_ {c-1} , Де c = \ mathcal {d} b / u \ mathcal {e} , Де u = W / 8 , Тобто, кількість байт в слові.

Якщо c не кратний W / 8 , То L_i доповнюється нульовими бітами до найближчого більшого розміру c , Кратного W / 8 .

У разі якщо b = c = 0 , То ми встановлюємо значення c = 1 , А L_0 = 0 .


1.2.3. Побудова таблиці розширених ключів

На цьому етапі відбувається побудова таблиці розширених ключів S_0 \ dots S_ {2 * (R +1) - 1} , Яка виконується наступним чином:

S_0 = P_w
S_ {i +1} = S_ {i} + Q_w

1.2.4. Перемішування

Циклічно N раз виконуються наступні дії:

~ G = S_i = (S_i + G + H) \ lll 3
~ H = L_j = (L_j + G + H) \ lll (G + H)
~ I = (i + 1) \ mod (2 (R + 1))
~ J = (j + 1) \ mod c ,

причому G, H, i, j - Тимчасові змінні, початкові значення яких дорівнюють 0. Кількість ітерацій циклу N - Це максимальне з двох значень 3 * c і (3 \ cdot 2 \ cdot (R + 1)) .


1.3. Шифрування


Перед першим раундом виконуються операції накладення розширеного ключа на шіфруемие дані:

~ A = (A + S_0) \; \ bmod \; 2 ^ w
~ B = (B + S_1) \; \ bmod \; 2 ^ w

У кожному раунді виконуються наступні дії:

~ A_ {i +1} = ((A_i \ oplus B_i) \ lll B_i) + S_ {2i}
~ B_ {i +1} = ((B_i \ oplus A_i) \ lll A_i) + S_ {2i +1}

1.4. Розшифровка

Для розшифровки виконуються зворотні операції, тобто в кожному раунді виконуються наступні операції:

~ B_ {i +1} = ((B_i - S_ {2i +1}) \ ggg A_i) \ oplus A_i
~ A_ {i +1} = ((A_i - S_ {2i}) \ ggg B_i) \ oplus B_i

2. Властивості

Алгоритм RC5 володіє наступними властивостями: [1]

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

3. Крипостійкість

RSA витратила багато часу на аналіз його роботи з 64-бітним блоком. Так в період з 1995 по 1998 р. вони опублікували ряд звітів, в яких докладно проаналізували криптостійкість алгоритму RC5. Оцінка для лінійного криптоаналізу показує, що алгоритм безпечний після 6 раундів. Диференціальний криптоаналіз вимагає 2 ^ {24} обраних відкритих текстів для алгоритму з 5 раундами, 2 ^ {45} для 10 раундів, 2 ^ {53} для 12 раундів і 2 ^ {68} для 15 раундів. А так як існує всього лише 2 ^ {64} можливих різних відкритих текстів, то диференціальний криптоаналіз неможливий для алгоритму в 15 і більше раундів. Так що рекомендується використовувати 18-20 раундів, або принаймні не менше 15 замість тих 12 раундів які рекомендував сам Ривест.


3.1. RSA Security Challenge

Для стимуляції вивчення і застосування шифру RC5 RSA Security Inc. 28 січня 1997 запропонувала зламати серію повідомлень, зашифрованих алгоритмом RC5 з різними параметрами, [2] призначивши за злом кожного повідомлення приз в $ 10 000. Шифр з найслабшими параметрами RC5-32/12/5 був зламаний протягом декількох годин. Тим не менше, останній здійснений злом шифру RC5-32/12/8 зажадав уже 5 років обчислень в рамках проекту розподілених обчислень RC5-64 (тут 64 = b 8, довжина ключа в бітах) під керівництвом distributed.net. Як і раніше неприступними поки залишаються RC5-32/12 / b для b від 9 до 16. distributed.net запустив проект RC5-72 для злому RC5-32/12/9, в якому за станом на листопад 2010 року вдалося перебрати 1.2% ключів. [3]

У травні 2007 року RSA Security Inc. оголосила про припинення підтримки змагання та виплати грошової винагороди. Щоб не припиняти проект RC-72, distributed.net вирішила спонсорувати для нього приз в $ 4 000 з власних коштів. [4]


3.2. Атака за часом виконання

На платформах, де операція циклічного зсуву на змінне число бітів виконується за різне число тактів процесора, можлива атака по часу виконання на алгоритм RC5. Два варіанти подібної атаки були сформульовані криптоаналітиків Говардом Хейз і Хеленою Хандшух ( англ. Helena Handschuh ). Вони встановили, що ключ може бути обчислений після виконання близько 220 операцій шифрування з високоточними замірами часу виконання і потім від 228 до 240 пробних операцій шифрування. Найпростіший метод боротьби з подібними атаками - примусове виконання зрушень за постійне число тактів (наприклад, за час виконання самого повільного зсуву).


4. Варіанти алгоритму

Т.к. однією з властивостей RC5 є його простота в реалізації та аналізі, цілком логічно, що багато криптологи [ хто? ] захотіли вдосконалити класичний алгоритм. Загальна структура алгоритму залишалося без змін, змінювалися лише дії виконуються над кожним блоком в процесі безпосередньо шифрування. Так з'явилося кілька різних варіантів цього алгоритму:


4.1. RC5XOR

У цьому алгоритмі додавання з ключем раунду по модулю 2 ^ w замінено операцією XOR:

~ A_ {i +1} = ((A_i \ oplus B_i) \ lll B_i) \ oplus S_ {2i}
~ B_ {i +1} = ((B_i \ oplus A_i) \ lll A_i) \ oplus S_ {2i +1}

Цей алгоритм виявився вразливим до диференціального і лінійному криптоаналіз. Бірюкову і Кушілевіцу вдалося знайти атаку методом диференціального криптоаналізу для алгоритму RC5XOR-32/12/16, використовуючи 228 обраних відкритих текстів.


4.2. RC5P

У цьому алгоритмі складання двох оброблюваних "подблоков" операцією XOR замінено складанням за модулем 2 ^ w :

~ A_ {i +1} = ((A_i + B_i) \ lll B_i) + S_ {2i}
~ B_ {i +1} = ((B_i + A_i) \ lll A_i) + S_ {2i +1}

Цей алгоритм виявився вразливим до диференціального криптоаналізу.

4.3. RC5PFR

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

~ A_ {i +1} = ((A_i \ oplus B_i) \ lll R_i) + S_ {2i}
~ B_ {i +1} = ((B_i \ oplus A_i) \ lll R_i) + S_ {2i +1} ,

де R_i фіксоване число.

Цей алгоритм не досить добре вивчений, проте передбачається, [ ким? ] що він нестійкий до диференціального криптоаналізу.


4.4. RC5KFR

У цьому алгоритмі число біт зсуву залежить від ключа алгоритму і від поточного раунду:

~ A_ {i +1} = ((A_i \ oplus B_i) \ lll R_i (L_i)) + S_ {2i}
~ B_ {i +1} = ((B_i \ oplus A_i) \ lll R_i (L_i)) + S_ {2i +1} ,

Цей алгоритм також не досить добре вивчений.

4.5. RC5RA

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

~ A_ {i +1} = ((A_i \ oplus B_i) \ lll f (L_i)) + S_ {2i}
~ B_ {i +1} = ((B_i \ oplus A_i) \ lll f (L_i)) + S_ {2i +1} ,

Передбачається, [ ким? ] що алгоритм RC5RA ще більш стійкий до відомим методам криптоаналізу, ніж RC5.


Примітки

  1. Rivest, RL (1994). " The RC5 Encryption Algorithm - theory.lcs.mit.edu / ~ rivest/Rivest-rc5rev.pdf "(pdf). Proceedings of the Second International Workshop on Fast Software Encryption (FSE) 1994e: 86-96.
  2. The RSA Laboratories Secret-Key Challenge - www.rsasecurity.com/rsalabs/node.asp?id=2100
  3. RC5-72: Overall project statistics - stats.distributed.net / projects.php? project_id = 8
  4. distributed.net: staff blogs - 2008 - September - 08 - n0cgi.distributed.net/cgi/planarc.cgi? user = bovine & plan = 2008-09-08.02:09

Цей текст може містити помилки.

Схожі роботи | скачати
© Усі права захищені
написати до нас