Большие экспоненты и 8-битные процессоры PIC

Как отметил Crasic в комментариях, вам на самом деле не нужно вычислять фактическую экспоненту. Вы можете использовать модульную арифметику, чтобы уменьшить максимальное значение, которое вам нужно сохранить:

Для$(a b)~\textrm{mod}~m$, максимальное значение, которое вам когда-либо потребуется хранить, равно$(m-1)^2$, что m=23означает, что вы должны иметь возможность хранить 484. Это выходит за пределы диапазона 8-битных чисел, но подходит для 16-битных. Однако, как указал Олин, некоторые 8-битные микропроцессоры могут эффективно манипулировать 16-битными значениями, так что это не является большой проблемой.

Общая реализация на C может выглядеть так:

uint16_t exp_mod(uint16_t base, uint16_t power, uint16_t m)
{
    uint16_t res = 1;
    while(power)
    {
        if(power & 1)
        {
            res = (res * base) % m;
        }
        res = (res*res) % m;
        power >>= 1;
    }
    return  res;
}

Если ваш UC имеет эффективную инструкцию по модулю, этого обычно достаточно. Однако, если вы этого не сделаете и знаете, что n всегда будет определенным значением, существует эффективная реализация деления (и, следовательно, по модулю) Т. Гранлуна и П. Л. Монтомери . У Agner Fog также есть описание того, как это работает .

Вот взломанная реализация для m=23.

uint16_t mod23(uint16_t m)
{
    // note: I didn't actually figure out what n and the error correction term is suppose
    // to be, I just guessed a value for n which produces a simple function
    // only checked to be correct for m <= 484
    // 
    // n = 11
    uint16_t res = a - 23*((m*89)>>11);
    return (res == 23) ? 0 : res;
}

Единственными обязательными 16-битными операциями являются:

• сложение/вычитание
• умножение
• побитовый сдвиг
• побитовое и
• сравнение равенства

Я не знаком с набором инструкций PIC, но вот примерное количество инструкций для наихудшего случая:

• 4*log2(power)сравнения
• 4*log2(power)прыжки
• 2*log2(power)вычитания
• 3*log2(power)побитовый сдвиг
• 6*log2(power)умножения

Для power=15, это примерно 76 инструкций. Обратите внимание, что это может произойти, если у вас есть доступ к инструкциям множественного сложения или другим специальным инструкциям. Я бы счел это вполне разумным.

примечание: эта реализация имеет переменные тайминги для того, сколько времени занимает exp_mod в зависимости от входного параметра, поэтому она уязвима для взломов, основанных на тайминге (хотя для 16-битного ключа тоже можно просто взломать методом грубой силы). Относительно легко изменить этот код, чтобы он был устойчивым к этому, введя фиктивные инструкции, которые теоретически должны только повредить средней производительности, а производительность в худшем случае не изменится.

Любая математика может быть выполнена на любом процессоре. Вопрос только в том, сколько операций, а значит и сколько времени это займет.

5 ¹⁵ = 2 ^34,8 , поэтому для выражения требуется не менее 35 бит. Биты приходят в байтах по 8 каждый на PIC 18, поэтому вы должны использовать 40 бит или 5 байтов для представления этого значения.

Итак, все, что вам нужно написать, это процедура, которая умножает 1-байтовое число на 5-байтовое число в 5-байтовое число. На самом деле это довольно просто, так как PIC 18 имеет аппаратный множитель 8x8 в 16 бит. По сути, вы умножаете один входной байт на каждый из широких числовых байтов отдельно и суммируете результаты. Я бы, вероятно, написал это как развернутый цикл, поэтому кишки будут состоять из 5 наборов умножения и двух сложений или 15 инструкций.

Добавлен

Как правильно указал Дэн Д. в комментарии, я забыл обратиться к модульной части. Это значительно сложнее, чем вычисление 5 ¹⁵ . По сути, вы делите на 23 и оставляете только остаток. Вы можете сохранить несколько инструкций, потому что вам не нужно частное в конце, но в основном вам все равно придется писать 5-байтовый алгоритм, разделенный на 1-байтовый с 1-байтовым остатком.

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

Отказ от ответственности: если вы хотите сделать это в образовательных целях, продолжайте. Если вы хотите использовать его для реальной защиты связи, возьмите копию «Руководства по прикладной криптографии».

Как уже говорилось, проблема не в возведении в степень, а в операции по модулю (если делать это наивно). Умножение Монтгомери — эффективный способ решить эту проблему. Короче говоря, проблема сопоставляется с другой группой, которая обладает тем свойством, что операция по модулю может быть заменена сдвигом битов (и/или копированием памяти).

Я не знаю о реализации DH на 8-битных чипах, но точно знаю, что есть реализации RSA для 8-битных микропроцессоров.