Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп’ютеризовані системи
Кафедра:
Комп'ютеризовані системи автоматики
Інформація про роботу
Рік:
2008
Тип роботи:
Інші
Предмет:
Основи збору, передавання та обробки інформації
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Алгоритм шифрування з відкритим ключем RSA
Інструкція до лабораторної роботи № 3
з дисципліни “Основи збору, передавання та обробки інформації”
для студентів базового напрямку 6.0914
“Комп’ютеризовані системи, автоматика і управління”
та базового напрямку 050201 “Системна інженерія”
Затверджено
на засіданні кафедри
“Комп’ютеризовані
системи автоматики”
Протокол № __ від __.__.2008
Львів 2008
Алгоритм шифрування з відкритим ключем RSA: Інструкція до лабораторної роботи № 3 з дисципліни “Основи збору, передавання та обробки інформації” для студентів базового напрямку 6.0914 “Комп’ютеризовані системи, автоматика і управління” та базового напрямку 050201 “Системна інженерія” / Укл.: А.Г. Павельчак, Р.В. Проць, В.В. Самотий – Львів: НУЛП, 2008. – 36 с.
Укладачі: А.Г. Павельчак, к.т.н., асистент
Р.В. Проць, к.т.н., доцент
В.В. Самотий, д.т.н., професор
Відповідальний за випуск:
А.Й. Наконечний, д.т.н., професор
Рецензент: З.Р. Мичуда, д.т.н., професор
Мета роботи: вивчити принцип функціонування асиметричних криптосистем з відкритими ключами на прикладі RSA, дослідити числові алгоритми, що використовуються у криптографії та реалізувати алгоритмічною мовою С++ алгоритм шифрування RSA.
1. Загальні відомості
Ідею, що покладено в основу асиметричних криптосистем, було висунуто Вайтфілдом Діффі (Whitfield Diffie) та Мартіном Гелманом (Martin Hellman), та незалежно Ральфом Меркле (Ralph Merkle). Ця революційна ідея була опублікована Діффі та Гелманом в 1976 році у статті «Нові напрямки в криптографії». Асиметричні криптосистеми, на відміну від симетричних алгоритмів, використовують для шифрування та розшифрування повідомлень не один секретний ключ, а пару ключів для кожного учасника протоколу – відкритий ключ E для шифрування та не співпадаючий з ним секретний ключ D для розшифрування. Для цих ключів, послідовно застосованих для повідомлення M, повинно виконуватися таке співвідношення
(1.1)
Співвідношення (1.1) можна розглядати як замок, що закривається одним ключем, а відкривається іншим.
Для безпеки такої системи секретний ключ D повинен бути таким, щоб його неможливо було визначити з відкритого ключа E або, щоб це визначення було нездійсненним з причин обмеження часу та пам’яті.
У асиметричних системах робота з ключами є простою. Щоб одержувач А, власник секретного ключа, зміг розшифрувати повідомлення, зашифроване відправником Б, по каналах зв’язку треба передати лише відкритий ключ учасника А. Цей принцип і визначає відкритість сеансу зв’язку: для безпечної взаємодії двох учасників достатньо домовитися про асиметричну процедуру шифрування та обмінятися відкритими ключами. Однак така простота керування ключами теж має певні обмеження. Учасники передбачуваного безпечного сеансу зв’язку повинні бути впевнені, що відкриті ключі інших учасників є справжніми, тобто, щоб порушник, що має намір перехопити секретну інформацію, не зміг непомітно проникнути в сеанс зв’язку та видати «свій» ключ за відкритий ключ чийогось партнера. Справжність відкритих ключів гарантується складними процедурами, та існують відповідні державні закони, що регулюють діяльність у цій області.
Принцип асиметричних криптосистем має широке застосування. За допомогою цих систем можна створювати цифрові підписи, у яких ключова функція перевернена задом наперед. Для формування цифрового підпису ми «шифруємо» повідомлення секретним ключем та передаємо отримане разом з повідомленням по каналу зв’язку. Тепер кожен, хто знає відповідний відкритий ключ, зможе розшифрувати зашифроване повідомлення та порівняти результат з вихідним текстом. При цьому сформувати цифровий підпис може лише власник секретного ключа. Варто зазначити, що, по відношенню до цифрових підписів, використання термінів «шифрування» та «розшифрування» є не зовсім коректним, тому кажуть, як правило, про «формування» та «перевірку» цифрового підпису.
До асиметричних систем, що формують цифрові підписи, ставлять таку жорстку вимогу: залежність значення D(M) від M повинна бути такою, яку можна перевірити. Ця перевірка є можливою, якщо математичні операції шифрування та розшифрування комутативні, тобто результатом почергового їх виконання повинно бути одне і теж вихідне повідомлення M
(1.2)
Застосовуючи відкритий ключ E до значення D(M), можна пере вірити, чи D(M) правильний цифровий підпис для повідомлення M.
2. Теорія чисел
2.1. Арифметика залишків (лишків).
Ідея арифметики залишків є простою та схожа на «арифметику годинників». Наприклад, ви сказали, що вернетеся з подорожі додому рівно опівночі (тобто 00:00), а запізнилися аж на 43 години. О котрій ж таки годині ви вернетеся додому? Якщо у вас звичайний механічний годинник з циферблатом на 12 годин, то вернетеся о 7 годині (рис. 1). Якщо ж у вас модерновий годинник з 24-х годинним циферблатом, то з’ясується, що це буде 19-та година, а якщо у вас чудернацький годинник з семигодинним циферблатом, то буде лише перша година. Це і є арифметика за модулем кількості годин циферблата.
У загальному, , якщо для деякого цілого числа . Якщо додатне число, та має значення між 0 та , тоді можна розглядати як залишок від ділення на . Іноді називають залишком (лишком) за модулем , а іноді називають конгруентним за модулем (знак потрійної рівності позначає конгруентність).
Множина чисел від 0 до утворює повну множину залишків за модулем . Це означає, що для будь-якого цілого числа його залишок за модулем є певним числом від 0 до . Відповідно операція позначає залишок від , що є деяким цілим числом від 0 до . Ця операція називається приведенням за модулем. Наприклад,
( ,
( .
Оператор реалізується алгоритмічною мовою С++ за допомо гою оператора %, що повертає залишок від ділення першого виразу на другий. Цей залишок буде від’ємним при від’ємному ділено му. І тому, коли операція % повертає від’ємне число, необхідно додавати число до результату операції приведення за модулем.
if (b % n >= 0) a = b % n; //
else { a = b; do a += n; while (a<0); }
Арифметика залишків є схожою на звичайну арифметику: вона комутативна, асоціативна та дистрибутивна. Крім того, приведення кожного проміжного результату за модулем дає такий ж результат, що й виконання всього обчислення з наступним приведенням кінцевого результату за модулем .
1: , (2.1)
,
2: , (2.2)
,
3: , (2.3)
,
4: , (2.4)
.
2.2. Алгоритми піднесення до степеню.
Операція піднесення до степеню деякого числа за модулем іншого цілого числа виглядає так:
. (2.5)
Зазначимо, що немає змісту спершу обчислювати , а потім обчислювати його залишок від ділення на , оскільки проміжний результат може бути аж надто великим числом, яке ми не в змозі будемо опрацювати. Наприклад, = (1 з 200 «0» після неї). Тому операцію (2.5) розбивають на ряд проміжних обчислень, викорис товуючи властивість (2.3).
Нехай необхідно обчислити , тоді:
(2.6)
Однак цей найпростіший спосіб потребує значних машинних затрат часу, і тому на практиці використовують значно ефективніші методи піднесення до степеню за модулем.
2.2.1. Метод справа-наліво двійкового потенціювання.
Цей метод має декілька назв. Інколи його називають алгоритмом двійкових квадратів та добутків, оскільки він реалізується за допо могою цих операції, а інколи і алгоритмом індійського потенціювання. Має назву потенціювання справа-наліво, тому що він перебирає символи вказівника степеню, починаючи з молодшого розряду.
Нехай необхідно обчислити вираз (2.5) зі значенням
. (2.7)
Представимо число у вигляді суми степенів 2
(2.8)
Тепер розпишемо вираз (2.7) з врахуванням розкладу (2.8)
. (2.9)
Застосовуючи властивість (2.3), (2.6) до виразу (2.9), отримуємо
. (2.10)
Такий підхід і називається методом двійкових квадратів та добутків. Мовою С++ цей алгоритм виглядає так:
// обчислення
m = 1;
while (x)
{
if (x&1) m = (m*a) % n;
x = x >> 1;
a = (a*a) % n;
}
2.2.2. Метод зліва-направо двійкового потенціювання.
Цей метод схожий до попереднього, з тією лиш різницею, що пе ребір символів вказівника степеню він виконує, починаючи зі старшо го розряду. Якщо представити вказівник у двійковому вигляді
, , (2.11)
де – кількість розрядів , то загальний алгоритм виглядатиме так:
Мовою С++ цей алгоритм виглядає так:
// обчислення
//визначення к-сті розрядів числа x
worker = x; n_x = 1;
while (worker > 1)
{ worker = worker >> 1; n_x++; }
//маска з "1" для старшого розрдяду x
mask = 1;
mask = mask << (n_x-1);
m = 1;
while (mask)
{
m = (m*m) % n;
if (x & mask)
m = (m*a) % n;
mask = mask >> 1;
}
У цьому алгоритмі за кожен прохід циклу обробляється один біт степеню. При цьому кількість піднесень до квадрату рівна кількості розрядів числа , а загальна кількість добутків визначається кількістю його одиничних розрядів. Отже чим менша вага (кількість “1”) числа , тим алгоритм двійкового потенціювання працює швидше.
2.2.3. Рекурсивний метод двійкового потенціювання.
Ефективною є реалізація методу двійкового потенціювання у вигляді рекурсивного алгоритму. Цей алгоритм у середньому зменшує кількість операцій до , де – довжина числа у бітах.
Мовою С++ цей рекурсивний алгоритм виглядає так:
// обчислення
unsigned long long m_recursive (unsigned long long a, unsigned long long x,
unsigned long long n)
{
unsigned long long tmp;
if (x==1) return a%n;
if (x&1)
{
tmp = m_recursive (a, x>>1, n);
tmp = (tmp*tmp)%n;
return (tmp*a)%n;
}
else
{
tmp = m_recursive (a, x>>1, n);
return (tmp*tmp)%n;
}
}
2.2.4. Метод вікна.
У більшості випадках, піднесення до квадрату виконується швидше, аніж загальне множення. І відповідно, для того щоби ще більше скоротити час обчислень, варто спробувати зменшити кількість загальних добутків. Це є можливим при використанні техніки вікон, яка використовує наперед обчислені значення.
Ідея методу базується на виборі для показника степеню осно ви системи числення більшої 2. З практичної точки зору основа вибирається рівною степеню двійки: .
У віконному методі за один раз враховується символів вказівника степеню. Спершу обчислюється та запам’ятовується таблиця значень , , … ,
, для , (2.12)
де – ширина вікна.
Далі записуємо число у системі числення за основою
, , (2.13)
де – кількість розрядів у системі числення за основою .
Загальний алгоритм методу вікна виглядає так:
Мовою С++ цей алгоритм виглядає так:
// обчислення
// заповнення значень
base =1; // основа системи числення для вікна w
for (int i=0; i<w; i++)
base *= 2;
unsigned long long *A = new unsigned long long [base];
A[0] = 1; // обчислення таблиці значень
for (int i=1; i<base; i++)
A[i] = (A[i-1]*a)%n;
// визначення к-сті розрядів числа x за основою base
worker = x; n_x = 1;
while (worker > base-1)
{ worker = worker / base; n_x++; }
// перевід з 10 системи числення у систему з основою base
int *x_base = new int [n_x];
for (int i=0; i<n_x; i++)
{ x_base[i] = x % base; x /= base; }
// основний алгоритм
m = 1;
for (int i=n_x-1; i>=0; i--)
{
for (int j=0; j<w; j++)
m = (m*m)%n;
f = x_base[i];
m = (m*A[f])%n;
}
delete [ ] A; delete [ ] x_base;
Метод вікна складається з двох етапів. На першому етапі виконуються підготовчі обчислення: формування таблиці значень , перевід показника степеню у систему числення з основою . На другому етапі виконуються уже безпосередні обчислення результату операції піднесення числа до степеню за модулем .
Зменшення обчислень у методі досягається за рахунок скоро чення числа загальних добутків до кількості розрядів числа за осно вою , однак кількість піднесень до квадрату залишається такою ж.
2.2.5. Метод змінного вікна.
Цей метод дає можливість ще зменшити, у порівнянні зі звичайним методом вікна, кількість загальних добутків. Для цього обчислюються та запам’ятовуються лише непарні значення степенів за модулем , , … ,
, для , (2.14)
де – ширина вікна, а показник степеню записується у такому вигляді
, , (2.15)
де – кількість розрядів у системі числення за основою . Відмінність виразу (2.15) від виразу (2.13) полягає у тому, що ми можемо для (чисел за основою ) вибирати лише непарні значення, а тому необхідно кожну суму цього ряду корегувати, змінюючи при цьому ширину вікна. Наприклад, для звичайного методу вікна переведення показника степеню у систему числення з шириною вікна (тобто з основою ) дає, відпо відно, число . Розкладемо за степенями згідно (2.13)
. (2.16)
У такому вигляді ми не можемо застосувати цей розклад (2.16) для методу змінного вікна, оскільки 1-й та 2-й розряди є парними числами. Тому для цих доданків необхідно здійснити певне перетворення, щоб ці розряди стали непарними
. (2.17)
Баланс між операціями множення та піднесення до степеню зміщується у бік більш бажаного піднесення у степінь, і при цьому обчислювати та зберігати необхідно лише степені числа з непарни ми показниками.
У методі змінного вікна важливо вміти правильно записати роз клад у ряд за степенями. Якщо у стандартному методі ширина вік на є сталою, то у методі змінного вікна ширина вікна визначається як
. (2.18)
Наприклад, число у вісімковій системі числення запишеться як . 1-й та 4-й розряди місять «0», і тому ширина вікна для їх попередніх розрядів має бути .
. (2.19)
Загальний алгоритм представлення числа
у вигляді , де непарне
Треба зазначити, що розмір вектора має бути на 1 більшим, ніж кількість розрядів, і відповідно, старший член має дорівнюва ти 0. Це є необхідно для основного алгоритму методу змінного вікна.
Мовою С++ алгоритм методу змінного вікна виглядає так:
// обчислення
// заповнення значень
base =1; // основа системи числення для вікна w
for (int i=0; i<w; i++)
base *= 2;
unsigned long long *A = new unsigned long long [base];
A[0] = 1; // обчислення таблиці значень
for (int i=1; i<base; i++)
A[i] = (A[i-1]*a)%n;
/ /визначення к-сті розрядів числа x за основою base
worker = x; n_x = 1;
while (worker > base-1)
{ worker = worker / base; n_x++; }
// масив для значень змінної ширини вікна
int *E = new int [n_x+1];
// перевід з 10 системи числення у систему з основою base
int *x_base = new int [n_x];
for (int i=0; i<n_x; i++)
{ x_base[i] = x % base; x /= base; }
// представлення у вигляді , де непарне
for (int i=0; i<n_x; i++)
if ( x_base[i]%2 ) // якщо значення непарне
E[i] = w*i;
else
{
k=0; F = x_base[i];
for (int j=0; j<i*w; j++)
F *= 2;
if (F==0)
{
x_base[i] = 0;
if (i) E[i] = E[i-1];
else E[i] = 0;
}
else
{
while (F%2 == 0 || F >= base)
{ F = F >> 1; k++; }
x_base[i] = F; E[i] = k;
}
}
E[n_x] = 0;
// основний алгоритм
m = 1;
for (int i=n_x-1; i>=0; i--)
{
for (int j=0; j<E[i+1]-E[i]; j++)
m = (m*m)%n;
f = x_base[i];
m = (m*A[f])%n;
}
for (int j=0; j<E[0]; j++)
m = (m*m)%n;
delete [ ] A; delete [ ] x_base; delete [ ] E;
Як бачимо, алгоритм методу змінного вікна має значну кількість попередніх обчислень. Однак це є оправданим для значної кількості операцій піднесення до однакового степеню чисел великої розряд ності. При цьому розклад у ряд (2.15) показника степеню виконується лише один раз, а для кожної окремої операції необхідно лише обчислити непарні значення степенів за модулем .
2.3. Прості числа.
Простим називають натуральне число, яке більше 1 та має лише два натуральних дільники: 1 та себе самого, тобто не ділиться ні на жодне інше число. Приклад простих чисел
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, …, 2365347734339, …, 2756839 – 1.
Простими , за винятком 2, можуть бути лише непарні числа.
Існують певні поліноміальні та експоненційні формули, за якими можна побудувати ряд простих чисел:
формули Ейлера
, для , (2.20)
, для , (2.21)
формула Лежандра
, для , (2.22)
формула Ескотта
, для , (2.23)
Числа Ферма
, для , (2.24)
Числа Марсена *
, (2.25)
* Необхідною умовою для отримання простого числа Марсена є те, що має бути простим числом, однак ця умова не є достатньою. Так, при 2, 3, 5, 7, 13, 17, 19 ми отримуємо, відповідно, прості числа Марсена, а при 11, 26, 29, 67, 257 отримуємо складені. Для аналізу простоти чисел Марсена використовують тест Люка-Лемера, за допомогою якого у 1998 році було доведено, що число Марсена при 3 021 377 просте і містить 909526 десяткових знаків. На разі знайдено лише 33 простих числа Марсена.
2.4. Найбільший спільний дільник.
Будь-яке ціле додатне ціле, на яке діляться одночасно цілі числа та , називають їх спільним дільником. Найбільший із спільних дільників чисел називають найбільшим спільним дільником (НСД) та позначають НСД (,). Якщо найбільший спільний дільник чисел дорівнює 1, тобто НСД (,) = 1, то ці числа називаються вза ємно простими. Так, числа 27 та 116 – взаємно прості, бо НСД (27, 116) = 1, а от 15 та 27 не є взаємно простими, оскільки НСД (15, 27) = 3.
Просте число є взаємно простим зі всіма іншими числами, крім чисел, кратних цьому простому числу.
Знаходять найбільший спільний дільник класичним алгоритмом Евкліда чи однією з його модифікацій.
2.4.1. Алгоритм Евкліда.
В основі алгоритму лежить повторне ділення із залишком: обчислюємо залишок , потім і так далі, поки залишок на стане рівним нулю.
Загальний алгоритм Евкліда обчислення НСД (,) для
Мовою С++ цей алгоритм виглядає так:
// обчислення НСД (,)
while (a != 0)
{
temp = b %a;
b = a;
a = temp;
}
nsd = b;
2.4.2. Бінарний алгоритм Евкліда.
Для комп’ютерів операції множення та додавання є набагато простішими, аніж операції ділення та обчислення залишку. Тому звичайна реалізація алгоритму Евкліда є не зовсім ефективною.
При обчисленнях НСД можна використати ряд таких еквівалент них перетворень
НСД (,) =. (2.26)
Зазначимо, що ділення на 2 є простою операцією, оскільки вона рівносильна простому зсуву розрядів у двійковій системі числення. Саме ця властивість і використовується у бінарному алгоритмі.
Бінарний алгоритм Евкліда обчислення НСД (,) для
Мовою С++ цей алгоритм виглядає так:
// обчислення НСД (,)
g = 1;
// якщо a та b парні числа відокремлення степеню двійки з НСД
while (a%2 == 0 && b%2 == 0)
{ a = a/2; b = b/2; g = 2*g; }
// тепер a чи b непарне число
while (a != 0)
{
while (a%2 == 0) a = a/2;
while (b%2 == 0) b = b/2;
//тепер обидва числа a та b непарні
if (a >= b) a = (a-b)/2;
else b = (b-a)/2;
}
nsd = g*b;
Замінивши обчислення залишку та ділення на 2 порозрядними операціями зсуву вправо (>>) та І (&), цей алгоритм мовою С++ може виглядати так:
// обчислення НСД (,)
g = 1;
// якщо a та b парні числа відокремлення степеню двійки з НСД
while ( !(a&1) && !(b&1) )
{ a = a>>1; b = b>>1; g = g<<1; }
// тепер a чи b непарне число
while (a)
{
while ( !(a&1) ) a = a>>1;
while ( !(b&1) ) b = b>>1;
//тепер обидва числа a та b непарні
if (a >= b) a = (a-b)>>1;
else b = (b-a)>>1;
}
nsd = g*b;
2.5. Обернені значення за модулем.
Нехай нам необхідно розв’язати таке рівняння
, (2.27)
де – невідома величина.
Наприклад, для звичайного лінійного рівняння з дійсними числами розв’язок є тривіальним: , .
На відміну від лінійного, рівняння (2.27) не завжди має розв’язок, а якщо і має, то він може бути не один.
Основним критерієм існування єдиного розв’язку рівняння (2.27) є виконання умови: НСД (,) = 1, тобто числа та мають бути взаємно простими. Тоді розв’язок (2.27) буде виглядати так:
, (2.28)
де мультиплікативне обернене за модулем до числа
. (2.29)
Тобто наша задача зводиться до пошуку цього оберненого значення .
2.5.1. Розширений алгоритм Евкліда.
Звичайний алгоритм Евкліда для знаходження НСД (,) зводився до послідовного ділення із залишком
, , (2.30)
де , , НСД (,).
Якщо для послідовності (2.30) провести ряд перетворень та виразити усі залишки через та , тоді
,
,
,
,
(2.31)
Таким чином, ми отримали рекурентну формулу (2.31) для зна ходження НСД (,) у вигляді лінійної комбінації чисел та з цілими числами та . Якщо числа та взаємно прості, тоді НСД (,) = 1, і відповідно
1 = НСД (,) =. (2.32)
З формули (2.32) випливає, що обернене значення .
Загальний розширений алгоритм Евкліда
обчислення оберненого значення
Мовою С++ цей алгоритм виглядає так:
// обчислення
// вхід: числа a та n, для яких треба знайти nsd= НСД (,)
long long n1, c, k, nsd, c1, c2, k1, k2, q, r;
n1 = n; //резервуємо значення n
c2 = 1; c1 = 0; k2 = 0; k1 = 1;
while(n != 0)
{
q = a/n; r = a - q*n; c = c2 - q*c1; k = k2 - q*k1;
a = n; n = r; c2 = c1; c1 = c; k2 = k1; k1 = k;
}
nsd = a; c = c2; k = k2;
// якщо аглоритм дав від’ємне значення с, тоді с = с (mod n)
if (c < 0) c += n1;
// вихід: числа nsd, c, k
// с – обернене значення за модулем n
Зауваження: у результаті роботи алгоритму можуть виникати від’ємні числа, і тому усі змінні мають бути знакового типу. Для беззнакових (unsigned) змінних алгоритм буде працювати некоректно! Якщо = НСД (,), то числа та не є взаємно простими.
2.5.2. Розширений бінарний алгоритм Евкліда.
Зауваження, викладені у п.2.4.2, стосуються і розширеного алгоритму Евкліда. Тобто, використовуючи властивості для НСД (2.26), ми можемо оптимізувати за кількістю обчислень також і розширений алгоритм Евкліда.
Загальний розширений бінарний алгоритм Евкліда
обчислення оберненого значення
Мовою С++ цей алгоритм виглядає так:
// обчислення
// вхід: числа a та n, для яких треба знайти nsd= НСД (,)
long long u, v, A, B, C, D, g, c, k, nsd;
g = 1;
// якщо a та b парні числа -> відокремлення степеню двійки з НСД
while ( !(a&1) && !(n&1) )
{ a = a>>1; n = n>>1; g = g<<1; }
// тепер лише a чи b непарне число
u = a; v = n; A = 1; B = 0; C = 0; D = 1;
do
{
while ( !(u&1) ) // поки u парне
{
u = u>>1;
if ( !(A&1) && !(B&1) ) { A = A>>1; B = B>>1; }
else { A = (A+n)>>1; B = (B-a)>>1; }
}
while ( !(v&1) ) // поки v парне
{
v = v>>1;
if ( !(C&1) && !(D&1) ) { C = C>>1; D = D>>1; }
else { C = (C+n)>>1; D = (D-a)>>1; }
}
if (u >= v) { u = u-v; A = A-C; B = B-D; }
else { v = v-u; C = C-A; D = D-B; }
}
while (u);
nsd = g*v; c = C; k = D;
if (c < 0) c += n1;
// вихід: числа nsd, c, k
// с – обернене значення за модулем n
3. Генерування простого числа
Для реалізації криптографічних систем з відкритими ключами необхідні прості числа великої розрядності. Основний метод генеру вання великих простих чисел є нескладним: для цього необхідно взяти випадкове число та перевірити чи воно просте. Для цього є розробле ний ряд алгоритмів визначення простоти числа. Простих чисел теж є багато (в околиці числа приблизно кожне з чисел є простим).
Найпростішим методом перевірки простоти числа є метод пробного ділення. По суті, ми намагаємося поділити число на всі числа, починаючи з 2 та закінчуючи . Якщо у результаті ділення отримуємо хоча б одне ціле число, тоді – складене число (не прос те), якщо ні – воно є простим числом. Однак метод пробного ділення можна використовувати лише для пошуку невеликих простих чисел.
Як правило, для перевірки простоти числа використовують імовірнісні тести. Ці тести дають відповідь, що число є складеним або ймовірно воно є простим. Прості числа завжди успішно проходять ці тести, складені ж числа можуть пройти його лише з певною (заданою) ймовірністю. Прості числа, отримані таким чином, називають «промисловими простими числами».
Загальний алгоритм генерування великого простого числа
Генеруємо випадкове -бітне число .
Встановлюємо старший та молодший біти рівними 1. (Старший біт гарантує необхідну довжину простого числа, а молодший біт забезпечує його непарність).
Перевіряємо, чи ділиться без остачі на невеликі прості числа: 3, 5, 7, 11 і т.д. Якщо виявляємо нульову остачу, тоді повторюємо операцію пошуку з п.1.
Виконуємо разів вибраний імовірнісний тест для визначення простоти числа. Тобто, якщо число прохо дить тест, тоді міняють умови тесту і проходять його ще раз, і так разів. Якщо ж число не проходить однієї з переві рок, тоді повторюємо операцію пошуку з п.1.
Перевірка п.3 алгоритму дає можливість відкинути значну кількість непарних чисел ще до п.4. Наприклад, перевірка діленням на 3, 5 та 7 відкидає 54% непарних чисел ще до п.4, перевірка діленням на всі прості числа, менші за 100, відкидає 76% непарних чисел, а перевірка діленням на всі прості числа, менші за 256, відкидає 80% непарних чисел. Ефективною вважається перевірка діленням на всі прості числа, менші за 2000. Однак іноді з метою «лінивства» та ком пактності програмного коду, замість побудови списку простих чисел, просто виконують ділення на усі підряд непарні числа. Якщо простих чисел включно до 2000 є близько 300, то усіх непарних буде 1000.
Мовою С++ алгоритм отримання простого числа виглядає так:
unsigned long long p, mask; // генероване просте число
int t=200; // t – кількість повторів тесту на простоту
bool BOOL;
Random^ autoRand = gcnew Random; // генератор випадкових чисел
do
{
BOOL = false;
p = autoRand->Next(1, 65535); // генерування наступного випадк.числа
mask = 1; p = p|1; p = p|(mask<<15); // встановл. ст. та мол. бітів в "1"
for (int i=3; i<2000; i+=2) //перевірка діленням на прості числа
if (p%i == 0) { BOOL = true; break; }
if ( !BOOL ) BOOL=Test(p,t); // ф-ція Test – тест на простоту числа p
}
while(BOOL);
Наведений у програмі генератор випадкових чисел взятий з бібліотеки класів .NET Framework FCL Visual Studio 2005. Його метод Next (int minValue, int maxValue) видає випадкове число типу int у межах, заданих числами minValue та maxValue-1. Функція Test() – імо вірнісний тест на простоту.
3.1. Тест Рабіна-Мілера (Rabin-Miller).
Цей тест є модифікацією тесту Ферма та приймає складене чис ло за просте з ймовірністю 0,25 для будь-якої випадкової основи . Тому багатократне повторення тесту дає можливість зменшити ймовірність похибки до визначеної наперед.
Припустимо, що число просте. Тоді згідно малої теореми Ферма для всіх цілих чисел , не кратних , виконується рівність
. (2.33)
Квадратний корінь з може приймати лише значення 1 та -1, оскільки це єдині розв’язки рівняння . Обчислимо послідовно квадратні корені
, , … , ,
поки не отримаємо непарне число . Якщо на деякому кроці ми отримаємо залишок не рівний 1, тоді він повинен бути рівним -1, інакше число не може бути простим.
Загальний алгоритм тесту Рабіна-Мілера
Якщо отримуємо результат «число ймовірно просте», то пов торю ємо перевірку з іншою основою , а якщо – «число складене», то одразу завер шу ємо тест. Зазначимо, що після повторів цього тесту ймовірність похибки становитиме (якщо алгоритм видасть відповідь «число ймовірно є простим числом»).
Мовою С++ цей алгоритм виглядає так:
bool Test (unsigned long long p, int t) // p – вхідне число, t – к-сть тестів
{
Random^ autoRand = gcnew Random; // ств. генер-ра випадк. чисел
int m = 0;
unsigned long long s = p-1, a, b;
while (s%2 == 0)
{ s = s/2; m++; }
for (int i=0; i < t; i++)
{
a = autoRand->Next(2, p-1);
if (NSD(a, p) != 1) return true; // true -- число p складене
// NSD (a, p) – ф-ція знаходження НСД (,)
b = StepMOD(a, s, p); // ф-ція піднесення до степеню за mod
if (b == 1 || b == p-1) continue; // число p ймовірно просте
for (int l=1; l<m; l++)
{
b=StepMOD(b,2,p);
if (b == p-1) { BooL = 1; break; } // p ймовірно просте
}
if (BooL == 0) return true; // true -- число p складене
}
return false; // число p ймовірно просте
}
// якщо функція повертає false – тоді число p є ймовірно простим,
// а якщо true – число p є складеним
3.2. Тест Соловея-Штрасена (Solovay-Strassen).
Цей тест побудований на такій теоремі: для будь-якого простого та деякого (з множини залишків за модулем ) справедлива така рівність
, (2.34)
де – символ Якобі, який приймає такі значення: 0 (якщо ді литься на ), 1 та -1.
Загальний алгоритм тесту Соловея-Штрасена
Загальний алгоритм обчислення символу Якобі
Якщо отримуємо результат «число ймовірно просте», то пов торю ємо перевірку з іншою основою , а якщо – «число складене», то одразу завер шу ємо тест. Зазначимо, що після повторів цього тесту ймовірність похибки становитиме (якщо алгоритм видасть відповідь «число ймовірно є простим числом»).
Мовою С++ цей алгоритм тесту Соловея-Штрасена виглядає так:
bool Test (unsigned long long p, int t) // p – вхідне число, t – к-сть тестів
{
Random^ autoRand = gcnew Random; // ств. генер-ра випадк. чисел
int J, s, m; // J – символ Якобі
unsigned long long a, c, b, a1, p1;
for (int i=0; i < t; i++)
{
a = autoRand->Next(2, p-1);
if (NSD (a, p) != 1) return true; // true – число p складене
c = StepMOD (a, (p-1)/2, p); // ф-ція підн-ня до степеню за mod
//Обчислення символу Якобі
J = 1; p1 = p;
do
{
if (a == 0) { J = 0; break; }
if (a == 1) { break; }
a1 = a; m = 0;
while (a1%2 == 0)
{ a1 = a1/2; m++; }
if (m%2 == 0) s = 1;
else
{
if (p1%8 == 1 || p1%8 == 7) s = 1;
else s = -1;
}
if (a1 == 1) { J = J*s; break; }
if (p1%4 == 3 && a1%4 == 3) s = -s;
a = p1%a1; p1 = a1; J = J*s;
}
while (1);
if (J<0) b = p+J;
else b = J;
if (b != c) { return true; } // true – число p складене
}
return false; // число p ймовірно просте
}
// якщо функція повертає false – тоді число p є ймовірно простим,
// а якщо true – число p є складеним
3.3. Тест Лемана (Lehmann).
Цей тест є простішим за попередній, та не потребує обчислення символу Якобі. Він виконується разів, і на кожному кроці має підтвердити про ймовірну простоту числа , якщо ж результат – складене, робота тесту одразу ж завершується. Після повторів цього тесту ймовірність похибки становить .
Загальний алгоритм тесту Лемана
Мовою С++ цей алгоритм виглядає так:
bool Test (unsigned long long p, int t) // p – вхідне число, t – к-сть тестів
{
Random^ autoRand = gcnew Random; // ств. генер-ра випадк. чисел
unsigned long long a, c;
for (int i=0; i < t; i++)
{
a = autoRand->Next(2, p-1);
if (NSD (a,p) != 1) return true; // true -- число p складене
// NSD (a, p) – ф-ція знаходження НСД (,)
c = StepMOD (a, (p-1)/2, p); // ф-ція підн-ня до степеню за mod
if (c != 1 && c != p-1) { return true; } // true -- число p складене
}
return false;
}
// якщо функція повертає false – тоді число p є ймовірно простим,
// а якщо true – число p є складеним
4. Протокол шифрування RSA
Безпека RSA побудована на складності розкладу великих чисел на множники. Відкритий та закритий ключі є функціями двох великих простих чисел. Припускається, що відновлення відкритого тексту за шифротекстом та відкритим ключем тотожне розкладу двох великих чисел на множники.
Для генерації двох ключів використовують два великі випадкові прості числа та (для максимальної безпеки їх вибирають одна кової довжини), та обчислюють їх добуток:
. (4.1)
Потім випадковим чином вибирають ключ шифрування , такий що та є взаємно простими числами. За допомогою розширеного алгоритму Евкліда обчислюється ключ дешифрування , такий що
, (4.2)
звідки
, (4.3)
де – мультиплікативне обернене за модулем до числа .
Зазначимо, що числа і взаємно прості. Числа і – це відкритий ключ, а числа і – закритий ключ. Два прості числа і більше не потрібні та можуть бути відкинуті, але не повинні бути розкритими.
При шифруванні, повідомлення спершу розбивається на цифрові блоки, менші (для двійкових даних вибирається найбільша степінь числа 2, менша ). Зашифроване повідомлення буде склада тися з блоків однакової довжини.
Формула шифрування виглядає так:
. (4.4)
Для дешифрування повідомлення кожен зашифрований блок обчислюється за такою формулою:
. (4.5)
Аналогічно, також повідомлення може бути зашифроване за допомогою ключа , а розшифроване за допомогою . На цій ідеї іноді і будують схему цифрового підпису, тобто, ви за допомогою секретного ключа шифруєте повідомлення, а одержувач розшиф ровує його за допомогою відкритого ключа . Достовірністю підпису буде зрозуміла на вигляд інформація.
5. Практичні рекомендації
Треба зазначити, що на розроблюваний у лабораторній роботі криптографічний алго ритм RSA штучно накладається ряд обмежень, пов’язаний з існуючими типами даних мови С++. Найбільший тип даних, що ми можемо використати, це 64 розрядний цілий тип unsigned long long (чи знаковий long long ). Побудова реальної сис теми RSA потребує значно більшої розрядності, наприклад, 2000-біт них даних. Таку розрядність можна одержати, лише розробивши новий та складний тип даних (але ми не ставили перед собою такої за дачі). Навіть маючи 64-розрядний тип даних, реально ми можемо створити систему RSA з вдвоє меншими розрядними ключами. Це безпосеред ньо пов’язано з робочими алгоритмами арифметики залиш ків (наприк лад, алгоритм піднесення до степеню за модулем). А от генерувати прості числа ми можемо ще із вдвічі меншою розрядністю (16 біт), оскільки .
У розроблюваній програмі, з метою уникнення випадкових по милок, рекомен дується використовувати усюди 64-роз ряд ний безнако вий цілочисель ний тип даних unsigned long long, якщо звісно про це не обумовлено окремо (наприклад, розширений алгоритм Евкліда мусить використовувати знаковий тип, оскільки цей алгоритм перед бачає від’ємні числа).
Далі ми коротко опишемо нюанси двох основних типів варіантів розроблюваних програм.
5.1. Система RSA для роботи з файлами.
У загальному, розроблювана програма цього варіанту завдання має мати вигляд, як на рис. 5.1.а.
а) б)
Рис. 5.1. Кінцевий вигляд програми
Вона складається з 3-х базових функцій: Генератор ключів, Шифрування RSA, Розшифрування RSA.
Завдання Генератора ключів видати нам пару ключів RSA: відкритий ключ ( і ) та секретний ключ ( і ).
Загальний алгоритм Генератора ключів
Мовою С++ цей алгоритм виглядає так:
unsigned long long p, q, n, E, D;
Random^ autoRand = gcnew Random; // ств. генератора випадкових чисел
p = Generator(autoRand); // генерування простого числа p
q = Generator(autoRand); // генерування простого числа q
n = p*q;
do
E = autoRand->Next (3, (p-1)*(q-1)>>1); // генерування числа E
while (NSD (E,(p-1)*(q-1)) != 1); // NSD () – ф-ція знаходження НСД
D = Inverse (E, (p-1)*(q-1)); // ф-ція обчислення оберненого за mod
// далі виконуємо вивід чисел p, q, n, E, D
// у відповідні їм елементи керування textBox
Для отримання простих чисел та в одному розподілі випад кових величин, рекомендується використовувати той самий генератор. Для цього в Генераторі ключів ми створюємо генератор випадкових чисел autoRand, та передаємо його за дескриптором у функцію генератора Generator().
Функція Шифрування RSA повинна послідовно зчитувати у бінарному вигляді з довільного файлу даних, шифрувати вхідну інформацію та записувати у вихідний файл. Для виконання операцій вводу-виводу скористаємося бібліотекою класів .NET Framework FCL Visual Studio 2005 (типи даних BinaryReader та BinaryWriter). Для вико ристання цих бібліотек необхідно дописати у верху файлу Form1.h доступ до відповідного простору імен, де розміщені ці типи даних
using namespace System::IO;
Мовою С++ функція Шифрування RSA може виглядати так:
String^ filename;
unsigned char p;
unsigned int m;
unsigned long long m1, c, n, E;
n = Convert::ToUInt64 (textBox3->Text);
E = Convert::ToUInt64 (textBox4->Text);
openFileDialog1->ShowDialog (); //викликаємо діалогове вікно вибору файлу
filename = openFileDialog1->FileName; //зчитуємо шлях до файлу
BinaryReader^ binReader = gcnew BinaryReader ( File::Open( filename,
FileMode::Open ) ); // створюємо об’єкт для бінарного читання з файлу
BinaryWriter^ binWriter = gcnew BinaryWriter ( File::Open( filename+".rsa",
FileMode::Create ) ); // створюємо об’єкт для бінарного запису у файл
try
{
do
{
p = binReader->ReadByte(); // зчитуємо 16-бітний блок даних
m1 = static_cast<unsigned long long>(p);
c=StepMOD(m1,E,n); // обчислюємо
m = static_cast<unsigned int>(c);
binWriter->Write( m ); // запис 32-бітн. зашифр.блоку даних
}
while(1);
}
catch(...) { }
binReader->Close(); //закриваємо файл з вх.даними
binWriter->Close(); //закриваємо файл з зашифр.даними
У програмі ми явно приводимо типи даних за допомою ключово го слова static_cast (тобто приведення відбувається статично на етапі компіляції). Блок try { } catch { } – це механізм обробки виключних ситуацій. Коли функція читання з файлу ReadByte() зауважує кінець файлу, то вона генерує помилку, яка перехоплюється та оброблюється у блоці catch. При цьому виконання програмного коду у блоці try завершується.
Функція Розшифрування RSA повинна послідовно зчитувати у бінарному вигляді з вибраного зашифрованого файлу, розшифрову вати та здійснювати запис у новий файл. Реалізація операцій вводу-ви воду аналогічна як у функції шифрування.
Мовою С++ функція Розшифрування RSA може виглядати так:
String^ filename;
unsigned char p;
unsigned int c1;
unsigned long long m, c, n, D;
n = Convert::ToUInt64(textBox3->Text);
D = Convert::ToUInt64(textBox5->Text);
openFileDialog1->ShowDialog ();
filename = openFileDialog1->FileName;
BinaryReader^ binReader = gcnew BinaryReader ( File::Open( filename,
FileMode::Open ) );
BinaryWriter^ binWriter = gcnew BinaryWriter ( File::Open( filename->
Replace(".rsa",""), FileMode::Create ) );
try
{
do
{
c1 = binReader->ReadUInt32(); // зчит. 32-бітн.блок шифр. даних
c = static_cast<unsigned long long>(c1);
m=StepMOD(c,D,n); // обчислюємо
p = static_cast<unsigned char>(m);
binWriter->Write( p ); // запис 16-бітного блоку розшифр.даних
}
while(1);
}
catch(...) { }
binReader->Close ();
binWriter->Close ();
5.2. Підбір закритого ключа та злом системи RSA.
У загальному, розроблювана програма цього варіанту завдання має мати вигляд, як на рис. 5.1.б. Її завдання, маючи відкритий ключ, відновити по ньому секретний ключ та розшифрувати перехоплене повідомлення. Для цього потрібно розкласти число на прості множники та . Виконати цей розклад є задачею простою, оскільки у нашому завданню лише 32-розрядне число. Розклад на множники можна виконати методом пробного ділення на усі непарні числа включно до . Однак, з метою компактності програмного коду, ми будемо перебирати усі непарні числа до включно.
Загальний алгоритм злому секретного ключа методом перебору
Мовою С++ цей алгоритм виглядає так:
unsigned long long p, q, n, E, D, i = 3;
E = Convert::ToUInt64(textBox1->Text);
n = Convert::ToUInt64(textBox2->Text);
while(i <= n)
{
if (n%i == 0) break;
i += 2;
}
p = i; q = n/p;
D = Inverse (E, (p-1)*(q-1)); // ф-ція обчислення оберненого за mod
// далі виконуємо вивід чисел p, q, D
// у відповідні їм елементи керування textBox
Реалізація функції Розшифрування RSA аналогічна як і у п.5.1.
6. Порядок виконання роботи
Вдома детально вивчити поданий у інструкції довідковий теоретичний матеріал до лабораторної роботи.
Згідно варіанту (порядкового номера в журналі викладача) завдання (таблиця 1 та 2), вдома розробити програму для реалізації вказаного проекту, а в лабораторії вписати програмний код та налагодити цю програму.
Отримані на комп’ютері результати правильної роботи програми представити викладачу.
По результатах виконаної роботи оформити звіт та здати його.
Таблиця 1. Завдання до лабораторної роботи
* інд...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора