Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Симетричні та асиметричні методи зашифрування інформації
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних технологій, автоматики та метрології
Факультет:
Не вказано
Кафедра:
Кафедра автоматики та телемеханіки
Інформація про роботу
Рік:
2005
Тип роботи:
Курсова робота
Предмет:
Методи та засоби криптографічних перетворень
Група:
ІБ – 41
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Інститут комп’ютерних технологій, автоматики та метрології
Кафедра автоматики та телемеханіки
Курсова робота
з курсу: „Методи та засоби криптографічних перетворень”
на тему: “Симетричні та асиметричні методи зашифрування інформації”
Львів – 2005
Зміст
Завдання 1
Теоретичні відомості
Блок-схема алгоритму
Список ідентифікаторів
Текст програми
Відкритий текст
Результат зашифрування
Висновки
Завдання 2
Теоретичні відомості
Вибір ключів
Зашифрування
Розшифрування
Висновки
Завдання 1
Вибрати ключі та розробити програму для за шифрування файлу даних заданим афінним шифром. Тип афінного шифру визначається останньою цифрою i НЗК. Об‘єм алфавіту визначається передостанньою цифрою j НЗК і дорівнює при і .
I
i mod 6
Тип афінного шифру
6
0
Зсув 1-го порядку
j
Розрядність алфавіту
Об‘єм алфавіту
7
12
4096
Теоретичні відомості
символьний алфавіт ототожнюємо з кільцем . А саме, кожна буква змінюється своїм номером у алфавіті, причому нумерація починається з нуля. Наприклад, латинська абетка утотожнюється, а українська із . Літера а української абетки трактується як 0, б як 1, і т. д. Тепер до букв відкритого тексту ми можемо вільно застосовувати операції додавання, множення за відповідним модулем.
Шифр зсуву.
Ключ: таке, що .
Шифрування: у повідомленні кожна буква заміщується буквою .
дешифрування: У криптотексті кожна буква заміщується буквою , де . Величину зворотнього зсуву будемо називати дешифруючим ключем.
Блок-схема прорами
Текст програми
#include <stdio.h>
#include <math.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
unsigned long a=123, n=4096;
const bit_mask = 12;
const mask = pow(2, bit_mask)-1;
void main(void)
{
char s[6];
FILE *f_in, *f_out;
int end_of_in_file=0, x_is_ready=1;
unsigned long buf_in, buf_out = 0, x;
int in_bits=32, out_cells=32;
if ( (f_in=fopen("data.in", "rb")) == NULL )
{
printf("cannot open the file data.in");
getch();
exit(1);
}
else
if ( (f_out=fopen("data.out", "wb")) == NULL)
{
printf("cannot open the file data.out or data_out.txt");
getch();
exit(1);
}
else
{
if (fread(&buf_in, 1, 4, f_in) != 0)
while (!end_of_in_file)
{
if (in_bits<=0)
{
if (fread(&buf_in, 1, 4, f_in) != 0)
{
x |= (buf_in << (bit_mask+in_bits)) & mask;
buf_in >>= (-in_bits);
in_bits += 32;
x_is_ready = 1 & !(in_bits==32);
}
else
{
end_of_in_file = 1;
x_is_ready = 1;
}
}
else
{
x = buf_in & mask;
buf_in >>= bit_mask;
in_bits -= bit_mask;
x_is_ready = 1 & (in_bits>=0);
}
/*--------------------------------*/
if (x_is_ready)
{
x = (unsigned int)(fmod(a+x, n));
itoa(x, s, 10);
printf("%s", strcat(s, " "));
buf_out |= x << (32-out_cells);
out_cells -= bit_mask;
if (out_cells<=0)
{
fwrite(&buf_out, 4, 1, f_out);
buf_out &= 0;
if (out_cells==0) out_cells = 32;
else
{
buf_out |= x >> (bit_mask+out_cells);
out_cells += 32;
}
}
}
}
fcloseall();
printf("\nReady. Press any key.");
getch();
}
}
Список ідентифікаторів
Ідентифікатори
Призначення
unsigned long a=123
Ключ
unsigned long n=4096
Розмір алфавіту
FILE *f_in
Вхідний файл
FILE *f_out
Зашифрований файл
int end_of_in_file=0
Прапорець кінця файлу
int x_is_ready=1
Прапорець готовності символа
unsigned long buf_in
Вхідний буфер (32 біти)
unsigned long buf_out = 0
Вихідний буфер (32 біти)
unsigned long x
Проміжний символ (9 біт)
int in_bits=32
Лічильник непрочитаних бітів вхідного буфера
int out_cells =32
Лічильник незаповнених бітів вихідного буфера
Текст вхідного повідомлення
Методи чисельного розв‘язування систем лінійних рівнянь поділяються на дві групи:
1) „точні” (прямі) методи, які дозволяють одержати розв‘язок, якщо він існує, як скінченну кількість арифметичних операцій (наприклад: метод Крамера, метод Жордана-Гауса та ін.);
2) наближені (ітераційні) методи, які дозволяють одержати розв‘язки системи лінійних рівнянь лише з заданою точністю з припущенням, що обчислення проводиться без округлень. Точний розв‘язок в даному випадку можна одержати я к результат нескінченно збіжного процесу. До таких методів відносять метод простої ітерації, метод Зейделя та ін.
„Точні” методи використовуються при розв‘язуванні на ЕОМ систем невисокого порядку (n<103 де n – число лінійних алгебраїчних рівнянь системи).
Наближені методи використовуються для систем високого порядку (n=103?106).
Переваги наближених методів (метод простих ітерацій) над точними (метод Гауса) є такими:
1. Час обчислень пропорційний n2 на ітерацію, тоді як для методу виключення час обчислень пропорційний n3. Якщо для розв‘язку потрібно менше ніж n ітерацій, то затрати машинного часу будуть менші.
2. Як правило, похибки округлення при ітераційному методі впливають на остаточні результати значно менше, ніж при розв‘язуванні методом Гауса, оскільки при його використанні похибки не нагромаджуються.
3. Метод ітерацій стає особливо зручним при розв‘язку систем, переважна кількість коефіцієнтів яких дорівнює 0.
Недоліком методу ітерацій є те, що рішення не завжди збігаються.
Метод Гауса
Метод Гауса можна реалізувати у вигляді різних обчислювальних схем, в основі яких лежить одна і та ж ідея послідовного виключення невідомих. Ми розглянемо схему, яка називається схемою єдиного ділення. Обчислювальну схему зручно ілюструвати на прикладі, тому обмежимося системою 4-го порядку. Ці ж прийоми можна застосувати для систем вищих порядків. Розглянемо наступну систему рівнянь:
Результат роботи програми(зашифрований текс)
2718 1024 2496 864 3058 865 2755 912 718 960 949 1760 962 848 1716 1227 2233 769 690 944 1489 996 1722 1025 439 1760 2237 941 3717 944 2746 1761 2242 765 1215 945 1486 964 2496 16 1213 1217 452 1009 1489 932 1458 788 2228 1757 1461 1041 3521 2176 3807 2018 1275 3348 964 1104 2239 3613 3314 964 1218 929 3717 1748 2750 1024 2496 864 1278 1220 2236 1757 950 848 948 912 977 1025 1486 948 2742 992 1464 1024 1466 980 3264 768 1123 849 4032 1952 1010 897 971 1760 2228 941 2034 1005 2239 129 1278 1220 1468 996 2236 941 2761 944 2239 1761 2236 909 4046 16 1987 1185 1266 992 2490 929 1975 865 713 864 1479 948 2753 992 2994 17 1467 1876 1471 976 3522 896 1469 800 1292 916 1975 961 1462 372 1474 928 1463 737 1278 916 1975 961 1462 308 1472 801 690 736 2047 734 1733 737 1778 737 2034 941 3584 2180 3807 2034 1275 932 1714 912 3002 816 2239 1757 2042 1021 1463 737 2248 877 2239 1901 242 816 964 800 442 1748 4049 16 2290 960 1977 960 1213 1217 452 1761 2496 816 3010 736 3524 1760 962 848 1716 1227 4025 864 1522 865 1987 817 3518 1760 2237 941 3717 944 2746 1761 2242 765 1215 945 1486 900 3514 817 3058 1760 1465 800 690 960 1488 1012 3264 945 1669 1025 1488 836 1010 992 1210 1040 2763 944 1215 929 1278 1124 1472 948 3251 865 195 816 703 1232 1010 992 1984 960 3510 1024 1742 1233 1522 816 1465 948 1468 1041 181 816 447 1985 1778 959 713 864 1467 980 3264 768 1123 849 4032 1760 1778 1760 1462 944 448 1040 1778 864 1473 800 2236 1761 958 832 1471 1760 2496 816 3010 736 3524 1760 1489 884 1266 817 2233 913 1998 737 1476 932 1719 897 645 1104 695 944 1472 836 2227 829 959 784 1472 964 962 1088 1719 1041 1280 276 1472 1012 4018 864 1479 916 1975 961 2230 765 1778 16 694 960 1219 1025 1486 916 1975 961 1462 964 962 1008 964 208 2034 1021 1463 737 2248 205 1278 916 1975 961 1462 324 3767 800 183 1232 1778 737 2034 941 512 1394 1878 959 713 16 1382 916 1975 961 3510 1760 3508 896 1472 865 1987 961 2228 1217 452 1009 1489 964 3522 1760 962 848 1716 1227 2233 769 690 944 1413 932 1458 292 416 1758 3523 1008 2756 928 498 816 3508 1008 4032 960 949 1760 961 992 2513 896 1477 1876 320 2021 2050 1749 2742 1760 1344 3636 3058 865 195 960 4082 16 2239 877 3519 1072 1266 912 2741 752 1474 208 713 864 1479 980 1925 944 721 1184 1522 865 1987 817 3518 1904 512 1394 1439 752 3517 832 695 16 242 816 964 800 1466 756 4026 960 3522 1008 964 768 965 1025 1742 1233 2290 912 1489 996 1722 1025 439 1760 3508 1008 4032 960 949 1760 961 992 2513 896 1477 1876 576 2021 2050 2245 1283 2101 763 1444 988 814 2754 768 2226 864 498 736 179 864 2744 944 2746 1761 2750 1024 2496 16 1460 1876 2750 1024 2496 1760 1473 961 1987 865 1479 4 2756 992 2994 17 3771 1748 1471 800 1778 961 713 864 3518 1760 250 816 964 800 2034 734 1733 737 1275 116 1778 737 3516 928 4026 1445 1500 1973 3035 735 1475 948 3251 865 195 816 447 1761 1473 961 961 992 2248 877 3519 880 754 2040 498 736 2034 1021 1463 737 2248 1213 1278 1012 2496 16 1010 897 2290 912 1489 916 1975 961 2230 1761 3508 896 957 1105 695 944 1489 1092 1714 1761 1728 1104 1722 913 695 1184 1010 992 1216 960 3010 17 699 864 1467 2996 773 1748 4017 1136 1472 788 1213 1761 962 848 1716 1227 4025 1040 1010 960 1476 17 691 960 242 816 3519 817 498 16 1464 2996 2034 1021 1463 737 2248 877 1278 1012 1472 836 1970 993 1970 865 242 736 3530 944 959 784 1472 1092 1714 1041 1522 1040 2230 1025 1486 916 695 1120 901 1444 1756 1973 987 895 1010 992 1970 864 957 1952 1010 960 3527 752 3516 1760 4032 992 2245 912 695 944 1489 964 3522 1760 1925 817 1474 1088 3717 944 448 1040 242 816 964 800 1413 756 193 864 1460 1216 452 1761 1471 1760 1728 1025 1970 961 713 16 1266 817 2233 913 1998 737 3524 1760 697 736 713 960 242 816 3519 817 1278 932 2949 1760 1473 865 1266 961 1977 3568 3281 1040 1460 944 2239 1757 2750 1024 2496 960 1470 260 2226 1009 434 1748 1728 897 133 1184 3516 1760 1473 865 3570 960 949 1760 3508 896 1472 865 1987 737 703 16 1010 960 3527 752 3516 1760 2751 1760 1471 784 962 928 2482 832 965 1025 1742 1233 512 1394 773 1380 2718 1024 2496 1760 1925 817 1474 1088 3717 1760 1987 737 1420 948 963 752 3517 768 1472 836 2242 1105 3519 928 1010 992 1466 980 3264 768 1123 849 2236 1761 3523 1008 2756 928 1278 964 1463 817 1460 832 1471 1760 2236 909 4046 16 1987 1185 3826 960 2487 17 2248 125 1983 17 1460 1220 3516 1072 2290 960 2242 765 959 129 1266 1973 3807 418 2487 960 2237 893 448 1760 2750 1024 2496 1040 2034 1021 1463 737 2248 877 3826 1757 2756 1952 3570 961 1266 17 2762 944 1215 1761 2751 1760 1465 768 2488 864 3058 752 2181 736 2000 1185 1219 1985 3807 402 1975 961 1462 260 2226 1009 690 1394 2718 1024 2496 1760 1429 1040 1475 1760 958 832 1471 1760 2754 736 2237 845 1989 736 3524 1760 1477 756 2234 912 2513 16 1266 17 697 864 1479 948 3251 865 195 1216 1460 912 718 864 1479 996 2759 928 1278 756 754 1008 959 768 1413 1220 3516 1072 4082 816 3512 1024 1486 948 694 736 2034 1757 1476 1760 1464 4 2742 1232 1010 960 195 16 950 768 959 784 1472 756 4026 912 3280 817 703 1232 498 816 2228 797 448 864 967 1748 3486 1760 962 848 181 1232 2751 928 1472 996 2759 928 453 1748 4049 736 498 736 3513 768 4018 1021 1742 1233 1522 1073 439 960 1488 116 3510 944 2240 960 2290 16 2749 944 1215 1985 754 750 3529 1008 957 769 178 1184 2239 1761 2755 817 2238 1761 1465 1041 713 960 2034 909 1744 1025 2242 769 1970 865 498 736 1010 992 4026 912 2482 16 1278 1012 448 1040 754 752 2750 832 442 960 1219 1761 3523 1008 2756 928 960 1761 518 772 1472 964 1472 1233 4022 1040 1280 564 1413 820 1010 992 3770 960 3518 1760 958 832 1471 1760 1465 1008 964 1008 1989 736 3524 1760 182 1232 1522 865 1987 817 1470 756 3770 865 1479 964 1472 1233 4022 16 948 1748 930 848 181 1232 2751 928 1472 932 1714 1025 1221 944 1477 996 1722 1025 439 1040 1266 17 692 1232 447 2177 3807 1234 2468
Завдання 2
Зашифрувати Слово відкритого тексту за алгоритмом RSA. Слово визначається останньою буквою і НЗК. Для генерування ключів використати числа p та q, які визначаються передостанньою цифрою j НЗК.
і
Слово
6
ФОН
j
p
q
7
5
17
Скласти програму для за шифрування файлу за алгоритмом RSA. Величина блоку -
Теоретичні відомості
RSA – криптографічна система відкритого ключа, що забезпечує такі механізми захисту як шифрування і цифровий підпис (аутентифікація – встановлення достовірності). Криптосистема RSA розроблена в 1977 році і названа на честь її розробників Ronald Rivest, Adi Shamir і Leonard Adleman.
Алгоритм RSA працює таким чином: беруться два достатньо великих простих числа p і q і обчислюється їх твір ; n називається модулем.
Потім вибирається число e, що задовольняє умові 1< e < (p - 1)*(q - 1) і що не має загальних дільників окрім 1 (взаємно просте) з числом (p - 1)*(q - 1).
Потім обчислюється число d таким чином, що (e*d - 1) ділиться на (p - 1)*(q – 1).
e – відкритий (public) показник
d – секретний (private) показник.
(n; e) – відкритий (public) ключ
(n; d). – секретний (private) ключ.
Дільників (чинники) p і q можна або знищити або зберегти разом з секретним (private) ключем.
Якби існували ефективні методи розкладу на співмножники (факторингу), то, розклавши n на співмножники (чинники) p і q, можна було б отримати секретний (private) ключ d. Таким чином надійність криптосистеми RSA заснована на важковирішуваній – практично нерозв'язною – завданню розкладання n на співмножники (тобто на неможливості факторингу n) оскільки в даний час ефективного способу пошуку співмножників не існує.
Нижче описується використання системи RSA для шифрування інформації і створення цифрових підписів (практичне застосування небагато відрізняється).
Шифрування
Припустимо, Аліса хоче послати Бобу повідомлення M. Аліса створює зашифрований текст З, підносячи повідомлення M до ступеня e і на модуль n: , де e і n – відкритий (public) ключ Боба. Потім Аліса посилає З (зашифрований текст) Бобу. Щоб розшифрувати отриманий текст, Боб підносить отриманий зашифрований текст C в степінь d і бере за модулем n:
; залежність між e і d гарантує, що Боб обчислить M вірно. Оскільки тільки Боб знає d, то тільки він має можливість розшифрувати отримане повідомлення.
Швидкість роботи алгоритму RSA
Як при шифруванні і дешифрувані, так і при створенні і перевірці підпису алгоритм RSA по суті складається з піднесення до степеня, яке виконується як ряд множень.
У практичних додатках для відкритого (public) ключа зазвичай вибирається відносно невеликий показник, а часто групи користувачів використовують один і той же відкритий (public) показник, але кожен з різним модулем. (Якщо відкритий (public) показник незмінний, вводяться деякі обмеження на головних дільників (чинники) модуля.) При цьому шифрування даних йде швидше ніж дешифрування, а перевірка підпису – швидше чим підписання.
Якщо k – кількість бітів в модулі, то в зазвичай використовуваних для RSA алгоритмах кількість кроків необхідних для виконання операції з відкритим (public) ключем пропорційно другому степеню k, кількість кроків для операцій секретного (private) ключа – третього степеня k, кількість кроків для операції створення ключів – четвертого степеня k.
Методи "швидкого множення" – наприклад, методи засновані на Швидкому Перетворенні Фурє Fourier (FFT – Fast Fourier Transform) – виконуються меншою кількістю кроків; проте вони не набули широкого поширення із-за складності програмного забезпечення, а також тому, що з типовими розмірами ключів вони фактично працюють повільніше. Проте продуктивність і ефективність додатків і устаткування тих, що реалізовують алгоритм RSA швидко збільшуються.
Алгоритм RSA набагато повільніше ніж DES і інші алгоритми блокового шифрування. Програмна реалізація DES працює швидше принаймні в 100 разів і від 1,000 до 10,000 – в апаратній реалізації (залежно від конкретного пристрою).
Способи злому криптосистеми RSA
Існує декілька способів злому RSA. Найбільш ефективна атака: знайти секретний (private) ключ, відповідний необхідному відкритому (public) ключу. Це дозволить нападаючому читати всі повідомлення, зашифровані відкритим (public) ключем і підроблювати підписи. Таку атаку можна провести, знайшовши головні співмножники (чинники) загального модуля n – p і q. На підставі p, q і e (загальний показник), нападаючий може легко обчислити приватний показник d. Основна складність – пошук головних співмножників (факторинг) n; безпека RSA залежить від розкладання на співмножники (факторингу), що є важким завданням, що не має ефективних способів рішення.
Фактично, завдання відновлення секретного (private) ключа еквівалентне завданню розкладання на множники (факторингу) модуля: можна використовувати d для пошуку співмножників n, і навпаки можна використовувати n для пошуку d. Треба відзначити, що удосконалення обчислювального устаткування саме по собі не зменшить стійкість криптосистеми RSA, якщо ключі матимуть достатню довжину. Фактично ж вдосконалення устаткування збільшує стійкість криптосистеми.
Інший спосіб зламати RSA полягає в тому, щоб знайти метод обчислення кореня степеня e з mod n. Оскільки , то коренем степеня e з (mod n) є повідомлення M. Обчисливши корінь, можна розкрити зашифровані повідомлення і підроблювати підписи, навіть не знаючи приватний (private) ключ. Така атака не еквівалентна факторингу, але в даний час невідомі методи, які дозволяють зламати RSA таким чином. Проте, в особливих випадках, коли на основі одного і того ж показника відносно невеликої величини шифрується достатньо багато зв'язаних повідомлень, є можливість розкрити повідомлення. Згадані атаки – єдині способи розшифрувати всі повідомлення, зашифровані даним ключем RSA.
Існують і інші типи атак, що дозволяють, розкрити тільки одне повідомлення і що не дозволяють нападаючому розкрити інші повідомлення, зашифровані тим же ключем.
Зрозуміло, існують і атаки направлені не на криптосистему безпосередньо, а на вразливі місця всієї системи комунікацій в цілому; такі атаки не можуть розглядатися як злом RSA, оскільки говорять не про слабкість алгоритму RSA, а скоріше про уразливість його конкретної реалізації.
Наприклад, нападаючий може оволодіти секретним (private) ключем, якщо той зберігається без належних обережностей. Необхідно підкреслити, що для повного захисту недостатньо захистити виконання алгоритму RSA і прийняти заходи обчислювальної безпеки, тобто використовувати ключ достатньої довжини. На практиці ж найбільший успіх мають атаки на незахищені етапи управління ключами системи RSA.
Рекомендована довжина ключа
Розмір ключа в алгоритмі RSA пов'язаний з розміром модуля n. Два числа p і q, твором яких є модуль, повинні мати приблизно однакову довжину оскільки в цьому випадку знайти співмножники (чинники) складніше, ніж у разі коли довжина чисел значно розрізняється. Наприклад, якщо передбачається використовувати 768-бітовий модуль, то кожне число повинне мати довжину приблизно 384 бита. Зверніть увагу, що якщо два числа надзвичайно близькі один до одного або їх різниця близька до деякого зумовленого значення, то виникає потенційна загроза безпеці, проте така вірогідність – близькість двох випадково вибраних чисел – незначна.
1. Візьмемо M = (p+q)/2
2. При p < q, маємо .
Оскільки , то значення p і q можна легко знайти, якщо різниця p - q достатньо мала.
Оптимальний розмір модуля визначається вимогами безпеки: модуль більшого розміру забезпечує велику безпеку, але і уповільнює роботу алгоритму RSA. Довжина модуля вибирається в першу чергу на основі значущості даних, що захищаються, і необхідної стійкості захищених даних і в другу чергу – на основі оцінки можливих загроз.
Хороший аналіз захисту, забезпечуваною певною довжиною модуля, приведений в описі модуля дискретного логарифма Rivest [Riv92a], але те ж можна застосувати і до алгоритму RSA. У пізнішому огляді захисту, пропонованого ключами RSA різної довжини захист аналізується на основі методів розкладання на множники (факторингу), що існували в 1995 і перспективах їх розвитку, а також розглядає можливість залучення великих обчислювальних ресурсів по інформаційних мережах. Проведена в 1997 році оцінка показала, що 512-бітовий ключ RSA може бути розкритий (факторингом) за $ 1,000,000 і вісім місяців. У 1999 році 512-бітовий ключ був розкритий за сім місяців і це означає, що 512-бітові ключі вже не забезпечують достатню безпеку за винятком дуже короткострокових завдань безпеки.
В даний час Лабораторія RSA рекомендує для звичайних завдань ключі розміром 1024 бита, а для особливо важливих завдань – 2048 бітів (наприклад, для головного Майстра Сертифікатів).
Деякі недавно введені стандарти встановлюють для загальних завдань мінімальний розмір ключа 1024 бита. Менш цінна інформація може бути надійно зашифрована ключем 768-бітової довжини, оскільки такий ключ все ще недосяжний для всіх відомих алгоритмів злому. Для оцінки рівнів безпеки різних розмірів ключів можна використовувати модель пропоновану Lenstra і Verheul.
Зазвичай ключ індивідуального користувача має певний термін життя, який закінчується через деякий час, наприклад, через рік. Це дає можливість регулярно замінювати ключі і забезпечувати необхідний рівень безпеки. Після закінчення терміну життя ключа, користувач повинен створити новий ключ, заздалегідь упевнившись, що параметри криптосистеми залишилися тим самим, зокрема що система використовує ключі тієї ж довжини. Звичайно, заміна ключа не захищає від нападу на повідомлення, зашифровані колишнім ключем, але для цього розмір ключа повинен підбиратися згідно очікуваному часу актуальності даних. Можливість заміни ключів дозволяє підтримувати криптографічну систему в соответстствії з поточними рекомендаціями про розміри ключів, які регулярно публікує Лабораторія RSA.
Користувачам необхідно враховувати, що оцінюваний час злому системи RSA – тільки усереднене значення, а масована атака на тисячі модулів в якомусь випадку може дати позитивний результат відносно короткий термін.
Хоча надійність будь-якого окремого ключа все ще висока, деякі методи факторингу завжди залишають нападаючому маленький шанс швидко знайти деякий ключ.
Що ж до утруднення злому збільшенням розміру ключа, те подвоєння довжини модуля в середньому збільшує час операцій відкритого (public) ключа (шифрування і перевірка підпису) в чотири рази, а час операцій секретного (private) ключа (розшифровка і підпис) у вісім разів. Різниця між часом роботи відритого і секретного ключів виникає тому, що відкритий показник може залишатися незмінним, тоді як модуль буде збільшений, а довжина приватного показника буде збільшена пропорційно збільшенню довжини ключа. Час створення ключів при подвоєнні модуля збільшується в 16 разів, але це нечасто виконувана операція і тому на загальній продуктивності це практично не позначається.
Треба відзначити, що розміри ключів в криптосистемі RSA (а також і в інших криптосистемах відкритого (public) ключа) набагато більше розмірів ключів систем блокового шифрування типа DES, але надійність ключа RSA незрівняна з надійністю ключа аналогічної довжини іншої системи шифрування.
Безліч простих чисел для криптосистеми RSA
Як доведено Евклідом більше двох тисяч років назад, існує нескінченна безліч простих чисел. Оскільки алгоритм RSA оперує з ключами певної довжини, то кількість можливих простих чисел кінцева, хоча проте дуже велике. По теоремі про Прості Числа кількість простих чисел менших деякого n асимптотика наближається до n = ln(n). Отже, кількість простих чисел для ключа довжиною 512 бітів або менше приблизно складає (десять в степені 150). Це більше, ніж кількість атомів у відомому Всесвіті.
Вибір ключів
Зашифрування
Ф
О
Н
24
18
17
14
69
34
24
18
17
Блок-схема прорами
Текст програми
#include <stdio.h>
#include <math.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
unsigned long a=13, n=4096;
const bit_mask = 12;
const mask = pow(2, bit_mask)-1;
//=========================================================================
unsigned long step_mod(unsigned long a, unsigned long x, unsigned long m);
//=========================================================================
void main(void)
{
char s[6];
FILE *f_in, *f_out;
int end_of_in_file=0, x_is_ready=1;
unsigned long buf_in, buf_out = 0, x;
int in_bits=32, out_cells=32;
if ( (f_in=fopen("data.in", "rb")) == NULL )
{
printf("cannot open the file data.in");
getch();
exit(1);
}
else
if ( (f_out=fopen("data.out", "wb")) == NULL)
{
printf("cannot open the file data.out or data_out.txt");
getch();
exit(1);
}
else
{
if (fread(&buf_in, 1, 4, f_in) != 0)
while (!end_of_in_file)
{
if (in_bits<=0)
{
if (fread(&buf_in, 1, 4, f_in) != 0)
{
x |= (buf_in << (bit_mask+in_bits)) & mask;
buf_in >>= (-in_bits);
in_bits += 32;
x_is_ready = 1 & !(in_bits==32);
}
else
{
end_of_in_file = 1;
x_is_ready = 1;
}
}
else
{
x = buf_in & mask;
buf_in >>= bit_mask;
in_bits -= bit_mask;
x_is_ready = 1 & (in_bits>=0);
}
/*--------------------------------*/
if (x_is_ready)
{
x = step_mod(x, a, n);
itoa(x, s, 10);
printf("%s", strcat(s, " "));
buf_out |= x << (32-out_cells);
out_cells -= bit_mask;
if (out_cells<=0)
{
fwrite(&buf_out, 4, 1, f_out);
buf_out &= 0;
if (out_cells==0) out_cells = 32;
else
{
buf_out |= x >> (bit_mask+out_cells);
out_cells += 32;
}
}
}
}
fcloseall();
printf("\nReady. Press any key.");
getch();
}
}
//========================================================================
unsigned long step_mod(unsigned long a, unsigned long x, unsigned long m)
{
unsigned long z = 1;
for(int i = 32; i>0; i--)
{
if ((x & ((unsigned long) pow(2, i))) != 0)
{
z*=a;
z=(unsigned long) fmod(z*z, m);
}
else
z=(unsigned long) fmod(z*z, m);
}
if ((x & 1) != 0)
z=(unsigned long) fmod(z*a, m);
return z;
}
Вихідне повідомлення
Методи чисельного розв‘язування систем лінійних рівнянь поділяються на дві групи:
1) „точні” (прямі) методи, які дозволяють одержати розв‘язок, якщо він існує, як скінченну кількість арифметичних операцій (наприклад: метод Крамера, метод Жордана-Гауса та ін.);
2) наближені (ітераційні) методи, які дозволяють одержати розв‘язки системи лінійних рівнянь лише з заданою точністю з припущенням, що обчислення проводиться без округлень. Точний розв‘язок в даному випадку можна одержати я к результат нескінченно збіжного процесу. До таких методів відносять метод простої ітерації, метод Зейделя та ін.
„Точні” методи використовуються при розв‘язуванні на ЕОМ систем невисокого порядку (n<103 де n – число лінійних алгебраїчних рівнянь системи).
Наближені методи використовуються для систем високого порядку (n=103?106).
Переваги наближених методів (метод простих ітерацій) над точними (метод Гауса) є такими:
1. Час обчислень пропорційний n2 на ітерацію, тоді як для методу виключення час обчислень пропорційний n3. Якщо для розв‘язку потрібно менше ніж n ітерацій, то затрати машинного часу будуть менші.
2. Як правило, похибки округлення при ітераційному методі впливають на остаточні результати значно менше, ніж при розв‘язуванні методом Гауса, оскільки при його використанні похибки не нагромаджуються.
3. Метод ітерацій стає особливо зручним при розв‘язку систем, переважна кількість коефіцієнтів яких дорівнює 0.
Недоліком методу ітерацій є те, що рішення не завжди збігаються.
Метод Гауса
Метод Гауса можна реалізувати у вигляді різних обчислювальних схем, в основі яких лежить одна і та ж ідея послідовного виключення невідомих. Ми розглянемо схему, яка називається схемою єдиного ділення. Обчислювальну схему зручно ілюструвати на прикладі, тому обмежимося системою 4-го порядку. Ці ж прийоми можна застосувати для систем вищих порядків. Розглянемо наступну систему рівнянь:
Отримане повідомлення
58 3 22 44 43 55 15 37 42 11 32 53 9 11 10 31 8 29 18 43 50 54 0 2 39 53 52 50 33 43 39 36 21 4 18 42 23 28 22 16 43 37 7 43 50 34 3 56 17 7 43 60 25 52 18 27 3 31 28 1 40 0 50 28 32 57 33 54 52 3 22 44 43 19 54 7 43 11 43 37 41 2 23 43 10 14 13 3 5 60 0 32 54 56 35 13 21 52 31 53 17 50 35 43 40 31 43 19 6 54 54 50 31 43 40 36 54 16 33 16 32 3 21 14 0 57 34 55 56 44 1 43 8 14 16 34 11 21 26 58 36 56 27 31 20 57 34 3 19 1 15 24 4 0 43 57 34 3 19 30 10 27 18 60 58 34 50 0 12 0 35 50 1 2 18 35 3 34 38 37 60 47 40 7 57 11 4 0 53 47 40 15 0 47 28 31 33 54 6 16 45 11 50 11 43 37 7 36 22 47 54 60 29 53 9 11 10 31 52 44 43 55 32 19 11 53 52 50 33 43 39 36 21 4 18 42 23 3 31 19 43 53 14 31 18 11 55 18 0 42 23 2 55 52 21 14 41 30 46 43 18 57 43 3 10 43 1 55 0 47 41 29 21 14 17 11 50 3 58 24 43 47 14 43 6 60 0 47 22 45 12 53 56 44 11 60 0 32 54 56 35 53 12 53 19 43 28 30 12 44 12 31 54 36 52 16 26 53 22 47 54 60 29 53 50 42 21 19 8 51 21 0 30 34 20 52 29 1 19 43 10 52 18 32 53 43 10 28 9 41 20 60 4 27 10 18 52 44 1 57 34 3 58 4 12 16 24 11 17 2 23 57 34 3 19 28 9 38 28 58 35 11 4 0 53 24 43 57 34 3 19 23 39 31 56 29 12 0 35 50 29 53 9 53 56 16 54 57 34 3 50 53 0 56 10 55 32 3 17 37 7 43 50 28 36 53 9 11 10 31 8 29 18 43 15 34 3 33 33 39 1 38 20 24 5 47 0 38 35 11 32 53 3 14 30 56 60 21 54 10 8 52 10 53 5 31 43 55 0 11 43 16 40 47 32 43 21 37 44 13 15 58 56 44 1 60 58 43 30 54 43 55 32 19 11 60 29 53 25 13 54 16 19 16 0 47 28 31 5 19 33 11 36 38 28 32 27 2 58 24 45 37 50 54 0 2 39 53 0 38 35 11 32 53 3 14 30 56 60 21 34 10 8 7 5 47 54 52 31 31 12 32 42 44 5 60 19 44 4 43 39 36 52 3 22 16 44 21 52 3 22 53 12 3 32 55 1 60 20 14 16 34 5 54 26 31 12 3 56 44 11 53 1 47 28 31 35 34 50 0 3 5 12 0 17 24 33 24 25 35 43 30 20 43 1 55 0 47 22 36 12 3 3 14 53 47 32 24 33 47 5 60 35 11 4 0 53 43 43 18 22 16 21 52 45 37 50 57 34 3 58 36 0 56 18 31 19 43 50 37 38 36 51 1 0 51 19 54 21 14 4 11 54 34 31 44 11 7 19 54 50 31 10 56 43 36 9 11 10 31 52 30 21 11 30 34 13 11 0 47 32 19 5 16 13 7 35 11 4 0 53 47 43 18 10 52 46 34 46 55 0 60 45 43 53 43 10 37 38 60 43 30 58 2 23 57 19 5 9 52 9 35 55 19 21 14 46 44 18 13 21 11 44 13 17 53 35 14 7 37 19 43 50 28 36 53 58 19 15 41 33 43 28 30 0 47 28 31 15 19 5 44 44 4 7 36 26 53 51 2 46 3 56 16 21 19 8 51 21 0 29 53 41 60 56 11 0 47 32 19 43 34 54 53 12 55 21 3 50 51 57 30 44 43 40 7 52 3 22 11 38 2 42 43 31 54 51 52 50 54 17 53 12 55 17 11 32 53 0 56 10 55 32 0 41 16 21 11 44 13 17 53 38 53 26 43 9 24 24 16 27 2 58 24 29 53 19 28 58 3 22 53 58 19 15 41 33 53 32 0 41 43 14 13 54 32 10 52 21 31 32 24 21 14 5 60 0 32 54 56 54 36 1 38 20 24 43 28 4 19 44 16 26 53 54 16 33 16 32 3 11 11 37 34 53 30 18 34 44 19 17 43 45 11 21 4 53 31 21 35 18 38 37 11 52 53 28 53 52 3 22 30 35 11 4 0 53 47 11 7 20 13 17 3 21 34 41 43 18 36 38 53 14 32 20 44 43 13 21 60 9 3 17 45 18 0 34 3 19 2 42 43 18 53 58 3 22 53 56 30 20 53 52 16 26 53 12 60 52 48 8 60 29 53 60 19 28 37 30 16 21 34 41 44 1 43 1 55 0 4 44 37 42 44 1 54 0 24 43 19 33 38 53 32 15 19 17 43 43 47 11 3 23 43 24 60 35 7 30 53 13 60 10 29 21 11 0 16 43 32 53 43 10 19 33 37 28 19 41 29 5 47 17 60 28 44 48 54 12 53 9 11 0 29 38 24 10 54 0 24 13 54 6 60 5 60 16 32 52 11 58 24 43 18 39 11 55 5 50 43 59 11 45 16 6 43 18 45 33 50 30 38 18 29 47 54 40 36 15 19 24 36 14 60 56 11 35 16 25 2 21 29 46 55 5 60 21 14 33 37 24 16 43 18 28 30 33 13 52 16 33 11 17 36 1 38 20 24 11 36 42 7 10 28 10 24 33 30 4 26 15 4 21 14 7 11 11 53 52 16 26 53 14 38 28 38 8 60 29 53 11 29 43 55 32 19 38 19 7 55 1 28 10 24 33 16 43 54 30 11 0 29 38 24 10 34 38 2 41 43 60 54 0 2 39 30 21 34 31 29 22 24 18 0 0
Ready. Press any key.
Висновки
Під час виконання даного завдання я вдосконалив свої знання про асиметричне шифрування кодом RSA та практично здійснив зашифрування та розшифрування слова СІМ. Основною проблемою, яка виникла стало співпадання деяких відкритих та зашифрованих символів. Думаю, це пов‘язано з тим, що використовувалися малі числа (ключ, модуль).
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора