Саратовский Державний Університет ім. Н. Г. Чернишевського
Курсова робота
«Хеш-функції в криптосистемах»
Виконав: студент 112гр. КніІТ
Іванченко Е. С.
р. Саратов 2001
Зміст
Введення
3
Метод хешування
3
Колізії і реверс
3
Односторонні хэши
4
Список літератури і сайтів
остання
Введення
У наш час велику роль в інформатиці грають мережеві технології, що базуються на поєднанні
величезної кількості машин в єдину мережу. Одним з яскравих прикладів такої мережі є Internet. Вона заснована на розрахованих на багато користувачів операційних системах, що дозволяють керувати даними, що зберігаються на віддалених
машинах (серверах) відразу декільком людям. Іноді потрібно зробити доступною для всіх лише частину документів. Наприклад, часто потрібно приховати
програмний код cgi-скрипта від сторонніх очей, але дуже небажано забороняти його виконання. Для цього операційній системі необхідно
"Пояснити", хто є власником. У більшості операційних систем ідентифікація проводиться за логіном і паролем. Але так як з файлом, в якому
міститься цей пароль, працюють не один, а кілька користувачів, то зберігання його у відкритому вигляді становить загрозу збереження документів. Для
цього треба було шифрування даних.
Метод хешування
Одним з найбільш поширених методів криптування є хешування. Метод хешування
дозволяє зберігати елементи з безлічі A у лінійному масиві X . Математично це можна записати так:
h: A ® (0, x-1)
т. тобто Функція h відображає кожен елемент безлічі A в індекс безлічі X .
Наприклад: нехай дані два безлічі A ( 'a', 'b', 'c', ...) і X (0, 1, 2, ...) , тоді функція h: A ® X ставить у відповідність кожному
елементу з безлічі A елемент з безлічі B . Таким чином h ( 'a') = 0 ,
h ( 'c') = 2 і т. д.
Колізії і реверс
Однак, можливе існування такого інтервалу на області визначення функції, в межах
якого вона стає ін'ектівной (тобто якщо h ( 'a') = 0, то існує така функція, g: X ® A , для якої g (0) = 'a' ).
Це означає, що тільки для одного елемента з безлічі A існує індекс x1. Функція буде ін'ектівна і в тому випадку, якщо жоден елемент з A не
відображається на інтервал (x1, x2) за умови, що останній не дорівнює нулю. У будь-якому іншому випадку на кожен індекс безлічі X відображається
більше одного елемента з A . Це так звана колізія хеш-функції.
Реверс хеш-функції полягає в пошуку всіх відображаються на даний індекс елементів. Для будь-якого кінцевого безлічі
це здійсненне завдання, яке має найбільш просте рішення на ін'ектівних інтервалах хеш-множини.
Односторонні хэши
У криптування використовуються особливі хеш-функції, що називаються односторонніми. Функція
|: X ® Y називається односторонньою, якщо | (x) може бути легко обчислена для будь-якого елемента з безлічі X, тоді для всіх елементів з
безлічі Y обчислення такого аргументу x, для якого | (x) = y , не розв'язна поліноміальною. Системи, побудовані на односторонніх функціях
злому, як правило, не піддаються.
Основні аспекти написання
При написанням алгоритму kript особлива увага приділялася таким аспектам:
вимоги користувача до алгоритму;
можливі варіанти витоку зашифрованого пароля;
найбільш дієві методи розшифровки.
1. Вимоги користувача
Основні вимоги до алгоритму з точки зору користувача є:
надійність;
швидкість роботи;
системні вимоги (необхідні ресурси).
2. Варіанти витоку пароль
Однією з головною причиною витоку пароля при використанні цього алгоритму є його
зберігання у відкритому вигляді самим власником, тому більша частина атак в наш час розрахована на довіру користувача (наприклад, по телефону дзвонить уявний
адміністратор мережі і просить пароль для проведення профілактичних робіт). У цьому випадку захист зводиться до ідентифікації не тільки користувача, але й машини, з
якої здійснюється запит.
Другою причиною служить його розшифровка.
3. Методи розшифровки
Цей метод пов'язаний з використанням більшістю користувачів занадто простих паролів
(завдовжки менше 8 символів, або, пароль, що несе на сбе якусь смислове навантаження (по батькові прабабусі по маминій
лінії)). У цьому випадку атаки зводяться до перебору можливих паролів, а захист - до їх ускладнення.
Для розшифровки пароля другу методом, потрібно знати його довжину і алгоритм шіфованія. У випадку, коли довжина пароля складе менше восьми символів, можна
скористатися наступним алгоритмом:
1. Перевернути зашифрований пароль.
2. Так як розмір блоку не може бути більше 5 байт і менше 1 байта, то розіб'ємо його на 8 блоків і запишемо у список (список перших блоків,
список другого, і т. д.). Отримаємо восьміподспісковий список списків, кожен подспісок якого представляє собою всі можливі блоки зашифрованих символів.
3. Пробігаємо в циклі по підсписки, звіряючи кожен елемент з усіма символами з ASCII наступним чином:
If j * generate (x, n, j) = then write (ord (j)), де j десятковий код символу, x - ключ, n --
послідовний номер символу в паролі (у діапазоні [1, 8]). Якщо виконати цю умову, то виведемо на екран знайдений символ.
Після виконання алгоритму на виході отримаємо або пароль, або таку послідовність, з якої його можна отримати.
Опис
В основі алгортма лежить функція від трьох аргументів generate = trunc (k * (abs (sin (ln (a) * x) +
sin (cos (b) * x )))):
1. ключа ( x );
2. десяткового код символу ( a );
3. номера символу під введеної рядку ( b ).
Вона використовується для перетворення десяткового коду символу до числа, яке лежить в інтервалі від 0
до 2 * k , де k - будь-яке число цілого типу. Чим більше число k - тим менше ймовірність колізій в подальшому.
Після обробки символу він додається до списку списків процедурою add_in_list (x:
integer; s: string; var gr: llist) в такий спосіб - l ^. inf: = ord (s [k]) * generate (x, ord (s [k]), k) ,
де l ^. inf -елемент списку списків, x - ключ (для функції generate ), s - рядок , розбивається на блоки по 8 символів.
Кожен подспісок має довжину не більше 8 елементів розміром до 5 байт.
Третім кроком є складання відповідних елементів процедурою summ_all (gr: llist; var
a: array_type) з кожного підсписки l у 8 елментний масив a , тобто перший елемент з першого елемента складається з
першим елементом другого, третього і т.д. підсписки і записується в a [1] .
Так - само чинимо і з іншими елементами підсписки.
Наступним щагом записуємо в файл ключ і по черзі всі елементи масиву a , оброблені функцією FromIntToString (), яка переводить
чисельний тип в символьний і перевертає.
Для звірки пароля його потрібно зашифрувати заново за відомим ключа та звірити з зашифрованих екземпляром.
Ось початковий текст програми:
kriptmod.pas
unit kriptmod;
interface
type Plist = ^ list;
list = record
inf: word;
num: 1 .. 8;
next: Plist;
end;
Llist = ^ List_of_list;
List_of_list = record
nb: Plist;
inf: 1 .. 32;
next: Llist;
end;
array_type = array [1 .. 8] of longint;
function generate (x: integer; a, b: byte): integer;
procedure add_in_llist (x: integer; s: string; var gr: llist);
procedure print_llist (gr: llist);
procedure summ_all (gr: llist; var a: array_type);
function FromIntToString (L: longint): string;
implementation
(- Ця функція переводить з цілочисельного типу в символьний ------------------------------------ ----------}
function FromIntToString;
var s: string;
l1: longint;
begin
l1: = l; s :='';
while (l1 div 10> 0) do
begin
case l1 mod 10 of
0: s: = s + '0 ';
1: s: = s + '1 ';
2: s: = s + '2 ';
3: s: = s + '3 ';
4: s: = s + '4 ';
5: s: = s + '5 ';
6: s: = s + '6 ';
7: s: = s + '7 ';
8: s: = s + '8 ';
9: s: = s + '9 ';
end;
l1: = l1 div 10;
end;
case l1 mod 10 of
0: s: = s + '0 ';
1: s: = s + '1 ';
2: s: = s + '2 ';
3: s: = s + '3 ';
4: s: = s + '4 ';
5: s: = s + '5 ';
6: s: = s + '6 ';
7: s: = s + '7 ';
8: s: = s + '8 ';
9: s: = s + '9 ';
end;
FromIntToString: = s;
end;
(- Функція генерації (основна )--------------------------------------- -------}
function generate;
begin
generate: = trunc (abs (122.5 * (sin (ln (a) * x) + sin (cos (b) * x ))));
end;
(- Процедура долучення до списку списків --------------------------------------- -------}
procedure add_in_llist;
var g: llist;
l: plist;
k, i, j: byte;
begin
k: = 1; i: = 1;
while (k
