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

{{Картка блочного шифру
|назва         = Present 
|опублікований = CHES, 2007-08-23;
|створений     = [[2007]] рік
|розробник     = Богданов, Кнудсен, Леандр, Паар, Пошманн, Робшо, Соа, Вікельсоа
|размір ключа  = 80 біт (Present-80) і 128 біт (Present-128)
|размір блоку  = 64 біт
|число раундів = 31
|тип           = [[SP-мережа]]
}}

'''Present'''&nbsp;— [[блочний шифр]] з розміром блоку 64 біта, довжиною ключа 80 або 128 біт і кількістю раундів 32.

Основне призначення даного шифру&nbsp;— використання в спеціальних приладах, на зразок [[RFID]] міток або [[мережа сенсорів|мереж сенсорів]].

Є одним з найбільш компактних криптоалгоритмів, існує оцінка, що для апаратної реалізації PRESENT потрібно приблизно в 2.5 рази менше логічних елементів ніж для [[Advanced Encryption Standard|AES]] або [[CLEFIA]].<ref name="KUL">{{cite web|url=http://www.kuleuven.be/english/news/ultra-lightweight-encryption-method-becomes-international-standard|title=Ultra-lightweight encryption method becomes international standard|archiveurl=https://www.webcitation.org/6FfMFhvJ4?url=http://www.kuleuven.be/english/news/ultra-lightweight-encryption-method-becomes-international-standard|archivedate=2013-04-06|deadurl=yes|accessdate=2012-02-28|author=Katholieke Universiteit Leuven}}</ref><ref>Masanobu Katagi, Shiho Moriai, [http://www.iab.org/wp-content/IAB-uploads/2011/03/Kaftan.pdf Lightweight Cryptography for the Internet of Things] {{Webarchive|url=https://web.archive.org/web/20180623061224/https://www.iab.org/wp-content/IAB-uploads/2011/03/Kaftan.pdf |date=23 червня 2018 }}, 2011</ref>

Даний шифр був представлений на конференції CHES 2007. Автори: Богданов, Кнудсен, Леандр, Паар, Пошманн, Робшо, Соа, Вікельсоа. Автори працюють в [[Orange|Orange Labs]], [[Рурський університет|Рурському університеті в Бохумі]] та [[Данський технічний університет|Данському технічному університеті]].

== Схема шифрування ==
[[Файл:Present_cypher_alg.png|міні|Схема шифрування]]
Основним критерієм при розробці шифру була простота реалізації при забезпеченні середнього рівня захищеності. Також важливим моментом була можливість ефективної апаратної реалізації.

Являє собою [[SP-мережа|SP-мережу]] з 31 раундом шифрування. Кожен раунд складається з операції XOR з раундовим ключем <math>K_i</math>, що складається з 64 біт, які визначають функцію оновлення ключа.

Далі проводиться розсіююче перетворення&nbsp;— блок пропускається через 16 однакових 4-бітних [[S-скриня|S-скринь]]. Потім блок піддається перемішуючому перетворенню (перестановка біт).<ref>Панасенко, Смагин, Облегченные алгоритмы шифрования // 2011 </ref>

=== S-скрині ===
У шифрі використовуються 16 однакових 4-бітних S-скринь:
{| class="wikitable" style="margin-bottom: 10px;"
| x
| 0
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
| 9
| A
| B
| C
| D
| E
| F
|-
|S(x)
| C
| 5
| 6
| B
| 9
| 0
| A
| D
| 3
| E
| F
| 8
| 4
| 7
| 1
| 2
|}
S-скриня створена таким чином, щоб збільшити опір до [[лінійний криптоаналіз|лінійного]] та [[диференційний криптоаналіз|диференційного криптоаналізу]]. Зокрема:

# <math>{\displaystyle P(\forall x\in [0,F]:S(x)+S(x+\Delta _{i})=\Delta _{o})<=4}  </math>, де <math>\Delta_i, \Delta_o</math>&nbsp;— будь-які можливі вхідні і вихідні диференціали не рівні нулю.

# <math>{\displaystyle P(\forall x\in [0,F]:S(x)+S(x+\Delta _{i})=\Delta _{o})=0}  </math>, де <math>wt(\Delta_i) = wt(\Delta_o) = 1</math>.

{{питання|Що таке P і <math>wt</math>?}}

=== P-скриня ===
Блок, що перемішує біти, заданий наступною матрицею:
{| class="wikitable" style="margin-bottom: 10px;"
| i
| 0
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
| 9
| 10
| 11
| 12
| 13
| 14
| 15
|-
| P(i)
| 0
| 16
| 32
| 48
| 1
| 17
| 33
| 49
| 2
| 18
| 34
| 50
| 3
| 19
| 35
| 51
|}
{| class="wikitable" style="margin-bottom: 10px;"
| i
| 16
| 17
| 18
| 19
| 20
| 21
| 22
| 23
| 24
| 25
| 26
| 27
| 28
| 29
| 30
| 31
|-
| P(i)
| 4
| 20
| 36
| 52
| 5
| 21
| 37
| 53
| 6
| 22
| 38
| 54
| 7
| 23
| 39
| 55
|}
{| class="wikitable" style="margin-bottom: 10px;"
| i
| 32
| 33
| 34
| 35
| 36
| 37
| 38
| 39
| 40
| 41
| 42
| 43
| 44
| 45
| 46
| 47
|-
| P(i)
| 8
| 24
| 40
| 56
| 9
| 25
| 41
| 57
| 10
| 26
| 42
| 58
| 11
| 27
| 43
| 59
|}
{| class="wikitable" style="margin-bottom: 10px;"
| i
| 48
| 49
| 50
| 51
| 52
| 53
| 54
| 55
| 56
| 57
| 58
| 59
| 60
| 61
| 62
| 63
|-
| P(i)
| 12
| 28
| 44
| 60
| 13
| 29
| 45
| 61
| 14
| 30
| 46
| 62
| 15
| 31
| 47
| 63
|}

=== Зміна ключів ===
Як ключ раунду <math>K_i</math> використовуються 64 лівих біт з регістра <math>K</math>, який містить ввесь ключ. Після отримання ключа раунду регістр <math>K</math> оновлюється за наступним алгоритмом:

# <math>[k_{79} k_{78} . . . k_1 k_0 ] = [k_{18} k_{17} . . . k_{20} k_{19} ]</math>
# <math>[k_{79} k_{78} k_{77} k_{76} ] = S[k_{79} k_{78} k_{77} k_{76} ]</math>
# <math>[k_{19}k_{18}k_{17}k_{16}k_{15}]=[k_{19}k_{18}k_{17}k_{16}k_{15}]\oplus </math> лічильник_раунду

== Криптостійкість ==

=== Диференціальний криптоаналіз ===
Даний шифр володіє властивістю, що будь-яка 5-раундова диференційна характеристика зачіпає щонайменше 10 S-скриньок. Таким чином, наприклад, для 25 раундів шифру будуть задіяні як мінімум 50 S-скриньок, і ймовірність характеристики не перевищує <math>2^{-100}</math>. Атака на версії шифру з 16 раундів шифрування вимагає <math>2^{64}</math> шифротексту, <math>2^{64}</math> доступів до пам'яті, <math>2^{32}</math> 6-бітних лічильників і <math>2^{24}</math> осередків пам'яті для [[Геш-таблиця|геш-таблиці]]. Ймовірність знаходження ключа <math>P\approx 0.999</math>.

=== Лінійний криптоаналіз ===
Максимальний нахил апроксимованої прямої для чотирьох раундів не перевищує <math>\frac{1}{2^7}</math>. Таким чином, для 28 раундів максимальний нахил становитиме <math>2^6 * {\left(\frac{1}{2^7}\right)^7} = 2^{-43}</math>. Тому, якщо врахувати, що для злому 31 раунду необхідна апроксимація для 28, то знадобиться <math>2^{84}</math> відомих пар текст-шифротекст, що перевищує розмір можливого тесту для шифрування.

=== Інші методи ===
* Алгебраїчна атака з використанням диференціальних характеристик. Основна ідея&nbsp;— представити шифр системою рівнянь нижчого порядку. Далі, для декількох пар текст-шифротекст відповідні їм системи рівнянь об'єднуються. Якщо як ці пари вибрати пари, відповідні деякій характеристиці <math>\delta</math> з імовірністю '''p''', то система справджуватиметься з цією ймовірністю '''p''' і рішення може бути знайдене при використанні <math>\frac{1}{p}</math> пар. Очікується, що вирішення такої системи простіше, ніж початкової, відповідній одній парі текст-шифротекст. Для Present-80 з 16 раундами дана атака дозволяє дізнатися чотири біти ключа за <math>\approx 6*2^{12}</math> секунд.
* Метод статистичного насичення. В даній атаці використовуються недоліки блоку перемішування бітів. Для злому Present-80 з 24 раундами потрібна пара текст-шифротекст <math>\approx 2^{60}</math> обчислень <math>\approx 2^{20}</math>.

== Порівняння з іншими шифрами ==
У таблиці нижче наведене порівняння характеристик шифру Present-80 з характеристиками інших блочних і [[Потоковий шифр|потокових шифрів]].<ref>PRESENT: An Ultra-Lightweight Block Cipher, Table 2</ref>
{| class="wikitable sortable" style="margin-bottom: 10px;"
! Назва
! Розмір ключа
!Розмір блоку
! Пропускна здатність ([[Біт на секунду|кб/c]])
! Площа (в&nbsp;{{нп|Gate_equivalent|GE|en|Gate_equivalent}})
|-
| Present-80
| 80
| 64
| 200
| 1570
|-
| AES-128
| 128
| 128
| 12.4
| 3400
|-
| Camelia
| 128
| 128
| 640
| 11350
|-
| DES
| 56
| 64
| 44.4
| 2309
|-
| DESXL
| 184
| 64
| 44.4
| 2168
|-
| Trivium
| 80
| 1
| 100
| 2599
|-
| Grain
| 80
| 1
| 100
| 1294
|}

== Застосування ==
У 2012 році організації [[Міжнародна організація зі стандартизації|ISO]] і [[Міжнародна електротехнічна комісія|IEC]] включили алгоритми PRESENT і CLEFIA в [[міжнародний стандарт]] полегшеного шифрування ISO/IEC 29192-2:2012.<ref>{{cite web|url=http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=56552|title=ISO/IEC 29192-2:2012|author=ISO|accessdate=2012-02-28|archiveurl=https://www.webcitation.org/6Fe4bAgHy?url=http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=56552|archivedate=2013-04-05|deadurl=yes}}</ref><ref name="KUL" /><ref name="ospwho">[http://www.osp.ru/news/2012/0228/13011754/ Алгоритм шифрования, предложенный как «более легкая» альтернатива AES, стал стандартом ISO] {{Webarchive|url=https://web.archive.org/web/20180427184108/https://www.osp.ru/news/2012/0228/13011754/ |date=27 квітня 2018 }} // Osp.ru, 02-2012</ref>

На базі PRESENT була створена компактна геш-функція H-PRESENT-128.<ref>[http://www.pvti.ru/data/file/bit/bit_1_2011_6.pdf LW-КРИПТОГРАФИЯ: ШИФРЫ ДЛЯ RFID-СИСТЕМ] {{Webarchive|url=https://web.archive.org/web/20130728075123/http://www.pvti.ru/data/file/bit/bit_1_2011_6.pdf |date=28 липня 2013 }}, С. С. Агафьин // Безопасность информационных технологий № 2011-4</ref><ref>[http://www.iacr.org/cryptodb/archive/2011/CRYPTO/video/rump/71040a68ec50a72283954e7d1f0a36ac.pdf Observations on H-PRESENT-128] {{Webarchive|url=https://web.archive.org/web/20170517152906/http://www.iacr.org/cryptodb/archive/2011/CRYPTO/video/rump/71040a68ec50a72283954e7d1f0a36ac.pdf |date=17 травня 2017 }}, Niels Ferguson (Microsoft)</ref>

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

== Посилання ==
* [https://web.archive.org/web/20101217063636/http://www.ist-ubisecsens.org/publications/present_ches2007.pdf PRESENT: An Ultra-Lightweight Block Cipher] {{недоступне посилання}}
* [http://www.ei.rub.de/media/ei/lehrmaterialien/Seminar_kryptanalyse_und_beweisbare_sicherheit/AlgDiffAttacks.pdf Algebraic Techniques in Differential Cryptanalysis] {{Webarchive|url=https://web.archive.org/web/20151031200434/https://www.ei.rub.de/media/ei/lehrmaterialien/Seminar_kryptanalyse_und_beweisbare_sicherheit/AlgDiffAttacks.pdf |date=31 жовтня 2015 }}
* [http://www.springerlink.com/index/n6u0g6g6774w8888.pdf Differential Cryptanalysis of Reduced-Round PRESENT]{{Недоступне посилання|date=листопада 2019 |bot=InternetArchiveBot }}
* Weak Keys of Reduced-Round PRESENT for Linear Cryptanalysis, Kenji Ohkuma // Lecture Notes in Computer Science Volume 5867, 2009, pp 249—265 [[doi:10.1007/978-3-642-05445-7_16]]
* [http://www.springerlink.com/content/e62232827002n882/ A Statistical Saturation Attack against the Block Cipher PRESENT]{{Недоступне посилання|date=листопада 2019 |bot=InternetArchiveBot }}

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

[[Категорія:SP-мережа]]