Onderzoekers factoriseren RSA-768-getal

Ehm, nee. Dat is pertinent niet waar.

Ze hebben een sleutel, die als challenge gepost was, gekraakt. Dat is indrukwekkend, maar heeft geen enkel gevolg voor alle andere sleutels die in gebruik zijn, en ieder gewoon mens kan met een gerust hart RSA-768 blijven gebruiken.

Uh nee, zo werkt RSA niet.

Zie voor het (openbare) algoritme: http://en.wikipedia.org/wiki/RSA

Ze hebben van 1 RSA key van 768-bit length dus de bijhorende twee priemgetallen gevonden. Ze hebben dus 2,5 jaar nodig gehad om 1 key te breken, wat volgens mij aangeeft dat de keys nog redelijk veilig zijn. (Als je een andere key wilt doen, kost dat je ook zo rond de 2,5 jaar dan.)

Er bestaat niet zoiets als een 'master sleutel' voor alle RSA sleutels. Dat zou het algoritme nogal kwetsbaar maken, laat staan onbetrouwbaar, aangezien je nooit kan weten of zo'n sleutel nou echt nog geheim is of niet.

[Reactie gewijzigd door Arcanedevil op maandag 11 januari 2010 12:12]

Overigens gebruikt vrijwel iedereen RSA-1024. Uitgaande van een beetje gelijkmatige spreiding van priemgetallen, kun je stellen dat:

als RSA-768 in 2,5 jaar te kraken is dan, uitgaande van dezelfde hardware, ...

duurt RSA-769 ongeveer 5 jaar
duurt RSA-770 ongeveer 10 jaar
duurt RSA-771 ongeveer 20 jaar
...
duurt RSA-1024 ongeveer... eh 2,5 * 2^256... jaar.

Nee, zo werkt dat niet; één bit toevoegen aan de key betekent niet dat het aantal berekeningen om de key te kraken verdubbelt, dat is alleen (ongeveer) zo voor bepaalde symmetrische ciphers.

Van Wikipedia:

In cryptography, key size or key length is the size (usually measured in bits or bytes) of the key used in a cryptographic algorithm (such as a cipher). An algorithm's key length is distinct from its cryptographic security, which is a logarithmic measure of the fastest known computational attack on the algorithm, also measured in bits. The security of an algorithm cannot exceed its key length (since any algorithm can be cracked by brute force), but it can be smaller. For example, Triple DES has a key size of 168 bits but provides at most 112 bits of security, since an attack of complexity 2¹¹² is known.

Door één bit aan een RSA key toe te voegen gaat de key length met één omhoog, maar de cryptographic security gaat met een stuk minder omhoog, zoals ik wat verderop zal laten zien.

Het Wikipedia artikel gaat als volgt verder:

This property of Triple DES is not a weakness provided 112 bits of security is sufficient for an application. Most symmetric-key algorithms in common use are designed to have security equal to their key length. No asymmetric-key algorithms with this property are known; elliptic curve cryptography comes the closest with an effective security of roughly half its key length.

Wat al suggereert dat één bit extra key length minder dan één bit cryptographic security genereert (RSA is een asymmetric-key cipher).

De cryptographic security van RSA is ongeveer sqrt(ln(2^k)*ln(ln(2^k)))/ln(2) bits, voor RSA sleutels van k bits. (bron: Fundamentals of Cryptology - het boek gebruikt overigens niet alle truukjes om de rekentijd te verkorten, dus dit geeft nog een optimistische schatting van de cryptographic security; deze RSA pagina geeft een paar waarden van ongeveer 25% bits minder. Maar dat is geen ramp voor deze uitleg)

Uitgaand van bovenstaande formule heeft een 768-bit RSA key een cryptographic security van 83.40 bits, en 769-bit RSA 83.46 bits. Dat betekent dus dat het toevoegen van één bit aan een 768-bit RSA key slechts 2^0.06 - 1 = 0.04 = 4% extra benodigde rekentijd toevoegt. Om de benodigde rekentijd te verdubbelen moet je van een 768-bit key naar een 784-bit key gaan.

1024-bit keys hebben een cryptographic security van 98.48, wat een vooruitgang is van 98.48 - 83.40 = 15.08 bits. Het kost dus ongeveer 2¹⁵ = 32768 keer zoveel rekenkracht om een 1024-bit key te kraken t.o.v. een 768-bit key.

Hier begin je trouwens wel te merken dat mijn formule voor de cryptographic security niet 100% nauwkeurig is; In het artikel staat dat ze verwachten RSA-1024 binnen 10 jaar te kraken. In 10 jaar tijd is de rekenkracht ongeveer een factor 1024 toegenomen (uitgaande van een verdubbeling per jaar), geen factor 32768. Maar om duidelijk te maken dat de relatie tussen key length en cryptographic security voor RSA niet lineair is, is het goed zat

edit:
Ah, tweaker ProfPi heeft verderop in deze discussie een link gepost naar de paper die beschrijft wat ze gedaan hebben om de RSA-768 modulus te factoriseren.

Uit de paper:

The number RSA-768 was taken from the now obsolete RSA Challenge
list [37] as a representative 768-bit RSA modulus (cf. [36]). This result is a record for factoring general integers. Factoring a 1024-bit RSA modulus would be about a thousand times harder [...]

Dat maakt mijn schatting van "een factor 1024 meer" aardig in de buurt, en bevestigt nog meer dat mijn formule voor de cryptographic security van RSA niet 100% toereikend is.

[Reactie gewijzigd door deadinspace op maandag 11 januari 2010 20:43]

SSL zoals het origineel bedacht was, is inmiddels overal vervangen door TSL (Transport Layer Security), en deze maakt gebruik van 1024bit of 2048 bit RSA keys welke momenteel respectievelijk 15 miljoen en 225 miljoen jaar om te kraken met behulp van een enkele pc

1024 bits zit in je client certificaat, 2048 is voornamelijk voor certificate authorities (CA's)

Nee het is dus juist niet uitermate veilig. Dat is het gehele punt. 2.5 jaar is in de encryptie wereld namelijk helemaal niks. Er zijn zat berichten waarvan je niet wilt dat ze ooit in jouw levensloop openbaar komen. Denk aan militaire documenten, bank geheimen e.d. Dit soort berichten mogen nooit binnen 2.5 jaar gekraakt worden (ja ik weet dat je dit soort dingen met een symmetrische encryptie doet en dat RSA asymmetrisch is, het gaat even om het punt). Daarom is dus ook het advies om over te stappen naar bijvoorbeeld 1024 bits.