Содержание к диссертации
Введение
Глава 1. Алгоритмические средства обеспечения информационной безопасности информационно-телекоммуникационных систем на основе коммутативного преобразования информации 14
1.1 Понятие коммутативного защитного преобразования информации 14
1.1.1 Известные алгоритмы коммутативного преобразования информации 15
1.2 Применение алгоритмов на основе коммутативного преобразования для обеспечения информационной безопасности 18
1.2.1 Бесключевой протокол передачи информации 19
1.2.2 Протокол стойкого шифрования по ключу малого размера 21
1.2.3 Протокол игры в покер по телефону (честной раздачи карт) 26
1.2.4 Электронная жеребьёвка 31
1.2.5 Применение коммутативного шифрования в сенсорных сетях 32
1.2.6 Применение коммутативного шифрования в протоколе аутентификации в многоуровневой системе 33
1.2.7 Обеспечение конфиденциальности при построении электронного магазина 33
1.3 Постановка задачи диссертационного исследования 35
Глава 2. Алгоритмы коммутативного преобразования в группе точек ЭК на основе способа вероятностного кодирования 37
2.1 Обоснование подхода к вероятностному кодированию сообщения точкой ЭК 37
2.1.1 Элементы эллиптической криптографии 42
2.2 Алгоритм вероятностного кодирования сообщения точкой ЭК над простым полем () (АВК1) з
2.3 Алгоритм вероятностного кодирования сообщения точкой ЭК над простым полем () повышенной эффективности (АВК2) 49
2.4 Обоснование построения алгоритма вероятностного кодирования сообщения точкой ЭК над полем двоичных многочленов (2) 52
2.5 Алгоритм вероятностного кодирования сообщения точкой ЭК над полем двоичных многочленов (2) (АВК3) 53
2.6 Обоснование выбора длины добавляемой последовательности
2.6.1 Подход к обоснованию 55
2.6.2 Вероятность существования точки ЭК с заданным значением абсциссы 56
2.6.3 Оценка вероятности невозможности закодировать некоторое -битовое сообщение 58
2.6.4 Оценка вероятности существования хотя бы одного сообщения длиной бит, которое невозможно закодировать точкой ЭК 60
2.6.5 Вычисление, на основе полученных оценок вероятностей, достаточной длины добавляемой последовательности в предложенных алгоритмах 66
2.7 Способ кодирования сообщения точкой ЭК на основе механизма расщепления сообщения 67
2.7.1 Обоснование способа 67
2.7.2 Алгоритм кодирования сообщения точкой ЭК на основе способа расщепления сообщения 2.8 Объединённый алгоритм кодирования сообщения точкой ЭК на основе способа вероятностного кодирования и способа расщепления сообщений (ОАК) 72
2.9 Выводы ко второй главе 80
Глава 3. Алгоритмы коммутативного преобразования на основе трудности задачи факторизации, на основе трудности двух независимых задач 82
3.1 Обоснование подхода к построению криптосхем на основе нескольких вычислительно трудных задач 82
3.2 Особенности использования задачи факторизации в коммутативных шифрах 85
3.2.1 Способ построения алгоритма коммутативного шифрования на основе задачи факторизации 87
3.2.2 Способ расщепления сообщения
3.3 Алгоритм коммутативного шифрования на основе задачи факторизации 90
3.4 Алгоритм коммутативного шифрования, взлом которого требует одновременного решения двух независимых трудных задач 92
3.5 Алгоритм коммутативного шифрования на основе задачи дискретного логарифмирования по составному модулю, взлом которого требует одновременного решения двух независимых трудных задач 94
3.6 Выводы к третьей главе 95
Глава 4. Реализация предложенных алгоритмов с использованием групп простого порядка 98
4.1 Понятие идеального коммутативного шифра 98
4.1.1 Обоснование подхода к выбору "идеальных" параметров алгоритма коммутативного шифрования 99
4.1.2 Выбор идеальных параметров для коммутативного шифра над двоичным полем 100
4.1.3 Выбор идеальных параметров для коммутативного шифра на эллиптической кривой 1 4.2 Алгоритм коммутативного шифрования на эллиптической кривой на основе механизма вероятностного кодирования 102
4.3 Протокол гарантированной защиты информации с разделяемым ключом малого размера 1 4.3.1 Обоснование стойкости построенного протокола на ЭК 106
4.3.2 Протокол защищённой передачи информации с разделяемым ключом малого размера, отличающийся наличием дополнительного разового ключа 108 4.3.3 Протокол защищённой передачи информации с разделяемым ключом малого размера, отличающийся использованием способа расщепления сообщения 112
4.3.4 Протокол защищённой передачи информации с разделяемым ключом малого размера, отличающийся использованием разделяемого ключа малого размера в коммутативных преобразованиях 115
4.3.5 Протокол защищённой передачи информации с разделяемым ключом малого размера, отличающийся отсутствием использования алгоритма симметричного шифрования 120
4.4 Выводы к четвёртой главе 125
Заключение 126
Сокращения
- Известные алгоритмы коммутативного преобразования информации
- Алгоритм вероятностного кодирования сообщения точкой ЭК над простым полем () (АВК1)
- Особенности использования задачи факторизации в коммутативных шифрах
- Обоснование подхода к выбору "идеальных" параметров алгоритма коммутативного шифрования
Введение к работе
Актуальность темы. Для решения ряда специфических задач информационных технологий, таких как задача защищённой передачи информации без предварительной договорённости о ключе/без обмена ключами («бесключевое шифрование») или при наличии ограниченного ключевого материала, задача равноправного случайного выбора сообщений из заданной их совокупности, осуществляемого каждым пользователем без раскрытия выбираемых сообщений (электронная жеребьёвка и т.п.) - применяются алгоритмы коммутативного защитного преобразования (шифрования) (далее - АКЗП). В последние десятилетия предложен ряд новых применений АКЗП в системах электронной коммерции (обеспечение конфиденциальности покупки), аутентификации в многоуровневых системах и сенсорных сетях (повышение стойкости системы к компрометации узлов).
При этом характерным является возрастание требований к АКЗП одновременно по стойкости, скорости и по простоте реализации. Это делает актуальным построение АКЗП, основанных на вычислениях на эллиптической кривой (ЭК).
При постоянном росте производительности технических средств и развитии научных подходов к решению вычислительно-сложных задач, лежащих в основе АКЗП, актуальным становится рассмотрение понятия безопасности криптографических алгоритмов и протоколов как интегральной характеристики, отражающей то, что оценка стойкости даётся как вычислительная трудоёмкость лучшего известного в настоящее время алгоритма взлома криптосхем, в то время как применение последних опирается также и на предположение о достаточно малой вероятности появления в обозримом будущем прорывных подходов к взлому криптосхем. Для существенного повышения указанного интегрального показателя безопасности (стойкость, приведённая на вероятность) отечественными и зарубежными исследователями были предложены схемы электронной подписи (ЭП), аутентификации, для взлома которых необходимо одновременное решение двух независимых трудных задач. Однако вопрос построения
АКЗП на основе двух сложных задач остался нерешённым.
В ряде важных для практики случаев использования протоколов на основе АКЗП возникают условия, когда потенциальный нарушитель знает исходное и преобразованное значение сообщения, что в случае "слабых" сообщений (имеющих малое значение порядка или порядок, не содержащий ни одного большого простого делителя) позволяет ему легко получить некоторую информацию о секретном ключе. Это делает актуальным синтез АКЗП, свободного от "слабых" сообщений.
Таким образом, актуальной является разработка АКЗП на основе вычислений в группе точек ЭК, АКЗП на основе сложности двух трудных задач, а также АКЗП, свободного от "слабых" сообщений, что обеспечит повышение уровня информационной безопасности информационно-телекоммуникационных систем, базирующихся на АКЗП.
Степень разработанности темы. Основополагающие научные исследования в области коммутативных защитных преобразований (КЗП) и их применения в области обеспечения информационной безопасности при передаче и распространении информации приведены в работах Shamir A. (1980), Rivest R. (1978), Massey J. (1981), Pohlig S. (1984). АКЗП начинают применяться для решения следующих практических задач: – обеспечения конфиденциальности в электронной коммерции
и азартных играх - работы исследователей Bao F. (2000),
Agrawal R. (2003), Cheung S. (2004), Chen C. (2011) Deusajute A.,
Barreto P. (2008), Lerner S. (2011); – аутентификации в многоуровневых системах (в частности,
веб-приложениях) и сенсорных сетях: Yang H. (2004),
Leonardo B. (2011), Паутов П.А. (2010); – защиты информации с заданным уровнем стойкости при
использовании ключей малого размера: Молдовян Н.А.,
Муравьев А.В. (2014).
Объект исследования: защищённые автоматизированные информационно-телекоммуникационные системы (АИТС).
Предмет исследования: способы и алгоритмы коммутативных защитных преобразований, используемые для обеспечения информационной безопасности АИТС.
Цель диссертационного исследования состоит в повышении
уровня информационной безопасности информационно-
телекоммуникационных систем и технологий, базирующихся на АКЗП.
Научная задача состоит в разработке совокупности алгоритмов коммутативного защитного преобразования, основанных на задачах дискретного логарифмирования (ЗДЛ) и факторизации (ЗФ). Для достижения поставленной цели и решения задачи диссертационного исследования были поставлены и решены следующие частные задачи: – разработка алгоритма КЗП на основе трудности ЗФ; – разработка алгоритма КЗП на основе трудности одновременного
решения ЗФ и ЗДЛ; – разработка алгоритма КЗП на основе трудности ЗДЛ в группе точек ЭК, отличающегося обоснованием размера случайного значения, присоединяемого к сообщению, кодируемому точкой ЭК, заданной над простым конечным полем; – разработка алгоритма КЗП на основе трудности ЗДЛ в группе точек ЭК, отличающегося обоснованием размера случайного значения, присоединяемого к сообщению, кодируемому точкой ЭК, заданной над конечным двоичным полем; – разработка алгоритма КЗП, свободного от "слабых" сообщений. Методы исследования. В работе использован аппарат и методы математической статистики, теории вероятности, алгебры, теории чисел, криптографии и вычислительные эксперименты.
На защиту выносятся следующие научные результаты: – алгоритм КЗП в группе точек ЭК, заданной над простым
конечным полем, отличающийся обоснованием выбора размера
случайного параметра, присоединяемого к сообщению; – алгоритм КЗП в группе точек ЭК, заданной над конечным
двоичным полем, отличающийся обоснованием выбора размера
случайного параметра, присоединяемого к сообщению; – алгоритм КЗП с улучшенным интегральным показателем
безопасности на основе сложности двух независимых трудных
задач (ЗФ и ЗДЛ в простом поле); – алгоритм КЗП, свободный от "слабых" сообщений.
Научная новизна.
-
Обоснован выбор размера случайного значения, присоединяемого к сообщению, кодируемому точкой ЭК, заданной над конечным простым и двоичным полями, с учётом двух вероятностных характеристик - вероятности невозможности закодировать некоторое сообщение точкой ЭК и вероятности существования хотя бы одного сообщения заданной длины, которое будет невозможно закодировать. Показано, что достаточно низкие значения указанных вероятностей достигаются при незначительном увеличении размера сообщения (не более 5%).
-
Предложен способ построения АКЗП в группе точек ЭК, отличающийся применением способа расщепления сообщения, при котором увеличение размера сообщения не превышает 3%.
-
Предложен способ построения АКЗП на основе вычислительной сложности ЗФ.
-
Предложен способ построения АКЗП с улучшенным интегральным показателем безопасности на основе сложности одновременного решения двух трудных задач - ЗФ и ЗДЛ.
-
Разработан АКЗП, свободный от "слабых" сообщений.
Теоретическая и практическая значимость работы.
Теоретическая значимость работы состоит в расширении арсенала стойких АКЗП, а именно: разработке АКЗП на основе сложности ЗФ, на основе сложности одновременного решения двух вычислительно сложных задач, а также АКЗП, свободного от слабых сообщений. Для построения АКЗП на основе сложности ЗДЛ в группе точек ЭК обоснован выбор размера случайного значения, присоединяемого к сообщению – параметр, определяющий превышение размера шифротекста над исходным сообщением. Также предложен новый способ построения АКЗП в группе точек ЭК, для которого среднее увеличение размера сообщения не превосходит 3%. Практическая значимость определяется тем, что обеспечение высокого уровня информационной безопасности современных информационно-телекоммуникационных систем, в том числе базирующихся на АКЗП, является актуальной и перманентной практической задачей.
Степень достоверности и апробация результатов.
Обоснованность научных положений, выводов и практических рекомендаций, полученных в диссертационной работе, обеспечивается анализом состояния исследований в данной области на сегодняшний день, формальными доказательствами, вычислительным экспериментом, полученным патентом Российской Федерации и апробацией результатов на научно-технических конференциях в 2012-2016 гг.
Основные результаты диссертации изложены в 17 публикациях, в том числе, в 3 статьях, опубликованных в ведущих рецензируемых журналах, входящих в перечень ВАК, 3 докладах на международных конференциях и 11 докладах на российских конференциях. Получен 1 патент на изобретение. Результаты диссертационной работы внедрены в учебный процесс на кафедре «Информационная безопасность» Санкт-Петербургского государственного электротехнического университета «ЛЭТИ» в учебные планы дисциплин «Криптографические методы защиты информации», «Криптографические протоколы».
Структура и объем работы. Диссертационная работа изложена на 150 стр., из которых основного текста – 130 стр., включает 4 главы, 17 рисунков, 8 таблиц. Библиографический список содержит 115 наименований.
Известные алгоритмы коммутативного преобразования информации
Заметим, что на третьем шаге протокола отправитель передаёт шифро-текст 3 - сообщение , зашифрованное на ключе получателя - но в то же время отправитель не знает ключа получателя. Получение такого шиф-ротекста обеспечивается свойством коммутативности при расшифровании 2: (2) = (EB(EA(M))) = (EA(EB(M)) = ().
Этот протокол вообще не требует обмена ни секретными, ни открытыми ключами, ни выработки общего ключа шифрования. На самом деле в этой системе отправителем и получателем применяются ключи индивидуального использования, которые однако не требуют того, чтобы их знала какая-либо другая сторона и используются «локально». Таким образом, поскольку ключевой обмен отсутствует, то мы говорим о «бесключевом шифровании». Суть состоит в том, что обе стороны формируют некоторые секретные параметры, но при этом совсем не требуется их передача партнёру по сеансу. Отправитель зашифровывает сообщение и посылает его получателю. Получатель ещё раз зашифровывает сообщение и возвращает двукратно зашифрованное сообщение отправителю. Отправитель расшифровывает сообщение, превращая его в однократно зашифрованное по ключу получателя, и отправляет его ещё раз получателю. Теперь получатель, зная свой секрет, по которому он осуществлял шифрование, выполняет процедуру расшифрования и восстанавливает сообщение, которое и хотел ему переслать отправитель. Схема достаточно проста, но требуется найти такие процедуры шифрующих преобразований, выполняемых двумя сторонами, которые были бы коммутативны относительно друг друга, в тоже время обеспечивали высокую криптостойкость этого протокола.
Например свойство коммутативности обеспечивается процедурой шифрования, заключающейся в наложении с помощью операции XOR () на сообщение ключа, длина которого равна длине . Пусть ключи и являются случайными равновероятными ключами, тогда в отдельности каждая из процедур шифрования = и = обеспечивает абсолютную стойкость криптографического преобразования [1, раздел 1.5]. Однако такой способ шифрования неприемлем в рассматриваемом протоколе. Действительно, в этом случае на шагах 1, 2 и 3 по открытому каналу пересылаются сообщения 1 = ; 2 = , 3 = , а следовательно, потенциальный нарушитель, прослушивающий канал связи и перехвативший эти шифротексты может легко вычислить = 1 2 3.
В качестве коммутативной функции шифрования А. Шамир (и независимо Дж. Омура) [26] предложили возведение в степень по простому модулю . Так же известна аналогичная схема при реализации коммутативной функции как возведение в степень по модулю неприводимого многочлена в поле двоичных многочленов - схема шифрования Месси-Омуры [27;28]. Приведённая схема бесключевого шифрования (трехшагового протокола шифрования) представляет практический интерес, как и схема открытого распределения ключей Диффи-Хеллмана, предоставляя возможность двум сторонам, не разделяющим общий секрет, конфиденциально обменяться информацией по незащищённому каналу. В тоже время протокол не обеспечивает аутентификации взаимодействующих сторон, уязвим к атаке "человек посередине".
Стандартные протоколы симметричного шифрования обеспечивают гарантированную стойкость при использовании ключей достаточно большого размера, например 128 или 256 бит [1; 29; 30], использование ключа малого разме 22 ра не является безопасным, так как при перехвате криптограммы практически возможно нахождение ключа путём перебора по ключевому пространству. Под малым размером понимается длина в 30-50 бит, чему например соответствует пароль в 6-10 символов числобуквенного алфавита [31]. Может показаться парадоксальным, что ключи такого размера находят применение для построения протоколов стойкого шифрования. Идея же такого построения заключена в комбинировании алгоритмов асимметричной и симметричной криптографии, малый ключ используется не напрямую для шифрования, а для осуществления процедур аутентификации сторон протокола, причём обеспечивается неразрывность процедур шифрования и аутентификации. Применение разделяемого секретного ключа в процедурах аутентификации сообщений принципиально отличается от их применения в процедурах шифрования сообщений. Это отличие состоит в том, что в последнем случае у потенциального атакующего имеется возможность многократного опробования различных значений ключа (атака по словарю), пока не будет найден секретный ключ, который использовался для шифрования, тогда как в первом случае имеется только возможность однократной попытки угадать секретный ключ и навязать легальному пользователю ложное сообщение. Вероятность такого обмана достаточно мала даже в случае использования коротких разделяемых ключей и составляет 2-, где длина ключа в битах.
Впервые такое применение малого ключа (пароля) было предложено [32] в 1992 году Стивом Беловином и Майклом Мерритом, обозначив новую группу протоколов обмена зашифрованными ключами (EKE, encrypted key exchange), в которых общий секретный ключ используется для шифрования генерированного случайным образом открытого ключа. В работе приводятся примеры использования указанного подхода с различными системами асимметричного шифрования. Например протокол DH-EKE - реализация этого подхода со схемой открытого распределения ключей Диффи-Хелмана [1;4;33] чем решается проблема атаки «человека по середине» через аутентификацию передаваемых публичных ключей путём их шифрования общим секретным ключом. Известны и другие вариации использованию малого ключа, например протокол SPEKE [34] - в схеме Диффи-Хеллмана малый ключ используется для генерации общего основания, используемого далее для выработки общего ключа. Недавно был предложен [24;25] протокол стойкого шифрования по ключу малого размера - на основе комбинирования протокола бесключевого шифрования (рассмотренного в разделе 1.2.1) и аутентификации передаваемых в рамках протокола криптограмм путём их шифрования общим секретным ключом малого размера. Заданный уровень стойкости обеспечивает коммутативное шифрование путём выбора соответствующих параметров алгоритма бесключевого шифрования. Симметричное шифрование используется как механизм аутентификации передаваемых сообщений по разделяемому ключу, благодаря чему потенциальный нарушитель не имеет возможность выдать себя за легального отправителя или получателя сообщения и найти значение секретного ключа методом угадывания или полного перебора. Поскольку значения шифротекстов, возникающих в проколе бесключевого шифрования являются псевдослучайными (вычислительно неотличимыми от случайных значений), то их зашифрование не даст возможности потенциальному атакующему найти значение разделяемого секретного ключа, а для легального отправителя и получателя сделает возможным проверить тот факт, что ни один из шифротекстов, переданных на этапах протокола бесключевого шифрования, не был подменён потенциальным нарушителем.
В протоколе используется алгоритм шифрования , для которого выполняется условие коммутативности (1.1). Схема протокола в общем виде приведена на рисунке 1.2, где - процедура расшифрования на ключе в алгоритме , параметры и являются секретными ключами отправителя и получателя соответственно для алгоритма коммутативного шифрования , ключ есть разделяемый отправителем и получателем ключ малого размера для использования его в алгоритме симметричного шифрования (АСШ) G. Передача сообщения выполняется по следующему алгоритму:
Алгоритм вероятностного кодирования сообщения точкой ЭК над простым полем () (АВК1)
Идея усовершенствования алгоритма основана на том, что выбор ординаты (большего или меньшего значения) на шаге 5 базового алгоритма, описанного в подразделе 2.2 можно использовать для определения необходимости использования "буферного" бита и, в случае, когда он не нужен - увеличения за его счёт - длины добавляемой случайной последовательности. Увеличение длины добавляемой последовательности в свою очередь увеличивает число проверяемых алгоритмом значений возможны точек ЭК, и в конечном счёте, уменьшает вероятность отказа (невозможности закодировать сообщение точкой ЭК).
Пусть ЭК задана над полем () и разрядность числа равна бит, причём разность — составляет число = [8.. 16] число добавляемых бит. Алгоритм кодирования -битового блока данных представлен на рисунке 2.3 и описывается следующим образом:
1. Установить значение счётчика = 0, = — , вычислить значение = -і- 2Р и сравнить и как -битовые двоичные числа (операция -Ь есть взятие неполного частного от деления, может быть представлена как "отбрасывание" последних бит в битовом представлении числа , осуществляемая битовым сдвигом [69]). Если , то перейти к шагу 2, в противном случае перейти к шагу 3. 2. Если 2Р, то сформировать -битовую строку , двоичное значение которой равно и перейти к шагу 7. В противном случае вывести сообщение "Кодирующей точки не существует". 3. Если 2Р-\ то сформировать ( - 1)-битовую строку , двоичное значение которой равно и перейти к шагу 4. В противном случае вывести сообщение "Кодирующей точки не существует". 4. Присвоить переменной значение , где знак «» обозначает операцию конкатенации (присоединения), и вычислить значение = (3 + + ) mod . 5. Вычислить символ Лежандра = (/). Если = 1, то перейти к шагу 6, иначе прирастить счетчик і— + 1 и перейти в шагу 3. 6. Вычислить два значения корня \ = ±y mod , где і,2 {1,2,..., - 1}, присвоить меньшее из значений переменной и перейти к шагу 10. 7. Присвоить переменной значение , где знак «» обозначает операцию конкатенации (присоединения), и вычислить значение = (3 + + ) mod . 8. Вычислить символ Лежандра = (/). Если = 1, то перейти к шагу 9, иначе прирастить счетчик і— + 1 и перейти к шагу 2. 9. Вычислить два значения корня \ = ±y mod , где і,2 {1,2,..., - 1}, присвоить большее из значений переменной и перейти к шагу 10. 10. Выдать пару значений (,) как координаты точки , которая кодирует сообщение . В алгоритме кодирования используются случайные значения, т.е. он является вероятностным. Одно сообщение может быть закодировано точками ЭК, имеющими различные значения абсциссы.
Предложенная версия алгоритма вероятностного (АВК2) кодирования отличается от АВК1, описанного в параграфе 2.2 меньшей вероятностью отказа, т.к. длина добавляемой последовательности может (в зависимости от значения кодируемого сообщения ) быть на 1 бит больше (- бит), тогда как в АВК1-она всегда составляет ( - - 1 бит). К недостаткам следует отнести несколько усложнившуюся процедуру декодирования, которая требует дополнительного вычисления корня.
Возможна модификация предложенного алгоритма так, чтобы на 1 бит увеличивать не длину добавляемой последовательности, а кодируемое сообщение, что с одной стороны позволит уменьшить превышение размера шифротекста над сообщением, но с другой - приведёт к изменяемой длине блока кодируемого сообщения, что очевидно уменьшит удобство схемотехнической реализации, за 52 труднит распараллеливание процесса кодирования независимых блоков одного сообщения.
Двоичные многочлены, заданные над полем (2) и имеющие степень, не превышающую значение - 1, образуют поле двоичных многочленов (2) при задании операции умножения многочленов по модулю неприводимого двоичного многочлена () степени . Множество всех возможных значений шифруемых сообщений представляются ненулевыми битовыми цепочками длины . Тривиально кодируемое сообщение может быть интерпретировано, как элемент бинарного поля (2) через использование полиномиального представления. Использование ЭК, заданных над полем характеристики 2 представляет интерес ввиду эффективности программно-аппаратной реализации вычислительных операций на ЭВМ [43;66;71;72].
Рассмотренная схема алгоритма кодирования сообщения точкой ЭК, заданной над простым полем (АВК1,АВК2) не может быть напрямую переложена для кодирования сообщения точкой ЭК, заданной над конечным двоичным полем многочленов в силу следующих особенностей:
1. Невозможность использования признака наличия корня (символа Ле-жандра) для определения принадлежности точки ЭК. Необходимо использовать иной механизм.
2. Т.к. все сообщения представляются многочленами степени - 1 меньшей степени неприводимого многочлена – то сообщения после присоединения добавочной последовательности строго меньше неприводимого многочлена, т.е. нет необходимости в использовании "буферного" бита, применима базовая схема алгоритма, описанная в параграфе 2.2.
Рассматривая стандартное уравнение (2.2) для несуперсингулярной эллиптической кривой в форме Вейерштрасса, заданной над конечным полем (2)-если (,) ,, и = 0, тогда 22 + = + + 2 . Заменив = (2.4) получим уравнение Л + Л = х + а -\— (2.5) X2 Для определения разрешимости этого уравнения после подстановки проверяемого значения Х{ (как механизм определения принадлежности точки к ЭК, вместо используемого в АВК1,АВК2 символа Лежандра) используется функции следа Тг(а) элемента поля а (подраздел 2.1.1) - квадратное уравнение А2 + А = а, для данного а Є GF(2n), в поле GF(2n) имеет решение тогда и только тогда, когда Тг(а) = 0 [41, стр. 76]. На практике подсчёт следа элемента легко осуществим, например формулы упрощённого подсчёта следа для NIST-кривых [62] приведены в [66, 7.1 Appendix]. Т.е. чтобы узнать, имеет ли уравнение (2.5) решение, нужно проверить след правой части уравнения, если он равен нулю (Тг(х + а + А) = 0), тогда уравнение имеет корни (элемент поля х является ж-координатой некоторой точки на эллиптической кривой Еаф). Можно вычислить решение А2 + А = а по формуле (2.3). Значение ординаты у вычисляется в соответствии с выполненной заменой (2.4) из найденного решения А уравнения (2.5) и абсциссы х: у = А х.
Особенности использования задачи факторизации в коммутативных шифрах
В основе алгоритма лежит идея объединения двух способов кодирования (вероятностного и расщепления) c целью уменьшения общего размера шифро-текста, получаемого в результате кодирования нескольких сообщений. В АКШ на основе только способа вероятностного кодирования - параметр алгоритма (длина добавляемой последовательности) выбирается достаточно большим для обеспечения пренебрежимо малых вероятностей Pr(-) и Pr() отказа - невозможности закодировать сообщение точкой ЭК (раздел 2.6.5). Но в предлагаемом «объединённом» алгоритме любое сообщение будет представлено точкой ЭК, что можно рассматривать как отдельное преимущество, но так же позволяет задать любое другое, в частности меньшее значение параметра в способе вероятностного кодирования (СВК, реализуемый алгоритмом АВК1,АВК2,АВК3, но с уменьшенной длиной добавляемой последовательности). В предлагаемом алгоритме сначала делается попытка закодировать исходное сообщение с помощью СВК. В случае успешного кодирования - размер шифротекста превышает размер исходного сообщения на несколько бит. В случае невозможности подобрать для сообщения точку ЭК - сообщение кодируется с помощью способа расщепления сообщения (СРС, предложен в разделе 2.7.2 на стр. 70), которым всегда можно закодировать сообщение точкой ЭК. В таком случае размер шифротекста превышает размер исходного сообщения двукратно, но такие случаи можно сделать достаточно редкими подобрав соответствующий параметр СВК - длину р добавляемой последовательности, которая определяет вероятность невозможности закодировать некоторое /і-битовое сообщение алгоритмом вероятностного кодирования (раздел 2.6.3). За счёт того, что большая часть сообщений будет кодироваться СВК (и изредка - СРС) - среднее удлинение сообщения будет невелико. Необходимо подобрать такую длину добавляемой последовательности р для СВК, чтобы в среднем размер шифротекста был меньше, чем если бы использовался только СВК.
Пусть є- число бит, на которые размера шифротекста превышает размер исходного сообщения. Тогда є равно р в случае представления сообщения точкой ЭК алгоритмом вероятностного кодирования и равно битовой длине 7г порядка поля, над которым задана ЭК в случае расщепления сообщения на пару значений (С,К), одно из которых является точкой ЭК. Таким образом є можно рассматривать как случайную величину, принимающую значение р с вероятностью 1 - Рг(-) (сообщение было успешно закодировано точкой ЭК с помощью СВК) и значение 7г с вероятностью Рг(—) (сообщение не было закодировано СВК и кодировалось точкой ЭК с помощью СРС). Тогда среднее значение є есть математическое ожидание М[є] [78], вычисляемое для дискретной случайной величины по формуле (2.39) Вероятность Рг(-) отказа (невозможности закодировать сообщение точкой ЭК) для используемого алгоритма вероятностного кодирования (АВК1,АВК2,АВК3) определяется формулами (2.10),(2.12),(2.13) соответственно.
Например, пусть ЭК задана над полем () и разрядность числа равна = 256 бит, причём разность — составляет число = 4 число добавляемых бит, в качестве алгоритма для СРС используется АВК3, вероятность Рг(—) для которого определяется формулой (2.13). Тогда: = л/0.969 0. Таким образом в данном примере можно говорить, что удлинение сообщения в среднем на одно сообщение составит 4 ± 1 бит. В процентном соотношении к длине исходного сообщения = 256 — 4 = 252 бит - составляет 4.004/252 100% « 1,6%. Полученное значение превышения размера шифро-текста над кодируемым сообщением в два раза меньше, чем при построении АКШ с использованием только АВК3 - при тех же условиях (том же размера порядка) удлинение сообщения составляет 8 бит (при выборе достаточной длины для обеспечения пренебрежимо малой вероятности отказа в кодировании, раздел 2.6.5).
Значение среднего удлинения сообщения для различных значений , и при использовании АВК1,АВК2,АВК3 приведены в таблицах 3,4,5 соответственно, где обозначены - - битовая длина порядка поля, над которым задана ЭК - - битовая длина кодируемого сообщения - - число бит, на которые длина сообщения задаётся меньше длины порядка поля, = — , что определяет длину присоединяемой к сообщению случайной последовательности в соответствующем алгоритме вероятностного кодирования ( = или = — 1, раздел 2.6.3). - М[є] - среднее значение удлинения сообщения на одно сообщение - математическое ожидание, вычисленное по формуле (2.37) - с.к.о. сг - среднее отклонение значения удлинения сообщения от среднего значения, среднеквадратичное отклонение, вычисленное по формуле (2.39) _ є = ММ 100% - превышение размера шифротекста над исходным сооб щением в %. Из указанных в таблицах значений заметим, что: - Наименьшее значение М[є] 5 бит при использовании АВК1 и АВК2 с параметром р = 4 и р = 5 бит, что в процентном отношении к битовой длине исходного сообщения не превышает 3%. С учётом разброса (с.к.о.) предпочтительным видится использование значения р = 5.
Наименьшее значение М[є] 4 бит при использовании АВК3 с параметром р = 3 и р = 4 бит, что в процентном отношении к битовой длине исходного сообщения не превышает 2.5%. С учётом разброса (с.к.о.) предпочтительным видится использование значения р = 4. Полученная разница в 1 бит объяснима тем, что в АВК3 для перебора используются все р бит, тогда как в АВК1 на 1 бит меньше. Последнее влечёт экспоненциальную разницу в значении вероятности Рг(—) (формулы (2.10),(2.13)) для этих алгоритмов. Частичное же использование упомянутого одного бита в АВК2 по сравнению в АВК1 уменьшило значение Рг(—) примерно в два раза (формула (2.12)). - при уменьшении длины добавляемой последовательности р - растёт среднее значение удлинение сообщения є, что объяснимо тем, что из-за возросшей вероятности Рг(-) сообщение чаще кодируется СРС, при котором превышение размера шифротекста над кодируемым сообщением составляет 100%. - при увеличении длины добавляемой последовательности р - значение є приближается к значению р, как если бы для кодирования использовался только СВК что объяснимо тем, что c уменьшением вероятность Рг(—) случаи кодирования СРС (дающие превышение размера шифротекста над кодируемым сообщением в 100%), происходят достаточно редко. Таким образом, при построении АКШ на основе предложенного алгоритма объединённого кодирования, в случае использования для вероятностного кодирования сообщения точкой ЭК АВК1 или АВК2- рекомендуемым значением для него является = 5 и = 4 для АВК3. При этом среднее превышение длины шифротекста над длиной исходного сообщения не превышает 3%. При этом принципиальным отличием предложенного способа построения АКШ по сравнению с построения АКШ на основе только алгоритма вероятностного кодирования является то, что любое сообщение будет представлено точкой ЭК, тогда как в способе вероятностного кодирования этот результат не гарантируется (но при выборе параметра алгоритма , в соответствии с приведённым в данной главе обоснованием, достигается пренебрежимо малая вероятность неудачи). При этом общее превышение размера шифротекста над исходным сообщением в предложенном способе кодирования даже несколько уменьшилось (3% против 5%).
Обоснование подхода к выбору "идеальных" параметров алгоритма коммутативного шифрования
Стойкость трехшагового протокола шифрования по коротким ключам определяется стойкостью используемого алгоритма коммутативного шифрования. Разделяемый секретный ключ К служит для того, чтобы предотвратить атаки активного нарушителя, в которых нарушитель выдаёт себя за легального отправителя или получателя.
Следует отметить важность сохранения личных ключей сторон протокола (еі,Є2) в тайне от злоумышленника. Это справедливо как в исходной схеме трех-проходного протокола Шамира [1;26] - знание любого из ключей напрямую приводит к восстановлению передаваемого сообщения М из перехваченного шиф-ротекста), так и в предложенном варианте с механизмом аутентификации - знание одного из этих ключей позволит на основе перехваченных шифротекстов С Х С Ъ С 3 восстановить малый ключ К перебором по ключевому пространству &(0,1 ... 21 1 — 1) и, далее, передаваемого сообщения М по следующей схеме:
Положим, злоумышленнику известен ключ е2. Перебором по ключевому пространству - для каждого проверяемого ключа К І І Є {l.. } 1. Подать тестируемый ключ Кг на вход алгоритма симметричного шифрования Gk , для расшифрования шифротекста С[: С\ = Ск-г(С[) = Mei и шифротекста С2: С2 = Gki l(C 2) = Мёхё2. 2. Умножить полученное значение С\ на известный ключ е\, равенство значений С\б\ и С2 с вероятностью, близкой к 1 означает что тестируемый ключ - искомый. Перейти к шагу 3, иначе перейти к проверке следующего возможного ключа К - шагу 1. 3. Расшифровать на ключе К І шифротекст С 3 получив Сз = Ме2, вычислить ключ расшифрования АКШ d2 как значение, взаимно обратное по модулю Q известному ключу е2 и получить передаваемое сообщение по формуле М = С?Д2
Строго говоря, равенство значений С\Є\ и С2 на шаге 2 означает лишь, что после расшифрования на ключе К{ получены такие точки ЭК, что Сіві = С2 mod Q, но не что Сі = С\, С2 = С2 и КІ = К. Т.е. при расшифрования АСШ G получены такие элементы группы, что один переходит в другой при домножении на число в\. С другой стороны числовая последова 107 тельность на выходе АСШ считается псевдослучайной (вычислительно неотличимой от случайной), следовательно вероятность такого события пренебрежимо мала. Указанная атака невозможна без знания злоумышленником ключей одной из сторон. В самом деле, даже в случае, когда не известен ключ Є2 (ei), но известно передаваемое сообщение М- для определения, что использован верный ключ Кг необходимо решение вычислительной задачи Диффи-Хеллмана (CDH, по трем элементам группы М, Ме\,Мв2 найти Ме\Є2) или задачу принятия решения Диффи-Хеллмана (DDH, по четырём элементам группы М,Ме\,Ме2,Ме:і принять решение е\Є2 = ез mod Q) [2]. Однако эти задачи считаются вычислительно-сложными (с оговоркой, что задача принятия решения Диффи-Хеллмана является легко разрешимой в суперсингулярных кривых с помощью алгоритма спаривания Вейля, что используется в личностной криптографии [2, глава 13]). Приведённые рассуждения подчёркивают необходимость сохранения в секрете/удаления по завершении сеанса связи личных ключей сторон протокола и не рассматривается как недостаток предложенной схемы.
Однако предложенная реализация протокола на ЭК имеет существенный недостаток, позволяющий злоумышленнику успешно осуществить атаку на основе известных шифротекстов, а именно при наличии достаточного числа перехваченных сообщений, восстановить секретный ключ малого размера.
Необходимым условием для возможности многоразового использования секретного ключа малого размера в предложенном протоколе бесключевого шифрования является псевдослучайность (вычислительная неотличимость от случайных значений) передаваемых шифротекстов, что предотвращает получение атакующим данных, использование которых позволяет осуществить многократную проверку предполагаемых значений разделяемого секретного ключа. Действительно, шифрование данных такого типа приводит к получению криптограмм, по которым определить короткий ключ шифрования методом перебора по пространству возможных ключей не представляется возможным, поскольку каждый из испытуемых ключей приведёт к восстановлению из криптограммы некоторого случайного (псевдослучайного) исходного текста. Для атакующего каждое допустимое значение ключа является равноправным, т.е. у него нет вычислительно эффективного критерия отбраковки неверных значений ключа.
В случае же реализации протокола на ЭК у атакующего есть такой критерий - передаваемое сообщение, до шифрования секретным ключом малого размера, соответствовало абсциссе точки ЭК. При разработке способа вероятностного кодирования в главе 2 было показано, что случайное значение является абсциссой точки ЭК с вероятностью 1/2, что позволяет злоумышленнику -методом перебора по пространству возможных ключей и проверкой полученного значения на соответствие точке ЭК - уменьшать множество возможных значений ключа в два раза на каждом перехваченном сообщении. Таким образом для нахождения значения ключа необходимо число перехваченных сообщений, равное битовой длине ключа. С учётом указанного недостатка предложенный протокол исключает повторное использование общего ключа малого размера, но при разовом его использовании позволяет гарантированно защищенно передать сообщение.
Рассмотрим два подхода для решения указанной проблемы: 1. устранение утечки информации о разделяемом ключе К путём использования дополнительного разового ключа R для шифрования передаваемых на шагах протокола сообщений - разделы 4.3.2, 4.3.3; 2. устранение критерия для отбраковки неверных значений разделяемого ключа К- разделы 4.3.4 и 4.3.5;
В основе данной вариации описанного в разделе 4.3 протокола лежит идея о введении дополнительного разового ключа R, который будет использоваться вместо общего разделяемого ключа К для шифрования сообщений, передаваемых на шагах протокола. Для обеспечения возможности использования разового ключа R обеими сторонами информационного обмена - в протокол вводится дополнительный шаг по шифрованию разового ключа R на разделяемом ключе К и передаче полученного значения отправителю.