Cookies op Tweakers

Tweakers maakt gebruik van cookies, onder andere om de website te analyseren, het gebruiksgemak te vergroten en advertenties te tonen. Door gebruik te maken van deze website, of door op 'Ga verder' te klikken, geef je toestemming voor het gebruik van cookies. Wil je meer informatie over cookies en hoe ze worden gebruikt, bekijk dan ons cookiebeleid.

Meer informatie

Door , , 43 reacties
Bron: Slashdot

Op Slashdot viel te lezen dat een wiskundige met de naam Daniel Bernstein een methode heeft gevonden om zeer grote getallen zeer veel sneller te factoriseren dan tot nu toe mogelijk was. Deze wiskundige beweert - door in plaats van één computer met zeer veel geheugen, veel computers met een beetje geheugen te gebruiken - niet linear, maar exponentieel sneller de factoren van een groot getal te kunnen berekenen, terwijl de kosten voor de benodigde hardware niet toenemen.

Met deze techniek zouden getallen met een factor drie groter dan nu het geval is gefactoriseerd kunnen worden. Als dit waar is zouden RSA sleutels van 2048 bits - op dit moment vrijwel onbreekbaar geacht - gefactoriseerd kunnen worden. Een markant detail is dat er veel geruchten de ronde gaan dat de NSA al jaren van deze methode op de hoogte was. Overigens wordt de veiligheid van symetrische sleutel cryptografie (DES, AES) niet door deze ontdekking aangetast:

Encryptie - sleutel "Now that this technique is known it explains how the spooks may be able to break crypto everyone else believed was "unbreakable" if they had previously made this discovery. Remember what happened with DES. The NSA said "make these changes. We can't tell you why." IBM made the changes. 20 years later, when differential cryptography was "discovered", it turned out those changes made it more resistant to differential cryptography..."

Troublegum gooide dit nieuws in de nieuwssubmit. Bedankt

Moderatie-faq Wijzig weergave

Reacties (43)

Het werkt natuurlijk 2 kanten op, als een bericht al sneller gedecodeerd kan worden (eerst zien, dan geloven, die gast kan nog doodgaan en zijn methode mee het graf in nemen ;)) dan kan een bericht ook sneller ge-encodeerd worden, en dus kunnen we (veel) grotere keys gaan gebruiken.
Dat is niet altijd zo; sommige algoritmen laten zich net zo snel encoderen als decoderen, sommige doen er langer over om te encoderen dan te decoderen (anders is een DivX-filmpje kijken lang niet zo leuk meer ;))
Lijkt me nauwelijks van toepassing. Het maken van zo'n sleutel ging sowieso al vele vele malen sneller dan het factoriseren. Het maken van zo'n sleutel is een recht-toe-recht-aan-proces, terwijl het kraakproces nog steeds vrijwel een brute-force methode is.

Maar we kunnen eenvoudig grotere sleutels gebruiken, klopt. We moeten alleen 'onze' inschatting van 'hoe groot moet een vrijwel onkraakbare sleutel zijn' aanpassen.
Met recht opzienbarend nieuws! Als het waar is zou het koetjes project (RC-5) dat nog steeds graast naar een sleuteltje van 64 bits geheel achterhaald zijn.
Gek genoeg lijkt de methode van Bernstein zich overigens juist perfect te lenen voor een gedistribueerde aanpak. Een programma dat niet één super pc vereist, maar vele zwakkere met een relatief kleine memory footprint is ideaal voor voor een geheel vernieuwd koetjes project.
Het RC5-64 project is de meest primitieve manier van het sleutel kraken (ik doe hier overigens vrolijk aan mee:-) aangezien gewoon domweg alle sleutels geprobeerd worden (=brute force methode).
Wat al langer toegepast wordt is het op wiskundige wijze kraken van een code. Het voorbeeld van dit artkel is er hier weer 1 van.
Als je goed doorleest, merk je dat dit resultaat slechts voor de limiet van zeer grote sleutels geldt. Het is heel goed mogelijk (merkt Bernstein zelf ergens op) dat het voor de huidige 1024/2048 bit sleutels geen enkel verschil maakt (of zelfs nadelig is).
+3 (Interessant)

Of gewoon een betere c.q aandachtigere lezer dan de rest. ;)
Hmmm... het kan ook een totaal ander verhaal zijn. Voer voor de paranoiden onder ons:

Stel NSA en die Daniel Bernstein kunnen al jarenlang met deze techniek berichten decoderen maar dat mensen als Phil Zimmerman hier niet van op de hoogte zijn.

Resultaat: PGP en aanverwante proggies worden als veilig gewaand en veel gebruikt, kijk naar Al Qaeda - die schijnt het ook intensief gebruikt te hebben. Ondertussen kijken de NSA lekker mee met die informatie.

Ze kunnen niet met de gevonden informatie naar buiten treden. Immers, daarmee geven ze direkt toe dat ze de encryptie hebben doorbroken. Is niet tactisch, je kunt beter de vijand in de waan laten dat ze een perfecte encryptie gebruiken en ondertussen lekker meelezen.

Wat hebben ze dan aan die informatie? Eenvoudig, het zet de NSA op een spoor - vergelijk het met de anonieme tipgever. Via dat spoor komen ze 'toevallig' ook andere onderwerpen tegen en bouwen dan op een zodanige wijze hun bewijsvoering op dat de hele decoderings-geschiedenis kan worden vergeten.

Dat lijkt me helemaal geen ondenkbare situatie. Maar waarom dan ineens deze wijziging? Mogelijk is die Daniel Bernstein gewoon geniaal en heeft een nieuwe methode gevonde en deze meteen aan de grote klok gehangen. Kan.

Mogelijk dat de NSA via hun decryptie methodiek informatie heeft ontdekt waarbij ze op geen enkele manier kunnen verdoezelen dat ze onkraakbaar geachte data hebben gedecodeerd. Het is natuurlijk niet tactisch voor de NSA om zelf te vertellen dat ze dergelijk goed gecrypte code kunnen decoderen want daarmee zouden ze de vijand meteen ongelovelijk op scherp zetten. Dus dan maar een geniaal wiskundige inzettend die zich hier wel voor wil lenen.

Resultaat is dat de publicatie een feit wordt. Enige tijd later zal de NSA komen met informatie waar ze al enige tijd mee in hun maag zitten.

Ondertussen gaan terroristen en anderen die gecrypte communicatie hebben gevoerd, zich afvragen of NSA alle gecrypte documenten hebben onderschept en nu gaan decoderen. Vast wel...

Welkom in de Brave New World.
Euh.. cpu kracht is toch belangrijker dan een hoeveelheid geheugen? Meer pc's is uiteindelijk meer cpu kracht. Of snap ik het nou niet?
misschien werkt het op basis van uitsplitsen van processen. Jouw proc kan nog steeds maar 1 proces doen.... welliswaar heel snel als je heel veel rekenkracht hebt. Maar als je een heleboel computers iets heel makkelijks laat doen, door die truck van hem dus... zou dat misschien het collosale verschil kunnen zijn.
Dus als je nu DUAL CPU draaid heb je eigenlijk het zelfde...

als je dan de "echte" IBM servers ziet

512x P3 550Mhz XEON CPU's hebt met 2mb L2 cash en 64Gb ram denk ik dat als je 512
losse P3 550 Xeons met 2Mb pakt toch echt slomer is dan de eerste config...

Simpel anders moet je ook 512x Win2k Advanced server Bv. draaien...

512x!!! anders maar 1keer en je hebt 512 instrukties die hij kan bewerken tegelijkertijd...
Ik denk dat je je daarin nog wel enorm kan vergissen.

Bij systemen met een dergelijk groot aantal processoren komen ook hele andere factoren om de hoek kijken waar je bij simpele dual/quad processor systemen geen problemen mee hebt. Om maar een voorbeeldje te noemen, alle cpu's van data voorzien, de verdeling van geheugen over de cpu's. De overhead zou op een bepaald moment een dusdanig grote component van de processorkracht kunnen gaan vormen dat het toevoegen van processoren het geheel alleen maar trager maakt.
Ik zeg niet dat dit per definitie zo is voor het genoemde voorbeeld, maar ik wil je er wel even op wijzen dat brute specs niet alles zeggend zijn.
Dus als je nu DUAL CPU draaid heb je eigenlijk het zelfde...

als je dan de "echte" IBM servers ziet

512x P3 550Mhz XEON CPU's hebt met 2mb L2 cash en 64Gb ram denk ik dat als je 512
losse P3 550 Xeons met 2Mb pakt toch echt slomer is dan de eerste config...

Simpel anders moet je ook 512x Win2k Advanced server Bv. draaien...

512x!!! anders maar 1keer en je hebt 512 instrukties die hij kan bewerken tegelijkertijd...
Zal niet lukken met w2k advanced server, daar kan je er maar 16 (of 32) mee aansturen.

Met datacenter kom je er wel, 512 cpu's.
De huidige methode heeft een gigantische hoeveelheid geheugen nodig om grote getallen te factorizeren. In de Factoring Challenge FAQ van RSA Laboratories staat een klein tabelletje met hoeveel machines (vergelijkbaar met een pentium 500) en geheugen er nodig zijn voor het factorizeren van sleutels met verschillende lengtes in 1 jaar als je de huidige methode gebruikt:

Bits in de sleutel______# machines______geheugen
___430______________________1_________weinig
___760_________________215000_________4GB
__1020______________342000000_______170GB
__1620______________1.6 * 10^15_______120TB

het geheugenaantal is dus per machine, en niet totaal :)
Ja idd, enkel moet je als je aan het 'rekenen' bent ook dingen in je geheugen opslaan en daarvoor is veel geheugen nodig vooral bij het trachten te kraken van code moet je heel veel onthouden.
Dus je moet genoeg geheugen hebben om alle 'tussen' berekeningen te onthouden en CPU power is nog even belangerijk voor het snel uitvoeren van het kraken enkel zonder genoeg geheugen dus veel geheugen kun je alles niet opslaan dus gebruik je niet alle power!
het zou niet best zijn als dit zou werken, dan moeten er nieuwe enctypie methoden bedacht worden.
Nee hoor, alleen langere codeersleutels.
Als er bedrijven zijn die hier allang van op de hoogte waren, dan zijn vast ook wel technieken om het betere te encrypten
Is dit niet wat wij nu ook al doen! met je }:O ?
nee

De RC5-64 contest van distributed.net heeft niets met het factorizeren van sleutels te maken. Bovendien is de methode van distributed.net brute force, dwz dat ze simpelweg alle mogelijkheden proberen tot de goeie is gevonden

En het factorizeren van sleutels is ook wel brute force te doen, maar dat kost echt veel teveel tijd (denk aan iets dat velen malen langer duurt dan de leeftijd van het universum :) )
hm jah lijkt er wel op..eigelijk wel een beetje weird dat dit nu wordt gezegd want et was toch al wel eerder duidelijk dat als je 100.000 computers gebruik dat altijd sneller is dan één supercomputer... wat dat betreft is er geen zupah bakkie die tegen alle }:O van NL kan.. alleen zoals je in de progressbar kan zien op distributed gaat et niet echt snel ofzo.. uiteindelijk wordt de key wel gekraakt.. maar of je dat écht gekraakt kan noemen..tis eigelijk net zoiets als een titanuimslot met een nagelvijl doorvijlen :Z
titanium is helemaal niet zo hard hoor dus als je een beetje een goeie nagelvijl hebt kom je wel een heel end gok ik. :*)
hmm, hier wil ik wel meer over horen, lijkt me sterk dat ze daar niet eerder aan zouden gedacht hebben.
gewoon zijn paper lezen, is best te doen. Ik zit nu op pagina 5 :)
Is dat te openen met Ghostviewer? Of waaranders mee?
Jep, gezien het een PostScript file is kan je het openen met Ghostview.

Voor hen die het nog niet kennen of hebben, je kan het downloaden op http://www.cs.wisc.edu/~ghost/
Da's lekker.... :(
Dus al die tijd konden ze toch mijn 1024 bits encrypted emails lezen die ik aan m'n moeder stuurde....
Dan wil ik niet weten wat jij in die e-mails naar jouw moeder schreef als je 1024bits encripty nodig hebt (je vriending alla ;) )
"ma check ff me online banksaldo"
"> inlogcode?"
"234243242"
"> ok"
"tis maar goed dat mijn encryptie secure is :)"
De 3-8-6 en de 4-8-6 kommen weer helemaal terug :) dalijk wil iedereen mijn 486 afpakken...

Ik bescherm je liefie :) jij mag lekker blijven serveren voor Stefan :)

Nee alles goed en aardig, wiskunde blijft oplosbaar en als je de regels goed gebruikt kan iets wat heel moeilijk lijkt, door een algoritme makkelijk oplosbaar zijn.

Met koude kernfusie, zie fok! wordt de wereld in 1 dag toch een stuk beter. Opeens gaat iedereen meehelpen aan nuttige dingen vaccins ontwikkelen voor ziekten bevoorbeeld, want als die RC• binnen een aantal dagen gekraakt is, dan is lang en breed bewezen dat het te kraken is.
Dat van die koude kernfusie moet ik nog zien, er zijn al genoeg wetenschappers geweest die hetzelfde beweerden en het fout hadden.
wiskunde blijft oplosbaar
Je kunt met wiskunde ook bewijzen dat sommige dingen onoplosbaar zijn! Ik weet niet precies wat je probeert te zeggen, maar ik denk dat je het iets te simplistisch probeert voor te stellen (8>
Ik denk dattie "Wiskunde blijft beantwoordbaar" bedoelde met dat.

Op dit item kan niet meer gereageerd worden.



Apple iOS 10 Google Pixel Apple iPhone 7 Sony PlayStation VR AMD Radeon RX 480 4GB Battlefield 1 Google Android Nougat Watch Dogs 2

© 1998 - 2016 de Persgroep Online Services B.V. Tweakers vormt samen met o.a. Autotrack en Carsom.nl de Persgroep Online Services B.V. Hosting door True