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

Реферат: UA 106668 U UA 106668 U 5 10 Корисна модель належить до обчислювальної техніки та може бути використана для формування випадкової послідовності перестановок, де під перестановкою розуміється послідовність з Μ чисел (слів, символів) діапазону [0, М-1], кожне з яких використовується в ній тільки по одному разу. Загальне число перестановок з Μ символів дорівнює МІ, при цьому кожна з них може бути пронумерована числами відрізка числової осі [0, МІ-1]. Для створення послідовностей перестановок використовуються різні прийоми [1], в тому числі, на основі представлення чисел у позиційній системі числення з факторіальною основою [2]. Позиційна система числення з факторіальним основою (надалі - факторіальна система) забезпечує виконання арифметичних операцій і взаємно однозначний зв'язок довільного числа В(n), що належить числовому відрізку [0, М!-1] і позначає номер перестановки в дискретний момент часу n, з перестановкою Р(n). Для формування перестановки її номер у факторіальній системі записується наступним чином: Bn  15 20 M1  bi n  i! , (1) i0 де i  0,M  1 , 0  bi n  i . Результат обчислення виразу за формулою (1) є інваріантним по відношенню до розташування символів bi n у номері перестановки (від старшого до молодшого чи від молодшого до старшого). Будемо називати послідовність символів bi n синдромом Sn і записувати його у вигляді: Sn  bM1, bM 2, bM3 , bM 4 ........b4 , b3 , b2, b1, b0 . 25 30 35 40 45 50 (2) За цим синдромом Sn обчислюється перестановка Pn . Для обчислення послідовності перестановок з використанням факторіальної системи може бути використаний генератор, який містить: - генератор числа Bn (у разі формування послідовності перестановок у лексикографічному порядку цей генератор являє собою лічильник, який змінює свій стан на +1 на початку формування кожної наступної перестановки); - перетворювач числа Bn у факторіальну систему; - формувач синдрому Sn , що виконує перетворення номера перестановки в синдром: Bn  Sn ; - формувач перестановки Pn , що виконує перетворення синдрому в перестановку: Sn  Pn . Відомі і викладені в роботах [2, 3] способи формування перестановок відрізняються правилами виконання перетворень Sn  Pn . Відповідно до цих робіт, найбільш розвиненими є способи формування перестановок, засновані на додаванні +1 до числа Bn і перерахуванні перестановок у лексикографічному порядку. Основною ознакою лексикографічного порядку формування перестановок є принцип обчислення числа Bn  Bn  1  1 з наступним обчисленням перестановки Pn . Такий принцип формування наступної перестановки призводить до того, що послідовності перестановок є передбачуваними. Це означає, що по кожній перестановці можна визначити всі наступні перестановки. Як наслідок, такі генератори не мають криптографічну стійкість і не можуть бути використані в ряді практичних застосувань, наприклад, таких як електронні системи розіграшу лотерей, жеребкування спортивних змагань, тасування карт в електронних іграх, системи криптографічного захисту інформації. Ця обставина стимулює процес створення нових способів формування послідовностей перестановок і пристроїв на їх основі, які породжують випадковий порядок перерахування перестановок і мають властивості відтворюваності і непередбачуваності. Зауважимо, що під властивістю відтворюваності розуміється можливість відтворення послідовності перестановок під час рознесення в просторі і (або) часу процесу їх формування. 1 UA 106668 U 5 10 15 20 25 30 35 Найбільш близьким до способу формування послідовності перестановок, що заявляється, є спосіб, реалізований у пристрої для перерахування перестановок [4]. Цей спосіб ґрунтується на використанні факторіальної системи та передбачає виконання операцій Bn  Sn  Pn . Пристрій, який його реалізує, містить: - генератор синдрому - факторіальний лічильник, на вхід якого подається +1 для обчислення номеру кожної наступної перестановки; - перетворювач "синдром - перестановка" Sn  Pn . Спосіб формування перестановок, реалізований прототипом, ґрунтується на обчисленні наступної перестановки за попередньою відповідно до правила: Sn  Sn  1  1 і наступного перетворення синдрому в перестановку Sn  Pn , що породжує передбачувану послідовність перестановок і, отже, має обмежене застосування. Суттю пропонованого способу є: - приховування закону формування наступного синдрому перестановки за попереднім, що забезпечує досягнення технічного результату - створення непередбачуваної послідовності перестановок для забезпечення їх криптографічного стійкості; - приховування закону перетворення синдрому перестановки в перестановку, що забезпечує досягнення технічного результату - підвищення непередбачуваності послідовності і, як наслідок, підвищення криптографічної стійкості послідовності перестановок. Досягнутий технічний результат - формування відтворюваної, непередбачуваної, некорельованої випадкової послідовності перестановок. Такий технічний результат досягається за рахунок відмови від лексикографічного порядку формування перестановок і використання обчислення перестановки за синдромом, значення якого визначається наступним чином: Sn  Sn  1  tn , де tn - випадкове зміщення. Зауважимо, що операція додавання виконується в факторіальній системі. Суттєво те, що якщо тримати в секреті послідовність tn , то послідовність перестановок стає непередбачуваною, зберігаючи при цьому властивість відтворюваності. Використання модифікації номеру наступної перестановки за попередньою за її синдромом Sn  Sn  1  tn з подальшим перетворенням Sn  Pn призводить до спрощення процедури обчислення перестановки, робить послідовність перестановок випадковою, руйнує кореляцію між суміжними перестановками. Для реалізації процедури обчислення Sn за значеннями Sn  1 і tn створені правила обчислення: - кожного з чисел b j n за заданими b j n  1 і tn , - символів переносу з молодшого розряду в старший -  j n . Правила мають вигляд: b j nb j n  1   j n j 1 , (3) де a - лишок (залишок) числа a по модулю b ; b 40  b j n  1   j 1n   j n   , j 1   (4) де a - ціла частина (функція "підлога") числа a , j  0,M  1 , 45 1n  tn . Особливістю наведених правил є та обставина, що операція Sn  Sn  1  tn виконується для значень Sn  1 і tn , представлених в різних системах числення - Sn  1 представлено в факторіальній системі, tn - у десятковій. Перетворення синдрому в перестановку здійснюється наступним чином. 2 UA 106668 U 5 10 15 20 25 30 35 40 45 50 У оперативний запам'ятовуючий пристрій (ОЗП) перетворювача, що містить Μ комірок пам'яті за адресами 0, 1, 2,…, М-1, заноситься базова перестановка Р(0) - одна з перестановок натуральної послідовності чисел 0, 1, 2, 3,…, М-1, яка використовується як елемент ключа перетворення, що тримається в секреті. Перетворення синдрому в перестановку починається зі старших розрядів синдрому, для чого зчитується вміст комірки ОЗП за адресою bM1n . Її вміст є першим символом перестановки. Далі за адресами 0, 1, 2,…, М-2 перезаписуються всі символи, що раніше містилися в ОЗП, окрім використаного в перестановці. Після цього з ОЗП зчитується символ, розміщений за адресою bM 2 n , який є другим символом перестановки. Процес зчитування та перезапису вмісту ОЗП повторюється, поки не буде вибраний останній символ перестановки. Спосіб формування випадкової послідовності перестановок, що заявляється, забезпечує перетворення синдрому в перестановку в режимах відкритого та прихованого перетворення. У режимі прихованого перетворення, крім значення tn , можуть зберігатися в секреті або піддаватися модифікації й інші параметри процесу формування перестановок: значення Sn  1 та базової перестановки Ρ(0). Приховане перетворення (якщо невідомий ключ) робить неможливим відновлення за перестановкою її синдрому, її порядкового номеру та правила перетворення синдрому в перестановку. Заявлений технічний результат від застосування запропонованого способу формування некорельованої послідовності перестановок, може бути досягнутий за допомогою пристрою, спрощена структурна схема якого (адаптована для створення генератора перестановок на однокристальній ЕОМ) показана на фіг. Пристрій містить блок (1) обчислення синдрому Sn за заданим значенням Sn  1 і tn , блок (2) обчислення перестановки Р(п) за заданим Sn , генератор (3) випадкових чисел (формувач числа tn ) і пристрій управління (4). У початковий момент часу з зовнішнього пристрою (наприклад, клавіатури ЕОМ) у блок (1) обчислення синдрому Sn завантажується довільно вибрана на розсуд оператора послідовність 5(0) із Μ чисел (наприклад, (0, 1, 2,…, М-1)), яка є вектором початкового завантаження (ВПЗ). Одночасно генератор випадкових чисел (3), наприклад лінійний конгруентний генератор, формує випадкове число tn , яке також завантажується в блок (1). Блок (1) обчислення синдрому за заданими S(0) і t(1) за формулами (3) і (4) обчислює значення першого синдрому S(1)=S(0)+t(1). Блок (2) формування перестановки обчислює першу перестановку Ρ(1) за заданим S(1). У залежності від вибраного режиму роботи (відкрите чи приховане перетворення) для формування наступного синдрому і, відповідно, наступної перестановки, пристрій управління (4) по шині управління (ШУ) задає блоку (1) обчислення синдрому значення S(1) (яке може бути піддане модифікації для режиму прихованого перетворення) і нове випадкове значення t(2). Так, перестановка за перестановкою, формується відтворювана непередбачувана випадкова послідовність перестановок, яка виводиться споживачеві. Джерела інформації: 1. Дональд Э. Кнут. Искусство программирования. В 7 т. Т.4. Выпуск 2. Генерация всех кортежей и перестановок. /Дональд Эрвин Кнут, Станфордский университет; пер. с англ. Ю.Г. Гордиенко. - М.: ООО "И.Д. Вильяме", 2008. - 160 с. 2. Э. Рейнгольд. Комбинаторные алгоритмы. Теория и практика /Э. Рейнгольд, Ю. Нивергельт, Н. Део; пер. с англ. Е.П. Липатова; под ред. В.Б. Алексеева. - М.: Мир, 1980. - 476 с. 3. Борисенко О.А. Електронна система генерації перестановок на базі факторіальних чисел /О.А. Борисенко, І.А. Кулик, О.Є. Горячев //Вісник СумДУ. Технічні науки. - 2007. - № 1. - С. 183188. 4. Пат. 59628 Україна, МПК (2011.01) G11B 20/10 (2006.01), G06F 17/00. Пристрій для перебору перестановок / Борисенко О.А, Горячев О.Є.; заявник та патентовласник Сумський державний університет. - № u201012855; заявл. 29.10.2010; опубл. 25.05.2011, Бюл. № 10. - 5 с. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 55 1. Спосіб формування випадкової послідовності перестановок, що використовує для представлення синдрому перестановки позиційну систему числення з факторіальною основою, а також блок перетворення послідовності символів синдрому у перестановку, який 3 UA 106668 U 5 10 15 відрізняється тим, що для формування випадкової послідовності перестановок у блоці формування синдрому використовується додатковий генератор випадкових чисел, значення з виходу якого підсумовуються з синдромом попередньої перестановки, а результат цього перетворення визначає синдром наступної перестановки, у блоці перетворення синдрому в перестановку використовується базова перестановка, відносно якої виконується це перетворення. 2. Спосіб за п. 1, який відрізняється тим, що з метою зниження кореляції між сусідніми перестановками та підвищення їх непередбачуваності для формування наступного синдрому і, відповідно, наступної перестановки, попереднє значення синдрому може бути модифіковане після формування однієї або декількох перестановок, правило модифікації зберігається в секреті і є елементом ключа перетворення. 3. Спосіб за п. 1 або п. 2, який відрізняється тим, що з метою зниження кореляції між сусідніми перестановками та підвищення їх непередбачуваності базова перестановка блока перетворення синдрому в перестановку зберігається в секреті і є елементом ключа перетворення. Комп’ютерна верстка Л. Ціхановська Державна служба інтелектуальної власності України, вул. Василя Липківського, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут інтелектуальної власності”, вул. Глазунова, 1, м. Київ – 42, 01601 4