Роторные машины и Функция хэширования SHA-1

Оглавление

Вопрос 6. Роторные машины 2

Введение 2

История появления алгоритма 2

Описание алгоритма 3

Достоинства и недостатки 6

Применение на практике 6

Вопрос 26. Функция хэширования SHA-1 8

Введение 8

История появления алгоритма 9

Описание алгоритма 9

Достоинства и недостатки 14

Применение на практике 15

 

Вопрос 6. Роторные машины

Введение

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

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

В первой половине ХХ века для автоматизации процесса выполнения многоалфавитных подстановок  стали широко применять роторные шифровальные машины.

История появления  алгоритма

В 1790-х годах будущий президент США Томас Джефферсон построил одну из первых механических роторных машин, упрощавшей использование полиалфавитных шифров. Среди других авторов-изобретателей стоит отметить полковника Десиуса Вадсворта (англ. Decius Wadsworth), изобретателя машины с вращательными шифровальными дисками с различным количеством букв. Хотя он изобрёл её в 1817 году, вся слава досталась Чарлзу Уитстону за аналогичную машину, представленную на Всемирной выставке 1867 года в Париже. Однако распространение роторные машины получили лишь в начале XX века.

В начале 1920-х  годов практически одновременно в разных странах появляются патенты  и электромеханические машины, использующие принципы криптографического диска (ротора) и автоматизирующие процесс шифрования. В США это был Эдвард Геберн (англ. Edward Hebern), после него — Хьюго Кох (англ. Hugo Koch) из Нидерландов и его «Энигма» (позже патент был куплен Артуром Шербиусом (англ. Arthur Scherbius)), Арвид Герхард Дамм из Швеции и его машина «B-1» — разработки последнего были продолжены Борисом Хагелиным.

«Энигму»  широко использовалась на немецком вооружении во времена Второй Мировой войны. Немецкие военные усовершенствовали «Энигму». Без учёта настройки положения колец, количество различных ключей составляло 1016. В конце 1920-х — начале 1930 годов, несмотря на переданные немецким аристократом Хансом Тило-Шмидтом данные по машине, имевшиеся экземпляры коммерческих вариантов, британская и французская разведка не стали браться за задачу криптоанализа. Вероятно, к тому времени они уже сочли, что шифр является невзламываемым. Однако группа из трёх польских математиков так не считала, и, вплоть до 1939 года, вела работы по «борьбе» с «Энигмой», и даже умела читать многие сообщения, зашифрованными «Энигмой» (в варианте до внесения изменений в протокол шифрования от декабря 1938 года). У одного из них, Мариана Реевского зародилась идея бороться с криптографической машиной с помощью другой машины. Идея озарила Реевского в кафе, и он дал машине имя «Бомба» по названию круглого пирожного. Среди результатов, переданных британским разведчикам перед захватом Польши Германией, были и «живые» экземпляры «Энигмы», и электромеханическая машина «Bomba», состоявшая из шести спаренных «Энигм» и помогавшая в расшифровке (прототип для более поздней «Bombe» Алана Тьюринга), а также уникальные методики криптоанализа.

Описание алгоритма

Главной деталью  роторной машины является ротор, на внешней  и внутренней стороне которого расположено  по n контактов.

n – число символов исходного  алфавита.

Каждый контакт  на внешней стороне соединен с  одним из контактов на

внутренней стороне. Соединение определяет таблицу подстановки. Соединение может быть изменено при помощи перемычек.

Роторная  машина состоит из нескольких роторов  и механизма их вращения.

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

Число таблиц подстановки для m роторов и алфавита из n символов

равно n^m.

Учитывая, что  для английского алфавита число  всевозможных таблиц подстановки ≈ 26!, то число роторов не превышает 10.

Для упрощения  реализации роторных машин как правило  один ротор дважды используется при  шифровании.

 

 

Ключом роторной машины может быть ее различные параметры, такие как:

• число роторов;

• порядок  подключения роторов;

• коммутация каждого ротора;

• механизм перемещения  ротора.

Развитием классической роторной машины стала ее электронная  версия. Основным компонентом этой версии является запоминающее устройство, которое выполняет функцию ротора.

R/W - операция  с памятью:

1 –  чтение данных;

0 –  запись данных.

CS – выбор  кристаллов, разрешает работу данного  АЗУ.

Пример:

Рассмотрим  АЗУ, для которого n = m = 8

АЗУ способно хранить 256х8 бит.

Содержимое  АЗУ определяет таблицу подстановки.

Чтобы применять  таблицу подстановки, необходимо занести  новую информацию в память

Достоинства и  недостатки

К достоинствам роторных машин  можно отнести:

1. высокая  криптостойкость (в свое время);

2. высокое  быстродействие;

3. простота  как программной, так и аппаратной  реализации;

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

Применение на практике

Фиалка (М-125) — шифровальная машина, разработанная в СССР вскоре после Второй мировой войны. Использовалась странами Варшавского договора до 1990-х годов. Большая часть машин после распада СССР была разобрана или уничтожена. Несколько экземпляров хранятся в частных коллекциях и музеях. Работающая модель представлена в Музее компьютерной истории (Computer History Museum) в США и Блетчли-Парке (Bletchley Park) в Великобритании. В истории криптографии мало что известно о Фиалке, до 2005 года вся информация об устройстве держалась в секрете. Правильное определение "Фиалки" - кодировочная машина т.к. обладала более слабой криптостойкостью чем шифровальные машины.

Энигма  — портативная шифровальная машина, использовавшаяся для шифрования и дешифрования секретных сообщений. Более точно, Энигма — целое семейство электромеханических роторных машин, применявшихся с 20-х годов XX века. Энигма использовалась в коммерческих целях, а также в военных и государственных службах во многих странах мира, но наибольшее распространение получила в нацистской Германии во время Второй мировой войны — именно Энигма вермахта (Wehrmacht Enigma) — германская военная модель — чаще всего является предметом дискуссий. Эта машина получила дурную славу, потому что криптоаналитики Антигитлеровской коалиции (точнее, Великобритании) смогли расшифровать большое количество сообщений, зашифрованных с её помощью. Специально для этих целей была создана машина с кодовым названием Turing Bombe, оказавшая значительную помощь Антигитлеровской коалиции (точнее, Великобритании) в войне. Вся информация, полученная криптоанализом с её помощью, имела кодовое название Ultra.

Purple — американское кодовое название японской шифровальной машины, известной в Японии как «Алфавитная печатная машина типа 97» или «Шифровальная машина типа B». Она использовалась Министерством иностранных дел Японии до и во время Второй мировой войны. Механизм работы прибора был основан на работе шагового искателя. Проект по дешифровке информации получил в США кодовое имя Magic. Шифровальная машина Purple пришла на замену шифратору Red, использовавшемуся тогда Министерством иностранных дел Японии.

Вопрос 26. Функция  хэширования SHA-1

Введение

Secure Hash Algorithm 1 — алгоритм криптографического  хеширования. Хэш-функцией называется  односторонняя функция, предназначенная  для получения дайджеста или  "отпечатков пальцев" файла,  сообщения или некоторого блока  данных.

Хэш-код создается функцией Н: h = H (M), где М является сообщением произвольной длины и h является хэш-кодом фиксированной длины.

Для того, чтобы  хеш-функция H считалась криптографически стойкой, она должна удовлетворять  трем основным требованиям, на которых  основано большинство применений хеш-функций  в криптографии:

• Необратимость или стойкость к восстановлению прообраза: для заданного значения хеш-функции m должно быть вычислительно невозможно найти блок данных X, для которого {H(X)=m}.
• Стойкость к коллизиям первого рода или восстановлению вторых прообразов: для заданного сообщения M должно быть вычислительно невозможно подобрать другое сообщение N, для которого H(N)=H(M).
• Стойкость к коллизиям второго рода: должно быть вычислительно невозможно подобрать пару сообщений ~(M, M'), имеющих одинаковый хеш.

Данные требования не являются независимыми:

• Обратимая функция нестойка к коллизиям первого и второго рода.
• Функция, нестойкая к коллизиям первого рода, нестойка к коллизиям второго рода; обратное неверно.

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

 

Атака «дней  рождения» позволяет находить коллизии для хеш-функции с длиной значений n битов в среднем за примерно 2^{n/2} вычислений хеш-функции. Поэтому n-битная хеш-функция считается криптостойкой, если вычислительная сложность нахождения коллизий для неё близка к 2^{n/2}.

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

История появления  алгоритма

В 1993 году NSA совместно  с NIST разработали алгоритм безопасного  хеширования (сейчас известный как SHA-0) (опубликован в документе FIPS PUB 180) для стандарта безопасного  хеширования. Однако вскоре NSA отозвало данную версию, сославшись на обнаруженную ими ошибку, которая так и не была раскрыта. И заменило его исправленной версией, опубликованной в 1995 году в  документе FIPS PUB 180-1. Эта версия и  считается тем, что называют SHA-1. Немного спустя, на конференции CRYPTO в 1998 году два французских исследователя  представили атаку на алгоритм SHA-0, которая не работала на алгоритме SHA-1 Возможно, это и была ошибка, открытая NSA.

Описание алгоритма

Алгоритм получает на входе  сообщение максимальной длины 264 бит и создает в качестве выхода дайджест сообщения длиной 160 бит.

Алгоритм состоит из следующих  шагов:

 
Рис. 9.1. Логика выполнения SHA-1

Шаг 1: добавление недостающих  битов

Сообщение добавляется таким образом, чтобы его длина была кратна 448 по модулю 512 (   ). Добавление осуществляется всегда, даже если сообщение уже имеет нужную длину. Таким образом, число добавляемых битов находится в диапазоне от 1 до 512.

Добавление состоит из единицы, за которой следует необходимое  количество нулей.

Шаг 2: добавление длины

К сообщению добавляется блок из 64 битов. Этот блок трактуется как беззнаковое 64-битное целое и содержит длину  исходного сообщения до добавления.

Результатом первых двух шагов является сообщение, длина которого кратна 512 битам. Расширенное сообщение может быть представлено как последовательность 512-битных блоков Y0, Y1, . . . , YL-1, так что общая длина расширенного сообщения есть L * 512 бит. Таким образом, результат кратен шестнадцати 32-битным словам.

Шаг 3: инициализация SHA-1 буфера

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

A = 67452301

B = EFCDAB89

C = 98BADCFE

D = 10325476

E = C3D2E1F0

Шаг 4: обработка сообщения  в 512-битных (16-словных) блоках

Основой алгоритма является модуль, состоящий из 80 циклических обработок, обозначенный как HSHA. Все 80 циклических обработок имеют одинаковую структуру.

 
Рис. 9.2. Обработка очередного 512-битного блока

Каждый цикл получает на входе текущий 512-битный обрабатываемый блок Yq и 160-битное значение буфера ABCDE, и изменяет содержимое этого буфера.

В каждом цикле используется дополнительная константа Кt, которая принимает только четыре различных значения:

0  <= t <= 19  K_t = 5A827999

(целая часть числа [2³⁰ x 2^1/2])

 

20 <= t <= 39  K_t = 6ED9EBA1

(целая часть числа [2³⁰ x 3^1/2])

 

40 <= t <= 59  K_t = 8F1BBCDC

(целая часть числа [2³⁰ x 5^1/2])

 

60 <= t <= 79  K_t = CA62C1D6

(целая часть числа [2³⁰ x 10^1/2])

Для получения SHAq+1 выход 80-го цикла складывается со значением SHAq. Сложение по модулю 232 выполняется независимо для каждого из пяти слов в буфере с каждым из соответствующих слов в SHAq.

Шаг 5: выход

После обработки всех 512-битных блоков выходом L-ой стадии является 160-битный дайджест сообщения.

Рассмотрим более детально логику в каждом из 80 циклов обработки одного 512-битного блока. Каждый цикл можно  представить в виде: