Хеш-функції у криптосистемах

Саратовський Державний Університет їм. М. Р. Чернышевского.

Курсова работа.

«Хеш-функции в криптосистемах».

Виконав: студент 112гр. КниИТ.

Іванченка Є. С.

р. Саратов 2001.

Метод хэширования.

Колізії і реверс.

Односторонні хэши.

Список літератури та сайтів последняя.

Нині великій ролі в інформатики грають мережні технології, що базуються на об'єднанні величезної кількості машин єдину мережу. Однією з яскравих прикладів такої мережі є Internet. Вона полягає в многопользовательских операційні системи, дозволяють управляти даними, хранящимися на удалённых машинах (серверах) одразу кільком людям. Іноді слід зробити доступною всім тільки п’яту частину документів. Наприклад, найчастіше потрібна приховати програмный код cgi-скрипта від від сторонніх очей, але дуже небажано забороняти його виконання. Для цього операційній системі необхідно «пояснити», хто є власником. У багатьох операційними системами ідентифікація проводиться у разі логину і паролю. Та оскільки з файлом, де міститься цей пароль, працюють не один, а кілька користувачів, то зберігання їх у відкритому вигляді загрожує схоронності документів. І тому знадобилося шифрування данных.

Метод хэширования.

Однією з найбільш поширених методів криптования є хэширование. Метод хеширования дозволяє зберігати елементи з багатьох A в лінійному масиві X. Математично це можна зробити записати так:

h: A ® {0, x-1}.

т. е. Функція h відображає кожен елемент безлічі A в індекс безлічі X. Наприклад: нехай дано два безлічі A {‘a', 'b', 'з', …} і 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. Оскільки розмір блоку може бути понад п’ять байт і менше 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; p. s: string; var gr: llist) так — l^.inf:=ord (s[k])*generate (x, ord (s[k]), k), де l^.inf-элемент списку списків, x — ключ (для функції generate), p. s — рядок, разбиваемая на блоки по 8 символів. Кожен подсписок має довжину трохи більше 8 елементів розміром до 5 байт.

Третім кроком є складання відповідних елементів процедурою summ_all (gr: llist; var a: array_type) з кожного подсписка l у вісім элментный масив 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; p. 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 p. s: string; l1: longint; begin l1:=l; p. s:= «»; while (l1 divx 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 divx 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, і, j: byte; begin k:=1; i:=1; while (k.