рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Расширение полей

Расширение полей - Лекция, раздел Математика, Материалы лекций Математические основы криптологии   Рассмотрим, Какова Связь Полей Gf(P) И Gf( P N ). ...

 

Рассмотрим, какова связь полей GF(p) и GF( p n ).

 

Пусть F - поле. Подмножество К поля Р, которое само является полем относительно операций поля Р, называется подполем. В этом случае F называется расширением поля К. Если K≠F , то К - собственное подполе.

Пример .Поле с множеством R действительных чисел является расширением поля с множеством рациональных чисел.

Поле GF( p n ) содержит единственное подполе, число элементов в котором простое и поэтому может рассматриваться как расширение поля GF(p) [2].

Поле GF(p) не имеет собственных подполей. Такие поля называются

 

простыми.

 

Теорема .(о существовании и единственности конечных полей) [11]. Для каждого простого числа q и каждого натурального числа n существует конечное поле GF(qn) из qn элементов.

Поле GF(qn) является расширением поля GF(q). qn называется порядком


 

поля GF(qn), натуральное число n - степенью поля, а простое число q -

 

характеристикой поля GF(qn).

 

Каждое подполе GF(qm) поля GF(qn) имеет порядок qm, где m | n и m > 0. И обратно - если m | n и m > 0, то для поля GF(qn) существует только одно подполе GF(qm) из qm элементов.

Пример. Подполя конечного поля GF(230) можно найти, вычислив все

положительные делители числа 30: 1, 2, 3, 5, 6, 10, 15. Представим взаимосвязи подполей в виде следующего рис. 2.3.

 

 

GF(230)

 


GF(26)

 

 

GF(22)


GF(210) GF(2 )

 

GF(23)


GF(25)

 

GF(2)

Рис. 2.3. Взаимосвязи подполей поля GF(230)

 

Элементами конечного поля GF(qn) (поля полиномов), число которых равно qn,

являются все полиномы (многочлены) вида

 

f(x) = αn−1xn−1 + ... + α1x + α0

 

- c коэффициентами αi ÎGF(q),

 

- со степенями от 0 до n-1 ( i = 0, n - 1 ),

 

- со степенью deg(f(x)) = n-1.

 

Данные полиномы f(x) называются полиномами над полем GF(q).

 

Для проверки примитивности полинома f(x) над полем GF(qn)

 

достаточно убедиться, что выполняются условия:

 

qn -


1) x


1 ºx mod


f ( x) ;


 


 

2) x


qn -1

pi º/


 

x mod


 

f ( x)


 

для "i = 0, k - 1 ,


 

 


k -1

i
где pi определяются из канонического разложения числа qn − 1 = Õpai


 

на k


 

 

простых сомножителей, αi - натуральные числа.


i = 0


 

Вопросы для самопроверки.

 

1. Что такое расширение конечного поля? Что такое подполе?

 

2. Какие полиномы над GF(qn) являются элементами конечного поля?

 

3. Поясните понятия порядок поля, степень поля, степень полинома.

 

4. Поясните понятия неприводимый и примитивный полиномы.

 

5. Поясните понятие эквивалентности двух полиномов.

 

6. Что такое НОД от двух полиномов? Как он вычисляется?

 

7. Каким образом можно определить примитивность полинома f(x) степени n над полем GF(q)?

 

 

Вычисление обратного элемента в конечном поле GF(2n)

 

Обратный элемент в конечном поле GF(2n) (n - натуральное число) используется как вспомогательный элемент при делении некоторого многочлена A(x) на многочлен B(x) в поле GF(2n) по полиному-модулю P(x). Результирующий полином C(x) будет получен как C(x) = A(x)? B-1(x) mod P(x), где B-1(x) - обратный элемент для многочлена A(x).

Одним из способов получения обратного элемента в поле полиномов является использование функции Эйлера. Понятие функции Эйлера по аналогии переносится из теории чисел в поле GF(2n).

Пусть задан неприводимый модуль-полином P(x). Функция Эйлера в поле GF(2n) будет задавать число взаимно простых с P(x) полиномов. Так как P(x) является неприводимым, то функция Эйлера φ(P(x)) = 2n - 1.

Тогда, применяя функцию Эйлера, обратный элемент будет

 

вычисляться как

 

- jP x - n -


A 1 ( x) =A (


( )) 1 (x) mod P( x) =A2


2 ( x) mod P(x) .


 

Обратный элемент в поле GF(qn), где q - простое число, также можно


 

вычислить и по модификации алгоритма Евклида, находящей переменные выражения α·a + β·b = НОД(a, b) (раздел 1.1), только вместо чисел в формулу будут подставляться полиномы. Для нахождения обратного элемента g−1(x) для полинома g(x) по полиному-модулю f(x) в качестве решаемого уравнения используется g−1(x)g(x)+t(x)f(x) = 1, где g−1(x), g(x), t(x), f(x)ÎGF(qn).

Пример 3.11. Пусть заданы элемент поля A(x) = x2 + 1 и полином-

 

модуль P(x) = x3 + x + 1 в поле GF(23). Найдем обратный элемент A-1(x).

 

Тогда, применяя формулу Эйлера, получим:

 

A-1 ( x) = Aj( P( x ))-1 (x) mod P(x) = (x 2 + 1)2 -2 mod( x3 + x + 1) =

= ( x 2 + 1)6 mod(x3 + x +1) = (x 2 + 1)2 ( x 2 + 1)4 mod(x3 + x + 1) .

 

Найдем остаток от деления для первого слагаемого


 

(x2 +1)2 =x4 +2x2 +1=x4 +1


 

(слагаемое 2x2 сокращается, так как


 

коэффициенты полиномов складываются по модулю 2) на модуль P(x),

 

например, делением столбиком.

 

Åx4 +0·x2+0·x+1 | x3 + x + 1

x4 + x2 + x | x x2 + x + 1


То есть


(x2 +1)2 mod(x3 +x +1) =x2 +x +1.


 

Далее найдем остаток от деления для второго слагаемого

 

((x 2 + 1)2 )2 = (x 2 + x + 1)2 = x 4 + x 2 + 1 на модуль P(x).

 

Åx4 + x2+0·x+ 1 | x3 + x + 1

x4 + x2 + x | x x + 1


То есть


(x2 +1)4 mod(x3 +x +1) =x +1.


 

Вычислим итоговое выражение:

 

(x2 +1)2 (x2 +1)4 mod(x3 +x +1) =(x2 +x +1)(x +1)mod(x3 +x +1) =


=(x3 +1)mod(x3 +x +1)


и найдем остаток от деления:


 

Åx3 +0·x+1 | x3 + x + 1

x3 + x + 1| 1

x

Тогда, обратным элементом является A-1(x) = x.

 

Выполним проверку: должно выполняться сравнение


 

A(x)? A−1(x)mod P(x) ≡ 1.

 

(x2 + 1) ? x mod P(x) = (x3 + x) mod (x3 + x + 1).

 

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

Å 1010

1011

То есть результатом является полином 1 и A(x)? A−1(x)mod P(x) ≡ 1.

 

Ответ: обратным элементом для полинома A(x) = x2 + 1 в поле GF(23),

 

где полином-модуль P(x) = x3 + x + 1, является многочлен A-1(x) = x.

 

Пример 3.12. Рассмотрим предыдущий пример с помощью взаимосвязи векторного и степенного представлений элементов. Пусть заданы элемент поля A(x) = x2 + 1 и полином-модуль P(x) = x3 + x + 1 в поле GF(23). Найдем обратный элемент A-1(x).

Примитивным элементом, с помощью которого можно получить все остальные элементы, является полином x (табл.3.8). Остальные элементы получим, умножая предыдущий элемент на x.

 

Для элементов 4, 6 и 7 необходимо выполнить нормировку модулем

 

P(x), например, с помощью деления столбиком:

 


4-ый элемент

Åx3 |x3+x+1

x3+x+1| 1

x+1


6-ой элемент

Åx3+x2 |x3+x+1

x3+ x+1| 1

x2+x+1


7-ой элемент

Åx3+x2+x |x3+x+1

x3+ x+1| 1

x2+ 1


 

Таблица 3.8. Элементы поля в разных представлениях

 

    Номер элемент а Нормальный базис ξ i (степенное представлени е) Стандартный базис (векторное представлени е)     Полиномиальное представление
ξ ¥
ξ 0
ξ 1 x
ξ 2 x2
  ξ 3=ξ 2ξ mod P(x )     x3 mod P(x) = x+1
ξ 4 (x+1)x = x2+x
  ξ 5 = ξ 4ξ mod P(x)   (x2+x)x = (x3+x2)mod P(x) = x2+x+1
  ξ 6= ξ 5ξ mod P(x)   (x2+x+1)x = (x3+x2+x) mod P(x) = x2+1

 

 

Применяя формулу Эйлера, получим:

 

A-1 ( x) = Aj( P( x ))-1 (x) mod P(x) = (x 2 + 1)2 -2 mod( x3 + x + 1) =

= ( x 2 + 1)6 mod(x3 + x +1) = (x 2 + 1)2 ( x 2 + 1)4 mod(x3 + x + 1) .

 

Выражение (x2+1)2 mod P(x) можно вычислить, используя взаимосвязь векторного и степенного представлений элементов. Полиномиальная запись x2+1 соответствует векторной записи 101 и степенной ξ 6. Тогда, применяя

правило умножения степеней примитивного элемента (раздел 3.2), получим

 


n
ξ 6?ξ 6 mod P(x) = x12mod(2 -1)


= x12 mod 7


= ξ5. То есть 6-му элементу ξ5 поля


 

GF(23) соответствует полиномиальное представление x2 + x + 1 (векторное

 

111).

 

Аналогично, (x2+1)4 mod P(x) = (ξ5)2 mod P(x) = x 10 mod 7 = ξ 3. То есть 4-му элементу ξ3 поля GF(23) соответствует полиномиальное представление x + 1

(векторное 011).

 


В итоге,


(x2 +1)2 (x2 +1)4 modP(x)


= ξ5?ξ3 mod P(x) = x8 mod 7 = ξ. То есть


 

2−му элементу ξ поля GF(23) соответствует полиномиальное представление x

 

(векторное 001).


 

Обратный элемент можно было найти и сразу:

 


(x2 +1)6 modP(x)


= (ξ 6)6 mod P(x) = ξ 36 mod7 = ξ .


 

Проверим условие существование обратного элемента - выполнимость сравнения A(x)? A−1(x)mod P(x) ≡ 1. Получим

(x2 + 1) ? x mod P(x) = ξ6? ξ mod P(x) = ξ7 mod 7 = ξ0 ≡ 1.

 

Ответ: обратным элементом для полинома A(x) = x2 + 1 в поле GF(23),

 

где полином-модуль P(x) = x3 + x + 1, является многочлен A-1(x) = x.

 

Пример 3.13. Рассмотрим пример 3.11, оперируя элементами поля, заданными в векторном представлении. Пусть заданы элемент поля A(x) = x2 + 1 и полином-модуль P(x) = x3 + x + 1 в поле GF(23). Найдем обратный элемент A−1(x). Будем использовать таблицу 3.8 из примера 3.12.

Применяя формулу Эйлера, получим:

 

A-1 ( x) = Aj( P( x ))-1 (x) mod P(x) = (x 2 + 1)2 -2 mod( x3 + x + 1) =

= ( x 2 + 1)6 mod(x3 + x +1) = (x 2 + 1)2 ( x 2 + 1)4 mod(x3 + x + 1) .

 

Полином (x2 + 1) можно записать в векторном виде как 101 (табл. 3.8).


 

1. Найдем значение (x2 + 1)2 в векторном виде:

Ä101

101

Å101

101

10001 «x4 + 1

3. Найдем значение ((x2 + 1)2)2 =

= (x2 + x + 1)2 в векторном виде:

Ä111

111

Å111

111

10101 «x4 + x2 + 1


 

2. Нормируем полученный результат x4 + 1 модулем P(x):

Å10001 | 1011

1011 | 1

111 «x2 + x + 1

 

4. Нормируем результат x4 + x2 + 1

модулем P(x):

Å10101 | 1011

1011 | 1

11 «x + 1


 


5. Вычислим в векторном виде

( x 2 + 1)2 (x 2 + 1)4 = ( x 2 + x +1)(x + 1) :

Ä 111

011

Å111

111

1001 «x3 + 1


6. Нормируем результат x3 + 1

модулем P(x):

Å1001 | 1011

1011 | 1

10 « x


Тогда, обратным элементом является A-1(x) = x.

 

Выполним проверку: должно выполняться сравнение

 

A(x)?A−1(x)mod P(x) ≡ 1.


 

1. Вычислим значение (x2 + 1) ? x в векторном виде:

Ä101

010

1010 «x3 + x


 

2. Нормируем результат x3 + x

модулем P(x):

Å1010 | 1011

1011 | 1

1 « 1

Результатом является полином 1 и

A(x)?A−1(x)mod P(x) ≡ 1.


Ответ: обратным элементом для полинома A(x) = x2 + 1 в поле GF(23),

 

где полином-модуль P(x) = x3 + x + 1, является многочлен A-1(x) = x.

 

 

Дополнительные примеры для решения.

 

Вычислите обратные элементы для:

 

1) x+1 по модулю x4 + x + 1 в поле GF(24) (ответ: x3+x2+x);

 

2) x2+x по модулю x3 + x + 1 в поле GF(23) (ответ: x + 1),

 

с помощью полиномиального и векторно-степенного представлений.

 

Вопросы для самопроверки.

 

1. Как можно вычислить обратный элемент в конечном поле GF(2n)?

 

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

3. Как выполняется сложение и умножение элементов в степенном представлении?

 

4. Каким образом нормируются результаты большей, а также равной степени, чем у полинома-модуля?

5. Как можно проверить, что обратный элемент был найден правильно?


 

 

– Конец работы –

Эта тема принадлежит разделу:

Материалы лекций Математические основы криптологии

В М Захаров.. Материалы лекций.. Математические основы криптологии..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Расширение полей

Что будем делать с полученным материалом:

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

Все темы данного раздела:

Лекция№1
    Криптология состоит из двух направлений: криптографии и криптоанализа.   Криптография – наука о способах преобразования (шифрования)

Асимметричное шифрование
    Алгоритм RSA (Revest, Shamir, Adelman) 1978г. e, n А, М В    

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

Алгоритм Евклида
  Алгоритм Евклида дает правило вычисления наибольшего общего делителя   (НОД) 2-х натуральных чисел. (a,b)= d , где d – НОД НОК – наименьшее общее кратное

Алгоритм рае кнута
   

Свойства делимости целых чисел
  Два числа a и b называются взаимно простыми если их НОД = 1   (a1,a2,….,an)= НОД   (a1,a2) = d1   (a3,d1) = d2

Свойства делимости целых чисел
  Свойства приведены без доказательства.   1)Свойство дистрибутивности   Пусть заданны три натуральных числа a,b,

Простые числа
  1)- каноническое разложение &nb

Получение простых чисел
  По мере того как мы будем изучать курс «Математические основы криптологии» мы будем возвращаться к этой теме. Задача получение простых чисел во многом зависит от того как с

Проверка простоты чисел Мерсенна
  Числами Мерсенна называются числа вида М(p) = 2p - 1, pÎN.   Задача для чисел Мерсенна - поиск в ряду э

Sp-2 mod M(p) ≡ 0, т.е. остаток равен 0
  Поясним, каким образом задается ряд Sk. Члены последовательности  

Алгоритм Бухштаба
  Данный алгоритм приведен из книги Бухштаба А.А. "Теория чисел" [4]. Пусть задано натуральное нечетное число n, n ≥ 9, которое необходимо разложить на 2

Алгоритм Ферма
  Алгоритм Ферма похож на алгоритм Бухштаба и является эффективным, если у раскладываемого числа n есть делитель (который

Функция Эйлера
  Имеется целое, положительное число m. Оно может быть как составным, так и простым. Функцию Эйлера принято обозначать, практически во всех учебниках как:  

Мультипликативная функция
  Имеем два натуральных числа a и b, если они взаимно просты, то мультипликативная функция устанавливает число взаимно простых чисел, для произведение двух взаимно простых чисел по фо

Числовая функция
  Это функция устанавливающая целую часть от некоторого рационального числа [a] – обозначение   может быть как положительное, так и отрицательное число

Для возведение натуральных чисел по модулю в большие степени
    Функция Эйлера может быть использована для возведение больших чисел в большую степень по модулю.     Имеется целое число

Возведение натуральных чисел по модулю в большие степени по схеме Горнера
Пусть задано выражение вида   y = a x mod m , (1.1)   где a ÎN - основание степени,  

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

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

Доказательство теоремы Эйлера
  Пусть даны m и φ(m)=k   Имеем число a, причем (a,m)=1     Берем ряд натуральных чисел: a1

Модулярная арифметика (продолжение) Квадратичные вычеты Степенные вычеты
  Продолжим исследовать вычеты. Широкое применение в криптографии нашла формула: xn ≡ a mod m, n=2 xn ≡ a mod p – квадратичный выч

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

Кольца и поля
  Алгебраические структуры с двумя бинарными операциями - сложение и умножение.     Определение 1.7. Множество S называется кольцом, е

Характеристика поля
  Определение 1.12. Если в поле Fq все ненулевые элементы имеют аддитивный порядок k, то говорят, что поле Fq имеет характеристику k. Обозначение. р - простое число.

Вычисление обратных элементов
  В арифметике действительных чисел просто вычислить обратную величину a−1 для ненулевого a: a-1 = 1/a или a? a-1 = 1.

Многочлены над конечным полем
  Onределенuе 1.13. Многочленом (относительно х) над полем GF(p)   m

Для любого простого р и nÎN существует хотя бы один неприводимый над полем GF(p) многочлен степени n [9]
Любой неприводимый над полем GF(p) многочлен степени п делит     многочлен x pm - x   (также и мног

Алrебраические структуры над множеством многочленов
  Кольцо многочленов над полем GF(p)   Определение 1.17. Кольцо, образованное многочленами над полем GF(p), называется кольцом многочлен

Системы уравнений сравнений
  Общий вид:   x ≡ c1 mod m1   x ≡ c2 mod m2

Pound; b£ n-1
  Если для каждого простого делителя p числа n-1 справедливы следующие утверждения:     (1) bn-1≡ 1(mod n),  

Числа Кармайкла
  Может ли составное нечетное число n быть псевдопростым по всем взаимно-простым с ним основаниям b? Забегая вперед, скачем, что «да».     Заметим

Процедура получения устойчивых простых чисел
  1. Генерируются простые числа s,t   2. Получаем простое число r такое что, (r-1) делит t без остатка: r-1|t На основе этих двух операций получаем про

М-последовательности. ГПСЧ типа ЛРС1
  Опр ед ел ени е. Последовательностью над полем   GF ( p)   будем   назы

M - последовательности на основе произведения многочленов
Рассмотрим способ построения схемы линейного регистра сдвига на основе характеристического многочлена, задаваемого как произведение   многочленов, при &nbs

Произведения многочленов
  Рассмотрим следующие свойства ЛРП, порождаемой схемой ГПСП,   изображенной на рис. 2.1, при a0 =1.  

ЛЕКЦИЧ 16
  Способы представления элементов поля GF(2n)   Для представления элементов в полях Галуа вида GF(2n) существуют ра

Алгоритм получения элементов поля GF(2n) в стандартном базисе
  Для построения элементов поля GF(2n) в стандартном базисе существует следующий алгоритм, использующий сдвиговыерегистры. На входе: поле GF(2n

Заданными в стандартном базисе
   

Алгоритм асимметричного шифрования RSA
  Алгоритм RSA предложили в 1978 г. 3 автора: Райвест (Rivest), Шамир (Shamir) и Адлеман (Adleman). RSA является алгоритмом с открытым ключом, работающим в режимах шифрования данных и

Математическая модель алгоритма RIJNDAEL
  Байты можно рассматривать как элементы конечного поля GF(28) -   многочлены степени не более 7   а7х7 + а6х

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

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги