Gran exponenciales y 8 bits PIC procesadores

Question

¿Alguien sabe si es de 8 bits (PIC) procesadores normalmente puede manejar grandes exponenciales, por ejemplo, 5^15 mod 23, con una velocidad razonable? No hacerlo resultará en más ciclos de 16-bits de los procesadores?

Yo estoy esperando para implementar de Claves Diffie-Hellman de Cambio en uno, pero el pensamiento de la computación gran exponenciales parece desalentador.

Son grandes exponenciales hace comúnmente en los procesadores de 8 bits? Es el intercambio de claves DH comúnmente implementado en tales dispositivos de gama baja?

Answer 1

Cualquier matemáticas se puede hacer en cualquier procesador. La única pregunta es cómo muchas de las operaciones, y por lo tanto cuánto tiempo va a tomar.

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

Así que todo lo que tienes que escribir es una rutina que multiplica un 1 byte número 5 número de bytes en el 5 byte número. Esto es en realidad bastante fácil, ya que el PIC 18 tiene un hardware de 8x8 en 16 bits del multiplicador. Básicamente, se multiplica la entrada de un byte por cada uno de los gran número de bytes por separado y se suman los resultados. Probablemente me escribo esto como un desenrollado de bucles, por lo que las entrañas será el 5 conjuntos de multiplicar y suma dos, o 15 instrucciones.

Agregó

Como Dan D señalado correctamente en un comentario, se me ha olvidado la dirección de el modulo de la parte. Que es mucho más complicado que la computación 5¹⁵. Básicamente, tendrás que hacer una división por 23 y mantener sólo el resto. Usted puede ser capaz de ahorrar un par de instrucciones, porque no necesita el cociente en la final, pero la mayoría todavía tiene que escribir un 5 bytes dividido por 1 byte 1 byte resto del algoritmo.

De nuevo, todo esto se puede hacer en un PIC de 18 años o de otros pequeños procesadores, pero tendrá muchas más instrucciones que un procesador que puede manipular 40 bits de los números de forma nativa.

Answer 2

Como crasic señaló en los comentarios, que realmente no es necesario para el cálculo de la exponencial real. Puede utilizar la aritmética modular para reducir el valor máximo que usted necesita para almacenar:

\begin{gather} (a b) ~\textrm{mod}~ m = ((a ~\textrm{mod}~ m) (b ~\textrm{mod}~ m)) ~\textrm{mod}~ m \end{reunir}

Para \$(a b)~\textrm{mod}~m\$, el valor máximo que se necesita para almacenar es \$(m-1)^2\$, que para m=23 significa que usted debe ser capaz de almacenar 484. Esto está fuera del intervalo de 8 bits de los números, pero cabe en 16-bits. Sin embargo, como Olin señaló algunos de los 8-bits de micros se pueden manipular los valores de 16 bits eficaz para que este no es un gran problema.

Una aplicación general en C 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 la uC tiene un eficiente módulo de instrucción, esto es generalmente lo suficientemente bueno. Sin embargo, si usted no lo hace y saber que n siempre será un valor determinado, hay una división eficiente (y por lo tanto el modulo) la aplicación por T. Granlun y P. L. Montomery. Agner Niebla también tiene una descripción de cómo funciona esto.

He aquí una hackeado aplicación 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;
}

La única de 16 bits de operaciones, a continuación, son:

• suma/resta
• la multiplicación
• bit a bit cambio
• bit a bit y
• la comparación de igualdad

Yo no estoy familiarizado con el PIC conjunto de instrucciones, pero aquí es más o menos el peor de los casos las instrucciones de conteo:

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

Para power=15, esto es aproximadamente 76 manual de instrucciones. Tenga en cuenta que esto puede ir hacia abajo si usted tiene acceso a multiplicar-agregar instrucciones u otras instrucciones especiales. Yo consideraría bastante razonable.

nota: Esta aplicación tiene la variable de los tiempos de cuánto tiempo exp_mod toma dependiendo del parámetro de entrada, por lo que es vulnerable a la sincronización basada en las grietas (aunque para una de 16 bits de la clave, puede ser simplemente la fuerza bruta agrietado, también). Es relativamente fácil de modificar este código para ser resistentes a este mediante la inyección de maniquí de instrucciones, que en teoría sólo debe doler rendimiento promedio y el peor de los casos el rendimiento es igual.

Answer 3

Descargo de responsabilidad: Si quieres hacerlo para fines educativos, vaya por delante. Si usted desea utilizar para proteger la comunicación, ir a una obtener una copia del "Manual de Criptografía Aplicada".

Como ya se ha dicho, el problema no es la exponenciación, pero el modulo de operación (si se hace ingenuamente). Montgomery multiplicación es una forma eficiente de resolver esto. En resumen, el problema se transforma en un grupo diferente al que tiene la propiedad de que el modulo de operación puede ser sustituido por el bit de desplazamiento (y/o la copia de la memoria)

Yo no sé acerca de DH implementaciones en 8-Bits chips, pero estoy seguro de que hay RSA implementaciones para la 8 Bits de los microprocesadores.