Перегляд вихідного коду сторінки RC6

{{Картка блочного шифру
|назва         = RC6
|зображення    = RC6 Cryptography Algorithm.JPG
|розробник     = [[RSA]] Laboratories
|створений     = [[1998]] р.
|опублікований = [[1998]] р.
|размір ключа  = 128-2040 [[біт]]
|размір блоку  = 128 [[біт]]
|число раундів = 20
|тип           = [[Мережа Фейстеля]] }}

'''RC6''' — симетричний блоковий [[криптографічний алгоритм]], похідний від алгоритму [[RC5]]. Був створений Роном Рівестом, Меттом Робшау і Реєм Сіднеєм для задоволення вимог конкурсу [[AES (конкурс)|Advanced Encryption Standard]] (AES). Алгоритм був одним з п'яти фіналістів конкурсу, був також представлений NESSIE і CRYPTREC. Є [[Власницьке ПО|власницьким]] (пропрієтарним) алгоритмом, і запатентований RSA Security, одначе дія патентів сплила, і зараз алгоритм знаходиться у відкритому доступі. В той же час, "RC6" залишається зареєстрованою торговою маркою RSA.

Варіант шифру RC6, заявлений на конкурс AES, підтримує блоки довжиною 128 біт і ключі довжиною 128, 192 і 256 біт, але сам алгоритм, як і RC5, може бути налаштований для підтримки більш широкого діапазону довжин як блоків, так і ключів (від 0 до 2040 біт)<ref name="rc6-512">[http://darksoftware.narod.ru/narod_is_best/rc6.zip Вихідні тексти RC6-32/20/64 з ключем 512 біт на мові C]{{Недоступне посилання|date=лютий 2019 |bot=InternetArchiveBot }}</ref>. RC6 дуже схожий на RC5 за своєю структурою і також досить простий у реалізації.

Є фіналістом AES, проте одна з примітивних операцій — операція множення, повільно виконується на певному обладнанні і ускладнює реалізацію шифру на ряді апаратних платформ і, що виявилося сюрпризом для авторів, на системах з архітектурою Intel IA-64 також реалізована досить погано. В даному випадку алгоритм втрачає одну зі своїх ключових переваг — високу швидкість виконання, що стало причиною для критики і однією з перепон для обрання як нового стандарту. Однак, на системах із процесором [[Pentium II]], [[Pentium Pro]], [[Pentium III]], [[PowerPC]] та [[ARM (архітектура)|ARM]] алгоритм RC6 випереджає переможця — [[Rijndael]].<ref name="rc6-aes">[ftp://ftp.rsasecurity.com/pub/rsalabs/rc6/rc6% 2Baes.pdf Порівняння алгоритмів RC6 і AES]{{Недоступне посилання|date=червень 2019 |bot=InternetArchiveBot }}</ref>

== Деталі RC6 ==
Так само, як і [[RC5]], RC6 — повністю параметризована сім'я алгоритмів шифрування. Для специфікації алгоритму з конкретними параметрами, прийнято позначення '''RC6-w/r/b''', де
* W — довжина [[машинне слово|машинного слова]] в [[біт]]ах.
* R — число раундів.
* B — довжина ключа в [[байт]]ах. Можливі значення 0..255 байт.
Для того щоб відповідати вимогам [[Advanced Encryption Standard|AES]], блочний шифр повинен працювати з 128-бітовими блоками. Так як [[RC5]] — виключно швидкий [[блочний шифр]], розширення його, щоб працювати з 128-бітовими блоками, привело б до використання двох 64-бітових робочих регістрів. Але архітектура і мови програмування ще не підтримують 64-бітні операції, тому довелося змінити проект так, щоб використовувати чотири 32-бітних регістри замість двох 64-бітних.

== Розширення ключа ==
'''Генерація констант:'''

Так само, як і в [[RC5]], в RC6 генерує дві псевдовипадкові величини, використовуючи дві математичні константи: [[експонента]] (e) і [[золотий перетин]] (f).

<math> ~ Q_w \leftarrow Odd ((f-1) * 2 ^ w) </math>

<math> ~ P_w \leftarrow Odd ((e-2) * 2 ^ w) </math>,

де <math> ~ Odd () </math> — це округлення до найближчого непарного цілого.
При w = 32 біта (у шістнадцятковому вигляді):

<math> ~ Q_ {32} = 9E3779B9 </math>

<math> ~ P_ {32} = B7E15163 </math>
  
'''Процедура розширення ключа для RC6-w/r/b:'''

Таблиця ключів для шифру RC6 також ідентична таблиці шифру [[RC5]]. Відмінність полягає в тому, що більша кількість слів з масиву L отримано з наданого користувачем ключа для використання протягом шифрування і розшифровки.
  
''Вхід:''
* B-байтний ключ, заданий користувачем, попередньо перетворений в масив з <math> c </math> слів <math> L [0, ..., c-1] </math>.
* R — кількість раундів.
''Вихід:''
* W-бітна таблиця ключів <math> S [0, ..., 2r +3] </math>.
<syntaxhighlight lang="C">

S[0] = Pw 
for i = 1 to 2r +3 do 
    S[i] = S[i-1] + Qw

A = B = i = j = 0

v = 3 * max {c, 2r +4} 
for s = 1 to v do 
    { 
        A = S[i] = (S[i] + A + B) <<< 3 
        B = L[j] = (L[j] + A + B) <<< (A + B) 
        i = (i +1) mod (2r +4) 
        j = (j +1) mod c 
    } 
</syntaxhighlight>

== Шифрування і розшифрування ==
RC6 працює з чотирма w-[[біт]]ними регістрами A, B, C і D, які містять вхідний вихідний текст і вихідний шифрований текст в результаті [[шифрування]].

=== Шифрування / Розшифрування за допомогою RC6-w/r/b ===
'''Процедура шифрування:'''

''Вхід:''
* R кількість раундів
* W-розрядні ключі для кожного раунду S [0, …, 2r + 3]
  
''Вихід:''
* Шифрований текст зберігається в A, B, C і D

<syntaxhighlight lang="C"> 
B = B + S[0] 
D = D + S[1] 
for i = 1 to r do 
{ 
t = (B (2B + 1)) <<< lg w 
u = (D (2D + 1)) <<< lg w 
A = ((A ⊕ t) <<< u) + S[2i] 
C = ((C ⊕ u) <<< t) + S[2i + 1] 
                (A, B, C, D) = (B, C, D, A)

} 
A = A + S[2r + 2] 
C = C + S[2r + 3] 
</syntaxhighlight>

'''Процедура [[розшифрування]]:'''

''Вхід:''
* Шифрований текст, збережений в A, B, C і D
* R кількість раундів
* W-розрядні ключі для кожного раунду S [0, …, 2r + 3]
  
'' Вихід:''
* Вихідний текст зберігається в A, B, C і D

<syntaxhighlight lang="C"> 
C = C - S[2r + 3] 
A = A - S[2r + 2]

for i = r downto 1 do 
{ 
(A, B, C, D) = (D, A, B, C) 
u = (D (2D + 1)) <<< lg w 
t = (B (2B + 1)) <<< lg w 
C = ((C - S[2i + 1]) >>> t) ⊕ u 
A = ((A - S[2i]) >>> u) ⊕ t 
} 
D = D - S[1] 
B = B - S[0] 
</syntaxhighlight>

== Безпека ==
Варіант алгоритму RC6, який був заявлений на [[Advanced Encryption Standard|AES]], як уже було сказано, підтримує блоки довжиною 128 біт і ключі довжиною 128, 192 і 256 біт, а також містить 20 раундів. Тобто RC6-128/20/b, де b = 128,192 або 256 біт. Щодо такого алгоритму ніяких атак не було виявлено. Були виявлені атаки тільки проти спрощених версій алгоритму, тобто алгоритму з зменшеною кількістю раундів.

Вважається, що найкращий варіант нападу на RC6, доступний для криптоаналітика, є повний перебір b-байтового ключа шифрування (або розширений ключовою масив S [0, …, 43], коли наданий користувачем ключ шифрування особливо довгий). Для повного перебору потрібно <math> min (2 ^ {8b}, 2 ^ {1408}) </math> операцій. Дон Копперсміт зауважив, що за рахунок значної пам'яті і попереднього обчислення можна організувати атаку «[[зустріч посередині|meet-in-the-middle]]», щоб відновити розширений ключовою масив S [0, …, 43]. Це вимагало б <math> 2 ^ {704} </math> обчислень і таким чином необхідну кількість операцій дорівнювало <math> min (2 ^ {8b}, 2 ^ {704}) </math>.
Сучасніші атаки, такі як [[диференціальний криптоаналіз|диференційний]] та [[лінійний криптоаналіз]], здійсненні на версіях шифру з маленькою кількістю раундів, складно здійсненні для нападу на повний шифр RC6 з 20 раундами. Складність полягає в тому, що важко знайти хороші повторювані особливості або лінійні наближення, з якими могла б бути здійснена атака.

Цікава проблема — встановити відповідні цілі для безпеки проти цих сучасніших атак. Щоб досягти успіху, ці атаки типово вимагають великої кількості даних, і отримання <math> 2 ^ {a} </math> блоків відомих або обраних пар зашифрованого \ [[відкритий текст|відкритого тексту]] — завдання відмінне від спроби повернути один ключ з <math> 2 ^ {a } </math> можливих. Варто зауважити, що з шифрами, що працюють зі швидкістю один терабіт в секунду (тобто, шифруючи дані зі швидкістю <math> 10 ^ {12} </math> біт / сек), час, необхідний для 50 комп'ютерів, що працюють паралельно, щоб зашифрувати <math> 2 ^ {64} </math> блоків даних, складає більше року; зашифрувати <math> 2 ^ {80} </math> блоків даних — більше ніж 98 000 років, і зашифрувати <math> 2 ^ { 128} </math> блоків даних складає більше ніж <math> 10 ^ {19} </math> років.

Хоча вимоги до даних для <math> 2 ^ {64} </math> блоків для успішної атаки могли б бути розглянуті як достатні в практичних термінах, розробники прагнули забезпечувати набагато більший рівень безпеки.

Дослідження [[RC5]] не проявили слабкостей в установці ключа. Це призвело до використання того ж процесу установки ключа і в RC6. Процес перетворення ключа, наданого користувачем, до таблиці ключів, здається, добре змодельований псевдовипадковий процес. Таким чином, у той час як немає доказів, що ніякі два ключі не призводять до однієї і тієї ж таблиці ключів, це, здається, дуже малоймовірно. Це можна оцінити як імовірність того, що існують два 256-бітових ключа, що призводять до однієї і тієї ж таблиці 44, 32-розрядних ключів, тобто приблизно <math> 2 ^ {2 * 256-44 * 32} = 2 ^ {- 896} = 10 ^ {-270} </math>.

Ми можемо підсумувати наші вимоги на безпеці RC6 наступним чином:

— Найкраща атака на RC6 є повний перебір для забезпеченого користувачем ключа шифрування.

— Вимоги до даних, щоб організувати складніші атаки на RC6, такі як диференційний і лінійний криптоаналіз, перевищують доступні дані.
  
Важливим критерієм резерву безпеки є максимальне число раундів, при якому можлива атака. Це можливо для 12 -, 14 — і 15 — раундових варіантів RC6.

{| class="wikitable"
|-
! Шифр
! Кількість раундів (b)
! Тип атаки
! Текст
! Байти пам'яті
! Операції
|-
|rowspan="3"| RC6-128/20/b
| 12
| Статистичні відмінності
| <math>2^{94}</math>
| <math>2^{42}</math>
| <math>2^{119}</math>
|-
| 14
| Статистичні відмінності
| <math>2^{118}</math>
| <math>2^{112}</math>
| <math>2^{122}</math>
|-
| 15 (256)
| Статистичні відмінності
| <math>2^{119}</math>
| <math>2^{138}</math>
| <math>2^{215}</math>
|}

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

== Оцінка апаратних засобів ==

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

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

З 20 раундами на блок час шифрування приблизно дорівнює 100 наносекунд для кожного блоку, забезпечуючи передбачувану швидкість передачі даних приблизно 1.3 Гбіт / сек.

== Виконання ==

Як випливає з опису алгоритму, RC6 — дуже компактний. Дійсно, реалізація алгоритму RC6 на Асемблері для мікропроцесора Intel Pentium Pro може бути здійснена в менш ніж 256 байтах коду для кожної з задач:
# Установки ключа,
# Блоку шифрування,
# Блоку дешифрування.
На відміну від багатьох інших алгоритмів шифрування RC6 не використовує довідкові таблиці під час шифрування. Це означає, код RC6 і дані можуть міститися в сучасній кеш пам'яті і тим самим економити місце в пам'яті.

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

== Гнучкість та напрямки розвитку ==

Як ми вже помітили, RC6 надає користувачеві велику гнучкість щодо розміру ключа шифрування, числа раундів і розміру слова основного обчислювального модуля.

У той час як RC6, представлений для розгляду на AES, базується на використання 32-розрядних слів (розмір блоку 128 біт), майбутня потреба ринку потребує розширення RC6 для інших розмірів блоку. Найбільшу важливість представляють розміри блоку в 256 біт, які використовували б розмір слова 64 біт і продуктивність, пропоновану наступним поколінням системної архітектури.
Також зазначимо, що структура RC6 дозволяє експлуатувати певний ступінь паралелізму в підпрограмах розшифровки і шифрування. Наприклад, обчислення t і u в кожному раунді може бути обчислено паралельно, як і поновлення A і C. Оскільки процесори розвиваються в напрямку збільшення кількості внутрішнього паралелізму (наприклад, з переміщенням до суперскалярної архітектурі), реалізації RC6 повинні продемонструвати велику продуктивність.

== Ліцензування ==
Оскільки RC6 не був обраний як [[Advanced Encryption Standard|AES]], то немає гарантій, що його використання є вільним. З січня 2007 вебсторінка<ref>[https://web.archive.org/web/20061229220543/http://www.rsasecurity.com/rsalabs/node.asp?id=2251 rsasecurity.com]</ref> офіційного сайту RSA Laboratories, розробника RC6, містить наступне:

: «We emphasize that ''if'' RC6 is selected for the AES, RSA Security will ''not'' require any licensing or royalty payments for products using the algorithm» ("Ми підкреслюємо, що ''якщо'' RC6 буде обраний як AES, то RSA Security ''не'' вимагатиме жодних ліцензійних чи авторських відрахувань за продукти, що використовують алгоритм").

Виділене слово «якщо» означає, що RSA Security Inc. тепер може вимагати ліцензійні та авторські платежі за будь-який продукт, який використовує алгоритм RC6. RC6 є запатентованим алгоритмом шифрування ({{US patent | 5724428}} і {{US patent | 5835600}}).

== Джерела ==
* R.L. Rivest, M.J.B. Robshaw, R.Sidney, and Y.L. Yin. [Http://theory.lcs.mit.edu/ ~ rivest/rc6.pdf The RC6 Block Cipher] {{Webarchive|url=https://web.archive.org/web/20081202115943/http://www.theory.lcs.mit.edu/ |date=2 грудня 2008 }}. v1.1, August 1998.
* J. Beuchat [https://web.archive.org/web/20060505225326/http://perso.ens-lyon.fr/jean-luc.beuchat/Publications/fpl2003.pdf FPGA Implementations of the RC6 Block Cipher].

== Примітки ==
{{reflist}}

== Посилання ==
* [http://www.users.zetnet.co.uk/hopwood/crypto/scan/cs.html # RC6 SCAN's entry on RC6] {{Webarchive|url=https://www.webcitation.org/652BeKiUl?url=http://www.users.zetnet.co.uk/hopwood/crypto/scan/cs.html |date=28 січня 2012 }}
* [https://web.archive.org/web/20061016164128/http://www.rsasecurity.com/rsalabs/node.asp?id=2512 RSA Security's RC6 page]
* [ftp://ftp.rsasecurity.com/pub/rsalabs/rc6/rc6v11.pdf Специфікація алгоритму RC6]{{Недоступне посилання|date=лютий 2019 |bot=InternetArchiveBot }}

{{Блочні алгоритми шифрування}}

[[Категорія:Блокові шифри]]
[[Категорія:Статті з прикладами коду мовою C]]