• 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 / Un análisis del dispositivo de factorización de Shamir

Un análisis del dispositivo de factorización de Shamir

21 septiembre, 1999 Por Hispasec Deja un comentario

La compañía RSA hace público un documento analizando el dispositivo
TWINKLE, diseñado por Adi Shamir. Este dispositivo permitiría acelerar
una de las dos etapas necesarias para factorizar un número, en tres
órdenes de magnitud (unas mil veces más rápido).
Como ya se comentaba en el boletín enviado el pasado 2 de Septiembre,
los algoritmos actuales de factorización se basan en dos etapas: en la
primera varios ordenadores buscan, en paralelo, una serie de relaciones
de congruencia. En una segunda etapa, un superordenador con una gran
cantidad de memoria procede a resolver la ecuación matricial obtenida en
el paso anterior.

El dispositivo de Shamir, llamada TWINKLE, permite acelerar unas mil
veces la primera etapa, aunque no aporta ninguna mejora adicional a la
segunda etapa.

En el documento que comentamos en este boletín, uno de los
investigadores de RSA realiza un análisis detallado de las implicaciones
prácticas de dicho dispositivo.

El primer paso consiste en evaluar cuánto se hubiera tardado en
factorizar RSA-140 (el mayor reto RSA factorizado en aquel momento;
recientemente se ha factorizado el RSA-155).

Para igualar las características de los equipos empleados en el reto
RSA-140, hubieran bastado sólo 7 dispositivos TWINKLE. Toda la primera
etapa de criba hubiera podido completarse en 6 días, en vez de las
cuatro semanas y 200 ordenadores utilizados realmente. La segunda etapa,
la resolución de la ecuación matricial, seguiría necesitando 100 horas
de cálculo en un superordenador. Se hubiera pasado de 33 días a 10 días.
Incluso con una criba infinitamente rápida, el tiempo requerido para
completar la segunda etapa hubiera sido de unas 100 horas. La ganancia
óptima no hubiera superado un factor del 800%.

RSA-140 tiene 465 bits. A medida que crece el tamaño de los números a
factorizar, aumenta el tiempo de criba, y el tamaño y tiempo para
resolver la ecuación matricial final. Operación, ésta última, que no se
puede paralelizar fácilmente.

Como comparación, factorizar RSA-140 (465 bits) consumió 64Mbytes de RAM
en cada una de las máquinas que colaboraron en la criba, y 825 Mbytes en
el superordenador. Factorizar un número de 768 bits supondrá 10Gigabytes
en cada ordenador que cribe y 160Gbytes en el superordenador. Factorizar
un número de 1024 bits necesitaría 256Gbytes en cada máquina de criba, y
10TeraBytes en el superordenador.

Se puede ver una estimación de tiempos para cada tamaño de número en
http://www.argo.es/~jcea/artic/hispasec08.htm.

A la vista de estos datos, es razonable pensar que las claves RSA de 768
bits son seguras a medio plazo, y las claves de 1024 bits están fuera de
las posibilidades de nada que podamos imaginarnos en este momento
tecnológico.

Más información:

An Analysis of Shamir’s Factoring Device
An Analysis of Shamir’s Factoring Device (PDF)
Nuevo dispositivo óptico para factorizar más rápido (jcea)
Nuevo dispositivo óptico para factorizar más rápido (HispaSec)
Factorización de RSA-155 (jcea)
Factorización de RSA-155 (HispaSec)

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
  • Campañas de phishing utilizan Flipper Zero como cebo
  • Técnica permite modificar ficheros PDF con firma digital
  • Tamagotchi para hackers: Flipper Zero
  • 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