Особенности и характеристики алгоритмов вычисления криптоподписей CSA-10, CSA-100, CSA-1000 и CSA-10000

Трунов Д.Н.

ОСОБЕННОСТИ И ХАРАКТЕРИСТИКИ АЛГОРИТМОВ ВЫЧИСЛЕНИЯ КРИПТОПОДПИСЕЙ CSA-10, CSA-100, CSA-1000 И CSA-10000

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

Введение

Продолжая работу над темой применения цифровых подписей файлов, начатую в работах [1, 2], возникла необходимость в существенном пересмотре принципов функционирования ранее созданного алгоритма AFS-1 [2], который в некоторых случаях оказался довольно неудобным. Во-первых, алгоритм AFS-1 вычислял цифровую подпись в виде ряда цифр заданной длины, применяя шифрование с многократно повторяющимися циклами. Притом, что и количество циклов, и длину подписи пользователю нужно было выбирать самостоятельно, с чем могут возникать сложности. Требовалось существенно ограничить разброс вариантов и оставить всего три-четыре «стандартных» варианта.

Во-вторых, важным недостатком AFS-1 были его высокие требования к вычислительному оборудованию. Например, основной рабочий массив имел размер 256 Мбайт, что является посильным для многих современных компьютеров и иных портативных вычислительных устройств, однако не для всех. Требовалось значительно сократить объём используемой для вычислений оперативной памяти.

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

Предполагалось создать новую модификацию алгоритма – AFS-2, однако, требуемые изменения были столь существенными, что создание новой модификации оказалось бессмысленным. Взамен было решено создать новый, более качественный и удобный алгоритм CSA – CryptoSignature Algorithm (алгоритм криптоподписи). О нём, его особенностях и отличиях от своего предшественника AFS-1 здесь и пойдёт речь.

Принципы применения цифровых подписей

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

Было установлено, что существующие решения по вычислению и проверке цифровых подписей основаны на вычислении так называемых Хэш-функций [3], а также алгоритмах шифрования с открытым ключом [3 – 5]. Хэш-функция обеспечивает вычисление по определённому алгоритму числовой последовательности небольшой длины для заданного файла, текста или иного массива данных. Особенность этой функции в том, что результат её вычисления всегда одинаков для одного и того же файла (массива данных), но кардинально отличается от результатов вычисления для других файлов (массивов). Даже если другой файл является легко модифицированным, вычисленная для него Хэш-функция будет разительно отличаться от таковой для оригинального файла.

Что касается шифрования с открытым ключом, оно обеспечивает проверку подлинности по следующей схеме. С помощью соответствующих программных средств автор электронного документа создаёт два связанных между собой ключа шифрования – открытый и закрытый. Открытый ключ он сообщает получателям или регистрирует его под своим именем, либо публикует. Закрытый же ключ хранит в секрете. Связь этих ключей такова, что зашифрованное с помощью закрытого ключа сообщение может быть расшифровано только открытым ключом (или наоборот), но определить закрытый ключ, зная открытый, очень сложно или практически невозможно.

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

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

В работах [1, 2] было предложено в отдельных случаях отказаться от применения шифрования с открытым ключом и остановиться только на Хэш-функциях. Например, вместо многостраничного документа (инженерного проекта, реферата, курсовой работы и т.п.) подписывать только вычисленную и распечатанную на бумажном носителе Хэш-функцию этого документа. Обычной подписью, на обычной бумаге. Получается некий симбиоз – документ электронный, подпись обычная. Однако принципы проверки те же: проверяющее лицо повторно вычисляет Хэш-функцию и сравнивает с той, которая подписана на бумаге. В случае их совпадения, документ является подлинным.

Более того, возможен вариант и отказа от подписей на бумаге. В работе [6] рассматривалась возможность применения для этого специальных депозитариев цифровых подписей. Вычисленная для электронного документа Хэш-функция в качестве цифровой подписи может быть размещена в таком депозитарии под именем автора документа. А уже на депозитарий возлагаются функции хранения подписей, защиты от несанкционированных изменений, проверки личности автора на этапе добавления новой подписи. Подобную функцию, кстати, уже выполняют некоторые социальные сети. К примеру, в социальной сети Linked in (www.linkedin.com) добавление любой записи на странице производится только от имени автора записи, а возможность её модификации исчезает через несколько минут после создания последней.

Свойства и характеристики алгоритмов CSA

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

Задача №2 – сокращение объёма используемой оперативной памяти компьютера. В качестве ориентира был принят до сих пор применяющийся в учебных целях язык программирования фирмы Borland Turbo Pascal v. 7.0. Условие таково: если алгоритм может быть реализован в Turbo Pascal, он может быть реализован везде. Алгоритм AFS-1 не мог быть реализован в Turbo Pascal из-за невозможности оперировать массивами данных объёмом 256 Мбайт, поэтому новый алгоритм изначально был написан в Turbo Pascal (см. Приложение 1).

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

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

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

Порядок работы алгоритма следующий.

1. Создаются два массива по 4096 байта (4 Кбайта) каждый – рабочий массив и массив ключа. Рабочий массив заполняется заранее определѐнными числами по схеме: в нулевую ячейку пишется 0, в первую – 1, во вторую – 2 и т.д. Поскольку каждая ячейка имеет объём 1 байт, туда можно помещать числа до 255. Значит, в 256-ю пишется 0, в 257-ю – 1 и т.д. до последней ячейки рабочего массива.

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

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

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

5. По завершении криптоподпись извлекается из рабочего массива, многократно зашифрованного в процессе вычисления. Каждый байт этого массива может иметь любое значение от 0 до 255 (или от 00 до FF в шестнадцатеричной системе счисления). Однако в подпись войдут только те из них, для которых в таблице 1 имеется символьный эквивалент. Причём в строгом соответствии с этим эквивалентом. Например, байт со значением 23 будет записан в подпись в виде символа #, а 5A – в виде буквы Z. Количество символов подписи ограничено заранее установленной её длиной.

Таблица 1 –

Допустимые значения элементов подписи и их символьный эквивалент

Все элементы рабочего массива, не имеющие в таблице 1 символьного эквивалента, не войдут в подпись. Это связано с тем, что все приведённые в таблице символы являются наиболее универсальными и содержатся практически в любой кодировке, в любом шрифте (все эти символы находятся на клавиатуре с английской раскладкой). Все прочие числовые значения также могут иметь свой символьный эквивалент, но их отображение может или отсутствовать в отдельных шрифтах или кодировках, или существенно отличаться от других. Поэтому было решено ограничиться значениями от 21 до 7E (94 символа: латиница большого и малого регистров, цифры, специальные символы). Пробел с кодом 20 не входит в этот диапазон.

В алгоритме по умолчанию принята длина подписи 40 символов (если во входных параметрах указать нулевое значение), однако допускается указать и иную длину. Рекомендуется применять одну из следующих длин: 10, 20, 40, 80. Количество циклов шифрования определяется параметром «Режим». Применяется всего 4 режима: 

  Режим 0: 10 циклов;
  Режим 1: 100 циклов;
  Режим 2: 1000 циклов;
  Режим 3: 10000 циклов.

В зависимости от выбранного режима (соответственно и циклов шифрования), определяется и тип алгоритма: CSA-10, CSA-100, CSA-1000 или CSA-10000. Число, указанное после аббревиатуры, как раз и определяет количество циклов. Длину подписи, если она стандартная и равна 40 символам, указывать не обязательно. Если же длина имеет иное значение, рекомендуется указывать её рядом с наименованием алгоритма в скобках.

Примеры вычисленных криптоподписей для одного и того же файла:
  CSA-100:      (:H{=,%pP!.d4ykw7j1-yC_)io5^w"0v@8+b,old
  CSA-10:       _45@PV:uW&\<N<.`zuMy}^#tQf$J0k2~MK;fW<hx
  CSA-10[10]: _45@PV:uW&

Важно отметить, что, в отличие от алгоритма AFS-1, где устанавливаемая длина цифровой подписи влияла на режим шифрования и сама подпись существенно менялась, если менялась её длина, здесь длина на режим шифрования не влияет. Какая бы длина ни была принята, если режим не меняется, алгоритм CSA вычисляет всегда одну и ту же символьную последовательность в качестве криптоподписи. Длина лишь устанавливает, сколько символов из этой последовательности будет возвращено в виде конечного результата.

Надёжность криптоподписей

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

Подделать подписанный электронный документ практически невозможно, поскольку поддельный документ будет иметь другую криптоподпись. Единственный способ –предусмотреть в поддельном документе специальное место, в которое нужно вносить каждый раз новые изменения. Дело в том, что если в любом месте документа даже один символ поменять на другой, например, А на Б, то полностью изменится его подпись. Если Б поменять на В - изменится ещё раз. Через определённое количество неповторяющихся изменений есть вероятность получить такую подпись, которая нужна.

Для исключения возможности создания такой подделки необходимо, чтобы:

а) криптоподпись имела как можно больше возможных вариантов (от количества вариантов криптоподписи зависит количество вариантов изменений в поддельном документе);

б) на вычисление криптоподписи тратилось достаточно ощутимое количество времени.

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

Для оценки параметров безопасности в таблице 2 приведены значения количества возможных вариантов криптоподписей в зависимости от выбранной длины. Поскольку каждый символ подписи может иметь одно из 94 значений, подпись из одного символа может иметь возможных варианта. Подпись из двух символов может иметь 94^2 = 8836 различных вариантов. Из трёх, соответственно, 94^3 = 830584 варианта. Время же вычисления зависит от размера файла и количества циклов шифрования.

Таблица 2 –

Количество вариантов криптоподписи в зависимости от её длины

В качестве примера произведём следующий расчёт. Допустим, вычисление криптоподписи по алгоритму CSA-10 для некоторого файла происходит за 0,1 секунды. Если принять длину подписи равной 10 символам, для полного перебора всех возможных изменений в поддельном файле для получения нужной подписи понадобится 0,1∙5,4∙10^19 секунд, или 1,7∙10^11 лет. Даже с перспективой дальнейшего повышения вычислительных возможностей, объединения компьютеров в сети и привлечения суперкомпьютеров, нет никаких оснований считать возможной подделку подписанных электронных документов.

Исходные тексты алгоритма

Самая простая реализация всех четырёх алгоритмов CSA-10, CSA-100, CSA-1000 и CSA-10000 была создана в виде программы CryptoSignature в среде разработки Turbo Pascal версии 7.0. Программа может работать под управлением операционной системы MS-DOS, а также систем Windows, поддерживающих режим MS-DOS. В своей работе CryptoSignature требует ввести имя файла, для которого вычисляется криптоподпись, режим вычисления (0…3), как указывалось выше, и длину подписи (0 – установить длину по умолчанию). После расчётов выводит на экран вычисленную подпись заданной длины.

Исходные тексты этой программы приведены в приложении 1.

Заключение

В отличие от алгоритма AFS-1, любой из алгоритмов CSA готов к использованию и не требует выбора параметров. Во всех случаях предлагается применять алгоритм CSA-10, для достаточно малых файлов - CSA-100, а модификации CSA-1000 и CSA-10000 нужны только для случаев, требующих повышенной сложности вычисления. Стандартной длины криптоподписи 40 символов достаточно для всех случаев. Если ограничено место для записи подписей, длины 20 и даже 10 символов достаточно для обеспечения надёжности подписи.

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

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

1. Трунов Д.Н. Принципы практического применения цифровых подписей // Проблеми гірничої технології: матеріали регіональної науково-практичної конференції, Красноармійський індустріальний інститут ДонНТУ, 30 листопада 2012 р. – Донецьк: Цифрова типографія, 2012. – С. 377 – 385.

2. Трунов Д.Н. Алгоритм вычисления сигнатуры файла, его особенности и область применения // Сучасні аспекти механізації та автоматизації енергоємних виробництв. Збірник матеріалів II регіональної науково-практичної конференції, Красноармійський індустріальний інститут ДВНЗ ДонНТУ, 25 квітня 2013 р. – Донецьк: ТОВ «Цифрова типографія», 2013. – С. 179 – 184.

3. Баричев С. Криптография без секретов – http://www.bnti.ru/dbtexts/ipks/old/analmat/1_2002/crypto4.pdf - 26.03.2015

4. Ерош И.Л. Дискретная математика. Математические вопросы криптографии: Учеб. пособие / СПбГУАП. СПб, 2001. – 56с.

5. Лунин А.В., Сальников А.А. Перспективы развития и использования асимметричных алгоритмов в криптографии - http://ibks.ftk.spbstu.ru/psw/crypto/Lunin24.html - 26.03.2015

6. Трунов Д.Н. Электронные публикации с применением цифровых подписей: особенности реализации и перспективы развития: Электронная публикация. - https://sites.google.com/site/publicworkstrunov, 2013. – 7 с.

Приложение 1. Исходные тексты программы CryptoSignature (Turbo Pascal)
Текст приложения приведён в оригинальном файле.

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