Карпінський
М.П., Дубчак Л.О., Яциковська У.О.
Тернопільський
національний економічний університет, Україна
Дослідження часової реалізації
алгоритму електронного цифрового підпису RSA
Сучасні інформаційні
системи, базовані на комп’ютерних мережах із супутниковими,
телекомунікаційними, оптоволоконними та іншими каналами зв’язку, забезпечують
створення, відправлення, передавання, одержання, зберігання, оброблення,
використання та знищення електронних документів. Хоча концепція електронного
документа з’явилася ще на початку 80-х років, його правовий статус було
визначено відносно недавно Законом України „Про електронні документи та
електронний документообіг” від 22 травня 2003 року № 851-IV, який встановлює
основні організаційно-правові засади електронного документообігу та
використання електронних документів в Україні [1].
Обов’язковим реквізитом електронного
документа, без якого він не може мати підстави для обліку і не матиме юридичної
сили, є електронний підпис, що використовується для ідентифікації автора або
підписувача електронного документа іншими суб'єктами електронного
документообігу.
На відміну від рукописного підпису,
електронний цифровий підпис (ЕЦП) має не фізичну, а логічну природу – це
послідовність символів, отримана за результатом криптографічного перетворення
набору електронних даних, який додається до цього набору або логічно з ним
поєднується і дає змогу підтвердити його цілісність та ідентифікувати
підписувача.
При підписанні електронного документу його
початковий зміст не змінюється, а додається блок даних ‑ електронний
цифровий підпис [4]. Отримання цього блоку можна розділити
на два етапи.
На першому етапі за допомогою програмного
забезпечення і спеціальної математичної функції обчислюється так званий
«відбиток повідомлення» (message digest). Цей відбиток має такі особливості:
·
фіксована довжина, незалежно від довжини
повідомлення;
·
унікальність відбитку для кожного
повідомлення;
·
неможливість відновлення повідомлення за
його відбитком.
Таким чином, якщо документ був модифікований, то
зміниться і його відбиток, що відобразиться при перевірці електронного
цифрового підпису.
На другому етапі відбиток документа шифрується за
допомогою програмного забезпечення та особистого ключа автора.
Таким чином, обчислення відбитку документа захищає його від модифікації сторонніми особами після підписання, а
шифрування особистим ключем автора підтверджує авторство документа.
Першою та найвідомішою у світі системою ЕЦП стала система RSA, математична схема якої була розроблена у 1977 році у США.
В даній системі спочатку необхідно визначити пару ключів (відкритий та
таємний). Припустимо, що відправник хоче підписати повідомлення 
перед його відправленням. Спочатку повідомлення (блок інформації,
файл, таблиця) стискається за допомогою хеш-функції 
в ціле число 
. Після цього обчислюють цифровий підпис 
під електронним
документом , використовуючи хеш-значення 
та таємний ключ 
як 
.
Пара 
передається
партнеру-отримувачу як електронний документ , підписаний електронним підписом , причому він сформований власником таємного ключа .
Після отримання пари одержувач обчислює
хеш-значення повідомлення двома способами. Перш
за все, він встановлює значення , застосовуючи криптографічні перетворення підпису з використанням
відкритого ключа 
як 
.
Крім того, він знаходить результат хешування прийнятого повідомлення за допомогою такої ж
хеш-фукції , тобто .
Якщо зберігається рівність обчислених значень, то отримувач признає
пару справжньою.
Очевидно, що дана схема дозволяє
захиститись від декількох видів поpушень:
ü відправник
не може відмовитись від свого повідомлення, якщо отримувач визнає, що таємний
ключ відомий лише йому;
ü
порушник без знання таємного ключа не
може ні сфоpмувати, ні зробити осмислену зміну повідомлення, пеpеданого по
лінії зв’язку;
ü дана
схема дозволяє пpи виpішенні багатьох конфліктних ситуацій обходитись без
посеpедників.
Загальний алгоритм електронного
цифрового підпису на основі RSA може
здійснюватись наступним чином.
Алгоритм А1:
Вхід: M, f
Вихід: (M, S)
Begin
1. random ( p1);
1.1. L = 2;
1.2. if L > 
1.2.1.
then p = p1
1.2.2. else
begin
1.2.2.1. if p1 mod L = 0 then 1
1.2.2.2.
else L = L+1;
1.2.2.3.
goto 1.2.
end;
2. random ( q1 );
2.1. L = 2;
2.2. if L > 
2.2.1.
then q = q1
2.2.2. else
begin
2.2.2.1. if q1 mod L = 0 then 1
2.2.2.2. else L = L+1;
2.2.2.3.
goto 1.2.
end;
3. N = p*q;
4. φ(N)
= ( p-1 )*( q-1 );
5. random (E1);
6. if E1 ≤
φ(N) and НСД ( E1, φ(N) ) ) =1
then
6.1. E =E1
6.2. else goto 5
7. random ( D1 );
8. if D1 < N and E*D1
( mod φ(N)) = 1 ;
8.1
then D = D1
8.2 else goto 7
9. розбиття M на блоки по
256 біт
10. for i = 1 to 4 do;
10.1. лінійне змішування 
, 
, 
(
= 
);
11. розбиття на 
по 64 біти;
12. for i = 1 to 4 do
12.1. S
= 
( h ) – шифрування простою заміною;
13. S = 
;
14. H = S
M H
;
15. H = f ( Z M; f ( L, f ( M, H
)));
16. S = H
( mod N );
17. вихід ( M, S )
end.
Для знаходження НСД двох чисел застосовується наступний
алгоритм А2:
Вхід: E1, φ(N)
Вихід : НСД (E1, φ(N) )
begin
1. if E1 > φ(N) then
begin
1.1.1. r
= E1;
1.1.2.
r
= φ(N);
end;
else
begin
1.2.1. r = φ(N);
1.2.2. r = E1;
end;
2. t = r;
3. k = 
;
4. r1 = t mod r;
5. r0 = (t – r)/k;
6. if 
r = 0 then
6.1 НСД( E1,
φ(N)) = r;
7. else goto 2
end;
end.
Для проведення аналізу
продуктивності та стійкості алгоритму цифрового електронного підпису на основі
алгоритму RSA необхідно спочатку визначити загальний час його виконання. Для
побудови математичної моделі часової реалізації необхідно здійснити аналіз часу
виконання кожної операції даного алгоритму. В таблиці 1 виділені основні
операції алгоритму А1 та часи, затрачені процесором для їх реалізації.
Таблиця 1 – Затрати часу на виконання
основних операцій алгоритму ЕЦП.
|
Операція |
Час(такти) |
|
random a |
t |
|
a = b |
t |
|
a = b, ( a – b ) |
t |
|
a > b |
t |
|
a mod b |
t |
|
|
t |
|
|
t |
|
a |
t |
|
a |
t9 |
|
розбиття на блоки |
t10 |
|
шифрування простою заміною |
t11 |
|
обчислення функції f |
t12 |
, (
)
Для генерування простих чисел у
досліджуваному алгоритмі А1 використовується “сито Ератосфена”. Цей метод не
дозволяє знаходити дуже великі прості числа, проте для використання простим
користувачем, який не передає фінансової конфіденційної чи таємної інформації,
його достатньо. Крім того, при застосуванні тесту Міллера – Рабіна чи Соловея –
Штрассена, загальний алгоритм аналізу алгоритму ЕЦП не змінюється.
У алгоритмі А1 необхідно
згенерувати два простих числа, тобто “сито Ератосфена” здійснюється двічі. Для
генерування простого числа р виконуються операції 1-1.2.2.3 даного
алгоритму. Для перевірки умови 1.2 необхідно здійснити обчислення 
і провести порівняння 
та . Крім того, в даному алгоритмі здійснюється перевірка ще
однієї умови 1.2.2.1, яка здійснює повернення на крок 1 чи на крок 1.2.
Математична модель побудови
часової реалізації “сита Ератосфена ” може мати наступний вигляд:
. (1)
Для виконання операцій присвоєння
(1.2.1) та додавання (1.2.2.2) необхідно врахувати ймовірність виконання
відповідних умов 1.2 та 1.2.2.1. Ймовірність того, що 
рівна 
, 
‑ 
, а виконання нерівності 
відбувається з
ймовірністю 
. Для виконання операції 1.2.2.2 необхідно виконання двох
умов зразу та , то ймовірність їх одночасного виконання рівна 
. Враховуючи дані ймовірності загальний час виконання “сита
Ератосфена” рівний:
. (2)
Для знаходження НСД на кроці 6
алгоритму А1 використовується алгоритм А2. В даному алгоритмі при перевірці виконання
умови 1 здійснюється виконання двох присвоєнь, якщо 
чи у протилежному
випадку. Тобто комп’ютер здійснює лише дві операції присвоєння у будь-якому
випадку і затрачає на це час 
. Операція 6.1 здійснюється лише при виконанні умови 
, тобто з імовірністю (на перевірку цієї
рівності процесор затрачає час 
). Отже, загальний час виконання алгоритму А2 знаходження
найбільшого спільного дільника двох чисел може мати наступне математичне
представлення:
. (3)
У алгоритмі А1 при виконанні операції 6 процесор повинен
спочатку перевірити виконання умов 
та 
. Тому ймовірність виконання операції присвоєння 6.1 рівна 
. Аналогічно ймовірність виконання операції 8.1 рівна 
. Варто також зазначити, що на порівняння 
процесор затрачає час
на множення, знаходження числа за модулем та порівняння результату з 1, тобто 
. Виходячи з математичних моделей (2) та (3) загальний час
виконання алгоритму А1 можна подати наступним чином:
.(4)
Для здійснення шифрування простою
заміною (крок 12.1 алгоритму А1) процесору необхідно здійснити 
присвоєнь, де ‑ довжина блоку 
, тобто, виходячи з кроку 11, 
. Звідси випливає, що 
. Тобто математична модель часової реалізації алгоритму ЕЦП
на основі RSA має наступний вигляд:
. (5)
З досліджень, проведених у [8]
випливає, що для здійснення операції піднесення до степеня за модулем (крок 16
алгоритму А1) доцільно використати β-арний
метод зліва направо чи метод ковзаючого вікна зліва направо [2, 6]. Тобто у математичному представленні (5), у
випадку використання β-арного методу зліва направо, час 
буде рівним
, (6)
де 
‑ час,
затрачений на переведення числа у бінарну систему числення, 
‑ позначення 
-арної системи числення.
А у випадку застосування методу ковзаючого вікна зліва направо
, (7)
де ‑ час,
затрачений на переведення числа у бінарну систему числення, 
‑ час, затрачений на знаходження найдовшої
послідовності 
, p – кількість
вікон у послідовності 
, 
‑ ширина найбільшого вікна.
З
аналізу формул (5), (6) та (7) випливає, що загальний час виконання алгоритму
ЕЦП на основі RSA залежить лише від часу .
Електронний цифровий підпис призначений для забезпечення діяльності фізичних та юридичних осіб, що здійснюється з використанням електронних документів. Його застосовують для ідентифікації підписувача та підтвердження цілісності даних в електронній формі. Використання електронного цифрового підпису не змінює порядку підписання договорів та інших документів, встановлених законом для вчинення правочинів у письмовій формі.
Виходячи
з досліджень, проведених у [8] випливає, що алгоритм ЕЦП на основі RSA має
найвищу продуктивність та стійкість при використанні β-арного методу зліва направо чи методу ковзаючого вікна зліва
направо піднесення до степеня за модулем та від складності одно направленої
хеш-функції (що є наступною проблемою для дослідження).
Проведені у даній науковій роботі дослідження
дозволяють проводити аналіз і інших алгоритмів електронного цифрового підпису.
Література
1.Вербіцький О.В. Вступ до криптографії. – Львів: Видавництво науково-технічної літератури, 1998.-247 с.
2. Ємець В., Мельник А., Попович Р. Сучасна криптографія. Основні
поняття. - Львів: Бак, 2003. – 144 с.
3. Молдовян А.А., Молдовян В.А., и др. Криптография. – Серия “ Учебники для вузов. Специальная литература.” – Спб.: Издательство “Лань”,
2000. – 224 c.
4. Романец Ю.В., Тимофеев П.А,
Шальгин В.Ф. Защита информации в компьютерных системах и сетях – М.: «Радио и
связь», 1999.
5. Чмора А.Л. Современная
криптография. 2-е изд., стер. – М.: Гелиос АРВ, 2002.- 256 с.
6. Seong-Min Hong, Sang-Yeop oh, Hyunsoo Yoon. New Modular Exponentiation. – Spring- Verlag,
1998.
7. Зайчик А.В. Основне пути утечки информации и
несанкционированного доступа в корпоративних сетях. // Науково-технічний журнал “ Захист інформації ” – 2003 - № 4. С. 19-24.
8.
Васильцов І.В., Васильків Л.О. Стійкість
сучасних алгоритмів модулярного експоненціювання до часового аналізу ‑
Науково-технічний журнал “Захист інформації”, №1, 2005, С. 54-69