Спосіб шифрування інформації

Реферат: Спосіб шифрування інформації, при якому виконують поділ символів відкритого тексту (ВТ) на 2 блоки по  символів у блоці, які утворюють матрицю стовпчик, а ключ утворюють з  кількості символів, які записують як квадратну матрицю ×. Символи шифрованого тексту (ШТ) формують в процесі перемноження поблоково матриці стовпчика і квадратної матриці ключа шифрування, які попередньо перетворюють у відповідні числа по модулю n, де n - кількість символів ВТ. Дешифрування шифрованого тексту виконують поділом символів ШТ на блоки (по  символів у блоці) і перемноження матриці стовпчика і квадратної матриці ключа дешифрування, які перетворюють у відповідні числа по модулю n. Перед множенням на матрицю ключа шифрування у відкритий текст перед і після кожного символу ВТ вставляють додаткові маскуючі символи. При цьому маскуючі символи на кожному кроці вставляння визначаються найменшою частотою вживання цього символу (з врахуванням вставлених маскуючих символів) у відкритому тексті з маскуючими символами, а при дешифруванні вилучають маскуючі символи в такому порядку, як вони вставлялися перед множенням на матрицю ключа шифрування. UA 99073 U (54) СПОСІБ ШИФРУВАННЯ ІНФОРМАЦІЇ UA 99073 U UA 99073 U 5 10 15 20 25 30 35 40 45 50 55 60 Корисна модель належить до криптографії і може бути використана при розробці криптографічних систем захисту інформації, захисту інформації в комп'ютеризованих системах і т.п. Відомий спосіб шифрування інформації Віженера (Fred Cohen. A Short History of Cryptography // Introductory Information Protection. - 1987. - ISBN 1-878109-05-7) на основі поліалфавітних перетворень елементів відкритого тексту (ВТ). Суть цього способу полягає в заміні кожного елемента ВТ на елемент шифрованого тексту (ШТ), згідно з буквою ключа, причому для кожної букви ключа є відповідний алфавіт заміни елементів ВТ. Якщо довжина ключа менша за довжину ВТ, то ключ повторюється стільки разів, щоб весь масив ВТ мав певний елемент ключа для перетворення. Недоліком даного способу для шифрування інформації є те, що при великих обсягах ВТ можна знаходити повторення в ШТ, які будуть розташовуватись на віддалях, кратних довжині ключа k. Найбільш близьким по технічній суті до способу шифрування, що заявляється, є блоковий спосіб шифрування інформації на основі шифра Хілла (Lester S. Hill. Cryptography in an Algebraic Alphabet". "The American Mathematical Monthly". - 1929, U.S. Patent 1 845 947. Лестер С. Хилл. Пристрій для шифрування. 1929, https://ru.wikipedia.org/wiki/Шифр_Xилла), при якому блок з k символів перетворюється в послідовність чисел (наприклад у відповідності до порядкового номера символу у алфавіті) і перший блок довжиною k (починаючи з першого символу ВТ) утворює матрицю стовпчик і множиться квадратна матриця ключ А (розміром k×k) на матрицю стовпчик В з k чисел, які відповідають k першим символам ВТ. Наступні символи ВТ послідовно діляться на наступні блоки по k символів і процес шифрування закінчується, коли всі букви ВТ будуть зашифровані. Ключ k може бути довільним і його тримають у таємниці. Для -1 -1 розшифрування ШТ необхідно обчислити обернену матрицю А (причому А·А =1, де 1 - це одинична матриця) і послідовно множити k символів ШТ на обернену матрицю, і процес дешифрування завертається тоді, коли всі символи (по k символів в блоці) будуть -1 розшифровані в процесі множення кожного блока ШТ на обернену матрицю А . При обчисленнях (при перемноженні двох матриць) можуть бути великі числа і тоді використовуються засоби пониження значень шкали чисел з допомогою модулярної арифметики. Величина модуля звичайно дорівнює кількості символів в алфавіті ВТ. Основним недоліком даного способу шифрування інформації є його невисока стійкість. Довжина блока (як і довжина ключа k чи розмірність матриці ключа) нескладно виявляється при статистичній обробці ШТ, тому що відстані між повтореннями при такому способі шифрування будуть на віддалях, кратних довжині ключа k. Якщо припустити, що матриці, які можуть використовуватись в цьому способі, можуть мати розміри 3×3 або 4×4, або 5×5, або 6×6, …. Матриці вищих порядків приводять до складних обчислень як оберненої матриці, так і самого процесу шифрування-дешифрування (складність множення матриць високих порядків росте в геометричній прогресії з розміром матриці). Невисока стійкість способу шифрування визначається тим, що цей спосіб шифрування є 2 лінійним, при перехопленні незначного об'єму ШТ (2×k символів) ключ можна вичислити засобами лінійної алгебри. Крім цього матриця буде мати обернену матрицю тільки в тому випадку, коли її детермінант не рівний нулю і не має спільних дільників з числом,яке дорівнює величині модуля. Спосіб шифрування на основі шифру Хілла - поліграмний блоковий шифр підстановки, заснований на лінійній алгебрі. Цей спосіб шифрування давав можливість зашифровувати більш ніж три символи за один цикл. Шифрування інформації відбувається наступним чином. Кожній букві відкритого тексту присвоюється число. Для латинського алфавіту часто використовується найпростіша схема: А=0, В=1,…, Z=25, але це не є істотною властивістю шифру. Блок з n букв розглядається як n-мірний вектор і множиться на n×n матрицю по модулю 26. (якщо як підстава модуля використовується число більше 26, то можна використовувати іншу числову схему - крім букв в алфавіт включають розділові знаки.) Ключем для шифру Хілла є матриця, яка представляється словом чи довільним набором букв. Для шифрування використовується числова квадратна матриця (3×3, 4×4, 5×5,…). Матриця повинна мати обернену матрицю, щоб була можлива операція розшифрування. Щоб розшифрувати повідомлення, необхідно звернути шифротекст назад у вектор і потім просто помножити на обернену матрицю ключа. Необхідно обговорити деякі складнощі, пов'язані з вибором шифрувальної матриці. Не всі матриці мають обернену матрицю. Матриця буде мати обернену в тому і тільки в тому випадку, коли її детермінант не дорівнює нулю і не має спільних дільників з основою модуля. Таким чином, якщо ми працюємо з основою модуля 26, то детермінант повинен бути ненульовим і не ділитися на 2 і 13. Якщо детермінант матриці 1 UA 99073 U 5 10 дорівнює нулю або має спільні дільники з основою модуля, то така матриця не може використовуватися в шифрі Хілла і повинна бути обрана інша матриця (в іншому випадку шифротекст буде неможливо розшифрувати). Тим не менш, матриці, які задовольняють вищенаведеним умовам, існують в достатку. Шифрування. Для кожної букви латинського алфавіту є відповідне їй число: А=0, В=1,…, Z=25. Блок з n букв представляється як n-мірний вектор і множиться n×n матрицю по модулю 26. (якщо використовується число більше 26, то можна використовувати іншу числову схему і добавити розділові знаки.) Матриця є ключем шифру. Матриця повинна мати обернену матрицю, щоб була можлива процедура розшифрування. В наступних прикладах використовуються латинські букви від А до Z. відповідні їм числові значення наведені в таблиці. А B C D Е F G Н I J K L M N O Р Q R S Т V V W X Y Z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 15 20 Розглянемо процес зашифрування слова 'DOG' з допомогою ключа (GYBNQKURP у буквенному представленні) і відповідному числовому представленні у вигляді матриці розміром 3×3:  6 24 1     13 16 10   20 17 15   . Так як букві 'D' відповідає число 3, 'О' - 14, 'G' - 6, то повідомлення можна представити як матрицю стовпець (або вектор): 3    14  6  . В цьому випадку зашифрований вектор буде:  6 24 1   3   360   22           13 16 10    14    323    11  (mod 26)  20 17 12   6   388   24          , 25 30 35 40 що відповідає шифрованому тексту 'WLY'. Ми бачимо, що кожна буква ШТ змінилася. Шифр Хілла досягнув дифузії по Шеннону, і n-розмірний шифр Хілла може досягнути дифузії n символів за раз. Розшифрування. Для того, щоб розшифрувати повідомлення, необхідно перетворити символи шифрованого тексту у вектор і перемножити на обернену матрицю ключа (IFKVIVVMI у буквенному представленні). (Існують стандартні методи обчислення обернених матриць, які широко використовуються у матричному численні). Обернена матриця в нашому прикладі буде:  8 5 10     21 8 21  21 12 8   . Якщо перемножити матрицю ключа на матрицю стовпчик ШТ 'WLY', тоді отримаємо:  8 5 10   22   471   3           21 8 21   11   1054   14  (mod 26)  21 12 8   24   786   6          . А результуюча матриця стовпчик дає можливість відновити символи відкритого тексту 'DOG'. Необхідно відмітити деякі особливості з вибором матриці ключа і оберненої матриці. Матриця буде мати обернену матрицю тільки в тому випадку, коли її детермінант не рівний нулю і не має спільних дільників з числом, яке є основою модуля. В основу корисної моделі поставлена задача удосконалити спосіб шифрування інформації шляхом введення маскуючих символів та встановлення їх серед символів відкритого тексту (ВТ), що ускладнює процедуру розпізнавання ВТ при переборі можливих варіантів шифрів і переборі ключів для кожного шифру та приводить до підвищення крипостійкості. 2 UA 99073 U 5 10 15 20 25 30 35 40 45 50 Поставлена задача вирішується тим, що в запропонованому способі шифрування інформації, при якому виконують поділ символів відкритого тексту (ВТ) на блоки по μ символів у 2 блоці, які утворюють матрицю стовпчик, а ключ утворюють з μ кількості символів, які записують як квадратну матрицю μ×μ, і символи шифрованого тексту (ШТ) формують в процесі перемноження поблоково матриці стовпчика і квадратної матриці ключа шифрування, які попередньо перетворюють у відповідні числа по модулю n, де n - кількість символів ВТ, дешифрування шифрованого тексту виконують поділом символів ШТ на блоки (по μ символів у блоці) і перемноження матриці стовпчика і квадратної матриці ключа дешифрування, які перетворюють у відповідні числа по модулю n, де n - кількість символів ВТ, згідно з корисною моделлю, перед множенням на матрицю ключа шифрування у відкритий текст перед і після кожного символу ВТ вставляють додаткові маскуючі символи, причому маскуючі символи на кожному кроці вставляння визначаються найменшою частотою вживання цього символу (з врахуванням вставлених маскуючих символів) у відкритому тексті з маскуючими символами, а при дешифруванні вилучають маскуючі символи в такому порядку, як вони вставлялися перед множенням на матрицю ключа шифрування. Встановлення перед процедурою шифрування перед кожним символом і після кожного символу ВТ додаткових маскуючих символів, причому при довжині блока шифрування μ необхідно вставляти таку кількість маскуючих символів (перед і після символу ВТ), щоб в кожний блок шифрування потрапляв хоча б один символ ВТ. Хоча ця вимога не є критичною для виконання, занадто багато маскуючих символів вставляти недоцільно, так як досягнення результату може бути при незначному збільшенні кількості символів шифрованого тексту (ШТ). Додаткові маскуючі символи вибираються керованим генератором випадкових чисел таким чином, щоб статистичний аналіз ВТ до вставляння і після вставляння маскуючих символів змінювався в сторону рівномірної частоти вживання символів. Генератор випадкових чисел на кожному кроці вставляння символу вибирає такий символ, який має найменшу частоту вживання символів. І ця частота і вживання символів визначається на кожному кроці і з кожним кроком частотна характеристика ВТ з маскуючими символами стає все більш рівномірною, що унеможливлює отримати однозначний результат при обробці статистичних параметрів тексту. Формування матриць ключів для шифрування і розшифрування виконується аналогічно як в шифрі Хілла. Формат матриць ключа і вектора відкритого тексту для шифрування може бути 2, 3, 4, 5, 6… Зараз нема технічних проблем для апаратного, програмного чи комбінованого способу перемноження матриць розміром 2×2, 3×3, 4×4, 5×5, 6×6, … Визначення частоти вживання символів у відкритому тексті (ВТ) також неважко визначити з допомогою k лічильників, які будуть визначати скільки разів вживався кожний символ у ВТ. Таким чином маскуючі символи будуть вставлятися перед і після символів ВТ в залежності від частоти вживаності, причому в зворотній залежності. Чим рідше вживається окремий символ ВТ, тим частіше він буде вставлятися як маскуючий символ. Якщо підрахунок частот вживання символів підраховувати після кожного циклу вставляння (перед і після окремого символу ВТ), то очевидно, що чим більше циклів вставляння маскуючих символів, тим більш рівномірною буде частотна характеристика вживання символів. Основні прийоми для розпізнавання способу шифрування, визначення довжини ключа є статистична обробка тексту, яка визначає частоту повторення символів і повторення групи символів ШТ, що може допомогти визначити довжину ключа. Маскуючі символи, які вставляються перед і після кожного символу ВТ, і їх процедура вставляння в певній мірі має випадковий характер, фактично стають додатковим шифруючим ключем. Справа в тому, що якщо при перемноженні матриць у матрицю символів ВТ вставляється хоча б один маскуючий символ, то при перемноженні змінюються всі результуючі символи ШТ. Якщо перемножимо матрицю ключа на матрицю вектор ВТ, то отримаємо: 1 2 3 10 16 4 5 6  11  11 (mod 26) 7 8 9 12 6 . Якщо в матриці вектор ВТ замінимо один символ (11 поміняємо на 5), то отримаємо: 1 2 3 10 4 4 5 6  5  7 (mod 26) 7 8 9 12 10 . Як бачимо заміна одного символу у векторі ВТ (11 замінили на 5) призвело до того, що всі інші символи також змінилися. Таким чином введення маскуючих символів навіть у невеликій кількості (наприклад вводиться один маскуючий символ перед символом відкритого тексту при 3 UA 99073 U 5 10 15 20 25 30 35 40 45 50 55 60 форматі матриці ключа 3×3 і матриця вектор ВТ буде змінена так: один маскуючий символ і два символи ВТ і так буде у всіх блоках шифрування) призведе до кардинальної зміни символів ШТ. І це тільки від введення маскуючих символів. А ще відбувається процедура перемноження матриці ключа на матрицю вектор ВТ. Таким чином всі закономірності ШТ (з точки зору статистичних характеристик і методик їх обробки) будуть суттєво змінені. Особливо великі проблеми при взламуванні коротких текстів, які зашифровані запропонованим способом шифрування, тому що статистика для таких паролів, кодів, умовних команд чи інших кодових слів, які означають режими роботи, і т.п., не відповідає статистиці природної мови ВТ. Тому, в зв'язку з вищевикладеним, запропонований спосіб шифрування має потенційні високі параметри криптостійкості, особливо при використанні його в системах безпеки для збереження конфіденційної інформації. Шифрування інформації запропонованим способом виконується наступним чином. Символи відкритого тексту ВТ доповнюються маскуючими символами в такому порядку. Визначення частоти вживання символів у відкритому тексті (ВТ) також визначається з допомогою k лічильників, які будуть визначати скільки разів вживався кожний символ у ВТ. Ця процедура виконується перед початком вставляння маскуючих символів і після кожного циклу вставляння маскуючих символів. Один цикл - це виконана процедура вставляння маскуючих символів перед і після кожного символу ВТ. Чим рідше вживається окремий символ ВТ, тим частіше він буде всталятися як маскуючий символ. Якщо підрахунок частот вживання символів підраховувати після кожного циклу вставляння (перед і після окремого символу ВТ), то очевидно, що чим більше циклів вставляння маскуючих символів, тим більш рівномірною буде частотна характеристика вживання символів. Таким чином відбувається підготовка ВТ до процедури шифрування. Далі виконується поділ символів відкритого тексту з маскуючими символами (ВТ+М) на блоки по μ символів у блоці, ці μ 2 символів утворюють матрицю стовпчик, а ключ утворюється з μ кількості символів, які записуються як квадратна матриця μ×μ і символи шифрованого тексту (ШТ) формуються в процесі перемноження поблоково матриці стовпчика і квадратної матриці, які попередньо перетворюються у відповідні числа по модулю n, де n - кількість символів ВТ. Процедура розшифрування відбувається в зворотньому порядку. Символи ШТ діляться на блоки по μ символів у блоці і по черзі перемножуються на обернену матрицю ключа і отримаємo ВТ+М. Остання дія, яку необхідно виконати, це з розшифрованого тексту ВТ+М видалити всі маскуючі символи в такому порядку, в якому вони вставлялися, і отримаємо ВТ. Запропонований спосіб шифрування інформації має високі параметри по криптостійкості, нескладно реалізується апаратним способом чи програмним способом або комбінованим способом. Шифр Хілла при μ=6 був реалізований у вигляді механічної шифрувальної машинки, описаній в патенті (U.S. Patent 1 845 947), який виконував множення матриць у форматі 6×6 по модулю 26 з допомогою системи шестерень і ланцюгів. При необхідності отримати високі параметри по криптостійкості необхідно вставляти достатньо маскуючих символів, кількість яких може в декілька разів перевищувати кількість символів відкритого тексту ВТ. Якщо приймається алгоритм вставляння маскуючих символів: вставляється один маскуючий символ перед кожним символом ВТ і один маскуючий символ після символу ВТ. В цьому випадку ВТ з маскуючими символами буде мати таку конфігурацію: в кожному блоці (якщо μ=3) буде один маскуючий символ перед символом відкритого тексту, символ ВТ і один маскуючий символ після символу ВТ. Блок має такий вигляд: {mi, vi, mi, }, де mi - маскуючий символ, vi - символ ВТ. Якщо конфігурація ВТ з маскуючими символами буде така, яка розглядалася вище, a =4, тоді перший блок буде мати такий вигляд {mi, vi, mi, mi, }, другий {vi, mi, mi, vi, }, третій - {mi, mi, vi, mi, }, четвертий - {mi, vi, mi, mi}, а п'ятий буде такий як перший і весь цикл з періодом чотири буде повторватися. Якщо приймається алгоритм вставляння маскуючих символів: вставляється два маскуючі символи перед кожним символом ВТ і нуль маскуючих символів після символу ВТ при =3. В цьому випадку блок має такий вигляд: {mi, mi, vi, }, де mi - маскуючий символ, vi - символ ВТ. Всі блоки будуть мати такий вигляд, тому що кількість вставлених маскуючих символів, які приходяться на один символ ВТ, дорівнює -1. Варіантів, які визначають конфігурацію ВТ з маскуючими символами, може бути багато. Вибирати необхідно такі, які забезпечують рівномірність частотної характеристики вживання окремих символів для ШТ. Дослідження частотних характеристик вживання окремих символів ШТ навіть при mi=1 підтверджує ефективність запропонованого способу шифрування інформації. Якщо раніше вся робота по криптографії виконувалася вручну і було небажано збільшувати довжину ШТ, то при сьогоднішньому стані шифрувальної техніки ця особливість не є 4 UA 99073 U визначальною. При використанні шифрувальних машин, спеціалізованих приладів, комп'ютеризованих пристроїв чи комп'ютерів, збільшення ШТ і видалення маскуючих символів виконується дуже швидко і не зменшує продуктивності праці оператора при шифруванні чи дешифруванні інформації. 5 ФОРМУЛА КОРИСНОЇ МОДЕЛІ 10 15 20 Спосіб шифрування інформації, при якому виконують поділ символів відкритого тексту (ВТ) на 2 блоки по  символів у блоці, які утворюють матрицю стовпчик, а ключ утворюють з  кількості символів, які записують як квадратну матрицю ×, і символи шифрованого тексту (ШТ) формують в процесі перемноження поблоково матриці стовпчика і квадратної матриці ключа шифрування, які попередньо перетворюють у відповідні числа по модулю n, де n - кількість символів ВТ, дешифрування шифрованого тексту виконують поділом символів ШТ на блоки (по  символів у блоці) і перемноження матриці стовпчика і квадратної матриці ключа дешифрування, які перетворюють у відповідні числа по модулю n, де n - кількість символів ВТ, який відрізняється тим, що перед множенням на матрицю ключа шифрування у відкритий текст перед і після кожного символу ВТ вставляють додаткові маскуючі символи, причому маскуючі символи на кожному кроці вставляння визначаються найменшою частотою вживання цього символу (з врахуванням вставлених маскуючих символів) у відкритому тексті з маскуючими символами, а при дешифруванні вилучають маскуючі символи в такому порядку, як вони вставлялися перед множенням на матрицю ключа шифрування. Комп’ютерна верстка І. Мироненко Державна служба інтелектуальної власності України, вул. Василя Липківського, 45, м. Київ, МСП, 03680, Україна ДП "Український інститут інтелектуальної власності", вул. Глазунова, 1, м. Київ – 42, 01601 5