Alex Holst wrote:
> IBM har åbenbart planer om at sælge lystigt ud af CPU tid på den nyeste
> udgave af Blue Gene. Oplysningerne indtil videre siger kr. 60.000 for at
> leje hele maskinen i en uge, men jeg har personligt mine tvivl om at
> sådan en lav pris er helt korrekt.
> Men hvis vi i det mindste antager, at virksomheder uden adgang til egen
> parallelcomputer nu let kan købe sig til CPU tid, hvad gør det så for
> muligheden i at brute-force sig igennem RSA/DSA nøgler med henblik på
> recovery eller tyveri?
> Er der nogen der tør gisne om hvad det så vil koste at brute-force sin
> vej igennem adgangskoder på RSA/DSA nøgler? Vælg selv bitstørrelse på
> nøglen og adgangskoden.
Urimeligt meget. Du kommer ikke uden om at du i RSA-tilfaeldet skal lave
unikke faktoriseringer over som minimum heltal (Z) (eller en anden ring
efter passende valg, saa vidt jeg husker). I DSA er det beregning af
diskrete logaritmer der goer udfaldet. Faelles for begge metoder er at
de kan goeres tilstraekkeligt modbydelige at regne paa til at en
parallel computer som udgangspunkt ikke kan knaekke dem. El-gamal (der
er en smuk kryptoalgoritme) baserer sig ligeledes paa diskrete
logaritmer. Dette var angrebet paa noeglen, som nok ikke er stedet at
angribe. Man kan lave perverse beregninger der giver et estimat paa hvor
lang tid det vil tage. Men laes nu videre ;)
Hvis angrebet gaar paa adgangskoden, staar du som regel med det problem
at du skal angribe en symmetrisk cipher saasom AES. Adgangskoden
benyttes saa til at dekryptere den private-key du egentlig har.
Naar man skal bryde en AES-cipher (eller en RSA/DSA cipher) saa kan man
godt antage at en parallel computer skalerer lineaert. I dette tilfaelde
multipliceres hastigheden derfor bare med en faktor baseret paa hvor
mange ens computere man kan saette igang. Men - hvis man kan gaa lidt
grummere til vaerks og kender noget til den konfiguration ens paralelle
computer har, saa er der tricks der goer at man i nogen tilfaelde kan
goere det vaesentligt hurtigere end en linear skalering.
Daniel J. Bernstein har et par interessante estimater, dog for en
specialbygget hardware:
http://cr.yp.to/snuffle/bruteforce-20050425.pdf
[DJB - Understanding Brute Force]
Det grundliggende her er at man skal tage sig i agt for at tro skidtet
skalerer lineaert. Man skal sandsynligvis vide en del mere om BlueGenes
konfiguration for at give et bud paa om den kan udnyttes til dette.
Hvis du imidlertid bare skal have en skalering der er lineaer boer man
overveje om det ikke er smartere at lade et zombie-netvaerk lave
arbejdet. Man kan eventuelt, alt efter morale og kriminalitetsniveau faa
yderligere hastighed ved at koble et saadant netvaerk sammen med BlueGene.