NUSH («Наш») - блочный алгоритм симметричного шифрования, разработанный Анатолием Лебедевым и Алексеем Волчковым для российской компании LAN Crypto.
NUSH имеет несколько различных вариантов, имеющих разный размер блока (64, 128, 256 бит), различное число раундов (в зависимости от размера блока равно 36, 128 или 132 раунда) и использует длину ключа в 128, 192 или 256 бит. Алгоритм не использует S-блоки, а только такие операции, как AND, OR, XOR, сложение по модулю и циклические сдвиги. Перед первым и после последнего раунда проводится «отбеливание» ключа.
Данный алгоритм был выдвинут в проекте NESSIE , но не был выбран, так как было показано, что линейный криптоанализ может быть эффективнее, чем атака перебором.
На основе алгоритма шифрования можно построить и другие алгоритмы. Несколько их них изложены в настоящей статье.
Описание алгоритма
Шифрование
Введём обозначения. Пусть - длина шифруемого блока открытого текста . (start key) - выбирается по некоторому расписанию на основе ключа К. Побитово добавляется к исходному тексту: После этого происходит r-1 раундов, задаваемых следующими уравнениями, в которых (Round subKey)- раундовые подключи, # - побитовая конъюнкция или дизъюнкция , выбирается в соответствии с расписанием, , - известные константы, >>>j - циклический сдвиг вправо на j бит:
Последняя итерация отличается от основных только отсутствием перестановки после вычисления выражений в правых частях равенств:
Выход: зашифрованный блок
Расшифрование
По общей формуле для обращения произведения операторов строится и процедура расшифрования.
Выполняется одна итерация по расшифрованию:
( - длина , можно производить циклический сдвиг влево на )
После этого основной цикл расшифрования, состоящий из итераций, также несущественно отличающихся от предыдущей:
Комментарии
В некоторых источниках считают, что процедура шифрования состоит из в 4 раза меньшего числа раундов, состоящих из 4 итераций приведённого выше типа (без начального и конечного сложения по модулю 2). Так, сами авторы шифра записывали свой алгоритм следующим образом:
- Определяли функцию R - «итерацию»:
- Описывали начальное преобразование (сложение («+») с KS)
- Говорили, что раунд состоит из 4 итераций:
где - к итерационному ключу добавляется соответствующая константа
- Описывали конечное преобразование (сложение («+») с KF).
Алгоритмы аналогичны, поскольку операция «+» определена авторами отдельно от основного описания метода шифрования. Следует отметить, что расписание операций «+» можно изменить, выбирая обратимые бинарные операции над векторами длины . Нелинейная операция обычного сложения с игнорированием переполнения призвана усложнить линейный криптоанализ. А операция XOR помогают избежать дифференциального криптоанализа. В дальнейшем будет рассматриваться первое описание алгоритма, приведённое в статье китайских математиков, произведших линейный криптоанализ алгоритма.
Выбор операций «+» был произведён по итогам исследований распараллеливания вычислений на процессорах типа Pentium. Выбор изменения порядка регистров a, b, c, d от раунда к раунду ускоряет появление диффузии и конфузии. Базовые операции (XOR, сложение по модулю , OR, AND) и их порядок ускорили выполнение алгоритма, реализованного на языке С на большинстве платформ, а имплементация алгоритма на ассемблере достаточно короткая.
Простота реализации
Из приведённого описания видно, что для реализации алгоритма необходимо:
При этом отсутствуют таблицы подстановок, присутствующие, например, в ГОСТе, а раунд состоит из 6 операций. То, что сдвиг осуществляется на заранее известную величину, не зависящую ни от открытого текста, ни от ключа, существенно упрощает реализацию алгоритма на микросхемах. Простота алгоритма позволяет легко проверить, что в конкретной имплементации отсутствует так называемый «черный ход».
Параметры
Константы и
Длина N блока составляет 64 бита
Проводится 36 раундов
| i | i | i | i | ||||
|---|---|---|---|---|---|---|---|
| 0 | ac25 | 9 | 6a29 | 18 | 96da | 27 | d25e |
| 1 | 8a93 | 10 | 6d84 | 19 | 905f | 28 | a926 |
| 2 | 243d | 11 | 34bd | 20 | d631 | 29 | 1c7b |
| 3 | 262e | 12 | a267 | 21 | aa62 | 30 | 5f12 |
| 4 | f887 | 13 | cc15 | 22 | 4d15 | 31 | 4ecc |
| 5 | c4f2 | 14 | 04fe | 23 | 70cb | 32 | 3c86 |
| 6 | 8e36 | 15 | b94a | 24 | 7533 | 33 | 28db |
| 7 | 9fa1 | 16 | df24 | 25 | 45fc | 34 | fc01 |
| 8 | 7dc0 | 17 | 40ef | 26 | 5337 | 35 | 7cb1 |
| i | i | i | i | ||||
|---|---|---|---|---|---|---|---|
| 0 | 4 | 9 | 2 | 18 | 5 | 27 | 13 |
| 1 | 7 | 10 | 9 | 19 | 1 | 28 | 12 |
| 2 | 11 | 11 | 4 | 20 | 2 | 29 | 3 |
| 3 | 8 | 12 | 13 | 21 | 4 | 30 | 6 |
| 4 | 7 | 13 | 1 | 22 | 12 | 31 | 11 |
| 5 | 14 | 14 | 14 | 23 | 3 | 32 | 7 |
| 6 | 5 | 15 | 6 | 24 | 9 | 33 | 15 |
| 7 | 4 | 16 | 7 | 25 | 2 | 34 | 4 |
| 8 | 8 | 17 | 12 | 26 | 11 | 35 | 14 |
Длина блоков 128 бит
При длине блока 128 бит проводится 68 раундов. Поэтому задаются 68 32-битных констант и 68 констант .
Длина блока 256 бит
При длине блока 256 бит проводится 132 раундов. Поэтому задаются 132 64-битных константы и 132 константы .
Расписание ключей
Ключ представляется в виде конкатенации N/4-битных слов. KS и KF задаются произвольным образом, а в качестве раундовых ключей по очереди используются все
128-битный ключ
Блок в 64 бита
Ключ К делится на 8 слов
Блоки в 128 бит и 256 бит
Ключ К делится на 4 и 2 слова соответственно, поэтому раундовые ключи повторяются с периодом 4 или 2. В последнем случае среди KS и KF есть одинаковые.
192-битный ключ
В зависимости от длины блока ключ делится на 12, 6, и 3 n-битных частей, что определяет период повторения раундовых ключей.
256-битный ключ
Здесь ключ является объединением 16, 8 или 4 двоичных слов.
Расписание операции #
| I | # | i | # | i | # | i | # |
|---|---|---|---|---|---|---|---|
| 0 | AND | 16 | OR | 32 | OR | 48 | AND |
| 1 | OR | 17 | OR | 33 | OR | 49 | AND |
| 2 | AND | 18 | AND | 34 | AND | 50 | AND |
| 3 | OR | 19 | AND | 35 | OR | 51 | AND |
| 4 | OR | 20 | AND | 36 | OR | 52 | AND |
| 5 | OR | 21 | AND | 37 | AND | 53 | AND |
| 6 | OR | 22 | AND | 38 | OR | 54 | OR |
| 7 | OR | 23 | OR | 39 | AND | 55 | AND |
| 8 | AND | 24 | AND | 40 | OR | 56 | OR |
| 9 | OR | 25 | OR | 41 | AND | 57 | OR |
| 10 | OR | 26 | OR | 42 | AND | 58 | OR |
| 11 | AND | 27 | OR | 43 | OR | 59 | AND |
| 12 | OR | 28 | AND | 44 | OR | 60 | AND |
| 13 | AND | 29 | OR | 45 | AND | 61 | AND |
| 14 | OR | 30 | AND | 46 | AND | 62 | OR |
| 15 | OR | 31 | AND | 47 | AND | 63 | OR |
Для дальнейших итераций все повторяется:
Быстродействие
В алгоритме отсутствуют операции с битовою сложностью выше, чем , где - битовая длина модуля или операндов (например, у произведения по модулю, нахождения обратного (по умножению) элемента или наибольшего общего делителя битовая сложность , а у возведения в степень - ). Поэтому естественно ожидать высокой скорости работы алгоритма. Авторами приводятся следующие данные:
Безопасность
Главной причиной отсеивания алгоритма NUSH в конкурсе NESSIE стала найденная Ву Венлингом и Фенгом Денго уязвимость алгоритма к линейному криптоанализу.
В своей статье «Линейный криптоанализ блочного шифра NUSH» они используют понятие сложности атаки , где характеризует потребности в памяти, а - в объёме вычислений.
Для N=64 и N=128 бит предложено 3 вида атак, а для N=256 - два. Сложности соответствующих атак:
| Длина блока, бит | Длина ключа, бит | |
|---|---|---|
| 64 | 128 | |
| 192 | ||
| 256 | ||
| 128 | 128 | |
| 192 | ||
| 256 | ||
| 256 | 128 | |
| 192 | ||
| 256 |
Для некоторых случаев версия с 192-битным ключом существенно надежнее, чем с более длинным ключом. Также можно заметить, что для есть случаи, когда сложности атак шифра с самой маленькой длиной ключа и самой большой практически совпадают. Кроме того, увеличение длины ключа сказывается не так сильно на сложности атаки, как хотелось бы.
Таким образом, существуют атаки на шифр NUSH эффективнее полного перебора. Поэтому есть вероятность улучшения этих атак или достижения вычислительной техниой уровня, достаточного для взлома шифра в разумное время.
Криптоанализ алгоритма
В качестве примера рассмотрим вторую атаку на шифр с длиной блока N=64 бита. Криптоанализ основан на построении зависимостей между битами ключа, исходного и зашифрованного текста, справедливых с вероятностью, отличающейся от 1/2. Эти соотношения строятся на основе уравнения, справедливого с вероятностью 3/4
Это уравнение можно проверить, используя описание алгоритма, и учтя, что для последнего (младшего) разряда операции «+» и совпадают. Действительно, имеем соотношение . Добавив к обеим частя равенства соотношение получим требуемое.
Рассмотрев 4 первых раунда дешифрования, можно установить, что .
Используя Piling-up лемму, с вероятностью . Получили связь между битами ключа и открытым и зашифрованным текстами.
Из расписания ключей можно получить, что если длина ключа составляет 128 или 256 бит, то , если же ключ состоит из 192 бит, то . Из этих данных оцениваем временную сложность атаки, задаваемой следующим алгоритмом:
Сложность по объёму хранимой информации оценивается как . Именно стольким количеством пар открытый-шифрованный текст должен обладать криптоаналитик. При этом тексты отнюдь непроизвольные. Из приведенных соотношений видно, что зависят не от всех битов входного и выходного блоков. Соответственно, среди выборки блоков открытого и зашифрованных текстов должны быть блоки с отличающимися соответствующими битами. Работа алгоритма с меньшим числом известных текстов возможна, но тогда с меньшей вероятностью найденное «максимальное» число на втором этапе будет действительно соответствовать настоящему ключу в виду непревышения корня из дисперсии числа событий «уравнение выполняется» над мат. ожиданием разницы чисел этого события и ему противоположного (можно рассмотреть схему Бернулли, где вероятность «успеха» равна вероятности выполнения соотношения).
Другие предложенные в той же статье атаки отличаются анализом на последней стадии соотношений для других раундов и самостоятельного интереса не представляют.
Другие алгоритмы на основе NUSH
На основе NUSH можно построить другие алгоритмы. В частности:
- схемы аутентификации
Хэш-функция
Перед началом хэширования происходит удлинение текста:
- Добавить к тексту единичный бит
- Добавить столько нулей, чтобы получился текст с длиной, кратной N (эти два этапа можно не выполнять, если исходная длина текста уже кратна N)
- Приписать N-битовое представление начальной длины LEN (в битах) текста
- Приписать результат побитового XOR между всеми N-битовыми блоками полученного на предыдущем шаге текста
В функции используются следующие переменные:
Начальные значения: , , где - константы, которые прибавляются во время шифрования к ключу KR, KS=KF=KR=0
For i = 0 to l-1
For j=0 to L/2-1 //L - число раундов для соответствующего вида NUSH { } H = NUSH(V) //Операция шифрования For j=15 to 4 For j=15 to 4
For j=0 to L/2-1 H = NUSH() For j=15 to 4
Значение хэш-функции длиной t*n (t<16) бит - первые t n-битовых слов регистра T
Код аутентичности сообщения
На основе хэш-функции может быть построена процедура аутентификации сообщения. От предыдущего алгоритма отличается только использованием ненулевого ключа.
Синхронный поточный шифр «NUSH Stream»
Пусть SYNC - известный двоичный вектор длины LENGTH. Есть два варианта этого шифра.
Вариант 1
Пусть N = LENGTH - длина блока, используемого при шифровании алгоритмом NUSH (LENGTH = 64, 128, 256) Пусть - вектор из COUNT N-битовых слов, который будет складываться с исходным текстом и с шифротекстом для шифрования и расшифрования соответственно.
For i =0 to COUNT −1
SYNC = (SYNC + 65257) modВариант 2
Здесь N=LENGTH / 2, где соответственно LENGTH = 128, 256, 512. Пусть - вектор длины N, SYNC= - вектор длины 2N T - временный регистр длины N=4n, , , , - соответствующие константы алгоритма NUSH.
Производимые вычисления:
SYNC = SYNC ^ NUSH(SYNC)
SYNC = SYNC ^ NUSH(SYNC) T=SYNC
For i =0 to COUNT −1
T = (T + 127) modАсимметричное шифрование
Выбор параметров
Вводится специфическая группа G c определенной авторами алгоритма операцией на основе умножения Монтгомери (Montgomery multiplication).
Почему RSA Security рекомендует использовать ключи длиной 1024 бита, 2048 бит и даже 3072 бит, в то время как большинство алгоритмов симметричного шифрования ограничиваются длиной от 112 до 256 бит. Мол, почему бы нам не увеличить длину ключей, например, до миллиона - чтобы защититься от потенциального брутфорса со стороны суперкомпьютеров, которые ещё не изобретены.
Несмотря на свою банальность, вопрос набрал достаточно много баллов, то есть у многих ещё нет чёткого понимания, чем отличается ассиметричный шифр криптографический алгоритм с открытым ключом от симметричного шифра, где для шифрования и расшифрования используется один и тот же ключ.
С точки зрения брутфорса, принципиальная разница в том, что для взлома ключа RSA нужно найти сомножитель определённой длины (причём можно использовать предвычисленные таблицы). Это математическая задача, которую нельзя сильно усложнять, иначе обычная расшифровка сообщения будет занимать слишком много времени. На диаграмме показана скорость расшифровки на 2-гигагерцовом процессоре Pentium.
Для взлома симметричного шифра требуется перебрать 2^N комбинаций, где N - длина ключа. Расшифровка сообщения в любом случае происходит мгновенно, имея симметричный ключ. По оценке NIST , 256-битный симметричный ключ примерно соответствует 15360-битному ключу RSA. Лучше всего этот пример описан в книге «Прикладная криптография» Брюса Шнайера, которую можно процитировать.
Одним из следствий закона второго термодинамики является то, что для представления информации необходимо некоторое количество энергии. Запись одиночного бита, изменяющая состояние системы, требует количества энергии не меньше чем kT; где Т - абсолютная температура системы и k - постоянная Больцмана. (Не волнуйтесь, урок физики уже почти закончен.)
Приняв, что k = 1,38*10 -16 эрг/K, и что температура окружающей вселенной 3,2K, идеальный компьютер, работая при 3,2K, потреблял бы 4,4*10 -16 эрга всякий раз, когда он устанавливает или сбрасывает бит. Работа компьютера при температуре более низкой, чем температура космического пространства, потребовала бы дополнительных расходов энергии для отвода тепла.
Далее, энергия, излучаемая нашим Солнцем за год, составляет около 1,21*10 41 эргов. Это достаточно для выполнения 2*10 56 перемен бита в нашем идеальном компьютере, а этого, в свою очередь, хватит для того, что бы 187-битовый счетчик пробежал все свои значения. Если мы построим вокруг Солнца сферу Дайсона и перехватим без всяких потерь всю его энергию за 32 года, мы сможем получить компьютер для вычисления 2 192 чисел. Конечно, энергии для проведения каких-нибудь полезных вычислений с этим счетчиком уже не останется.
Но это только одна жалкая звезда. При взрыве типичной сверхновой выделяется около 10 51 эргов. (В сто раз больше энергии выделяется в виде нейтрино, но пусть они пока летают). Если всю эту энергию удастся бросить на одну вычислительную оргию, то все свои значения сможет принять 219-битовый счетчик.
Эти числа не имеют ничего общего с самой аппаратурой, они просто показывают максимальные значения, обусловленные термодинамикой. Кроме того, эти числа наглядно демонстрируют, что вскрытие грубой силой 256-битового ключа будет невозможно, пока компьютеры построены из обычной материи и располагаются в обычном пространстве.
Отличительные особенности:
- 256 бит перезаписываемой энергонезависимой памяти
- EEPROM организована как одна 256 байтная страница
- 64 бит одноразово программируемой памяти, которая автоматически защищается от записи после программирования
- Контроль, адресация и питание по одному проводу
- 8 битный идентификационный код семейства DS1971 для идентификации ридером
- Диапазон напряжения питания от 2,8 В до 6,0 В во всем температурном диапазоне от -40°C до +85°C
Функциональная схема:
Описание iButton:
256 битная EEPROM DS1971 семейства iButton является мощным перезаписываемым носителем информации, который предназначен для идентификации и хранении информации об изделии или владельце. Доступ к этой информации может быть осуществлен с минимальными аппаратурными затратами при помощи всего одного вывода микроконтроллера. DS1971 имеет регистрационный номер, запрограммированный лазером в процессе производства, состоящий из 48 битного уникального заводского номера, 8 битов CRC, и 8 битного кода семейства (14H) плюс 256 битную EEPROM. Питание при программировании и считывании прибора DS1971 поступает по одной линии связи 1-Wire. Данные передаются по последовательному протоколу 1-Wire, который требует только одной линии вывода данных и общего вывода. 48 битный серийный номер, содержащийся в памяти с лазерным программированием, обеспечивает полную идентификацию прибора. Прочный MicroCan корпус имеет высокую устойчивость к воздействию внешних неблагоприятных факторов, таких как загрязнение, влажность и вибрация. Его компактная форма в виде монеты, обеспечивает самовыравнивание в ответном контактном разъеме, что обеспечивает простоту использования человеком - оператором или автоматом. Аксессуары DS1971 позволяют закрепить его практически на любой поверхности, включая печатные платы, фото- идентификационные брелки и брелки для ключей. Приборы могут применяться для контроля за передвижением грузового транспорта и путешественников, управления доступом и хранения градуировочных констант.
Описание:
Блок-схема показывает распределение функций между управляющим блоком и секцией памяти DS1971. DS1971 имеет четыре главных модуля данных: 1) 64 битное ПЗУ с лазерным программированием, 2) 256 битную EEPROM с буферным блокнотом, 3) 64 битную однократно программируемую память с буферным блокнотом и 4) 8 битную память состояния. Для доступа к памяти устройство управления шиной должно сначала выполнить одну из команд управления памятью. Все данные считываются и записываются начиная с младшего значащего бита.
Для измерения длины есть такие единицы, как миллиметр, сантиметр, метр, километр. Известно, что масса измеряется в граммах, килограммах, центнерах и тоннах. Бег времени выражается в секундах, минутах, часах, днях, месяцах, годах, веках. Компьютер работает с информацией и для измерения ее объема также имеются соответствующие единицы измерения.
Мы уже знаем, что компьютер воспринимает всю информацию .
Бит – это минимальная единица измерения информации, соответствующая одной двоичной цифре («0» или «1»).
Байт состоит из восьми бит. Используя один байт, можно закодировать один символ из 256 возможных (256 = 2 8). Таким образом, один байт равен одному символу, то есть 8 битам:
1 символ = 8 битам = 1 байту.
Буква, цифра, знак препинания – это символы. Одна буква – один символ. Одна цифра – тоже один символ. Один знак препинания (либо точка, либо запятая, либо вопросительный знак и т.п.) – снова один символ. Один пробел также является одним символом.
Изучение компьютерной грамотности предполагает рассмотрение и других, более крупных единиц измерения информации.
Таблица байтов:
1 байт = 8 бит
1 Кб (1 Килобайт
) = 2 10 байт = 2*2*2*2*2*2*2*2*2*2 байт =
= 1024 байт (примерно 1 тысяча байт – 10 3 байт)
1 Мб (1 Мегабайт ) = 2 20 байт = 1024 килобайт (примерно 1 миллион байт – 10 6 байт)
1 Гб (1 Гигабайт ) = 2 30 байт = 1024 мегабайт (примерно 1 миллиард байт – 10 9 байт)
1 Тб (1 Терабайт ) = 2 40 байт = 1024 гигабайт (примерно 10 12 байт). Терабайт иногда называют тонна .
1 Пб (1 Петабайт ) = 2 50 байт = 1024 терабайт (примерно 10 15 байт).
1 Эксабайт = 2 60 байт = 1024 петабайт (примерно 10 18 байт).
1 Зеттабайт = 2 70 байт = 1024 эксабайт (примерно 10 21 байт).
1 Йоттабайт = 2 80 байт = 1024 зеттабайт (примерно 10 24 байт).
В приведенной выше таблице степени двойки (2 10 , 2 20 , 2 30 и т.д.) являются точными значениями килобайт, мегабайт, гигабайт. А вот степени числа 10 (точнее, 10 3 , 10 6 , 10 9 и т.п.) будут уже приблизительными значениями, округленными в сторону уменьшения. Таким образом, 2 10 = 1024 байта представляет точное значение килобайта, а 10 3 = 1000 байт является приблизительным значением килобайта.
Такое приближение (или округление) вполне допустимо и является общепринятым.
Ниже приводится таблица байтов с английскими сокращениями (в левой колонке):
1 Kb ~ 10 3 b = 10*10*10 b= 1000 b – килобайт
1 Mb ~ 10 6 b = 10*10*10*10*10*10 b = 1 000 000 b – мегабайт
1 Gb ~ 10 9 b – гигабайт
1 Tb ~ 10 12 b – терабайт
1 Pb ~ 10 15 b – петабайт
1 Eb ~ 10 18 b – эксабайт
1 Zb ~ 10 21 b – зеттабайт
1 Yb ~ 10 24 b – йоттабайт
Выше в правой колонке приведены так называемые «десятичные приставки», которые используются не только с байтами, но и в других областях человеческой деятельности. Например, приставка «кило» в слове «килобайт» означает тысячу байт, также как в случае с километром она соответствует тысяче метров, а в примере с килограммом она равна тысяче грамм.
Продолжение следует…
Возникает вопрос: есть ли продолжение у таблицы байтов? В математике есть понятие бесконечности, которое обозначается как перевернутая восьмерка: ∞.
Понятно, что в таблице байтов можно и дальше добавлять нули, а точнее, степени к числу 10 таким образом: 10 27 , 10 30 , 10 33 и так до бесконечности. Но зачем это надо? В принципе, пока хватает терабайт и петабайт. В будущем, возможно, уже мало будет и йоттабайта.
Напоследок парочка примеров по устройствам, на которые можно записать терабайты и гигабайты информации.
Есть удобный «терабайтник» – внешний жесткий диск, который подключается через порт USB к компьютеру. На него можно записать терабайт информации. Особенно удобно для ноутбуков (где смена жесткого диска бывает проблематична) и для резервного копирования информации. Лучше заранее делать резервные копии информации, а не после того, как все пропало.
Флешки бывают 1 Гб, 2 Гб, 4 Гб, 8 Гб, 16 Гб, 32 Гб, 64 Гб и даже 1 терабайт.
