2Анализ алгоритмов шифрования и разработка методики безопасной идентификации пользователей 2.1Анализ алгоритмов шифрования передаваемой информации
При построении корпоративных систем электронного документооборота, основанных на асимметричных алгоритмах шифрования, неизбежно возникает ряд проблем, связанных с реализацией математического решения криптографических функций разрабатываемого комплекса. Важность данной задачи обусловлена постоянным совершенствованием и модификацией, что неизбежно приводит к доработке существующих или созданию новых средств шифрования и, как следствие, к возникновению проблем при реализации данных средств.
В качестве базового алгоритма шифрования для процесса аутентификации был взят алгоритм электронно-цифровой подписи (ЭЦП).
Система шифрования на основе ЭЦП должна защищать от следующих действий злоумышленника:
Отказ от выполненных действий. Субъект утверждает, что он не посылал некоторое сообщение, хотя на самом деле он его послал;
Модификация сообщения. Получатель модифицирует полученное сообщение и утверждает, что именно такую версию он и получил;
Подделка. Субъект фабрикует сообщение и утверждает, что оно ему прислано;
Перехват. Злоумышленник С перехватывает сообщение, посланное А к В с целью модификации;
Маскировка. Посылка сообщения от чужого имени;
Повтор. Злоумышленник С посылает повторно сообщение от А к B, перехваченное им ранее.
Алгоритм электронно-цифровой подписи (ЭЦП) является одной из разновидностей асимметричных алгоритмов шифрования. Электронная подпись (ЭП) – информация в электронной форме, которая присоединена к другой информации в электронной форме (подписываемой информации) или иным образом связана с такой информацией, которая используется для определения лица, подписывающего информацию [68]. По своему существу электронная подпись представляет собой реквизит электронного документа, позволяющий установить отсутствие искажения информации в электронном документе с момента формирования ЭП и проверить принадлежность подписи владельцу сертификата ключа ЭП. Значение реквизита получается в результате криптографического преобразования информации с использованием закрытого ключа ЭП.
Все существующие алгоритмы ЭЦП построены по единому принципу. Разница заключается лишь в математической реализации отдельно взятого алгоритма. Это связано с тем, что каждый новый алгоритм получает улучшения по двум основным направлениям: повышение криптостойкости и снижение временных затрат и вычислительных ресурсов, при этом схема генерации и верификации шифра остаётся неизменной.
Для уяснения сущности алгоритма рассмотрим математические принципы, на которых они базируются. Все математические операции можно разделить на две части: вычисление дайджеста подписываемого документа и сам алгоритм вычисления и проверки шифра.
1 Хеширование применяется для сравнения данных: если у двух массивов хеш-коды разные, массивы гарантированно различаются; если одинаковые – массивы, скорее всего, одинаковы. В общем случае однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов входного массива; существует множество массивов, дающих одинаковые хеш-коды – так называемые коллизии. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций. Среди множества существующих хеш-функций принято выделять криптографически стойкие, применяемые в криптографии. Для того, чтобы хеш-функция считалась криптографически стойкой, она должна удовлетворять трем основным требованиям, на которых основано большинство применений хеш-функций в криптографии:
необратимость: для заданного значения хеш-функции m должно быть вычислительно неосуществимо найти блок данных ��, для которого ��(��) = ��;
стойкость к коллизиям первого рода: для заданного сообщения �� должно быть вычислительно неосуществимо подобрать другое сообщение ��, для которого ��(��) = ��(��);
стойкость к коллизиям второго рода: должно быть вычислительно неосуществимо подобрать пару сообщений (М, М’), имеющих одинаковый хеш.
Данные требования не являются независимыми:
обратимая функция нестойка к коллизиям первого и второго рода;
функция, нестойкая к коллизиям первого рода, нестойка к коллизиям второго рода; обратное утверждение неверно.
Следует отметить, что не доказано существование необратимых хеш-функций, для которых вычисление какого-либо прообраза заданного значения хеш-функции теоретически невозможно. Обычно нахождение обратного значения является лишь вычислительно сложной задачей. Для криптографических хеш-функций также важно, чтобы при малейшем изменении аргумента значение функции сильно изменялось (лавинный эффект). В частности, значение хеша не должно давать утечки информации даже об отдельных битах аргумента. [44]
2 В источниках [46] и [66] описание алгоритма вычисления и проверки ЭЦП сформулировано следующим образом. Пусть �� и �� – это закрытый и открытый ключ соответственно. Такая пара является единственной. Существует функция �� = ��(��), которая связывает �� и �� и, благодаря которой функции вычисления и проверки подписи становятся взаимообратными. Так же существует группа параметров ��, которая является открытой, и не должна меняться в пределах подписания и проверки одного документа. Пусть М – текст сообщения или документа, которые необходимо подписать с помощью электронной подписи. Функция ℎ(��) вычисляет хеш сообщения. Пусть существует функция ��(��, ℎ(��), ��, ��), где �� – случайное число, генерируемое каждый раз, при вычислении электронной подписи документа, тогда �� = ��(��, ℎ(��), ��, ��) – шифр, существующая в открытом виде, доступная всем, а в первую очередь получателю. Получателю известно само сообщение ��, параметры алгоритма �� и открытый ключ отправителя ��, а так же электронно-цифровая подпись к текущему документу, которую сгенерировал отправитель, назовём её ��′, и, которая должна совпадать с r, но возможно подверглась изменениям в результате действий злоумышленника. Функция �� = ��′(��,��(��),��) вычисляет аналогичный шифр, но на данном этапе это происходит уже с помощью открытого ключа. Таким образом, при равенстве ��′ и �� можно сделать вывод о том, что подпись и сам документ признается подлинным. Существует важное ограничение, накладываемое на параметры ��. В силу того, что в алгоритмах используются операция ������ (остаток от деления), не имеющая обратной, тем самым обозначая логику защиты алгоритма, параметры �� должны быть простые числа. Кроме того, данные параметры должны быть «длинными» числами, причём, чем «длиннее» число, тем выше криптостойкость алгоритма. Ключи алгоритма �� и �� берутся на основе параметров ��.
Представление чисел в алгоритмах с открытым ключом.
Несмотря на то, что с виду алгоритм достаточно не сложен в реализации, для вычисления всех параметров необходимо произвести большой объём операций. Это связано с тем, что параметры всех формул алгоритма – довольно длинные числа (примерно 21024), и для осуществления простейших операций над ними необходим специальный модуль работы с большими числами, так как стандартные типы данных не позволяют вместить такие числа [43].
Числа, для представления которых в стандартных компьютерных типах данных не хватает количества двоичных разрядов, называются "длинными". Реализация арифметических операций над такими "длинными" числами имеет название "длинной арифметики".
Организация работы с "длинными" числами во многом зависит от их представления. "Длинное" число можно записать, например, с помощью массива десятичных цифр, количество элементов в таком массиве равно количеству значащих цифр в "длинном" числе. При реализации арифметических операции над этим числом размер массива должен быть достаточным, чтобы разместить в нем и результат, например, результат операции умножения.
Существуют и другие представления "длинных" чисел. Рассмотрим одно из них. Представим наше число
30! = 265252859812191058636308480000000
в виде:
30! = 2 * (104)8 + 6525 * (104)7 + 2859 * (104)6 + 8121 * (104)5 + 9105 * (104)4 + 8636 * (104)3 + 3084 * (104)2 + 8000 * (104)1 + 0000 * (104)0.
Это представление наталкивает на мысль о массиве, представленном в таблице 2.1.
Таблица 2.1 – Представление числа
Номер элемента в массиве А
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
Значение
|
9
|
0
|
8000
|
3084
|
8636
|
9105
|
8121
|
2859
|
6525
|
2
|
Мы можем считать, что наше "длинное" число представлено в 10000-10 системе счисления (десятитысячно-десятичная система счисления, приведя аналогию с восьмерично-десятичной системой счисления), а "цифрами" числа являются четырехзначные числа. В целях ускорения вычислений выгодно брать за основание системы счисления, в которой будет храниться «длинное» число, равное максимально допустимому числу одного из стандартных типов данных (216 = 65536).
В нулевом элементе массива хранится длина числа или количество используемых ячеек в массиве. Для удобства дальнейшей работы цифры числа будут храниться в обратном порядке. Для совершения простейших операций над такими числами необходимо применять алгоритмы сложения, вычитания, умножения и деления «столбиком».
Определение «простоты» числа.
Задача определения простоты чисел является неотъемлемой частью реализации асимметричных алгоритмов шифрования. Неудовлетворительное решение данной задачи может сильно повлиять на защищённость данных. Напомним, что число называется простым, если не имеет целых делителей кроме единицы и самого себя. При традиционном подходе достаточно поделить число m по порядку на все числа от 2 до m-1, тогда число m можно считать простым в случае неделимости на целое ни на одно из предложенных. Учитывая, что в алгоритмах шифрования используются «длинные» числа (порядка 21024), подобный подход становиться вычислительно неосуществимой задачей.
В этом случае можно прибегнуть к малой теореме Ферма, которая гласит, что при условии простоты p и любом b выполняется равенство
bp-1 = 1 (mod p).
Обобщение и доказательство приводятся в источнике [44].
На примере числа 341, являющееся не простым, 341 = 11 * 31, равенство то же выполняется. 2340 = 1 (mod 341).
Действительно, 2340 = (210)34 = 102434,
но 1024 = 3 * 341 + 1 = 1 (mod 341), поэтому 102434 = 1 (mod 341).
Более того, существуют числа, которые не являются простыми, но которые ведут себя как простые в малой теореме Ферма. Такие числа называются кармайкловыми, то есть числа, являющиеся взаимно простыми с b, при которых выполняется условие малой теоремы Ферма.
Модификация данной теоремы, предложенная Рабином, применима к любым целым числам.
Тест Рабина является вероятностным. Для входного целого числа m тест Рабина может выдать один из следующих двух ответов: число m является составным; не знаю.
В случае первого ответа число m действительно является составным, тест Рабина предъявляет доказательство этого факта. Второй ответ может быть выдан как для простого, так и для составного числа m. Однако для любого составного числа m вероятность второго ответа не превышает 1/4. Ценность теста Рабина состоит именно в неравенстве, ограничивающем сверху вероятность второго ответа для произвольного составного числа m.
При проведении N тестов с составным числом m, в результате которых получаем второй ответ из двух возможных, вероятность того, что число m – составное, не превышает (1/4)N . При N → ∞ вероятность этого факта стремиться к нулю. Тем не менее, тест Рабина не предъявляет доказательства того, что число m простое. Доказательство законности теста Рабина и алгоритм его работы приведены в источнике [45].
Генерация случайных чисел.
В криптографических алгоритмах с открытым ключом требуется «длинное» случайное число, генерируемое каждый раз, когда необходимо зашифровать данные.
В качестве генератора случайного или неожиданного числа предлагается взять механизм, основанный на случайном действии подписчика документа. Такой способ получения случайного числа называется биологическим генератором случайных чисел. Данное предположение позволит вовлечь пользователя в работу системы подписания документа с одной стороны, и позволит сгенерировать довольно криптостойкое случайное число, меньше других подверженное взлому. В роли случайного действия пользователя предлагается взять мини-рисунок, сделанный самим пользователем и изображающий настоящую рукописную подпись. Для получения случайного числа необходимо использовать хэш-функцию, аргументом которой будет являться битовая последовательность, являющаяся одним из представлений полученного растрового изображения, а результатом – число необходимой длины, установленной конкретным алгоритмом шифрования.
H(X) = r, (2.1)
где r – искомое случайное (неожиданное) число заданной длины;
H – хэш-функция;
X – битовая последовательность.
Возможный вид мини-рисунка, сделанного пользователем, изображён на рисунке 2.1.
Рисунок 2.1 – Мини-рисунок, сделанный пользователем
В заключение следует отметить, что в данном подразделе были рассмотрены особенности применения алгоритмов шифрования основные проблемы, которые могут возникнуть в результате их построения: представление чисел, определение простоты числа, генерация случайных чисел, и предложены наиболее подходящие способы решения данных проблем.
|
