www.wikidata.uk-ua.nina.az

Twofish симетричний алгоритм блочного шифрування з розміром блоку 128 біт і довжиною ключа до 256 біт Число раундів 16 Р

Twofish

Twofish — симетричний алгоритм блочного шифрування з розміром блоку 128 біт і довжиною ключа до 256 біт. Число раундів 16. Розроблено групою фахівців на чолі з Брюсом Шнайером. Був одним з п'яти фіналістів другого етапу конкурсу AES. Алгоритм розроблений на основі алгоритмів Blowfish, SAFER і Square.

Twofish
Розробники Брюс Шнайєр
Уперше оприлюднений 1998 р.
Раундів 16
Тип Мережа Фейстеля

Відмінними особливостями алгоритму є використання попередньо обчислюваних та залежних від ключа S-box'ів і складна схема розгортки підключення шифрування. Половина n-бітного ключа шифрування використовується як власне ключ шифрування, інша — для модифікації алгоритму (від неї залежать S-box'и).

Загальні відомості ред.

Twofish розроблявся спеціально з урахуванням вимог та рекомендацій NIST для конкурсу AES :

  • 128-бітний блочний симетричний шифр
  • Довжина ключів 128, 192 і 256 біт
  • Відсутність слабких ключів
  • Ефективна програмна (в першу чергу на 32-бітних процесорах) та апаратна реалізація
  • Гнучкість (можливість використання додаткових довжин ключа, використання в поточному шифруванні, хеш-функціях і т. д.)
  • Простота алгоритму - для можливості його ефективного аналізу

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

Алгоритм Twofish виник в результаті спроби модифіковані алгоритм Blowfish для 128-бітового вхідного блоку. Новий алгоритм повинен був бути легко реалізованим апаратно (у тому числі використовувати таблиці меншого розміру), мати досконалішу систему розширення ключа (key schedule) і мати однозначну функцію F.

В результаті, алгоритм був реалізований у вигляді змішаної мережі Фейстеля з чотирма гілками, які модифікують один одну з використанням криптоперетворень Адамара (Pseudo-Hadamar Transform, PHT).

Можливість ефективної реалізації на сучасних (для того часу) 32-бітних процесорах (а також в смарт-картах і подібних пристроях) - один з ключових принципів, яким керувалися розробники Twofish.
Наприклад, у функції F при обчисленні PHT і складання з частиною ключа K навмисно використовується додавання, замість традиційного xor. Це дає можливість використовувати команду LEA сімейства процесорів Pentium, яка за один такт дозволяє обчислити перетворення Адамара . (Правда в такому випадку код доводиться компілювати під конкретне значення ключа).

Алгоритм Twofish не запатентований і може бути використаний ким завгодно без будь-якої плати або відрахувань. Він використовується в багатьох програмах шифрування, хоча і отримав менше поширення, ніж Blowfish.

Опис алгоритму ред.

Twofish розбиває вхідний 128-бітний блок даних на чотири 32-бітних підблоки, над якими, після процедури вхідного відбілювання (input whitening), проводиться 16 раундів перетворень. Після останнього раунду виконується вихідна відбілювання (output whitening).

Відбілювання (whitening) ред.

Відбілювання — це процедура xor'а даних з підключами перед першим раундом і після останнього раунду. Вперше ця техніка була використана в шифрі Khufu/Khare і, незалежно, Рональдом Рівестом (англ. Ron Rivest) в алгоритмі шифрування DESX. Joe Killian (NEC) і Phillip Rogaway (Каліфорнійський університет) показали, що відбілювання дійсно ускладнює завдання пошуку ключа повним перебором (exhaustive key-search) в DESX . Розробники Twofish стверджують, що в Twofish відбілювання також істотно ускладнює завдання підбору ключа, оскільки криптоаналітика не може дізнатися, які дані потрапляють на вхід функції F першого раунду.

Тим не менш, виявилися і негативні сторони. Цікаве дослідження провели фахівці дослідницького центру компанії IBM. Вони виконали реалізацію алгоритму Twofish для типової смарт-карти з CMOS-архітектурою і проаналізували можливість атаки за допомогою диференціального аналізу споживаної потужності (DPA — Differential Power Analysis). Атаці піддавалася саме процедура вхідного вибілювання, оскільки вона безпосередньо використовує xor підключів з вхідними даними. У результаті дослідники показали, що можна повністю обчислити 128-бітовий ключ проаналізувавши всього 100 операцій шифрування довільних блоків.

Функція g ред.

Функція g — основа алгоритму Twofish. На вхід функції подається 32-бітове число X, яке потім розбивається на чотири байти x0, x1, x2, x3. Кожен з вийшов байтів пропускається через свій S-box. (Слід зазначити, що S-box'и в алгоритмі не фіксовані, а залежать від ключа). Отримані 4 байти на виходах S-box'ов інтерпретуються як вектор з чотирма компонентами. Цей вектор множиться на фіксовану матрицю MDS (maximum distance separable) розміром 4x4, причому обчислення проводяться в скінченному полі по модулю непривідного многочлена

MDS матриця — це така матриця над кінцевим полем K, що якщо взяти її як матрицю лінійного перетворення з простору у простір , то будь-які два вектори з простору виду (x, f (x)) будуть мати як мінімум m+1 відмінностей в компонентах. Тобто набір векторів вигляду (x, f (x)) утворює код, що володіє властивістю максимального рознесення (maximum distance separable code). Таким кодом, наприклад, є код Ріда-Соломона.

В Twofish властивість максимальної рознесеність матриці MDS означає, що загальна кількість змінних байт вектора a і вектора не менше п'яти. Іншими словами, будь-яка зміна тільки одного байта в a призводить до зміни всіх чотирьох байтів в b.

Криптоперетворення Адамара (Pseudo-Hadamar Transform, PHT) ред.

криптоперетворення Адамара — оборотне перетворення бітового рядка довжиною 2n. Рядок розбивається на дві частини a і b однакової довжини в n біт. Перетворення обчислюється таким чином:

Ця операція часто використовується для «розсіювання» коду (наприклад в шифрі SAFER).

В Twofish це перетворення використовується при змішуванні результатів двох g-функцій (n = 32).

Циклічний зсув на 1 біт ред.

У кожному раунді два правих 32-бітових блоки, які xor-яться з результатами функції F, додатково циклічно зрушуються на один біт. Третій блок зрушується до операції xor, четвертий блок — після. Ці зрушення спеціально додані, щоб порушити вирівнювання по байтах, яке властиво S-box'ам та операції множення на MDS-матрицю. Проте шифр перестає бути повністю симетричним, так як при шифруванні й розшифровці зрушення слід здійснювати в протилежні сторони.

Генерація ключів ред.

Twofish розрахований на роботу з ключами довжиною 128, 192 і 256 біт. З вихідного ключа генерується 40 32-бітних підключів, перші вісім з яких використовуються тільки в операціях вхідного і вихідного вибілювання, а решта 32 — в раундах шифрування, по два підключі на раунд. Особливістю Twofish є те, що вихідний ключ використовується також і для зміни самого алгоритму шифрування, так як використовуються у функції g S-box'и не фіксовані, а залежать від ключа.

Для формування раундових підключів вихідний ключ M розбивається з перестановкою байт на два однакові блоки і . Потім за допомогою блоку і функції h шифрується значення 2 * i, а за допомогою блоку шифрується значення 2*i+1, де i — номер поточного раунду (0 — 15). Отримані зашифровані блоки змішуються криптоперетвореням Адамара, і потім використовуються як раундові підключі.

Технічні подробиці ред.

Розглянемо більш докладно алгоритм формування раундових підключів, а також залежить від ключа функції g. Як для формування підключів, так і для формування функції g в Twofish використовується одна основна функція: h (X, L 0 , L 1 , ..., L k ). Тут X, L 0 , L 1 , ..., L k - 32 бітні слова, а k = N / 64, де N - довжина вихідного ключа в бітах. Результатом функції є одне 32-бітове слово.

Функція h ред.

Функція виконується в k етапів. Тобто для довжини ключа 256 біт буде 4 етапи, для ключа в 192 біта - 3 етапи, для 128 біт - 2 етапи.

На кожному етапі вхідний 32-бітове слово розбивається на 4 байта, і кожен байт піддається фіксованою перестановці бітів q 0 або q 1

Результат представляється у вигляді вектора з 4 байтів і множиться на MDS матрицю. Обчислення проводяться в полі Галуа GF (2 8 ) по модулю непривідного многочлена .

Перестановки q 0 і q 1 ред.

q 0 і q 1 - фіксовані перестановки 8 бітів вхідного байта x.

Байт x розбивається на дві 4-бітні половинки a 0 і b 0 , над якими проводяться наступні перетворення:

Тут - 4-бітний циклічний зсув вправо, а t 0 , t 1 , t 2 , t 3 - табличні заміни 4-бітових чисел.

Для q 0 таблиці мають вигляд:

Для q 1 таблиці мають вигляд:

Генерація ключів ред.

Нехай M - вихідний ключ, N - його довжина в бітах. Генерація підключів відбувається наступним чином:

  • Оригінальний ключ розбивається на 8 * k байтів , де k = N / 64.
  • Ці 8 * k байтів розбиваються на слова по чотири байти, і в кожному слові байти переставляються у зворотному порядку. У підсумку виходить 2 * k 32-бітних слова
  • Отримані 2 * k 32-бітних розбиваються на два вектора і розміром в k 32-бітових слів.

Підключі для i-го раунду обчислюються за формулами:

Функція g і S-box'и ред.

Функція g визначається через функцію h:

Вектор S, як і вектора M e і M o , теж формується з вихідного ключа і складається з k 32-бітових слів. Вихідні байти ключа розбиваються на k груп по вісім байт. Кожна така група розглядається як вектор з 8-ма компонентами і множиться на фіксовану RS матрицю розміром 4x8 байт. В результаті множення виходить вектор, що складається з чотирьох байт. Обчислення проводяться в полі Галуа по модулю непріводімогомногочлена .

Криптоаналіз ред.

Вивчення Twofish зі скороченими числом раундів показало, що алгоритм володіє великим запасом міцності, і, в порівнянні з іншими фіналістами конкурсу AES, він виявився найстійкішим. Проте його незвичайна структура і відносна складність породили деякі сумніви щодо якості цієї міцності.

Нарікання викликало розділення вихідного ключа на дві половини при формуванні раундових підключів. Криптографи Fauzan Mirza і Sean Murphy припустили, що такий поділ дає можливість організувати атаку за принципом «розділяй і володарюй», тобто розбити задачу на дві аналогічні, але простіші . Однак реально подібну атаку провести не вдалося.

На 2008 рік найкращим варіантом криптоаналізу Twofish є варіант усіченого диференціального криптоаналізу, який був опублікований Shiho Moriai і Yiqun Lisa Yin в Японії в 2000 році . Вони показали, що для знаходження необхідних диференціалів потрібно 2 51 підібраних відкритих текстів. Проте дослідження мали теоретичний характер, жодної реальної атаки проведено не було. У своєму блозі творець Twofish Брюс Шнайєр стверджує, що в реальності провести таку атаку неможливо .

Посилання ред.

Примітки ред.

  1. «Announcing Request for Candidate Algorithm Nominations for the Advanced Encryption Standard (AES)» [ 5 червня 2011 у Wayback Machine.] (англ.). Department of Commerce - National Institute of Standards and Technology - Federal Register: September 12, 1997
  2. Nechvatal J., Barker E., Bassham L., Burr W., Dworkin M., Foti J., Roback E. pdf «Report on the Development of the Advanced Encryption Standard (AES)»[недоступне посилання з червня 2019] (англ.). - National Institute of Standards and Technology.
  3. J. Kilian and P. Rogaway rogaway/papers/desx.pdf «How to Protect DES Against Exhaustive Key Search»[недоступне посилання з червня 2019] (англ.) February 2, 2000
  4. N. Ferguson, J. Kelsey, B. Schneier, D. Whiting «A Twofish Retreat: Related-Key Attacks Against Reduced-Round Twofish» [ 19 липня 2008 у Wayback Machine.] (англ.) Twofish Technical Report # 6, February 14, 2000
  5. Suresh Chari, Charanjit Jutla, Josyula R. Rao, Pankaj Rohatgi «A Cautionary Note Regarding Evaluation of AES Candidates on Smart-Cards» [ 13 жовтня 2012 у Wayback Machine.] (англ.), 1999
  6. Fauzan Mirza, Sean Murphy «An Observation on the Key Schedule of Twofish» [ 21 грудня 2016 у Wayback Machine.] (англ.) - Information Security Group, Royal Holloway, University of London - January 26, 1999
  7. Shiho Moriai, Yiqun Lisa Yin / twofish-analysis-shiho.pdf «Cryptanalysis of Twofish (II)» [ 22 жовтня 2016 у Wayback Machine.] (англ.) - The Institute of Economics, Information and Communication Engineers
  8. Bruce Schneier «Twofish Cryptanalysis Rumors» [ 9 червня 2012 у Wayback Machine.] (англ.) blog
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Twofish simetrichnij algoritm blochnogo shifruvannya z rozmirom bloku 128 bit i dovzhinoyu klyucha do 256 bit Chislo raundiv 16 Rozrobleno grupoyu fahivciv na choli z Bryusom Shnajerom Buv odnim z p yati finalistiv drugogo etapu konkursu AES Algoritm rozroblenij na osnovi algoritmiv Blowfish SAFER i Square TwofishRozrobniki Bryus ShnajyerUpershe oprilyudnenij 1998 r Raundiv 16Tip Merezha FejstelyaVidminnimi osoblivostyami algoritmu ye vikoristannya poperedno obchislyuvanih ta zalezhnih vid klyucha S box iv i skladna shema rozgortki pidklyuchennya shifruvannya Polovina n bitnogo klyucha shifruvannya vikoristovuyetsya yak vlasne klyuch shifruvannya insha dlya modifikaciyi algoritmu vid neyi zalezhat S box i Zmist 1 Zagalni vidomosti 2 Opis algoritmu 2 1 Vidbilyuvannya whitening 2 2 Funkciya g 2 3 Kriptoperetvorennya Adamara Pseudo Hadamar Transform PHT 2 4 Ciklichnij zsuv na 1 bit 2 5 Generaciya klyuchiv 3 Tehnichni podrobici 3 1 Funkciya h 3 1 1 Perestanovki q 0 i q 1 3 2 Generaciya klyuchiv 3 3 Funkciya g i S box i 4 Kriptoanaliz 5 Posilannya 6 PrimitkiZagalni vidomosti red Twofish rozroblyavsya specialno z urahuvannyam vimog ta rekomendacij NIST dlya konkursu AES 1 128 bitnij blochnij simetrichnij shifr Dovzhina klyuchiv 128 192 i 256 bit Vidsutnist slabkih klyuchiv Efektivna programna v pershu chergu na 32 bitnih procesorah ta aparatna realizaciya Gnuchkist mozhlivist vikoristannya dodatkovih dovzhin klyucha vikoristannya v potochnomu shifruvanni hesh funkciyah i t d Prostota algoritmu dlya mozhlivosti jogo efektivnogo analizuOdnak same skladnist strukturi algoritmu i vidpovidno skladnist jogo analizu na predmet slabkih klyuchiv abo prihovanih zv yazkiv a takozh dosit povilne chas shifruvannya porivnyano z Rijndael na bilshosti platform zigralo ne na jogo korist 2 Algoritm Twofish vinik v rezultati sprobi modifikovani algoritm Blowfish dlya 128 bitovogo vhidnogo bloku Novij algoritm povinen buv buti legko realizovanim aparatno u tomu chisli vikoristovuvati tablici menshogo rozmiru mati doskonalishu sistemu rozshirennya klyucha key schedule i mati odnoznachnu funkciyu F V rezultati algoritm buv realizovanij u viglyadi zmishanoyi merezhi Fejstelya z chotirma gilkami yaki modifikuyut odin odnu z vikoristannyam kriptoperetvoren Adamara Pseudo Hadamar Transform PHT Mozhlivist efektivnoyi realizaciyi na suchasnih dlya togo chasu 32 bitnih procesorah a takozh v smart kartah i podibnih pristroyah odin z klyuchovih principiv yakim keruvalisya rozrobniki Twofish Napriklad u funkciyi F pri obchislenni PHT i skladannya z chastinoyu klyucha K navmisno vikoristovuyetsya dodavannya zamist tradicijnogo xor Ce daye mozhlivist vikoristovuvati komandu LEA simejstva procesoriv Pentium yaka za odin takt dozvolyaye obchisliti peretvorennya Adamara T 0 2 T 1 K 2 r 9 m o d 2 32 displaystyle T 0 2 T 1 K 2r 9 mod 2 32 nbsp Pravda v takomu vipadku kod dovoditsya kompilyuvati pid konkretne znachennya klyucha Algoritm Twofish ne zapatentovanij i mozhe buti vikoristanij kim zavgodno bez bud yakoyi plati abo vidrahuvan Vin vikoristovuyetsya v bagatoh programah shifruvannya hocha i otrimav menshe poshirennya nizh Blowfish Opis algoritmu red Twofish rozbivaye vhidnij 128 bitnij blok danih na chotiri 32 bitnih pidbloki nad yakimi pislya proceduri vhidnogo vidbilyuvannya input whitening provoditsya 16 raundiv peretvoren Pislya ostannogo raundu vikonuyetsya vihidna vidbilyuvannya output whitening Vidbilyuvannya whitening red Vidbilyuvannya ce procedura xor a danih z pidklyuchami pered pershim raundom i pislya ostannogo raundu Vpershe cya tehnika bula vikoristana v shifri Khufu Khare i nezalezhno Ronaldom Rivestom angl Ron Rivest v algoritmi shifruvannya DESX Joe Killian NEC i Phillip Rogaway Kalifornijskij universitet pokazali sho vidbilyuvannya dijsno uskladnyuye zavdannya poshuku klyucha povnim pereborom exhaustive key search v DESX 3 Rozrobniki Twofish stverdzhuyut 4 sho v Twofish vidbilyuvannya takozh istotno uskladnyuye zavdannya pidboru klyucha oskilki kriptoanalitika ne mozhe diznatisya yaki dani potraplyayut na vhid funkciyi F pershogo raundu Tim ne mensh viyavilisya i negativni storoni Cikave doslidzhennya proveli fahivci doslidnickogo centru kompaniyi IBM 5 Voni vikonali realizaciyu algoritmu Twofish dlya tipovoyi smart karti z CMOS arhitekturoyu i proanalizuvali mozhlivist ataki za dopomogoyu diferencialnogo analizu spozhivanoyi potuzhnosti DPA Differential Power Analysis Ataci piddavalasya same procedura vhidnogo vibilyuvannya oskilki vona bezposeredno vikoristovuye xor pidklyuchiv z vhidnimi danimi U rezultati doslidniki pokazali sho mozhna povnistyu obchisliti 128 bitovij klyuch proanalizuvavshi vsogo 100 operacij shifruvannya dovilnih blokiv Funkciya g red Funkciya g osnova algoritmu Twofish Na vhid funkciyi podayetsya 32 bitove chislo X yake potim rozbivayetsya na chotiri bajti x0 x1 x2 x3 Kozhen z vijshov bajtiv propuskayetsya cherez svij S box Slid zaznachiti sho S box i v algoritmi ne fiksovani a zalezhat vid klyucha Otrimani 4 bajti na vihodah S box ov interpretuyutsya yak vektor z chotirma komponentami Cej vektor mnozhitsya na fiksovanu matricyu MDS maximum distance separable rozmirom 4x4 prichomu obchislennya provodyatsya v skinchennomu poli G F 2 8 displaystyle GF 2 8 nbsp po modulyu neprividnogo mnogochlena x 8 x 6 x 5 x 3 1 displaystyle x 8 x 6 x 5 x 3 1 nbsp MDS matricya ce taka matricya nad kincevim polem K sho yaksho vzyati yiyi yak matricyu linijnogo peretvorennya f x M D S x displaystyle f x MDS x nbsp z prostoru K n displaystyle K n nbsp u prostir K m displaystyle K m nbsp to bud yaki dva vektori z prostoru K n m displaystyle K n m nbsp vidu x f x budut mati yak minimum m 1 vidminnostej v komponentah Tobto nabir vektoriv viglyadu x f x utvoryuye kod sho volodiye vlastivistyu maksimalnogo roznesennya maximum distance separable code Takim kodom napriklad ye kod Rida Solomona V Twofish vlastivist maksimalnoyi roznesenist matrici MDS oznachaye sho zagalna kilkist zminnih bajt vektora a i vektora b M D S a displaystyle b MDS a nbsp ne menshe p yati Inshimi slovami bud yaka zmina tilki odnogo bajta v a prizvodit do zmini vsih chotiroh bajtiv v b Kriptoperetvorennya Adamara Pseudo Hadamar Transform PHT red kriptoperetvorennya Adamara oborotne peretvorennya bitovogo ryadka dovzhinoyu 2n Ryadok rozbivayetsya na dvi chastini a i b odnakovoyi dovzhini v n bit Peretvorennya obchislyuyetsya takim chinom a a b mod 2 n displaystyle a a b pmod 2 n nbsp b a 2 b mod 2 n displaystyle b a 2b pmod 2 n nbsp Cya operaciya chasto vikoristovuyetsya dlya rozsiyuvannya kodu napriklad v shifri SAFER V Twofish ce peretvorennya vikoristovuyetsya pri zmishuvanni rezultativ dvoh g funkcij n 32 Ciklichnij zsuv na 1 bit red U kozhnomu raundi dva pravih 32 bitovih bloki yaki xor yatsya z rezultatami funkciyi F dodatkovo ciklichno zrushuyutsya na odin bit Tretij blok zrushuyetsya do operaciyi xor chetvertij blok pislya Ci zrushennya specialno dodani shob porushiti virivnyuvannya po bajtah yake vlastivo S box am ta operaciyi mnozhennya na MDS matricyu Prote shifr perestaye buti povnistyu simetrichnim tak yak pri shifruvanni j rozshifrovci zrushennya slid zdijsnyuvati v protilezhni storoni Generaciya klyuchiv red Twofish rozrahovanij na robotu z klyuchami dovzhinoyu 128 192 i 256 bit Z vihidnogo klyucha generuyetsya 40 32 bitnih pidklyuchiv pershi visim z yakih vikoristovuyutsya tilki v operaciyah vhidnogo i vihidnogo vibilyuvannya a reshta 32 v raundah shifruvannya po dva pidklyuchi na raund Osoblivistyu Twofish ye te sho vihidnij klyuch vikoristovuyetsya takozh i dlya zmini samogo algoritmu shifruvannya tak yak vikoristovuyutsya u funkciyi g S box i ne fiksovani a zalezhat vid klyucha Dlya formuvannya raundovih pidklyuchiv vihidnij klyuch M rozbivayetsya z perestanovkoyu bajt na dva odnakovi bloki M o displaystyle M o nbsp i M e displaystyle M e nbsp Potim za dopomogoyu bloku M o displaystyle M o nbsp i funkciyi h shifruyetsya znachennya 2 i a za dopomogoyu bloku M e displaystyle M e nbsp shifruyetsya znachennya 2 i 1 de i nomer potochnogo raundu 0 15 Otrimani zashifrovani bloki zmishuyutsya kriptoperetvorenyam Adamara i potim vikoristovuyutsya yak raundovi pidklyuchi Tehnichni podrobici red Rozglyanemo bilsh dokladno algoritm formuvannya raundovih pidklyuchiv a takozh zalezhit vid klyucha funkciyi g Yak dlya formuvannya pidklyuchiv tak i dlya formuvannya funkciyi g v Twofish vikoristovuyetsya odna osnovna funkciya h X L 0 L 1 L k Tut X L 0 L 1 L k 32 bitni slova a k N 64 de N dovzhina vihidnogo klyucha v bitah Rezultatom funkciyi ye odne 32 bitove slovo Funkciya h red Funkciya vikonuyetsya v k etapiv Tobto dlya dovzhini klyucha 256 bit bude 4 etapi dlya klyucha v 192 bita 3 etapi dlya 128 bit 2 etapi Na kozhnomu etapi vhidnij 32 bitove slovo rozbivayetsya na 4 bajta i kozhen bajt piddayetsya fiksovanoyu perestanovci bitiv q 0 abo q 1Rezultat predstavlyayetsya u viglyadi vektora z 4 bajtiv i mnozhitsya na MDS matricyu Obchislennya provodyatsya v poli Galua GF 2 8 po modulyu neprividnogo mnogochlena x 8 x 6 x 5 x 3 1 displaystyle x 8 x 6 x 5 x 3 1 nbsp Matricya MDS maye viglyad MDS 01 E F 5 B 5 B 5 B E F E F 01 E F 5 B 01 E F E F 01 E F 5 B displaystyle mbox MDS begin pmatrix 01 amp EF amp 5B amp 5B 5B amp EF amp EF amp 01 EF amp 5B amp 01 amp EF EF amp 01 amp EF amp 5B end pmatrix nbsp Perestanovki q 0 i q 1 red q 0 i q 1 fiksovani perestanovki 8 bitiv vhidnogo bajta x Bajt x rozbivayetsya na dvi 4 bitni polovinki a 0 i b 0 nad yakimi provodyatsya nastupni peretvorennya a 0 x 16 displaystyle a 0 x 16 nbsp b 0 x mod 16 displaystyle b 0 x bmod 16 nbsp a 1 a 0 b 0 displaystyle a 1 a 0 oplus b 0 nbsp b 1 a 0 ROR 4 b 0 1 8 a 0 mod 16 displaystyle b 1 a 0 oplus mbox ROR 4 b 0 1 oplus 8a 0 bmod 16 nbsp a 2 t 0 a 1 displaystyle a 2 t 0 a 1 nbsp b 2 t 1 b 1 displaystyle b 2 t 1 b 1 nbsp a 3 a 2 b 2 displaystyle a 3 a 2 oplus b 2 nbsp b 3 a 2 ROR 4 b 2 1 8 a 2 mod 16 displaystyle b 3 a 2 oplus mbox ROR 4 b 2 1 oplus 8a 2 bmod 16 nbsp a 4 t 2 a 3 displaystyle a 4 t 2 a 3 nbsp b 4 t 3 b 3 displaystyle b 4 t 3 b 3 nbsp y 16 b 4 a 4 displaystyle y 16b 4 a 4 nbsp Tut ROR 4 displaystyle mbox ROR 4 nbsp 4 bitnij ciklichnij zsuv vpravo a t 0 t 1 t 2 t 3 tablichni zamini 4 bitovih chisel Dlya q 0 tablici mayut viglyad t0 8 1 7 D 6 F 3 2 0 B 5 9 E C A 4 t1 E C B 8 1 2 3 5 F 4 A 6 7 0 9 D t2 B A 5 E 6 D 9 0 C 8 F 3 2 4 7 1 t3 D 7 F 4 1 2 6 E 9 B 3 0 8 5 C A Dlya q 1 tablici mayut viglyad t0 2 8 B D F 7 6 E 3 1 9 4 0 A C 5 t1 1 E 2 B 4 C 3 7 6 D A 5 F 9 0 8 t2 4 C 7 5 1 6 9 A 0 E D 8 2 B 3 F t3 B 9 5 1 C 3 D E 6 4 7 F 2 0 8 A Generaciya klyuchiv red Nehaj M vihidnij klyuch N jogo dovzhina v bitah Generaciya pidklyuchiv vidbuvayetsya nastupnim chinom Originalnij klyuch rozbivayetsya na 8 k bajtiv m 0 m 8 k 1 displaystyle m 0 m 8k 1 nbsp de k N 64 Ci 8 k bajtiv rozbivayutsya na slova po chotiri bajti i v kozhnomu slovi bajti perestavlyayutsya u zvorotnomu poryadku U pidsumku vihodit 2 k 32 bitnih slova M i displaystyle M i nbsp M i j 0 3 m 4 i j 2 8 j i 0 2 k 1 displaystyle M i sum j 0 3 m 4i j cdot 2 8j i 0 2k 1 nbsp Otrimani 2 k 32 bitnih rozbivayutsya na dva vektora M e displaystyle M e nbsp i M o displaystyle M o nbsp rozmirom v k 32 bitovih sliv M e M 0 M 2 M 2 k 2 displaystyle M e M 0 M 2 M 2k 2 nbsp M o M 1 M 3 M 2 k 1 displaystyle M o M 1 M 3 M 2k 1 nbsp Pidklyuchi dlya i go raundu obchislyuyutsya za formulami r 2 24 2 16 2 8 2 0 displaystyle rho 2 24 2 16 2 8 2 0 nbsp A i h 2 i r M e displaystyle A i h 2i rho M e nbsp B i ROL h 2 i 1 r M 0 8 displaystyle B i mbox ROL h 2i 1 rho M 0 8 nbsp K 2 i A i B i mod 2 32 displaystyle K 2i A i B i bmod 2 32 nbsp K 2 i 1 ROL A i 2 B i mod 2 32 9 displaystyle K 2i 1 mbox ROL A i 2B i bmod 2 32 9 nbsp Funkciya g i S box i red Funkciya g viznachayetsya cherez funkciyu h g X h X S displaystyle g X h X S nbsp Vektor S yak i vektora M e i M o tezh formuyetsya z vihidnogo klyucha i skladayetsya z k 32 bitovih sliv Vihidni bajti klyucha rozbivayutsya na k grup po visim bajt Kozhna taka grupa rozglyadayetsya yak vektor z 8 ma komponentami i mnozhitsya na fiksovanu RS matricyu rozmirom 4x8 bajt V rezultati mnozhennya vihodit vektor sho skladayetsya z chotiroh bajt Obchislennya provodyatsya v poli Galua G F 2 8 displaystyle GF 2 8 nbsp po modulyu neprivodimogomnogochlena x 8 x 6 x 3 x 2 1 displaystyle x 8 x 6 x 3 x 2 1 nbsp RS matricya maye viglyad RS 01 A 4 55 87 5 A 58 D B 9 E A 4 56 82 F 3 1 E C 6 68 E 5 02 A 1 F C C 1 47 A E 3 D 19 A 4 55 87 5 A 58 D B 9 E 03 displaystyle mbox RS begin pmatrix 01 amp A4 amp 55 amp 87 amp 5A amp 58 amp DB amp 9E A4 amp 56 amp 82 amp F3 amp 1E amp C6 amp 68 amp E5 02 amp A1 amp FC amp C1 amp 47 amp AE amp 3D amp 19 A4 amp 55 amp 87 amp 5A amp 58 amp DB amp 9E amp 03 end pmatrix nbsp Kriptoanaliz red Vivchennya Twofish zi skorochenimi chislom raundiv pokazalo sho algoritm volodiye velikim zapasom micnosti i v porivnyanni z inshimi finalistami konkursu AES vin viyavivsya najstijkishim Prote jogo nezvichajna struktura i vidnosna skladnist porodili deyaki sumnivi shodo yakosti ciyeyi micnosti Narikannya viklikalo rozdilennya vihidnogo klyucha na dvi polovini pri formuvanni raundovih pidklyuchiv Kriptografi Fauzan Mirza i Sean Murphy pripustili sho takij podil daye mozhlivist organizuvati ataku za principom rozdilyaj i volodaryuj tobto rozbiti zadachu na dvi analogichni ale prostishi 6 Odnak realno podibnu ataku provesti ne vdalosya Na 2008 rik najkrashim variantom kriptoanalizu Twofish ye variant usichenogo diferencialnogo kriptoanalizu yakij buv opublikovanij Shiho Moriai i Yiqun Lisa Yin v Yaponiyi v 2000 roci 7 Voni pokazali sho dlya znahodzhennya neobhidnih diferencialiv potribno 2 51 pidibranih vidkritih tekstiv Prote doslidzhennya mali teoretichnij harakter zhodnoyi realnoyi ataki provedeno ne bulo U svoyemu blozi tvorec Twofish Bryus Shnajyer stverdzhuye sho v realnosti provesti taku ataku nemozhlivo 8 Posilannya red Twofish web page Arhivovano 26 chervnya 2012 u Wayback Machine Vihidni kodi Twofish Arhivovano 26 chervnya 2012 u Wayback Machine Twoish A 128 Bit Block Cipher Arhivovano 29 serpnya 2008 u Wayback Machine Algoritmi shifruvannya finalisti konkursu AES Arhivovano 30 sichnya 2012 u Wayback Machine Spisok produktiv sho vikoristovuyut Twofish Arhivovano 1 chervnya 2012 u Wayback Machine Primitki red Announcing Request for Candidate Algorithm Nominations for the Advanced Encryption Standard AES Arhivovano 5 chervnya 2011 u Wayback Machine angl Department of Commerce National Institute of Standards and Technology Federal Register September 12 1997 Nechvatal J Barker E Bassham L Burr W Dworkin M Foti J Roback E pdf Report on the Development of the Advanced Encryption Standard AES nedostupne posilannya z chervnya 2019 angl National Institute of Standards and Technology J Kilian and P Rogaway rogaway papers desx pdf How to Protect DES Against Exhaustive Key Search nedostupne posilannya z chervnya 2019 angl February 2 2000 N Ferguson J Kelsey B Schneier D Whiting A Twofish Retreat Related Key Attacks Against Reduced Round Twofish Arhivovano 19 lipnya 2008 u Wayback Machine angl Twofish Technical Report 6 February 14 2000 Suresh Chari Charanjit Jutla Josyula R Rao Pankaj Rohatgi A Cautionary Note Regarding Evaluation of AES Candidates on Smart Cards Arhivovano 13 zhovtnya 2012 u Wayback Machine angl 1999 Fauzan Mirza Sean Murphy An Observation on the Key Schedule of Twofish Arhivovano 21 grudnya 2016 u Wayback Machine angl Information Security Group Royal Holloway University of London January 26 1999 Shiho Moriai Yiqun Lisa Yin twofish analysis shiho pdf Cryptanalysis of Twofish II Arhivovano 22 zhovtnya 2016 u Wayback Machine angl The Institute of Economics Information and Communication Engineers Bruce Schneier Twofish Cryptanalysis Rumors Arhivovano 9 chervnya 2012 u Wayback Machine angl blog Otrimano z https uk wikipedia org w index php title Twofish amp oldid 37340793