Спосіб формування імітовставки

Реферат: UA 106669 U UA 106669 U 5 10 15 20 25 30 35 40 Корисна модель належить до обчислювальної техніки і може бути використана в системах імітозахисту інформації. Одні з найбільш стійких до злому способів і алгоритмів захисту інформації від нав'язування хибних даних базуються на використанні блокових алгоритмів шифрування даних. Так, для формування імітовставки можуть бути використані стандарти DES [1] у режимах СВС або CFB або ГОСТ 28147-89 [2] у режимі вироблення імітовставки. Використання вказаних алгоритмів вимагає застосування великого (рівного 16 для DES або 32 для ГОСТ 28147-89) числа раундів перемішування кожного з блоків даних, що призводить до істотної втрати продуктивності процесора в процесі формування імітовставки і обмежує застосування цього класу алгоритмів. Ніякі з відомих прийомів і способів, що використовуються для захисту від нав'язування хибних даних, не застосовують для формування імітовставки послідовності перестановок. У той же час, відомими є способи формування перестановок, які базуються на представленні чисел в позиційній системі числення з факторіальною основою [3, 4, 5], але вони не передбачають можливість формування імітовставки. Вибраний як прототип найбільш близький за сукупністю властивостей до об'єкту, що заявляється, спосіб формування перестановок реалізований у пристрої для перебору перестановок [6]. Цей спосіб характеризуються порівняно малою розмірністю перестановок і швидким зростанням розмірності оброблюваних чисел (що досягає значень у сотні і тисячі десяткових знаків), з чим пов'язане різке зниження швидкодії алгоритму обчислення перестановок, а також їх стійкості до злому. Так, у роботі [6], як і в цій заявці, для формування перестановок використана система числення з факторіальною основою, але не прийняті заходи приховування правила їх формування, а також створення імітовставки на основі перестановок. Суттю пропонованого способу формування імітовставки є те, що як імітовставка використовується вибрана в деякому порядку частина символів перестановки великої розмірності. Ця перестановка формується з послідовності символів повідомлення, перетворених у послідовність взаємозв'язаних чисел у системі числення з факторіальною основою. Для приховування закону формування імітовставки використовується змінний ключ перетворення. Спосіб формування імітовставки, що заявляється, і пристрій на його основі позбавлені вказаних недоліків - із зростанням розмірності перестановки розмірність чисел, з якими доводиться оперувати, не перевищує порядку перестановки М, а час обчислення перестановки істотно знижується, що дозволяє підвищувати криптографічну стійкість імітозахисту шляхом збільшення розмірності перестановки. Для детальнішого викладу сутності способу, що заявляється, врахуємо, що система числення з факторіальною основою (факторіальна система) забезпечує взаємно однозначний зв'язок довільного числа В(n), що належить числовому відрізку [0,М!-1] і означає номер перестановки в дискретний момент часу n, з перестановкою Р(n). Для формування перестановки її номер записується у факторіальній системі у вигляді: Bn  M1  bM1i n  M  1  i! , (1) i 0 де i  0,M  1; 0  bi n  i ; n 1 N - кількість символів у повідомленні. , 45 50 Будемо називати послідовність символів bj(n) синдромом SF(n) перестановки Р(n) і записувати його у вигляді: SF n  bM1n,bM2 n,...,b1n,b0 n , (2). Для кожного символу повідомлення обчислюється синдром перестановки, функціонально пов'язаний з попередньою частиною повідомлення, що забезпечує зчеплення всіх символів повідомлення. Зчеплення символів повідомлення проводиться за рахунок виконання операції: SF n  ƒSF n  1  t10 n , (3) де символ  означає підсумовування чисел, представлених у різних системах числення, факторіальній SF n  1 і десятковій t10 n ; SF 0 - вектор початкового завантаження. 55 У цілому, вираз SF n  ƒSF n  1  t10 n говорить про те, що наступний синдром обчислюється в результаті підсумовування підданого деякому функціональному перетворенню попереднього синдрому SF n  1 і числа t10 n , яке є n-им символом тексту, представленого в 1 UA 106669 U 5 10 15 20 25 30 десятковій системі числення. Для останнього, N-го, символу тексту обчислюється останній синдром SF(N). За цим синдромом обчислюється перестановка P(N), з якої шляхом вибору l символів формується імітовставка. Зазначимо, що перестановка P(N) має прихований зв'язок з кожним символом тексту, завдяки чому досягається ефект розсіювання - під час спроби щонайменшої модифікації тексту, наприклад у випадку заміни однієї букви (чи символу) тексту на іншу, змінюється вся імітовставка. Розглянемо процедуру перетворення синдрому в перестановку. Передусім зазначимо, що вираз (1) описує модель лототрону - урни з М пронумерованими і перемішаними кулями. З цієї урни по черзі витягаються кулі, причому перша куля вибирається з множини М куль, друга - з множини (М-1) куль, а остання визначається єдиним чином - останньою, не вибраною з кошику кулею. Послідовність цифр - номерів куль - утворює перестановку. Відповідно до цієї заявки, замість лототрону з кулями використовується оперативний запам'ятовуючий пристрій (ОЗП), у який за адресами 0, 1, 2, ..., (М-2), (М-1) записується послідовність із М слів у деякому випадковому (і приховуваному) порядку (базова перестановка чисел 0, 1, 2, ..., (М-2), (М-1). Ця базова перестановка є ключем перетворення синдрому в перестановку. Тоді на k-му кроці формування перестановки (під час обчислення k-го символу перестановки) виконуються наступні дії: 1) вибирається k-е слово сигнатури зі сторони старших розрядів - bм-k; 2) із ОЗП зчитується слово за адресою bм-k. Це слово є k-им символом перестановки: рk = R(bM-k) (R(i) - вміст комірки ОЗП за і-ою адресою); 3) зчитане слово видаляється з ОЗП, а всі інші слова переписуються відповідно до наступного правила: Ri  Ri для 0  i  bMk  1; Ri  Ri1 для bMk  i  M  k  1. Указана процедура виконується для всіх значень k від 1 до М-1. Таким чином, суттю пропонованого способу є: - приховування закону формування наступного синдрому перестановки відповідно до процедури SF n  ƒSF n  1  t10 n за рахунок приховування параметрів перетворення SF n  1  ƒSF n  1 . Як перетворення SF n  1  ƒSF n  1 можуть, наприклад, бути використані наступні операції: - операція bi  bi  zi modi для кожного факторіального коефіцієнта синдрому bi і всіх i  0,M  1, де 35 40 45 50 55 - і-ий символ ключа модифікації синдрому Z  zM1, zM2,..., z1, z0 , який тримається в секреті; - перестановка символів попередньої перестановки відповідно до ключа модифікації синдрому, який тримається в секреті, з подальшим її перетворенням у синдром. Виконання перетворення SF n  1  ƒSF n  1 забезпечує досягнення технічного результату - створення непередбачуваного останнього синдрому SF(N) з подальшим формуванням непередбачуваної перестановки P(N) і криптографічно стійкої імітовставки; - приховування параметрів перетворення останнього синдрому в перестановку (приховування базової перестановки - початкового заповнення ОЗП перетворювача синдрому в перестановку), що забезпечує досягнення технічного результату - підвищення криптографічної стійкості останньої перестановки P(N) і виробленої з неї імітовставки; - приховування правила вибору символів останньої перестановки, які використовуються для створення імітовставки. У цілому, приховуваними параметрами імітовставки - ключем імітозахисту - є набір, що складається з: - вектора початкового завантаження SF 0 ; - ключа модифікації синдрому; - ключа перетворення синдрому в перестановку; - правила вибору l символів імітовставки з М можливих. Зазначимо, що вектор початкового завантаження, ключ модифікації синдрому і ключ перетворення синдрому в перестановку є послідовностями з М символів кожна. Це означає, що повна довжина ключа формування імітовставки дорівнює lкл  3M  l . Технічний результат, що досягається, - формування криптографічно стійкої імітовставки з підвищеною швидкодією її створення за рахунок зниження розмірності оброблюваних чисел. zi 2 UA 106669 U 5 10 Заявлений технічний результат застосування запропонованого способу - формування імітовставки високої криптографічної стійкості - може бути досягнутий за допомогою пристрою, спрощена структурна схема якого показана на фіг. 1 або фіг. 2. Схеми на фіг. 1 і фіг. 2 відрізняються точкою знімання зворотного зв'язку, залежною від функції модифікації синдрому. Так, на фіг. 1 показана структурна схема генератора імітовставки, що використовує операцію SF n  ƒSF n  1 , а на фіг. 2 - операцію SF n  ƒPn  1 . На фіг. 1 і фіг. 2 прийняті наступні позначення: 1 - блок формування синдрому SF n шляхом модифікації синдрому SF n  1 з урахуванням значення t10 n ; 2 - блок формування перестановки Pn за заданим значенням SF n ; 3 - блок формування імітовставки; SF 0 - вектор початкового завантаження. Пристрій містить тривходовий блок (1) формування синдрому SF n і послідовно включені 15 20 25 блок (2) формування перестановки Pn за заданим SF n і блок (3) формування імітовставки за заданим P(N). На перший вхід блока формування синдрому (1) подаються символи інформаційної послідовності (повідомлення, що захищається від підміни) t10 n , на другий вхід - вектор початкового завантаження SF 0 , а на третій - попередній обчислюваному синдрому синдром SF n  1 або попередня перестановка Pn  1 у залежності від функції модифікації синдрому. На початку роботи із зовнішнього пристрою (наприклад, клавіатури ЕОМ) у блок формування синдрому (1) завантажується (довільно вибрана на розсуд оператора) послідовність SF 0 , що складається з М чисел, сформованих відповідно до виразу (1). Одночасно, з джерела інформації зчитується перший символ повідомлення - число t10 1 , яке також завантажується в блок (1). Блок формування синдрому (1) за заданими значеннями SF 0 і t10 1 обчислює значення першого синдрому: SF 1  SF 0  t10 1 . Для пристрою, що має структуру, представлену на фіг. 1, для формування всіх наступних синдромів, починаючи з синдрому SF(2), замість вектора початкового завантаження SF(0) використовується модифікований синдром ƒSF n  1 , після чого виконується перетворення у 30 35 40 відповідності до виразу (2): SF n  ƒSF n  1  t10 n . Для пристрою, реалізованого за схемою фіг. 2, після формування кожного синдрому в блоці формування перестановки (2) за значенням SF n  1 і ключем перетворення, що тримається в секреті, виконується формування перестановки Pn  1 , яка надходить на вхід блока формування синдрому (1). У цьому блоці за секретним ключем виконується перетворення перестановки Pn  1 у синдром, після чого виконується перетворення у відповідності до виразу (2): SF n  ƒSF n  1  t10 n . Далі процес повторюється до моменту отримання від джерела останнього символу повідомлення t10(N) і формування синдрому SF(N). За синдромом SF(N) у блоці формування перестановки (2) обчислюється перестановка P(N). За цією перестановкою у блоці формування імітовставки (3) вибираються визначені ключем у символів і видаються на вихід пристрою як імітовставки. Теоретична стійкість запропонованого способу формування імітовставки для злому ключа перетворення методом "грубої сили" угрупуванням з 1000 сучасних обчислювальних машин складає десятки мільйонів років за розмірності перестановки М ≥ 12. 45 50 55 Список джерел: 1. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования: ГОСТ 28147-89. - [Введен в действие 1990-07-01]. - М.: ИПК издательство стандартов, 1989. - 28 с. - (Государственный стандарт Союза ССР). 2. Data encryption standard (DES): FIPS PUB 46-3. - [Reaffirmed 1999-10-25]. - U.S. Department of commerce / National Institute of Standards and Technology (NIST), 1999. - 22 p. - (Federal information processing standard). 3. Кнут Дональд Э. Искусство программирования. В 7 т. Т.4. Выпуск 2. Генерация всех кортежей и перестановок. / Дональд Эрвин Кнут, Станфордский университет; пер. с англ. Ю.Г. Гордиенко. - М.: ООО «И.Д. Вильямс», 2008. - 160 с. 3 UA 106669 U 5 10 15 20 25 30 35 4. Рейнгольд Э. Комбинаторные алгоритмы. Теория и практика / Э. Рейнгольд, Ю. Нивергельт, Н. Део; пер. с англ. Е.П. Липатова; под ред. В.Б. Алексеева. - М.: Мир, 1980. - 476 с. 5. Борисенко О.А. Електронна система генерації перестановок на базі факторіальних чисел / О.А. Борисенко, І.А. Кулик, О.Є. Горячев // Вісник СумДУ. Технічні науки. - 2007. - № 1. - С. 183188. 6. Пат. 59628 Україна, МПК (2011.01) G11B 20/10 (2006.01), G06F 17/00. Пристрій для перебору перестановок / Борисенко О.А, Горячев О.Є.; заявник та патентовласник Сумський державний університет. - № u201012855; заявл. 29.10.2010; опубл. 25.05.2011, Бюл. № 10. - 5 с. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 1. Спосіб формування імітовставки, що використовує для представлення символів повідомлення чисельні значення в десятковій системі числення, який відрізняється тим, що з метою забезпечення непередбачуваності імітовставки вона формується шляхом вибору в деякому порядку, що є ключем перетворення, частини символів перестановки великої розмірності, синдром якої формується в блоці формування синдрому шляхом перетворення послідовності символів повідомлення в послідовність взаємозв'язаних чисел, що представлені у факторіальній системі числення і є синдромами перестановок, у блоці перетворення синдрому в перестановку використовується базова перестановка, відносно якої виконується формування перестановки. 2. Спосіб за п. 1, який відрізняється тим, що з метою підвищення криптографічної стійкості імітовставки в блоці формування синдрому в початковий момент часу задається і тримається в секреті вектор початкового завантаження, що є синдромом перестановки, а кожен наступний синдром формується шляхом підсумовування попереднього синдрому зпоточним значенням символу повідомлення. 3. Спосіб за п. 2, який відрізняється тим, що з метою підвищення криптографічної стійкості імітовставки для формування наступного синдрому його попереднє значення піддається модифікації, правило модифікації тримається в секреті і є елементом ключа перетворення. 4. Спосіб за п. 1, п. 2, п. 3, який відрізняється тим, що з метою подальшого підвищення криптографічної стійкості імітовставки за рахунок приховування правила перетворення синдрому в перестановку базова перестановка блока перетворення синдрому в перестановку тримається в секреті і є елементом ключа перетворення. 5. Спосіб за п. 1, п. 2, п. 3, п. 4, який відрізняється тим, що з метою зменшення витрат часу на формування імітовставки перестановка обчислюється в блоці перетворення синдрому в перестановку тільки один раз після обробки останнього символу повідомлення і формування останнього синдрому. 4 UA 106669 U Комп’ютерна верстка О. Гергіль Державна служба інтелектуальної власності України, вул. Василя Липківського, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут інтелектуальної власності”, вул. Глазунова, 1, м. Київ – 42, 01601 5