Оптимальный алгоритм декодирования AES - посоревнуемся? ;)

[_Ivana]

Собственно, сабж Поскольку написано, что "Обсуждение алгоритмов без привязки к языку программирования ведется НЕ ЗДЕСЬ, а в корне раздела Computer Science", то пощу тему сюда. Есть такой стандарт шифрования AES, возьмем параметры по умолчанию (16 байт блок, 10 раундов). Задача - предложить оптимальный (в определенном компромиссном смысле) алгоритм, реализующий дешифровку. Реализовать лучше на С или ассемблере (а вот и привязка к языку....), т.к. алгоритм будет использоваться на микроконтроллерах - для расшифровки зашифрованной прошивки. Хотя важен принцип - можно хоть на Паскале или Бэйсике. Если кому лениво - можно просто русскими словами описАть идею кода. Критерии оптимальности - минимальное время декодирования при относительно минимальных требованиях к памяти (как ОЗУ так и флеш) - чтобы быстрее прошивка заливалась и при этом минимум памяти контроллера съедался. Если есть заинтересовавшиеся - прошу

ЗЫ да, я знаю что есть несколько открытых исходников данной задачи для микроконтроллеров, я смотрел их, но, как мне кажется, реализовал алгоритм оптимальнее всех мною виденных. Разумеется, я могу ошибаться Если будет кому будет интересно - выложу сюда исходный код.

ЗЗЫ если предлОжите код на С или С++, то я могу загнать его в проект (не в симулятор контроллера, а в экзешник на Вижуал Студии) и сравнить скорости. Как замерять я к своему стыду не знаю , поэтому я просто запущу расшифрование в цикле 5 000 000 раз зашифрованного одного блока и засеку время на секундомере Или предложИте свой вариант сравнения.

[e2e4]

Ну время засекать можно и средствами языка (time.h и пр.), правда в многозадачной ОС это может плохо сработать, но можно наловчиться, увеличив кол-во итераций и ожидая приемлемую ошибку.
Однако, лучше бы вы не раскрывали назначения своего алгоритма, а еще лучше - не делали бы этого вообще, если я правильно понял вашу цель.

[Euler7]

_Ivana в сообщении #754305 писал(а):

Есть такой стандарт шифрования AES

Есть такой набор инструкций процессора AES instruction set...

[_Ivana]

e2e4 в сообщении #754426 писал(а):

Однако, лучше бы вы не раскрывали назначения своего алгоритма, а еще лучше - не делали бы этого вообще, если я правильно понял вашу цель.

Поясните пожалуйста. Моя цель при реализации этого алгоритма была в создании бутлоадера для МК, способного быстро и малозатратно принимать закодированную прошивку. Моя цель при создании этой темы была предложить участникам форума интересную задачку, которую у меня получилось имхо достаточно эффективно решить, оживить раздел, дать другим возможность подумать. Что из этого вас смущает? Скажите прямо, можно в ЛС.

Euler7 правильно, есть. Вот я и предлагаю реализовать его (точнее только часть декодирования) программно, дабы применять на тех микроконтроллерах, где таких аппаратных возможностей нет.

[e2e4]

А, я ошибся. Предположил, что некоторые МК могут иметь встроенные средства защиты уже загруженной прошивки, связанные с шифрованием. Мне известно о МК, защищающих прошивку 128-битным паролем, но это аппаратная защита на доступ к флэш-массиву.
Любопытно, а зачем может понадобиться передавать закодированную прошивку?

[_Ivana]

e2e4

(Оффтоп)

Чтобы интеллектуальную собственность защитить различные халявщики не взламывали код и не воровали исходники таким образом. А закодированную прошивку можно хоть на сайт на всеобщее скачивание выкладывать в разделе апдейтов - скачай и загружай на свой девайс, который ее корректно раскодирует и зашьет.

[Euler7]

_Ivana в сообщении #754447 писал(а):

Euler7 правильно, есть. Вот я и предлагаю реализовать его (точнее только часть декодирования) программно, дабы применять на тех микроконтроллерах, где таких аппаратных возможностей нет.

Тогда причём тут скорость? Разный набор инструкций даст разную скорость, надо плясать от архитектуры. К тому же далеко не под каждый контроллер есть C++ компилер. А хорошая реализация на сях есть, например, в OpenSSL.

[_Ivana]

Euler7 в сообщении #754457 писал(а):

К тому же далеко не под каждый контроллер есть C++ компилер.

Да. Но зато у меня в Вижуал студии есть С++ проект, где я реализовал этот алгоритм (оставаясь в рамках чистого С). А идеи, повторюсь, можно хоть на Паскале, хоть русскими словами написать.

Euler7 в сообщении #754457 писал(а):

А хорошая реализация на сях есть, например, в OpenSSL.

Спасибо, посмотрю если найду. Сравню со своим алгоритмом, скажу впечатления.

[Euler7]

Все "идеи" есть в википедии, это стандарт шифрования, его все знают и любая нормальная криптографическая библиотека его содержит. Например вот реализация в PolarSSL. А соревноваться нужно в реализации нетривиальных алгоритмов с привязкой к платформе.

[Xaositect]

(Оффтоп)

_Ivana в сообщении #754456 писал(а):

Чтобы интеллектуальную собственность защитить различные халявщики не взламывали код и не воровали исходники таким образом. А закодированную прошивку можно хоть на сайт на всеобщее скачивание выкладывать в разделе апдейтов - скачай и загружай на свой девайс, который ее корректно раскодирует и зашьет.

Тут такое дело. Если ключ расшифрования будет храниться в каком-нибудь ROM, то никто не мешает его оттуда прочитать.
Вообще, не зря везде пишут, что если вам нужна криптография, то используйте ее правильно и не пишите ее сами.

_Ivana в сообщении #754305 писал(а):

ЗЫ да, я знаю что есть несколько открытых исходников данной задачи для микроконтроллеров, я смотрел их, но, как мне кажется, реализовал алгоритм оптимальнее всех мною виденных. Разумеется, я могу ошибаться Если будет кому будет интересно - выложу сюда исходный код.

А покажите свой код. Я просто слабо вижу, где в AES можно убавить память и размер программы, если писать на C без привязки к конкретному набору команд. Не будешь же S-box каждый раз программно генерировать вместо того, чтобы держать в памяти.

[e2e4]

Тогда в вашем случае быстрота расшифровки в общем-то не принципиальна, важен только размер алгоритма и кол-во занимаемой для работы ОЗУ, и то здесь всего лишь надо уложиться в аппаратные возможности МК, дальше вылизывать не имеет смысла? Вы ведь при старте МК расшифровываете всю прошивку ему в память, или все-таки раскодируете "на лету"?
А в вашем МК код бутлоадера вытащить можно?

[_Ivana]

Euler7 в сообщении #754467 писал(а):

А соревноваться нужно в реализации нетривиальных алгоритмов с привязкой к платформе.

Так где же ваши темы - предложения на этот счет? Если смогу, то с удовольствием попробую. Добавьте к критике хоть немного конструктива.
Спасибо за пример, пока взглянул бегло - должно быть быстро, но навскидку - не радует размер пары таблиц FT и RT (да и вообще их наличие).

Xaositect, конечно покажу. Вечером, как буду на своем компе. Если нет желающих предоставить свои (или скопированные их библиотек) примеры кода. Кстати, прямой S-box для декодирования не нужен, нужна только инверсная таблица. Хотя, через S-box можно проводить расширение ключа, но.... это уже началось хоть какое-то конкретное обсуждение алгоритма. К примеру, тот же S-box можно сгенерировать кодом в ОЗУ и использовать оттуда, а можно хранить во флеш как массив констант. А перед тем как я выложу свой код, не могли бы вы выложить с вашей точки зрения наиболее оптимальный код декодирования на С? Хоть из любой понравившейся вам библиотеки

e2e4 в сообщении #754485 писал(а):

дальше вылизывать не имеет смысла?

Ну если так рассуждать, то можно вообще прийти к варианту - укладывается в аппаратные возможности и ладно.

[Euler7]

_Ivana в сообщении #754512 писал(а):

Так где же ваши темы - предложения на этот счет?

А мне это надо? Вон в соседней теме какие-то квадраты ищут, вот и пример нормальной задачи.

_Ivana в сообщении #754512 писал(а):

Добавьте к критике хоть немного конструктива.

Что понимается под "конструктивом"? Есть быстрые реализации AES на все случаи жизни и ссылки я привёл. Это похоже на аргумент алкаша - ему говорят пить вредно, от тебя воняет, найди работу и т.д. и т.п. Но для него это неконструктивная критика.

_Ivana в сообщении #754512 писал(а):

Спасибо за пример, пока взглянул бегло - должно быть быстро, но навскидку - не радует размер пары таблиц FT и RT (да и вообще их наличие).

Оптимизация по скорости за счёт памяти. Это распространённая практика, поскольку с ОЗУ обычно проблем меньше чем с процессором.

[_Ivana]

Euler7 в сообщении #754519 писал(а):

Что понимается под "конструктивом"?

Я не имел в виду AES, а вообще касательно ваших слов

Цитата:

А соревноваться нужно в реализации нетривиальных алгоритмов с привязкой к платформе.

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

Цитата:

А мне это надо?

Теперь ясна ваша позиция и роль в мировой революции.

Euler7 в сообщении #754519 писал(а):

Оптимизация по скорости за счёт памяти. Это распространённая практика, поскольку с ОЗУ обычно проблем меньше чем с процессором.

Вот и про это в том числе можно было поговорить, что я и имел в виду, когда писал "оптимальный в определенном компромиссном смысле", конечно баланс скорости и памяти.

ЗЫ но вообще, какая то конкретика и критика будут хоть как то уместны только тогда, когда я выложу свой код (часа через полтора). А до тех пор вообще непонятно, к чему относится ваша "конструктивная критика", простите.

[_Ivana]

Используется синтаксис C

const unsigned char invSbox[] =
{
        0x52,0x09,0x6A,0xD5,0x30,0x36,0xA5,0x38,0xBF,0x40,0xA3,0x9E,0x81,0xF3,0xD7,0xFB,
        0x7C,0xE3,0x39,0x82,0x9B,0x2F,0xFF,0x87,0x34,0x8E,0x43,0x44,0xC4,0xDE,0xE9,0xCB,
        0x54,0x7B,0x94,0x32,0xA6,0xC2,0x23,0x3D,0xEE,0x4C,0x95,0x0B,0x42,0xFA,0xC3,0x4E,
        0x08,0x2E,0xA1,0x66,0x28,0xD9,0x24,0xB2,0x76,0x5B,0xA2,0x49,0x6D,0x8B,0xD1,0x25,
        0x72,0xF8,0xF6,0x64,0x86,0x68,0x98,0x16,0xD4,0xA4,0x5C,0xCC,0x5D,0x65,0xB6,0x92,
        0x6C,0x70,0x48,0x50,0xFD,0xED,0xB9,0xDA,0x5E,0x15,0x46,0x57,0xA7,0x8D,0x9D,0x84,
        0x90,0xD8,0xAB,0x00,0x8C,0xBC,0xD3,0x0A,0xF7,0xE4,0x58,0x05,0xB8,0xB3,0x45,0x06,
        0xD0,0x2C,0x1E,0x8F,0xCA,0x3F,0x0F,0x02,0xC1,0xAF,0xBD,0x03,0x01,0x13,0x8A,0x6B,
        0x3A,0x91,0x11,0x41,0x4F,0x67,0xDC,0xEA,0x97,0xF2,0xCF,0xCE,0xF0,0xB4,0xE6,0x73,
        0x96,0xAC,0x74,0x22,0xE7,0xAD,0x35,0x85,0xE2,0xF9,0x37,0xE8,0x1C,0x75,0xDF,0x6E,
        0x47,0xF1,0x1A,0x71,0x1D,0x29,0xC5,0x89,0x6F,0xB7,0x62,0x0E,0xAA,0x18,0xBE,0x1B,
        0xFC,0x56,0x3E,0x4B,0xC6,0xD2,0x79,0x20,0x9A,0xDB,0xC0,0xFE,0x78,0xCD,0x5A,0xF4,
        0x1F,0xDD,0xA8,0x33,0x88,0x07,0xC7,0x31,0xB1,0x12,0x10,0x59,0x27,0x80,0xEC,0x5F,
        0x60,0x51,0x7F,0xA9,0x19,0xB5,0x4A,0x0D,0x2D,0xE5,0x7A,0x9F,0x93,0xC9,0x9C,0xEF,
        0xA0,0xE0,0x3B,0x4D,0xAE,0x2A,0xF5,0xB0,0xC8,0xEB,0xBB,0x3C,0x83,0x53,0x99,0x61,
        0x17,0x2B,0x04,0x7E,0xBA,0x77,0xD6,0x26,0xE1,0x69,0x14,0x63,0x55,0x21,0x0C,0x7D
};

const unsigned char key[] =
{
        0x0f,0x15,0x71,0xc9,0x47,0xd9,0xe8,0x59,0x0c,0xb7,0xad,0xd6,0xaf,0x7f,0x67,0x98,
        0xdc,0x90,0x37,0xb0,0x9b,0x49,0xdf,0xe9,0x97,0xfe,0x72,0x3f,0x38,0x81,0x15,0xa7,
        0xd2,0xc9,0x6b,0xb7,0x49,0x80,0xb4,0x5e,0xde,0x7e,0xc6,0x61,0xe6,0xff,0xd3,0xc6,
        0xc0,0xaf,0xdf,0x39,0x89,0x2f,0x6b,0x67,0x57,0x51,0xad,0x06,0xb1,0xae,0x7e,0xc0,
        0x2c,0x5c,0x65,0xf1,0xa5,0x73,0x0e,0x96,0xf2,0x22,0xa3,0x90,0x43,0x8c,0xdd,0x50,
        0x58,0x9d,0x36,0xeb,0xfd,0xee,0x38,0x7d,0x0f,0xcc,0x9b,0xed,0x4c,0x40,0x46,0xbd,
        0x71,0xc7,0x4c,0xc2,0x8c,0x29,0x74,0xbf,0x83,0xe5,0xef,0x52,0xcf,0xa5,0xa9,0xef,
        0x37,0x14,0x93,0x48,0xbb,0x3d,0xe7,0xf7,0x38,0xd8,0x08,0xa5,0xf7,0x7d,0xa1,0x4a,
        0x48,0x26,0x45,0x20,0xf3,0x1b,0xa2,0xd7,0xcb,0xc3,0xaa,0x72,0x3c,0xbe,0x0b,0x38,
        0xfd,0x0d,0x42,0xcb,0x0e,0x16,0xe0,0x1c,0xc5,0xd5,0x4a,0x6e,0xf9,0x6b,0x41,0x56,
        0xb4,0x8e,0xf3,0x52,0xba,0x98,0x13,0x4e,0x7f,0x4d,0x59,0x20,0x86,0x26,0x18,0x76
};

#define xtime(a) (((a)<0x80)?(a)<<1:(((a)<<1)^0x1b) )

void AES_Decode(unsigned char* T)
{
        unsigned char i, roundCounter, temp;

        //invAddRoundKey
        for(i=0; i<16; i++) {T[i] ^= key[160 + i];}

        for( roundCounter = 10; roundCounter > 0; roundCounter-- )
        {
                if(roundCounter != 10)
                { //invMixColumns
                        unsigned char A, B, C, D;
                        for(i=0; i<16; i+=4)
                        {
                                A = T[i+0] ^ T[i+2]; B = T[i+1] ^ T[i+3]; C = A ^ B;
                                A = xtime(A); A = xtime(A); B = xtime(B); B = xtime(B);
                                C ^= xtime(A ^ B);
                                A ^= C; B ^= C; C = A; D = B;
                                A ^= xtime(T[i+0] ^ T[i+1]);
                                B ^= xtime(T[i+1] ^ T[i+2]);
                                C ^= xtime(T[i+2] ^ T[i+3]);
                                D ^= xtime(T[i+3] ^ T[i+0]);
                                T[i+0] ^= A; T[i+1] ^= B; T[i+2] ^= C; T[i+3] ^= D;
                        }
                }
                //invShiftRows
                temp=T[1]; T[1]=T[13]; T[13]=T[9]; T[9]=T[5]; T[5]=temp;
                temp=T[2]; T[2]=T[10]; T[10]=temp; temp=T[14]; T[14]=T[6]; T[6]=temp;
                temp=T[7]; T[7]=T[11]; T[11]=T[15]; T[15]=T[3]; T[3]=temp;

                //invSubBytesAddRoundKey
                temp = 16*(roundCounter - 1); // ((roundCounter - 1)<<= 4)
                for(i=0; i<16; i++) {T[i] = invSbox[T[i]] ^ key[temp + i];}
    }
}