Описание и исходный текст алгоритма криптографической подписи CSA-2

Трунов Д.Н.

ОПИСАНИЕ И ИСХОДНЫЙ ТЕКСТ АЛГОРИТМА КРИПТОГРАФИЧЕСКОЙ ПОДПИСИ CSA-2

Копия статьи, опубликованной 22.12.2017 на сайте https://sites.google.com/site/publicworkstrunov

Введение

Алгоритм CSA-2 (CryptoSignature Algorithm #2) представляет собой разновидность хеш-функции [1], предназначенную для создания криптографических подписей. Под криптографической подписью здесь подразумевается вычисленный для электронного документа (файла или массива данных) отпечаток (контрольный код, хеш-код), который предполагается заверять обычной (собственноручной) подписью, что будет равнозначно подписанию самого документа.

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

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

Суть хеш-функции

Хеш-функция представляет собой функцию вида [3, 4]:

h = H(M),

где M – сообщение произвольной длины, h – результат фиксированной длины m.

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

 1) зная M, легко вычислить h;

 2) зная h, трудно определить M, для которого H(M) = h;

 3) зная M, трудно определить другой сообщение M’, для которого H(M) = H(M’);

 4) должно быть трудно найти два случайных сообщения M и M’, для которых H(M) = H(M’).

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

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

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

h1 = H(M),

h2 = H(M + h1),

h3 = H(M + h2),

...

hn = H(M + hn-1).

Такой подход удобен для хеширования коротких сообщений во избежание вскрытия прообраза путём перебора возможных его вариантов. Например, для хеширования паролей в системах аутентификации [5]. Однако такой способ не очень удобен для вычисления хеш-кода документа достаточно большого размера. В этом случае может понадобиться другой алгоритм, изначально включающий в себя увеличенное количество циклов вычисления.

Алгоритм CSA-1

Идея выполнения хеш-функцией большого числа циклов вычисления была реализована в алгоритме CSA-1, рассмотренном в работе [6]. Фактически алгоритм разделялся на четыре отдельных алгоритма с циклами вычисления от 10 до 10000 (число после точки): CSA-1.10, CSA-1.100, CSA-1.1000 и CSA-1.10000 (прежние обозначения: CSA-10, CSA-100, CSA-1000 и CSA-10000). Кроме того, в алгоритме CSA-1 можно было также выбирать и длину вычисляемого кода, которая варьировалась от 10 до 80 символов.

В отличие от многих других алгоритмов, представляющих хеш-код в виде шестнадцатеричных чисел, здесь код представлялся обычными символами латинского алфавита, цифрами и знаками, которые есть на клавиатуре с английской раскладкой: символы 0x21..0x7E таблицы ASCII (всего 94 символа). Это позволяло уменьшить длину хеш-кода (без потери информативности) и корректно его отображать даже в простом текстовом видеорежиме. Поскольку наиболее распространен текстовый видеорежим с шириной экрана 80 символов [7], длина кода CSA-1 также ограничена 80 символами, хотя стандартная длина взята равной его половине – 40 символов.

Учитывая, что одним алгоритмом можно было вычислять несколько кодов (с разным количеством циклов), типичная криптографическая подпись могла выглядеть, например, так:

CSA-1.100:  #~jeQ;ng84/|k:Q?RRW)s2QLD&-(Tc~1ul~r13,k

CSA-1.1000: \aJ&.Cq;}t@+R/'ZuxCE)l&x<u.x,~EeDi&n]2H-

Реализация алгоритма CSA-2

Несмотря на повышенное количество циклов вычисления, алгоритм CSA-1 оказался недостаточно надёжным, поскольку в своей реализации имел множество слабых мест. Для решения этой проблемы была разработана новая версия алгоритма – CSA-2. Эта версия внешне очень похожа на своего предшественника, поскольку точно так же предполагает циклы вычисления от 10 до 10000 и выдаёт результат в виде строки, состоящей из такого же набора символов. Правда, длина в этот раз задана равной строго 40 символам без возможности её изменения. Внутренне же CSA-2 имеет совершенно другую реализацию.

При разработке алгоритма шифрования ESCK-5, рассмотренного в работе [8], была обнаружена возможность его применения не только для шифрования, но и для вычисления хеш-функций. Было решено положить в основу CSA-2 алгоритм шифрования ESCK-5, внеся в него некоторые изменения, позволяющие из двусторонней функции (шифрование и расшифровка) сделать одностороннюю (хеширование).

Исходный текст алгоритма CSA-2 на языке программирования Delphi/Object Pascal приведён в приложении 1. Поскольку CSA-2 является лишь изменённой версией алгоритма ESCK-5, рассмотренного отдельно, нет смысла слишком подробно вдаваться в подробности его реализации, поэтому остановимся только на рассмотрении некоторых основных принципов и отличительных особенностей.

Принципы работы

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

Как и в ESCK-5, для работы применяются два массива M и K, состоящие из 256 элементов типа Cardinal (целые 32-разрядные числа без знака) каждый. Это рабочий массив и массив ключа шифрования соответственно. В начало массива M вписывается размер Size вычисляемого массива, остальные элементы массива заполняются нулями. Массив ключа K инициализируется при помощи функции Gen начальной генерации ключа. После этого производится шифрование вычисляемого массива с помощью функции EncryptMass, а конечный результат преобразуется с помощью функции GetSign непосредственно в символьную строку.

При шифровании массива функцией EncryptMass он разбивается на блоки размером по 1024 байта каждый. Если вычисляемый размер не кратен 1024, то в последнем блоке будут свободные байты. Они заполняются нулями и также участвуют в шифровании. Все байты блока объединяются группами по 4, формируя 32-разрядные целые числа типа Cardinal. Первыми идут младшие байты, последними – старшие. Эти 32-разрядные числа добавляются к массивам M и K, причём для добавления к M применяется операция «+» (сложение), а для K – операция XOR (исключающее ИЛИ). После этого массив ключа K дополнительно зашифровывается функцией GFunc количеством раз, равным установленному количеству циклов. Таким же количеством раз производится шифрование функцией Enc массива M при помощи ключа K. Потом таким же образом добавляется и обрабатывается следующий блок и так до конца массива.

После шифрования функцией EncryptMass конечный результат располагается в массиве M. Его можно вернуть в качестве полной криптографической подписи с помощью процедуры FullSignature. Однако обычно подпись преобразуется в символьную строку с помощью функции GetSign. Эта функция сжимает массив M до 10 чисел типа Cardinal, затем каждое это число записывает 4 символами, выполнив 4 раза деление числа на 94. Остаток деления формирует код символа, а результат участвует в следующем делении. Остаток может присутствовать и после четвёртого деления, но он уже не учитывается в подписи.

Функция шифрования Enc предполагает для каждого элемента рабочего массива M[I] вычисление нового значения на основе самого M[I], а также других четырёх элементов: M[A1], M[A2], M[A3] и M[A4]. Адреса A1..A4 вычисляются на основе элементов M[I], K[I] и K[I+1] (или K[0], если I=255). Все четыре элемента собираются парами в разных комбинациях, и к каждой паре применяется своя функция, включающая элементарные битовые операции, такие как AND (И), OR (ИЛИ), XOR (исключающее ИЛИ) и NOT (отрицание). Все вычисления в парах накапливаются в конечном результате с помощью операций XOR, ROL (циклический сдвиг влево) и ROR (циклический сдвиг вправо).

Применение элементарных операций призвано снизить вероятность нахождения более простого и быстрого способа вычисления функции. Операция XOR позволяет сохранить одинаковую вероятность значения 1 или 0 в битах результата. Операции ROL и ROR призваны переносить влияние отдельных битов аргумента на другие биты результата. Сама функция Enc практически полностью идентична таковой в алгоритме ESCK-5. Разница лишь в том, что в ESCK-5 допускалась работа с неполным блоком и предполагалась обратимость вычислений (расшифровка). В CSA-2 все блоки полные, а необратимость вычислений является необходимостью, потому на вычисляемый элемент обязательно влияет он сам.

Функция GFunc предназначена для самозашифровки массива ключа K в процессе генерации ключа или шифрования массива. Является односторонней функцией и по принципу действия сходна с функцией шифрования Enc, только вместо шифруемого массива M применяется сам ключ K. Функция полностью идентична таковой в алгоритме ESCK-5.

Генерация ключа шифрования. Парольный хеш

Генерация начального значения ключа шифрования K производится при помощи функции Gen. В отличие от ESCK-5, в CSA-2 по умолчанию пароль не используется. Поэтому функция Gen лишь устанавливает циклы шифрования для дальнейших вычислений и производит начальную инициализацию массива K. Однако пароль можно установить с помощью процедуры SetPassword. Тогда при генерации ключа после начальной инициализации массива K символы пароля будут загружаться в массив, а сам массив – зашифровываться при помощи функции GFunc. Пароль устанавливается только для одной генерации и потом сбрасывается (до следующей его установки с помощью процедуры SetPassword).

Вычисление криптографической подписи (хеш-функции) с паролем может преследовать несколько возможных целей. Если это секретный пароль, то такую функцию можно использовать, например, как аналог электронной цифровой подписи. Но для этого потребуется доверенная третья сторона. Предположим, сторона А посылает стороне Б электронный документ с подписью в виде хеш-кода, вычисленного для этого документа с учётом секретного пароля П. Этот пароль известен только стороне А и стороне В, которой доверяют и А, и Б. Сторона Б, чтобы проверить подпись, посылает тот же документ стороне В. Та вычисляет хеш-код с помощью пароля П стороны А и возвращает этот код стороне Б. Сторона Б сравнивает коды, полученные от стороны А и стороны В и, если они совпадают, считает подпись действительной.

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

CSA-2.10:          roX4^G}^r:4PUh0AgMfhDz$/hvXfX$."8[g~zE51

CSA-2.100:         F7#f!6%S1qM[d.~mYENeR01!;HP)@'%l*r"!)+"Z

CSA-2.100("0000"): %FgNm.u\pyc%Ypf/r7&|N6:tF,Bco1{y>:-R,mPi

Как видно, третий код вычислен с паролем, состоящим из четырёх нулей (указаны в скобках и двойных кавычках вместе с обозначением алгоритма). Такие составные коды намного более устойчивы к коллизиям и больше подходят для создания подписей большого срока действия.

Другие функции алгоритма

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

Следует учесть, что по умолчанию алгоритм работает со строками в кодировке Ansi (тип AnsiString), где каждый символ имеет размер 1 байт. В то же время, более распространённой кодировкой является Unicode [9], в которой каждый символ имеет размер 2 байта (тип WideString). Символы результата вычисления подписи выглядят одинаково в обеих кодировках, а кодировка легко меняется с одной на другую. Однако кодировка подписываемой строки имеет принципиальное значение.

Преобразование WideString в AnsiString перед вычислением может привести к потере данных, что недопустимо. Поэтому для вычисления подписи строки в кодировке Ansi предназначена функция SignStringA, а для WideString – функция SignStringW. Во втором случае результат вычисления будет также типа WideString. Такая же ситуация и с вычислением подписей файлов: если имя файла задано в строке типа AnsiString, применяется функция SignFileA, если WideString – функция SignFileW. В целом, при необходимости алгоритм достаточно легко полностью перевести на кодировку Unicode.

Особенности вычисления

Несмотря на то, что алгоритм позволяет вычислять хеш-функции с практически любым количеством циклов шифрования, заданным 32-разрядным целым числом, для создания криптографических подписей предполагается применять только 4 основных значения циклов шифрования: 10, 100, 1000 и 10000. Как и в случае с CSA-1, алгоритм тогда будет иметь 4 варианта маркировки: CSA-2.10, CSA-2.100, CSA-2.1000 и CSA-2.10000. В отдельных случаях возможно применение другого количества циклов шифрования.

Если функция вычисляется с открытым паролем, его нужно указать вместе с алгоритмом, например, так: CSA-2.10(“ABCD”). Секретный пароль, разумеется, указывать не следует, однако может быть полезным указать факт вычисления функции с паролем. Например, так: CSA-2.10P.

Заключение

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

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

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

Источники информации

1. Википедия. Криптографическая хеш-функция [Электронный ресурс] URL: https://ru.wikipedia.org/wiki/Криптографическая_хеш-функция

2. Википедия. Электронная подпись [Электронный ресурс] URL: https://ru.wikipedia.org/wiki/Электронная_подпись

3. Баричев С. Криптография без секретов [Электронный ресурс] // Бюро научно-технической информации. – URL: http://www.bnti.ru/dbtexts/ipks/old/analmat/1_2002/crypto4.pdf

4. Шнайер Брюс. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. – М.: Триумф, 2002. – 816 с.

5. Википедия. Аутентификация [Электронный ресурс] URL: https://ru.wikipedia.org/wiki/Аутентификация

6. Трунов Д.Н. Особенности и характеристики алгоритмов вычисления криптоподписей CSA-10, CSA-100, CSA-1000 и CSA-10000 [Электронный ресурс] – URL: https://sites.google.com/site/publicworkstrunov

7. Википедия. Текстовый видеорежим [Электронный ресурс] URL: https://ru.wikipedia.org/wiki/Текстовый_видеорежим

8. Трунов Д.Н. Алгоритм шифрования ESCK-5: описание, принцип работы, исходные тексты [Электронный ресурс] – URL: https://sites.google.com/site/publicworkstrunov

9. Википедия. Юникод [Электронный ресурс] URL: https://ru.wikipedia.org/wiki/Юникод

Приложение 1. Исходный текст алгоритма CSA-2 на языке программирования Delphi/Object Pascal

Текст приложения приведён в оригинальном файле.

Оригинальный файл: Открыть