Курс "Защита информации", кафедра радиотехники, Московский физико-технический институт (МФТИ)

2010: Главная Экзамен Лекции Семинары Проекты Эссе | Преподаватели Литература | Архив: 2009 2008-fall 2008 2007 2006 2005 2004 2003 | English
HTML-версия эссе "Hash-functions development methods and analisys", Suslova_V, 2004, сгенерированная из pdf/rtf.
Конвертация не вcегда корректна. Смотрите исходный pdf.

Методыпостроенияхэш-функций. Иханализ.

ВыполнилаСусловаВера, группа 019 курс: Защитаинформации 2004 год

Методыпостроенияхэш-функций. Иханализ. .................................................................2

1.Чтотакоехэш-функция.......................................................................................................2

2. Методыпостроениякриптографическиххэш-функцийивопросыэффективности.........................................................................................................................3

2.1 N-хэш....................................................................................................................................4

2.2 MD4 ......................................................................................................................................4

2.3 MD5 ......................................................................................................................................5

2.4 SECURE HASH ALGORITHM (SHA)............................................................................6

2.5 MDC......................................................................................................................................7

Методыпостроенияхэш-функций. Иханализ.

1.Чтотакоехэш-функция.

Криптографическиеметодынетолькопозволяютобеспечиватьконфиденциальность, ноиконтролироватьцелостностьпередаваемыхданных. Контрольцелостности, какправило, осуществляетсяметодомвычисленияконтрольнойсуммыданных. Внастоящееразработанобольшоечислоалгоритмов, вычисляющихконтрольныесуммыпередаваемыхданных. Деловтом, чтовбольшинствеслучаевдостаточнопростойконтрольнойсуммы, например, втехслучаях, когдаобъеминформациинеизвестензаранееилиимеетзначениескоростьобработки.

Ноприиспользованиипростойконтрольнойсуммыможноподобратьнесколькомассивовданных, укоторыхбудетполучатьсяодинаковаяконтрольнаясумма. Криптографическистойкиеконтрольныесуммыполучаютсявслучаеприменениякисходномутекстухэш-функции.

Хэш-функция — этопроцедураобработкисообщения, врезультатедействиякоторойформируетсястрокасимволовфиксированногоразмера (дайджестсообщения). Изменениявтекстесообщенияприводяткизменениюдайджеста, получаемогопослепримененияхэш-функции. Поэтомулюбыеискажения, внесенныевтекстсообщения, отразятсявдайджесте.

Алгоритмпримененияхэш-функциизаключаетсявследующем:

Коллизии. Коллизиейхэш-функции H(X) называетсяситуация, когдасуществуютдваразличныхтекста X1 и X2, такихчто H(X1) = H(X2).

Основноетребование, предъявляемоекриптографическимиприложениямикхэш-функциям, состоитвотсутствииэффективныхалгоритмовпоискаколлизий.

Гипотезаосуществованииодностороннихфункций. Пододностороннейфункциейподразумеваютфункцию, определеннуюнамножественатуральныхчиселинетребующуюбольшихвычислительныхресурсовдлявычислениясвоегозначения. Втожевремявычислениеобратнойфункции, (когданужнопоизвестномузначениюфункциивосстановитьзначениеаргумента) оказываетсяневозможнотеоретически (либооченьсложнодлявычисления).

Существованиеодностороннихфункцийпоканедоказано, поэтомувсеиспользуемыевнастоящеевремяхэш-функцииявляютсялишь "кандидатами" водносторонниефункции, хотяиимеютдостаточнохорошиесвойства.

2. Методыпостроениякриптографическиххэш-функцийивопросыэффективности.

Внастоящеевремяиспользуюттриосновныхметодадляпостроенияхэш-функций:

  1. построениехэш-функциинаосновесуществующегоалгоритмашифрования(например, наосновешифровГОСТ 28147 - 89, DES и FEAL.),

  2. построениехэш-функциинаосновеизвестнойматематическойзадачи, какправиловычислительнотрудной (например, функцияизрекомендаций MKKTT X.509);

  3. построениехэш-функции "снуля".

Приразработкекриптографическистойкиххэш-функцийрекомендуетсяруководствоватьсяследующимипринципами (сформулированнымиРайвестом (Rivest)):

Какправило, хэш-функцияпоследовательноприменяютсякблокувходноготекста, приэтомиспользуетсяхеш-функция, полученнаянапредыдущемшаге. Поэтомухэш-кодомвсегосообщенияявляетсякод, получаемыйпослехэшированиявсеготекста: H i = h(H i1,

M i ), тоестьдляэффективностиинадежностихэш-функции, элементарнаяхэш-функциятожедолжнаудовлетворятьвышеперечисленным.

Наиболеестойкиехэш-функцииполучаютсяприпостроении “снуля”. Вэтомслучаерекомендуетсяиспользоватьизвестныеметодыипринципыпостроениянадежныхшифраторов.

2.1 N-хэш.

АлгоритмбылразработанфирмойНиппонтелефонэндтелеграф (Nippon Telephone & Telegraph) в 1990.

Навходподаютсяблокидлиной 128 битов, ккоторымприменяетсятакназываемая“размешивающая ” функция (аналогичнаяфункцииалгоритмашифрования FEAL), врезультатенавыходеполучаетсяхэш-кодв128 бит.

Накаждомшагеалгоритмавкачествеаргументаобрабатываетсяблоксообщениядлиной128 битихэш-кодпредыдущегошага. Хэш-кодомвсегосообщенияявляетсяхэш-код, полученныйпослеобработкицелоготекста.

Принципработы “размешивающей” функции: старшаяимладшаячастихэш-кода, полученногоотпредыдущегоблока, меняютсяместами, затемскладываютсясвеличиной1010…1010 (длиной 128 бит) иблокомхэшируемоготекста.

Хэш-кодотблокутекстапоступаетнавходкаскадаиз N (N=8) преобразующихфункций. Вкачествевторогоаргументапреобразующиефункциииспользуютхэш-кодпредыдущегошага, сложенныйпокоординатносоднойизвосьмиконстант.

Идеяиспользоватьалгоритмблочногошифрования, сизвестнойстойкостью, каксхемыхэширования, напервыйвзглядкажетсянеплохой. Однаковнекоторыхслучаяхэтоможетповлечьзасобойрядпроблем: необходимостьзаданиянекоторогоключа, спомощьюкоторогопроисходитшифрование. Этотключнеобходимосохранятьвсекрете, иначезнаяключиокончательныххэш-код, можновыполнитьпроцедурувобратномнаправлении.

Ещеодиннедостатоксостоитвтом, чторазмерыхэш-кодаиблокавалгоритмесовпадают. Вобщемслучаеразмерблокадостаточномал, чтоделаетсхемунеустойчивойкатакенаоснове "парадоксаднярождения". Сейчасиспользуютсяалгоритмыхэшированиясразмеромхэш-кодавтраз (часто, т=2) большим, чемразмерблокаалгоритмашифрования.

2.2 MD4

Алгоритм MD4 (Message Digest) былразработанРайвестом (Rivest). Присозданииалгоритмаразработчикстремилсядостичьследующихцелей:

  • Безопасность. Дляпостроенияколлизийнесуществуеталгоритмаэффективнееметода "грубойсилы" (т. е. метода, основанногона "парадокседнярождения").

  • Стойкостьалгоритмадолжна, подобношифраторам, обеспечиватьсяегособственнойконструкцией (т.е. алгоритмпостроенбезиспользованиякаких-либопредположительнотрудныхзадач).

  • Скорость. Существуетэффективнаяпрограммнаяреализацияна 32-разрядномпроцессоре.

  • Простотаикомпактность. Алгоритм MD4 неиспользуетсложныхструктурданныхиподпрограмм.

  • Алгоритмоптимизировандляегореализациинамикропроцессорахтипа Intel.

Вскорепослетого, какалгоритмстализвестен, былинайденыколлизиидля 2 из 3 раундовэтогоалгоритма. Хотяниодинизпредложенныхметодовпостроенияколлизийнеприводиткуспехудляполного MD4, Райвестусилилалгоритмипредложилновуюсхемухэширования MD5.

2.3 MD5

Отличия MD5 от MD4:

  • восновнойциклбылдобавленещеодиндополнительныйраунд (четвертый);

  • вкаждомоператореприсуммированиииспользуетсяуникальнаяконстанта;

  • измененафункция, использованнаявовторомраундесцельюсделатьееменеесимметричной.

  • кпромежуточнымрезультатамкаждогошагаприбавляютсярезультатыпредыдущихшагов, чтопозволяетусилитьэффектраспространенияошибки;

  • измененпорядоксчитываниясловвовторомитретьемраундах;

  • величинациклическогосдвигавкаждомраундеоптимизированасточкизренияусиленияэффектараспространенияошибки. Сдвигиотраундакраундуразличаются.

Входнойтекстделитсянаблокидлиной 512 бит, каждыйизэтихблоковделитсязатемна16 частейпо 32 бита, конкатенациякоторыхобразует 128-битовыйхэш-код.

Сначалатекстдополняетсятакимобразом, чтобыдлинаполучаемоготекста (вбитах) былана 64 меньшечисла, кратного 512. Этоосуществляетсяпутемдобавлениякконцутекста 1 инужногочисланулей. Затемктекступриписывается 64-битовоепредставлениедлиныисходногосообщения. Такимобразом, получаетсятекст, длинакоторогократна

512.

Инициализируются 4 переменныхпо 32 бита:

A = 01 23 45 67;

B = 89 AB CD EF;

C = FE DC BA 98;

В = 76 54 32 10.

Основнойциклалгоритма. Создаютсякопииначальныхпеременных: ААдля A, BB дляB, CC дляС, DD для D.

Вкаждомцикле, состоящемиз 4 раундовдействуют 16 операторов. Всеоператорывычисляютсякак : u=v+((F(v,w,z)+M i +t i <<s j .

Здесь u, v, w, z -это A, B, C и D вразличныхраундах.

M j обозначает j-тыйподблокобрабатываемогоблока. Вкаждомраундепорядокобработкиочереднымоператоромподблоковопределяетсязадаваемойвявномвидеподстановкойнамножествевсехподблоков (их, такжекакиоператоров, 16).

t i -случайныеконстанты.

Вконцеосновногоцикласуммируютсяпеременные A, B, C и D стекущими AA, BB, CC и DD. Этоиявляетсявыходомалгоритма, послеобработкипоследнегоблокаю

2.4 SECURE HASH ALGORITHM (SHA)

SHA разработанв 1993 годуНациональныминститутомстандартовитехнологий (NIST) СШАсовместносАгентствомнациональнойбезопасностиСША. Разработчикисчитают, чтодля SHA невозможнонайтиалгоритм, нетребующийбольшихвычислительныхресурсов, которыйпозволилбынайтиколлизии.

Врезультатепримененияалгоритмаполучаетсяхэш-коддлиной 160 бит. Процедурадополненияхэшируемоготекстадократного 512 битаманалогичнаподобнойпроцедуреалгоритма MD5.

Назначаются 5 переменныхпо 32 бита (валгоритме MD5 такихпеременныхбыло 4):

A = 67 45 23 01;

B = EF CD AB 89;

C = 98 BA DC FE;

D= 10 32 54 76;

У = С3 D2 E1 F0.

Такжекакив Md5 создаютсякопииэтихпеременных AA, BB, CC, DD и EE. Основныйциклданногоалгоритмасостоитиз 4 раундов, каждыйизкоторыхсостоитиз 20 операторов.

SHA скорееявляетсямодификацией MD4, нежелиновойразработкой. СравнимизмененияMD4, сделанныеприразработке MD5, иизменения, сделанныев MD4 приразработкеSHA.

  1. Вкаждомизалгоритмовиспользуется 4 раунд. В SHA функция, используемаяв 4 раундеаналогичнофункциииз 2 раунда.

  2. В SHA используетсятотжепринципаддитивнойконстантыдлякаждогооператоравраунде, чтоив MD4. (в MD5 константакаждогооператораотличаетсяотдругих).

  3. Вовторомраунде SHA используетсятажефункциячтоив MD4, тогдакакв MD5 онабылаизменена, чтобысделатьееменеесимметричной.

  4. Дляусиленияэффектараспространенияошибкив SHA добавлена 5-япеременнаяпокоторойидет "зацепление", врезультатеэтогометодденБура --Босселэра, эффективныйдля MD5, перестаетработатьвслучае SHA.

  5. Еслив MD5 измененпорядоксчитываниясловвовторомитретьемраундах, тов SHA входныесловасчитываютсяпоправилу, созданномунаосновекода, исправляющегоошибки.

  6. В MD5 величинациклическогосдвигаменяетсяотраундакраундуиотоператоракоператору, ав SHA используютпростыециклическиесдвиги

2.5 MDC

РазработанофирмойАйБиЭм (IBM). Вкачествесхемыхэшированияиспользуетблочныйшифр (воригинале DES) дляполученияхэш-кода, длинакотороговдваразабольшедлиныблокашифра. Существуютдвавариантаэтойразработки: MDC2 и MDC4. Перваяработаетнесколькобыстрее, ноявляетсяменеенадежной, чемвторая.

Схемавычисленияфункции MDС4.

H1 0= I1, где I1 --начальноезначение,

H2 0= I 2, где I2 --ещеодноначальноезначение;

X1 i || X2 i = E mod1(H1i1)(M1 i ) ⊕ M1 i ;

X3 i || X4 i = E mod 2(H1i1)(M2 i ) ⊕ M2 i ;

Y1 i || Y2 i = E mod1(X1i || X 4i ) (H2 i1) ⊕ H2 i1;

Y3 i || Y4 i = E mod 2(X 3i || X 2i )(H1 i1) ⊕ H1 i1;

H1 i =Y1 i ||Y4 i ;

H2 i =Y3 i ||Y2 i ;

Хэш-кодомявляетсяобъединениепоследнихзначений H1и H2 . Здесьобозначено: M1 иM2 --соответственнолеваяиправаячасти i-тогоблокахэшируемоготекста. Функцияmod1 простозаменяетзначения 1-гои 2-гобитоваргументаназначения 1 и 0 соответственно, а mod2 -- назначения 0 и 1.

Хэш-функция MDC4 использованавпроекте RIPE, хотяэффективность (скоростьхэшированияприпрограммнойреализации) уданнойсхемынизкая.

Литература.

  1. http://www.jetinfo.ru/2001/3/2/article2.3.2001126.html

  2. http://www.perspektiva.org/ecommerce/Glava3/Index61.html

  3. http://www.cryptography.ru/db/msg.html?mid=1161287&uri=node55.html


Page last update: Fri Jun 10 10:12:29 2005 MSD.
Website last update:
Rambler's Top100 Рейтинг@Mail.ru