exponenciales grandes y procesadores PIC de 8 bits

Como se indica en los comentarios, no es necesario calcular la exponencial real. Puede utilizar la aritmética modular para reducir el valor máximo que necesita almacenar:

\ begin {se reúne} (a b) ~ \ textrm {mod} ~ m = ((a ~ \ textrm {mod} ~ m) (b ~ \ textrm {mod} ~ m)) ~ \ textrm {mod} ~ m \ end {se reúnen}

Para \ $ (ab) ~ \ textrm {mod} ~ m \ $, el valor máximo que necesitará almacenar es \ $ (m-1) ^ 2 \ $, que para m=23 significa que debe poder almacenar 484. Esto está fuera del rango de los números de 8 bits, pero se ajusta a 16 bits. Sin embargo, como Olin señaló, algunos micros de 8 bits pueden manipular valores de 16 bits de manera eficiente, por lo que no es un gran problema.

Una implementación general en C podría tener el siguiente aspecto:

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;
}

Si su uC tiene una instrucción de módulo eficiente, esto suele ser lo suficientemente bueno. Sin embargo, si no lo hace y sabe que n siempre será un valor determinado, hay una implementación eficiente de división (y, por lo tanto, módulo) por T. Granlun y P.L. Montomería . Agner Fog también tiene una descripción de cómo funciona esto .

Aquí hay una implementación pirateada para 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;
}

Las únicas operaciones de 16 bits requeridas son:

• suma / resta
• multiplicación
• desplazamiento a nivel de bits
• bitwise y
• comparación de igualdad

No estoy familiarizado con el conjunto de instrucciones de PIC, pero aquí hay unas instrucciones en el peor de los casos:

• 4*log2(power) comparaciones
• 4*log2(power) salta
• 2*log2(power) sustracciones
• 3*log2(power) bitwise shift
• 6*log2(power) multiplicaciones

Para power=15 , esto es aproximadamente 76 instrucciones. Tenga en cuenta que esto puede disminuir si tiene acceso a instrucciones de adición múltiple u otras instrucciones especiales. Consideraría esto bastante razonable.

nota: Esta implementación tiene tiempos variables por el tiempo que demora exp_mod dependiendo del parámetro de entrada, por lo que es vulnerable a las grietas basadas en el tiempo (aunque para una clave de 16 bits, solo puede ser brutal) fuerza agrietada, también). Es relativamente fácil modificar este código para que sea resistente a esto mediante la inyección de instrucciones ficticias, que en teoría solo deberían afectar el rendimiento promedio y el desempeño en el peor de los casos no se modifica.

Cualquier matemática se puede hacer en cualquier procesador. La única pregunta es cuántas operaciones y, por lo tanto, cuánto tiempo tomará.

5 ¹⁵ = 2 ^34.8 , por lo que requiere al menos 35 bits para expresar. Los bits vienen en bytes de 8 cada uno en un PIC 18, por lo que usarías 40 bits o 5 bytes para representar este valor.

Entonces, todo lo que tiene que escribir es una rutina que multiplica un número de 1 byte por un número de 5 bytes en el número de 5 bytes. Esto es realmente bastante fácil ya que el PIC 18 tiene un hardware 8x8 en 16 bits multiplicador. Básicamente, multiplica el byte de entrada por cada uno de los bytes de número ancho por separado y suma los resultados. Probablemente escribiría esto como un bucle desenrollado, por lo que las agallas serían 5 series de una multiplicación y dos adiciones, o 15 instrucciones.

Añadido

Como Dan D señaló correctamente en un comentario, me olvidé de abordar la parte de módulo. Eso es significativamente más complicado que computar 5 ¹⁵ . Básicamente, haces una división por 23 y solo mantienes el resto. Es posible que pueda guardar algunas instrucciones porque no necesita el cociente al final, pero en su mayoría aún tiene que escribir un byte de 5 bytes dividido por 1 byte con el algoritmo de resto de 1 byte.

Nuevamente, todo esto se puede hacer en un PIC 18 u otros procesadores pequeños, pero tomará muchas más instrucciones que en un procesador que pueda manipular los números de 40 bits de forma nativa.

Descargo de responsabilidad: si desea hacerlo con fines educativos, adelante. Si desea utilizarlo para proteger realmente la comunicación, obtenga una copia del "Manual de criptografía aplicada".

Como ya se dijo, el problema no es la exponenciación, sino la operación de módulo (si se hace ingenuamente). La multiplicación de Montgomery es una forma eficiente de resolver esto. En resumen, el problema se asigna a un grupo diferente que tiene la propiedad de que la operación de módulo se puede reemplazar por desplazamiento de bits (y / o copia de memoria)

No sé sobre implementaciones de DH en chips de 8 bits, pero estoy seguro de que hay implementaciones RSA para microprocesadores de 8 bits.