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

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

ЛЕКЦИЧ 16

ЛЕКЦИЧ 16 - Лекция, раздел Математика, Материалы лекций Математические основы криптологии   Способы Представления Элементов Поля Gf(2N)...

 

Способы представления элементов поля GF(2n)

 

Для представления элементов в полях Галуа вида GF(2n) существуют различные способы, образующие изоморфные поля:

- полиномиальное;

 

- стандартный базис;

 

- при помощи сопровождающей матрицы;

 

- параллельные массивы;

 

- нормальный базис - в виде:

 

- значения степеней примитивного элемента ξ,

 

- степеней примитивного элемента ξ.


 

I. Полиномиальное представление.

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

 

f(x) = a0 + a1x + … + an−1xn-1, (3.1)

 

- степени deg(f(x)) ≤ n-1

 

- с коэффициентами ai ÎGF(2).

 

II. Стандартный базис(векторное представление):

 

- элементы поля задаются полиномами вида (3.1);

 

- хранятся коэффициенты полинома f(x) в виде двоичного вектора. Используются 2 метода расположения старших степеней полинома f(x):

- математическая форма записи (запись слева направо):

 

- слева располагается старшая степень полинома,

 

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

- обратный порядок (запись справа налево):

 

- оптимально для операций умножения и сложения полиномов. Достоинствами векторного представления является следующее:

- рационально используется память,

 

- простота выполнения операций сложения и вычитания полиномов

 

(например, на регистровых структурах).

 

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

Операция получения бинарного коэффициента полинома реализуется следующим образом:

1) находится байт, содержащий требуемый коэффициент в виде бита;

 

2) байт сдвигается вправо, чтобы бит оказался на младшей позиции байта;

3) байт логически умножается на двоичную единицу:

 

- для обнуления остальных бит,


 


 

как:


- и выделения нужного бита.

 

На языке программирования Сиоперацияполучения бита выполняется

 

(x >> i) & 1,


 

где x - значение машинного слова,

 

i - позиция искомого бита,

 

>> - сдвиг значения переменной x на i позиций вправо (слева добавляются нули),

& - операция логического умножения.

Для установки значения y (y Î{0, 1}) для i-го бита используется операция:

 

(x & ~(1 << i)) | (y << i),

 

где << - операция сдвига значения переменной y на i позиций влево (справа добавляются нули),

~(…) - двоичная инверсия значения в скобках,

 

| - операция логического сложения,

(x & ~(1 << i)) - обнуление i-го бита в переменной x (демаскирование i-го бита).

 

Левая часть выражения обнуляет i-ый бит в числе x, а правая часть -

 

устанавливает новое значение y в i-ю позицию.

 

Стандартный базис применяется:

 

- для перевода между собой двух типов представления элементов нормального базиса:

- из степени примитивного элемента в его значение,

 

- и обратно.

 

III. Представление элементов конечного поля GF(2n) при помощи

 

сопровождающей матрицы A, заданной примитивным многочленом

 

ψ(x) = a0 + a1x + … + an−1xn-1 + xn, где ai Î{0, 1}.

 

Сопровождающая матрица A строится на базе полинома-модуля ψ(x)

 

следующим образом.


 

 

1. Матрица A = (aij), aij Î{0, 1}, i, j = 0, n - 1, заполняется нулями.

 

2. Единицами заполняется главная нижняя поддиагональ:

 

- для "i = 1, n - 2 выполняется аi+1,I = 1.

 

3. В верхнюю строку матрицы записываются коэффициенты при неизвестных ψ(x) в порядке убывания степеней неизвестных:

- для i = 0, n - 1: a0,i = an-i-1.

 

n
Тогда получим матрицу следующего вида (рис.3.1).

 


Степени этой матрицы A, A2, …,

 

определяют элементы поля GF(2n):


A2 -1


 

вместе с нулевой матрицей


 

- нижняя строка матрицы А i в виде вектора (a(n-1)0, a(n-1)1, …, a(n-1)(n-1))

 

задает

 

- соответствующий i-ый элемент поля GF(2n) - степень примитивного элемента ξ i, "i = 0,2 n - 2 .

an-1 an-2 an-3 … a2 a1 a0

1 0 0 0 0 0

An?n = 0 1 0 0 0 0

0 0 1 0 0 0

… … …

0 0 0 0 1 0

Рис.3.1. Структура сопровождающей матрицы

 

 

Пример 3.1. Представим элементы поля GF(23) в виде степеней сопровождающей матрицы.

Для многочлена ψ(x) = x3 + x + 1 сопровождающая матрица имеет вид

 

(рис. 3.2):

 

 
A3?3 =
 

Рис.3.2. Сопровождающая матрица для полинома ψ(x) = x3 + x + 1


 

Получим следующее множество элементов поля: (0, E, А, А2, А3, А4, А5,

 

А6) (рис. 3.3), где E - единичная матрица размера n? n и А7 совпадает с E:

 

         
0 = ; E= ; A=
         

 

         
A2= ; A3= ; A4=
         
                           
A5= ; A6= ; A7=
         

Рис. 3.3. Степени матрицы A

 

Для хранения элементов поля требуется объем памяти:

 

- равный 2n? n? n = 2n? n2 бит,

 

- где n? n - объем памяти под одну матрицу. Для операций:

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

 

- можно хранить только матрицу A.

 

При вычислении матрицы A i, "i = 2, 2n - 2 :

 

- потребуется выполнить (n-1)? n2? (i-1) операций сложения и

 

- n? n2? (i-1) операций умножения,

 

- где (i-1) - количество последовательных возведений в степень,

 

- (n - 1) - количество операций для получения одного элемента результирующей матрицы при умножении матриц Ai-1 и A.

Данный способ представления элементов поля применяется:

 

- при умножении двух полиномов методом Paar [16]:

 

- замена комплексной операции умножения

 

- на множество умножений и сложений полиномов меньших степеней;

- для получения значений степеней примитивного элемента при использовании нормального базиса.


 

IV. Представление полиномов в виде параллельных массивов, где элементы:

- первого массива хранят степени неизвестных полинома (степень при неизвестной с ненулевым коэффициентом),

- а элементы второго - коэффициенты при неизвестных.

 

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

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

- при которых находятся коэффициенты,

 

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

V. Нормальный базис. Элементы поля представляются в виде:

 

- степеней примитивного элемента,

 

- которым сопоставлены бинарные значения элементов поля (элементы в стандартном базисе).

Для поля GF(2n) требуется вычислить и хранить:

 

- (2n - 1) степеней примитивного элемента,

 

- каждая из которых имеет длину n-1 бит.

 

Все элементы поля GF(2n) можно записать в виде множества:

 

n
GF(2n) = {0, 1, ξ, ξ2, …, x2 -2 },

 

где ξ - примитивный элемент.

 

Для получения элементов поля GF(2n) в этом базисе можно использовать:

- способ последовательного умножения ξ i на ξ (то есть ξ используется

 

как образующий элемент поля GF(2n));

 

- вычисление сопровождающей матрицы A. Пример 3.2. Построим поле GF(2n), где n = 3. Пусть даны:

- неприводимый полином-модуль ψ(x) = x3 + x + 1 и


 

- ξ - заранее известный примитивный элемент поля, являющийся корнем модуля, т.е. если ψ(ξ) = ξ3 + ξ + 1 = 0.

Тогда GF(23) = (0, 1, ξ, ξ2, ξ3, ξ4, ξ5, ξ6).

 

Элементы поля GF(23) в нормальном базисе можно построить следующим образом:

1) на каждом шаге будем умножать предыдущий элемент поля на ξ;

 

2) если получается полином, степень которого ≥ deg ψ(ξ) (x заменили на

ξ), то осуществляется взятие остатка от деления текущего результата на полином ψ.

 


ξ0=1 = (001) ξ1=ξ = (010) ξ2=ξ2 = (100) ξ3=1+ξ = (011)


ξ4=ξ+ξ2 = (110) ξ5=ξ3+ξ2 = (111) ξ6=ξ4+ξ3 = (101) ξ7=1=ξ0.


 

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

 

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

 

- нерационален,

 

- так как хранится большое количество информации.

 

Существует 2 формы представления элементов поля в нормальномбазисе - в виде:

- значения степеней примитивного элемента;

 

- степеней примитивного элемента.

 

а) Хранение значений степеней примитивного элемента(эквивалент стандартного базиса):

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

- значение ξ i представляется в виде двоичных коэффициентов

 

n
многочлена ξ i;

 


- для хранения поля GF(2n) = (0, 1, ξ, …, ξ i, …,

 

двумерный вектор - матрица,


x2 -2 ) используется


 

- каждая i-ая строка матрицы содержит двоичное значение элемента ξ i.

 

Матрица будет иметь следующий размер:

 

- количество строк (количество степеней примитивного элемента)

 

равно 2n-1,

 

- количество столбцов n,

 

- где n - максимальная степень полинома-модуля,

 

- то размер равен (2n-1)? n ячеек.

 

б) Хранение степеней примитивного элемента, а не значения степеней примитивного элемента:

- для задания элемента ξ i хранится степень i;

 

- элемент, равный 1, заменяется на ξ 0, а соответственно его степень равна 0;

- если значение степени примитивного элемента равно 0, то принимается:

- что показатель степени примитивного элемента равен неопределенности,

- обозначаемой символом "¥".

 

Использование данного метода хранения:

 

- дает выигрыш в памяти,

 

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

- упрощает операции умножения элементов и возведения их в степень,

 

- так как операции выполняются не с векторами, а с целыми числами -

 

степенями элементов.

 

В качестве недостатков можно отметить:

 

- так как в основном в операциях с элементами поля участвуют сами значения элементов поля,

- то требуется система перевода степени примитивного элемента в его значение;

- неэффективен при сложении элементов;


 

- увеличивается время работы алгоритма:

 

- на преобразование из степени в значение и обратно;

 

- для этого используется предварительно полученная матрица из пункта а).

При вычислении некоторой операции с элементами, заданными в видестепеней (например, сложение элементов):

- элементы поля записываются в стандартном базисе (в векторном представлении);

- над ними выполняются арифметические операции;

 

- в конце возможно обратное преобразование результата:

 

- результирующий бинарный вектор ищется в матрице из пункта а),

 

- номер найденной строки i и будет задавать степень элемента ξ i.

 

Пример 3.3. В табл. 3.1 записаны элементы поля GF(24) в разных представлениях для полинома-модуля ψ(x) = x4 + x + 1.

В полиномиальном представлении следующий элемент получается:

 

- путем умножения предыдущего элемента, заданного в виде полинома,

 


на x;


 

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


 

степени модуля,

 

- то выполняется нормирование результата - поразрядное сложение по модулю 2 результата и полинома ψ(x).

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

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

 

Таблица 3.1 (окончание). Элементы поля в разных представлениях

 

  ξ 8 = ξ 7ξ mod φ(x)   (x3+x+1)x = (x4+x2+x)mod φ(x) = x2+1
ξ 9 = ξ 8ξ (x2+1)x = x3+x
  ξ10= ξ 9ξ mod φ(x)   (x3+x)x = (x4+x2)mod φ(x) = x2+x+1
ξ11= ξ10ξ (x2+x+1)x = x3+x2+x
  ξ12=ξ11ξ mod φ(x)   (x3+x2+x)x = (x4+x3+x2) mod φ(x) = x3+x2+x+1
  ξ13=ξ12ξ mod φ(x)   (x3+x2+x+1)x = (x4+x3+x2+x) mod φ(x)= x3+x2+1
  ξ14=ξ13ξ mod φ(x)   (x3+x2+1)x = (x4+x3+x) mod φ(x) = x3+1

 

Рассмотрим получение 11-го элемента. Для получения 11-го элемента

 

10−ый элемент умножается на x:

 

(x3 + xx = x4 + x2.

 

Поразрядно сложим векторы коэффициентов для полинома

 

x4+x2 (101002) и полинома-модуля x4 + x + 1 (100112):

 

Å100112

001112.

Получаем 11-ый элемент, равный:

 

- в стандартном базисе 01112,

 

- или в полиномиальном x2 + x + 1.

 

Если степень результата будет > степени модуля ψ(x), то осуществляется деление результата на ψ(x). Например:

- получим 11-ый элемент через 7-ой;

 

- умножим полином, соответствующий 7-му элементу, на x4: (x3 + x2)·x4= x7 + x6;

- так как степень результата > степени модуля, то выполняется деление результата на модуль ψ(x) (например, столбиком), а не сложение с ним:


 


x7 +x6

Å

x7 +


 

 

x4 +x3


x 4 + x + 1

x3 +x2 +1


 

x6 +x4 +x3


Å x6 +

 

x4 +

Å x4 +


 

x3 + x 2

 

x2

x + 1

 

x2 +x +1


Получим остаток x2 + x + 1, который и является 11-м элементом поля.

 

 

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

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

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

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

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

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

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

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

Лекция№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), называется кольцом многочлен

Расширение полей
  Рассмотрим, какова связь полей GF(p) и GF( p n ).   Пусть F - поле. Подмножество К поля Р, которое само является полем относительно операций поля Р, на

Системы уравнений сравнений
  Общий вид:   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.  

Алгоритм получения элементов поля 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
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги