Саратовский Державний Університет ім. Н. Г. Чернишевського
Курсова робота
«Хеш-функції в криптосистемах»
Виконав: студент 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.pasunit kriptmod;interfacetype 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;
(- Функція генерації (основна )------------------------ ---------------------< br>-)
function generate; begin generate: = trunc (abs (122.5 * (sin (ln (a) * x) + sin (cos (b) * x )))); end;
(- Процедура долучення до списку списків ------------------------------------ < br>----------}procedure add_in_llist; var g: llist; l: plist; k, i, j: byte; begin k: = 1; i: = 1; while (k
