RSA: Creación de una clave de longitud deseada

Question

Gracias y con respeto a los usuarios de este sitio, he conseguido crear un procedimiento de Cifrado/Descifrado para el algoritmo RSA.

También implementé una prueba de primalidad probabilística de Miller-Rabin.

Ahora mi pregunta es mucho más simple, pero mi cabeza realmente no puede inventar una respuesta.

Supongamos que necesito una clave de longitud 1024 y he generado dos primos, cada uno 512 bits de valor. Pero su producto no será necesariamente 1024 -bit de largo, puede ser menor.

¿Qué debo hacer en este caso? ¿Descartar los primes y volver a intentarlo? ¿Hay alguna solución más inteligente?

¡Muchas gracias!

\============ UPDATE ===================

Gracias a jarra y Gadi A He aprendido que, para los números binarios, basta con poner a 1 los dos bits más significativos para generar la longitud de bits deseada.

Otro reto es que en mi biblioteca los números grandes pueden tener una base de dígitos arbitraria;

Así que la estructura real es a_0 mod BASE | a_1 mod BASE | ... | a_(n-1) mod BASE .

¿Qué debo hacer para obtener una clave de n longitud de los dígitos, donde todos los dígitos tienen base numérica BASE ?

Answer 1

Usted simplemente debe escoger los números al azar de una manera que asegura que son más grandes de algún número grande; se puede hacer mediante el establecimiento de la MSB a ser 1, como se sugirió en el comentario. También puede hacer algo como

p=rand(big_num) + big_num;

Un consejo adicional: la mayoría de las veces no necesitará Miller-Rabin para descubrir que un número aleatorio no es primo: lleve una tabla de los 100 primeros primos más o menos e intente dividir primero el número que está probando entre ellos. En la práctica, suele ahorrar mucho tiempo.

Answer 2

Supongo que tu pregunta actualizada es: ¿Cómo puedo generar dos números primos de n dígitos (en base $b$ ) tal que su producto tenga 2n dígitos?

Un camino: Que ambos sean mayores que $\sqrt{b^{2n-1}}$ . (Entonces su producto es mayor que $b^{2n-1}$ y, por tanto, tiene 2n dígitos). Todavía tendrás una gran región en la que puedes generar aleatoriamente los primos. Por ejemplo, para generar dos números primos de 2 dígitos en base 10 cuyo producto tenga 4 dígitos, sólo tienes que asegurarte de que ambos tengan al menos 32 dígitos. (Puesto que $\sqrt{1000}\approx31.6$ .)

Más sencillamente, si no quiere calcular $\sqrt{b^{2n-1}} = (\sqrt{b})b^{n-1}$ precisamente, basta con asegurarse de que el primer dígito de los primos es algo al menos $\sqrt{b}$ . Así, por ejemplo, al generar dos primos de n dígitos en base 10, basta con asegurarse de que el primer dígito de ambos primos sea al menos 4. (Puesto que $\sqrt{10}\approx3.16$ .) Esto significaría que cada primo es al menos $\sqrt{b}b^{n-1}$ como antes, por lo que su producto es al menos $b^{2n-1}$ y tiene $2n$ dígitos.