Автореферат С.Е.Нысанбаевой


  

УДК 004.056.55                                                             На правах рукописи

 

 

 

 

 

 

 

НЫСАНБАЕВА САУЛЕ ЕРКЕБУЛАНОВНА

 

 

 

 

Разработка и исследование криптографических систем

на базе непозиционных полиномиальных систем счисления

 

 

 

05.13.01 - Системный анализ, управление и обработка информации

 

 

 

Автореферат

 

диссертации на соискание ученой степени

доктора технических наук

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Республика Казахстан

Алматы, 2009

 

 

Работа выполнена в Институте проблем информатики и управления  Министерства образования и науки Республики Казахстан

 

 

Научный консультант:         доктор технических наук,

                                                   профессор Бияшев Р.Г.

 

 

Официальные оппоненты:   доктор технических наук

                                                   Веселов Г.Е.

                                                   

                                                    доктор технических наук,

                                                    профессор Исмаилов Б.И.

                                                     

                                                    доктор технических наук,

                                                    профессор Бейсенби М.А.

 

 

Ведущая организация:         Институт математики Министерства

                                               образования и науки Республики Казахстан

 

 

 

Защита состоится 23 апреля 2009 г. в 15-00 часов на заседании  объединенного  диссертационного совета ОД 14.13.03 при Казахском национальном техническом университете  имени К. И. Сатпаева  Министерства образования и науки  Республики Казахстан по адресу:  Республика Казахстан, 050013, г. Алматы, ул. Сатпаева, 22, нефтяной корпус, конференц - зал.   

 

С диссертацией можно ознакомиться в библиотеке Казахского национального технического университета  имени К. И. Сатпаева

 

 

Автореферат  разослан   12  марта  2009 г.

 

 

 

 

 

Ученый секретарь объединенного

диссертационного совета ОД 14.13.03

доктор технических наук, профессор                                   Б.Х.. Айтчанов

 

 

 

Введение

 

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

Криптографические алгоритмы, созданные в 70–80–е гг. ХХ в., должны были удовлетворять требованиям по экономичности их реализации. В настоящее время возможности технической базы по реализации шифров возросли на несколько порядков по сравнению с возможностями их аппаратной реализации в 70-е и 80-е гг. прошлого века. В результате пропорционально увеличились и возможности их криптоанализа и, как следствие, существенно возросли требования к их криптостойкости, которые обусловили изменения в современных подходах к построению симметричных шифров с секретными ключами.

Первый стандарт шифрования данных DES (Data Encryption Standard),  основанный на принципе Керкхоффса (A.Kerckhoffs) в криптографии и построенный по схеме Фейстеля (H.Feistel) был принят в США в 1977 г. Он являлся наиболее распространенным алгоритмом, используемым в системах защиты коммерческой информации. Новый стандарт шифрования AES (Advanced Encryption Standard) объявлен в мае 2002 г. Его относят к нетрадиционным, поскольку он имеет архитектуру «квадрат», в которой производятся непосредственные преобразования, в том числе и алгебраические, над шифруемым блоком, представленным в форме матрицы байтов. В России действует  единый алгоритм ГОСТ 28147-89 блочного шифрования данных, определенный как одноименный стандарт шифрования.

Широкое внедрение беспроводной связи в информационных и телекоммуникационных системах и сетях обуславливает необходимость обеспечения информационной безопасности в режиме реального времени, что возможно при использовании эффективных поточных шифров, составным элементом которых являются генераторы псевдослучайных последовательностей (ПСП). Необходимость  в стойких поточных шифрах, обладающих качественными алгоритмами генерации  ПСП, свидетельствует    проект ECRYPT (2004–2008 гг.) – European Network of Excellence for Cryptology. В соответствии с ним проводился конкурс для поточных шифров  eSTREAMStream Cipher Proposals for Ongoing Analysis.

Актуальность темы исследования.

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

Республика Казахстан активно развивает государственную систему защиты информации и ее законодательно-правовую основу. Принятые нормативные документы подтверждают это, характеризуя актуальность  исследований диссертации: 1) Закон РК «О государственных секретах»; 2) Государственный стандарт на средства криптографической защиты информации СТ РК1073-2002; 3) Указ Президента Республики Казахстан «О развитии космической деятельности в Республике Казахстан на 2005-2007 годы», которым сформирована Государственная программа «Развитие космической деятельности в Республике Казахстан на 2005-2007 годы»; 4) Закон Республики Казахстан «Об информатизации»: глава 8 «Защита электронных информационных ресурсов и информационных систем». 

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

Цель исследований: разработка надежных и эффективных криптографических средств (алгоритмов шифрования, формирования ЭЦП, генерации и распространения ключей) для создания отечественной системы защиты информации и информационной безопасности, продекларированной Советом безопасности Республики Казахстан и сформулированной в главе 8 «Защита электронных информационных ресурсов и информационных систем» Закона Республики Казахстан «Об информатизации».

Достижение поставленной цели осуществляется путем:

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

-    построения алгоритма генерации псевдослучайных последовательностей и анализа его статистических свойств;

-    создания программных продуктов для предложенных нетрадиционных алгоритмов шифрования и построения 2–х схем электронных цифровых подписей.

Задачи исследования, осуществление которых позволило достичь поставленной цели:

-    разработать, исследовать и программно реализовать следующие нетрадиционные алгоритмы:

·        шифрования (зашифрования и расшифрования) электронного сообщения заданной длины;

·             формирования электронной цифровой подписи для электронного сообщения заданной длины по модулям  нескольких избыточных оснований (ЭЦП–1);

·             создания электронной цифровой подписи для электронного сообщения заданной длины по модулю одного избыточного основания (ЭЦП–2);

·        распространения секретных ключей;

-    провести анализ криптостойкости алгоритмов шифрования, формирования электронных цифровых подписей ЭЦП–1 и ЭЦП–2 и открытого обмена ключами, созданных на базе нетрадиционного подхода;

-    построить генератор ПСП и исследовать его статистическую безопасность.

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

Предмет исследования:

-    алгоритм шифрования электронного сообщения заданной длины, разработанный на базе модулярной арифметики и его криптостойкость;

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

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

-    предложенный алгоритм генерации ПСП и его статистические свойства;

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

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

Научная новизна полученных результатов состоит  в следующем: 

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

-    предложен, изучен и программно реализован новый нетрадиционный алгоритм формирования электронной цифровой подписи по модулям нескольких избыточных оснований для электронного сообщения заданной длины, который включает 3 этапа – формирование НПСС, хэширование (сжатие) сообщения путем вычисления вычетов по модулям введенных избыточных оснований; шифрование полученного хэш-значения;

-    разработан, исследован и программно реализован новый нетрадиционный алгоритм, в котором совмещены создание электронной цифровой подписи по модулю одного избыточного основания для электронного сообщения заданной длины и процесс обнаружения/исправления ошибок, формирование ЭЦП-2 состоит из трех этапов, при хэшировании вычисляются три избыточных вычета, составляющие ЭЦП–2 и использующиеся для обнаружения и коррекции одиночной ошибки и выявления многократной ошибки;

-    построен новый алгоритм генерации псевдослучайных последовательностей;

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

Положения, выносимые на защиту:

-    алгоритм шифрования (зашифрования и расшифрования) электронного сообщения заданной длины, разработанный на базе непозиционных полиномиальных систем счисления и данные анализа его криптостойкости;

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

-    алгоритм создания электронной цифровой подписи по модулю одного избыточного основания, построенный на основе непозиционных полиномиальных систем счисления, результаты исследования особенностей его построения и оценки его криптостойкости;

-    алгоритм генерации псевдослучайных последовательностей и результаты  оценки его качества;

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

Теоретическая и практическая значимость полученных результатов.

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

Практическая значимость полученных результатов заключается в:

-    разработке отечественных надежных нетрадиционных криптографических систем и построении статистически безопасного генератора псевдослучайных последовательностей;

  возможности  их использования для защиты данных при их хранении и передаче  в информационно-телекоммуникационных системах электронного правительства, электронного голосования, дистанционного обучения;

-    создании программ и комплексов программ, реализующих  вычисление неприводимых многочленов над полем GF(2) заданной степени, формирование полных криптографических ключей, нетрадиционные алгоритмы зашифрования и расшифрования электронных сообщений, формирования и проверки электронных цифровых подписей, на которые получены акт проверки и испытаний их макетных образцов и 6 свидетельств о государственной их регистрации как объектов интеллектуальной собственности Республики Казахстан.

Апробация работы. Результаты диссертационной  работы докладывались на научных семинарах лаборатории информационной безопасности, 2-й Международной научно-практической конференции «Состояние, проблемы и перспективы информатизации в РК»  (26-30 сент.  2005 г., Республика Казахстан, г. Усть-Каменогорск); VIII, IX и Х Международной научно-практической конференции «Информационная  безопасность»  (3-7 июля 2006 г., 3-7 июля 2007 г. и 24-27 июня 2008 г., Россия, г. Таганрог); 6–й и 7–й Международной конференции «Информационные технологии и безопасность» (19–23 окт. 2006 г. и  27 сент. –2 окт. 2007 г., Украина, Крым, п.г.т. Партенит); IV Международной научной конференции «Проблемы дифференциальных уравнений, анализа и алгебры» (Республика Казахстан, г. Актобе, 18-21 окт. 2006 г.); Юбилейной Международной научно-технической конференции «50 лет модулярной арифметики» (в рамках V Международной научно-технической конференции «Электроника и информатика – 2005»). 23-25 нояб. 2006 г., Россия, Зеленоград); Международной конференции «Автоматизация и управление, перспективы, проблемы и решения» (15-18 янв. 2007 г., Республика Казахстан,  Алматы); XI Международной конференции «Комплексная защита информации» (20-23 марта 2007 года, Республика Беларусь, Новополоцк); Международной конференции, посвященной итогам выполнения Государственной программы «Развитие космической деятельности в Республике Казахстан на 2005 – 2007 годы» (27–28 сент. 2007 г., Республика Казахстан, г. Алматы); 3–й Международной научно-технической конференции «Инфокоммуникационные  технологии в науке, производстве и образовании» (1-5 мая 2008 г., Россия, г. Ставрополь), Международной научной конференции «Современные проблемы математики, информатики и управления», посвященной  60-летию д.ф.-м.н., проф. М.Б. Айдарханова (2– 3 окт. 2008 г., г. Алматы).

Связь   темы   с   планами   научно-исследовательских   программ.

Диссертационная работа выполнялась в соответствии с планами научных и прикладных работ лаборатории информационной безопасности  Института проблем информатики и управления МОН РК в рамках тем следующих программ научных исследований МОН РК:

1. «Разработка технологий по информационной безопасности (криптографическая защита информации на основе нетрадиционных подходов)», № госрегистрации 0103РК00120, программы фундаментальных исследований  «Разработка фундаментальных основ принятия решений, языков спецификаций, биокомпьютерного моделирования, управления сложными объектами для создания безопасных и эффективных информационных систем (ПФИ, 2003-2005 гг., шифр Ф.0266);

2. «Разработка и исследование технологий защиты информации, базирующихся на модулярной арифметике», № госрегистрации 0106РК00524, программы фундаментальных исследований «Разработка и исследование моделей, методов и алгоритмов создания защищенных и интеллектуальных информационных технологий» (ПФИ, 2006-2008 гг., шифр Ф.0369-8);

3. «Разработка технологических основ создания и применения спутниковых информационно-телекоммуникационных систем и обеспечения их безопасности» (№ госрегистрации 0105РК00189) Государственной программы «Развитие космической деятельности в Республике Казахстан на 2005-2007 годы».

Публикации. Результаты исследований представлены в 40 работах, из которых  6 – авторские свидетельства  об интеллектуальной собственности на разработанные программные продукты. 

Структура и объем диссертации. Работа изложена  на 240 страницах, состоит из введения, 4 разделов, заключения, списка использованных источников из 110 наименований и 3 приложений.

 

Основная часть

 

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

В первом разделе приводятся результаты, полученные при разработке и исследовании алгоритма шифрования с использованием непозиционных полиномиальных систем счисления. В классических системах остаточных классов (СОК) целые положительные числа  представляются в виде набора остатков (вычетов), полученных от их деления на основания СОК. В соответствии с Великой китайской теоремы об остатках представление числа в виде последовательности вычетов будет единственным, если основания будут попарно просты между собой. В отличие от них предлагаемый алгоритм создается в полиномиальных системах счисления в остаточных классах, в которых основаниями служат неприводимые многочлены над полем GF(2). Тогда полиномы с двоичными коэффициентами можно также представить в виде последовательности вычетов, полученных в результате их деления  на выбранную систему полиномиальных оснований.

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

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

1. Пусть     неприводимые многочлены, выбранные в качестве рабочих оснований НПСС. Многочлен  степени  является основным рабочим диапазоном НПСС. В этой системе любой многочлен, степени меньше m, имеет единственное представление в виде его вычетов по модулям рабочих оснований  соответственно. Тогда сообщение длины N бит можно интерпретировать  как последовательность  остатков  от деления некоторого многочлена F(x) на рабочие основания соответственно:   , где , . Остатки  выбираются так, чтобы первым  битам сообщения соответствовали двоичные коэффициенты остатка , следующим  битам – двоичные коэффициенты остатка  и так далее,  последним  двоичным разрядам – двоичные коэффициенты вычета .

2. Используемая ключевая последовательность длины N бит также интерпретируется  как последовательность  остатков , но от деления некоторого другого многочлена G(x) по тем же рабочим основаниям системы: , где , .

Тогда в качестве криптограммы  может рассматриваться некоторая функция зашифрования H(F(x),G(x)):  , где , .

В соответствии с операциями непозиционной системы счисления операции в функциях F(x), G(x), H(x) выполняются параллельно по модулям полиномов  , выбранных в качестве оснований НПСС. Восстановление позиционного представления F(x) производится по его  непозиционному виду. В случае хранения, передачи и обработки информации оно осуществляется по формуле: 

                 , ,  ,        (1)

где значения многочленов Мi (x) выбираются для выполнения указанного в формуле сравнения. Для хранимой и передаваемой информации восстановление происходит по выражению:

                                         ,    ,  .                       (2)

Полным ключом в этом алгоритме является многочлен G(x) и конкретный набор оснований, выбранных из всего множества неприводимых многочленов степени не выше значения N. Выбор всех систем рабочих оснований степени от  до  производится при  условии выполнения  уравнения

                                                                  ,                                                    (3)

где  - неизвестные коэффициенты и число выбранных неприводимых многочленов степени , один конкретный набор этих коэффициентов является одним из решений (3) и задает одну систему рабочих оснований;  - количество всех неприводимых многочленов степени , ,  - число  выбранных оснований. Уравнение (3) определяет то количество S оснований,  вычеты по которым покрывают длину сообщения, все эти основания  должны быть различными, даже если они являются полиномами одной степени. С ростом порядка неприводимых многочленов их количество быстро увеличивается: так для многочленов степени 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 и 16 их количество соответственно равно 1, 1, 2, 3, 6, 9, 18, 30, 56, 120, 240, 488, 972, 1936, 3876 и  7749.  Поэтому   уравнение (3) имеет достаточно широкий выбор решений. Для определения количества всех неприводимых полиномов заданной степени над полем  разработана программа «NeprivodPolinom» на Delphi 6, зарегистрированная как объект интеллектуальной собственности Комитетом по правам интеллектуальной собственности Министерства юстиции Республики Казахстан (КИС МЮ РК).

Исследована криптостойкость нетрадиционного алгоритма шифрования.

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

Для доказательства этого рассчитывается число комбинаций выбора оснований для каждой степени оснований, определяемых равенством (3). Тогда с учетом перестановок оснований  число комбинаций формирования системы из S выбранных оснований конкретных степеней  будет определяться  выражением:   

                                       f = .                           (4)

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

 

                        ),             (5)

в котором суммирование распространено на всевозможные комбинации коэффициентов , удовлетворяющих    равенству (3).Определенные по формуле (5) значения криптостойкости шифрования показали, что увеличение длины от N=1 до N =16 бит, т. е. на один порядок,  надежность шифрования возрастает на 9 порядков. Таким образом, надежность предложенного алгоритма существенно возрастает с увеличением длины сообщения, а следовательно и с ростом степени оснований (таблица 1).

Рассмотрено также влияние на криптостойкость шифрования систем  оснований только одной степени или только разных степеней. Криптостойкость системы в общем случае (4)-(5) выше, чем в частных, так как возможностей выбора оснований различных степеней больше.

В государственном стандарте Республики Казахстан СТ РК 1073-2002 на средства криптографической защиты информации установлены  четыре уровня безопасности, согласно которым длина ключа реализуемых СКЗИ симметричных алгоритмов криптографического преобразования должна быть не менее 56, 112, 168 и 256 бит соответственно. Показано, что криптостойкость нетрадиционного алгоритма шифрования для минимальных длин ключей  СТ РК 1073-2002 может быть выше  на десятки порядков при существенно меньших длинах ключа.

Определено возможное количество вариантов выбора различных между собой систем оснований НПСС (формула (4)) из числа всех неприводимых многочленов, которые используются  для шифрования сообщения длины N от 1 до 16 бит. Начиная с N=4, увеличение длины сообщения на 1 бит ведет к возрастанию числа возможных  вариантов более чем в 2 раза.

Осуществлена программная реализация предложенного нетрадиционного алгоритма шифрования на Delphi 6, проведенная в два этапа.

На первом этапе создан комплекс «Ciphering/Deciphering» из 4–х программ,  в которых были апробированы процедура генерации полного ключа, алгоритм и метод симметричного зашифрования для хранимых и передаваемых сообщений заданной длины, вычисления инверсного ключа и расшифрования криптограммы. Комплекс создан в соответствии с планом работ на 2006 г.  по заданию  «Разработка технологических основ создания и применения спутниковых информационно-телекоммуникационных систем и обеспечения их безопасности» Государственной программы «Развитие космической деятельности в Республике Казахстан на 2005-2007 годы».

 

Таблица 1 - Криптостойкость нетрадиционных алгоритмов шифрования, формирования ЭЦП и   распространения секретных ключей

Длина  сообщения (блока) или секретного ключа обмена

 

 

1

 

 

2

 

 

3

 

 

4

 

 

5

 

 

6

 

 

7

 

 

8

 

 

9

 

 

10

 

 

11

 

 

12

 

 

13

 

 

14

 

 

15

 

 

16

Алгоритм

шифрования,

формула (5)

5,0·10-1

2,5·10-1

3,1·10-2

7,8·10-3

2,0·10-3

3,8·10-4

9,3·10-5

2,0·10-5

4,5·10-6

9,1·10-7

2,1·10-7

4,8·10-8

1,0·10-8

2,4·10-9

4,8·10-10

1,1·10-10

Алгоритм

ЭЦП– 1,

формула

(11)

5,0·10-1-5,0·10-1

5,0·10-1-0,3·10-1

1,3·10-1-2,0·10-3

6,3·10-2-1,2·10-4

3,1·10-2-7,6·10-6

1,2·10-2-2,3·10-7

6,0·10-3-1,3*·10-8

2,6·10-3-5,5·10-10

1,2·10-3-2,5·10-11

4,9·10-4-9,1·10-13

2,2·10-4-4,0·10-14

9,6·10-5-1,7·10-15

4,1·10-5-6,9·10-17

2,0·10-5-4,0·10-18

7,9·10-6-1,2·10-19

3,6·10-6-5,6·10-21

Алгоритм

ЭЦП– 2, формула (20)

 

 

-

 

 

-

 

 

 

-

 

 

-

 

 

-

 

 

-

 

 

-

 

 

-

 

 

-

 

 

-

 

 

-

6,0·10-8

2,5·10-8

4,5·10-11

3,7·10-11

3,7·10-13

Алгоритм открытого обмена ключами, формула (22)

 

 

2,1 ·10-1

1,4 ·10-2

1,0 ·10-3

1,7 · 10-4

2,4 ·10-5

2,4 ·10-6

3,2 ·10-7

3,4 ·10-8

3,9 ·10-9

3,4 ·10-10

4,8 ·10-11

4,7 ·10-12

6,5 ·10-13

6,7 ·10-14

7,1 ·10-15

 

На втором этапе по плану работ вышеуказанного задания на 2007 г. были отдельно решены задачи генерации полных секретных ключей и блочного симметричного шифрования (зашифрования и расшифрования). Тогда за  шифруемый блок длиной N бит принимается сообщение заданной длины N бит. Вначале была разработана программа «Keysgener» для генерации полных криптографических ключей, их хранения в  базе данных ключей и удаления из БД. Эти полные ключи предназначены для использования в программных реализациях  шифрования и  систем ЭЦП. Затем был создан программный комплекс «Shifr/RasShifr» из трех программ: 1) «KeyCase» выбирает ключи для блочного симметричного зашифрования и расшифрования из БД полных ключей; 2) «Shifr» зашифровывает открытое сообщение произвольной длины по блокам; 3) «RasShifr» по блокам расшифровывает криптограмму.

На программные продукты «Ciphering/Deciphering», «Keysgener» и «Shifr/RasShifr»  получены авторские свидетельства , выданные  КИС МЮ РК.

Сравнение предложенного нетрадиционного алгоритма шифрования со стандартом  AES выявило преимущество предложенного алгоритма в криптостойкости на десятки и сотни порядков в зависимости от длины ключа.

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

Второй раздел посвящен разработанному алгоритму формирования ЭЦП по модулям нескольких избыточных полиномиальных оснований длины  для подписываемого сообщения длины N (<<N). Алгоритм состоит из трех взаимосвязанных блоков: 1) восстановления функции F(x): для этого выбирается система рабочих оснований для сообщения длины N с учетом  порядка их расположения; 2) хэширования сообщения длины N до длины  путем  введения системы избыточных оснований, в которой также важно их расположение; 3) шифрования хэш-значения: выбор системы оснований для шифрования и их размещения, генерации ключевой последовательности.

Первый этап. Процедура построения НПСС описана в 1– м разделе.

Второй этап. Хэширование (сжатие) сообщения от длины N до длины  производится путем расширения НПСС на избыточные (дополнительные) основания , которые выбираются произвольно  из всех неприводимых многочленов степени не выше . Эта система оснований формируется независимо от выбора рабочих оснований  , но в данном алгоритме среди  избыточных оснований могут быть и совпадающие с некоторыми из рабочих. Затем вычисляются дополнительные вычеты   от деления восстановленного многочлена F(x) на дополнительные основания. Тогда хэш–значение интерпретируется как последовательность этих вычетов: ,  где  , . В сумме длины избыточных вычетов  составляют длину хэш-значения.

Третий этап. Для шифрования полученного хэш-значения используется предложенный алгоритм шифрования на базе НПСС. Для этого выбирается система оснований  из числа неприводимых многочленов с двоичными коэффициентами степени не выше . В состав оснований  могут попасть  некоторые многочлены как из рабочих оснований , так и из избыточных . Тогда хэш-значение длины  интерпретируется как последовательность остатков  от деления некоторого многочлена F1(x) на выбранные основания  соответственно: , где , .

 Затем генерируется ключ длины , интерпретируемый как последовательность остатков   от деления некоторого полинома G1(x) на те же  основания :                                              ,  , .

Полученная в результате шифрования криптограмма  может быть представлена как некоторая функция H1(F1(x),G1(x)):                                            ,  , .

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

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

В связи с этим при выводе формулы криптостойкости процедуры формирования ЭЦП определяются все возможные способы формирования оснований на каждом этапе.

На первом этапе общее число различных систем из S оснований конкретных степеней   будет определяться так же, как в выражении (4):

                                       Z1 = .                        (6)

Второй этап. Степени и число неприводимых многочленов, используемых при выборе избыточных оснований, обозначаются, как  и   соответственно. Число выбранных избыточных оснований из БД неприводимых многочленов различных степеней в этом случае определяется из аналога уравнения (3) , где - число выбранных дополнительных оснований степени , , ,  число выбранных дополнительных оснований системы, запись вычетов по которым покрывает хэш-значение длины  . Всевозможные варианты выбора таких систем избыточных оснований определяются выражением:

                                      ,                             (7)

где суммирование распространено на всевозможные комбинации выбора систем дополнительных оснований степени не больше .

Вычеты  вычисляются по восстановленной функции F(x), вследствие этого все варианты выбора систем из U дополнительных оснований будут получены при совместном осуществлении операций выбора систем  S рабочих и U избыточных оснований, т. е.  из произведения выражений (6) и (7):

      .   (8)

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

                                               .                                  (9)

В уравнении (9): ,    неизвестные коэффициенты или число выбранных оснований степени , , . Для всех вариантов выбора систем из W оснований и ключевой последовательности получим  выражение:

                             2.                   (10)

Тогда криптостойкость формирования ЭЦП находится из  выражения:

                 = 1/[2((

                            )                                 (11)

                         )],

где внешнее суммирование распространено на все возможные выборы систем S рабочих оснований из числа неприводимых полиномов с двоичными коэффициентами степени не выше значения N.

По формуле (11) рассчитаны криптостойкости ЭЦП-1 в зависимости  от длины подписываемого сообщения: от  N=1 бит до N=16 бит.  При этом длина ЭЦП задавалась от =1 бит до =N бит с  интервалом 1 бит. В связи с этим для подписываемого сообщения заданной длины получен диапазон изменения значений криптостойкости ЭЦП (таблица 1). Например, для N=16 бит этот диапазон составляет . В частности,  при длине ЭЦП, равной 6 бит (=6),  ее криптостойкость  равна  6,7·10-11, а при увеличении длины подписываемого сообщения на 10 бит (=16), криптостойкость цифровой подписи равна , т. е. увеличение – на 10 порядков.  Эти данные свидетельствуют о высокой надежности нетрадиционного алгоритма

Полученные результаты показывают, что предлагаемый нетрадиционный   алгоритм формирования ЭЦП позволяет создавать их значительно меньшей длины, по сравнению с той длиной, которая указана в СТ РК 1073-2002, при сохранении, а при необходимости и увеличения ее криптостойкости.

Проведен также анализ влияния состава полиномиальных оснований на  криптостойкость  цифровой подписи, поскольку надежность ЭЦП зависит от составов и сочетания систем оснований на всех  этапах ее формирования.

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

Осуществлена программная реализация алгоритма в виде комплекса  «EDS1/CheckEDS1» из трех программ: 1) «KeyCaseEDS1» производит выбор полного  ключа из базы данных;  2) «EDS1» формирует ЭЦП для сообщения произвольной длины;  3) «CheckEDS1» проверяет  правильность ЭЦП. На комплекс получено авторское свидетельство, выданное  КИС МЮ РК.

В третьем разделе представлен второй разработанный нетрадиционный алгоритм формирования системы ЭЦП–2.  В отличие от первого алгоритма формирования ЭЦП–1, в нем вводится одно избыточное основание и совмещены функции формирования ЭЦП и обнаружения/исправления ошибок.

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

                                             ,                                   (12) 

где здесь и далее знак    означает сложение по модулю 2,   - вычет от деления  произведения  на  избыточное основание  (или вычет по модулю ). Второй дополнительный вычет определяется, как сумма всех рабочих вычетов поразрядно  по модулю 2:

                                                     .                                         (13)

Третий  избыточный вычет вычисляется по модулю дополнительного основания от позиционного представления многочлена F(x) по формуле:

                                                .                             (14)

Расширение многочлена , в виде которого интерпретируется электронное сообщение, на  избыточные вычеты   будет иметь вид: . При наличии одной ошибки в рабочих вычетах (например, по -му основанию ) избыточные вычеты (12) - (14) изменят свои значения на , , . Ошибкой является любое искажение вычета  по модулю рабочего основания , и ее величина  может быть равна любому элементу из полной  системы вычетов по модулю , . Тогда  представится в виде  , где искаженный вычет принадлежит полной системе вычетов по модулю полинома .

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

             ,  ,       (15)

Введя обозначения для невязок: ,   и вычитая (12) и (13) соответственно из первого и второго уравнений (15), получим 

                                           ,  .                                 (16)

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

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

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

Утверждение 3. Каждой ошибке  соответствует одна пара невязок .

Утверждение 4. Каждой паре невязок  соответствует одна ошибка  .

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

Утверждение 5. Выбор избыточного основания зависит от используемой системы полиномиальных рабочих оснований и их количества.

Показывается правильность утверждения 5 и определены условия выбора степени избыточного основания  в общем случае:

                                                          .                                       (17)

Неравенство (17)  характеризует  зависимость  от наибольшей и наименьшей степени конкретной системы рабочих оснований и их количества S. Рассмотрены также некоторые частные случаи выбора дополнительного основания.

Утверждение 6. Степень избыточного основания должна быть не меньше наибольшей степени рабочих оснований.

Это утверждение определяет еще одно условие выбора избыточного основания: число элементов полной системы вычетов по модулю избыточного основания  не должно быть меньше количества элементов полной системы вычетов по модулю рабочего основания :

                                                             .                                               (18)

Таким образом, выбираемое избыточное основание должно удовлетворять  налагаемым на него двум условиям  (17) и (18).

Рассмотрены также возможные варианты ошибок по контрольным вычетам.

Длина ЭЦП должна быть существенно меньше длины N электронного сообщения, т. е. . В рассматриваемом алгоритме длина  ограничена условием: , тогда степень избыточного вычета определяется неравенством   , откуда следует более сильное ограничение на длину ЭЦП–2 и степень :

                                                       .                                    (19)

Утверждение 7. Криптостойкость  нетрадиционного алгоритма формирования ЭЦП по модулю одного избыточного основания определяется числом всевозможных способов выбора оснований на всех этапах алгоритма формирования ЭЦП: системы рабочих оснований из множества неприводимых многочленов степени не выше N, избыточного основания из множества неприводимых многочленов степени не выше  с учетом всех ограничений на его выбор и полного ключа для шифрования хэш-значения длиной .

Существует конкретное количество всех возможных  систем рабочих оснований, покрывающих подписываемое сообщение длиной N и используемых для формирования ЭЦП-2. В каждой  из этих систем рабочих оснований имеется свое конкретное наибольшее  значение их степени. Поэтому  при подписывании сообщения длины N степень  принимает значения из конкретного диапазона возможных  наибольших степеней. Тогда, как следует из вышеизложенного, по описанному алгоритму может быть сформировано несколько ЭЦП с различными длинами , k=1,2,…,K, где K – число всех цифровых подписей, которые могут быть получены для сообщения  заданной длины N. Надежность полученных подписей определяется числом всевозможных способов выбора оснований на всех этапах алгоритма формирования ЭЦП-2. Формула для определения  криптостойкости выводится так же, как и в аналогичной процедуре алгоритма формирования ЭЦП–1. Здесь:

Z1 = .

Количество способов выбора одного избыточного основания   равно  числу  всех неприводимых многочленов  степени  :

                                                       Z2 = .    

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

На этапе шифрования хэш-значения получим:

                        Z3 = .  

Для одной системы рабочих оснований при конкретных значениях    и  все  способы формирования проверяющей подписи  будут  определяться произведением  Z1Z2Z3. Тогда всевозможные варианты формирования ЭЦП длины  должны учитывать все системы рабочих оснований, определяемых уравнением (3), т. е. описываться формулой: Z1 Z2 Z3 .  Все же способы формирования ЭЦП  с проверяющими функциями для сообщения одной определенной длины N есть сумма всех :                                                        Y =  . Тогда криптостойкость ЭЦП-2 описывается выражением:

                = 1/ [ (

                             *)].                  (20)

Таким образом, в нетрадиционном алгоритме формирования ЭЦП–2 длина и надежность цифровой подписи определяются длиной подписываемого сообщения и выбором систем оснований на каждом этапе с учетом всех условий выбора избыточного основания (17)–(19) (таблица 1).  Криптостойкость ЭЦП–2 может быть достаточно высокой, но по надежности этот алгоритм уступает нетрадиционной процедуре создания ЭЦП–1

Создан программный комплекс «EDS2/CheckEDS2» из двух программ: формирования ЭЦП для сообщения заданной длины  «EDS2»  и проверки  ЭЦП «CheckEDS2», реализующих алгоритм формирования ЭЦП–2 для сообщения заданной длины. На этот комплекс получено авторское свидетельство, выданное  КИС МЮ РК

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

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

Cуть предлагаемого алгоритма генерации (построения) псевдослучайных последовательностей состоит в следующем. На первом этапе задаются два числа  и  и находится их произведение . Затем из  вырезается заданное количество любых подряд идущих разрядов, сохраняющиеся как первый элемент (вырезка) генерируемой последовательности . После этого  умножается на В и из результата второго произведения  аналогично  вырезается второй элемент  . Итог этого этапа – генерация начальных элементов последовательности {}. На втором этапе –  умножается на , из полученного произведения  вырезается по аналогии с первым этапом элемент . Затем находится произведение чисел   и , из результата которого  вырезается элемент . Таким образом, после второго этапа получаются следующие два элемента последовательности:  . На последующих этапах генерации элементов формируется последовательность  заданной  длины.

При компьютерном моделировании исследовалось влияние значений чисел  и В, места расположения вырезок и длины (количество элементов или вырезок) генерируемой последовательности на качество генератора. Исследовались последовательности, сформированные из элементов по 8 бит 3-х видов в зависимости от места их вырезания – в начале, в центре и в конце результата умножения. Поэтому эти вырезки  назвали соответственно «первая слева», «в центре» и «последняя справа». Проверялись последовательности длиною из 10000 и 100000 элементов, сгенерированные для 14 вариантов  значений чисел А и В  (таблица 2.)

Анализ качества генерируемых последовательностей проводилось в два этапа. Вначале осуществлялась генерация ПСП c проверкой  на периодичность. В случае отсутствия периода проводился анализ статистической безопасности последовательности по 5 графическим тестам – «Гистограмма распределения элементов», «Распределение на плоскости», «Проверка серий», «Проверка на монотонность», «Автокорреляционная функция», и 4 оценочным тестам –  «Проверка несцепленных серий»,  «Частотный тест», «Проверка частот», «Проверка дырок».

 

  Таблица 2 – Варианты значений чисел А и В

Номер

варианта

Значения

чисел А и В

Номер

варианта

Значения

чисел А и В

1

8

А=222, В= 777

2

А=521, В=1279

9

А=777, В=222

3

А=555, В= 333

10

А=333, В= 777

4

А=1978, В=2007

11

5

А=248, В= 256

12

6

13

7

14

 

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

В совместных работах с Н.А.Капаловой анализ статистических свойств был проведен при значениях  чисел А и В вариантов 1–5 для  последовательностей длиной также и в 1000 и 1000000 элементов по указанным  оценочным и первым 3–м графическим тестам.

Тест «Гистограмма распределения элементов» оценивает равномерность распределения символов и определяет частоту появления конкретного символа. В сгенерированной последовательности подсчитывается число появлений  элементов и строится график его зависимости от численного представления элемента. Последовательность удовлетворяет свойствам случайности, если присутствуют все возможные элементы рассматриваемой разрядности, а разброс частот появления символов стремится к нулю.

На рисунке 1 представлены результаты тестирования для вариантов 2 (I) и 6 (II) значений чисел А и В для последовательностей из 100000 элементов, построенных  из вырезок «первая слева», «в центре» и «последняя справа» (соответственно варианты а, б и в).

На графиках рисунка 1,а (вырезка – «первая слева») видно, что элементы расположены  неравномерно. Гистограмма варианта 6 величин А и В имеет «ступенчатый» вид.  На первом участке разброс растет, а значения частот уменьшаются. На втором – частота резко возрастает вначале, а потом также уменьшается. На третьем участке значения частот почти выравниваются,  но их значения меньше, чем на первых участках. Для варианта 2 график гистограммы имеет более «пологий» вид. Эти гистограммы отражают особенности распределения элементов в графиках других вариантов чисел А и В.

В гистограммах последовательностей, сформированных из вырезок «в центре» и  «последняя справа», значительно равномерней частота появления элементов. Небольшое уменьшение значений частот наблюдается для некоторых последовательностей из элементов «в центре» в самом конце графиков (рис. 1,б), которое отсутствует в гистограммах последовательностей из элементов «последняя справа» (рис. 1,в). Наименьший разброс частоты появления элементов «в центре» наблюдается у вариантов 1 и 6 чисел А и В, а наибольший –  у вариантов 2 и 9.

Характерные особенности гистограмм по всем вариантам 1-14 проявляются уже и при меньших длинах  в  10000 элементов.  Лучшими являются результаты тестирования последовательностей, сформированных из вырезок «в центре» и «последняя справа».

 

Рисунок 1 - Результаты анализа по тесту «Гистограмма распределения элементов»: варианты – 2 (I) и 6(II), длина ПСП    100000 элементов,

 вырезки –  а) «первая слева; б) «в центре»;  в) «последняя справа»

Тест «Распределение на плоскости» предназначен для определения зависимостей между элементами последовательности. На плоскости (поле) размером , где - разрядность элемента последовательности, наносятся точки с координатами , где , n - длина последовательности. Если между элементами отсутствуют зависимости, то точки по всему полю расположены хаотично (равномерно), т. е., можно сказать, что получена ПСП. В противном случае на поле точки расположены неравномерно или образуют  «узоры».

Этот тест выявил аналогичные особенности влияния на качество сгенерированных последовательностей всех параметров. Для последовательностей, сформированных из вырезок «первая слева», наблюдаются более разреженное распределение точек в верхнем правом углу на плоскости их распределения. Чем длиннее последовательность, тем плотней точки покрывают плоскость – для длины 100000 элементов поле может оказаться практически черным. Характерное распределение элементов на плоскости наблюдается также уже при длине 10000 элементов. Более равномерным распределением отличаются последовательности, генерируемые по вырезке  «в центре» и правее нее.

Тест «Проверка серий» оценивает равномерность распределения символов на основе анализа частоты появления нулей и единиц, и серий, состоящих из k бит. Подсчитывается, сколько раз встречаются нули и  единицы (k=1), серии-двойки (00, 01, 10, 11: k=2), серии-тройки (000, 001, 010, 011, 100, 101, 110, 111: k=3) и т.д. В последовательностях, статистические свойства которых близки к свойствам случайной последовательности, разбросы между числом появлений нулей и единиц, между числом появлений различных серий каждого вида, должны стремиться к нулю. Последовательность исследуется в битовом виде. При k=8 графики серий совпадают с графиками теста «Гистограмма распределения элементов».

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

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

На рисунке 2 представлены графики, построенные для последовательностей из 100000 элементов «первая слева», «в центре» и «последняя справа» для  вариантов 1 (I) и 6 (II) значений  чисел А и В. (На плоскости графиков приведена также координатная сетка для оси абсцисс).

 

Рисунок 2 - Результаты анализа по тесту «Проверка на монотонность»:

варианты – 2 (I) и 6 (II),  длина ПСП – 100000 элементов,

вырезки –  а) «первая слева; б) «в центре»;  в) «последняя справа»

 

В варианте 1 (рис. 1,а) для последовательности, построенной из вырезок «первая слева», основная часть участков невозрастания (неубывания)  имеет длину от 5 до 8 бит. На графике можно выделить 2 зоны. В первой зоне от начала осей координат имеются участки длиной из 4, 10, 11, 12 и 13 бит. Во второй зоне, примерно от 20000 на горизонтальной оси,  равномерно расположены участки от 5 до 10 бит. В этой последовательности длиннее участки, поэтому их общее количество меньше, чем у других на рисунке 1. На рисунках 1,б и 1,в  большая часть участков имеет длину от 4 до 6 для вырезок «в центре» и от 4 до 5 бит для вырезок «последняя справа». Здесь также выделяются две зоны участков. В первой зоне  для вырезок «в центре» есть участки из 3 и 8 бит, а для вырезок «последняя справа» – из 3 и 7 бит. Как видно, по всем вырезкам сохраняется характер распределения участков.

У варианта 6 значений  чисел А и В  основная часть участков невозрастания и неубывания для вырезок «первая слева» имеет длину от 4 до 5 бит. Имеются участки длиной из 3 и 7 бит. В последовательностях, сформированных из вырезок «в центре» и  «последняя справа», длина у большей части участков меняется от 4 до 6 бит. На рисунке 1,б  присутствуют участки длиной 3 и 7 бит, а на рисунке 1,в – из 3, 7 и 8 бит. В этом варианте выполняется правило: чем больше длина участка невозрастания (неубывания), тем реже он встречается. Но для последовательностей, построенных из вырезок «в центре» и  «последняя справа», такие участки встречаются чаще и равномерней.

Исследование качества других вариантов для А и В по этому тесту  также подтвердило результаты анализа по предыдущим графическим тестам.

Тест «Автокорреляционная функция» (АКФ) проверяет наличие корреляции между сдвинутыми копиями исследуемой последовательности и обнаруживает зависимость между ее подпоследовательностями в битовом и символьном виде.

В битовой АКФ исследуемая последовательность в битовом виде нормируется: вместо “0” записывается  “– 1”, а “1” остается “1” и вычисляются всплески корреляции:  , где n и  – длина и элементы нормированной последовательности, . При формировании символьной АКФ исследуемая последовательность также нормируется: элементы последовательности записывается в двоичном виде , где R – их разрядность. Тогда  нормированное значение элемента представляется в виде . Затем вычисляются всплески корреляции по указанной выше формуле. Значения всплесков корреляции должны стремиться к нулю во всех точках, кроме тех, чьи значения кратно длине последовательности  в символах для символьной АКФ и в битах для битовой АКФ. Значительные всплески свидетельствуют о зависимости элементов последовательности.

Графики последовательностей, построенных из 10000 элементов «первая слева», «в центре» и «последняя справа», приведены на рисунке 3 для  вариантов 2 (I) и 6 (II) значений  чисел А и В.

Для варианта 2 величин А и В всплески корреляции в последовательности, построенной из вырезок «первая слева», принимают значения из интервала чисел , из вырезок «в центре» – в интервале чисел ,  из вырезок «последняя справа» – в интервале . В этом случае лучший результат получен для последовательностей, составленных из вырезок «первая слева» и «последняя справа».

Для варианта 6 для последовательности, сгенерированной из вырезок «первая слева», значения всплесков корреляции находятся в интервале чисел , из вырезок «в центре» –  в интервале , из вырезок «последняя справа» – в  интервале . Для этого варианта по всем трем последовательностям результаты тестирования являются положительными. Графики других вариантов величин А и В, а также битовых  АКФ показали, что символьная АКФ более «чувствительна» к качеству последовательностей и всплески корреляции малы для последовательностей, сформированных из вырезок «в центре» и  «последняя справа».

 

Рисунок 3 –  Результаты анализа по тесту «Автокорреляционная функция»:

варианты – 2(I)  и  6(II), длина ПСП    10000 элементов,  символьная,

вырезки –  а) «первая слева»; б) «в центре»;  в) «последняя справа»

 

По графическим тестам выявлены общие особенности влияния параметров на качество последовательностей: оценку статистических свойств можно проводить по небольшой длине из 10000 элементов, от значений чисел А и В зависит качество последовательностей; построение последовательностей необходимо производить из элементов, вырезаемых «в центре» и правее них.

Для оценки статистических свойств по оценочным тестам были выбраны по два теста из набора Д. Кнута и руководства НИСТ. Исследование проводилось для последовательностей длиной в 10000 элементов (или 80000 бит) по вышеуказанным в таблице 14 вариантам значений чисел А и В, сформированных из вырезок «первая слева», «в центре» и «последняя справа».

По  тесту  «Проверка несцепленных серий»        (Д.Кнут) исследуются на случайность последовательности  длины n: в них анализируются несцепленные (непересекающиеся) серии различной длины m. Подсчитывается число появлений  всевозможных несцепленных таких серий (последние лишние биты отбрасываются) и вычисляется статистика:

.

 

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

Результаты тестирования для последовательностей, сформированных из вырезок «первая слева», являются отрицательными. Для последовательностей, сформированных из вырезок «в центре», результаты являются положительными для 8 вариантов 1,3–6, 8, 10 и 13. Тестирование для последовательностей, сформированных из вырезок «последняя справа», являются положительными результаты для 10 вариантов 1, 5–7 и 9–14 значений чисел А и В. Самый низкий результат для последовательностей, составленных из вырезок «в центре» и «последняя справа», получен для варианта 2. По всем сериям прошли тест по вырезкам «в центре» и «последняя справа»  варианты 1, 5, 6, 10 и 13 .

По «Частотному  тесту» (НИСТ) проверяется равномерность появления 0 и 1 в сгенерированной последовательности в двоичном виде  длины n. Вычисляется разница между числом появления единиц  и нулей :  . Вначале вычисляется статистика:    и находится значение . Значение  должно быть больше 0,01. Полученные величины  и  приведены в таблице 3. 

Для последовательностей, сформированных из вырезок «первая слева», получены отрицательные значения ,  из вырезок «в центре» –  положительные значения получены в 11 вариантах 1,3, 5–8  и 10–14, из вырезок «последняя справа»    13 вариантов прошли тест за исключением варианта 2. Как и в предыдущем тесте, наименьшими статистическими показателями  обладают последовательности, составленные из вырезок «в центре» и «последняя справа», для варианта 2 значений чисел А и В. Лучшие показатели по вырезкам «в центре» и «последняя справа»  показали 11 вариантов 1, 3, 5–8, 10–14 значений чисел А и В.

 

Таблица 3 –  «Частотный тест»,   длина ПСП –  10000 элементов

Номер

варианта

Вырезки

«первая слева»

 

«в центре» 

«последняя справа» 

P

P

P

1

3188

-7,4E36

2

0.994

112

0,692

2

3882

-1,7E41

1190

0.000

596

-0,990

3

3158

-5,4E36

480

0.090

70

0,805

4

3404

-2,1E38

836

0.003

46

0,871

5

3528

-1,3E39

176

0.534

112

0,692

6

3636

-6,0E39

142

0,616

152

0,591

7

3476

-6,1E38

88

0,756

66

0,816

8

3454

-4,4E38

210

0,458

144

0,611

9

3342

-8,2E37

764

– 250961,4

156

0,5811

10

2922

-8,8E34

166

0,557

178

0,5291

11

3300

-4,3E37

96

0,734

200

0,480

12

3370

-1,3E38

322

0,255

82

0,7712

13

3486

-7,0E38

470

0,097

212

0,454

14

3794

-5,2E40

542

0,044

78

0,783

 

По тесту «Проверка частот» (Д. Кнут) оценивается равномерность распределения символов в изучаемой последовательности  -разрядных чисел длины . Находится количество появлений  каждого числа и статистика:  , которая проверяется с помощью критерия , число степеней свободы здесь равно .    Тестирование  проведено для 8-ми разрядных чисел (таблица 4). Число степеней свободы  256, тогда  статистика  должна принимать значения от 221 до 285,3927. Для последовательностей, сформированных из элементов  «первая слева» для всех значений чисел А и В получены  отрицательные результаты. Для последовательностей, составленных из вырезок «в центре» и «последняя справа»  худшим является вариант 2 значений чисел А и В, а тест прошли 11 вариантов 1, 4–10 и 12–14 значений чисел А и В.

 

     Таблица 4 – Тест «Проверка частот»,  длина ПСП – 10000 элементов

 

Номер

варианта

Статистика ,  = 8,   256

Вырезки:

«первая слева»

«в центре»

«последняя справа»

1

931,507

237,747

276,966

2

640,486

243,328

212,915

3

586,675

218,240

263,654

4

670,592

235,648

282,291

5

751,898

278,810

252,595

6

922,445

275,942

269,645

7

896,998

251,981

260,941

8

633,728

251,878

244,454

9

593,587

222,899

229,197

10

617,190

246,400

242,355

11

937,754

287,411

237,184

12

837,248

266,982

271,642

13

846,106

281,882

255,002

14

971,187

222,182

279,373

 

В тесте «Дырок» (Runs Test, НИСТ) исследуется  равномерность распределения 0 и 1 в проверяемой последовательности на основе анализа количества появлений подпоследовательнотей «блоков» и «дырок», состоящих соответственно из одних единиц и одних нулей. Проверяется двоичная последовательность  длины . Находится предтестовая  статистика - доля единиц в последовательности: . Если , то тест не пройден. В противном случае находится статистика (количество блоков и дырок) , где  при  и  при . Затем находится значение , которое  должно быть больше 0,01.

Последовательностями, сформированными из элементов  «первая слева», не пройдена предтестовая статистика (таблица 5). Для последовательностей, составленных из вырезок «в центре», вариант 2 не прошел предтестовую статистику, а в варианте 4.11 – отрицательно . У последовательностей, построенных из вырезок «в центре», по всем вариантам величин  А и В  получены положительные результаты. Лучшие статистические характеристики  для вырезок «в центре» и «последняя справа» получены 12 вариантами 1, 3–10 и 12–14 значений чисел А и В.

 

    Таблица 5 – Тест «дырок», длина ПСП – 10000 элементов

 

Номер

варианта

Вырезки

«первая слева»

 

«в центре» 

«последняя справа» 

Предтес.  статистика

P

Предтес.  статистика

P

Предтес.  статистика

P

1

нет

0,540

да

0,384

да

0,606

2

нет

0,114

нет

0,937

да

0,707

3

нет

0,982

да

0,402

да

0,729

4

нет

0,366

да

0,094

да

0,292

5

нет

0,212

да

0,814

да

0,203

6

нет

0,806

да

0,989

да

0,853

7

нет

0,674

да

0,882

да

0,322

8

нет

-2,6Е05

да

0,382

да

0,436

9

нет

0,236

да

0,387

да

0,760

10

нет

0,897

да

0,739

да

0,869

11

нет

-7,6Е07

да

-1,653

да

0,867

12

нет

0,949

да

0,451

да

0,4371

13

нет

0,888

да

0,797

да

0,401

14

нет

0,921

да

0,741

да

0,506

 

Результаты проверки качества последовательностей по оценочным тестам согласуются с данными проверки по графическим тестам. Компьютерное моделирование качества предложенного алгоритма генерации псевдослучайных последовательностей  показало, что период генератора не обнаружен при длинах последовательности до 100000 элементов, статистические свойства генерируемых последовательностей зависят от значений чисел А и В, построение последовательностей необходимо производить из элементов, вырезаемых из центральной части последовательности и правее нее, статистические свойства генерируемых последовательностей можно определить по последовательностям длиной  из 10000 элементов, в качестве величин А и В предпочтительнее использовать иррациональные числа или подобные вариантам 5 и 10.

Генерация ключей является  одной из задач процесса управления ключами. Другая его задача -  реализация функции открытого распределения ключей. Безопасность классического алгоритма Диффи – Хеллмана обусловлена трудностью вычисления дискретных логарифмов в конечном поле.

Суть разработанного (модернизированного) алгоритма состоит в следующем. Предположим, что два пользователя А и С хотят организовать защищенный коммуникационный канал. Формируется  непозиционная полиномиальная  система счисления путем выбора  рабочих оснований   степени  соответственно.  Определяется рабочий диапазон НПСС - многочлен  степени . Тогда единственное непозиционное представление любого многочлена  F(x) степени меньше m  записывается   в виде:

                                           ;                                  (21)

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

Для восстановления позиционного вида многочленов находятся базисы НПСС по выражению (1). Для этого определяются следующие полиномы: , . Находятся также и инверсные к ним многочлены : , . Тогда по формуле (1) вычисляются базисы по следующим выражениям: . Многочлены  также держатся в секрете.

Абоненты А и С, также как и классическом алгоритме Диффи–Хеллмана, выбирают случайно и независимо друг от друга по одному секретному ключу соответственно  и : .

Далее каждый из участников обмена вычисляет новый элемент –  открытые ключи. Абонент  А  определяет:

, где ;

а абонент С находит:

, где ;

 

где . Операции возведения в степень могут выполняться параллельно по модулям полиномов, выбранных в качестве рабочих оснований НПСС.  Затем А и С обмениваются элементами и по открытому каналу связи.

После получения   абонент А по ключу определяет:

, ;

где . Абонент С по полученному   и по своему вычисляет:

, ;.

где . Поскольку (, то и . В результате этих действий абоненты А и С стали обладателями общего элемента  – их общего ключа. Для восстановления позиционного вида полинома   применяется формула (1).

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

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

            .       (22)

Проведенные расчеты показали, что использование нетрадиционного подхода при построении алгоритма открытого распространения ключей позволяет существенно повысить его надежность, в том числе и при изменении длины общего ключа. Увеличение длины ключа от 2 до 16 бит приводит к росту криптостойкости на 14 порядков, а на 1 бит – примерно на 1 порядок (таблица 1). Для ключа длиной 128 бит  стандарта шифрования AES  при выборе одной системы рабочих оснований из 8 неприводимых многочленов 16 степени  криптостойкость  модифицированного алгоритма равна.

Основные результаты и выводы диссертации изложены в заключении.

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

Заключение

 

Основные результаты, полученные в диссертационной работе:

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

2. Определено количество возможных вариантов выбора систем оснований НПСС из числа неприводимых многочленов, применяемых при шифровании сообщения длины от 1 до 16 бит. Увеличение длины на 1 бит вызывает рост количества  указанных вариантов примерно в 2 раза.

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

4. При сопоставлении разработанного алгоритма шифрования с государственным стандартом Республики Казахстан СТ РК 1073-2002 на средства криптографической защиты информации по приведенным в нем требованиям к  криптостойкости и со стандартом шифрования США выявлено, что его использование с учетом требований стандарта СТ РК 1073-2002 по надежности повышает стойкость криптографического преобразования на десятки порядков при значительно меньшей длине ключевых последовательностей, а криптостойкость может быть выше криптостойкости стандарта AES  при длине ключа 128 и 192 бита на десятки порядков, а при длине ключа 256 бит – на сотни порядков.

5. Создан нетрадиционный алгоритм формирования электронной цифровой подписи по модулям нескольких избыточных оснований для электронного сообщения заданной длины, включающий 3 этапа: формирование НПСС; хэширование сообщения длины N до длины  путем введения системы избыточных оснований; шифрование полученного хэш-значения.

7. Получена формула криптостойкости алгоритма формирования ЭЦП–1, характеризующаяся полным ключом из выбранных систем рабочих и избыточных оснований и числом их перестановок, а также полным ключом для шифрования хэш–значения. Криптостойкость зависит от длины сообщения и цифровой подписи.

8. Разработан нетрадиционный алгоритм, в котором совмещены 2 функции: алгоритм создания электронной цифровой подписи для электронного сообщения заданной длины и процедура обнаружения/исправления ошибок. Формирование ЭЦП–2 также производится в 3 этапа, но при хэшировании вводится 1 избыточное основание и вычисляются 3 избыточных вычета, которые  используются для формирования ЭЦП–2, для обнаружения и коррекции одиночной ошибки и выявлении многократной ошибки. Определены условия выбора оснований на каждом этапе формирования ЭЦП–2. Максимальная степень рабочего основания не должна превышать степени избыточного основания.

9. Найдена формула, характеризующая зависимость криптостойкости ЭЦП–2 от  полного ключа. Надежность данного алгоритма также зависит от длины сообщения и электронной подписи, однако эта зависимость является более нелинейной по сравнению с алгоритмами шифрования и создания ЭЦП–1.

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

11. Проведено компьютерное исследование генератора на периодичность и статистическую безопасность по 5 графическим тестам «Распределение на плоскости», «Гистограмма распределения элементов», «Проверка серий», «Проверка на монотонность» и «Автокорреляционная функция»  и  4 оценочным тестам «Проверка несцепленных серий», «Частотный тест», «Проверка частот», «Тест дырок» на 14 вариантах  значений двух чисел. Периодичность не обнаружена в последовательностях длиной до 100000 элементов.

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

13. Разработан алгоритм открытого распространения криптографической ключевой информации на базе непозиционных полиномиальных систем счисления. Секретными в нем являются неприводимые многочлены, которые выбираются в качестве рабочих оснований и примитивных элементов, а также личные ключи.

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

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

Разработка программных продуктов проведена  в соответствии с календарными планами по разделу «Комплексное обеспечение безопасности информационных космических технологий» по теме «Разработка технологических основ создания и применения спутниковых информационно-телекоммуникационных систем и обеспечения их безопасности» Государственной программы «Развитие космической деятельности в Республике Казахстан на 2005-2007 годы». Получен акт проверки и испытаний макетных образцов созданных программ и программных комплексов.

Полученные результаты диссертационной работы являются новыми и имеют теоретическую и практическую ценность. Разработанные новые алгоритмы нетрадиционных криптографических преобразований и генерации ПСП способствуют развитию теории криптографической защиты информации и генераторов ПСП и направлены на создание системы надежной и эффективной криптографической защиты информации, обеспечивающей информационную безопасность в телекоммуникационных и информационных системах и сетях различного назначения, в том числе и спутниковых.  Они вносят вклад в создание и развитие отечественных средств  криптографической защиты в соответствии с Законом Республики Казахстан «Об информатизации» от 11.01.07 № 217-Ю ЗРК. Разработанные программные средства могут быть использованы для криптографической защиты хранимых и передаваемых электронных данных в информационных системах электронного правительства, электронного голосования, дистанционного обучения.

Предлагаемые разработки позволяют при достаточно простой реализации создавать эффективные системы и средства защиты информации повышенной надежности при меньших длинах ключей симметричных криптографических систем и формирования электронной цифровой подписи по сравнению с теми длинами, которые рекомендованы в государственном стандарте Республики Казахстан «СТ РК 1073-2002. Средства криптографической защиты информации. Общие технические требования. - Астана: Госстандарт РК, 2002».

 

Список опубликованных работ по теме диссертации

1    Бияшев Р.Г., Горковенко Е.В, Нысанбаева С.Е. Алгоритм формирования электронной цифровой подписи повышенной надежности // Проффи. – 2005. –  № 17. – С. 2-5.

2           Амербаев В.М., Бияшев, Р.Г., Горковенко Е.В, Нысанбаева С.Е. Использование модулярной арифметики при формировании электронной подписи с заданными характеристиками // Докл. Нац. акад. наук Республики Казахстан. - Алматы: Гылым, 2005, № 4. – С. 30-37.

3           Бияшев Р.Г., Горковенко Е.В, Нысанбаева С.Е. Алгоритм генерации ключей повышенной надежности // Матер. 2-й Междунар. науч.-практ. конф. «Состояние, проблемы и перспективы информатизации в РК». – Усть-Каменогорск : Изд-во Вост.-Казахст. гос. техн. ун-та им. Д. Серикбаева, 2005. – 26-30 сентября. – С. 131-132.

4     Амербаев В.М., Бияшев, Р.Г., Нысанбаева С.Е. Применение непозиционных систем счисления при криптографической защите // Изв. Нац. акад. наук Республики Казахстан. – Сер. физ.-мат. – Алматы: Гылым, 2005. - № 3. – С. 84-89.

5    Бияшев Р.Г.,  Арсланова С.З., Нысанбаева С.Е. «NeprivodPolinom» (программа для ЭВМ) // Свидетельство о государственной регистрации объекта интеллектуальной собственности. Запись в реестре Комитета по правам интеллектуальной собственности Мин-ва юстиции Республики Казахстан № 055 от 21 февраля 2006 г.

6     Бияшев Р.Г., Нысанбаева С.Е. Процедура шифрования сообщения в полиномиальной системе остаточных классов // Новости науки Казахстана: Науч.-техн. сборник. – Алматы, 2006. -  Вып. 3. - С. 142-148.

7     Бияшев Р.Г., Нысанбаева С.Е. Влияние состава полиномиальных оснований непозиционной системы счисления на надежность шифрования  // Материалы VIII Международной науч.-практ. конф. «Информационная безопасность». Ч.2. – Таганрог: изд-во ТРТУ, 2006. - С. 66-69.

8     Бияшев Р.Г., Нысанбаева С.Е. Нетрадиционный подход к созданию криптосистем // Информационные технологии и безопасность: Сб.науч. тр.- Украина, Киев, 2006. - Вып. 9. - С. 20-27.

9    Бияшев Р.Г., Нысанбаева С.Е. Создание электронной цифровой подписи в непозиционной полиномиальной системе // IV Междунар. научн. конф. «Проблемы дифференциальных уравнений, анализа и алгебры» (Актобе, 18-21 октября 2006 г.). Тез. докл. – Актобе, 2006 –  С. 131.

10       Бияшев Р.Г., Нысанбаева С.Е. Исследование надежности электронной цифровой подписи в непозиционной полиномиальной системе счисления // Изв. Нац. акад. наук Республики Казахстан. – Сер. физ.-мат. – Алматы: Гылым, 2006. - № 5. - С. 56-61.

11      Бияшев Р.Г., Горковенко Е.В, Нысанбаева С.Е. Алгоритмы шифрования сообщений и формирования электронной цифровой подписи с заданной криптостойкостью // «50 лет модулярной арифметики». Юбил. Междунар. науч.-техн. конф. (В рамках V Междунар. науч.-техн. конф. «Электроника и информатика – 2005»). Зеленоград, 23-25 ноября 2006 г: Сборник научных трудов.- М.: ОАО «Ангсрем», МИЭТ, 2006 - С. 576-586.

12      Бияшев Р.Г., Арсланова С.З., Нысанбаев Р.К., Нысанбаева С.Е. «Ciphering/Deciphering» (программа для ЭВМ) // Свидетельство о государственной регистрации объекта интеллектуальной собствен­нос­ти. Запись в реестре Комитета по правам интеллектуальной собственности Мин-ва юстиции Республики Казахстан  № 466 от 13 декабря 2006 г.

13       Бияшев Р.Г., Нысанбаева С.Е. Моделирование информационных систем накопительного типа // Тр. Междунар. конф. «Автоматизация и управление, перспективы, проблемы и решения», 15-18 января 2007 г. – Алматы: КазНТУ, 2007. – С. 326-329.

14       Бияшев Р.Г.,  Нысанбаева С.Е. Формирование электронной цифровой подписи с проверяющими функциями // Комплексная защита информации: материалы XI Междунар. конф. (20-23 марта 2007 г., Новополоцк, Республика Беларусь). – Минск: Амалфея, 2007. – С. 51-54.

15      Бияшев Р.Г., Арсланова С.З., Нысанбаев Р.К., Нысанбаева С.Е. «Keysgener» (программа для ЭВМ) // Свидетельство о государст­венной регистрации объекта интеллектуальной собствен­нос­ти. Запись в реестре Комитета по правам интеллектуальной собственности Мин-ва юстиции Республики Казахстан  249 от 17 мая 2007 г.

16      Бияшев Р.Г., Нысанбаева С.Е. Моделирование генерации ключей в непозиционной полиномиальной системе счисления // Изв. ЮФУ. Технические науки. Тематический выпуск «Информационная безопасность» - Таганрог: Изд-во ТТИ ЮФУ, 2007. - № 1 - С.193-198.

17       Капалова Н.А., Нысанбаева С.Е.  Генератор ключевых последовательностей для поточного шифрования // Матер. IX Междунар.науч.-практ. конф. «Информационная безопасность». Ч. 2. – Таганрог: Изд-во ТТИ ЮФУ, 2007. - С. 135-137.

18      Бияшев Р.Г., Арсланова С.З., Нысанбаев Р.К., Нысанбаева С.Е. «Shifr/ RasShifr» (программный комплекс для ЭВМ) // Свидетельство о государст­венной регистрации объекта интеллектуальной собствен­нос­ти. Запись в реестре Комитета по правам интеллектуальной собственности Мин-ва юстиции Республики Казахстан  352 от 26 июля 2007 г.

19       Бияшев Р.Г., Нысанбаева С.Е. Криптографическая защита в информационных космических технологиях на базе нетрадиционного подхода // Матер. Междунар. конф., посвящ. итогам выполнения Государственной программы «Развитие космической деятельности в Республике Казахстан на 2005-2007 годы»: Тез. докл. - Алматы,  2007 - С. 172-174.

20       Капалова Н.А., Нысанбаева С.Е. Исследование алгоритма генерации псевдослучайных последовательностей для поточных криптосистем // Матер. Междунар. конф., посвящ. итогам выполнения Государственной программы «Развитие космической деятельности в Республике Казахстан на 2005 – 2007 гг.». Тез. докл.. -  Алматы, 2007. - C. 102-103.

21       Капалова Н.А., Нысанбаева С.Е. Исследование алгоритма генерации псевдослучайных последовательностей // Информационные технологии и безопасность. Менеджмент информационной безопасности: Сб. научн. тр. - Украина, Киев, 2007. – Вып.10. - C. 32-39.

22       Бияшев Р.Г., Нысанбаева С.Е. Исследование  надежности корректирующей электронной цифровой подписи // Управление защитой информацией. - Минск-Москва, 2007. – Т. 11, № 4. – С. 447-453.

23       Бияшев Р.Г., Арсланова С.З., Нысанбаева С.Е. Создание криптосистем в спутниковых информационно-телекоммуникационных системах на базе модулярной арифметики // Информационные технологии  в высшем образовании. – Алматы: КазНУ им. аль-Фараби. 2007. – Т. 4,  № 1. – С.71-81.

24       Капалова Н.А., Нысанбаева С.Е. Разработка алгоритма и оценка качества  генератора псевдослучайных последовательностей // Новости науки Казахстана: Науч.-техн. сб.. - Алматы,  2007. – Вып. 4 - С. 105-111.

25       Нысанбаева С.Е. Алгоритм формирования корректирующей электронной цифровой подписи // Изв. Нац. акад. наук Республики Казахстан. – Сер. физ.-мат. – Алматы: Гылым, 2007. - № 5. - С. 52-57.

26      Бияшев Р.Г., Арсланова С.З., Нысанбаев Р.К., Нысанбаева С.Е. «EDS1/CheckEDS1» (программный комплекс для ЭВМ) // Свидетельство о государст­венной регистрации объекта интеллектуальной собствен­нос­ти. Запись в реестре Комитета по правам интеллектуальной собственности Мин-ва юстиции Республики Казахстан  521 от 15 ноября  2007 г.

27       Капалова Н.А., Нысанбаева С.Е.  Алгоритм открытого распределения ключей на базе непозиционной полиномиальной системы счисления // Вестник КазНУ. Сер. мат., мех., информат. -  2007, №3 (54). - С. 82-87.

28       Нысанбаева С.Е. Обеспечение аутентификации и целостности в информационных системах накопительного вида // Изв. науч.-техн. общества «КАХАК». - Алматы, 2007. -  № 3. - С.19-28.

29       Нысанбаева С.Е. Процедура хэширования в нетрадиционном алгоритме формирования электронной цифровой подписи // Математический журнал. – Алматы, 2007. - Т.7 , № 4 (26). - С.­­­ 69-74.

30      Бияшев Р.Г., Арсланова С.З., Нысанбаев Р.К., Нысанбаева С.Е. «EDS2/CheckEDS2» (программный комплекс для ЭВМ) // Свидетельство о государст­венной регистрации объекта интеллектуальной собствен­нос­ти. Запись в реестре Комитета по правам интеллектуальной собственности Мин-ва юстиции Республики Казахстан  ­­­006 от 15 января 2008 г.

31      Нысанбаева С.Е. Моделирование криптографических систем  на основе модулярной арифметики // Новости науки Казахстана: Науч.-техн. сб.. - Алматы. 2008. - Вып. 1 - С. 37-41.

32       Нысанбаева С.Е. Разработка программы процедуры  генерации и хранения криптографических ключей на базе модулярной арифметики // Изв. науч.-техн. общества «КАХАК». - Алматы, 2008. - №1. - С.­­­ 16-24.

33       Нысанбаева С.Е. Моделирование нетрадиционного алгоритма формирования электронной цифровой подписи // Вестник Нац. инженерной академии РК. – Алматы,  2008. - № 1 (27). - С. ­­­­ 33-38.

34      Нысанбаева С.Е. Реализация алгоритма шифрования  на базе непозиционной полиномиальной системы счисления // Вестник Каз. нац. техн. ун–та им. К.И.Сатпаева. - Алматы, 2008. - № 2 (65). - С. ­­­­ 102–109.

35      Нысанбаева С.Е. Реализация алгоритма формирования электронной цифровой подписи на базе непозиционной полиномиальной системы счисления // Вестник Каз. нац. техн. ун–та им. К.И.Сатпаева. – Алматы, 2008. - № 2 (65). - С. ­­­­ 123–130.

36       Капалова Н.А., Нысанбаева С.Е. Исследование нетрадиционного алгоритма открытого распределения ключей // Инфокоммуникационные  технологии в науке, производстве и образовании: Третья Межд. науч.-практ. конф. Ч. III. -  г. Ставрополь, Северо-Кавказ. гос. техн. ун– т, 1-5 мая 2008. - С. 217-222.

37      Нысанбаева С.Е. Сравнение алгоритма шифрования, разработанного на базе модулярной арифметики, со стандартом  шифрования AES // Математический журнал. – Алматы, 2008. - Т.8, № 1 (27). – С. 82-89.

38      Нысанбаева С.Е. Эффективность нетрадиционного подхода к построению криптографических  систем с секретным ключом // Вестник Каз. акад. транспорта и коммуникаций. – Алматы, 2008. -  № 4 (53). - С. ­­­ 142-148.­

39       Капалова Н.А., Нысанбаева С.Е. Анализ статистических свойств алгоритма генерации псевдослучайных последовательностей // Матер X-й Междунар. науч.-практ. конф. «Информационная безопасность». Ч. 2. - Таганрог: Изд-во ТТИ ЮФУ, 2008. - С. 169-172.

40      Бияшев Р.Г., Нысанбаева С.Е.,  Капалова Н.А. Разработка и исследование алгоритма генерации псевдослучайных последовательностей // Матер. Междунар. науч. конф. «Современные проблемы математики, информатики и управления», посвящ. 60-летию д.ф.-м.н., проф., акад. Междунар. академии информатизации М.Б. Айдарханова: Сб. науч. тр.- Алматы, Институт проблем информатики и управления, 2008. – С.248– 253.

 

ТҮЙІН

 

Нысанбаева Сәуле Еркебұланқызы

Позициялы емес полиномды санау жүйелер негізінде

криптографиялық жүйелерді құру және зерттеу

 

05.13.01 – жүйелі талдау, басқару және ақпаратты өңдеу

 

Техника ғылымдарының докторы  ғылыми дәрежесін

алу үшін дайындалған диссертация

 

Диссертациялық жұмыстың зерттеу объектісі позициялы емес полиномды санау жүйелерін (ППСЖ) қолдану арқылы құрылған шифрлеу, бір және бірнеше артылымды негіз модулі бойынша электрондық сандық қолтаңба түзетін алгоритмдер және ашық байланыс арналары арқылы криптографиялық кілттерді  тарату Диффи-Хеллманның модификацияланған алгоритмі, сондай ақ псевдокездейсоқ тізбектер (ПКТ) генераторы болып табылады.

Жұмыстың мақсаты:  позициялы емес полиномды санау жүйелер негізінде шифрлеу, түрлі сандық артылымды негіз модулі бойынша электрондық сандық қолтаңбалар түзетін және ашық түрде құпия кілттерді тарату жаңа  алгоритмдерін құру және олардың криптотұрақтылығын зерттеу; ұсынылған шифрлеу, электрондық сандық қолтаңбалар түзетін дәстүрлі емес алгоритмдер үшін бағдарламалық өнімдер жасау; ПКТ генерлеу алгоритмін құру және олардың статистикалық қасиеттерін сараптау.

Диссертациялық жұмыстың негізгі нәтижелері:

-            ППСЖ қолдану арқылы белгіленген ұзындықтағы электронды хабарды шифрлеу алгоритмі құрылған; полиномиальді негізін таңдау әдістерінің мүмкін болатындарын теру арқылы оның криптотұрақтылығы зерттелді; шифрлеудің тұрақтылығы айтарлықтай хабар ұзындығына байланысты;

-            бұл алгоритмді СТ РК 1073-2002 стандартының криптотұрақтылық талаптарын ескере отырып қолданғанда симметриялық шифрлеудің сенімділігін айтарлықтай көтеруге болады,  кілттер ұзындығының мейлінше қысқа кезінде;

-            ұсынылған шифрлеу алгоритмі бағдарламалық жүзеге асырылды: 3 бағдарламалық өнім құрылды, криптографиялық толық кілттерді генерлейтін, толық кілттер мәлімет қорынан симметриялық шифрлеуге кілттерді таңдайтын; берілген және ерікті ұзындықтағы ашық хабарды шифрлеу және криптограмманы дешифрлеу;

-            3 кезеңнен тұратын, ұзындығы берілген электрондық хабар үшін  бірнеше артылымды негіз модулі бойынша электрондық сандық қолтаңба түзетін (ЭСҚ-1) дәстүрлі есес алгоритм ұсынылды: ППСЖ құру; бірнеше артылымды негіз енгізі арқылы хабарды хэширлеу; алынған хэш-мәнді шифрлеу;

-            толық кілтпен сиппаталатын (таңдалған жүйенің жұмыс және артылымды полиномиальды негіздері мен осы жүйедегі оларың орынауыстыру саны, және де хэш-мәнді шифрлеу үшін толық кілтпен) ЭСҚ-1  криптотұрақтылық формуласы алынды; электрондық сандық қолтаңба түзу процедурасының криптотұрақтылығы хабардың ұзындығынан айтарлықтай тәуелді;

-            үш бағдарламадан тұратын кешен түрінде ЭСҚ-1 құру және тексеру процедурасы бағдарламалық жүзеге асырылған, онда мәліметтер қорынан толық кілт таңдалып, ерікті ұзындықтағы хабар үшін сандық қолтаңба түзіледі және сандық қолтаңбаның дұрыстығы тексеріледі;

-            бір артылымды негіз модулі бойынша электрондық сандық қолтаңба түзуді (ЭСҚ-2) қателерді табу/түзету процессімен біріктіретін дәстүрлі емес алгоритм құрылды; ол да үш кезеңнен тұрады; ЭСҚ-2 құрайтын хэшерлеу кезінде үш артылымды қалдық есептеледі  және бірлік қателерді табу мен түзетуге, қат-қабат қателерді айқындауға қолданылады; ЭСҚ-2 құрудың әр кезеңінде негіздерді таңдау шарттары анықталды; криптотұрақтылықтың толық кілттен тәуелділігін сипаттайтын формула алынды; аталмыш ЭСҚ түзетін процедураның криптотұрақтылығы сонымен қатар хабар ұзындығына байланысты екені анықталды;

-            ЭСҚ-2 жүйесі екі бағдарламадан кешенді жүзеге асырылған: берілген ұзындықтағы хабарға  электрондық қолтаңба түзу, және де ЭСҚ дұрыстығы мен қателерін тексеру;

-            ПКТ түзетін алгоритм ұсынылды, онда тізбек элементі екі санның, енгізілген және  аралық мәндердің, көбейтіндісінің  қатар орналасқан бірнеше биттен тұратын қиқықтан түзіледі және алгоритмнің статистикалық қасиеттеріне компьютерлік зерттеу жүргізілді;

-         ППСЖ негізделген ашық криптографиялық кілттерді тарату алгоритмі ұсынылды және оның криптотұрақтылығы зерттелді.

Құрылған шифрлеу, ЭСҚ түзу және ашық түрде құпия кілттерді тарату алгоритмдері, сондай ақ ПКТ генерлеу процедурасы криптографиялық қорғау және  ПКТ генерлеу теорияларын кеңейтеді.

 GF(2) өрісінде берілген дәрежелі келтірілмейтін көпмүшеліктерді есептеуді, шифрлеу мен дешифрлеу, толық кілттерді генерлеу, электрондық сандық қолтаңба түзу және тексеру дәстүрлі емес алгоритмдерді жүзеге асыратын бағдарламалық өнімдерге Қазақстан Республикасының зияткерлік меншік объектісі ретінде мемлекеттік тіркеу куәліктер алынды.

 

 

 

 

 

 

 

 

 

 

Summary

 

Nyssanbayeva Saule Erkebulanovna

Development and Research of Cryptographic Systems

on Base of Non-Positional Polynomial Notations

 

05.13.01 - System analysis, control and information processing

 

Dissertation is presented for the scientific degree of  technical sciences doctor 

 

 

Object of research - nontraditional algorithms of enciphering, formation of the electronic digital signature on modules of one and several superfluous bases and modified Diffie-Hellman algorithm of open distribution of the cryptographic keys constructed with use non-positional polynomial notations (NPPN), and also algorithm of generation of pseudorandom sequences (PCS).

The purpose of researches: development of new algorithms of enciphering, formation of electronic digital signatures on modules of different number of the superfluous bases and open distribution of confidential keys on the basis of non-positional polynomial notations and studying of their cryhtostability; creation of software for the proposed nontraditional algorithms of ciphering and formation of electronic digital signatures; construction of algorithm of pseudorandom sequences generation and the analysis of it statistical properties.

The following results are received:

-            the algorithm of enciphering of the electronic message of the determinated length with use NPPN is developed; research of its cryptostability by exhaustive search of possible ways of a choice of the polynomial bases is carried out; cryptostability of enciphering considerably depends on length of the message;

-            application of this algorithm in view of requirements of the standard ST RK 1073-2002 on cryhtostability can increase essentially reliability of symmetric enciphering on tens orders at much smaller lengths of keys;

-            program realization of the offered{suggested} algorithm of enciphering is carried out: are developed 3 software making generation of full cryptographic keys, a choice of keys for symmetric enciphering from a DB of full keys; encryption open messages of the set and any length and decryption of cryptograms;

-             the nontraditional algorithm of formation of the electronic digital signature on modules of the several superfluous bases (EDS-1) for the electronic message of the set length which includes 3 stages is offered: formation NPPN, hash of messages by introduction of the several superfluous bases; enciphering of the received hash-value;

-            the cryptostability formula EDS-1 which is characterized by a full key (by chosen systems of the working and superfluous polynomial bases and number of their rearrangements in these systems, and also a full key for enciphering hash-value) is received; it is established, that procedure cryptostability of formation of the digital signature essentially depends on length of the message;

-            procedure of formation and check EDS-1 as a complex from  three programs  in which the full key gets out of a DB is realized, the digital signature for the message of any length is formed and correctness of the digital signature is program checked;

-            the nontraditional algorithm combining creation of the digital signature  on the module of one superfluous basis (EDS-2) with process of detection / correction of mistakes is developed; it also consist of three stages; at hash three superfluous residues which make EDS-2 and used for detection and correction of a single mistake and revealing of a repeated mistake are calculated;

-            conditions of a choice of the bases at each stage of formation EDS-2 are determined; the formula describing cryptostability dependence from a full key is deduced; it is revealed, that cryptostability the given procedure of formation EDS also depends on length of the message; system EDS-2 is realized by a complex from two programs: formations of the digital signature for the message of the set length, and also check of authenticity EDS and presence of mistakes;

-            the algorithm of generation of pseudorandom sequences in which PCS are formed of elements (cuttings) several successively going bits, cut out of result of product of entrance and intermediate values two numbers is offered and computer modeling of it statistical properties is carried out;

-            the open distribution  algorithm of secret keys with use NPPN is constructed and it cryptostability is investigated.

 The created algorithms of enciphering, formation EDS and open distribution of secret keys, and also procedure of generation PCS develop the theory of cryptographic protection and generators PCS.

Copyright certificates on state their registration as objects of the intellectual property of Republic Kazakhstan on the software realizing calculation of nonreducible polynoms of the set degree above field GF(2), nontraditional algorithms encryption and decryption, generation of full keys, formation and check of electronic digital signatures are received.