Warning: Missing argument 2 for wpdb::prepare(), called in /home/stromber/public_html/kryptoblog/wp-content/plugins/wp-super-edit/wp-super-edit.core.class.php on line 109 and defined in /home/stromber/public_html/kryptoblog/wp-includes/wp-db.php on line 1222
Faktorisering av RSA-640 genomförd » Kryptoblog

Faktorisering av RSA-640 genomförd

November 9th, 2005 by Joachim Strömbergson Leave a reply »

Enligt en artikel på MathWorld har en grupp forskare i Tyskland lyckats med att genom faktorisering hitta det hemliga primtal som ligger till grund för RSA-640.

Primtalet i fråga är 193 siffror stort och ser ut så här:

310 7418240490 0437213507 5003588856 7930037346 0228427275 4572016194 8823206440 5180815045 5634682967 1723286782 4379162728 3803341547 1073108501 9195485290 0733772482 2783525742 3864540146 9173660247 7652346609

Enligt forskarna själva tog det totalt fem månader att genomföra faktoriseringen. Metoden man använde var Number Field Sieve. Här finns forskargruppens eget meddelande om faktoriseringen. I meddelandet beskriver man bland annat det system man använt:


Sieving has been done on 80 2.2 GHz Opteron CPUs and took 3 months.
The matrix step was performed on a cluster of 80 2.2 GHz Opterons
connected via a Gigabit network and took about 1.5 months.

RSA-640 är en av de deltävlingar som RSA Security har ställt upp i tävlingen The RSA Factoring Challenge. Det viktiga skälet till att RSA håller denna tävling är att faktorisering av produkten av två primtal är direkt överförbart till att försöka hitta den privata nyckeln i ett assymetriskt nyckelpar baserat på RSAs teknologi.

Forskargruppen har tidigare även vunnit tävlingen RSA-200, en tävling i att faktorisera, inte ett tal med 200 bitar utan ett tal med 200 siffror (något förvirrande namngivning av RSA-utmaningarna).

Även om ett 640 bitars primtal är mycket mindre än 1024, än mindre än 2048 har det gått relativt fort framåt vad gäller faktorisering av stora primtal. Kombinationen av snabba datorer och allt bättre parallella algoritmer ger imponerande resultat. Förhoppningsvis är det ingen som använder assymetriska nyckar som är mindre än 1024 bitar, om inte annat bör detta vara en väckarklocka om att det är hög tid att skaffa fler bitars marginal.

No related posts.

Related posts brought to you by Yet Another Related Posts Plugin.

Advertisement

3 comments

  1. Ett ännu större tal faktoriserades redan i maj i år, av samma grupp forskare. Det var ett tal med 200 decimala siffror, eller 663 binära.

    För RSA-640 tog sållningen, vilket är det mest tidskrävande steget, tre månader på 80 2.2 GHz Opteron-processorer. Som jämförelse uppskattades sållningen för RSA-200 till att ta 55 år på en ensam 2.2 GHz Opteron-processor, dock utfördes sållningen på olika sorters maskiner. Matrissteget utfördes på samma kluster och tog tre månader för RSA-200 jämfört med 1.5 för RSA-640.

  2. G says:

    Det är inte ett primtal som faktoriserats (det är trivialt att faktorisera primtal!). Det som faktoriserats är en produkt av två stora primtal. Vanlig felskrivning…

  3. Joachim says:

    Lina: Du har naturligtvis helt rätt. RSAs namngivning av utmaningarna varierar mellan att ange bitar och siffror, så jag tog för givet att RSA-640 var den utmaningen med störst antal bitar som knäckts. (Och så skall man läsa igenom ordentligt också 😉

    G: Helt korrekt påpekande, problemet är att hitta primtalen som använts som operander. Skall rätta till det och inte glömma bort det.

Leave a Reply

You must be logged in to post a comment.