Общая картина: этот код должен вычислить обратный по модулю двоичный неприводимый многочлен $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$), отменяя дублирование.
