Pregunta:
He visto que en gmail hay 3 certificados en jerarquía. Noté que todos los certificados tienen el mismo exponente (65537 con 24 bits). ¿Por qué el valor del exponente es el mismo para todos los certificados y cómo?
Respuesta:
Este es un truco común para acelerar el cifrado y la verificación. El exponente es especial, ya que es un número primo pequeño con solo dos bits establecidos, lo que hace que la exponenciación modular en el software sea lo suficientemente rápida. Otro exponente público de uso común es el 3, pero creo que uno está cayendo en desgracia en estos días.
Consulte esta pregunta para obtener más información sobre la seguridad de estos exponentes especiales.
En cuanto al "cómo" de estos exponentes, dado que el módulo se genera aleatoriamente (dentro de algunas restricciones, por supuesto), la clave privada sigue siendo aleatoria y no se puede determinar solo a partir del exponente y módulo públicos.
La razón por la que queremos la menor cantidad posible de bits en el exponente es la forma en que se realiza la exponenciación modular. Cuando calcula la exponenciación modular utilizando la clave pública, solo tiene dos números: el exponente público, e , y el módulo, n . Para las claves privadas, podemos tener más información (en realidad, los factores primos de n ) para acelerar los cálculos (puede buscar el "Teorema del resto chino" para RSA si está interesado), pero obviamente estos factores primos no se pueden distribuir a lo largo con la clave pública. Entonces, nos quedamos con el algoritmo estándar de multiplicar y cuadrar .
La idea principal del algoritmo es cuadrar el mensaje para cada bit de su exponente y multiplicarlo a un acumulador cuando se establece el bit correspondiente en el exponente. Digamos que quieres calcular m 13 . Primero se escribe como una multiplicación de una serie de m 2 j , es decir, m 2 3 · m 2 2 · m 2 0 . Establezca una variable en my el resultado en 1. Ahora, comience a contar de 0 a 3 (la longitud máxima de bits del módulo). Para cada valor, si 13 tiene la posición del bit en el contador establecido, multiplique su resultado con la variable. Antes de aumentar su contador, eleve al cuadrado su variable. Con este esquema, calculará m , m 2 , m 4 y m 8 en cada iteración de su ciclo al elevar al cuadrado su variable. Cuando un bit se establece en exponente, elige el valor y lo multiplica con su resultado para obtener m · m 2 · m 8 (que es m 13 ). Para una clave aleatoria de 1024 bits, deberá llamar a sqrmod(m, n) 1024 veces, y también a mulmod(accumulator, m, n) aproximadamente 512 veces (los bits son aleatorios, por lo que solo sabemos que es menor que 1024 y 512 en promedio).
Cuando tiene un exponente pequeño con solo dos bits establecidos, digamos 65537, necesita elevar al cuadrado solo 16 veces y multiplicar solo una vez ( m 2 k se puede calcular inicializando un valor am , y elevándolo al cuadrado repetidamente k veces, y m 65537 = m 2 16 · m ). Es incluso más rápido cuando el exponente es 3: elevas al cuadrado una vez y multiplicas una vez.