tanenbaum_seti_all.pages (525408), страница 231
Текст из файла (страница 231)
Их начальные значения — это постоянные величины, определенные стандартом. Начало сообщения б12-битный блок 32-разрядное слово НОС:3 ИГО С:3 мт с::) с.:) с:и:и":) с".) с:] с:ис::) с:и:и:) с:Л с:Л с::) сЛ н1 с:Л иг1 С") мз с — и — ис — )~ — )~ — )( — )~ — и )1 — )с — )с-~~ — )с — )~ — ~~ — )с — ) Нзс-~ игз дополнение нз с:.) М, С:3ПС:3С::ВС::)С:ВС:ВС:3С:3С:3С:ВС:3С:АВВЕ) ЕД)В И С::) Иг С::) б е Рис. 8.19. Сообщение, дополненное до размере, кратного 512 битам (а)1 выходные переменные (бИ массив слов (в) Затем поочередно обрабатываются блоки с М, по М„г Для текущего блока 16слов сначала копируются в начало вспомогательного массива ((г размером 80 слов, как показано иа рис.
8.19, в. 64 оставшихся слова вычисляются с использоваиием следующей формулы: )(~~ Б~(% ХОК (( ХОК ))~' н ХОК )' и) (16 ь 1< 79), где У()Р) представляет собой поворот 32-разрядпого слова )(г на Ь бит. Теперь по значениям Н, ... Н, инициализируются переменные от т( до Е. Сами вычислеиия иа псевдо-С можно записать таким образом; тог(1 О; 1<ВО н н) ( (аар - 5'(А) + б(В, С, 0) е Е + И. + К,. Е-О. 0 С; С-5а(В).
В-А; А-Геар: где постояииые К, определяются стандартом. Смешиваюшие функции уг задаются следующим образом: ~(В, С, )3) = (В А)х)0 С) ОК ()х)ОТ В А)х)) ) г)) (О <1~ 19), ДВ, С, Е)) = В ХОК С ХОК 0 (20 <(< 39), ЦВ, С, П) = (В АХВ С) ОК (В АЛЕ) И) ОК (С АВ)Е) 2)) (40 ~ 39), У(В, С,2)) = В хок с хок 1) (60 < 1 < 79). После 80 итераций цикла значения переменных Л ...
Е добавляются к Н, ... Н, соответственно. ЦиФровые подписи 861 После обработки первого 512-битного блока начинается обработка следую щего. Массив йг инициализируется заново с помощью нового блока, однако Н сохраняется неизменным. По окончании этого блока обрабатывается следующий и так далее, пока все 512-разрядные блоки сообщения не попадут в эту кастрюлю. После обработки последнего блока пять 32-разрядных слов в массиве Н выводятся в качестве 160-битного значения криптографической хэш-функции.
Полный код 8НА-1 приведен в ВЕС 3174. В настоящее время идет работа над новыми версиями 3НА-1 с 256ь 384- и 512-разрядными значениями хэш-функций, Задача о днях рождения В мире шифров многое оказывается совсем не таким, каким кажется на первый взгляд. Можно, например, предполагать, что для ниспровержения профиля сообщения, состоящего нз гп разрядов, потребуется порядка 2~ операций. На самом деле, часто оказывается достаточно 2н л операций, если использовать метод, основанный на задаче о днях рождения, опубликованный в ставшей классической книге (апта!, 1979).
В основе идеи этого метода лежит задача, часто приводимая в качестве примера профессорами математики на курсах по теории вероятности. Вопрос: сколько студентов должно находиться в классе, чтобы вероятность появления двух человек с совпадающими днями рождения превысила 1/2? Большинство студентов обычно ожидают, что ответ будет значительно больше 100. На самом же деле, теория вероятности утверждает, что это число равно 23. Не вдаваясь в тонкости анализа атой проблемы, палим интуитивно понятное объяснение: из 23 человек мы можем сформировать (23 22)/2 = 253 различных пары, у каждой из которой дни рождения могут совпасть с вероятностью 1/365.
Теперь этот ответ уже не кажется таким удивительным. В более общем случае, если имеется некое соответствие между и входами (людьми, сообщениями и т. д.) и л возможными выходами (днями рождения, профилями сообщений и т. д.), мы имеем ~(и — 1)/2 входных пар. Если п(п — 1)/2 > Й, то вероятность того, что будет хотя бы одно совпадение выхода при различных входах, довольно велика, Таким образом, вероятность существования двух сообщений с одинаковыми нрофплямн велика уже при и > %. Это означает, что 64-разрялный профиль сообщения можно с большой вероятностью взломать (то есть найти два различных сообщения с одинаковым профилем), перебрав 2" сообщений.
Рассмотрим практический пример. На кафедре компьютерных наук Государственного университета появились вакансия и два кандидата на эту должность, Том и Дик. Том работает на факультете на два гола дольше Дика, поэтому его кандидатура будет рассматриваться первой. Если он получит эту должность, значит, Дику не повезло. Том знает, что заведующая кафедрой Марилин высоко ценит его работу, поэтому он просит ее написать для него рекомендательное письмо декану факультета, который будет решать дело Тома. После отправки все письма становятся конфиденциальными. 862 Глава 8. Безопасность в сетях Мэрилин просит написать это письмо декану свою секретаршу Элен, подчеркивая, что она хотела бы видеть в этом письме. Когда письмо готово, Мэрилин просматривает его, подписывает 64-разрядной подписью и посылает декану. Позднее Элеи может послать это письмо электронной почтой. К несчастью для Тома, у Элен роман с Диком, и она хочет обмануть Тома.
Поэтому она пишет следующее письмо с 32 вариантами в квадратных скобках. Уважаемый господин декан, Это [письмо ) обращение) отражает мое (искреннее ~ откровенное) мнение о проф. Томе Уилсоне, являсошемся (кандидатом ] претендентом) иа профессорскую должность [в ссастоящее время ] в этом году). Я (знакома ] работала) с проф. Уилсоном в течение [почти ] около) шести лет. Он является (выдающимся ] блестлщим] исследователем, обладающим [большим талантом ] большими возможностями] и известнылс [во всем мире ] пе только в кашей стране) своим [серьезным ~ созидательным) подходом к [большому числу ] широкому спектру] [сложных ] перспективных) вопросов.
Он также является [высоко ( весьма] [уважавмым ) ценимым) [преподавателем ] педагогом]. Его студенты дают его [занятиям ] лекциям] [самые высокие ] высочайшие] оценки. Он самый (популярный ] любимьсй] (преподаватель ] учитель) (нашей кафедры / нашего университета). [Кроме ~ Помимо) того, (гранты ] контракты] проф. Уилсона [существенно ~ значительно) пополнили (фонды ] финансовые запасы] нашей кафедры. Эти [денежные ] финансовые) средства [позволили кам ~ дали возможность] [выполнить ~ осуществить] (много ] ряд) [важных ] специальных) программ, [таких как ] среди которых], государственная программа 2000 года. Без этих средств было бы невозможным продолжение этой программьс, такой [важной ~ значительной) для нас.
Я настойчиво рекомендую вам предоставить ему эту должность. К несчастью для Тома, закончив печатать это письмо, Элен тут же принимается за второе: Уважаемый господин декан, Это [письмо ] обращение] отражает мое (искреннее ) откровенное) [мнение ) суждение] о проф. Томе Уилсоне, являющемся (кандидатом ] претендентом) на профессорскую должность в [настоящее время ] этом году]. Я (знакома ~ работала] с проф. Уилсоном в течение [почти ] около] шести лет. Он является [слабым ] недостаточно талантливым) (исследователем ] ученым], почти не известным в той области науки, которой он занимается.
В его работах практически не заметно понимания [ключевых ] главных) (проблем ~ вопросов] современности. (Более ] Кроме] того, он также не является сколько-нибудь [уважаемым ] ценимым) (преподавателем ] педагогом). Его студенты дают его [запятиям ] лекциям) (самые низкие ( негативные] оценки. Он самый непопулярный «преподаватель ( учитель) нашей кафедры, [славящийся ~ печально известный] своей [привычкой ) склонностью] (высмеивать ]ставить в иеудобпое положение] стулентов, осмелившихся задавать вопросы на его (лекциях ~ занятиях]. (Кроме ) Помимо) того, [граиты ] контракты) проф.
Уилсона [почти ] практически] не пополняют (фондов ] финансовых запасов] нашей кафедры. Если не удастся быстро найти новый источник финансирования, [мы будем еьснуждены ] Управление открытыми ключами 868 нам придется] )закрыть ) прекратить) )много ~ ряд) )валсных ~ специальных) программ, )таюгх как ! среди которых) государственная программа 2000 года.
К сожалению, при таких [условиях ( обстоятельствах) я не могу )предлагать ( рекомендовать) его вам на зту должность. Затем Элен заставляет свой компьютер сосчитать 2гл профиля сообгцения для каждого варианта обоих писем, что занимает всю ночь. Есть шансы, что олин профиль первого письма совпадет с одним из профилей второго письма. Если нет, она может добавить еще несколько вариантов слов и выражений в каждое письмо и попытаться еще раз за выходные. Предположим, что ей удалось найти такое совпадение. Назовем положительный отзыв письмом А, а отрицательный— письмом В, Элен отправляет письмо А электронной почтой Мэрилин на утверждение.
Мэрилин, конечно, утверждает письмо, вычисляет 64-разрядный профиль сообщения, подписывает профиль и посылает по почте подписанный профиль декану, Независимо Элен посылает декану письмо В (вместо письма А, которое следует отправить на самом деле). Получив письмо и подписанный профиль, декан запускает алгоритм вычисления профиля сообщений для письма В, видит, что его профиль совпадает с тем, что ему прислала Мэрилин, и увольняет Тома. Он даже не может себе представить, что Элен удалось создать два письма с одинаковыми профилями сообщений и отправить ему совсем не тот вариант, который читала и подписала Мэрилин. (Вариант с хэппи-эндом, столь любимым американцами: Элен сообщает Дику о своих проделках. Потрясенный Дик порывает с ней.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
