Cracking un N bits números de módulo RSA

Question

Esto está relacionado con mi posterior anterior, donde mi única opción era tener un algoritmo RSA que parecía relativamente débil. Supongamos que yo quiero para codificar un número de 35 bits (de 0 hasta 34359738367) con un módulo de 36 bits (entre 34359738368 68719476735 hasta).

Haciendo referencia a la http://en.wikipedia.org/wiki/RSA que pueda ver que mi n es entre 34359738368 68719476735 hasta un totient aleatorio (de la forma P-1 * q-1). Yo elija un d aleatoria y e. Puedo codificar un número y mostrar que en la interfaz de usuario.

A los efectos de argumentación supongamos que un usuario puede ver hasta 1.000 dichas salidas. ¿Puede usar algunos algoritmos como Polla de ni nada por el estilo para romper mi D, E o N y con ello iniciar la predicción de nuevos números? Si es así la fuerza con la que va a ser? (Por el hecho de saber decir 1000 conjuntos de entradas / salidas)

Como un ejemplo (considere 6 salidas como muestra en el formato de entrada / salida),

1. 10001621865,31116156015
2. 10001621866,33031668326
3. 10001621867,37351399313
4. 10001621868,06071714212
5. 10001621869,01188523761
6. 10001621870,18341011998

Puede alguien decirme lo que mi n, d, e fue? (N entre 34359738368 hasta 68719476735)

Simplemente quiero saber cómo manipulable que es, así que si me podía dar ninguna información sobre el tiempo, la rapidez, el número de salidas puede uno tiene que ver, lo que se puede utilizar algoritmos etc. Será grande.

PS: El usuario no ve la "e" como el algoritmo estándar de RSA. Él sólo puede ver los conjuntos de salida de entrada.

Detalles Añadidos Estoy tratando de presentar un secuencial de identificación de usuario de dB para el usuario. Debido a que es secuencial no quiero un usuario de adivinar Identificación de otro usuario haciendo algunas inscripciones. Para evitar esto tengo que trepar a un número de dígitos <= 12. Había gran cantidad de limitaciones en torno a este que se han explicado en esta pregunta .

También el valor de n, d y e no se conoce para el usuario. El máximo que un usuario puede ver es de unos pocos entrada ouput muestras (por medio de registrarse repetidamente)

La aceptación de la respuesta Publicado por Accipítridos ya que el algoritmo "Jacobi" se puede utilizar para descifrar esto en cuestión de pocos segundos. Sin saber N, E o p.

Answer 1

Un atacante puede adivinar un factor p de n y e mod (p-1). Cada suposición se puede comprobar mediante la adopción de un mensaje m, el cálculo de m ^ e mod p y luego comparar con c mod p, donde c es el texto cifrado correspondiente. Como p y e mod (p-1) son quizás 20 bits cada uno, esto significa que la seguridad del esquema no es mayor que 40 bits.

Pero 40 bits sólo es un límite superior muy cruda. Un atacante puede hacer mucho mejor. Por ejemplo se puede adivinar un factor p. Luego se calcula los símbolos de Jacobi de los mensajes y textos cifrados. Si un mensaje m es un residuo cuadrático mod p, entonces el texto cifrado debe ser un residuo cuadrático mod p y viceversa. Por lo tanto, si esta relación no es satisfecha por un par de mensajes / texto cifrado se puede rechazar la suposición de p. O el atacante puede calcular logaritmos discretos entre mensaje y texto cifrado. Esto le da a un candidato mucho más rápido para el mod (p-1).

Esto debería dar un nivel de seguridad de 20-30 bits; de ahí requerir unos segundos para romper. Si se extiende el número de muestras a 20 podría tratar algunos puntos de referencia.

Actualización: Ya que no me dio 20 muestras para ejecutar un experimento, que tenía que generar ellos yo mismo. Con las siguientes muestras

m = 10001621865  c = 31116156015
m = 10001621866  c = 33031668326
m = 10001621867  c = 37351399313
m = 10001621868  c = 6071714212
m = 10001621869  c = 1188523761
m = 10001621870  c = 18341011998
m = 10001621871  c = 7620400191
m = 10001621872  c = 36106912203
m = 10001621873  c = 37615263725
m = 10001621874  c = 7795237418
m = 10001621875  c = 34774459868
m = 10001621876  c = 4555747045
m = 10001621877  c = 33123599635
m = 10001621878  c = 34836418207
m = 10001621879  c = 33962453633
m = 10001621880  c = 6258371439
m = 10001621881  c = 7500991556
m = 10001621882  c = 5071836635
m = 10001621883  c = 911495880
m = 10001621884  c = 39558568485

como entrada, el algoritmo descrito anteriormente encuentra los factores 201821 y 206153  en 20 ms. Como se describe esto no necesita saber electrónico, aunque su elección de e = 65537 es fácil de adivinar y se puede explotar también.

La fuerza de RSA es que se basa en la dificultad de factorizar números enteros grandes. Aquí se quita esta dificultad y lo que queda son los puntos débiles (es decir, las relaciones matemáticas) de RSA. La construcción de un bloque de cifrado basado en RSA es una idea horrible. Realmente no veo por qué no desea utilizar una construcción de Luby-Rackoff como propuse anteriormente.

Answer 2

RSA es vulnerable frente a un ataque de texto cifrado elegido. Es decir, decimos que queremos romper texto cifrado y, podemos utilizar uno de los pares de texto cifrado de texto plano para romperlo.

¿Cómo romperlo:

elegir un x0 y y0, donde x0 y y0 es un par de texto claro-texto cifrado que se ha proporcionado.

y1 = y0 * y n y1 mod es otro de los 1000 textos cifrados dadas al usuario que satisfaga este criterio. x1 es el descifrado de y1, que también se da, esto significa:

x1 y1 = ^ d mod n (esto se ha dado a nosotros, que ya sabemos x1)

x1 = (y0 * y) ^ d mod n x1 = y0 ^ d * y ^ d mod n Ξ x0 * x

x1 * x0 ^ -1 = x

x es el descifrado de y.

Esto es por supuesto depende de si o no y0 * y n mod produce otro texto cifrado que ya que tenemos, y ya que tenemos sólo 1,000 tales pares para trabajar con, es poco probable pero no inviable de romper. Sólo tienes que elegir los pares con extremo cuidado.

También me gustaría añadir que el tamaño de n se trabaja con una heurística permite la factorización para encontrar los factores primos de n con bastante rapidez. Además, RSA es vulnerable a ataques puntuales, pero que puede ser frustrado fácilmente.

Con la información añadida: Sin saber N, D, o E, no hay absolutamente ninguna información proporcionada en absoluto, lo que significa combinaciones de adivinanzas de N, D, o E es tan bueno como adivinando el texto plano sí mismo. Para encontrar N y E, hay por lo menos 43,359,738,367 combinaciones de n de adivinar, así como todas las combinaciones de correo podrían ser. No es fácil para alguien incluso con 1000 pares de texto cifrado de texto plano para poder descifrar y e n.

Answer 3

Esta es una idea horrible, 36 bits RSA ?? ¿Por qué no simplemente ir con un bloque o corriente de cifrado? De esta manera se obtiene la 1:. 1 mapeo y de una manera más segura tanto

Una solución alternativa que yo recomendaría sería el uso de un hash SHA como UID y almacenar el número secuencial para cada usuario en la base de datos como una columna separada.