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

Содержание



Введение	3

1 гомоморфноЕ шифрованиЕ	6

1.1 Методы гомоморфного шифрования предложенные ранее	7

1.2 Недостатки предложенных ранее методов	10

1.3 Возможности исправить недостатки известных решений	13

1.4 Постановка задачи	13

2 применяймые математические методы	15

2.1 Поля Галуа	15

2.2 Задача дискретного логарифмирования	36

2.3 Алгоритм Берлекэмпа	44

3 Практическая реализация и ИССледования	55

3.1 Метод шифрования и метод поиска изоморфизмов	55

3.2 Простейший пример реализации	57

3.3 Поиск изоморфизмов в поле GF(28) и разработка алгоритмов	61

3.4 Исследование поля GF(220) и реализация программ	69

Заключение	75

Список используемой литературы	77

Приложение А	90

Приложение Б	95

Приложение В	97

Приложение Г	103




Введение





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

В 1978 году, Рональдом Ривестом, Леонардом Адлеманом, Майклом Дертузосом впервые было сформировано такое понятие, как гомоморфное шифрование. Однако их первые попытки потерпели неудачу. Тогда авторы решили, что их идея не подлежит реализации. С тех пор более 30 лет не было реализации гомоморфного шифрования. Хотя и были попытки создать такую систему Шафи Гольдвассер и Сильвио Микали в 1982 году, в 1999 году Паскалем Пэйе, в 2005 году Дэн Бонэ, Ю Чжин Го и Коби Ниссим. В 2009 году предложенное Крэйгом Джентри система получила развитие в IBM и схема получила название BGV (Бракерски-Гентри-Вайкунтанатан. В нашей стране вопрос гоморфного шифрования развивают Бабенко Л. К., Буртыка, Ф. Б. Макаревич О. Б., Трепачева А. В, Жиров А. О., Жирова А. О., Кренделев С. Ф.

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

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

Провести анализ методов гомоморфного шифрования;

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

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

Решить задачу дискретного логарифмирования в расширенном поле, с целью ускорить процесс дешифрования;

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

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

Объектом исследования является метод шифрования данных на основе гомоморфных отображений.

Предмет исследования составляет способ шифрование данных на основе гомоморфных отображений в расширенных полях Галуа.

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

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

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

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

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

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

Апробация результатов работы. Научные результаты работы публиковались в сборнике материалов Всероссийской конференции «Инженерные кадры – будущее инновационной экономики России» в Секции № 4 «Информационные технологии – основа стратегического прорыва в современной промышленности».

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

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

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

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

Структура и объем работы. Работа состоит из аннотации, введения, 3 глав, заключения, библиографического списка. Основное содержание работы изложено на 105 страницах машинописного текста, 12 рисунке, 3 таблицах, 4 листингах программ, 4 приложениях. Список используемой литературы включает 92 наименование, среди которых 31 отечественных, 61 зарубежных авторов.








1 гомоморфноЕ шифрованиЕ





Нынешняя криптография, на сегодняшний день, включает в себя больше, чем просто наука о методах обеспечения передачи конфиденциальной информации от одного клиента к другому. Криптография стремиться разрешить целый ряд задач относящихся к обработке конфиденциальной информации и разделения доступа к этой информацией. Начало современной криптографии дало шифрование открытым ключом, которое предложили впервые Диффи и Хеллмана в работе [1], и реализовано Ривестом, Шамиром и Адлеманом [2]. При шифровании открытым ключом отправитель шифрует сообщение с помощью открытого ключа получателя, а получатель – расшифровает шифрованный текст, используя свой секретный ключ, для получения исходного сообщения. Но, если рассматривать с такой точки зрения, современные методы шифрования позволяют получить доступ к зашифрованным данным только по принципу все или ничего – наличие секретного ключа позволяет расшифровать сообщение целиком, а без ключа зашифрованный текст совершенно бесполезен.

Подобное положение дел вызвало интересный вопрос в 1978 году у создателей криптосистемы RSA Ривеста, Адлемана и Дертузо [3]: можно ли делать произвольные вычисления над данными, в то время как они остаются зашифрованными, никогда не расшифровывая их? 

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

Методы гомоморфного шифрования в отечественной литературе мало представлены, в основном гомоморфным шифрованием представлены зарубежной литературой. Среди отечественной литературы гомоморфные криптосистемы представлены в статьях [5, 6, 7].

1.1 Методы гомоморфного шифрования предложенные ранее





Ранее упоминалась, что первая схема шифрования, позволяющая проводить вычисления над данными в зашифрованном виде, была предложена Ривестом, Адлеманом и Дертузо [3] в 1978 году, в статье под названием «О банках данных и гомоморфизмах, сохраняющих конфиденциальность». Функция возведения в степень и функция RSA были предложены в качестве аддитивного и мультипликативного гомоморфизмов, соответственно. Но, обе эти функции не давали криптостойкости даже против атаки по выбранному открытому тексту. Поэтому авторы решили, что их идея не подлежит реализации.

В 1984 году первая схема гомоморфного шифрования, отвечающая требованиям семантической криптостойкойсти, была предложена Гольдвассером и Микали в работе [8], где было внедрено удобное определение криптостойкости для шифрования. В схеме GM шифрование проводит сложение зашифрованных битов по модулю 2 (функция «исключающее или»). Многие криптосхемы, которые созданы позже, были либо аддитивно, либо мультипликативно гомоморфны. Такие системы предлагали: в 1984 году Эль Гамаль [9]; в 1999 году Пэйе [10]; в 2001 году Дамгаард и Юрик [11]; схемы шифрования на основе теории решеток: работа Айтая и Дворк [12] в 1997 году, работа Реджева [13, 14] в 2004 году; и многие другие [15, 16, 17]. 

В 1999 году Сэндер, Янг и Юнг [18] построили систему шифрования, которая может вычислять NC1 схемы. Но зашифрованные данные в их криптосистеме возрастают в геометрической прогрессии с нарастанием глубины схемы, что приводит к ограничению на NC1.

Миновало не мало времени, прежде чем появились схемы шифрования, которые выходят за границы простого аддитивного или мультипликативного гомоморфизма. Представленная в 2005 году работа Боне, Го и Нисим [19] схема шифрования на основе билинейных спариваний на эллиптических кривых позволяла выполнять множество сложений, а также одно умножение открытых текстов. В 2010 году Джентри, Галеви и Вэйкунтанасан в свое работе [20] доказали, как можно достичь такой же функциональности, используя решетки. 

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

Система шифрования, которую предложили в 2010 году 
Агилара-Мелькором, Гэйборитом и Герранцом [22], гомоморфно производит вычисления над многомерными полиномами. В этой криптосистеме зашифрованный текст возрастет экспоненциально от степени полинома. Первым претедентом на полностью гомоморфное шифрование была работа Феллоуза и Коблица [23] в 1993 году на основе сложности проблемы принадлежности идеалу (ППИ) в кольце полиномов от нескольких переменных Fq [x1 ,...,xn]. Метод был взломан при многих вариантах выбора параметров.

Значительный вклад принесла работа Джентри [24] в 2009 году. Уже после выхода работы Джентри заинтересованность исследователей к гомоморфному шифрованию значительно вырос. Стали появляться работы с модификациями исходной системы шифрования Джентри[25], которые улучшали её производительность.

В 2010 году Дамьен Шехли и Рон Штейнфелд предложили некоторые оптимизации и улучшения [26], а затем были созданы первые рабочие реализации полностью гомоморфной схемы шифрования Джентри[25] Найджелом Смартом с Фредериком Веркаутереном [27, 28], и Крейгом Джентри c Шайемом Халеви [29, 30].

В 2010 году Мартин ван Дейк, Крейг Джентри, Шай Халеви и Видон Вайкунтанахан сформировали следующую полностью гомоморфную криптосистему[31]. В нее внедрены многие принципы системы Джентри, но не использовала идеальные решётки. Вместо этого, они продемонстрировали, что можно заменить гомоморфную составляющая на идеальных решётках на простую гомоморфную схему, которая использовала бы целые числа. Схема оказалась гораздо проще схемы Джентри, но, все же, заимствовала похожие параметры в плане гомоморфности и эффективности.

Гомоморфный элемент в работе Дейка [31] схож с криптосхемами, представленных ранее, Левьелом и Наккахой[32] в 2008 году и Брамом Кохеном[33] в 1998 году. Но метод Кохена не был гомоморфен по операции сложения. Схема Левьелы-Наккахи могла производить только вычисления по операции сложения, и может быть изменена для поддержки небольшого количества операций перемножения. Множество улучшений и оптимизаций схем были предложены в ряде работ Джен-Себастиан Корона, Танкрида Лепойнта, Аврадипа Мандалы, Дэвида Наккхи и Мехди Тибухи [34, 35, 36, 37].

Несколько новых схем, которые относят к гомоморфному шифрованию второго поколения, были разработаны с 2011 года Цвиком Бракерски, Крейгом Джентри, Видоном Вайкунтанаханом и другими. Такие разработки привели к более эффективным полностью гомоморфным схем шифрования. К ним относяться:

		Криптосистема Бракерски-Гентри-Вайкунтанахана (BGV)[38], построенная на технике Бракерски-Вайкунтанахана[39]. 

	Криптосистема Бракерски[40]. 

	Криптосистема на NTRU созданная Лопез-Альтом, Тромером и Вайкунтанаханом (LTV)[41].

	Криптосистема Гентри-Сахай-Вотерс (GSW)[42]. 

Две реализации второго поколения схем шифрования представлены для общественного пользования:

		Библиотека HElib [43] сделанная Шаем Хавели и Виктор Шоуп которая реализует криптосистему BGV с GHS оптимизацией

		Библиотека FHEW[44] сделанная Лео Дуглас и Даниэль Миккианакио которая является реализацией комбинации криптосистемы обучения с ошибками Регева и техники создания гибкой схемы Алперин-Шериффа и Пейкерта[45]. 

Обе библиотеки относятся к реализациям полностью гомоморфному шифрованию. HElib демнострирует результат в 5-10 минут для преобразования сжатого шифротекста с порядка 1000 знаков, в гибкий[46]. FHEW преобразует несжатый шифротекст в гибкий за порядка 1/2 секунды на один бит[47]. В конце 2014 обновленная реализация HElib демонстрировала результат в 4 минуты для расчета AES схемы для 120 входных потоков, достигнув тем самым удельной скорости в 2 секунды на один поток[43]. 

Кроме совершенствований криптосистемы Джентри, некоторые исследователи искали другие принципы построения полностью гомоморфного шифрования. Таким направлением является симметричное гомоморфное шифрование [48].

В работах [49, 50, 51, 52] в 2013 году попытались построить симметричную гомоморфную схему шифрования, используя полиномы от многих переменных, среди этих работ есть отечественные разработки. Другие работы в 2014 году посвящены гомоморфному шифрованию на основе матричных полиномов [53, 54].







1.2 Недостатки предложенных ранее методов





Можно подвести итоги предложенных методов, точнее, их недостатки, до 1993 года: существовали лишь системы либо аддитивно, либо мультипликативно гомоморфны. Позже, вплоть до 2009 существовали гомоморфные криптосистемы, которые могли бы выполнять сложения и одиночное умножение [19, 20], а также, можно отметить, что существовали криптосистемы, которые могли бы вычислять ветвящиеся программы [21], полиномы [22] и NC1 схемы при увеличении размера шифртекста [18]. 

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

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

Для «шумной» криптосхемы Джентри, процесс преобразования схемы в «гибкую» эффективно «обновляет» шифрованный текст. Используя к шифротексту гомоморфную операцию дешифрирования, получается новый текст, который шифрует те же данные что и раньше, но с меньшим уровнем шума. Время от времени обновляя шифротекст, когда тот достигает высокого уровня шума, можно проводить над ним безграничное число операций без помех. Защищенность своей схемы Джентри [25] обосновал двумя проблемами: проблемой сложности худшего случая криптографии на идеальных решетках и задачей о сумме подмножеств.

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

Защищенность многих схем реализованных с 2011 года обоснована на сложности решения проблемы обучения с ошибками. Только у LVT[41] схемы защита обоснована на варианте вычислительной NTRU задачи. У всех этих криптосистем, в отличие от схем, предложенных ранее, наиболее неспешное возрастание шума в процессе гомоморфных вычислений. Вследствие внесения дополнительной оптимизации сделанной Крейгом Джентри, Шаем Хавели и Найджелом Смартом, появилась система шифрования с практически оптимальной асимптотической сложностью: Сложность вычисления T операций над зашифрованными данными с параметром защиты k имеет сложность вычисления лишь T·polylog(k [55, 56, 57]. Данные оптимизации созданы на технике 
Смарта-Веркаутерена, позволила сжимать набор текстовых переменных в один шифрованный текст и обрабатывать переменные данные одним потоком[28]. Большинство достижений из второго поколения полностью гомоморфных криптосистем были использованы в схеме шифрования на целых числах[36, 37].

Цвика Бракерски и Видон Вайкунтанахан отметили, что для некоторых схем, криптосистема GSW демонстрирует слабое возрастание шума, и это дает большую эффективность и большую защищенность [58]. Якоб Алперин-Шерифф и Крис Пейкерт позднее описали эффективную технику модифицирования шифрованного текста в гибкий, которая как раз и использовала такой тип схем[59]. Но такой тип модифицирования, к сожалению, оказался не совместим с методами сжатия шифрованного текста, и в итоге, оптимизации 
Гентри-Сахай-Вотерс не имеет возможности применения к ней[57].









1.3 Возможности исправить недостатки известных решений





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

Есть другой путь, не идти по пути конструкции Джентри, а искать возможность альтернативных решений, чем и занимаются в основном отечественные исследователи. Такие работы представлены в работах: Бабенко Л., Буртыка Ф., Макаревич О., Трепачева А. [48], Жиров А., Жирова А., Кренделев С. [50,51], Ростовцев А., Богданов А., Михайлов М. [52], Буртыка Ф.[53,54]







1.4 Постановка задачи





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

		(1.1)

то есть должна существовать функция шифрования , где m – открытый текст, k – ключ шифрования, которая гомоморфна относительно операций * и + над открытыми текстами, при существования эффективного алгоритма M.

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

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






2 применяймые математические методы





Поскольку теорию полей Галуа используют в различных работах комбинаторики и теории кодирования, то она встречается в различных литературных источниках, одним из самых используемых является работа математиков Рудольфа Лидла и Гаральда Нидеррайтора[61], которая посвящена теории полей Галуа. Так же для изучения теории полей Галуа использовались учебные пособия по высшей алгебре[62, 63], компьютерной алгебры[64], криптографии[65, 66, 67], теории сигналов [68].

Для решения задачи дешифрования, в предлагаемом методе шифрования, нужно использовать алгоритмы, решающие задачу дискретного логарифмирования. Задача дискретного логарифмирования является основной из задач, на которых базируется криптография с открытым ключом, а так же, базируется безопасность таких современных криптографические алгоритмов как Диффи-Хеллмана, Эль-Гамаля, Мэсси-Омуры и др. Теоретические данные и готовые алгоритмы взяты с учебных пособий по криптографии [65, 69, 70, 71, 72, 73, 74]









2.1 Поля Галуа





Теория конечных полей началась с XVII-XVIII веков. Теорией конечных полей простого порядка занимались такие ученые, как Пьер Ферма, Леонард Эйлер, Жозеф Луи Лагранж, Адриен Мари Лежандр. Однако в этой работе необходима теория конечных полей, имеющая начало с работ Гаусса и Галуа[61]. 

В 1830 году восемнадцатилетний Эварист Галуа издал труд[75], который лёг в основу общей теории конечных полей. В своем труде Галуа вводит воображаемый корень сравнения , где  — произвольный многочлен степени v, неприводимый по модулю p. Потом рассматривается общее выражение , где  — некоторые целые числа по модулю p. Если присваивать этим числам всевозможные значения, выражение A будет принимать  значений. Далее Галуа демонстрирует, что эти значения образуют поле, и мультипликативная группа этого поля является циклической. Таким образом, этот труд является основой в фундаменте общей теории конечных полей. В отличие от ранних работ, где рассматривали только поля , Галуа рассматривает уже поля , которые стали называть полями Галуа в его честь.

Позже математик Элиаким Мур, в 1893 году, доказал теорему о классификации конечных полей, которая утверждает, что любое конечное поле является полем Галуа, другими словами поле из  элементов изоморфно полю классов вычетов многочленов с коэффициентами из  по модулю неприводимого многочлена степени n[76]. В этом же году Генрих Вебер, который первый, попытался дать аксиоматический подход к теории конечных полей. Он стремился объединить в своей работе понятия, которые возникли в разных разделах математики, в том числе и понятие конечного поля[77]. Позже в 1905 году Джозеф Веддербёрн доказывал малую теорему Веддербёра, которая заключалась в следующем, что любое конечное тело коммутативно, то есть является полем.

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

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

Под операцией над множеством подразумевают соответствие, при котором каждой паре элементов множества отвечает однозначно определенный элемент этого же множества. Элементы множества обычно обозначают буквами а, b, с, d, множества через М = {а, b, с, d, ...}, а операцию символически записывают в виде с = а * b. При операции сложения пишут с = а + b, а при операции умножения 
с = ab. Операции вычитания и деления обычно не рассматривают как основные, вследствие того, что они являются обратными, соответственно, для сложения и умножения.

Множество элементов называется полем, если заданы операции сложения и умножения, удовлетворяющие следующим законам [75, 78] 
(см. табл 1).

Поле, содержащее конечное число элементов q, называется конечным полем и обозначается GF(q) (GF — означает Galois Field — поле Галуа). Порядком конечного поля называется число элементов поля.

Множество, в котором задана только основная операция сложения и выполняются законы А1—A5, называется коммутативной аддитивной группой, а множество, в котором задана только основная операция умножения и выполняются законы M1 —M5 — коммутативной мультипликативной группой. Часто вместо термина «коммутативная группа» используется термин «абелева группа».

Группа, имеющая конечное число элементов, называется конечной группой. Конечная группа обозначается через G = {а, b, с, ...} Порядком конечной группы называется число элементов группы.

Все элементы любого конечного поля образуют аддитивную группу, поэтому порядок аддитивной группы поля совпадает с порядком поля. Мультипликативная группа поля включает все элементы поля, кроме нулевого, поэтому мультипликативная группа поля порядка q имеет порядок q— 1.

Таблица 2.1

Законы выполняющиеся в поле

Законы

Операция



сложение

умножение

Замкнутость: для каждой пары элементов существует, и притом единственный элемент 

А1.



М1.



Ассоциативность:



А2.



М2.



Коммутативность:



А3.



М3.



Наличие единичного элемента: существует элемент , такой, что , где 

А4.





М4.





Наличие обратных элементов для любого  существует элемент такой, что 

А5.





М5.





Дистрибутивность

D1. 

D2. 



Простым примером конечного поля является простое поле, элементами которого являются целые числа по модулю простого числа р.

Сравнение целых чисел х, у по модулю т [79] 

		 	х = у (mod т)	(2.1)
по определению эквивалентно равенству

		 	x — y = km	(2.2)
для некоторого целого k.

Все целые числа х такие, что x ? r(mod т) при фиксированном r, то есть числа, которые дают при делении на т остаток r, образуют класс чисел по модулю т, который обозначают через {r} или r(mod т). Из определения следует, что всем числам класса отвечает один и тот же остаток r и можно получить все числа класса, если в форме mk + r заставить k пробегать все целые числа. Соответственно т различным значениям r имеем т классов чисел по модулю т. Любое число класса называется вычетом по модулю m по отношению ко всем числам этого класса.

Из свойств сравнения известно [79], что если х ? a (mod m) и 
у ? b (mod m), то х + у ? а + b (mod m) и ху ? ab (mod m). Тем самым определены сложение и умножение классов вычетов по модулю т:

		 	{а} + {b} = {а + b},	(2.3)

		 	{а}{b} = {аb}.	(2.4)

Можно проверить, что все законы поля, исключая М5, удовлетворяются для сложения и умножения классов вычетов, заданных посредством (2.3), (2.4) при произвольном т. Однако М5 выполняется только при условии, что т = р, где р — простое число.

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

Таким образом, полная система вычетов по модулю простого числа р образует конечное поле порядка р, которое обозначают через GF(p) и называют простым полем Галуа.

Сложение и умножение элементов поля осуществляется в виде арифметических операций по модулю р над соответствующими числами.

Расширенное поле GF(pn). Аналогично сравнению целых чисел по модулю т можно определить сравнение для полиномов над полем GF(p).

Полином А (х) называется полиномом над полем GF(p), если его коэффициенты аi принадлежат полю GF(p). Степенью полинома А(х) называется наибольшее число п такое, что an   0(mod р).

Сравнение полиномов А(х), В(х) по модулю полинома F(x) [75, 78]

		 	A(x) ? B(x)(mod F(x))	(2.5)
по определению эквивалентно равенству

		 	A(x) – В(х) = К (x)F (х)	(2.6)
для некоторого полинома К(x).

Все операции в сравнении (2.5) выполняются по модулю р; данный факт обычно отмечают записью

		 	A(x) ? B(x)(modd F(x),p)	(2.7)

которая читается: полином А (x) сравним с полиномом В(х) по двойному модулю (F(x),p) [68].

Все полиномы A(х) над полем GF(p) такие, что А(х) ? R(x) (modd F(x), р) при постоянном R(x), то есть полиномы, которые дают при делении на F(x) остаток R(x), образуют класс полиномов по двойному модулю (F(x), р), который обозначают через {R(x)} или R(x) (modd F(x), р).

Из определения следует, что всем полиномам класса отвечает один и тот же остаток R(x) и можно получить все полиномы класса, если в форме 
F(x)K(x) + R(x) заставить К(х) пробегать все полиномы с коэффициентами из GF(p).

Если F(x) — полином степени п над полем GF(p), то всевозможные остатки R(x) — полиномы степени не выше п — 1:

		 		(2.8)

где каждое из а0, а1, ..., ап-1 может быть любым из р элементов поля GF(p).

Из (2.8) следует, что существует точно рп различных полиномов R(x). Соответственно имеется рп классов полиномов по двойному модулю (F(x), р). Любой полином класса называется вычетом по двойному модулю (F(x), р) по отношению ко всем полиномам этого класса.

В соответствии со свойством сравнений [75, 78], если 
А(х)?R(х)(modd F(х),р) и В(х)?Р(х)(modd F(х),р), то 
А(х)+B(х)?R(х)+P(х)(modd F(х),р) и А(х)В(х)?R(х)Р(х)(modd F(х),р).

Тем самым определены сложение и умножение классов вычетов по двойному модулю (F (х), р):



	 	{R (x)} + {Р (х)} = {R (x) + Р (x)} и 

		 	{R (х)} ? {Р (х)} = {R (х) Р (х)}.	(2.9)

Можно проверить, что все законы поля, исключая М5, удовлетворяются для сложения и умножения классов вычетов, заданных посредством (2.9) при произвольном F(x) над полем GF(p). Однако, так же, как это имело место при сравнении целых чисел, М5 выполняется только в том случае, если 
F(x)=f(x) — полином, неприводимый над GF(p).

Полином f(x) степени n?1 с коэффициентами из поля GF(p) неприводим над полем GF(p), если он не может быть представлен в форме f(x) =А(х)В(х), где А(х) и В(х) —полиномы над GF(p) [75].

Взяв от каждого класса по одному вычету, получим полную систему вычетов. Обычно в качестве полной системы вычетов употребляют полиномы степени не выше п — 1, т. е. полиномы вида (2.8).

Полная система вычетов по двойному модулю (f(x), р), где f(x) —полином, неприводимый над GF(p), и р — простое число, удовлетворяет всем законам поля.

Таким образом, полная система вычетов по двойному модулю (f(x), р) образует конечное поле, содержащее рп элементов, которые обозначают через GF(pn) и называют расширенным полем или расширением степени п простого поля GF(p).

Основополагающая теорема полей Галуа гласит [75, 78]: Для каждого простого числа р и произвольного п ? 1 существует конечное поле порядка рп, единственное с точностью до изоморфизма.

Ниже будем обозначать расширенное поле через GF(qs), где для расширения степени п поля GF (р), q = рп и s=1. Поле GF(qs) будем называть полем порядка qs характеристики р; при этом, для сокращения записи, будем писать 
А (х) ? В (х) (modd f (х), р), независимо от того, является ли поле порядка qs характеристики р расширением степени п поля GF (р) или расширением степени s поля GF (рп')

Период элемента поля GF(qs). Согласно свойству М1, если поле GF(qs) содержит элемент а, то оно должно содержать также степени а2=аа, а3=аа2,… Безусловно, что в конечном поле не все степени будут различными. Следовательно, должен существовать такой наименьший положительный показатель степени ?, что а? ? 1 (modd f (х), р); ? в этом случае называется периодом элемента а [75, 78]. Если период элемента а равен ?, то элементы 
а°, а1,... , а?-1 все различны. Так как порядок мультипликативной группы поля GF (qs) равен qs - 1, то максимально возможный период элементов поля GF (qs)

		 	?max=qs -1	(2.10)

Отметим, что в поле характеристики р не может быть элементов, период которых кратен р. И в самом деле, если предположить обратное, что 
? = kp, то по определению периода элемента akp ? 1 и akp — 1 = 0. Но в поле характеристики р всегда справедливо [75, 78]

		 	aP±bP = (a±b)P.	(2.11)

Поэтому 0 ? akp — 1 ? (ak—1)p отсюда следует, что период ? элемента а есть k, что противоречит сделанному допущению.

Теорема о периоде элемента поля GF(qs). Если известен период произвольного элемента поля GF(qs), то можно установить период элемента ak, где k — произвольное целое число, если воспользоваться теоремой о периоде элемента поля [75].

	Если период элемента а равен ?, то период элемента аk есть ?/(?, k), где 
(?, k) — наибольший общий делитель чисел ? и k.	(2.12) 

	В частности, из данной теоремы следует, что порядок мультипликативной группы поля GF(qs) всегда кратен периоду любого его ненулевого элемента или, иными словами, что период е любого ненулевого элемента поля GF(qs) всегда делит порядок мультипликативной группы поля qs—1; последнее записывается как ?| qs—1 [83].

	Также из теоремы о периоде элемента вытекает, что если ? и k взаимно простые числа, то период элемента ак равен периоду элемента а, т. е., если 
(?, k)= 1 и а?= 1, то ? 1, ?1 == kt.	 (2.13)

Первообразный элемент поля GF(qs) [82]. Элемент а, имеющий максимально возможный период (2.10), называется первообразным элементом поля GF(qs). Если обозначить первообразный элемент буквой , то степени  различны и пробегают все ненулевые элементы поля GF(qs). Поэтому первообразный элемент поля является образующим элементом мультипликативной группы поля G:

G = {}

	и	(2.14)

GF (qs) = {}.

Так как qs-1 ? 1, то qs ? 0, qs+1 ? 2,..., и мультипликативная группа поля GF (qs) — циклична.

Если  — первообразный элемент поля GF (qs), то все степени , где k и qs — 1 — взаимно простые числа, также являются первообразными элементами этого поля. Таких чисел k имеется (qs — 1), где  — функция Эйлера [79]. Функция Эйлера (k) определена для всех целых положительных k и представляет собой число чисел ряда 0, 1,..., k — 1 взаимно простых с k.

Следовательно, в поле GF(qs) имеется

		 	 (qs — 1)	(2.15)
первообразных элементов.

Далее, если	 — первообразный элемент поля GF(qs) то мультипликативно обратный элемент  тоже является первообразным, так как — 1 ?qs - 2 (mod qs— 1), a qs—2 и qs—1 всегда взаимно просты. Поэтому в поле GF(qs) имеется

		 		(2.16)
первообразных элементов  и столько же мультипликативно обратных им.

Если элемент а поля GF (qs) имеет период ?, где ?|qs -1, то все степен.......................