3934

Фіналіст AES – шифр Serpent

Реферат

Информатика, кибернетика и программирование

Тема доповіді – Фіналіст AES – шифр Serpent. План Загальні відомості про конкурс AES. Основні відомості про шифр Serpent Структура алгоритму Розшифрування та розширення ключа. Алгоритм вибору підключів і...

Украинкский

2012-11-10

134.5 KB

7 чел.

Тема доповіді – Фіналіст AES – шифр Serpent. 

План

  1.  Загальні відомості про конкурс AES.
  2.  Основні відомості про шифр Serpent
  3.  Структура алгоритму
    1.  Розшифрування та розширення ключа.
    2.  Алгоритм вибору підключів із ключа.
    3.  Перестановка, S-box, лінійне перетворення.
    4.  Ефективна реалізація

Список використаних джерел

Контрольні питання до теми

Загальні відомості про конкурс AES

 У 80-х роках у США був прийнятий стандарт симетричного криптоалгоритму для внутрішнього застосування DES (Data Encryption Standard), який отримав досить широке поширення в свій час. Проте на даний момент цей стандарт повністю неприйнятний для використання з двох причин: основна - довжина його ключа 56 біт, що надзвичайно мало на сучасному етапі розвитку ЕОМ,  другорядна - при розробці алгоритм був орієнтований на апаратну реалізацію, тобто містив операції, що виконуються на мікропроцесорах за неприйнятним великий час (наприклад, такі як перестановка біт всередині машинного слова за певною схемою).

Все це спонукало Американський інститут стандартизації NIST - National Institute of Standards & Technology на оголошення в 1997 році конкурсу на новий стандарт симетричного криптоалгоритму. Цього разу вже були враховані основні недоліки шифру-попередника, а до розробки були підключені найбільші центри з криптології з усього світу. Тим самим, переможець цього змагання, названого AES - Advanced Encryption Standard, стане де-факто світовим крипттостандартом на найближчі 10-20 років.

Вимоги, пред'явлені до кандидитом на AES в 1998 році, були гранично прості: алгоритм повинен бути симетричним, алгоритм повинен бути блоковим шифром, алгоритм повинен мати довжину блоку 128 біт, і підтримувати три довжини ключа: 128, 192 і 256 біт. Також були додаткові вимоги: використовувати операції, легко реалізовані як апаратно (у мікрочіпі), так і програмно (на персональних комп'ютерах і серверах), орієнтуватися на 32-розрядні процесори, не ускладнювати без необхідності структуру шифру для того, щоб всі зацікавлені сторони були в змозі самостійно провести незалежний криптоаналіз алгоритму і переконатися, що в ньому не закладено будь-яких незадокументованих можливостей. На подальшому розвитку було обрано п’ять фіналістів у їх число і війшов шифр Serpent, Mars, TwoFish, RC6, Rijndael [слайд 2].

 2 жовтня 2000 NIST оголосив про свій вибір - переможцем конкурсу став бельгійський алгоритм RIJNDAEL.

 

2.Основні відомості про шифр Serpent

 Головна родзинка шифру SERPENT в тому, що всі три його автора - це "аси криптоаналізу", найбільш відомі розкриттям шифрів інших криптографів. Ізраїльський дослідник Елі Біхам - один з творців диференціального криптоаналізу - техніки, що лежить в основі більшості сучасних методів розкриття блокових шифрів. Данець Ларс Кнудсен вже згадувався в цьому огляді у зв'язку з шифром угоди (Кнудсен - єдиний криптограф, що фігурує одразу в двох проектах). Англієць Росс Андерсон з Кембриджського університету з початку 90-х років відомий своїми неординарними криптоаналітичних роботами [2].

Алгоритм був одним з фіналістів 2-го етапу конкурсу AES. Як і інші алгоритми, що беруть участь у конкурсі AES, Serpent має розмір блоку 128 біт і можливe довжинe ключа 128, 192 або 256 біт. Алгоритм представляє собою 32-раундову SP-мережу, що працює з блоком з чотирьох 32-бітових слів. Але Serpent був розроблений так, що всі операції можуть бути виконані паралельно, використовуючи 32 1-бітових потоки.

При розробці Serpent використовувався більш консервативний підхід до безпеки, ніж у інших фіналістів AES, проектувальники шифру вважали, що 16 раундів достатньо, щоб протистояти відомим видам криптоаналізу, але збільшили число раундів до 32, щоб алгоритм міг краще протистояти ще не відомим методам криптоаналізу. Ставши фіналістом конкурсу AES, Serpent алгоритм в результаті голосування зайняв 2 місце.

Особливостями алгоритму є: Алгоритм оптимізовано для програмної реалізації в техніці "бітових зрізів" (bitslice) і має ряд обумовлених цим фактом особливостей: у ньому використовуються початкова та зворотна їй кінцева бітові перестановки, які не впливають на стійкість шифру і призначені для оптимізації його реалізації. При реалізації в техніці "бітових зрізів" виконання цих перестановок в явному вигляді не потрібно, при традиційній реалізації - потрібно. Крім того, з тієї ж самої причини в алгоритмі використовуються вузли замін малого розміру (4 на 4 біта), тому що в рамках зазначеної техніки вони реалізуються у вигляді серії логічних операцій над даними і при більшому розмірі це стає важко реалізованим [3].

3 Структура алгоритму

Алгоритм являє собою мережу Фейштеля для чотирьох гілок змішаного типу: 2 парні гілки змінюють сумісності значення непарних, потім міняються місцями. Як криптоперетворення використовуються тільки  виключне "АБО", табличні підстановки і бітові зрушення. Алгоритм складається з 32 раундів. Самі раунди складені таким чином, що додавання до гілками матеріалу ключа на першому і останньому раундах утворює вхідне і вихідне забілювання [4].

Алгоритм Serpent являє собою SP-мережа, в якій весь блок даних довжиною 128 біт на кожному раунді розбивається на 4 слова довжиною по 32 біта. Всі значення, що використовуються для шифрування, представляються бітовими потоками. Індекси біт пробігають значення від 0 до 31 для 32-бітових слів, від 0 до 127 для 128-бітових блоків, від 0 до 255 для 256-бітових ключів і так далі. Для внутрішніх обчислень всі біти величин представлені в прямому порядку (little-endian).

  Serpent шифрує відкритий текст P довжиною 128 біт в шифротекст C довжиною 128 біт за 32 раунди за допомогою 33 підключений K_ (0), ..., K_ (32), довжиною 128 біт. Довжина використовуваного ключа може приймати різні значення, але для конкретики зафіксуємо їх довжину у 128, 192 або 256 біт. Короткі ключі довжиною менше 256 біт доповнюються до повної довжини в 256 біт.

Шифрування складається з наступних основних кроків:

Початкова перестановка;

32 раунди, кожен з яких складається з операції змішування з 128-бітовим ключем (побітове логічне що виключає «або»), таблична заміна (S-box) і лінійне перетворення. В останньому раунді лінійне перетворення замінюється додатковим накладанням ключа;

Кінцева перестановка;

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

Рівняння структури алгоритму:



,де

,

де  — це застосування таблиці підстановки  32 рази паралельно и  — лінійне перетворення.

Рис 1. Графічне зображення алгоритму [слайд 3]

3.1 Розшифрування та розширення ключа

Розшифрування відрізняється від шифрування тільки тим, що повинні бути використані інверсні (зворотні) таблиці замін, а також зворотні лінійні перетворення, і ключі подаються у зворотному порядку. Як і інші алгоритми, що брали участь у конкурсі AES, Serpent має можливі довжини ключа 128, 192 або 256 біт. "Неповний» ключ довжиною менше 256 біт доповнюється за наступним правилом: додається одиничний біт праворуч, за ним іде стільки нульових бітів, щоб довжина ключа стала дорівнювати 256 бітам.

3.2 Алгоритм вибору підключів із ключа

Спочату при необхідності ключ доповнюється до 256 біт і перетворюється в 33 підключа  довжиною 128 біт наступним чином:

Оригінальний ключ представляється у вигляді 8 32-бітових слів w − 8,...,w − 1 для обчислення проміжного ключа за правилом: , де  — це дробова частина золотого січення або 0x9e3779b9.

Раундовий ключі обчислюються з проміжних ключів використанням таблиць підстановок наступним чином:

Проміжні 32-бітові величини  перенумеровуються і виходять 128-бітові підключі:

При стандартному описі алгоритму ми повинні застосувати початкову перестановку IP  до раундового ключа, щоб розташувати біти ключа в належному порядку, тобто .

3.3 Перестановка, S-box, лінійне перетворення.

Початкова перестановка IP, задається наступною таблицею, де вказується позиція, на яку перейде відповідний біт (наприклад, біт 1 перейде на 32 позицію).

Рис 2. Таблиця початої перестановки [слайд 4]

В алгоритмі Serpent таблиці замін є 4-бітовими перестановками з властивостями стійкості до диференціального криптоаналізу, до лінійного криптоаналізу і тією  властивістю, що порядок вихідних біт, як функції вхідних повинен бути максимальний, тобто бути рівним 3. Таблиця підстановок генерується з відомих і добре вивчених таблиць для алгоритму DES в ітераційному процесі, поки не будуть отримані бажані диференціальні й лінійні властивості. Таким чином, створюється 8 таблиць підстановок.

Рис. 3 Таблиця підстановки [слайд 4]

Лінійне перетворення LT  задається наступною таблицею, де біти перераховані від 0 до 127 (наприклад, вихідний 2 біт утворений 2, 9, 15, 30, 76, 84, 126 бітами, складеними за модулем 2). У кожному рядку описується 4 вихідних бита, які разом складають вхідні дані на одну таблицю замін у наступному раунді. Варто зазначити, що даний набір являє собою таблицю IP (LT (FP (x))), де LT  і є те лінійне перетворення.

Ця перестановка є зворотною до початкової, тобто і задається наступною таблицею:

Рис. 4  Таблиця початої перестановки [слайд 4]

3.4 Ефективна реалізація

Бажання авторів зробити алгоритм саме таким, яким він є стає зрозумілим при розгляді його ефективної низькорівневою реалізації. Serpent був створений таким чином, щоб всі операції в процесі шифрування й розшифрування одного блоку могли бути виконані паралельно в 32 потоку. До того ж низькорівневе опис алгоритму набагато простіше, ніж стандартне опис. Ніяких початкових і кінцевих перестановок не потрібно. Шифрування складається з 32 раундів. Відкритий текст є першими проміжними даними . Після закінчення 32 раунду, i кожен раунд складається з:

1.Змішування з ключем. Проводиться побітове виключне АБО проміжних даних , з ключем довжиною 128 біт;

2. Застосування таблиць підстановок. Вхідні дані довжиною 128 біт поділяються на 4 слова по 32 біта. Таблиця підстановок, реалізована послідовністю логічних операцій (як якщо це було б реалізовано апаратно), застосовується до цих 4 слів. У результаті виходить 4 вихідних слова. Таким чином, центральний процесор виконує підстановку по 32 копій таблиці одночасно;

3.Лінійне перетворення. 32-бітові слова перетворюються наступним чином







                             [слайд 5]




В останньому раунді це лінійне перетворення замінено додатковим змішуванням з ключем

Першою причиною вибору такого лінійного перетворення є максимізація лавинного ефекту. Такі таблиці підстановок мають властивість, що зміна кожного вхідного біта призведе до зміни 2 вихідних бітів. Таким чином, кожен вхідний біт відкритого тексту вже через 3 раунду впливає на всі вихідні біти. Аналогічно кожен біт ключа впливає на результат шифрування. Друга причина полягає в простоті перетворення. Воно може бути реалізовано на будь-якому сучасному процесорі з мінімальними витратами.

Список використаних джерел

  1.  http://kiev-security.org.ua/box/1/56.shtml
  2.  http://kiwibyrd.chat.ru/aes/aes1.htm
  3.  http://www.enlight.ru/crypto/algorithms/serpent/serpent00.htm
  4.  книжка лекції
  5.  Article “Serpent: A Proposal for the Advanced Encryption Standard” - . Ross Anderson, Eli Biham, Lars Knudsen

Контрольні питання позавтра придумаю


Рекомендую одразу поставити собі
MathType6.6 (є у файлообміннику курсу і набирати формули а не картинки, на лекції покажу як правильно вставляти в wiki.tstu.edu.ua)


 

А также другие работы, которые могут Вас заинтересовать

77011. Административный надзор как способ обеспечения законности: понятие, правовые основы, органы осуществляющие, их правовое положение 28.37 KB
  Административный надзор как способ обеспечения законности: понятие правовые основы органы осуществляющие их правовое положение. Административный надзор как способ обеспечения законности представляет собой особый вид государственной деятельности специально уполномоченных органов исполнительной власти и их должностных лиц направленный на строгое и точное исполнение органами исполнительной власти коммерческими и некоммерческими организациями а также гражданами общеобязательных правил имеющих важное значение для общества и...
77012. Надзор прокуратуры за законностью в процессе осуществления исполнительной власти (государственного управления): понятие, сущность 30.34 KB
  Прокуратура наделена комплексом полномочий позволяющих прокурорам своевременно реагировать на нарушения законности в управлении принимать меры по устранению причин и условий ее нарушения восстанавливать нарушенные права привлекать к ответственности виновных лиц. Проверки исполнения законов законности издаваемых поднадзорными объектами правовых актов нарушения прав и свобод граждан осуществляются прокуратурой на основании поступивших в нее сообщений заявлений жалоб сведений о фактах нарушения законности. В целях обеспечения законности...
77013. Обжалование в суд неправомерных действий органов исполнительной власти (государственного управления) и их должностных лиц 26.2 KB
  Обжалование в суд неправомерных действий органов исполнительной власти государственного управления и их должностных лиц: правовая основа сроки обращения в суд стадии рассмотрения. Для обеспечения законности в деятельности органов исполнительной власти существенное значение имеют личные обращения граждан с жалобами предложениями и заявлениями. Выступая в личном качестве как частное лицо по собственной инициативе каждый гражданин вправе оценивать деятельность органа исполнительной власти любого должностного лица или государственного...
77014. Административно-правовое регулирование в сфере экономической деятельности 26.83 KB
  Административно-правовое регулирование в сфере экономической деятельности. Экономика – совокупность производственных отношений соответствующих данной ступени развития производительных сил общества господствующий способ производства организация структура и состояние хозяйственной жизни или какой-либо отрасли хозяйственной деятельности. В РФ гарантируются единство экономического пространства свободное перемещение товаров услуг и финансовых средств поддержка конкуренции свобода экономической деятельности признаются и защищаются равным...
77015. Административно-правовое регулирование в социально-культурной сфере 24.67 KB
  Государство охраняет труд и здоровье людей обеспечивает поддержку нетрудоспособных и пожилых граждан развивает систему социальных служб оказывающих медицинские образовательные культурные и другие услуги населению В сфере образования науки и культуры Правительство РФ обеспечивает проведение единой государственной политики в области образования определяет основные направления развития общего и профессионального образования развитие системы бесплатного образования разрабатывает и осуществляет меры государственной поддержки развития...
77016. Административно-правовое регулирование в административно-политической сфере 22.45 KB
  В эту подсистему входят Министерство иностранных дел РФ Министерство РФ по делам гражданской обороны чрезвычайным ситуациям и ликвидации последствий стихийных бедствий Министерство внутренних дел РФ Министерство обороны РФ и Министерство юстиции РФ в ведении трех последних имеются свои федеральные службы и агентства самостоятельные федеральные службы внешней разведки безопасности охраны контроля за оборотом наркотиков и фельдъегерская служба самостоятельные федеральные агентства Управление делами Президента РФ и Главное...
77017. Государственное управление как разновидность социального управления: понятие, содержание, задачи и функции, субъекты государственного управления 25.79 KB
  Государственное управление как разновидность социального управления: понятие содержание задачи и функции субъекты государственного управления. Государственное управление – вид социального управления с функционированием которого связано формирование специальной отрасли права – административного права. Также выделяют подвиды социального управления: 1 семейное социальное – осуществляемое внутри семьи; 2 общественное социальное – руководство отдельными организованными группами людей политическими партиями религиозными организациями и т....
77018. Разделение властей в Российской Федерации. Исполнительная власть: признаки, сущность, функции и механизм их осуществления 30.77 KB
  Исполнительная власть – ветвь государственной власти представленная системой органов исполнительной власти осуществляющих государственное управление делами общества обеспечивая его поступательное развитие на основе законодательства РФ и самостоятельной реализации полномочий исполнительнораспорядительного характера.Первый признак исполнительной власти ее вторичность подчиненное положение зависимость от высшей власти.Второй признак исполнительной власти ее организующий характер. Их осуществляют органы исполнительной власти имеющие...
77019. Понятие и предмет административного права. Общественные отношения, регулируемые административным правом 24.55 KB
  Виды управленческих отношений регулируемых нормами административного права: По субъектному признаку: между соподчиненными субъектами государственного управления вертикальные отношения; между субъектами исполнительной власти не находящимися в состоянии соподчинения горизонтальные отношения; между субъектами исполнительной власти и исполнительными органами местного самоуправления; между субъектами исполнительной власти и общественными объединениями; между субъектами исполнительной власти и государственными служащими; между...