¿es esta una forma correcta de generar claves rsa?

Question

¿Este código me va a dar valores correctos para las claves RSA (suponiendo que las demás funciones sean correctas)? im teniendo problemas para conseguir mi programa para descifrar correctamente, como en ciertos bloques no se descifra correctamente

esto es en python:

import random 
def keygen(bits): 
    p = q = 3 
    while p == q: 
     p = random.randint(2**(bits/2-2),2**(bits/2)) 
     q = random.randint(2**(bits/2-2),2**(bits/2)) 
     p += not(p&1)        # changes the values from 
     q += not(q&1)        # even to odd 

     while MillerRabin(p) == False:   # checks for primality 
      p -= 2 
     while MillerRabin(q) == False: 
      q -= 2 
    n = p * q 
    tot = (p-1) * (q-1) 
    e = tot 
    while gcd(tot,e) != 1: 
     e = random.randint(3,tot-1) 
    d = getd(tot,e)      # gets the multiplicative inverse 
    while d<0:       # i can probably replace this with mod 
     d = d + tot 
    return e,d,n 

un conjunto de claves generadas:

e = 3daf16a37799d3b2c951c9baab30ad2d

d = 16873c0dd2825b2e8e6c2c68da3a5e25

n = dc2a732d64b83816a99448a2c2077ced

Answer 1

Supongo que está haciendo esto por diversión y aprendizaje, y no por algo que necesite seguridad real.

Aquí es un par de cosas que noté (en ningún orden particular):

1. no le garantiza que tendrá n longitud bits. Puede ser tan corto como bits - 4.

2. random no es un generador de números aleatorios criptográficamente seguro.

3. Es común (e igual de seguro) seleccionar el exponente público, e, a 65537. Esto es primo, por lo que puede reemplazar la verificación de coprime con una comprobación de divisor.

4. Es un poco extraño buscar e configurando e = tot (la comprobación de coprime está destinada a fallar).

De lo contrario, se ve bien. La clave parece funcionar bien, también. ¿Tiene un ejemplo de un bloque que no se está descifrando correctamente? Recuerde que solo puede encriptar datos que sean menores que n. Entonces, con una clave de 128 bits (como en su ejemplo) no puede encriptar todos los números de 128 bits.

Answer 2

Matemáticamente, su n, e y d parecen respetar las reglas RSA (es decir, para cada primer r que divide n, r no divide n y d es un inverso de e módulo r-1). Sin embargo, RSA es un poco más que eso; también exige algunas reglas de relleno, que regulan cómo un mensaje (una secuencia de bytes) debe transformarse en un módulo entero n, y viceversa. El relleno estándar (consulte PKCS#1) implica que al menos 11 bytes se agregan al mensaje, y el resultado no debe seguir siendo n. Por lo tanto, con un módulo de 128 bits como el que muestra, la longitud máxima del mensaje de entrada para el cifrado será de 5 bytes.

Además, algunas implementaciones de RSA se negarán a trabajar con claves RSA que son demasiado pequeñas para la seguridad. Un módulo de 128 bits puede ser un factor en cuestión de segundos (ver this page para un applet Java de factorización, que usa ECM y tamiz cuadrático para factorizar números relativamente pequeños como el tuyo). El registro actual en factorización es de 768 bits; se recomienda una longitud de módulo de al menos 1024 bits para la seguridad a corto plazo. Una implementación típica de RSA aceptará usar claves de 512 bits, pero muchas rechazarán algo más corto que eso.

Otro posible problema es en el orden relativo de p y q. Las ecuaciones establecidas en PKCS # 1 asumen que p> q (de lo contrario, existe una resta adicional para realizar en la parte CRT). Si tiene p < q, entonces algunas implementaciones pueden equivocarse (lo encontré con la implementación estándar RSA de Microsoft en Windows). Simplemente compare p con q y cámbielos si es necesario.

Siempre a nivel práctico, algunas implementaciones generalizadas RSA rechazarán una clave RSA tal como el exponente público e no encaja dentro de un entero de 32 bits (esto incluye la implementación RSA usada en Windows, en particular a través de Internet Explorer para conectarse a los sitios web de HTTPS, así que cuando escribo "generalizado" lo digo en serio). La seguridad de RSA no parece verse afectada por la elección de e, por lo que es habitual elegir una pequeña e, que acelera la parte que utiliza la clave pública (es decir, cifrado, en lugar de descifrado o verificación de firma) , a diferencia de la generación de firmas). e = 3 es lo mejor que podría hacer, pero por razones tradicionales (incluido un malentendido histórico sobre una supuesta debilidad), a menudo se usa e = 65537. Solo necesita tener e relativamente mejor que p-1 y q-1. En una implementación práctica, primero elija e, luego realice un ciclo dentro de la generación para p y q, siempre que no coincidan con esa regla adicional.

Desde el punto de vista de la seguridad:

• Su proceso de generación no es uniforme, en la que serán seleccionados algunos números enteros primos más frecuencia que otros. En particular, un primer p tal que p + 2 también es primo casi nunca será seleccionado. Con un tamaño de módulo adecuado, esto debería ser no ser un problema (ese tipo especial de sesgo se estudió y descubrió que no es un gran problema), pero no obstante es una mala relación pública.

• Su n puede ser un poco más pequeño que el tamaño de destino, en caso de que ambos p y q están cerca del límite inferior de su rango de generación.Una manera simple de evitar que se va a restringir el rango de [sqrt (2) * 2 ^b-1, 2 ^b] tanto para p y q.

• No puedo garantizar la seguridad del módulo random que utiliza. Un generador de números aleatorios criptográficamente seguro no es una tarea fácil de hacer.

• En términos generales, la implementación correcta de RSA sin filtrar información confidencial a través de varios canales secundarios (tiempo, uso de la memoria caché ...) no es una tarea fácil. Si desea seguridad en una configuración práctica, realmente debería realmente usar un paquete existente. Creo que Python tiene formas de interactuar con OpenSSL.