SP-мережа, або мережа замін-перестановок (англ. substitution-permutation network) — це ряд пов'язаних математичних операцій що використовуються в блочних шифрах, наприклад AES. SP-мережу також використовують , SAFER, SHARK, і .
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOWpMMk5rTDFOMVluTjBhWFIxZEdsdmJsQmxjbTExZEdGMGFXOXVUbVYwZDI5eWF6SXVjRzVuTHpNMk1IQjRMVk4xWW5OMGFYUjFkR2x2YmxCbGNtMTFkR0YwYVc5dVRtVjBkMjl5YXpJdWNHNW4ucG5n.png)
Така мережа приймає блок відкритого тексту і ключ на вході, і застосовує декілька «раундів» S-скринь і які чергуються для отримання блоку шифротексту. S- і P-скрині перетворють підблоки вхідних бітів на вихідні біти. Ці операції обираються такими щоб бути зручними для ефективного втілення в залізі, наприклад додавання за модулем 2 (XOR) і . Ключ вводиться в кожному раунді, зазвичай у вигляді ключа раунду (англ. round keys) похідного від нього. (Іноді самі S-скрині залежать від ключа.)
Розшифрування здійснюється зворотнім процесом (використанням обернених S- і P-скринь і застосуванням ключів раундів у зворотному порядку).
S-скриня замінює маленький блок бітів (дані на вході) на інший блок бітів (дані на виході). Ця заміна має бути однозначною, для гарантування оборотності (відповідно розшифрування). Зокрема довжина даних на вході може збігатись із довжиною даних на виході (зображення праворуч містить S-скрині для 4 біт на вході і виході), що не завжди має місце для S-скриньок, які також можуть змінювати довжину, наприклад DES. S-скрині це зазвичай не просто перестановка бітів. Вдала S-скринька має властивість змінювати близько половини бітів на виході через зміну одного біту на вході (лавиновий ефект). Також вона матиме властивість залежності кожного біту на виході від кожного біту на вході.
P-скриня — перестановка всіх бітів: вона отримує вихідні дані усіх S-скриньок поточного раунду, переставляє біти і передає результат S-скринькам наступного раунду. Хороша P-скриня має властивість: вихід будь-якої S-скрині розподіляється між якнайбільшою кількістю S-скринь наступного раунду.
На кожному раунді ключ раунду (отриманий з ключа за допомогою простих дій, наприклад, із використанням S- і P-скринь) додається через якусь просту групову дію, зазвичай XOR.
Одна S- або P-скриня не має особливої криптостійкості: S-скриню можна розглядати як підстановочний шифр, а P-скриню як перестановочний шифр. Однак, добре продумана SP-мережа з кількома почерговими раундами S- і P-скринь вже задовільняє властивостям плутанини і поширення (англ. confusion and diffusion) Шеннона:
- Причина для поширення така: У випадку зміни одного біту відкритого тексту і подання його на вхід S-скрині, її вихід буде різнитись кількома бітами, тоді ці зміни розповсюджуються через P-скриню поміж кількома S-скринями, отже вихід всіх цих S-скринь знов змінюються в кількох бітах і т.д.. За кілька раундів кожен біт змінюється кілька разів, отже, з рештою, шифротекст змінюється повністю псевдовипадковим чином. Зокрема, для довільного блоку на вході, якщо змінюється i-й біт, тоді ймовірність зміни j-го біта на виході приблизно половина для будь-якого i та j, а це сувора умова лавиновості.
- Причина для плутанини така сама як і для поширення: зміна одного біта ключа змінює кілька раундових ключів, і кожна така зміна поширюються мід усіма бітами, змінюючи шифротекст складним чином. І навпаки, зміна шифротексту змінить ключ повністю.
Хоча Мережа Фейстеля, яка використовує S-скрині (наприклад DES) дуже подібна до SP-мереж, тут є декілька відмінностей, що роблять кожну з них застосовнішою в певних умовах. Для даної кількості плутанини і поширення SP-мережа має більше «властивого паралелізму» (англ. inherent parallelism) отже — окремий процесор з більшою кількістю функціональних одиниць — може обробити її швидше ніж мережу Фейстеля. ЦПУ з малою кількістю функціональних одиниць — як більшість смарт-карт — не може отримати перевагу від цього властивого паралелізму.
Примітки
- "Principles and Performance of Cryptographic Algorithms" [ 10 жовтня 2007 у Wayback Machine.] by Bart Preneel, Vincent Rijmen, and Antoon Bosselaers.
- "The Skein Hash Function Family" [ 15 січня 2009 у Wayback Machine.] 2008 by Niels Ferguson, Stefan Lucks, Bruce Schneier, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, Jesse Walker page 40.
Джерела
- Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography. CRC Press, 2007.
- Douglas R. Stinson, Cryptography. Theory and Practice. Third edition. Chapman & Hall/CRC, 2006.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
SP merezha abo merezha zamin perestanovok angl substitution permutation network ce ryad pov yazanih matematichnih operacij sho vikoristovuyutsya v blochnih shifrah napriklad AES SP merezhu takozh vikoristovuyut SAFER SHARK i Shema triraundovoyi merezhi zamin perestanovok sho shifruye 16 bit vhidnogo tekstu v 16 bit vihidnogo S skrini Si s P skrini P i klyuch raundu Ki Taka merezha prijmaye blok vidkritogo tekstu i klyuch na vhodi i zastosovuye dekilka raundiv S skrin i yaki cherguyutsya dlya otrimannya bloku shifrotekstu S i P skrini peretvoryut pidbloki vhidnih bitiv na vihidni biti Ci operaciyi obirayutsya takimi shob buti zruchnimi dlya efektivnogo vtilennya v zalizi napriklad dodavannya za modulem 2 XOR i Klyuch vvoditsya v kozhnomu raundi zazvichaj u viglyadi klyucha raundu angl round keys pohidnogo vid nogo Inodi sami S skrini zalezhat vid klyucha Rozshifruvannya zdijsnyuyetsya zvorotnim procesom vikoristannyam obernenih S i P skrin i zastosuvannyam klyuchiv raundiv u zvorotnomu poryadku S skrinya zaminyuye malenkij blok bitiv dani na vhodi na inshij blok bitiv dani na vihodi Cya zamina maye buti odnoznachnoyu dlya garantuvannya oborotnosti vidpovidno rozshifruvannya Zokrema dovzhina danih na vhodi mozhe zbigatis iz dovzhinoyu danih na vihodi zobrazhennya pravoruch mistit S skrini dlya 4 bit na vhodi i vihodi sho ne zavzhdi maye misce dlya S skrinok yaki takozh mozhut zminyuvati dovzhinu napriklad DES S skrini ce zazvichaj ne prosto perestanovka bitiv Vdala S skrinka maye vlastivist zminyuvati blizko polovini bitiv na vihodi cherez zminu odnogo bitu na vhodi lavinovij efekt Takozh vona matime vlastivist zalezhnosti kozhnogo bitu na vihodi vid kozhnogo bitu na vhodi P skrinya perestanovka vsih bitiv vona otrimuye vihidni dani usih S skrinok potochnogo raundu perestavlyaye biti i peredaye rezultat S skrinkam nastupnogo raundu Horosha P skrinya maye vlastivist vihid bud yakoyi S skrini rozpodilyayetsya mizh yaknajbilshoyu kilkistyu S skrin nastupnogo raundu Na kozhnomu raundi klyuch raundu otrimanij z klyucha za dopomogoyu prostih dij napriklad iz vikoristannyam S i P skrin dodayetsya cherez yakus prostu grupovu diyu zazvichaj XOR Odna S abo P skrinya ne maye osoblivoyi kriptostijkosti S skrinyu mozhna rozglyadati yak pidstanovochnij shifr a P skrinyu yak perestanovochnij shifr Odnak dobre produmana SP merezha z kilkoma pochergovimi raundami S i P skrin vzhe zadovilnyaye vlastivostyam plutanini i poshirennya angl confusion and diffusion Shennona Prichina dlya poshirennya taka U vipadku zmini odnogo bitu vidkritogo tekstu i podannya jogo na vhid S skrini yiyi vihid bude riznitis kilkoma bitami todi ci zmini rozpovsyudzhuyutsya cherez P skrinyu pomizh kilkoma S skrinyami otzhe vihid vsih cih S skrin znov zminyuyutsya v kilkoh bitah i t d Za kilka raundiv kozhen bit zminyuyetsya kilka raziv otzhe z reshtoyu shifrotekst zminyuyetsya povnistyu psevdovipadkovim chinom Zokrema dlya dovilnogo bloku na vhodi yaksho zminyuyetsya i j bit todi jmovirnist zmini j go bita na vihodi priblizno polovina dlya bud yakogo i ta j a ce suvora umova lavinovosti Prichina dlya plutanini taka sama yak i dlya poshirennya zmina odnogo bita klyucha zminyuye kilka raundovih klyuchiv i kozhna taka zmina poshiryuyutsya mid usima bitami zminyuyuchi shifrotekst skladnim chinom I navpaki zmina shifrotekstu zminit klyuch povnistyu Hocha Merezha Fejstelya yaka vikoristovuye S skrini napriklad DES duzhe podibna do SP merezh tut ye dekilka vidminnostej sho roblyat kozhnu z nih zastosovnishoyu v pevnih umovah Dlya danoyi kilkosti plutanini i poshirennya SP merezha maye bilshe vlastivogo paralelizmu angl inherent parallelism otzhe okremij procesor z bilshoyu kilkistyu funkcionalnih odinic mozhe obrobiti yiyi shvidshe nizh merezhu Fejstelya CPU z maloyu kilkistyu funkcionalnih odinic yak bilshist smart kart ne mozhe otrimati perevagu vid cogo vlastivogo paralelizmu Primitki Principles and Performance of Cryptographic Algorithms 10 zhovtnya 2007 u Wayback Machine by Bart Preneel Vincent Rijmen and Antoon Bosselaers The Skein Hash Function Family 15 sichnya 2009 u Wayback Machine 2008 by Niels Ferguson Stefan Lucks Bruce Schneier Doug Whiting Mihir Bellare Tadayoshi Kohno Jon Callas Jesse Walker page 40 DzherelaJonathan Katz and Yehuda Lindell Introduction to Modern Cryptography CRC Press 2007 Douglas R Stinson Cryptography Theory and Practice Third edition Chapman amp Hall CRC 2006