N. 14:  RSA y los intentos para descifrarlo

§1  Bibliografía

  "Soluciones criptográficas en aplicaciones no dedicadas", de Julio Cesar Hernandez es una serie de dos artículos publicados en Byte Esp.  El primero, en el n.50 p.132. Contiene sendas tablas estadísticas de frecuencias de letras en castellano y en inglés.

"Sistemas de Clave Pública en Internet".  Por Miguel Catalina Gallego y Alvaro Begué Aguado.  PC World n.136 p.281.  Un artículo muy claro y didáctico sobre este método de seguridad en Internet. Incluye algunas referencias Webográficas.

En concreto da una explicación sobre el fundamento matemático del sistema RSA:

"El funcionamiento del sistema está en la teoría elemental de números, en particular en el teorema de Euler-Fermat.  Este teorema permite asegurar que al elevar un número entero entre 0 y N-1 a cierto número k y después tomar el resto de la división entre N, se llega al número inicial.  El truco es hacer la operación anterior en dos pasos.  El primero será la clave pública y el segundo la privada.  Para generar las claves, lo único que cuesta bastante tiempo de procesamiento es calcular dos números primos p y q grandes (unas cién cifras).  Para ello se suelen usar métodos probabilísticos, que permiten encontrar números que es muy probable que sean primos.  Entonces se toma N igual al producto p y q.  En este caso k=(p-1)(q-1)+1.

Conociendo k es bastante fácil deducir a partir de una de las claves cuál es la otra; pero para conocer k hay que saber cuanto valen p y q, para lo cual hay que descomponer N en un producto de dos primos. Esto puede parecer un problema sencillo, ya que N es público, pero si los número son grandes, los mejores algoritmos conocidos tardarían millones de años en resolver el problema.  En esto se basa la seguridad de RSA".

§2  La EFF y el sistema DES

Reproducimos el original inglés de la noticia por la que se anuncia el descifrado de este sistema de encriptación, basado en el sistema de clave pública RSA y utilizado por el Gobierno USA.

FOR IMMEDIATE RELEASE:

Tuesday, January 19, 1999 EFF's DES Cracker puts final nail in coffin of insecure government Data Encryption Standard RSA Code-Breaking Contest.

Again Won by Distributed.Net and Electronic Frontier Foundation (EFF) DES Challenge III Broken in Record 22 Hours RSA DATA SECURITY CONFERENCE, SAN JOSE, CA -- Breaking the previous record of 56 hours, Distributed.Net, a worldwide coalition of computer enthusiasts, worked with the Electronic Frontier Foundation's (EFF) "DES Cracker," a specially designed supercomputer, and a worldwide network of nearly 100,000 PCs on the Internet, to win RSA Data Security's DES Challenge III in a record-breaking 22 hours and 15 minutes.

The worldwide computing team deciphered a secret message encrypted with the United States government's Data Encryption Standard (DES) algorithm using commonly available technology.  From the floor of the RSA Data Security Conference & Expo, a major data security and cryptography conference being held in San Jose, Calif., EFF's DES Cracker and the Distributed.Net computers were testing 245 billion keys per second when the key was found.

First adopted by the federal government in 1977, the 56-bit DES algorithm is still widely used by financial services and other industries worldwide to protect sensitive on-line applications, despite growing concerns about its vulnerability.

RSA has been sponsoring a series of DES-cracking contests to highlight the need for encryption stronger than the current 56-bit standard widely used tosecure both U.S. and international commerce.  "As today's demonstration shows, we are quickly reaching the time when anyone with a standard desktop PC can potentially pose a real threat to systems relying on such vulnerable security", said Jim Bidzos, president of RSA Data Security, Inc.  "It has been widely known that 56-bit keys, such as those offered by the government's DES standard, offer only marginal protection against a committed adversary.  We congratulate Distributed.Net and the EFF for their achievement in breaking DES in record-breaking time.   "As part of the contest, RSA awarded a $10,000 prize to the winners at a special ceremony held during the RSA Conference.

The goal of this DES Challenge contest was not only to recover the secret key used to DES-encrypt a plain-text message, but to do so faster than previous winners in the series.  As before, a cash prize was awarded for the first correct entry received.  The amount of the prize was based on how quickly the key was recovered.  "The diversity, volume and growth in participation that we have seen at Distributed.Net not only demonstrates the incredible power of distributed computing as a tool, but also underlines the fact that concern over cryptography controls is widespread", said David McNett, co-founder of Distributed.Net".

EFF believes strongly in providing the public and industry with reliable and honest evaluations of the security offered by DES.  We hope the result of today's DES Cracker demonstration delivers awake-up call to those who still believe DES offers adequate security", said John Gilmore, EFF co-founder and project leader.  "The government's current encryption policies favoring DES risk the security of the national and world infrastructure.

"The Electronic Frontier Foundation began its investigation into DES cracking in 1997 to determine just how easily and cheaply a hardware-based DES Cracker (i.e., a code-breaking machine to crack theDES code) could be constructed.  Less than one year later and for well under U.S. $250,000, the EFF, using its DES Cracker, entered and won the RSA DES Challenge II-2 competition in less than 3 days, proving that DES is not very secureand that such a machine is inexpensive to design and build. "Our combined world-wide team searched more than 240 billion keys every second for nearly 23 hours before we found the right 56-bit key to decrypt theanswer to the RSA Challenge [III], which was 'See you in Rome (second AES Conference, March 22-23, 1999)'", said Gilmore.  The reason this message was chosen is that the Advanced Encryption Standard (AES) initiative proposes replacing DES using encryption keys of at least 128 bits.

RSA's original DES Challenge was launched in January 1997 with the aim of demonstrating that DES offers only marginal protection against a committed adversary.  This was confirmed when a team led by Rocke Verser of Loveland, Colorado recovered the secret key in 96 days, winning DES Challenge I.  Since that time, improved technology has made much faster exhaustive search efforts possible.  In February 1998, Distributed.Net won RSA's DES Challenge II-1 with a 41-day effort, andin July, the Electronic Frontier Foundation (EFF) won RSA's DES Challenge II-2 when it cracked the DES message in 56 hours.

EFF has prepared a background document on the EFF DES Cracker, which includes the foreword by Whitfield Diffie to "Cracking DES". See: www.eff.org.

  Inicio