Общая картина: этот код должен вычислить обратный по модулю двоичный неприводимый многочлен $P$ каждого ненулевого бинарного многочлена $R$ степени меньше, чем у $P$. Для этого был выбран производящий многочлен $G=1+x$, и табулирует $Q_i=G^i\bmod P$, который достигает всех желаемых $R$. Мультипликативная инверсия $R=Q_i$ является $Q_{255-i}$.
Этот код оценивает S-блок AES и обратно следующим образом:
(кодовый блок, начинающийся в пытаться
) Он оценивает р = 0x11б = 283
который представляет двоичный многочлен $P=1+x+x^3+x^4+x^8$ как целое число: значение, полученное при оценке этого многочлена для целого числа $х=2$. Это общее соглашение используется в AES для преобразования двоичных полиномов в целые числа.
(кодовый блок, начинающийся в пусть т
) Он вычисляет таблицу т[я]
представляющий двоичный многочлен $Q_i=(1+x)^i\bmod P$ по этой конвенции. Что $Q_i$ рассчитывается на повторение $Q_{i+1}=Q_i\,(1+x)\bmod P$ с $Q_0=1$, переводя на t[i+1] = t[i] ^ ((t[i] << 1) ^ ((t[i] >>> 7) * p))
с т [0] = 1
в соответствии с указанной конвенцией.
Например: $Q_0$ является (бинарным) многочленом $1$, представлена т [0] = 1
. $Q_1=1+x$, представлена т[1] = 3
. $Q_2=(1+х)^2=1+х^2$, представлена т[2] = 5
. $Q_7=(1+х)^7=1+х+х^2+х^3+х^4+х^5+х^6+х^7$, представлена т[2] = 0xff = 255
. $Q_8=(1+x)^8\bmod P=(1+x^8)\bmod P=x+x^3+x^4$, представлена т[8] = 0x1a = 26
.
(кодовый блок, начинающийся в пусть Sbox
) Табулирование $Q_i=(1+x)^i\bmod P$ было полезно, потому что $(1+x)^{255}\bmod P=1$, следовательно $Q_{255-i}$ является мультипликативным, обратным $Q_i$. И $Q_i$ достигает всех ненулевых бинарных полиномов степени $<8$ (это $1+х$ является генератором). Поэтому целое число т[255 - я]
представляет собой мультипликативную инверсию многочлена, что целое число т[я]
представляет собой. И когда в петле я
идет от 0
к 254
что дает мультипликативную обратную величину каждого из 255 ненулевых многочленов степени $<8$. Затем цикл просто применяет ² аффинное преобразование, указанное в оставшейся части цикла. определение AES S-box. Нулевой многочлен имеет особый случай.
Например: когда в петле я = 8
, т[я]
является т[8] = 0x1a = 26
представляющий $Q_8=х+х^3+х^4$, и т [255-я]
(собираюсь Икс
, не связанный с $х$) является т[247] = 0xfd = 253
представляющий полином $Q_{247}=1+x^2+x^3+x^4+x^5+x^6+x^7$. Что $Q_{247}$ является мультипликативным, обратным $Q_8$. По определению S-блока AES остается только применить аффинное преобразование² к Икс
, затем установите результат в Sbox[t[i]] = Sbox[26]
.
(функция, обратная
) Обратная таблица вычисляется путем поиска каждой записи в таблице. Это работает, но неэффективно. InvSbox[i] = sbox.indexOf(i);
можно заменить более простым и эффективным InvSbox[sbox[i]] = i;
.
¹ Обоснование: в t[i+1] = t[i] ^ ((t[i] << 1) ^ ((t[i] >>> 7) * p))
т[я]
является целым числом в $[0,2^8)$ и представляет $Q_i$ степени $<8$
т[я] << 1
является четным целым числом в $[0,2^9)$ и представляет $Q_i\,x$.
т[я] >>> 7
либо 0
или же 1
. Это коэффициент срока заказа $х^7$ в $Q_i$.
(t[i] >>> 7) * p
соответственно либо 0
или же 0x11b = 283
, представляющий $0$ или же $P$.
(t[i] << 1) ^ ((t[i] >>> 7) * p)
соответственно представляет $(Q_i\,x)$ или же $(Q_i\,x)+P$, и (при рассмотрении двух случаев) является целым числом в $[0,2^8)$, таким образом, представляет собой бинарный полином степени $<8$, что, таким образом, $(Q_i\,x)\bmod P$.
t[i] ^ ((t[i] << 1) ^ ((t[i] >>> 7) * p))
таким образом, является целым числом в $[0,2^8)$ и представляет $Q_i+(Q_i\,x)\bmod P)=Q_i\,(1+x)\bmod P=Q_{i+1}$, степени $<8$.
В C стандартная идиома вероятного постоянного времени для этого выражения будет (по существу с & -
используется вместо умножения):
t[i+1] = t[i] ^ ((t[i] << 1) ^ (p & -(t[i] >> 7)))
.
Примечание: некоторые переусердствовавшие компиляторы C будут ошибочно лаять на -
, заставить их замолчать.
² Заявление х |= х << 8;
дублирует биты в переменной Икс
(представляющий модульную инверсию $Q_i$), так что последующие сдвиги вправо становятся эквивалентными вращению, когда речь идет о младших 8 битах. Заявление х ^ = (х >> 4) ^ (х >> 5) ^ (х >> 6) ^ (х >> 7);
реализует циркуляционная матрица умножение. затем ^ 0x63
(представляющий многочлен $1+х+х^5+х^6$) — постоянное сложение, а & 0xFF
сохраняет младшие 8 битов (с точки зрения степени $<8$), отменяя дублирование.