Саратовский ГосударственныйУниверситет им. Н. Г. Чернышевского Курсовая работа Хеш-функции в криптосистемах Выполнил студент 112гр. КниИТИванченко Е. С. г. Саратов 2001Содержание Введение 3Методхэширования 3Коллизиии реверс 3Односторонниехэши 4Списоклитературы и сайтов последняя ВведениеВнаше время большую роль в информатике играют сетевые технологии, базирующиесяна объединении
огромного числа машин в единую сеть . Одним из ярких примеровтакой сети является Internet. Она основана на многопользовательских операционных системах, позволяющих управлять данными, хранящимися на удал нныхмашинах серверах сразу нескольким людям. Иногда требуется сделать доступнойдля всех только часть документов. Например, зачастую требуется скрытьпрограмный код cgi-скрипта от посторонних глаз, но весьма нежелательнозапрещать
его исполнение. Для этого операционной системе необходимо объяснить , кто является владельцем. В большинстве операционных системидентификация производится по логину и паролю. Но так как с файлом, в котором содержитсяэтот пароль, работают не один, а несколько пользователей, то хранение его воткрытом виде представляет угрозу сохранности документов. Для этогопотребовалось шифрование данных. МетодхэшированияОднимиз наиболее распростран нных методов
криптования является хэширование. Методхеширования позволяет хранить элементы из множества A в линейном массивеX. Математически это можно записать так h A 61614 0, x-1 т. е. Функция hотображает каждый элемент множества A в индекс множества X.Например пусть даныдва множества A a , b , c , и X 0, 1, 2, , тогда функция h A 61614
X ставит всоответствие каждому элементу из множества A элемент из множества B.Таким образом h a 0, h c 2 и т. д.Коллизиии реверсОднако,возможно существование такого интервала на области определения функции, вграницах которого она становится инъективной т.е. если h a 0, то существует такая функция, g X 61614 A, длякоторой g 0 a . Это означает, что только для одного элемента из множества A существует индекс x1.Функция будет инъективна и в том случае, если ниодин элемент из A не отображается на интервал x1, x2 приусловии, что последний не равен нулю. В любом другом случае на каждый индексмножества X отображается более одного элемента из A. Это такназываемая коллизия хэш-функции. Реверс хэш-функциизаключается в поиске всех отображаемых на данный индекс элементов. Для любогоконечного множества это разрешимая задача, которая имеет наиболее
простоерешение на инъективных интервалах хэш-множества.ОдносторонниехэшиВ криптовании используются особые хэш-функции, называемые односторонними.Функция 61614 Y называется односторонней,если 61606 x может быть легко вычислена для любого элемента измножества X, тогда для всех элементов из множества Y вычислениетакого аргумента x, для которого 61606 x y, не разрешимополиномиально.
Системы, построенные на односторонних функциях взлому, какправило, не поддаются. Основные аспекты написанияПри написанием алгоритма kript особое внимание уделялось следующимаспектам требования пользователя к алгоритму возможные варианты утечки зашифрованного пароля наиболее действенные методы расшифровки. 1. Требования пользователяОсновные требования к алгоритму с точки зрения пользователя являются над жность скорость работы системные требования необходимые ресурсы .
2. Варианты утечки пароляОдной из главной причиной утечки пароля при использовании этого алгоритмаслужит его хранение в открытом виде самим владельцем, поэтому большая частьатак в наше время рассчитана на доверие пользователя например, по телефонузвонит мнимый администратор сети и просит пароль для проведенияпрофилактических работ . В этом случае защита сводится к идентификации нетолько пользователя, но и машины, с которой производится запрос. Второй причиной служит его расшифровка. 3. Методы расшифровкиЭтот метод связан с использованием большинством пользователей слишкомпростых паролей длиной менее 8 символов, или, пароль, несущий на сбе какую-то смысловую нагрузку отчествопрабабушки по маминой линии . В этом случае атаки сводятся к переборувозможных паролей, а защита – к их усложнению. Для расшифровки пароля вторым методом, требуется знать его длину и алгоритмшифования. В случае, когда длина пароля составит менее восьми символов, можновоспользоваться следующим алгоритмом 1.
Перевернуть зашифрованный пароль. 2. Так как размер блока не может быть более 5 байт и менее 1байта, то разобь м его на 8 блоков и запишем в список список первых блоков,список вторых, и т. д Получим восьмиподсписковый список списков, каждыйподсписок которого представляет собой все возможные блоки шифрованных символов.3. Пробегаем в цикле по подсписку, сверяя каждый элемент совсеми символами из ASCII следующим образом If j generate x,n,j lt элементподсписка gt 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 interfacetypePlist 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 functiongenerate x integer a, b byte integer procedureadd in llist x integer s string var gr llist procedureprint llist gr llist proceduresumm all gr llist var a array type functionFromIntToString L longint string implementation Этафункция переводит из целочисленного типа в символьный functionFromIntToString var s string l1 longint begin l1 l s while l1 div 10 gt 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 Функциягенерации основная functiongenerate begin generate trunc abs 122.5 sin ln a x sin cos b x end Процедурадобавления в список списков procedureadd in llist var g llist l plist k, i, j byte begin k 1 i 1 while k lt length s do begin new g g .inf i g .nb nil j 1 while j lt 8 and k lt length s do begin new l l .inf ord s k generate x,ord s k ,k l .num j l .next g .nb g .nb l k k 1 j j 1 end g .next gr gr g i i 1 end end Процедуразаполнения массива a proceduresumm all var g llist l plist i 1 8 begin g gr while g lt gt nil do begin l g .nb i 1 while l lt gt nil do begin a i a i l .inf l l .next i i 1 end g g .next end end end.kript.pas programkuzik usescrt, kriptmod varx integer i 1 8 pass string l Llist arr array type f text begin clrscr randomize
Генерируем число x abs random 9999-101 101 write Password textcolor 0 readln pass add in llist x,pass,l summ all l,arr assign f, shadow rewrite f writeln f,x for i 1 to 8 dowrite f,FromIntToString arr i writeln f close f textcolor 2 writeln User added in base. repeat until keypressed end. unkript.pas program kuzik uses crt,kriptmod var x integer i 1 8 pass, pass1 string l Llist arr array type f text s, s1 string begin clrscr write
Password textcolor 0 readln pass Открываемфайл с паролями assign f, shadow reset f Читаемключ readln f,x Читаемзашифрованный пароль readln f,pass1 close f Шифруемтолько что введ нный пароль add in llist x,pass,l summ all l,arr for i 1 to 8 dos1 s1 FromIntToString arr i Сверяем егос паролем из shadow if pass1 s1 then begin textcolor 2 writeln Password correct. end else begin textcolor 4 writeln
Password incorrect! end repeat until keypressed end.