АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Предварительные математические понятия

Читайте также:
  1. I. ОСНОВНЫЕ ПОНЯТИЯ (ТЕРМИНЫ) ЭКОЛОГИИ. ЕЕ СИСТЕМНОСТЬ
  2. III.I. ПОНЯТИЯ «КАРТИНА МИРА» И «ПАРАДИГМА». ЕСТЕСТВЕННОНАУЧНАЯ И ФИЛОСОФСКАЯ КАРТИНЫ МИРА.
  3. VIII.1. Общие понятия обязательственного права
  4. Абстрактное речевое мышление, понятия, умозаключения.
  5. АПРАКТИЧЕСКИЕ И АГНОСТИЧЕСКИЕ РАССТРОЙСТВА. ПРЕДВАРИТЕЛЬНЫЕ ЗАМЕЧАНИЯ.
  6. Базовые понятия предметного поля социальной информатики
  7. Базовые понятия языка Пролог
  8. Бальнеология. Понятия и определения
  9. Бухгалтерский учет: понятия, объекты учета, принципы, основные задачи и организация
  10. В защиту понятия мотивации
  11. Важнейшие понятия в системе денежного обращения
  12. ВАЖНЕЙШИЕ ТЕРМИНЫ И ПОНЯТИЯ

Практически все операции Rijndael определяются на уровне байта. Байты можно рассматривать как элементы конечного поля GF (28). Некоторые операции определены в терминах четырехбайтных слов. Введем основные математические понятия, необходимые для обсуждения алгоритма.

Поле GF(28)

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

Байт b, состоящий из битов b7, b6, b5, b4, b3, b2, b1, b0, представляется в виде полинома с коэффициентами из {0, 1}:

b7х7 + b6х6 + b5х5 + b4х4 + b3х3 + b2х2 + b1х1 + b0

Пример: байт с шестнадцатеричным значением '57' (двоичное 01010111) соответствует полиному

х6 + х4 + х2 + х + 1

Сложение

В полиномиальном представлении сумма двух элементов является полиномом с коэффициентами, которые равны сумме по модулю 2 (т.е. 1 + 1 = 0) коэффициентов слагаемых.

Пример: '57' + '83' = 'DA' или в полиномиальной нотации:

(х6 + х4 + х2 + х + 1) + (х7 + х + 1) = х7 + х6 + х4 + х2

В бинарной нотации мы имеем: 01010111 + 10000011 = 11010100. Очевидно, что сложение соответствует простому XOR (обозначается как ) на уровне байта.

Выполнены все необходимые условия Абелевой группы: операция сложения (каждой паре элементов сопоставляется третий элемент группы, называемый их суммой), ассоциативность, нулевой элемент ('00'), обратный элемент (относительно операции сложения) и коммутативность.

Умножение

В полиномиальном представлении умножение в GF (28) соответствует умножению полиномов по модулю неприводимого двоичного полинома степени 8. Полином является неприводимым, если он не имеет делителей, кроме 1 и самого себя. Для Rijndael такой полином называется m(x) и определяется следующим образом:

m(x) = x8 + x4 + x3 + x + 1

или '11B' в шестнадцатеричном представлении.

Пример: '57' • '83' = 'C1'

Или

(x6 + x4 + x2 + х + 1) (x7 + х + 1) =
= x13 + x11 + x9 + x8 + x7 + x7 + x5 + x3 + x2 + x + x6 + x4 + x2 + х + 1 =
= x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1

(x8 + x4 + x3 + х + 1) (x5 + x3) + x7 + x6 + 1 = x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 +1

Следовательно,

x13 + x11 + x9 + x8 + x6 + x5 + x4 + x8 + 1 mod (x8 + x4 + x3 + х + 1) = x7 + x6 + 1

Ясно, что результат является двоичным полиномом не выше 8 степени. В отличие от сложения, простой операции умножения на уровне байтов не существует.

Умножение, определенное выше, является ассоциативным, и существует единичный элемент ('01'). Для любого двоичного полинома b(x) не выше 8-й степени можно использовать расширенный алгоритм Евклида для вычисления полиномов a(x) и c(x) таких, что

b(x) a(x) + m(x) c(x) = 1

Следовательно,

a(x) • b(x) mod m(x) = 1

или

b-1(x) = a(x) mod m(x)

Более того, можно показать, что

a(x) • (b(x) + c(x)) = a(x) • b(x) + a(x) • c(x)

Из всего этого следует, что множество из 256 возможных значений байта образует конечное поле GF (28) c XOR в качестве сложения и умножением, определенным выше.

Умножение на х

Если умножить b(x) на полином х, мы будем иметь:

b7x8 + b6x7 + b5x6 + b4x5 + b3x4 + b2x3 + b1x2 + b0x

x • b(x) получается понижением предыдущего результата по модулю m(x). Если b7 = 0, то данное понижение является тождественной операцией. Если b7 = 1, m(x) следует вычесть (т.е. XORed). Из этого следует, что умножение на х может быть реализовано на уровне байта как левый сдвиг и последующий побитовый XOR c '1B'. Данная операция обозначается как b = xtime (a).


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.006 сек.)