• Saltar al contenido principal
  • Saltar a la barra lateral principal
  • Saltar al pie de página

Una al Día

Boletín de noticias de Seguridad Informática ofrecido por Hispasec

Usted está aquí: Inicio / General / Nuevo dispositivo óptico para factorizar más rápido

Nuevo dispositivo óptico para factorizar más rápido

2 septiembre, 1999 Por Hispasec Deja un comentario

Adi Shamir, la «S» del popular algoritmo RSA, ha diseñado un dispositivo
óptico (presentado en EuroCrypt’99) capaz de acelerar, en órdenes de
magnitud, uno de los pasos clave de los modernos algoritmos de
factorización. Ello permitirá «romper» claves asimétricas, consideradas
seguras hasta ahora, en un tiempo razonable.
Recordemos que muchos de los algoritmos criptográficos asimétricos basan
su seguridad en la dificultad de factorizar un número «n» cuando éste es
muy grande. Es decir, en encontrar los factores «p» y «q» tales que
«n=p*q». El RSA, por ejemplo, uno de los algoritmos asimétricos más
populares que existe, basa su seguridad en esta premisa.

La mayoría de los algoritmos modernos de factorización se basan en el
concepto de criba. En una primera etapa se localizan una serie de
números cuyos cuadrados módulo «n» tengan descomposiciones «suaves»
(«smooth», en inglés) en factores primos pequeños. Esta primera etapa es
la más lenta, ya que un ordenador personal rápido requiere varios
segundos para validar cada valor tentativo, y la mayoría de los valores
evaluados resultan no ser válidos. Afortunadamente la comprobación de
cada valor puede realizarse de forma independiente, por lo que es
posible realizarlo en paralelo, en máquinas distintas.

Es interesante comentar que el número de valores «suaves» necesarios
para pasar a la siguiente etapa es un parametro que puede fijarse de
forma arbitraria. No obstante, este parámetro especifica también la
probabilidad de que un valor tenga una descomposición «suave». Es decir,
que si fijamos el parámetro para requerir muchos valores «suaves», la
probabilidad de que un valor dado sea «suave» es mayor que si cambiamos
el parámetro para requerir menos valores. Dado que evaluar y descartar
un valor, por no ser «suave», es una operación lenta, es preferible
aumentar las probabilidades de éxito aún a costa de necesitar más
valores «suaves» antes de pasar a la siguiente etapa. En la práctica se
suele trabajar tomando como base los primeros 200.000 números primos,
con lo que se necesitarán unos 200.000 valores «suaves».

Una vez localizados un cierto número de valores «suaves», un
superordenador (se requiere muchísima memoria RAM) procede a realizar
una eliminación gaussiana de la matriz resultante de combinar los
números «suaves» obtenidos en la etapa de criba, y tras una simple
operación de «máximo común denominador», se obtiene la factorización de
«n». Esta etapa tiene una duración reducida, comparada con la anterior.
No es fácilmente paralelizable, pero se trata de un paso muy rápido.

Adi Shamir, uno de los creadores del propio RSA, ha diseñado un
dispositivo óptico, de coste comparable al de una estación de trabajo de
gama media (5.000 dólares) capaz de realizar la etapa de criba, la
operación más costosa, mil veces más rápido que un ordenador de altas
prestaciones. En la práctica ello hubiera supuesto que la factorización
del reto RSA-140, completada en Febrero de 1.999 y que supuso el empleo
de doscientas estaciones de trabajo calculando a lo largo de cuatro
semanas, se hubiera podido completar en apenas unas pocas horas.

El dispositivo es un cilindro de un tamaño aproximado de 6*10 pulgadas
(aproximadamente 15*25 centímetros). Se llama TWINKLE, es muy sencillo y
barato de fabricar (no requiere componentes de precisión). Funciona,
básicamente, operando diodos electroluminiscentes (LEDs), cada uno de
ellos parpadeando con un período fijado en relación con el primo que
representa. Un ordenador conectado a TWINKLE le va enviando valores a
comprobar, proceso que consume menos de una centésima de segundo.
TWINKLE devolverá, a su vez, una estimación de la «suavidad» del número.
Bastará, por tanto, que el ordenador verifique informáticamente si el
número es o no «suave», tal y como lo hacía previamente. Pero ahora se
limitará a realizar esta operación exclusivamente con los valores que
TWINKLE marque como más probables, lo que supone una impresionante
mejora de rendimiento.

¿Cuáles son las implicaciones prácticas?. Una mejora de tres órdenes de
magnitud en el rendimiento de los algoritmos de factorización constituye
una ganancia considerable. Como ya hemos dicho, romper el reto RSA-140
supuso el empleo de 200 potentes máquinas durante cuatro semanas
(criba), más 100 horas de cálculo en un superordenador para la reducción
Gaussiana. Si se hubiesen empleado 200 TWINKLEs, el tiempo de criba se
hubiera reducido a apenas 40 minutos. Las 100 horas de cálculo finales
tendrían que efectuarse de todos modos, eso sí.

El reto RSA-140 factorizó una clave de 465 bits. Considerando
exclusivamente el tiempo de criba, la complejidad del NFS (Number Field
Sieve) es de O(e^(1.92*(ln(n)^(1/3))*(ln(ln(n))^(2/3))), obteniendo la
siguiente tabla aproximada:

Longitud de la clave Tiempo de criba
BITS Dígitos
465 140 X
512 154 6*X
565 170 47*X
615 185 278*X
665 200 1508*X
768 231 39154*X
1024 308 47285717*X
2048 616 5.3*10^16*X

A la luz de esta tabla, y mientras no se descubran algoritmos de
factorización más avanzados, las claves RSA de 1024 bits son todavía
seguras. Pero las claves de menos de 768 bits, especialmente las de 512
bits, son tremendamente vulnerables. Si tenemos en cuenta que las
versiones internacionales de los navegadores sólo pueden utilizar claves
asimétricas de 512 bits, vemos claramente que los certificados de
usuario que se generan en la actualidad son susceptibles de ataque por
entidades con recursos moderados.

Por cierto, TWINKLE es la abreviatura de «The Weizmann INstitute Key
Locating Engine».

Más información:

TWINKLE
http://www.rsa.com/rsalabs/html/twinkle.htm
http://www.rsa.com/pressbox/html/990504.html
http://www.rsa.com/rsalabs/html/twinkle_qa.html
http://jya.com/twinkle.eps
http://ceu.fi.udc.es/art-gpul/RSA_512bit_optic_cracker_design.txt
http://catless.ncl.ac.uk/Risks/20.38.html

Factorización RSA-140

Jesús Cea Avión
jcea@argo.es
http://www.argo.es/~jcea/

Acerca de Hispasec

Hispasec Ha escrito 6939 publicaciones.

  • View all posts by Hispasec →
  • Blog

Compártelo:

  • Twitter
  • Facebook
  • LinkedIn
  • Reddit
  • Telegram
  • WhatsApp

Publicaciones relacionadas

Publicado en: General

Interacciones con los lectores

Deja una respuesta Cancelar la respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.

Barra lateral principal

Buscar

Síguenos

siguenos en twitter

UAD360 EDICIÓN 2022

https://www.youtube.com/watch?v=go_CSWK56yU

Populares de UAD

  • Vulnerabilidad zero-day en AWS Glue
  • Técnica permite modificar ficheros PDF con firma digital
  • Tamagotchi para hackers: Flipper Zero
  • Campañas de phishing utilizan Flipper Zero como cebo
  • Parches de enero 2023: Microsoft corrige 98 vulnerabilidades

Entradas recientes

  • Vulnerabilidad zero-day en AWS Glue
  • Evasión de CloudTrail en AWS a través de API no documentada
  • Parches de enero 2023: Microsoft corrige 98 vulnerabilidades
  • UAD se abre a la comunidad
  • Campañas de phishing utilizan Flipper Zero como cebo
  • Vulnerabilidades críticas en productos de Synology
  • Más de dos docenas de errores de WordPress explotados por un nuevo malware de Linux
  • Correo electrónico
  • Facebook
  • LinkedIn
  • RSS
  • Twitter

Footer

UAD

UAD nació a raíz de un inocente comentario en un canal IRC hace 24 años. A través de los archivos, un lector curioso puede ver cómo ha cambiado (o no) la seguridad de la información desde entonces.

Aviso Legal

  • Aviso Legal
  • Términos y Condiciones
  • Política de Privacidad
  • Política de Cookies

Copyright © 2023 · Hispasec Sistemas, S.L. Todos los derechos reservados

Este sitio web utiliza cookies propias y de terceros para fines analíticos y para mostrarte publicidad (tanto general como personalizada) relacionada con tus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación (por ejemplo, páginas visitadas), para optimizar la web y para poder valorar las opiniones de los servicios consultados por los usuarios. Para administrar o deshabilitar estas cookies haz clic en: Configurar Cookies


Rechazar todo Aceptar Todo
Configurar Cookies

Resumen de privacidad

Este sitio web utiliza cookies para mejorar su experiencia mientras navega por el sitio web. De estas, las cookies que se clasifican como necesarias se almacenan en su navegador, ya que son esenciales para el funcionamiento de las funcionalidades básicas del sitio web. También utilizamos cookies de terceros que nos ayudan a analizar y comprender cómo utiliza este sitio web. Estas cookies se almacenarán en su navegador solo con su consentimiento. También tiene la opción de optar por no recibir estas cookies. Pero la exclusión voluntaria de algunas de estas cookies puede afectar su experiencia de navegación.
Necesaria
Siempre activado
Las cookies necesarias son absolutamente esenciales para que el sitio web funcione correctamente. Estas cookies garantizan funcionalidades básicas y características de seguridad del sitio web, de forma anónima.
CookieDuraciónDescripción
cookielawinfo-checkbox-analytics11 monthsEsta cookie está configurada por el complemento de consentimiento de cookies de GDPR. La cookie se utiliza para almacenar el consentimiento del usuario para las cookies en la categoría "Análisis".
cookielawinfo-checkbox-functional11 monthsLa cookie está configurada por el consentimiento de cookies de GDPR para registrar el consentimiento del usuario para las cookies en la categoría "Funcional".
cookielawinfo-checkbox-necessary11 monthsEsta cookie está configurada por el complemento de consentimiento de cookies de GDPR. Las cookies se utilizan para almacenar el consentimiento del usuario para las cookies en la categoría "Necesario".
cookielawinfo-checkbox-others11 monthsEsta cookie está configurada por el complemento de consentimiento de cookies de GDPR. La cookie se utiliza para almacenar el consentimiento del usuario para las cookies en la categoría "Otro.
cookielawinfo-checkbox-performance11 monthsEsta cookie está configurada por el complemento de consentimiento de cookies de GDPR. La cookie se utiliza para almacenar el consentimiento del usuario para las cookies en la categoría "Rendimiento".
viewed_cookie_policy11 monthsLa cookie está configurada por el complemento de consentimiento de cookies de GDPR y se utiliza para almacenar si el usuario ha dado su consentimiento o no para el uso de cookies. No almacena ningún dato personal.
Analítica
Las cookies analíticas se utilizan para comprender cómo interactúan los visitantes con el sitio web. Estas cookies ayudan a proporcionar información sobre métricas, el número de visitantes, la tasa de rebote, la fuente de tráfico, etc.
GUARDAR Y ACEPTAR