Реализуйте S-блок Рейндаэля

15

S-box от Rijndael - это часто используемая операция шифрования и дешифрования AES . Обычно он реализован в виде 256-байтовой таблицы поиска. Это быстро, но означает, что вам нужно перечислить 256-байтовую таблицу поиска в вашем коде. Бьюсь об заклад, кто-то из этой толпы может сделать это с меньшим количеством кода, учитывая основную математическую структуру.

Напишите функцию на вашем любимом языке, которая реализует S-блок Rijndael. Самый короткий код выигрывает.

Кит Рэндалл
источник
1
Бонусные баллы (одобрение от меня), если результирующая функция имеет постоянное время (т. Е. Нет зависимых от данных путей к коду, доступа к массиву или чего-либо, что поддерживает ваш язык).
Пауло Эберманн
@ Доступ к массиву PaŭloEbermann является постоянным временем во многих языках (он добавляет (масштабированное) значение к указателю и разыменовывает его, поэтому таблица поиска очень быстрая)
трещотка
@ratchetfreak Доступ к массиву - O (1), но фактическое время доступа зависит, например, от попаданий или пропаданий кэша, что приводит к атакам по стороннему каналу на AES.
Пауло Эберманн
@ PaŭloEbermann, но вы можете использовать более короткий код, чтобы заполнить таблицу поиска, которая будет хорошо вписываться в страницу памяти.
Питер Тейлор
@ PaŭloEbermann, и если таблица длиной 256 хранится в коде (как enum, сгенерированный во время компиляции), вы почти гарантируете попадание в кеш
ratchet freak

Ответы:

6

Рубин, 161 символов

R=0..255
S=R.map{|t|t=b=R.select{|y|x=t;z=0;8.times{z^=y*(x&1);x/=2;y*=2};r=283<<8;8.times{r/=2;z^r<z/2&&z^=r};z==1}[0]||0;4.times{|r|t^=b<<1+r^b>>4+r};t&255^99}

Чтобы проверить вывод, вы можете использовать следующий код для печати в табличной форме:

S.map{|x|"%02x"%x}.each_slice(16){|l|puts l*' '}
Говард
источник
7

GolfScript, 60 символов

{[[0 1{.283{1$2*.255>@*^}:r~^}255*].@?~)={257r}4*99]{^}*}:S;

Этот код определяет именованную функцию, Sкоторая принимает байт и применяет к ней S-блок Rijndael. (Он также использует внутреннюю вспомогательную функцию с именем, rчтобы сохранить несколько символов.)

Эта реализация использует таблицу логарифма для вычисления GF (2 8 ) обратно, так как предложенный Томасом Pornin . Чтобы сохранить несколько символов, вся логарифмическая таблица пересчитывается для каждого входного байта; несмотря на это, несмотря на то, что GolfScript является очень медленным языком в целом, этот код занимает всего около 10 мс для обработки байта на моем старом ноутбуке. Предварительный расчет таблицы логарифмов (as L) ускоряет ее примерно до 0,5 мс на байт при скромной стоимости еще трех символов:

[0 1{.283{1$2*.255>@*^}:r~^}255*]:L;{[L?~)L={257r}4*99]{^}*}:S;

Для удобства вот простой тестовый набор, который вызывает функцию S, как определено выше, для вычисления и распечатки всего S-блока в шестнадцатеричном виде, как в Википедии :

"0123456789abcdef"1/:h; 256, {S .16/h= \16%h= " "++ }% 16/ n*

Попробуйте этот код онлайн.

(Демонстрация в режиме онлайн предварительно вычисляет таблицу логарифмов, чтобы не занимать слишком много времени. Несмотря на это, онлайн-сайт GolfScript иногда может случайно зависнуть; это известная проблема с сайтом, и перезагрузка обычно исправляет ее.)

Объяснение:

Начнем с вычисления логарифмической таблицы, а именно с вспомогательной функции r:

{1$2*.255>@*^}:r

Эта функция принимает два входа в стек: битовую маску и битовую маску сокращения (константа между 256 и 511). Он дублирует входной байт, умножает копию на 2 и, если результат превышает 255, XOR с помощью битовой маски возвращает значение ниже 256.

В коде генерации таблицы журнала функция rвызывается с битовой маской редукции 283 = 0x11b (что соответствует многочлену редукции Rijndael GF (2 8 ) x 8 + x 4 + x 3 + x + 1), и результатом является XORed с исходным байтом, эффективно умножая его на 3 (= x + 1, как многочлен) в конечном поле Рейндаля. Это умножение повторяется 255 раз, начиная с байта 1, и результаты (плюс начальный нулевой байт) собираются в массив из 257 элементов, Lкоторый выглядит следующим образом (средняя часть опущена):

[0 1 3 5 15 17 51 85 255 26 46 ... 180 199 82 246 1]

Причина, по которой существует 257 элементов, состоит в том, что с добавленным 0 и 1, встречающимся дважды, мы можем найти модульную инверсию любого данного байта, просто посмотрев его (основанный на нуле) индекс в этом массиве, отрицая его и посмотрев до байта в отрицательном индексе в том же массиве. (В GolfScript, как и во многих других языках программирования, отрицательные индексы массива считаются в обратном направлении от конца массива.) Действительно, это именно то, что делает код L?~)L=в начале функции S.

Остальная часть коды вызывает вспомогательную функцию в rчетыре раза с уменьшением битовой маской 257 = 2 8 +-для создания четыре битовых-повернутой копии перевернутого входного байта. Все они собраны в массив вместе с константой 99 = 0x63, и XORed вместе для получения окончательного результата.

Илмари Каронен
источник
7

x86-64 Машинный код - 23 22 20 19 байтов

Использует набор инструкций AES-NI

66 0F 6E C1          movd        xmm0,ecx
66 0F 38 DD C1       aesenclast  xmm0,xmm1
0F 57 C1             xorps       xmm0,xmm1  
66 0F 3A 14 C0 00    pextrb      eax,xmm0,0
C3                   ret

Используя соглашения о вызовах Windows, принимает байт и выводит байт. Нет необходимости менять направление, ShiftRowsпоскольку это не влияет на первый байт.

мне'
источник
2
На этот раз x86_64 извлекает mathematica и имеет встроенную функцию для этого.
moonheart08
6

Таблица может быть сгенерирована без вычисления обратных значений в конечном поле GF (256) с использованием логарифмов. Это выглядело бы так (код Java, использующий, intчтобы избежать проблем со подписанным byteтипом):

int[] t = new int[256];
for (int i = 0, x = 1; i < 256; i ++) {
    t[i] = x;
    x ^= (x << 1) ^ ((x >>> 7) * 0x11B);
}
int[] S = new int[256];
S[0] = 0x63;
for (int i = 0; i < 255; i ++) {
    int x = t[255 - i];
    x |= x << 8;
    x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7);
    S[t[i]] = (x ^ 0x63) & 0xFF;
}

Идея состоит в том, что 3 является мультипликативным генератором GF (256) *. Таблица t[]такова, что t[x]равна 3 х ; так как 3 255 = 1, мы получаем, что 1 / (3 x ) = 3 255-x .

Томас Порнин
источник
не должно быть 0x1B(один 1 в шестнадцатеричном литерале) вместо0x11B
трещотка урод
@ratchetfreak: нет, это должно быть 0x11B (я пытался). intТип 32-бит в Java; Я должен отменить старший бит.
Томас Порнин
ах не осознавал этого
трещотка урод
Это >>> вместо >> в строке 4?
Джо З.
@JoeZeng: оба будут работать. В Java «>>>» - это «беззнаковое смещение», «>>» - «знаковое смещение». Они отличаются тем, как они обрабатывают бит знака. Здесь значения никогда не будут достаточно широкими, чтобы знаковый бит был ненулевым, поэтому это не имеет никакого значения.
Томас Порнин
6

GolfScript (82 символа)

{256:B,{0\2${@1$3$1&*^@2/@2*.B/283*^}8*;;1=},\+0=B)*:A.2*^4A*^8A*^128/A^99^B(&}:S;

Использует глобальные переменные Aи B, и создает функцию в качестве глобальной переменной S.

Инверсия Галуа - это грубая сила; Я экспериментировал с наличием отдельной mulфункции, которую можно было бы повторно использовать для аффинного преобразования после инверсии, но это оказалось более дорогим из-за разного поведения переполнения.

Это слишком медленно для онлайн-демонстрации - время ожидания даже в первых двух строках таблицы.

Питер Тейлор
источник
Мой быстрее (и короче;). +1 в любом случае, хотя.
Илмари Каронен
4

Питон, 176 символов

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

def S(x):
 i=0
 for y in range(256):
  p,a,b=0,x,y
  for j in range(8):p^=b%2*a;a*=2;a^=a/256*283;b/=2
  m=(p^1)-1>>8;i=y&m|i&~m
 i|=i*256;return(i^i/16^i/32^i/64^i/128^99)&255
Кит Рэндалл
источник
Умножение с постоянным временем зависит от платформы (даже на 32-битных платформах, например, ARM Cortex M0). Смотрите этот связанный вопрос
fgrieu
1
@fgrieu Конечно, но это все умножения на константы, которые могут быть легко реализованы в постоянное время, используя сдвиги и добавления.
Кит Рэндалл,
2

d

ubyte[256] getLookup(){

    ubyte[256] t=void;
    foreach(i;0..256){
        t[i] = x;
        x ^= (x << 1) ^ ((x >>> 7) * 0x1B);
    }
    ubyte[256] S=void;
    S[0] = 0x63;
    foreach(i;0..255){
        int x = t[255 - i];
        x |= x << 8;
        x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7);
        S[t[i]] = cast(ubyte)(x & 0xFF) ^ 0x63 ;
    }
    return S;

}

это может генерировать таблицу поиска во время компиляции, я мог бы сохранить некоторые, сделав ubyte универсальным параметром

редактировать не направлять ubyteна ubyteбез поиска в массиве, не ветвления и полностью unrollable петли

B[256] S(B:ubyte)(B i){
    B mulInv(B x){
        B r;
        foreach(i;0..256){
            B p=0,h,a=i,b=x;
            foreach(c;0..8){
                p^=(b&1)*a;
                h=a>>>7;
                a<<=1;
                a^=h*0x1b;//h is 0 or 1
                b>>=1;
            }
            if(p==1)r=i;//happens 1 or less times over 256 iterations
        }
        return r;
    }
    B s= x=mulInv(i);
    foreach(j,0..4){
        x^=(s=s<<1|(s>>>7));
    }
    return x^99;
}

edit2 использовал алгоритм @Thomas для создания таблицы поиска

чокнутый урод
источник