МатематическаямодельалгоритмаRijndael

БайтыможнорассматриватькакэлементыконечногополяGF(2⁸)-

многочленыстепенинеболее7

а₇х⁷⁺а₆х⁶⁺а₅х⁵⁺а₄х⁴⁺а₃х³⁺а₂х²⁺а₁х¹⁺а₀х⁰,

которыемогутбытьзаданыстрокойкоэффициентов

{а₇,a₆,a₅,a₄,а₃,а₂,а₁,a₀},а_i{0,1},i0,7.

Например,байтувдвоичномвиде11001011₂₍илиcb₁₆)ставитсявсоответствиемногочленх⁷⁺х⁶⁺х³⁺х+1.

В раундах шифрования используются 32-битные слова,представленныеввидемногочленовa(х)скоэффициентамиа_iGF(2⁸)

_{размеромвбайт,i0,3:}

а(х)=а₃х³⁺а₂х²⁺а₁х+a₀.

ОперациясложениямногочленовскоэффициентамиизGF(2⁸).Сложениедвухмногочленова(х)иb(х)скоэффициентамиизGF(2⁸)заключаетсявпоразрядномсложениипооперацииXORкоэффициентовпринеизвестныходинаковойстепени:

а(х)+b(х)=(а_3b₃)х³⁺(а_2b₂)х²⁺(а_1b₁)х+(a_0b₀).

Призаданииполиномовввиде4-байтовыхсловсложениезаключаетсявпоразряднойоперацииXORвсехразрядовскладываемыхслов.

_{ОперацияумножениямногочленовскоэффициентамиизGF(2}⁸_).

Пустьперемножаются2многочлена

а(х)=а₃х³⁺a₂х²⁺а₁х+a_0иb(х)=b₃х³⁺b₂х²⁺b₁х+b₀.

Результатомумноженияс(х)=а(х)?b(х)будетмногочлен

c(х)=c₆x⁶⁺c₅x⁵⁺c₄x⁴⁺c₃x³⁺c₂x²⁺c₁x+c₀,где

c₀₌a₀b₀,

c₁₌a₁b_0a₀b₁,

с₂₌а₂b_0а₁b_1a₀b₂,

с₃₌а₃b_0a₂b_1а₁b_2a₀b₃,

с₄₌а₃b_1а₂b_2a₁b₃,

с₅₌а₃b_2а₂b₃,

с₆₌а₃b₃.

Для того чтобы результат умножения мог быть представлен 4-

байтовымсловом,егонормируютпомодулю-многочленомстепенинеболее4-многочленом

x⁴+1.

Результатомd(x)умножениядвухмногочленовпомодулюх⁴⁺1

_{d(x)=a(x)?b(х)mod(х}⁴₊₁₎

будетмногочлен

d(x)=d₃x³⁺d₂x²⁺d₁x+d₀,гдеd₀₌a₀b_0a₃b_1a₂b_2a₁b₃,d₁₌a₁b_0a₀b_1a₃b_2a₂b₃,d₂₌a₂b_0a₁b_1a₀b_2a₃b₃,

d₃₌a₃b_0a₂b_1a₁b_2a₀b₃,

Иливматричнойформе:

_d0

_{a0a3a2a1}

_b0

_d

_aa

_aa

_b

_¹_¹

^{0 3 2}_

¹_.

_d2

_{a2a1a0a3}

_b2

_{  }

_{  }

_^d_3

_^a₃^a₂^a₁^a_0

_^b_3

Многочленb(х)=b₃x³⁺b₂x²⁺b₁x+b₀₍b_iGF(2⁸),

i0,3)можно

умножитьнахпомодулюх⁴+1следующимобразом.Умножениеаналогичноциклическомусдвигукоэффициентовb_iвлево,всторонустаршейстепениb(х):

(х?b(х))mod(х⁴⁺1)=b₂x³⁺b₁x²⁺b₀x+b₃.

РаундпреобразованияалгоритмаRijndael

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

1)заменабайтовS[](SubBytes)-каждыйбайтблокаданныхзаменяетсяновымзначениемпофиксированнойматрицезамены;

2)побайтовыйциклическийсдвигR_(ShiftRows)встрокахматрицы:i-ястрокациклическисдвигаетсянаi-1байтоввлево,а1-ястроканеизменяется;

3)матричноеумножениеM?[](MixColumns)-байты,представленныеввидемногочленовнадполемGF(2⁸),умножаютсянафиксированныймногочлентретьейстепениg(x)помодулюx⁴+1;

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

_{ключаалгоритма.}

_k0

_{1-ыйраунд} ^X0

2-ойраунд

S[]

S[]

R_ ^M?[]

R_ ^M?[]

_X1 k₁

_X2 k₂

_………

_………

10

^{10-ыйраунд k}_{10 X}

^{S[] R}_

Рис.4.2.СхемапреобразованияданныхалгоритмомRIJNDAELсдлинойключав128бит

X-входнойблокданных;

X_iиX_i+1-преобразуемыйблокнавходеивыходеi-гораунда,i0,10;

k_i-ключевойэлементi-гораунда.

В10-мраундеоперацияM?[]отсутствует.Преобразование SubBytes (1-ый шаг раунд

шифрования/расшифрования)являетсянелинейнойзаменойбайт,выполняемойдлякаждогобайтавходныхданных.SubBytesвыполняетследующиепреобразованиявходногобайта:

1)вычисляетсяобратныйэлемент(раздел3.4)отвходногобайтапо

операцииумножениявполеGF(2⁸);принимается,что0остается0;

_{2)выполняетсяаффинноепреобразованиенадбитамивходногобайта:}

_b'_0

_1 0

0 0 1

1 1 1_

_b_0

_1_

_{  }

_{   }

_^b'1_

_b'2

_^{1 1}

_{1 1}

0 0 0

_{1 0 0}

^{1 1 1}_

_{0 1 1}

_^b1_

_b2

_¹_

_0

_{  }

_{   }

_^b'3_

_b'4

_^{1 1}

_{1 1}

1 1 0 0

_{1 1 1 0}

^{0 1}_

_{0 0}

_^b3_

_b4

_^0_,

₀

_{  }

_{   }

_^b'_5

_^{0 1}

1 1 1 1

^{0 0}_

_^b_5

_¹_

_{b }

_{ b }

_^'6_

_{0 0 1}

_

1 1 1 1

⁰_{ }⁶_{ }¹_

^_^b'₇^_

^_^{0 0}

0 1 1

^{1 1 1}_

^_^b₇^_

^_^0_

^гдеb_i^иb'_i^{-исходноеипреобразованноезначениеi-гобита,}

i0,7.

Аффинноепреобразованиеможнозаписатьввидеуравнения:

^b'i^=bi^b(i+4)mod8^b(i+5)mod8^b(i+6)mod8^b(i+7)mod8^b(i+4)mod8^ci^,

гдеc₀₌c₁₌c₅₌c₆₌1,c₂₌c₃₌c₄₌c₇₌0.

ВпреобразованииMixColumns(3-ойшаграунда)входныебайтырассматриваютсякакмногочленынадGF(2ⁿ)иумножаютсяпомодулюx⁴⁺1

_{намногочленg(x)вида}

g(x)='03'x³⁺'01'x²⁺'01'x+'02'.

_{Операциюумноженияможнопредставитьвматричномвидекак}

_s'_0c

_02030101_

_s_0c

_{s' }

_{01020301}

_{s }

_ 1c_

_

1c_

_s'2c

_{01010203}

_s2c^,

_{  }

_{  }

_^s'_3c

_^03010102_

_^s_3c

гдеs_icиs’_ic-i-ыебайтывходногоивыходногодвойныхслов,

c-номердвойногословавшифруемомтексте.

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

i0,3,

1. Какими достоинствами и недостатками обладает алгоритм

RIJNDAEL?

2.КакиеестьмодификацииалгоритмаRIJNDAEL?

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

алгоритмеRIJNDAEL?