Re: [FYI] (Fwd) BXA Press Release on New Regs

[Matthias Bauer <bauer@informatik.uni-erlangen.de>]

Hi,
> > "up to 1024 bits" ?? Das koennen die doch nicht Ernst meinen...
> 
> Reality Check: das groesste Problem beim Faktorisieren ist der enorme
> RAM-Bedarf im zweiten Schritt. Leider hat kein Mensch den
> Mathematikern erzaehlt, dass die 2 GB RAM, die man zum Faktorisieren
> eines 512-bit Keys braucht, heutzutage fuer kleines Geld im Laden zu
> kaufen sind.
> 
> Leider hat sich auch die Tatsache, dass ein 1024-bit-Key nur 2.800 mal
> so schwierig zu faktorisieren wie ein 512-bit-Key ist, noch nicht
> wirklich herumgesprochen.
Humhum, gemach gemach! Beim Faktorisieren mit Number Field Sieve
oder QFS oder einem anderen Siebverfahren eben hat man nach dem 
vorzugsweise verteiltem Verbasteln von verdammt vielen
Gleichungen das Problem, dass man die alle speichern muss, aber das
ist nicht das, was irgend jemanden davon abhaelt, schnell mal alle
Keys auf dem Keyserver zu brechen. Man muss in diesen Gleichungen
lineare Abhaengigkeiten finden und das laeuft auf sowas wie Gausssche
Elimination auf schwach besetzten Matrizen raus (Wiedemann Algorithmus
oder modifizierter Lanczos Block Algo).  Die Komplexitaet davon ist
mindestens quadratisch, egal wie viel Speicher man drauf wirft. Ausserdem
lassen sich solche Matrix-Algorithmen nur schwer parallelisieren.
Das erklaert auch, warum fuers Faktorisieren der RSA-140 Challenge 2000
MIPS-Jahre und fuer RSA-155 8000 MIPS-Jahre noetig waren. Die haben
nicht vergessen, genuegend Speicher einzukaufen, die hatten grosse
Gleichungssysteme zu loesen.
Lag mir grad am Herzen...

Sch"onen Tag noch

Matthias