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

На правах рукописи

Осипян Валерий Осипович

РАЗРАБОТКА МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ СИСТЕМ ПЕРЕДАЧИ И ЗАЩИТЫ ИНФОРМАЦИИ, СОДЕРЖАЩИХ ДИОФАНТОВЫ ТРУДНОСТИ

05.13.18 — математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание уч!иой степени доктора физико-математических наук

Ставрополь 2006

Работа выполнена на кафедре информационных технологий Кубанского государственного \ ниверситета

Научный консультант: доктор физико-математических наук.

профессор Семенчин Евгений Андреевич

Официальные оппоиепты:

доктор технических наук, профессор Бабенко Людмила Климентьевна

Ведущая организация: Ростовский государственный университет.

Зашита диссертации состоится 27 декабря 2006 г. в 14 час. на заседании регионального диссертационного совета ДМ 212.256.05 при Ставропольском государственном университете по адресу: 355009, г. Ставрополь, ул. Пушкина, 1.

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

доктор физико-математических наук, профессор Добровольский Николай Михайлович

доктор физико-математических наук, профессор Толпаев Владимир Александрович

Автореферат разослан

ноября 2006 г.

Учёный секретарь диссертационного совета, канд. физ.-мат. наук, доцент

Копыткова Л.Б.

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

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

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

В последние годы наблюдается интенсивное развитие кюрии зашиты информации. За сравнительно короткий срок под влиянием пофебностен практики опубликовано значительное число работ, посвященных различным проблемам )тои 1еории. М И. Анохин, Л К Бабенко, Р.Г Бияшев, Ю В Бородакнй, Ж. Ьрассар, Ю.Л Брюхомицкий, Ы П. Варнавскнй, Г А Гапуев, М М Глухой, Н Д Гуц, П Н Депянин, У. Диффи, А Л Зубарев, С С Ищукеш, Г А Кабагянскии, II Коблиц, А Г Конхейм, О Б Макаревич, Т А Мазурова, С Мафтик, А А Мол-довян, Дж.Л Мэси, Ю.В. Нестеренко, В И Нечаев, А А. Петров, В Г Проскурин, А Г Ростовцев, Е Б Маховенко, А. Соломин, В М Сндельников, И Д Сидоров, С Н. Смирнов, М.Э. Хеллман, Л.Дж. Хоффман, А В Черемушкин, А.Г Чефранов, А Л Чмора, К. Шеннон, Б Шнайер, В В. Ящепко и др Усиленные теоретические и практические исследования продолжаются и можно с уверенностью ска«пь, что повышенный интерес к данной сфере исследований сохранится и в обозримом будущем. Более того, из обшей теории информации выделилась новая самостоятельная ветвь - теория зашиты информации (ТЗИ), основным предметом которой является исследование возможностей повышения надежности передаваемых данных по реальным каналам связи Эта теория, несомненно, имеет большое будущее, так как стремительно расширяется сеть пользователей персональных компьютеров, а вместе с ней повышаются требо-пания к передаваемой и обрабатываемой информации.

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

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

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

3) разработка математических моделей для описания новых систем передачи и гашиты информации.

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

1) создать абсолютно надежный автономный канал связи, недоступный

для оппонентов,

2) использовать общедоступный канал, но скрыть сам факт передачи конфиденциальной информации;

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

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

Вопросы защиты информации самым непосредственным образом связаны с методами кодирования, В известных работах М.Н. Лршинова, Э, Бсрлскэмпа, Р, Блейхута, Р.К, Боуза, М. Бутлера, P.P. Впршамопа, Р. Галлагера, В.Н, Гоопы, Ю.Г. Дадпспа, В,И, Дмиттриева, Е. Ивалари, Я, Инагаки, Т. Касами, В,Д. Колесника, В,И. Коржика, В.И, Левснщтсйна, Ф.Дж, Мак-Вильямса, Е.Т. Мироч-никова, У. Питерсона, Д.К, Рой-Чоудхури, IO.I1. Руднева, Л.Е, Спдовского, И. Слоэна, А. Харкевнча, Я.А, Хстагурова, В.П, Цымбопа, К. Шеннона, Г.М, Тененгольца, Н. Токура, М.В. Яковкина и др, разработан ряд конструктивных методов построения контролирующих кодов, которые имеют большую практическую ценность. Однако, несмотря на значительный прогресс в изучении теории кодов, недостаточно полно рассмотрены практические аспекты программно-аппаратной реализации полученных новых разработок. К тому же в некоторых случаях больший эффект может быть достигнут при использовании неоптимального алгоритма кодирования и декодирования, который имеет простую программную или программно-аппаратную реализацию, В этом смысле класс циклических кодов, как важнейший подкласс линейных кодов, является эффективным как с алгоритмической, так и с вычислительной точек зрения благодаря использованию аппарата полей Галуа. С другой стороны, имеется прямая аналогия между обычными циклическими кодами передачи информации и циклическими AN-кодами, Причйм, многие известные циклические коды имеют арифметические аналоги, хотя нерешенной остается задача построения класса циклических AN-кодов, подобного классу кодов БЧХ, Подчеркнем, что циклические коды допускают простую техническую реализацию и могут быть использованы для изучения, поиска и построения других не менее эффективных в практическом отношении кодов. Особое внимание в этой связи заслуживают исследования Р.К, Боуза, X, Мэттсона, Д.К. Рой-Чоудхури, Г, Соломона, А, Хоквинхема, которые сводят задачу синтеза эффективных кодов к задаче отыскания порождающих полиномов g(x) над конечными полями, имеющими заданное множество корней.

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

Дальнейшее развитие этой проблемы и, в частности, задачи построения неприводимых в поле Галуа полиномов, отражено в работах А.А, Албсрта, Э, Берлекэмпа, Г.А, Гаракова, Л.Е. Диксона, Д,Н. Ленского, Р, Лидла, Г, Нидср-райтсра, Э.А, Сергеева, В,М, Сидельникова, С.А, Степанова, А,Г. Школьника,

М В Яковкннл и лр Наиболее важным вклад н решение данном проблемы внес I* I5 Варшамов, получившим ряд фундаментальных результатов консфумивной теории приводимости полиномов над конечными полями

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

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

математической модели, использующей сравнение вида

и

1-1

где р, - члены заданной числовой последовательности, а, - могут принимать значения, вообще говоря, из различных числовых множеств Д„ ¡=1. . п, ¡1 е7.. В частности, совокупность всех бинарных решений указанного сравнения при Р,=ч, т=2п, а>0 задаёт код Варшамова, исправляющий одиночные вставки, выпадения и симметричные ошибки В то же время, если в качестве Р взять рюкзачный вектор, а в качестве а - спектр некоторого элемента открытого текста, то получим математическую модель рюкзачной системы защиты информации

Подчеркнем, что в целом детали комбинированного использования теории защиты информации с теорией кодирования еще недостаточно проработаны, хот я на пракшке такие модели имеются. Так, например, разработанная Мак-')лисом матсмашческая модель защиты информации имеет сходство с моделями рюкзачного типа, основанными на плотных рюкзаках, в которой исполыу-клея коды Гоппы, обнаруживающие и исправляющие I >1 ошибок.

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

бор, как отмечал К, Шейном, связан с задачей, которая содержит диофантовм трудности (до недавнего времени никто не строил СЗИ по такому принципу),

В 1982г, Л, Шамир нашёл полиномиальный по размеру стандартного рюкзака Кя алгоритм решения задач о рюкзаке типа Меркля-Хеллмана, а потому соответствующая рюкзачная система защиты информации (РСЗИ) не может считаться надежной системой с открытым ключом. Заметим, что все задачи о нестандартных сверхрастуших рюкзаках также имеют полиномиальную сложность Бр =» п0"\ и достаточно легко построить алгоритм их решения. Однако возникают большие трудности при разработке алгоритмов решений, задач о рюкзаке с плотным или другими типами рюкзаков К<-, Кц и КР,

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

Подытожив все затронутые выше нерешенные теоретические и практические задачи теории защиты информации, можно констатировать, что на данном этапе развития ТЗИ уровень прикладных достижений теории кодирования и теории защиты информации не соответствует уровню достижений современной алгебры и теории чисел, В частности, недостаточно полно используются результаты исследований ^-полных задач, а именно: задач построения полиномов с заданными свойствами в полях Галуа, задач рюкзачного типа при моделировании стойких систем безопасной передачи данных по дискретным каналам с заданными характеристиками, сочетающими одновременно функции как передачи, так и зашиты информации, С другой стороны, современные результаты алгебры и теории чисел не в состоянии обеспечить удовлетворительное решение многих практических задач теории защиты информации, в том числе с обнаружением и исправлением канальных и других ошибок, поступающих извне, Поэтому, исходя из сложившегося к настоящему времени состояния развития теории систем защиты информации, можно сформулировать следующую важную проблему научного исследовании; построить на основе ЫР-полных задач эффективную, содержащую диофантовы трудности, математическую модель СЗИ (в частности, полналфавитпую) с обнаружением и исправлением, как аппаратно-канальных, так и других ошибок, поступающих извне.

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

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

Оснопнпя идея диссертационного исследовании заключается в реализации (хотя бы частичной) положения К, Шеннона, который считал, что иаи-

большей неопределенностью при подборе ключей може1 обладать С $11, содержащая диофантовы трудности.

Для достижения поставленной в диссертации цели потребовалось решить следующие основные задачи.

1) обобщить известные результаты по разработке )ффективных методов построения в явном виде полиномов с заданными свойствами в полях Галуа На основе полученных результатов предложить циклические корректирующие коды;

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

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

4) развить и обобщить основные результаты теории асимметричных стандартных рюкзачных систем и предложить математические модели СЗИ на основе обобщенного, универсального и функционального рюкзаков,

5) на основе числовых равносильных рюкзаков построить математические модели полиалфавитных СЗИ с обнаружением и исправлением ошибок.

Научная новизна исследования заключается в следующем:

1) разработаны рекуррентный и другие алгоритмы построения полинома деления круга Х„ (х), которые удобно использовать при больших п, имеющих два и более простых нечетных делителя. Эти алгоритмы допускают эффективную реализацию па ЭВМ. Был построен класс корректирующего циклического кода на основе полинома Х„(х) и арифметических AN-кодов со специальными генераторами;

2) разработаны конструктивные методы построения в явном виде неприводимых в Г,, полиномов заданной степени. Предложен алгоритм факторизации полинома па основе представления его с помощью базисных элементов :iu, ai,..., я,,., кольца Fp|x|;

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

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

ся в том, что в большинстве случаев сами параметры имеют невысокий показатель, равный I или 2;

5) предложены новые методы построения нестандартных рюкзачных О И с повторениями и без повторений компонентов рюкзака. Разработаны нестандартные РСЗИ на основе обобщённого, универсального и функционального рюкзаков, введенных автором;

6) построены математические модели систем защиты информации в классе МР-полных задач на основе нормальных и других многопараметричсских решений многостепенных систем диофантовых уравнений заданной степени;

7) разработана теория асимметричных рюкзачных систем защиты информации, На основе равносильных рюкзаков построена математическая модель полиалфапитпой СЗИ с обнаружением и исправлением ошибок.

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

Теоретическая ценность работы состоит в разработке:

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

- новых и в обобщении известных методов параметризации многостепенных систем диофантовых уравнений;

- новых методов нахождения числовых решений многостепенных систем диофантовых уравнений типа Тарри-Эскота;

- теории нестандартных рюкзачных систем защиты информации.

Практическая ценность работы состоит:

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

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

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

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

- в построении системы защиты информации, содержащей диофантовы трудности, на основе положения К, Шеннона,

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

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

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

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

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

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

Результаты диссертационного исследования послужили основой для практических рекомендаций, используемых в Краснодарском высшем военном училище (военный институт) имени генерала армии С М. Штеменко при проведении практических занятий по дисциплинам «Криптографические методы п средства обеспечения информационной безопасности» и «Элеметы теории сложности криптозрафических алгоритмов», а также при чтении лекционного курса «Синтез и анализ криптографических алгоритмов Основные принципы построения криптоалгоритмов» (заключение прилагается) Комплекс программ для О ВМ (свидетельство № 2005611707) внедрен в практику и используется при подготовке и переподготовке специалистов ОВД в Краснодарской академии МВД России (акт внедрения ирилагаетсч) Математические методы и модели, разработанные в диссертации, используются в учебном процессе на факультете прикладной математики КубГУ в рамках спецкурса «Теория и практика передачи информации» (заключение прилагается)

Апробация работы. Результаты диссертационного исследования и основные научные положения работы докладывались и обсуждались на Всесоюзной школе "Конструктивные методы и алгоритмы теории чисел" (Минск, 1989 г.), на Международных конференциях "Современные проблемы теории чисел" (Тула, 1993 г., 1996 г., Воронеж, 1995 г.), на Международных конференциях "Алгебра и теория чисел: современные проблемы и приложения" (Тула, 2003 г., Саратов, 2004 г., Одесса, 2005 I ), на Международных научно-практических конференциях по информационной безопасности (Таганрог, 2003, 2004, 2005, 2006 г.г.), на Второй Международной научно-практической конференции "Исследование, разработка и применение высоких технологий в промышленности" (Санкт-Петербург, 2006 г.), на V Международной научной конференции «Ломоносовские чтения» (Севасюполь, 2006 г.), па VII Всероссийском симпозиуме по прикладной и промышленной математике (Кисловодск, 2006 г.), па Всероссийской научно-практической конференции "Современное Российское общество: проблемы безопасности, преступности, терроризма" (Краснодар, 2005, 2006г.г.), на I, II региональных межведомственной конференциях по защите информации (Краснодар 2000, 2003 гг.), на межвузовской научно-практической конференции "Информационная безопасность при использовании средств вычислительной техники" (Краснодар, 2003 г ).

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

собия [22, 33, 43], двенадцать статей [32, 41,45, 46, 47, 49, 57, 58,59, 60, 61, 62], входящих в перечень ведущих научных журналов, рекомендуемых ВЛК для опубликования основных научных результатов докторских диссертаций и сорока восьми различных публикаций в журналах и сборниках.

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

Структура и содержание работы. Диссертационная работа состоит из введения, шести глав, заключения, библиографического списка, содержащего 223 наименования, и двух приложений. Она изложена на 320 страницах машинописного текста.

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

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

Обсуждаемые в работе модели преимущественно основываются на применении многостепенных систем диофантовых уравнений.

Пусть N (»1X1 + ЯаХ2+ ... + а„х„ = ш) - число целых неотрицательных решений линейного диофантова уравнения

Я|Х| + Я2Ха+... +п„х„Н!т, где свободный член т и все коэффициенты а„ - натуральные числа.

Приведена задача Рк - построения числа 1У(Я|Х( + а2хг + ... + апх„ = ш) для произвольного п и больших ш:

N (Я|Х| + а3Х}+... + а„х„-ш)- Йнгхсс:;;:'.., -С,";.";'„,.)+ О(^),

11*0

где а„ определяются из треугольной системы линейных уравнений , .

сх„ =(-!)"/Р,„

¿«.АГ Е

;,„) =

11-1) к, ^ +к, , 1-й

1 = 1,2.....и - 2.

Здесь А" = 1. и,а,,...,ап)- симметрическая функция коэффициентов

а,,...,ап, старший член которой равен

С помощью данной модели, опираясь на оценку числа решений для заданных простых параметров р, <|, г, таких, что р+ц > г, р < (| < г, в главе VI строится пример, опровергающий гипотезу Н.Г.Чеботарева о свойствах коэффициентов полинома деления круга Х,1<1Г(х).

Приведено решение задачи выбора оптимального кода, предложенное Р Р. Варшамовым, который, введя в рассмотрение специальные диофантовы уравнения, получил оценку для максимально возможного числа сигналов в кодах с коррекцией различного рода сгруппированных (пачек) ошибок произвольной длины и интенсивности Это решение сводится к нахождению нулей функции \'11,,1(1)> где и > (I, ц > О, Ь й:0 - целые числа и

Функции К„,,,(Ч) и У1| (1(Ч) имеют важное значение в теории кодирования для установления мощностей некоторых специальных, наиболее эффективных, несимметрических корректирующих кодов, и в кибернетике, в частности, на их основе доказывается ряд свойств, связанных с классическими функциями аддитивной теории чисел

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

+ X 2 + ... + X ™ = У Ч + у ^ + ... + у ¡;, , к= 1 ..и, 1КП1

Отмечено, что важность ^-полных задач (в частности, задач Р(,, 1\\, Р» и других) состоит в том, что в теории защиты информации многие симмефичныс алгоритмы и алгоритмы с открытыми ключами могут быть взломаны »а недетерминированное полиномиальное время К таким системам защиты информации относятся СЗИ на основе нестандартных рюкзаков (в частности, на основе !<(„ Кц, К|. и других), разработанные автором в пятой главе диссертационной работы Подчёркнуто, что выбор подходящей гадачн 1*1 (экспоненциальной сложности) позволит смоделировать модель М^ системы безопасной передачи информации с нужной стойкостью = ес,(|" и особенно, если этот выбор связан

П<",И' П аЦ1, а:Г'-"=а„(а,.-1)(а,1-2)...(ао-кц).

^М-К^О-тах^йН, Кв,(1)= £

I.

с задачей Гц, которая содержит диофантовые трудности. Задачу Р|> в вычислительном плане можно назвать сверхтрудной задачей.

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

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

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

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

Отмечено, что для достижения поставленной цели диссертационной работы необходимо:

1) построить математическую модель циклических кодов на основе предложенных методов построения в явном виде полиномов в полях Галуа с заданными свойствами;

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

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

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

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

личных подстановок, в частности \->\'" Особое внимание уделяется исследованию полиномов деления круга Х„(\) над полями Галуа, для которых разработаны различные методы их построения

Предлагается удобная для практических приложений математическая модель циклических кодов длины п с исправлением одиночных и двойных ошибок с порождающим полипомом Х(|(х), d|n и описывается модель арифметических AN-кодов для специальных генераторов 2р +1, 4р +1, 4" + I идр

Пусть Х„(х) =J^[(x""1 - I)''''"- полином деления круга, являющийся дели-

d|n

телем *" - 1 и имеющий своими корнями все элементы поля Галуа Fq одною и того же порядка Метод полного разложения полинома х " - I в F4 хорошо известен Однако в большинстве случаев на практике целесообразно сначала разложить х 1 в произведение круговых полиномов, а затем рассмотреть дальнейшее их разложение на неприводимые множители над полем Fq. Построение полинома Х„(х) в явном виде по указанной формуле при больших п, имеющих два и более простых нечетных делителя, не равных между собой, связано с трудоёмкими вычислениями. Отметим, что в числителе и знаменателе этой формулы (т.к. íí(tl) = ±1) при содержится соответственно

i + ci +c4k+... + c;|k,í| и с'+ ги-|,к

двучленов, число которых с ростом п быстро растет и, следовательно, указанная формула становится не пригодной для практического применения Приведён рекуррентный метод построения полинома Х„(\) в поле F,„ требующий, по сравнению с другими известными методами, значительно меньшего числа арифметических операций и допускающий эффективную реализацию на ЭВМ. Данный метод позволяет задать Х„(\) в поле F,, в виде следующего выражения Xp,pJ...Pk(x)=(-I)"'Q„11Xp1pí...pk,(xl")+(-l)""l>m,Xp)p!...pt2pk(V>"), IV, =[-Va2'™'ai..-i]»Q...-i =[a2->aj>—-я,«-!скобки Ойлера, а (а„ и2,..., а„) - непрерывная дробь частного Р,„ / Q,„.

Приведен новый алгоритм нахождения коэффициентов а„ полинома Х„(х) и степенных сумм S, = S, n = <x¡ + cXj ч-----его корней, который легко программируется и сводится к модифицированному варианту схемы Горнера:

Л„=\Д„ ,-<u-l)0>A ^(«-¿ЖА ,-... 2(s„ ,A,-su)...),A„ = l ,

где

О 2

О О о о

s ч 2 *•• Ч

Указанные методы построения полинома Х„(х) позволяют предложить удобную для практических приложений математическую модель эффективного помехоустойчивого циклического кодированияна основе порождающего полинома g(x) соответствующего кода, представляющего произведение некоторого числа полиномов деления круга; ■

е(х)=Пхч(х)< <Чп. ii

Так, например, если п - показатель полинома X,i(x), tl|n, n * 3k, то X,i(x) порождает двоичный код длины n с исправлением одиночных и двойных ошибок, а в случае g(x)®Xi(x)Xrt(x), meord^^ipid)- циклический (n, п-т-!)-код с минимальным расстоянием не меньше шести.

Рассмотрены различные приложения теоремы Брауна для описания модели арифметических AN-кодов с исправлением одиночных ошибок, Для М(Л, ri) (максимально возможного числа кодовых слов арифметического AN-кода) определены его значения в случае простых генераторов 2р +1, 4р +1,4"+ I и др.

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

Предложены эффективные алгоритмы факторизации полиномов, которые основаны на применении аппарата формальных степенных рядов в Fp^x), результатов теории числовых и функциональных цепных дробей. Разработан операторный метод построения неприводимых в F,, полиномов заданной степени, рассмотрены приложения указанного метода к задаче факторизации двучленов и других полиномов специального вида. Показано, что приведенный способ факторизации полиномов над Fp с незначительными изменениями легко распространяются на случай поля Fn, где q - р1,1 Ь2, Приведен алгоритм построения неприводимых в F4 полиномов с заданным периодом, основанный на известном разложении полинома n поле Галуа, Предложен метод целых перестановочных функций, сохраняющих приводимость в Fr Разработан алгоритм построения неприводимых полиномов методом анализа.

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

VD(x)^(яо(х), я|(х),..я||/2|(х),.... я,(х), 2я„(х))), где D(x) - полином четной степени над Fp, то если:

- длина периода разложения л/Щх) в цепную дробь над F, равна I»2k +1,то D(x)»a¡„W + Bí„(х), (а,.,(х)^,,(х)) = I ;

- длина периода разложения ^о(х) в цепную дробь ikiaf, равна! » 2к + 2,то

D(x) = pt,1(x)(i-|ik.1(x)a^1(x) + pk(x)),ak,2(4) = ak(x),2a1<h,(x) = akil(x)pk,1(x), где г - решение уравнения 4r = I над Fr, a(x), /3(х) - неполные частные.

Из этого результата непосредственно следует утверждение- если разлагается в цепную дробь с четной длиной периода I = 2U+2 и deg рк+1(х)>1, то полином D(x) приводим над полем К,, и можно выделить, по крайней мере, два множителя 1)(х) над Г„.

Автором предложен операторный метод, который позволяет па основе заданных элементов a0(.v), ai(.v),..., а,,_,(х) из кольца Fp[\| исследовать проблему факторизации полинома f(x) и смежные с ней задачи

Пусть {Ь„} - последовательность элементов х], удовлетворяющая условию b„ = \rtav (х) для и где v - наименьший неотрицательный вычет числа и по модулю р и 0!= |р~'и|. Последовательность {Ь„} будем называть нормальной, если в кольце Fn|x| выполняется условие:

gx"-"-,a„(x)|,=f(x)!', 11 = 0

где f(x) - некоторый полином над полем F„. Введен в рассмотрение класс операторов,

Ло, А],..., Ар_1,

областью определения которых являются элементы кольца F„[x|. Будем говорить, что над полиномом g(x) = ¿g„.\°H3 F,,lx| произведена операция Av.

О <\ <р — 1 и писать s(x)Av, если g(x)Av= Л g ц а „,, (\). По определению, для

(1*0

любого натурального числа к полагаем

Akv = (Ak-|)Av, А," = Е, где Е - единичный оператор. Доказано, что если А(х), В(х) - два произвольных полинома из Fnfx|, делящихся на полином D(x)eF„[x|, то полином

Ш = ((А(х) В(х) "-') <"-",|/" также будет делиться на полином П(х). Многократное применение этого результата при

B(x) = f(x), А(х) = хр~ — 1

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

A,,„(x) = (A„n,-AI)V", Г(х)) степени не более п является произведением всех простых делителей f(x), степень которых делит число ш. Откуда, в свою очередь, следует утверждение: для любого натурального числа m полином А.т(х) является произведением всех простых делителей полинома f(x) степени m, т е

(11 m d *m

Доказано также, что если степень d любого простого делителя полинома

rjx) =х'Чх+1

делит число 2к, но не делит к, т.е. 2 Л1Г1 2к, то п кольце Р3|х| имеет место следующее разложение:

fuW-n'^'-'w. illlh iltk

где lkM,"(x) - произведение всех <h(d) различных неприводимых над полем Fj делителей полинома fk(x) степени il.

Отсюда можно заключить, что для любого натурального числа d|2k, удовлетворяющего условию 2/Кг'2к, имеет место равенство

« »[и

где t|,(d) - общее число всех различных неприводимых над Fj делителей полинома

fk(x)« Х2"+Х+1

степени d.

Рассмотрено приложение данного метода к задаче факторизации двучлена f(x)« х" - я, n > I, я б F„\ (п, р) = 1

над полями Галуа.

Приведен алгоритм факторизации неприводимых над Fn полиномов заданного периода pt.

Пусть р л q - простое число, v " ortl (q, р) (ord(u,v) к показатель, которому и принадлежит по модулю v), f(x) ~ простой над Fn полином степени п Ы периода t, ф(х) - полином степени п удовлетворяющий условию ф(х{') «О (mod f(x)). Тогда полином

h(x) » ф(хрЩхГ1

представляет собой произведение (р—t)(nt»')i'"1 неприводимых над Fq' полиномов, период каждого из которых равен pt, ". • -

Приведены результаты факторизации полиномов методом'анализа, изучены свойства неприводимых f(x) полиномов при различных подстановках, в частности, при подстановках x->(x + M(x)f(x)) для различных М(х) е Fp|x|, М(х) * О,

Для составных полей Галуа найдены условия существования перестановочных целых функций f(x) и предложен метод подсчета их числа Nn,'„ (f(x)), •

Пусть F(|- поле Гплуа порядка q я р ', I 2:1 и х |, х },.. ., х q - все его элементы,а

s=ix,g(x)i4х;.х/ *'' V А

- подстановка элементов поля Fq, порожденная перестановочной функцией g(x)eF4|x|, Доказано, что целая функция

R(*)= £«„*"' 1 Sni Sq-1, g(x) e l\, [x|

является перестановочной в поле Гч тогда и только тогда, когда определитель Л (йо» Км ■•• ' В,..) системы линейных уравнений

Ф„(»„>»,»-.», ,) = °> 11 = 1 --Ч. получаемых из тождества

не равен нулю

Для NPi,, (f(\)) - числа перестановочных в F,, целых функций f(x) степени п, показано, что

Получены рекуррентные формулы относительно числа N,, „ (Г(\)) для р = 3, 5 и других значений. Последние результаты используются в главе V для задания перестановок при программной реализации алгоритмов генерации поточных шифров, в частности, при построении алгоритмов безызбыточного кодирования перестановок, разработанных JI К. Бабенко и другими авторами.

Четвертая глава посвящена теоретическому исследованию и нахождению параметрических решений многостепенных систем диофантовых уравнений вида

\ * + \ \ + ... + х = у * + у ) + ... + у , k = 1 .. 11, n < т, или в компактной записи

встречающихся в проблеме Таррн-Эскота, поставленной ещё в 1912 году Решением диофантовых уравнений занимались выдающиеся математики XVII-XIX веков Л. Эйлер, К.Ф Гаусс, П Л. Чебышев и др. В наше время в области диофантовых уравнений значительных успехов добились И.М Виноградов, Д К. Фадеев, Б.Н. Делоне, А.А Карацюба, В.Г. Спринджук, О.Т. Аванесов, A.B. Малышев и др.

Так как при n ära указанная система имеет лишь тривиальные решения (совокупность ai, а2,..., а,,, значений переменных х i, х 2,..., х 1П отличается от совокупности Ь,, 1>2, Ь,„ значении переменных у м у >,..., у „.лишь порядком следования), то исследуются только решения многостепенной системы диофантовых уравнений n-ой степени, для которых и < in.

Подробно изучены следующие многостепенные системы:

Ii

х,, х j,xm —у,, у 2,..., у

н

* I ' х 2 ' •••' х л . I 1 v и .1 — У | ' У I » — * У а ► I ' У

(называемые почти идеальными), и

^I'11!.....x„, =У|0',.....У„.,

(называемые идеальными или нормальными).

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

V , = \ , (а, Ь,..., с), у , = у , (а, Ь,..., с), а, Ь,..., с, \„ у, е N, i = 1.. in, на основе которой можно получить решения ai, а2.....а„„ b,, Ь2,. .. , Ь1П в натуральных или целых комплексных числах:

a,,a2,...,am = b,,b2,...,bm , п < m.

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

Предложено следующее обобщение известной теоремы Фролова- если

и

а,,а2, ...,am = Ь,, Ьг, ..., Ь„,

— какое-либо частное решение многостепенной системы n-й степени (n = 2k - 1 или и = 2к) от m переменных

m m

ii i»i

для которого выполнятся соотношение

|](а1Ь1)Ча,-"-Ь; !,) = 0,

ici

где натуральные числа г и 1 пробегают все без исключения натуральные числа в границах 1 ^ г < к - 1, 2r + 1 £ 1 < и, а и b - отличные от нуля и неравные между собой произвольные целые числа, то

а»! + bb|, аа2 + bb2,..., аа„, + bb,„ = bai + abb ba2 + abj,..., ba„, + abnl является двупараметрическим решением указанной системы.

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

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

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

Приведены методы параметризации указанных систем уравнений для различных значений ш и п. Нормальные многостепенные системы диофантовых уравнений частично изучены Ж, Черником, Г.Л, Дорвартом, O.E. Бровном, А, Глоденом, О.Н, Осипяном и др. Рассматривается построение решения нормальной системы диофантовых уравнений 3-ей степени

л

Х|»Х,.*Л»Х<ВУ|»У1»У)»У<

на основе равенств двух целочисленных и целозначных функций:

f„ (а, Ь, с, d) » (ар +bq)" + (bp +cq)" + ( ср <+dq)" ■=■ (dp + aq)" , g„ (я, b, c, d ) я (aq + bp) n+ ( bq + ср)и + (cq + dp)" + (dq + яр)". Пусть я * с, b л d, |р| * |q|, я, b, с, d, p, q e Z, тогда если:

1. я + снЬ+d , то fB(fl,b,c,d)=> g„ (a,b,c,d) при n я 1,2, 3, что доставляет многопараметрические решения нормальной многостепенной системе диофантовых уравнений

*;+...+*; -у;+...+у; f i»=I, 2,3,

j

наименьшее из которых 1,4,5,8=2,2,7,7.

2. a' + ac+c'ab'+bd + dVro fn(fl,b,c,d)» g„ (a,b,c,d) при n » I, 2, 4, что

доставляет многопараметричсскис решения многостепенной системе диофан-тофых уравнений

. х"+...+х; =у;ч...+у;,и«1, 2,4, наименьшее из которых 3" +10" +13" +19" =5" +6" +17" +17",

Пусть я,,а,,... ,я^,Ь,,Ь,,... ,Ь6- частное решение многостепенной системы пятого порядка

¿>1-2>1, II »1,2, 3,4, 5,

причем

2ХМак-Ьк) = 0, ¿»кьк(«;-ь:) = 0.

к I к 1

2ХМ»г-ь;) = 0, Еа;ь1(а,-Ь1)=0

к I к I

1 опы для произвольных а,Ь е Т., (а,Ь) = 1, аЬ * 0 справедливы равенства ¿(ака + ЬкЬ)" = ¿(Ька + акЬ)", п = 1, 2, 3,4, 5.

к I к I

и

6 6

£(ака + ¡ЬкЬ)" = £(Ька + ¡акЬ)", п = 1, 2, 3, 4, 5,

к 1 к I

где I *= — 1.

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

в

2а + ЗЫ,За + 6Ы,4а + 2Ы,6а + 8Ы,7а + 4Ы.8а + 7Ы=

ч

=3а + 2Ы,6а + ЗЫ, 2а + 4Ы,8а + 6Ы,4а + 7Ы,7а + 8Ы.

*

В частности, из решения I, 6, 7, 17, 18, 23 = 2, 3, II, 13, 21, 22 следует общее двунараметрическое решение:

а + 2Ь,6а + ЗЬ,7а + 11Ь,17а+13Ь,18а + 2!Ь,23а + 22Ь=

=2а + Ь,За + 6Ь,11а + 7Ь,13а + 17Ь,21а + 18Ь,22а + 23Ь

Приведён также метод решения системы 5-й степени

< + х;+...+=у; + у;+...+. исходя из двух частных решений друго! о уравнения х,4 + х® +... + х^ = у4, решения которого сравнительно легко найти* х, = 751)5—а5, х3 = 25Ь'! + а5, х3= -25Ь5 + а\ х4 = 1 0а31>\ х,= 50а1)\ у = 75Ь5+ На основе двупараметрического решения последнею уравнения получены серии решений для исходной системы 5-й степени. Вот одно из возможных многочисленных её решении:

X, = 75гч-К20, хг = 25г"+ .ч2и, х, = -25г" + ч4= юЛ12, х5= г10+75ч*, у, = 75^-г", у2 = 25*5 + Г20, уз—гбь"1 + г20, у, = Юг12*2, у, = ч!" +75г\ Указаньг методы построения двупараметрических решений многостепенных систем диофантовых уравнений в натуральных числах путем сведения этих систем к нормальной системе, содержащей уравнения меньших степеней. Например, систему уравнений

х" + у" + г" = ч" + V11 + уу", п = 2, 4, /. Ф х+у, * и+у, (х, у, г, и, V, \у) = 1 можно свети к нормальной многостепенной системе 2-го порядка*

X, У, Ъ ^ и, V, \У,

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

х « Зя2Ь(а1 + 2Ь2), и ЗяЬ2(2а2+ Ь1),

у " я(2я4 + 2я21>2 + 5Ь4), V = Ь(5я4 + 2я2Ь2 + 2|Д

г - 2Ь(я2 - Ьг)(2яг + 1>2), и- = 2я(я2- Ьг)(а2 + 2Ь2), (я, Ь) = I и

144,841, 1225 « 400,441, 1369.

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

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

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

Одна из основных модификаций СЗИ основана на задаче моделирования равносильных рюкзаков размерности ш степени п, которые определяются в диссертации следующим образом: два рюкзака А = (Я|, яг,..., я„,) и В »(Ь|, 1>2, ..., Ьга) размерности ш &3 равносильны между собой и имеют степень п, если они являются решением многостепенной системы диофантовых уравнений п-й

п

степсниразмерностит:х|,х,,...,хт = УцУ,,»чУ„ . Равносильность рюкзаков А и В обозначается

IV п

Л я В ИЛИ (я 1 , Я 2 I • ■.« я ,„) Я (Ь I , Ь 2 ,..., Ь ,„), 1 <п < ш,

п

Очевидно, относительно введённого бинарного отношения А =■ В выполняются следующие три свойства эквивалентности:

п

1. А => А (рефлексивность);

п п

2. Если А а В, то В = А (симметричность);

ПН п

3. Если А == в, В и С, то А = С (транзитивность).

Например, следующие двупараметрические рюкзаки размерности ш = 5

равносильны между собой и имеют степень п = 4:

j

(I9a+b,15:i+5b,l ln+9b,3a+17b,2a+18b) = (a+I9b,5a+15b,9a+l lb,17a+3b,18a+2b).

Из данного соотношения можно получить сколь угодно много равносильных числовых рюкзаков размерности in = 5 степени п = 4, придав свободным параметрам а и b различные целые, в частности, натуральные шачення Причем, можно подобрать а и b таким образом, чтобы один или оба числовых рюкзака Л и В были инъективными

Изучаются математические модели асимметричных рюкзачных систем защиты информации Мц, для которых предлагается в качестве открытых ключей выбирать равносильные рюкзаки размерности I степени h, где I > m, h > 11 определяются по заданным кри териям канала связи Равносильные рюкзаки могут быть найдены как решения нормальной многостепенной системы диофантовых уравнений h-ой степени, содержащей I переменных, исходя из соответствующего решения н-ой степени с m переменными.

Другая модификация СЗИ с равносильными рюкзачными векторами основывается на указанной выше обобщённой геореме М. Фролова и операции обобщенного сильного модульного умножения. В отличие от стандартного сильного модульного умножения здесь предусматривается ещё и сложение по модулю г > тах{ а, b }, где а > тах{ а,}, b > тах{ b,! с соответствующими ограничениями для операции по заданному модулю.

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

х,,х2,...,х1П = у,,у2.....у„,, 1 <n<m.

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

а I , а 2, • • ■ , ¡1 in = b i , b 2,..., h ,„,

либо и то и другое одновременно.

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

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

\ 2 + k Y : = Р, к = 1,2,3, модель многопользовательского варианта системы защиты RSA, модель полиномиального варианта системы ышшы USA, построенная на основании ре-

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

Все изложенные в работе СЗИ являются новыми и обобщают ранее известные. Они могут найти применение при безопасной передаче электронных данных.

Вводится понятие обобщенно сверхрастущего рюкзачного вектора: А, ■ (а | , а 2,.. . , я „) - обобщенно сверхрастущий вектор, если для любого j = 2 .. n имеет место неравенство

я (P-I)afc.

ь-!

Показано, что обобщенный рюкзачный вектор Af= (я \ , я 2 > • • •. я „) размерности п, it £ 3, является плотным и инъективным, если

« I и с, я, *» р J"J ((р - 1)с + 1), j « 2.. и, где с - некоторая целая положительная константа.

Аналогично показано, что универсальный рюкзачный вектор без повторений

А и (а ,, я 3,..., а „)

размерности и, п & 3, с каскадными значениями

ZC,,=» {m„ mi,..., m„), 0 ¿пц ¿р - 1 для входа (А, v) является плотным и инъективным, если

я, ■=> с,aj и m J((m- 1)с+ 1), j132.. n, m » тях{ Ш|, т2,... ,m„}, тИ,

Множество значений vi, для которых входы (A, vO со спектром 'ACV<= { mlt nij,..., tn„}, имеют решения, назовем допустимыми значениями и обозначим через va { Vo, V|,... vt}, Количество всех допустимых числовых значений v для рюкзачного вектора А обозначим через ц (Уд) и назовем мощностью входа, Так как для одного и того же v могут быть разные решения, то обозначим через ц (А) мощность различных решений и назовем его мощностью рюкзака А, Для инъективного вектора А справедливо равенство

И (VA) я Ц (А) и (m,+l) (nij+I)... (m„+l).

Показано, что для универсального рюкзачного вектора

А (я 1 , я j,..., я „),

с каскадными значениями

ZC,,~ {nit, пъ,..., ni„}, 0 ¿mi :£р - I имеет место соотношение;

2

т,Я| + 1п,я2 +... + т„а„ « -—- V v,,

H(A) S

из которого следует, что если;

I. А - стандартный рюкзак, то ni| т2 и ... ™ т, - 1, ц (А)в2", а, следовательно,

л I 1]

2. Л - обобщенный рюкзак, то т, = т2 = .. . = т„ = р - 1, р (Л)= р" и

2 "С-!

:ь + а2 + ... + а„ = -> v .

Предлагается рекуррентный алгоритм построения универсального пньек-1ивного (нлогного) векгораЛ + 1 размерноеги п + 1 со спектром входа

ХС„= ! 111 ,, 111 .......11 „, Щ „ ц },

если известен аналотчнып вектор А = (а I , а 2, - • • , п „) размеривши и (п >2) В соответствии с алтритмом компонент

а „ + | = П1 , а | т щ 2 а 2 + .,. + 111 „ а „ н а, определяется таким образом, чтобы выполнялось следующее равенство для мощностей:

гдеУ. =М(У + ка|1+1), V +а={у „+ а, V + а,... + а}, аег, т ,еХС,„ * + > кТо V *

¡=1 . . ч, а 2 > а,.

Пусть А= ( а | , а 2 . • ■ • , а „ ) — произвольный универсальный рюкзачный вектор размерности п >3 с множествами коэффициентов повторов ею компонентов и входа (а, v) соответственно.

2К,= { к,, к2,..., к, ( , к, + к2 + ... + к, = п, I < п 7,С,,= { 1111, и12, • • •, т., }, 0 <т, <р - 1, а вектор В = (1> ] , Ь 2 • • • • •> Ь „), Ь , = с а , (пюс1 т), (т, с) = 1, получен из А сильным модульным умножением относительно ш и с. где т > т 1а 1 + т 2а 2 +. . . + т „а „. Тогда решение задачи о рюкзаке для универсального входа (В , ус) совпадаете единственным решением для входа (А,у), что позволяет смоделировать систему защиты информации Мц с открытым ключом на основе задачи универсального рюкзака Кц, следовательно, построить соответственно;

- модель М<, на основе стандартною рюкзака при Ш| = ш2= .. .= т„ — 1, модель Мо на основе обобщенного рюкзака Кц, при 1111 = т2= .. . = т„ =

р-1

Предлагается модель М\\ ващщы информации рюкзачного типа на основе р- ичною кода Варшамова

Wl, = { \ , х2...х„I \У = Х|х1=а(пшип+1), \„еВ = { О, I.....р-1 },аег },

¡ >

в которой для установления взаимно-однозначного соответствия между >ле-ментарными сообщениями I и числовыми эквивалентами е применяется р-ичпый код Варшамова \У„ В частности, при р = 3, п = 6, а = 0 имеем следующий код XV,,, состоящий из 105 кодовых слов, первые 30 из которых (их можно применить при кодировании букв английского алфавита) имеют вид

000000 000112 000120 000201 001011 001100 001212 001220 002022 002111 002200 010002 010010 010122 010211 011021 011102 011110 011222 012001 012121 012202 012210 020012 020020 020101 020221 021000 021112 021120. Код \Уб является 3-ичным равномерным нелинейным кодом. Он одновременно обнаруживает и исправляет ошибки типа +1 или-1.

В отличие от модели классической рюкзачной системы Мц, в которой при определении V для входа (А, V) те или иные компоненты рюкзачного вектора А либо присутствуют, либо нет, здесь рассматривается случай, когда они могут повторяться заданное число раз в зависимости от числа р Ь2, В качестве рюкзачной функции преобразования открытого текста Т для данной модели М\у определяется обобщенная рюкзачная функция 1',,(х) ■» ВрУУх, где ХУх - шифр Варшамоваэлементарного сообщения х, а вектор В,,-открытый ключ.

В данной главе кроме моделей Мо и Мц систем защиты информации на основе задач Ко и Кц приводится модель М,? системы защиты информации на основе задачи КР - о функциональном рюкзаке

А(х) •» (а 1(х), а 2(х),.... а „(х)),

элементами которого являются теоретико-числовые функции от одной и той же переменной х, определённые п некоторой натуральной области ее изменения Х»{х}. По логической структуре данная модель Мр мало чем отличается от моделей Мо и Мц, Разница заключается лишь в том, что для данной модели множество значений Хе,{х} позволяет устанавливать дополнительные ключи (так называемые переменные ключи) при прямом и обратном преобразовании данных, Кроме того, с помощью функционального рюкзака А(х) можно задать многие плотные и сверхрастущие числоные рюкзаки, рассмотренные в литературе:

А(хп)•» (а,(хо), я2(х0),..., а„(х0)).

Например, если функциональный рюкзак с одной переменной имеет вид А(х) (х, х + 1,2(х + 1), 4(х + 1), ..., 2 (х + 1)), то для каждого натурального х х0 он является плотным и одновременно сверхрастушим.

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

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

А(Х|,Х1,..., х()»(Я|(Х|, х2,... ,х(), я2(х<, .......х,),..., я„(х1э х2)... ,х,)),

где Я|(хц х2,... ,Х|), 1 »= 1. .п, I Ь2 теоретико-числовые функции, принимающие, в частности, натуральные значения. Так, например, функциональный рюкзак от двух переменных

А(х, у) = (х, х + у, 2х + у + 1, 4х + 2у + 2,..,,2"-'х + 2"-:(у+ 1))

является сверхрастущим рююаком для каждой пары ншур.шьных ¡начешш \ и у Например, при \ = I, у = 2 рюкзак

А(1,2) =(1,3,6, 12.....5-2"

сверчрастущий для любо| о допустимого п.

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

Преобразование назовем моноалфавитным, если Л* и Р" состоят и! одних и 1е\ же букв и каждой букве соответствует только один шифр В противном случае, когда Р состоит из букв более чем из двух различных алфавитов, - полиалфавитным Полиалфавитпое преобразование называется П-алфавитным, если Р" представляет собой объединение к различных алфавитов, г е.

Р = Р,и Р,... и рк Преобразование будем называть икже полиалфавитным, если одной и той же букве шданного алфавита при прямом преобразовании соответствует несколько шифров, как, например, для шифров Плейфейра или Виженера Систему ¡ащиты информации назовем моноалфавитнои С $ И, если замены шемен-■арных сообщений одинаковы на протяжении всего открытого текста, и полн-алфавитпой С МИ в противном случае.

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

С = (с , , с г ,..., с „)

- произвольный числовой рюкзачный вектор размерности н, и £ 3, компоненты которого расположены в неубывающем порядке своих шачений и для произвольного V некоторые входы (С, V) обладают более чем одним решением. 11усть далее каждому элементарному сообщению i =- v соответствует некоторый спектр = (а | , а 2, . . . , а „) ( возможно, не единственный). Тогда алгоритм построения полиалфавигной системы защиты информации с открытым ключом на основе С совпадает с алгоритмом построения системы ¡ащиты информации со стандартным рюкзаком К>,

Аналогично ¡адается любая полпалфавитная модель МР на основе других ркжгаков Кч, К<., К(, и К|, При лом необходимо учитывать число повторов ХК, и 2С,, для универсального рюкзака

Отмечено, что криптостойкость указанных СШ для больших шачений параметров рюкзачных векторов сравнительно выше, чем для стандартных В самом деле, если обозначить через 1Ч(К) количеспю всех вариантов выбора ключей, ю для стандартного рюкзака оно равно М(К) = 2", для обобщенного рюкика 1<> = Р", а для универсальною рюкшка

2"<:М(К) й(Ш|+1)(т2+1)... (т„+1), где п - длина рюкзака.

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

н

(а |, а а т) = (Ь |, Ь г,..., Ь ,„)

строить два других -

п

(с | , с 2 , . . . , с ,) и («i , , ii , , . . . , (i |)

степени II размерности 1, где И и I определяются, исходя из характеристик канала, Согласно обобщённой теореме М. Фролова, из равносильности двух рюкзаков степени п размерности т

п

(а |, я г,.,., а 1И) = (Ь 1, Ь 2,..., Ь „,), 1 £п < т всегда следует равносильность двух других - тоже степени п и размерности т:

п

(ЯЯ| + ЬЬ|, яя2 + ЬЬ2,аа„+ ЬЬ„) о (|>Я| +аЬ„ 1>я2 + аЬ2,..., 1>я„+ яЬ„), где я и Ь - произвольные целые числа, отличные от пуля и неравные между собой- С другой стороны, на основе теоремы Тарри, из равносильности последних двух рюкзаков степени п размерности т следует равносильность двух других степени п+1 размерности 2т:

пи

(а,, Я2,..., Я„„ 1)1+11, Ь2+11,..., Ьщ+Н) = (Ь|, Ь2,,„, Ь„„ Я1+И, Я2+11,..М я,„+11), где И ~ произвольное целое число,

Аналогично для любого 4 можно указать пару расширенных равносильных рюкзаков степени п + I размерности кв2'т вида

п+1

(а I, я I,..., а к) = (Ь 1 , Ь 2 ,..., Ь к), I Ы, I йМ < к.

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

л

X, ,х2 ,...,хп1 == у, ,у г ,.,.,ут,

а вторая - любое расширение первой: . п п

1. (а |, а 2,..., а „,) я (Ь ,, Ь 2,..., Ь Р11), (или Л= В), I < т;

П*| 11 + 1

2. (с ! , с 2 ,..., с к) ((II , (I 2 1 ■ • • I (I к), (или С = Р), I 5:1, 1 < к,

Тогда задача о равносильных числовых рюкзаках (А, V) (или (В, V)) разрешима, и ей решение совпадает с решением для входа (С, V) (или (И, V)),

Относительно последнего утверждения можно сделать следующие важные замечания при моделировании СЗИ;

1) целесообразно рассмотреть модели открытых С.Ш, для которых чи-

еловые равносильные рюкзаки С = D выступают в качестве открытых ключей,

а соотве!ствепно рюкзаки Л = В закрытых В отличие от стандартного сильного модульного умножения для рюкзачных систем, щесь относительно равносильных рюкзаков С и D можно предусмофеть и сложение по модулю r>m:u{a, b } с соответствующими oiраничениями на операции по заданному модулю г, где а > maxja, {, b > шах jit,},

2) в ¡ависимостн от выбранных значении параметров а и b указанные рюкзаки могут быть как инъекгивными, так и не являться таковыми В случае инъективных рюкзаков следует рассмотреть модели иолиалфавшных С {II В противном случае либо модели полиалфавитных СШ, либо одинаковые шифры исключить из рассмотрения,

3) следует определять значения параметров а и b таким образом, чтобы рассмотренные рюкзаки были сверхрастущими или нормальными. В этом случае соответствующая задача о рюкзаке будет разрешима либо за линейное время, либо она будет принадлежать классу NP-полных задач.

В пятой главе показано также, что если

(а , , а :,. .., а ,„) = (b , , b ,,... , b „,), 1 ¿n < m - два равносильных рюкзака, соответствующих многонараметричсскому решению mhoi остепепнои системы диофантовых уравнений степени п размерности т. то можно смоделировать рюкзачную СЗИ, которая одновременно обнаруживает и исправляет как аппаратно-капальные, гак и внешние ошибки.

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

+ Х5'= у«

н его двупараметрическое решение

X, =751/- :i\ Х2 = а";+ 251>\ Х3 = л*~ 25b\ Х^= lOaV, Xs = 50ali\ У =- a5+75b'. Адресат по полученному искомому шифру, например, Е = 14025517307 определяет сначала соответствующие ¡начения параметров а - 2, 1> = I, воспользовавшись равенством

!is+75b5=l 4025517307|/,=107, а затем и сами решения Xi =74, Xj = 57, Xj - 7, Xj = SO, X<; = 100. После чего легальному пользователю легко построить основной секретный ключ А (7, 57, 74, 80, 100), а затем приступить к восстановлению исходного текста отправителя, имея все необходимое для этого.

В шестой глаис приводятся описания среды реалтации разработанных в предыдущих главах алгоритмов и upoi раммпых модулей В качестве языка программирования исполыуется я ¡ык Pascal 7.0 в среде ОС MS Windows 98

Результаты реализации на ЭВМ разработанных алгоритмов подтверждают теоретические оценки относительно значений коэффициентов полинома Х„(х) и позволяют построить пример, опровергающий гипотезу И. Г, Чеботарева; впервые построен в явном виде полином деления круга Хщ5(х) степени 960 с помощью рекуррентного алгоритма, коэффициенты которого принимают значения;

± 1,0, ±2, ±3,&4,-5, Созданные программные комплексы удовлетворяют практическим требованиям и не накладывает ограничений на степень безопасности передаваемой информации. Можно выбрать один из двух возможных режимов преобразования открытых данных в зависимости от ценности последних. Оба режима строятся на основе проблемы рюкзака с учетом всех параметров рюкзачных систем зашиты информации с целью защиты электронных данных от несанкционированного доступа в сетях ЭВМ.

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

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

1. Осипяп В, О, Об одном рекуррентном методе нахождения полиномов деления круга над конечными полями // Всесоюзная школа «Конструктивные методы и алгоритмы теории чисел»: Тез, докл.- Минск, 1989,- С. 114,

2. Осипяп В, О, Решение в целых числах некоторых диофантовых и систем диофантовых уравнений // КубГУ,- Краснодар, 1979,- 13 с, - Дел, в ВИНИТИ 04.01,79, №91-79,

3. Оеипян О, Н,, Осипян В, О, Новые двупараметричсские решения многостепенной системы диофантовых уравнений Х|П+,,.+Х4Псгу|"+,.,+у,(", п-2,4,6 // КубГУ, -Краснодар, 1985.- 14 е.-Ден. в ВИНИТИ 14.05.85,№ 3639-85,

4. Осипян О, Н., Осипян В, О, О некоторых свойствах многочленов деления круга и их арифметических приложениях // КубГУ, - Краснодар, 1981,- Ч,

1. - 25 с, - Деп, в ВИНИТИ 07.07,81, № 3736-81,

5. Осипян О. Н., Осипян В, О, О некоторых свойствах многочленов деления круга и их арифметических приложениях // КубГУ. - Краснодар, 1981, - Ч,

2.-21 о,- Деп. в ВИНИТИ 07.07.81,№ 3737-81.

6. Осипян О. Н., Осипян В. О, О целых решениях многостепенной системы диофантовых уравнений Х|"+х2"+ ...+хйп=у|п+у2п+ • .■+Уб", пв1,2,3,4 // КубГУ,

- Краснодар, 1982, - 19 с. - Деп, в ВИНИТИ 31.12.82, № 6552-82.

7. Осипян О, Н., Осипян В, О., Об одном способе получения новых многоип-раметрических решений многостепенных систем диофантовых уравнений Х|п+..,+хАу|П+...+У4П, п» 1,2,4 и п»1,2,3 // КубГУ, - Краснодар, 1985,- 16 с.

- Деп. в ВИНИТИ 26.06.85, № 5084-85.

8. Осипяп О.Н., Осипян В,О, Новые миогопараметрические решения многостепенной системы диофантовых уравнений п-~2,4 // КубГУ, - Краснодар, 1993. - 6 с. - Деп, в ВИНИТИ 26,06.93, № 1820-В93,

9. Осипян О.Н., Осипян В.О, Многопараметрические решения многостепенной системы диофантовых уравнений Х|п+„.+Х(1п=У|"+,..+У(,", п=1,2,4 // КубГУ. -Краснодар, ¡993,- 11 с,-Деп. п ВИНИТИ 26.06,93,№ 1821-В93.

Ю.Оснпян В О Об одном меюде определения всех делителей идаинмо сепе-рабельного полинома над конечными нолями // Междунар конф "Современные проблемы теории чисел" Тез. докл - Тула, 1943 - С 1 19-120 11.Осипян ВО Об одном алгоритме к синтезу неприводимых над конечными полями полиномов заданной степени // Межвуз сб. "Вопросы прикл матем. и механики" Краснодар, 1994 - Вып 1 С 13-18 12.0снпян В.О Подсчет числа перестановочных целых функций полей Галуа // Междунар конф "Современные проблемы теории чисел" Tei. докл. Воронеж, 1995 С 119-121 13. Осипян О 11 , Осипяп В О Новые многопараметрические решения многостепенной системы диофантовых уравнений Х|" i тХ5" Y|"+ ьУ-,", п 1,2, 3,5,7 // Межвуз сб "Вопросы прикл матем. и механики" Краснодар, 1995. -Ч. I, Вып. 2. С 11-15. Ы.Осипян О I I , Осипян В О Новые многопараметрические решения мнгогост. системы диофантовых уравнении Х|"+ ..+Xsn=Y,"+ ..+Y5",n= 1,2,3,5,7 // Меж-Byi. сб "Вопросы прикл. матем и механики" - Краснодар, 1995. Ч II, Вып. 2.-С 15-19

15-Осипян О.Н , Осипян ВО Новые двухпараметрические решения многостепенной системы диофантовых уравнений Xnt-Y"+Z" UnbVnbW", n-2,4 в натуральных числах // Межвуз. сб. "Вопросы прикл. матем. и механики". Краснодар, 1995. - Ч. I, Вып. 3. - С. 10-15.

16-Осипян О.Н , Осипян В.О. Новые двухпараметрические решения многостепенной системы диофантовых уравнений Xnt-Yn+Zn-U"i-V"b\V", п 2,4 в натуральных числах // Межвуз. сб "Вопросы прикл. матем. и механики". -Краснодар, 1995 -Ч II.Вып.3.-С 15-21.

17,Осипян В О. Метод перестановочных функций, сохраняющих приводимость полиномов в полях Галуа // Междунар. конф. "Современные проблемы теории чисел": Тез. докл. -- Тула, 1996. - С. 118-119. 18.0сипян ВО. Циклотомические классы и случаи приводимости полиномов деления круга над полями Галуа // Межвуз сб "Вопросы прикл матем. и механики". - Краснодар, 1997. - Вып. 4. - С. 16-20. Ю.Оснпян О.Н , Осипян В О Получение параметрических решений диофантовых уравнении x^t-x?5*- . +X5,=yi5+y;5К . . +У55 , (Х|,\;.....x5,yi,y:, . . . ,

у5)=1 и других//Межвуз. сб "Вопросы прикл матем. и механики". Краснодар, 1997. - Ч. I, Вып. 4. С. 14-19. 20.0снпян О.Н , Осипян В.О Получение параметрических решений диофантовых уравнений X|SbX;Sl. . |S }-y2S ■ • , (X|,X3, . , X^,V|,y:, y<0=l н других // Межвуз сб. "Вопросы прикл матем и механики" Краснодар, 1997 Ч II, Вып 4 - С. 19-21 21.Осипян В О Элементы теории передачи информации: Учеб. пособие

Краснодар, 1998 52 с 22.Камалян Р 3, Осппян В О. Математическое моделирование Учебно-методичсское пособие для студентов всех форм обучения в ИМСИ1 Учеб пособие - Краснодар, 1998 - 64 с. 23.Осипян О Н , Осипян В О 11олучение параметрического решения многостепенной системы диофантовых уравнений п-и степени по какому-либо часг-

кому решению той же системы // КубГУ.- Краснодар, 1999, - Ч, I,- 10 с.-Деп, в ВИНИТИ 29.12.99, № 3896-В99, 24,Осинян О.Н., Осипян В.О, Получение параметрического решения многостепенной системы диофантовых уравнений n-й степени по какому-либо частному решению той же системы, // КубГУ, - Краснодар, 1999,- Ч, II, - 10 с,— Деп, в ВИНИТИ 29,12.99, № 3897-В99, 25.0сипян В.О., Осипян К.В, Система защиты информации на основе решений многопараметрических систем диофантовых уравнений // Сб, тез, докл, per. межвед, конф, по защите информации, - Краснодар, 2ООО, - С. 44-45, 26.0сипян В.О, Об одной криптосистеме с открытым ключом на основе кода Варшамова // V Междунар, конф, «Алгебра и теория чисел: совр, проблемы и приложения»: Тез, докл.- Тула, 19-24 мая 2003, - С, 170, 27,Осипян О.Н., Осипян В.О, Синтез СЗИ на основе многопарамстрическнх решений многостепенных систем диофантовых уравнений // V Междунар, конф, «Алгебра и теория чисел: совр, проблемы и приложения»: Тез, докл, -Тула, 19-24 мая 2003. - С. 172. 28.0сипян В.О., Осипян К,В, Система защиты информации на основе специального рюкзака // Материалы межвуз, научно-практической конф, «Ин-форм, безопасность при использовании средств выч, техники», - МВД РФ, Краснодарский юридический институт, 2003,- С, 40-41. 29,Осипян В,О., Осипян К.В., Спирина С.Г. Система зашиты информации на основе секретного рюкзака // Материалы межвуз, научно-практической конф, «Информ, безопасность при использовании средств выч, техники», -МВД РФ, Краснодарский юридический институт, 2003, - С. 41-43, .Осипян В.О. Об одном обобщении рюкзачной криптосистемы // Изв, вузов Сев.-Кавк, региона, - 2003. - № 5. - С. 18-25. 31 .Осипян В.О., Осипян К.В, Математические основы теории и практики защиты информации: Учеб, пособие. - Краснодар, 2003. - 192 с, 32.0сипяп В.О. Система зашиты информации на основе кода Варшамова // Инф, противодействие угрозам терроризма, - Таганрог, 2003. - № I, - С. 121-123,

ЗЗ.Осипян В.О., Осипян К.В, О математических системах обеспечения информационной безопасности на современном этапе // Сб, тез. докл, II per, Межвед, конф, по защите информации, - Краснодар, 2003,- С. 18-20, 34.0сипян В,О, Асимметрическая система зашиты информации на основе универсального и функционального рюкзаков // Защита информации. Конфидент. - СПб., 2004, б, - С. 61-63. 35.0сипян В.О; О криптосистемах с заданным рюкзаком // Материалы VI Междунар, научно-практич, конфер, - Таганрог, 2004,- С. 269-271. Зб.Осипян В.О, Генерация перестановок с помощью перестановочных целых функций // Материалы VI Междунар. научно-практич, коифер, - Таганрог, 2004.-С. 271-273,

37.0сипяи В.О, О некоторых алгоритмах синтеза неприводимых над Fq полиномов методом анализа // Материалы VI Междунар, научно-практич, коп-фер, - Таганрог, 2004, - С. 273-274.

.38.Осипян В.О Разработка методов построения систем передачи и <ащиты информации - Краснодар, 2004 -180 с.

^ЗФ.Осипяи ВО О полиалфавигной критосисгеме с обобщенным рюкзаком // Изв вуюв Сев - Кавк ротона Спец Вып. «Mai моделнров и компыот. технологии» - 2004. - С 65-66

40.0сипян BOO криптосистемах с ра¡личными рюк гаками // Инф противодействие угрозам терроризма. Таганрог, 2004. №3 С 53-56

41.0сипяи В О , Осипян К.В Криптография в упражнениях и ¡адачах- Учеб. издание. М Гелиос АРВ, 2004. 144 с.

42,Осипян В О , Арутюнян А С. О приводимости полиномов деления Kpyia над

полями Галуа // VI Междунар конфер. «Алгебра и теория чисел совр про, блемы и приложения». Тез. докл Саратов, 19-24 сент. 2004 С 170.

(¿Э.Осипян В.О О системе защиты информации на основе функционального рюкзака//Вопросы защиты информации. - М.2004. №4 _ с 16-19

@Юсипян В О Разработка системы тщиты информации на основе математической модели универсального рюкзака с повторениями // Итв вузов Сев -Кавк. региона. - 20Ü5 - № 2. - С. 12-15.

(45^Ссипян В О Об одном способе нахождения всех простых делителей ¡адан-ного полинома над конечными полями // Вестник (ТУ, 2005. Вып. 43. - С 69-72

46.0сипян В О Моделирование систем защиты информации, содержащих дио-фантовую трудность // Материалы VII Междунар. научно-практич. конфер. -Таганрог, 2005. - С 202-209.

(¡7К)снпян В О , Семенчин Е.Н Построение систем мщиты информации на основе проблемы универсального рюкзака // Изв. вуюв 'Г РТУ, 2005. №4. - С. 182-188.

48.0сипян В О , Арутюнян А С. Моделирование систем шщиты информации, на основе решений диофантовых уравнений // VII Междунар. ,инебр. конфер - Одесса, 20-27 июля 2005. - С. 147-148.

49.0сипян В О. О решениях нормальной многостепенной системы диофантовых уравнений пятого порядка в натуральных и в целых комплексных (гауссовых) числах // VII Междунар. ал!сбр. конфер. - Одесса, 20-27 июля 2005. -С 148-149.

50.0сипян ВО, Спирина С.Г, Арутюнян А.С Модели систем защиты информации на основе универсального и функционального рюкзаков И Всерос. на-учно-практич конфер «Современное Российское общество- проблемы безопасности, преступности, терроризма» Тез докл, - Краснодар, 19 20 мая 2005 С 19-24

51.0ишян В О , Мирчаяп А В Сравнительный анализ криптостонкосш классической и обобщенной рюкзачной криптосистем // Математические методы и информационно-технические средства: Тр. Всерос. научно-практич конфер - Краснодарская академия МВД России, 2005. - С 24-27.

52.Осипян В О , Пашина-Дитмарова Г В Еще раз о uumire информации языки сценариев // Математические методы и информационно-технические средства Тр Всерос научно-практич конфер Краснодарская академия МВД России, 2005 - С. 27-29

53.0сипян В.О., Шелудяков АЛ, Сжатие компьютерной информации с использованием нейросстевых технологий // Математические методы и информационно-технические средства; Тр, Всерос, научно-практич. конфер, - Краснодарская академия МВД России, 2005, - С, 36-38, 54,Осипян В, О., Осипян А,В, Многошифровая система зашиты информации с обнаружением и исправлением ошибок // Сб, трудов II Междунар. научно-практич, копфер, «Исследование, разработка и применение высоких технологий в промышленности», - СПб., 2006, - С, 172-173, 55.0сипян В.О., Арутюпян A.C., Мирзаян Л.В, Моделирование плотного рюкзака на основе функционального // Сб, трудов II Междунпр, научно-практич, конфер. «Исследование, разработка и применение высоких технологий в промышленности», - СПб,, 2006, - С, 86, 56.0сипян В.О., Осипян А.В, Универсальная модель задачи о ранце и ей приложение // Математические методы и информационно-технические средства: Тр, Всерос, научно-практич. конфер, - Краснодарская академия МВД России, 2006,-С. 41-42, @)Осипя11 В.О. Моделирование систем защиты информации на основе равносильных рюкзаков, содержащих диофантовую трудность, с обнаружением и исправлением ошибок // Вопросы зашиты информации, - М., 2006, — № 2, - С, 2-6, (^.Осипян В.О, О системе защиты информации на основе проблемы рюкзака // L,-Изв. ТПУ,- 2006, - №2. ~ Т. 309, - С. 209-212,

(^Осипян В.О, Моделирование систем защип,г информации рюкзачного типа с переменными ключами // Изв, вузов Сев.-Кавк, региона, - 2006, - № 3, - С. 31 -34, (Б^Осипян В. О, Об одном алгоритме построения нормальных инъективных рюкзачных векторов заданной размерности П Обозрение прикладной и промышленной математики, - 2006, - Т, 13, Вып, 4, - С, 694-696. /61.Осипян В, О, Модель СЗИ с сжатием и исправлением ошибок // Изв, вузов Т-ТРТУ,2006.- №7.-С, 192-194,

(о^Юсипян В.О, Моделирование асимметричной рюкзачной системы защиты информации, содержащей диофантовую трудность // Вестник СГУ, - 2006, -Вып, 47,-С. 69-72.

бЗ.Осипян В, О., Воронов П.Е. Модифицированный алгоритм адаптивного кодирования Хаффмана И Материалы VIII Мсждунар, научно-практич. конфер, - Таганрог, 2006, - С. 53-58. б4.0сипян В, О., Мирзаян A.B. Построение системы аутентикации на основе универсального рюкзака // Материалы VIII Мсждунар, научно-практич, конфер, - Таганрог, 2006. - С. 58-60, бЯ.Осипян В, О, Система защиты информации па основе плотного обобщённого

рюкзакп: Программа для ЭВМ, - Свидетельство № 2005611707 от 12,07,05, бб.Осипян В, 0„ Мирзаян А.В, Система зашиты информации па основе плотного универсального рюкзака: Программа для ЭВМ, - Свидетельство Hs 2006610879 от 10.01.06. 67,Осипян В. О. Система шифрования на основе уравнения xl + kyl= р,

к " 1,2,3: ВИТИЦ. - Свидетельство № 70990000172 от 20.12,99, 68.0СИПЯИ В, О, Криптосистема с открытым ключом на основе обобщенного рюкзака: ВИТИЦ, - Свидетельство № 73200300103 от 21.05.03,

Осипян Валерий Осипович

РАЗРАБОТКА МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ СИСТЕМ ПЕРЕДАЧИ И ЗАЩИТЫ ИНФОРМАЦИИ, СОДЕРЖАЩИХ ДИОФАНТОВЫ ТРУДНОСТИ

АВТОРЕФЕРАТ диссертации на соискание учёной степени доктора физико-математических наук

Подписано в печать 13.10.2006. Формат 60х84|,|Ь. Бумага Maestro. Печать трафаретная. Усл. печ. л. 2,09. Тираж 100 экз. Заказ № 6196.

Тираж изготовлен в типографии ООО «Просвещение-Юг» с оригинал-макета заказчика, г. Краснодар, ул. Селезнёва, 2. Тел./факс: 239-68-30.

ВВЕДЕНИЕ.

ОСНОВНЫЕ ОБОЗНАЧЕНИЯ.

I. АНАЛИЗ МОДЕЛЕЙ И МЕТОДОВ РЕШЕНИЙ NP-ПОЛНЫХ ЗАДАЧ.

1.1. Анализ алгоритмов построения полиномов с заданными свойствами в полях Галуа.

1.2. Анализ алгоритмов факторизации полиномов в полях Галуа.

1.3. Труднорешаемые задачи и модели систем защиты информации.

1.4. Моделирование труднорешаемых задач с помощью диофантовых уравнений.

II. МОДЕЛИРОВАНИЕ ЦИКЛИЧЕСКИХ КОДОВ НА ОСНОВЕ Хп(х).

2.1. Рекуррентный метод моделирования полинома Хп(х)

2.2. Численный алгоритм построения Хп(х)

2.3. Вычисление коэффициентов полинома Хп(х)

2.4. Моделирование неприводимых полиномов с помощью подстановок.

2.5. Метод циклотомических классов моделирования Хп(х)

2.6. Моделирование циклических кодов с порождающим полиномом Х(|(х).

2.7. Математические модели циклических AN-кодов.

III. МЕТОДЫ ФАКТОРИЗАЦИИ ПОЛИНОМОВ В ПОЛЯХ ГАЛУА.

3.1. Алгоритм факторизации полиномов над Fp с помощью функциональных цепных дробей.

3.2. Операторный метод факторизации полиномов и смежные с ним задачи.

3.3. Факторизация полиномов с заданным периодом.

3.4. Метод перестановочных целых функций.

3.5. Моделирование неприводимых полиномов методом анализа.

IV. МОДЕЛИ И МЕТОДЫ ПАРАМЕТРИЧЕСКИХ РЕШЕНИЙ.

МНОГОСТЕПЕННЫХ СИСТЕМ ДИОФАНТОВЫХ УРАВНЕНИЙ.

4.1. Основные модели и методы многопараметрических решений.

4.2. Метод решений нормальных многостепенных систем.

4.3. Метод решения с помощью понижения степени.

4.4. Метод решения на основе введения целозначных функций.

4.6. Метод общих решений уравнений n-ой степени.

4.7. Модели и методы решений в целых комплексных числах.

4.7.1. Решение систем второго порядка в целых комплексных числах.

4.7.2. Метод решения нормальной системы третьего порядка.

4.7.3. Метод решения нормальной системы четвёртого порядка.

4.7.4. Метод решения нормальной системы пятого порядка.

4.7.5. Метод общих решений в целых и комплексных числах.

V. МАТЕМАТИЧЕСКИЕ МОДЕЛИ СИСТЕМ ЗАЩИТЫ

ИНФОРМАЦИИ НА ОСНОВЕ NP-ПОЛНЫХ ЗАДАЧ.

5.1. Модель на основе обобщенного рюкзака.

5.2. Модель на основе кода Варшамова.

5.3. Моделирование с помощью универсального рюкзака.

5.4. Моделирование с помощью функционального рюкзака.

5.5. Модели полиалфавитных систем защиты информации.

5.6. Моделирование систем, содержащих диофантовую трудность.

5.6.1. Модель защиты информации на основе конструктивного рюкзака.

5.6.2. Модель защиты информации на основе закрытого рюкзака.

5.6.3. Модель с обнаружением и исправлением ошибок.

5.7. Моделирование асимметричных систем на основе задачи факторизации.

5.7.1. Модель многопользовательского варианта RSA.

5.7.2. Модель полиномиального варианта RSA.

5.8. Моделирование перестановок на основе перестановочных целых функций.

5.9. Метод композиции различных моделей.

5.10. Модель преобразования на основе теоремы Эйлера - Ферма.

VI. АЛГОРИТМЫ И ОЦЕНКИ НА ОСНОВЕ.

ПРЕДЛОЖЕННЫХ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ.

6.1. Оценка значений коэффициентов Х„(х) и гипотеза Н.Г.Чеботарёва.

6.2. Алгоритм защиты информации на основе модели плотного обобщённого рюкзака и его реализация на ЭВМ.

6.3. Алгоритм защиты информации па основе модели плотного универсального рюкзака и его реализация па ЭВМ.

6.4. Алгоритм защиты информации на основе модели функционального рюкзака.

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

Значительные успехи, достигнутые в различных сферах деятельности человека с появлением компьютерных технологий, стимулируют научно-исследовательские работы, направленные на совершенствование существующих, разработку и создание новых безопасных информационных систем. При этом общеизвестно [8,10,12,60,61,134,137,151,165], что в процессе хранения, передачи и обработки информации (в дальнейшем хранение информации будем рассматривать как передачу информации во времени) могут произойти как внутриканальные преобразования (ошибки), так и в целом, по отношению к каналу внешние несанкционированные воздействия на канал. Поэтому для того, чтобы уменьшить или исключить эти нежелательные события вовсе, необходимо представить информацию в таком виде, чтобы она была устойчивой к указанным воздействиям. Другими словами, необходимо на основании характеристик канала выбрать такой способ преобразования исходных данных, чтобы вероятность случайного или преднамеренного искажения передаваемой и обрабатываемой информации была меньше любой-наперёд заданной величины.

Подчеркнём, что если проблема защиты информации в каналах связи от помех решена на достаточно высоком уровне с помощью помехоустойчивого кодирования [34,60,61], то основные задачи компьютерной безопасности, которые связаны с обеспечением конфиденциальности, целостности и доступности информации, обрабатываемой в компьютерных системах, далеки ещё от окончательного решения, хотя в последнее время в этой области появилось большое количество работ [6,7,14,31,46,51,53,64-69,94,105,115,139142,165,205,217 и др.] и их число непрерывно возрастает. Несмотря на определенные успехи в данной области, интенсивные теоретические и практические исследования продолжаются и в настоящее время, и можно с уверенностью сказать, что повышенный интерес к этим работам сохранится в обозримом будущем. Более того, из общей теории информации выделилась самостоятельная интенсивно развивающаяся ветвь - теория защиты информации (ТЗИ), основным предметом которой является исследование возможностей повышения надёжности передаваемых электронных данных по реальным каналам связи. Эта теория, несомненно, имеет большое будущее, так как стремительно расширяется сеть пользователей персональных компьютеров, а вместе с ней повышаются требования к передаваемой и обрабатываемой информации.

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

1. Совершенствование математических моделей передачи информации с целью увеличения её надёжности и объёма передаваемых сообщений.

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

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

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

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

2. Использовать общедоступный канал, но скрыть сам факт передачи конфиденциальной информации.

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

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

Исходя из теоретических положений [31,53,141,165] построения стойких и эффективных моделей систем защиты информации, отметим особо, что все математические задачи являются моделями сокрытия и защиты информации, а решения этих задач соответствуют правильным ключам. Следовательно, выбор подходящей труднорешаемой задачи, в частности, NP-полной задачи, позволяет смоделировать систему защиты информации на должном уровне. Особенно, если этот выбор, как отмечал К. Шеннон [163], связан с задачей, которая содержит диофантовые трудности. В приложении книги [43] собрано более 300 задач, NP-полнота которых установлена. Остановимся на одной такой задаче - задаче о рюкзаке К. Как известно [51], стандартная задача Ks относится к классу NP-поЛных задач и она эквивалентна по сложности задаче о коммивояжере Рк. В частности, если верна основная гипотеза теории сложности, в чём уверено большинство специалистов, то не существует алгоритма А, который бы решал произвольную задачу о рюкзаке за время, полиномиальное по длине рюкзака. Тогда, следуя этой гипотезе [43,51,139] можно доказать NP-полноту нестандартных задач о рюкзаках Kg, Ки и KF [109] на основе методов локальной замены и построения компонент.

В 1982г. А.Шамир [216] нашёл полиномиальный по размеру рюкзака алгоритм решения задач о рюкзаке типа Меркля-Хеллмана, а потому соответствующая РСЗИ не может считаться надёжной системой с открытым ключом. Заметим также, что все задачи о нестандартных рюкзаках со сверхрастущими рюкзаками имеют полиномиальную сложность SP = п0(,) и достаточно легко строить алгоритм их решении [195]. Однако возникают большие трудности при разработке алгоритмов решений задач о рюкзаке с плотным или другими типами рюкзаков Kg, Ки и KF, впервые предложенных автором [106].

Таким образом, для моделирования стойких систем защиты информации необходимо исследование новых труднорешаемых задач РЕ и предложить эффективные модели М СЗИ. Причём, стойкость Ss таких систем защиты информации напрямую будет зависеть от сложности SE труднорешаемой задачи Ре. Поэтому, если задачу Ри можно решить полиномиальным алгоритмом АР, то она принадлежит классу Р и соответствующая модель М будет иметь полиномиальную стойкость Sp.

Так как вопросы защиты информации самым непосредственным образом связаны с методами кодирования, обратимся к краткому обзору результатов исследований в области теории избыточного кодирования. В работах [12,13,17,29,196] разработан ряд конструктивных методов синтеза контролирующих кодов, имеющих большую практическую ценность. Заметим также, что, несмотря на значительный прогресс в изучении теории кодов, недостаточно полно рассмотрены практические аспекты программно-аппаратной реализации полученных новых разработок. К тому же в некоторых случаях больший эффект может быть получен при использовании неоптимального алгоритма кодирования и декодирования, который имеет простую программную или программно-аппаратную реализацию. В этом смысле класс циклических кодов, как важнейший подкласс линейных кодов, является эффективным как с алгоритмической, так и с вычислительной точки зрения - благодаря использованию аппарата полей Галуа.

С другой стороны, как известно [44], имеется прямая аналогия между обычными циклическими кодами передачи информации и циклическими AN-кодами. Причём многие известные циклические коды имеют и арифметические аналоги, хотя нерешенной остаётся задача построения класса циклических AN-кодов, подобного классу кодов БЧХ.

Циклические коды допускают простую техническую реализацию и могут быть использованы для изучения, поиска и построения других не менее эффективных в практическом отношении кодов. Особое внимание в этой связи заслуживают исследования Р.К. Боуза, Д.К. Рой-Чоудхури [13], А. Хок-винхема [196], которые сводят задачу синтеза эффективных кодов к задаче отыскания порождающих полиномов g(x) =]^[(xn/d -1) над конечными поd|n лями, имеющими заданное множество корней. Дальнейшее развитие этой проблемы, и, в частности, задачи построения неприводимых в поле Галуа полиномов отражено в [176,180] и других работах. Наиболее важный вклад в решении данной проблемы внес P.P. Варшамов [17,19-27,30], получивший ряд фундаментальных результатов конструктивной теории приводимости полиномов над конечными полями, введя в рассмотрение специальные диофан-товы уравнения, решил в общем виде задачу синтеза и оценки максимально возможного числа сигналов в кодах с коррекцией сгруппированных (пачек) ошибок произвольной длины и интенсивности [28].

Следует отметить целый ряд новых подходов, включающих методы современной алгебры и геометрии [42], комбинаторики и теории чисел [30], предложенных различными авторами для решения вышеперечисленных задач. Центральное место здесь занимает диофантовый анализ [1,2,3,28,48,172] и, в частности, теория построения систем параметрических решений многостепенных систем диофантовых уравнений [11,78-82,143,144,191,194]. С помощью аппарата диофантового анализа удалось получить решение чрезвычайно важных в практическом отношении задач, трудно поддающихся решению обычными способами [3,48]. Перечислим некоторые из них.

При отрицательном решении гипотезы Н.Г.Чеботарёва [168] о свойствах полинома деления круга Xpqr (х) в работе [48], для оценки числа N (t+ pqz + pry + qrx = n) - целых неотрицательных решений, при исследовании алгебраической структуры периодических рекуррентных последовательностей в [3] были использованы линейные диофантовы уравнения вида aiXj + а2х2 + . + atxt = iri. При изучении недвоичных кодов полезным оказалось привлечение новых для теории арифметических кодов неэлементарных методов теории чисел [44]. Для доказательства квазисовершенности кодов БЧХ, исправляющих две ошибки, в [60] изучается многостепенная система уравнений над x+y+z=a

F . вида: .

Автором предлагается новый подход к построению x3 + y3 + z3 = b. систем, содержащих диофантовые трудности, возникающие при решении многостепенных систем диофантовых уравнений высоких степеней: х1'+х2'+. . .+х„1=у1,+у21+. . .+yn') i=l. -т. При этом, в зависимости от значений основных параметров тип, учитывается либо сложность решения системы, либо сами решения, либо и то и другое одновременно. Особенность таких уравнений заключается в том, что в общем случае неизвестны общие непереборные методы их решения. В то же время для отдельных значений шип эти уравнения допускают параметризацию по одному, двум и более параметрам, т.е. можно получить параметрические решения: х;= Xj(a„ а2,., а,), у-, = у^ , а2,., at), i = 1. ш, Xj е N, у-, е N, из которых следуют конкретные решения в натуральных числах (в общем случае - в целых комплексных (гауссовых) числах). Эта специфика многостепенных систем диофантовых уравнений позволяют нам строить эффективные симметричные и асимметричные СЗИ.

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

WeiP=2P.«, =а(то^т),где Pj- члены заданной числовой последовательности, cii - могут принимать значения, вообще говоря, из различных числовых множеств Aj, (i = 1 . n), aeZ. В частности, совокупность всех бинарных решений сравнения при Pi = I, ш = 2п, а > 0 задаёт код Варшамова, исправляющий одиночные вставки, выпадения и симметричные ошибки [29]. В то же время, если в качестве р взять рюкзачный вектор, а в качестве а -спектр некоторого элемента открытого текста, то получим математическую модель рюкзачной системы защиты информации (РСЗИ).

Подчёркнём, что в целом детали комбинированного использования теории защиты информации с теорией кодирования ещё недостаточно проработаны [142], хотя на практике такие модели имеются. Так, например, разработанная Мак-Элисом [205] математическая модель защиты информации имеет сходство с моделями рюкзачного типа, основанными на плотных рюкзаках, в которой используются коды Гоппы, обнаруживающие и исправляющие t > 1 ошибок. Автором предлагается рассмотреть задачу математического моделирования систем защиты информации на основе равносильных рюкзаков с обнаружением и исправлением ошибок, содержащих диофантовые трудности.

Таким образом, для моделирования стойких систем защиты информации необходимо исследование новых труднорешаемых задач РЕ и разработка на их основе новых моделей М систем защиты информации. Причём, стойкость Ss таких систем защиты информации напрямую будет зависеть от сложности SE труднорешаемой задачи РЕ. Поэтому, если задачу Рц можно решить полиномиальным алгоритмом Ар, то она принадлежит классу Р, и соответствующая модель М будет иметь полиномиальную стойкость Sp.

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

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

В работе отражены последние достижения автора по разработке эффективных информационных систем передачи и защиты компьютерной информации, исследованы различные модели систем защиты электронных данных и предложены новые методы их построения. Для этого проведены достаточно подробные исследования полиномиальных систем в конечных полях и систем параметрических решений специальных многостепенных систем диофантовых уравнений. Особое место в работе занимают теоретические исследования проблемы рюкзака и моделирование соответствующих СЗИ на их основе. В частности, в отличие от математической модели стандартного рюкзака, рассматриваются модели обобщённого, универсального и функционального рюкзаков. На основании указанных типов рюкзаков строятся соответствующие СЗИ, которые являются более эффективными, чем аналогичные стандартные рюкзачные СЗИ, предложенными Р.Мерклем, М.Хельманом, Б.Чором, Р.Ривестом, А.Саломаа и другими авторами.

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

Основная идея диссертационного исследования состоит в реализации сложной по К.Шеннону СЗИ, содержащей диофантовы трудности, позволяющие смоделировать стойкие системы передачи и защиты информации (К.Шенноном отмечалось, что наибольшей неопределённостью при подборе ключей, обладают СЗИ, содержащие диофантовы трудности). Для достижения поставленной в диссертации цели соискателю потребовалось провести соответствующие исследования и решить следующие основные задачи:

1. Проанализировать и обобщить результаты известных работ по разработке эффективных методов построения в явном виде в полях Галуа полиномов с заданными свойствами.

2. На основе полученных результатов предложить циклические коррек тирующие коды, которые удобно использовать на практике.

3. Провести исследование некоторых задач из класса NP, на основе которых смоделировать эффективные системы защиты информации.

4. Разработать новые методы параметрических решений многостепенных систем диофантовых уравнений в натуральных и целых комплексных числах и предложить СЗИ, содержащие диофантовые трудности.

5. Развить и обобщить теорию асимметричных стандартных рюкзачных систем и предложить математические модели СЗИ на основе обобщённого, универсального и функционального рюкзаков.

6. На основе числовых равносильных рюкзаков построить математические модели СЗИ с обнаружением и исправлением ошибок.

Научная новизна исследования.

1. Разработаны рекуррентный и другие эффективные алгоритмы построения полинома деления круга Х„ (х), которые удобно использовать при больших п, имеющих два и более простых нечётных делителя и которые допускают эффективную реализацию на ЭВМ. Был построен класс корректирующего циклического кода на основе полинома Хп(х) и арифметических AN-кодов со специальными генераторами.

2. Разработаны конструктивные методы построения неприводимых в Fp полиномов заданной степени в явном виде. Предложен эффективный алгоритм факторизации заданного полинома на основе представления его с помощью базисных элементов А0, Ai,., Api кольца Fp [х].

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

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

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

6. Построены математические модели систем защиты информации в классе NP-полных задач на основе нормальных и других многопараметрических решений многостепенных систем диофантовых уравнений заданной степени.

7. Р азработана теория асимметричных рюкзачных систем защиты информации. На основе равносильных рюкзаков построены математические модели СЗИ с обнаружением и исправлением ошибок.

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

Теоретическая ценность работы состоит:

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

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

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

- в разработке новой теории нестандартных рюкзачных систем защиты информации.

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

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

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

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

Апробация работы. Результаты диссертационного исследования и основные научные положения работы докладывались и обсуждались на Всесоюзной школе "Конструктивные методы и алгоритмы теории чисел" (Минск, 1989г.), на Международных конференциях "Современные проблемы теории чисел" (Тула, 1993г., 1996г., Воронеж, 1995г.), на Международных конференциях "Алгебра и теория чисел: современные проблемы и приложения" (Тула, 2003г., Саратов, 2004г., Одесса, 2005г.), на Международных научно-практических конференциях по информационной безопасности (Таганрог, 2003, 2004, 2005, 2006г.г.), на Второй Международной научно-практической конференции "Исследование, разработка и применение высоких технологий в промышленности" (Санкт-Петербург, 2006 г.), на V Международной научной конференции «Ломоносовские чтения» (Севастополь, 2006 г.), на VII Всероссийском симпозиуме по прикладной и промышленной математике (Кисловодск, 2006г.), на Всероссийской научно-практической конференции "Современное Российское общество: проблемы безопасности, преступности, терроризма" (Краснодар, 2005, 2006г.г.), на I, II региональных межведомственной конференциях по защите информации (Краснодар 2000, 2003г.г.), на межвузовской научно-практической конференции "Информационная безопасность при использовании средств вычислительной техники" (Краснодар, 2003г.).

Публикации. Основные результаты диссертационной работы опубликованы в 65 печатных работах: в 60 научных статьях, более 10 из которых вышли в изданиях, рекомендуемых ВАК, в одной монографии, в 2 интеллектуальных продуктах ВНТИЦ, (свидетельства: № 70990000172 от 20.12.99г., № 73200300103 от 21 мая 2003г) и в двух программах для ЭВМ (свидетельства: № 2005611707 от 12.07.05, № 2006610879 от 06.03.06).

Структура и объём работы. Диссертационная работа состоит из введения, шести глав, заключения, библиографического списка, содержащего 223 наименований, и приложения. Она изложена на 320 страницах машинописного текста.

Заключение

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

Основные научные результаты, изложенные в данной диссертации состоят в следующем.

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

Предложенный автором рекуррентный алгоритм построения полинома деления круга Х„ (х), в частности, неприводимого в явном виде полинома заданной степени, в отличие от других известных алгоритмов не зависит от стандартных параметров - порядка поля и степени моделируемого полинома. Описанный алгоритм требует значительно меньшего числа вспомогательных вычислений и допускает эффективную реализацию на ЭВМ. Метод такой реализации сводится к многократному использованию рекуррентных формул (см. п. 2.2.):

1°. X n(x) = QmiXnn n (хр ) + (p-l)Pm ,ХВ „ „ (хРк"'), еслирк=2.

PiР2*"Рь ' Р1Р1—Рь-i v ' ' m-l Pi-Pu-zPk ' rK

2°. Xnn . (x) = Qm ,Xn n (xPk) + Pm.Xn n n (xp"-'), еслирк*2,

P1P2 Pkx ' ^m-l P1P2—Pt-iv ' m-l Pi - Pk-2PkV n r '

Показано, что данный алгоритм с незначительными поправками можно применить для построения минимальных полиномов элементов а составных полей Галуа GF(pm), и его можно использовать для практических приложений. При этом предварительно необходимо рассмотреть приводимость полинома Х„ (х) на основе циклотомических классов.

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

Он легко реализуем на ЭВМ с помощью модифицированной схемы Горнера: если положить s, 1 0 . О О s2 s, 2 . 0 0 s,

S , S ч m m-l m-2 s

З'-'и-З

2(Su-.Ai-Su)-),A0=l, где su степенные суммы. Совершенно аналогично определяются и коэффициенты а„ полинома Х„ (х) в Fp.

С помощью указанного алгоритма в качестве примера построен полином Х2145М степени 960, опровергающую гипотезу Чеботарёва (см. п. 6.1.).

2. Разработаны конструктивные модели и методы построения в явном виде неприводимых в Fp полиномов заданной степени. Предложен эффективный алгоритм разложения заданного сеперабельного полинома на неприводимые множители в полях Галуа с помощью операторов А0, А|,., Api поля Галуа. В отличие от других известных алгоритмов его конечный результат зависит только от показателя степеней вспомогательных полиномов, не превышающих заданного числа. Такой подход максимально упрощает процедуру разложения полинома, он хорошо просматривается на примере задачи о разложении двучленов. Данный метод позволяет исследовать достаточно широкий круг задач, в частности, оценить количество неприводимых полиномов с заданными свойствами и вывести конечную формулу для вычисления числа неприводимых полиномов специального вида.

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

4. Указан, с помощью разработанных методов построения полиномов с заданными свойствами, класс корректирующих циклических и арифметических AN-кодов. Для арифметических AN-кодов построены классы простых полей с заданными примитивными элементами. Показано, что класс циклических кодов с порождающими полиномами Xd (x),d |п совпадает с классом циклических кодов Меласа и Меггита.

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

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

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

8. На основании результатов исследований труднорешаемых задач, в частности задач многостепенного диофантового анализа, были предложены новые методы построения эффективных нестандартных рюкзачных СЗИ. Разработан новый класс систем защиты информации с открытым ключом, и изучен различные его модификации, в основе моделирования которых лежат дио-фантовые трудности, возникающие при решении многостепенных систем диофантовых уравнений высоких степеней вида п x,,x2,.,xm = у,,у2,.,ут,1< п < т.

При этом, в зависимости от основных параметров шип, учитывается либо сложность решения этой системы, либо сами решения п a i 2 f • - т = b 1, b 2,., b т, либо и то и другое одновременно. Предложены эффективные методы моделирования систем защиты информации в классе NP-полных задач, на основе нормальных и других многопараметрических решений многостепенных систем диофантовых уравнений высоких степеней.

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

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

Показано, что если п а 1, а 2,., a m) = (b 1 , b 2,. •, b т), 1<п<т

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

Х,,Х2,.,Хт = у , ,у 2 ,.,у т , то можно смоделировать рюкзачную СЗИ, которая одновременно обнаруживает и исправляет канальные ошибки.

Одна из модификаций СЗИ с равносильными рюкзачными векторами основываются на обобщённой теореме М.Фролова и операции обобщённого сильного модульного умножения. Впервые предложен метод построения рюкзачных СЗИ на основе обобщённого сильного модульного умножения. Разработан алгоритм построения многоалфавитной асимметричной СЗИ на основе универсального рюкзака с повторениями.

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

Указаны условия, при выполнении которых заданный инъективный рюкзак является плотным. Найдено рекуррентное соотношение для компонентов таких универсальных и обобщённых рюкзаков.

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

13. Предложена математическая модель СЗИ на основе теоремы Эйлера - Ферма, которая обобщает аналогичный результат Нечаева В.И. (свидетельство № 70990000172 от 20.12.99г.). На основе задачи факторизации, построены модели многопользовательского и полиномиального вариантов системы RSA.

14. Математические модели систем передачи и защиты информации, предложенные в диссертационной работе, реализованы на ЭВМ в виде пакетов прикладных программ, которые зарегистрированы в Российском агентстве по патентам и товарным знакам (свидетельства: № 2005611707 от 12.07.05, № 2006610879 от 06.03.06).

1. Аванесов Э.Т. Оценка числа решений линейного диофантова уравнения // Тр. ин-та / Ивановский гос. пед. ин-т- 1963. - т. 34 - с. 3-7.

2. Айерленд К., Роузен М. Классическое введение в современную теорию чисел: Пер. с англ. / Под ред. А.Н.Паршина. М.: Мир, 1987. - 416 с.

3. Аракелов В. А., Варшамов Р. Р. К исследованию алгебраической структуры периодических рекуррентных последовательностей // Изв. АН Арм. ССР, 1971-T.V1.-№5.-с. 379-385.

4. Аршинов М.Н.,Садовский J1.E. Коды и математика. -М.: Наука, 1983-144с.

5. Ахо А. и др. Построение и анализ вычислительных алгоритмов: Пер. с англ / А. Ахо, Дж. Хопкрофт, Дж. Ульман. М.: Мир, 1978. - 354с.

6. Бабенко J1.K. и др. Защита информации с использованием смарт-карти электронных брелоков / Л.К.Бабенко, С.С.Ищуков, О.Б.Макаревич. М.: ГелиосАРВ, 2003. -352с.

7. Бабенко Л.К., Мазурова Т.А., Сидоров И.Д., Чефранов А.Г. Алгоритмы безызбыточного кодирования перестановок и их обоснование // Изв. вузов. ТРТУ.- 2003.- № 4.- с. 259-262.

8. Берлекэмп Э. Алгебраическая теория кодирования: Пер. с англ. / Под ред. С. Д. Бермана.-М.: Мир, 1971.-480с.

9. Биркгоф Г., Барти Т. Современная прикладная алгебра: Пер. с англ. / Под. ред. Ю. И. Манина.-М.: Мир, 1976,-400с.

10. Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ./ Под. ред. К.Ш. Зигангирова. -М.: Мир, 1986 576с.

11. Боревич 3. И., Шафаревич И. Р. Теория чисел. -М.: Наука, 1985 504с.

12. Боуз Р. К., Рой-Чоудхури Д. К. Дальнейшие результаты относительно двоичных групповых кодов с исправлением ошибок // Кибернетический сборник. -М.: Мир,1963. вып. 6. - с. 7-12.

13. Боуз Р. К., Рой-Чоудхури Д. К. Об одном классе двоичных групповыхкодов с исправлением ошибок // Кибернетический сборник. М.: Мир, 1961.-вып. 2,- с. 83-94.

14. Брассар Ж. Современная криптология. М.: Полимед, 1999 176с.

15. Бурьян В. Ю. О коэффициентах полиномов деления круга // Тр. пед. инта. / Краснодарский пед. ин-т. 1949. - с. 95-127.

16. Варшамов P.P. Математические методы повышения надежности реальных систем связи / / Изв. АН СССР ./Технологическая кибернетика-1964.-№4.-с. 53-58.

17. Варшамов Р. Р. Некоторые вопросы конструктивной теории приводимости полиномов над конечными полями // Проблемы кибернетики 1973 -№27.-с. 154-159.

18. Варшамов Р. Р. О возможности увеличения мощности линейных корректирующих кодов //ДАН СССР.- 1975- т.223- №1.- с. 60-63.

19. Варшамов Р. Р. Об одном линейном операторе в поле Галуа и его приложении //Изд. АН Венгрии 1973-№8 - с. 5-19.

20. Варшамов P.P. Об одном методе построения неприводимых полиномов над конечными полями //ДАН Арм. ССР,- 1984 XXIX.- №1.- с.26-28.

21. Варшамов Р. Р. Об одной теореме из теории приводимости полиномов //ДАН СССР.- 1964,- т. 156.- №6.- с. 13 08-1311.

22. Варшамов Р. Р. Общий метод синтеза неприводимых полиномов над полями Галуа //ДАН СССР.- 1984.-т.275.-№5.- с.1041-1044.

23. Варшамов Р. Р. Операторные подстановки в поле Галуа и их приложения //ДАН СССР.- 1973.- т.- 211.- №4.- с.768-771.

24. Варшамов Р. Р. Ананиашвили Г. Г. К теории приводимости полиномов в конечном поле //Абстрактная и структ. теория релейных устройств-1966-с.134-138.

25. Варшамов Р. Р., Ананиашвили Г.Г. К вопросам разложимости полиномов над GF(2) //Сообщения АН Груз. ССР.- 1966.-т.41.-№1.- с. 129-134.

26. Варшамов Р. Р. Гамкрелидзе JI. И. Об одном методе построенияпримитивных полиномов над конечными полями //Сообщение АН Груз. ССР.- 1980.- т.99.-№1-с.61-64.

27. Варшамов P.P. Гараков Г.А. К теории самодвойственных полиномов над полем Галуа //Математические вопросы кибернетики и вычислительной техники. 1974.-t.4-c.5-17.

28. Варшамов Р. Р. Оценка числа сигналов в кодах с коррекцией ошибок //ДАН СССР. 1957.- т.117.- №5.- с. 1021-1024.

29. Варшамов Р. Р., Тененгольц Г. Н. Об одном классе циклических кодов.

30. Проблема кибернетики 1967 - №22 - с. 157-166.

31. Варшамов Р. Р. К математической теории кодов: Дис. д-ра физ-мат. на-ук-М.: ИАиТ, 1966.-97с.

32. Введение в криптографию /Под ред. В.В.Ященко М. :МЦНМО-ЧеРО. -1998.-272с.

33. Виноградов И. М. Основы теории чисел М.: Наука, 1981- 176с.

34. Виноградов И. М. Избранные труды. М.: АН СССР, 1952.- 436с.

35. Галлагер Р. Теория информации и надежная связь. М.: Сов. Радио, 1974.- 746с.

36. Галуев Г.А. Математические основы и алгоритмы криптографии. Таганрог, 2000,- 132с.

37. Гараков Г.А. Таблицы неприводимых полиномов над полем GF(p) р< 11 // Математические вопросы кибернетики и вычислительной техники-1970.-с. 112-142.

38. Гашков С.Б., Чубриков В.Н. Арифметика. Алгоритмы. Сложность Вычислений. М.: Высшая школа, 2000- 320с.

39. Гаусс К.Ф. Труды по теории чисел. М.: АН СССР, 1959.- с.773-806.

40. Гельфонд А.О. Избранные труды. М.: Наука, 1973- 440с.

41. Гинзбург Б.Д. Об одной теоретико-числовой функции, имеющей приложение в теории кодирования // Проблемы кибернетики. 1967- вып. 19-с.249-252.

42. Глушков В. Н. Синтез цифровых автоматов. М.: ГИФМЛ, 1962.-476с.

43. Гоопа В. Н. Алгебраико-геометричкские коды //Изв. АН СССР, 1982т.46 №4- с.762-781.

44. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: Пер. с англ. / Под ред. А.А.Фридмана. М.: Мир, 1982 - 416с.

45. Дадаев Ю.Г. Теория арифметических кодов. М.: Радио и связь, 1981-272с.

46. Дискретная математика и математические вопросы кибернетики / Под ред. С.В.Яблонского и О.Б.Лупанова. М.: Наука, 1974 - т.1 - 312с.

47. Диффи У., Хеллман М.Э. Защищённость и имитостойкость. Введение в криптографию. /ТИИЭР.-т. 67-№3.-с.71-109.

48. Дмиттриев В.И. Прикладная теория информации.- М.: Высшая школа, 1989.-320с.

49. Иванов В. К. О свойствах коэффициентах уравнений деления круга //Успехимат. наук. 1941-№9-с.313-317.

50. Карп Р. М. Сводимость комбинаторных задач // Киб. сб.- М.: Мир, 1975-с.16-38.

51. Кнут Д. Искусство программирования. Получисленные алгоритмы: Пер. с англ./ Под ред. К.И.Бабенко М.: Мир, 1999 - т.2.- 724с.

52. Коблиц Н. Курс теории чисел и криптографии: Пер с англ. / Под ред. A.M. Зубкова.- М.: НИ ТВП, 2001.- т. 3.- 260с.

53. Колесник В. Д., Мирочнико Е. Т. Декодирование циклических кодов. -М.: Связь, 1968.-252с.

54. Конхейм А.Г. Основы криптографии. -М.: Радио и связь, 1987-250с.

55. Кук С.А. Сложность процедур вывода теорем // Киб. сб., нов. сер.- М.: Мир, 1975 вып. 12- с.5-15.

56. Кюрегян М.К. Об одном методе построения неприводимых полиномов над полями Галуа //ДАН Арм. ССР, 1986. т. XXXI1.- №2. - с.58-61.

57. Кюрегян М.К. Разложение полиномов над конечными полями //ДАН Арм. ССР, 1985 т. XXXI - №2- с.69-73.

58. Левин А.А. Универсальные задачи перебора // Проблемы передачи информации. т.9. - №3 - Ю73- с Л15-116.

59. Ленской Д.Н. К арифметике многочленов над конечным полем /Волжск.матем. сб.- 1966-вып.4.-с.155-159.

60. Лидл Р., Нидеррайтер Г. Конечные поля. М.: Мир, 1988. - 820с.

61. Мак-Вильянс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. Пер. с англ. /Под ред. Л.А. Бассалыго. М.: Связь, 1979 - 744с.

62. Математика. Сб. переводов 1964.—8:5.—с. 15-22.

63. Матиясевич Ю. В. Диофантовость перечислимых множеств //ДАН СССР.- 1970.-191.-2-с.279-282.

64. МатиясевичЮ. В. Диофантовы множества//Успехи матем. наук 1972-т.26. - вып.- 5(167).- с. 185-222.

65. Мафтик С. Механизмы защиты в сетях ЭВМ. М.: Мир, 1993. - 216с.

66. Молдовян А.А. и др. Криптография / А.А. Молдовян, Н.А. Молдовян, Б.Я. Советов. С.-П.: Лань, 2000. - 220с.

67. Мэси Дж.Л. Современная криптология: введение. //ТИИЭР, 1988. т.76. -№5. - с.24-42

68. Нечаев В.И. Суммы квадратов и криптография // Междунар. конф. "Современные проблемы теории чисел": Тез. докл. Воронеж, 1995. - с.119.

69. Нечаев В.И. Элементы криптографии. Основы теории защиты информа-ции.-М.: Высшая школа, 1999. 109с.

70. Обозрение прикладной и промышленной математики //М., 2002. -т.9-вып.1. -с.26-45.

71. Ожигова Е.П. Что такое теория чисел. М.: Знание, 1970 - 96с.

72. Окунев Л.Я. Целые комплексные числа. Учпедгиз., 1941. 112с.

73. Осипян О. Н. О цепных дробях функциональных квадратических ирра-циональностей над кольцом ZPx. // Исследование по алгебре. Краснодар, 1973-с.З 8-69.

74. Осипян В. О. Об одном рекуррентном методе нахождения полиномов деления круга над конечными полями // Всесоюзн. школа «Конструктивные методы и алгоритмы теории чисел»: тез. докл. Минск, 1989. - с.114.

75. Осипян В. О. Решение в целых числах некоторых диофантовых и системдиофантовых уравнений // Куб. ГУ. Краснодар, 1979. - 13с. - Деп. в ВИНИТИ 04.01.79, № 91-79.

76. Осипян О. Н., Осипян В. О. Новые двупараметрические решения многостепенной системы диофантовых уравнений Х!П+. .+х4п=у1"+. .+у4п, п=2,4,6 // Куб. ГУ. Краснодар, 1985. - 14с. - Деп. в ВИНИТИ 14.05.85, № 3639-85.

77. Осипян О. Н., Осипян В. О. О некоторых свойствах многочленов деления круга и их арифметических приложениях ч. №1 // Куб. ГУ. Краснодар,1981. 25с. - Деп. в ВИНИТИ 07.07.81, № 3736-81.

78. Осипян О. Н., Осипян В. О. О некоторых свойствах многочленов деления круга и их арифметических приложениях ч.2 // Куб. ГУ. Краснодар, 1981. - 21с. - Деп. в ВИНИТИ 07.07.81, № 3737-81.

79. Осипян О. Н., Осипян В. О. О целых решениях многостепенной системы диофантовых уравнений Xin+x2n+ .+ХбП=уГ+у2П+ .+УбП, п=1,2,3,4 // Куб. ГУ. Краснодар, 1982. - 19с. - Деп. в ВИНИТИ 31.12.82, №6552-82.

80. Осипян О. Н., Осипян В. О., Об одном способе получения новых многопараметрических решений многостепенных систем диофантовых уравнений х,п+.+х4П=у,п+.+у4п, п=1,2,4 и п=1,2,3 // Куб. ГУ. Краснодар, 1985. - 16с. - Деп. в ВИНИТИ 26.06.85, №5084-85.

81. Осипян В. О. Разработка методов построения и анализ специальных классов циклических кодов: Автореф. канд. физ.-мат. наук. Ереван, ВЦ АН РА, 1990.- 14с.

82. Осипян О.Н., Осипян В.О. Новые многопараметрические решения многостепенной системы диофантовых уравнений Xn+Yn+Zn=Un+Vn+Wn, п=2,4. // Куб. ГУ. Краснодар, 1993. - 6с. - Деп. в ВИНИТИ 26.06.93, № 1820-В93.

83. Осипян О.Н., Осипян В.О. Многопараметрические решения многостепенной системы диофантовых уравнений Xin+.+X6n=:Y.n+.+Y6n, п=1,2,4 // Куб. ГУ. Краснодар, 1993.-1 lc.-Деп. в ВИНИТИ 26.06.93, № 1821-В93.

84. Осипян В.О. Об одном методе определения всех делителей заданногосеперабельного полинома над конечными полями // Междунар. конф. "Современные проблемы теории чисел": Тез. докл. Тула, 1993 - с.119-120.

85. Осипян В.О. Об одном алгоритме к синтезу неприводимых над конечными полями полиномов заданной степени // Межвуз. сб. "Вопросы прикл. матем. и механики".- Краснодар, 1994. вып.1- с. 13-18.

86. Осипян В.О. Подсчёт числа перестановочных целых функций полей Галуа// Междунар. конф. "Современные проблемы теории чисел": Тез. докл. -Воронеж, 1995- с. 119-121.

87. Осипян О.Н., Осипян В.О. Новые многопараметрические решения мнго-гост. системы диофантовых уравнений Xin+.+X5n=Yin+.+Y5n,n=l,2,3,5,7, ч. I. // Межвуз. сб. "Вопросы прикл. матем. и механики".- Краснодар, 1995. вып.2- с.11-15.

88. Осипян О.Н., Осипян В.О. Новые многопараметрические решения мнго-гост. системы диофантовых уравнений Xin+.+X5n=Yin+.+Y5n,n=l >2,3,5,7, ч. II. // Межвуз. сб. "Вопросы прикл. матем. и механики".- Краснодар, 1995.- вып.2.- с.15-19.

89. Осипян О.Н., Осипян В.О. Новые двухпараметрические решения многостепенной системы диофантовых уравнений Xn+Yn+Zn=Un+Vn+Wn, п=2,4 в натуральных числах, ч. I. // Межвуз. сб. "Вопросы прикл. матем. и механики",- Краснодар, 1995. вып.З. - с. 10-15.

90. Осипян О.Н., Осипян В.О. Новые двухпараметрические решения многостепенной системы диофантовых уравнений Xn+Yn+Zn=Un+Vn+Wn, п=2,4 в натуральных числах, ч. II. // Межвуз. сб. "Вопросы прикл. матем. и механики",- Краснодар, 1995. вып.З. - с. 15-21.

91. Осипян В.О. Метод перестановочных функций, сохраняющих приводимость полиномов в полях Галуа // Междунар. конф. "Современные проблемы теории чисел": Тез. докл. Тула, 1996. - с.118-119.

92. Осипян В.О. Циклотомические классы и случаи приводимости полиномов деления круга над полями Галуа // Межвуз. сб. "Вопросы прикл. матем. и механики".- Краснодар, 1997. вып.4. - с. 16-20.

93. Осипян О.Н., Осипян В.О. Получение параметрических решений диофантовых уравнений х^+хД. +х55=у,5+у25+. +у55, (хьх2,., х5,уьу2,., У5)—1 и других. 4.1. // Межвуз. сб. "Вопросы прикл. матем. и механики",-Краснодар, 1997. вып.4. - с. 14-19.

94. Осипян О.Н., Осипян В.О. Получение параметрических решений диофантовых уравнений х,5+х25+. +x55=yi5+y25+. +у55, (х,,х2,. • •, х5,уьу2,., ys)=l и других. Ч. И. // Межвуз. сб. "Вопросы прикл. матем. и механики".-Краснодар,1997. вып.4. - с. 19-21.

95. Осипян В.О. Элементы теории передачи информации: Учеб. пособие. -Краснодар, 1998.-52с.2 2

96. Осипян В.О. Система шифрования на основе уравнения X + кУ =Р, к= 1,2,3 // ВНТИЦ 20.12.99, № 70990000172.

97. Осипян О.Н., Осипян В.О. Получение параметрического решения многостепенной системы диофантовых уравнений п-й степени по какому-либо частному решению той же системы, ч. I. // Куб. ГУ. Краснодар, 1999. -Юс. - Деп. в ВИНИТИ 29.12.99, № № 3896-В99.

98. Осипян О.Н., Осипян В.О. Получение параметрического решения многостепенной системы диофантовых уравнений n-й степени по какому-либо частному решению той же системы, ч. II. // Куб. ГУ. Краснодар, 1999. -Юс. - Деп. в ВИНИТИ 29.12.99, № № 3897-В99.

99. Осипян В.О., Осипян К.В. Система защиты информации на основе решений многопараметрических систем диофантовых уравнений/ Сб. тез. докл. per. межвед. конф. по защите информации Краснодар, 2000 - с.44-45.

100. Осипян В.О. Об одной криптосистеме с открытым ключом на основе кода Варшамова //V Междунар. конф. «Алгебра и теория чисел: совр. проблемы и приложения»: Тез. докл.- Тула, 19-24 мая 2003- с. 170.

101. Осипян О.Н., Осипян В.О. Синтез СЗИ на основе многопараметрических решений многостепенных систем диофантовых уравнений // V Междунар. конф. «Алгебра и теория чисел: совр. проблемы и приложения»: Тез. докл.-Тула, 19-24 мая 2003. с. 172.

102. Осипян В.О. Криптосистема с открытым ключом на основе обобщённого рюкзака//ВНТИЦ 21.05. 2003, № 73200300103.

103. Осипян В.О., Осипян К.В. Система защиты информации на основе специального рюкзака // Материалы межвуз. научно-практической конф. «Информ. безопасность при использовании средств выч. техники», МВД РФ, Краснод. юридич. институт, 2003, с.40-41.

104. Осипян В.О. Об одном обобщении рюкзачной криптосистемы // Изв. вузов. Сев.-Кавк. региона, 2003, Прил. № 5.- с. 18-25.

105. Осипян В.О., Осипян К.В. Математические основы теории и практики защиты информации. Краснодар, 2003- 192с.

106. Осипян В.О. Система защиты информации на основе кода Варшамова // Инф. противодействие угрозам терроризма. Таганрог, 2003.-№1- с.121-123.

107. Осипян В.О., Осипян К.В. О математических системах обеспечения информационной безопасности на современном этапе // Сб. тез. докл. II per. межвед. конф. по защите информации. Краснодар, 2003- с. 18-20.

108. Осипян В.О. Асимметрическая система защиты информации на основе универсального и функционального рюкзаков // Защита информации. Конфидент.- С-П., 2004.- №6. с.61-63.

109. Осипян В.О. О криптосистемах с заданным рюкзаком // Материалы VI междунар. научно-практич. конфер. Таганрог, 2004. - с.269-271.

110. Осипян В.О. Генерация перестановок с помощью перестановочных целых функций // Материалы VI междунар. научно-практич. конфер. Таганрог, 2004.-с.271-273.

111. Осипян В.О. О некоторых алгоритмах синтеза неприводимых над Fq полиномов методом анализа // Материалы VI междунар. научно-практичконфер. Таганрог, 2004. - с.273-274.

112. Осипян В.О. Разработка методов построения систем передачи и защиты информации. Краснодар, 2004. - 180с.

113. Осипян В.О. О полиалфавитной криптосистеме с обобщённым рюкзаком // Изв. вузов. Сев.- Кавк. региона. Спец. Выпуск «Мат.моделиров. и компьют. технологии», 2004 с.65-66.

114. Осипян В.О. О криптосистемах с различными рюкзаками / / Инф. противодействие угрозам терроризма. Таганрог, 2004.-№3.- с. 53-56.

115. Осипян В.О., Осипян К.В. Криптография в упражнениях и задачах. М.: Гелиос АРВ, 2004.-144с.

116. Осипян В.О., Арутюнян А.С. О приводимости полиномов деления круга над полями Галуа // VI Межд. конф. «Алгебра и теория чисел: совр.проблемы и приложения»: Тез. докл. Саратов, 19-24 сентября 2004. -с. 170.

117. Осипян В.О. О системе защиты информации на основе функционального рюкзака // Вопросы защиты информации. М., 2004 - № 4. - с. 16-19.

118. Осипян В.О. О системе защиты информации на основе универсального рюкзака // Изв. Вузов. ТПУ- №3.

119. Осипян В.О. Система защиты информации на основе плотного обобщённого рюкзака. Комплекс программ для PC. № 2005611707 от 12.07.05.

120. Осипян В.О. Разработка системы защиты информации на основе математической модели функционального рюкзака с повторениями // Изв. Вузов. Сев.- Кавк. региона, 2005 с.

121. Осипян В.О. Разработка системы защиты информации на основе математической модели универсального рюкзака с повторениями // Изв. вузов. Сев.- Кавк. региона-2005-№2. с. 12-15.

122. Осипян В.О. Об одном способе нахождения всех простых делителей заданного полинома над конечными полями // Вестник СГУ, 43/2005. с.69-72.

123. Осипян В.О. Моделирование асимметричной рюкзачной системы защиты информации, содержащей диофантовую трудность // Вестник СГУ, 2005,- с.

124. Осипян В.О. Моделирование систем защиты информации, содержащих диофантовую трудность//Материалы VII Междунар. науч.-практ. Конф-Таганрог, 2005.- с.202-209.

125. Осипян В.О., Семенчин Е.Н. Построение систем защиты информации на основе проблемы универсального рюкзака // Изв. вузов. ТРТУ, 2005. -№4.-с. 182-188.

126. Осипян В.О., Арутюнян А.С. Моделирование систем защиты информации, на основе решений диофантовых уравнений // VII Междунар. алгебр, конф.— Одесса, 20-27 июля 2005 с.42-43.

127. Осипян В.О. О решениях нормальной многостепенной системы диофантовых уравнений пятого порядка в натуральных и в целых комплексных (гауссовых) числах //VII Междунар. алгебр, конф Одесса, 20-27 июля 2005.- с.43-44.

128. Осипян В.О., Мирзаян А.В. Система защиты информации на основе плотного универсального рюкзака. Комплекс программ для PC, 06.03.06. №2006610879.

129. Осипян В.О., Мирзаян А.В. Сравнительный анализ криптостойкости классической и обобщенной рюкзачной криптосистем // Там же. с.24-27.

130. Осипян В.О., Пашина-Дитмарова Г.В. Еще раз о защите информации: языки сценариев // Там же. с.27-29.

131. Осипян В.О., Пашина-Дитмарова Г.В. Алгоритм шифрования «17» // Там же. с.29-31.

132. Осипян В.О. Моделирование систем защиты информации на основеравносильных рюкзаков, содержащих диофантовую трудность, с обнаружением и исправлением ошибок //Вопросы защиты информации-М.,2006.-№2.-с. 16-19.

133. Осипян В.О. Моделирование систем защиты информации рюкзачного типа с переменными ключами // Изв. вузов. Сев.-Кавк. Регион. № 5 с.

134. Основы криптографии: Учеб. Пособие / А.П.Алфёров, А.Ю.Зубов, А.С. Кузьмин, А.В.Черемушкин. М.: Гелиос АРВ, 2002. - 480 с.

135. Петров А.А. Компьютерная безопасность. Криптографические методы защиты. -М.: ДМК, 2000.-448 с.

136. Питерсон У., Уэлдон Э. коды, исправляющие ошибки /Под ред. Р. Д. Добрушина и С. И. Самойленко. М.: Мир, 1976 294с.

137. Пупков К.А. и др. Функциональные ряды в теории нелинейных систем / К.А. Пупков, В.И. Капалин, А.С. Ющенко. М.: Наука, 1976 - 448с.

138. Ростовцев А.Г. Алгебраические основы криптографии. СПБ.: Мир и семья, 2000. - 354с.

139. Ростовцев А., Маховенко Е.Б. Введение в криптографию с открытым ключом. СПБ.: НПО "Мир и Семья", 2001. - 312 с.

140. Ростовцев А., Маховенко Е.Б. Теоретическая криптография. СПБ.: Профессионал 2005 - 492с.

141. Саломаа А. Криптография с открытым ключом. М.: Мир, 1995- 318с.

142. Серпинский В. Сто простых, но одновременно и трудных вопросов арифметики. М.: Учпедгиз, 1961 - 76с.

143. Серпинский В. О решении уравнений в целых числах. М., 1961.

144. Серпинский В. Что мы знаем и чего не знаем о простых числах. M.-JL: ГИФ-МЛД963. - 66с.

145. Серре И.А. Курс высшей алгебры. С.-П., М.: Изд. М.О.Вольф, 1897.

146. Степанов С. А. О числе неприводимых в Fqx. многочленов специального вида // Успехи мат. наук, 1985 т.40. - вып.4 (244). - с. 199-200.

147. Сушкевич А. К. Основы высшей алгебры.-М.-Л.:ОГИЗ ГИТТЛ,1941-460с.

148. Схрейвер А. Теория линейного и целочсленного программирования. -М.: Мир, 1991.-704с.

149. Тарьян Р.Э. Сложность комбинаторных алгоритмов. // Кибернетический сборник. -М.: Мир, 1963. вып. -17.-е. 7-12.

150. Теория кодирования: Пер. с япон. / Под ред. Б.С. Цыбакова и С.И. Гель-фанда./Т. Касами., Н.Токура, Е.Ивадари,Я.Инагаки. -М.: Мир, 1978-576с.

151. Фрумкин М.А. Сложность дискретных задач // ЦЭМИ АН СССР, 1981.

152. Харари Ф. Теория графов. М.: Мир,1973 - 336с.

153. Хартманис ДЖ., Стирнз Р. О вычислительной сложности алгоритмов. // Кибернетический сборник., нов. сер.- М.: Мир, 1967 вып.-№4. - с.57-85.

154. Хачиян JI.T. Полиномиальный алгоритм в линейном программировании / /ДАН СССР, 1979. т.244- вып.5. - с.

155. Хетагуров Я.А., Руднев Ю.П. Повышение надёжности цифровых устройств методами избыточного кодирования. М.: Энергия, 1974 - 262с.

156. Хинчин А.Я. Три жемчужины теории чисел. -М.-Л.:ОГИЗ ГИТТЛ, 1947.-72с.

157. Хованский А.Н. Приложение цепных дробей и их обобщений к вопросам приближённого анализа. М.: Гостехиздат, 1956. - 204с.

158. Холл М. Комбинаторика. М.: Мир, 1970 - 424с.

159. Хоффман Л.Дж. Современные методы защиты информации. М.: Радио и связь, 1980-264с.

160. Ху Т. Целочисленное программирование и потоки в сетях. -М.: Мир, 1974.-4 Юс.

161. Цымбал В.П. Теория информации и кодирование. Киев: Вища школа, 1977.-288с.

162. Шеннон К. Теория связи в секретных системах // В кн.: Работы по теории информации и кибернетике. М., 1963. - с. 33-402.

163. Школьник А. Г. Задачи деления круга. М.: Учпедгиз, 1961. - 74с.

164. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы,исходные тексты на языке Си. М.: ТРИУМФ, 2002. - 816с.

165. Шнирельман Л.Г. Простые числа. М.-Л.: ГИТТЛ, 1940 - 60с.

166. Шоломов Л.А. Основы теории дискретных логических и вычислительных устройств. М.: Наука, 1980 - 400с.

167. Чеботарев Н. Г. Несколько задач из различных отделов алгебры и теории чисел // Успехи метем, наук, 1938. №4. - с.284-286.

168. Чеботарев Н. Г. Основы теории Галуа. т.1. М.-Л.: ГИТТЛ, 1934 - 222с.

169. Чеботарев Н. Г. Основы теории Галуа. т.2. М.-Л.: ГИТТЛ, 1937 - 160с.

170. Чмора А.Л. Современная прикладная криптография. М.: Гелиос АРВ, 2001.-244с.

171. Эйлер Л. Введение в анализ бесконечно малых. М.-Л.: ОНТИ, 1936-272с.

172. Яглом A.M., Яглом И.М. Вероятность и информация. М.: Наука, 1973 .-512с.

173. Яковкин М. В. Численная теория приводимости многочленов. -М.: АН СССР, 1959.

174. Agou S. Factorisation des polynomes a coefficients dans un corps fini. Publ. Dep. Math. Lyon 13, no. 1,1976.-p. 63-71.

175. Albert A. A. Fundamental concepts of higher algebra Univ. of Chicago Press, 1956.

176. Beard J.T.B. Computing in GF(q). Math. Comp.28,1974. p. 1159-1166.

177. Bachmann P. Die Lehre ron der Kreisteilung und ihre Berihungen zur Zahhen theorie Leipzig, 1872.

178. Berlekamp E.R., Rumsey H., Solomon G. On the Solution of Algebraic Equa tions over Finite Fields // Information and control 10, 1967. p. 553-564.

179. Berlekamp E.R. Factoring polynomials over large finite fields. Ath. Сотр.24,1970.-p. 713-735.

180. Brickell E. Breaking iterated knapsacks. In: Advances in Cryptology. Crypto'84, Heidelberg etc.: Springer, 1985-p. 342-358.

181. Brickell E., Odlyzko A. Cryptanalysis: A survey of recent results. Proc.

182. EE, 1988.-v.-76.-p. 578-593.

183. Brown D.T. Error detecting and correcting binary codes for arithmetic opera tions.// IRE Trans.- 1960. -v.9.- № 3.-p. 333-337.

184. Butler M.C.R. On the reducibility of polynomials over finite fields. Quart. Math. (2) 5, 1954—p. 102-107.

185. Butler M.C.R. The irreducible factors of f(x m) over a finite field. London Math. Soc., 4,1955.-p. 480-483.

186. Carlitz L. Sets of primitive roots. Compositio Math. 13. 1956. p. 65-70.

187. Carmichael R. D. The Theore of Numbers and Diophantine analysis New York, 1959.

188. Chernick J. Ideal Solutions of the Tarri-Escott problem // Amer. Math. Monthly, 1937.-№ 56,44n. 10.-p. 626-633.

189. Cohen S. D. The distribution of polynomials over finite fields // Acta arit metica, XVIII, 1970.-p. 255-271.

190. Collins G.E. The calculation of multivariate polynomial resultants. Assoc. Comput. Mach. 18,1971.-p. 515-532.

191. Discson L. E. Hustory of the Teory of Numbers, v. 2. Diophantine analysis-New York, 1952.

192. Discson L. E. Liner Groupswith an Exposition of the Galois Field Theory-Teubner, Leipzig, 1901.

193. Erdos P. Some recent advances and current problems in number theory, Lectures onModernMathematics. 1965-v. 3.-p. 196-244.

194. Gloden A. Mehgradige Gleichungen Groningen, 1944 - p. 104.

195. Gurari E.M., Ibarra O.H. An NP-complete number theoretic problem, Proc.lOth Ann. ACM. Symp. On Theory of computing New York, 1978 - p. 205-215.

196. Hocquenghem A. Codes correcteur d'errcurs. Chiffres- 1959- v.2-p.147-156.

197. Klee V., Minty G.J. How good is simplex algorithm? Inequalities III, Academic Press. New York, 1972.-p. 159-175.

198. Kronecker L. Memoire sur les facteurs irreductibles de l'expression xn-l. Math. Pures Appl.- 1854.- 19.-p. 177-192.

199. Lang S. Algebra, Addison-Wesley, Reading, Mass. 1971.

200. Lempel A. Analysis and synthesis of polynomials and sequences over GF(2). IEEE Trans. Information Theoiy .-1971, IT-17.- p. 297-303.

201. Lenstra A.K. Lattices and factorization of polynomials. SIGSAM Bull. 1981, 15.- no. 3,- p. 15-16.

202. Lenstra A.K. Primality testing algorithms // Lecture Notes in Math. V.901, 1981.-p.- 243-257.

203. Lehmer E. On the Magnitude of the Coefficients of the Cyclotomis Polynomial // Bull. Amer. Math. Soc., 1936,42.-p. 389-392.

204. Lueker G.S. Two NP-complete problems in nonnegative integer programming. Сотр. Science Laboratory, 1975, 178.

205. MacEliece RJ. A public-key cryptosystem based on algebraic coding theory. //Deep Space Network Progress Report, Jet Propulsion Labs, Pasadena. 1978, 42-44.-p.-114-116.

206. Madden D.J. Polinomials and primitive roots in finite fields. Number Theoiy 13.,1981.-p. 499-514.

207. Mcelece R.J. Factorization of polynomials over finite fields. Math. Сотр. 23, 1967-p. 861-867.

208. Mcelece R.J. Table of polynomials of period e over GF(p), Math. Сотр. 23, 1969.-p. 1-6.

209. Menezes A.J., van Orschot P.C., Vanstone S.A. Handbook of applied cryptography.- CRC Press, 1996.

210. Merkle R. C., Hellman M.E. On the security of multiple encryption // Communications of the ACM., 1981, vol. 24.

211. Moenck R.T. On the efficiency of algorithms for polynomial factoring. Math. Сотр. 31, 1977.-p. 235-250.

212. Mordell L. J. Diophantine equations // London New York, Acad. Press, 1969.

213. Pallet A.E. Sur jes foctions irreductibles savant un module premier, C.R. Acad. Sci. Paris. 1881, 93.-p. 1065-1066.

214. Rao T. R. N. Error coding for arithmetic processors. N.Y. Academic Press, 1974.

215. Riesel H. Prime numbers and computer methods for factorization. Birk-hauser, 1985.

216. Shamir A. A polynomial time algorithm for breaking the basic Mercle-Hellman cryptosystem. In: Proceedings of the 23rd Annual Symposium on the Foundations of Computer Science, 1982. - p. 145-152.

217. Schneir B. Applied cryptology. John Wiley&Sons? Inc., 1996.

218. Selmar S. E. On the irreducibility of certein trinoials, M. S., 1956,4. -№2.

219. Swan R.G. Factorization of Polynomials over Finite Fields, Pacific J.Math., 12, p.-1099-1106.

220. Swift J.D. Construction of Galois fields of characteristic two and irreducible polynomials. Math. Сотр. 1960, 14. p. 99-103.

221. Wiliams K.S. On the number of solutions of a congruence? Amer.Math. Monthly 7, 1966.-p. 44-49.

222. Zadeh N. A bad network problem for the simplex mrthod and other minimum cost flow algorithms. Math. Programming 5, 1973. p. 255-266.

223. Zierler N. Linear recurring sequency //1. Soc. Ind. Appl. Math. 1959, V.7, №1.- p. 31-48.