Hilversumse wiskundige krijgt lintje voor onderzoek naar priemgetallen

De Wiskundige Herman te Riele is vrijdag tot Officier in de Orde van Oranje-Nassau benoemd voor zijn wetenschappelijk onderzoek naar priemgetallen en cryptografie bij het Centrum Wiskunde & Informatica. Hij kraakte onder andere de RSA-155 code.

Te Riele doet al sinds 1971 onderzoek naar priemgetallen en cryptografie bij het CWI in Amsterdam, zo meldt de organisatie zelf. Een van de belangrijke wapenfeiten van de wiskundige was de weerlegging van het vermoeden van Mertens uit 1897. Door de weerlegging van Te Riele en Andrew Odlyzko in 1985 werd duidelijk dat het vermoeden niet gebruikt kon worden om de Riemann-hypothese te bewijzen. Deze hypothese is een van de zeven belangrijke onopgeloste problemen in de wiskunde.

De wiskundige kreeg ook bekendheid met zijn werk bij de kraak van de RSA-155 code van 512bit, in 1999. Te Riele leidde het team dat de code succesvol wist te factoriseren in priemgetallen. Ook RSA-140 van 463bit ging het team eerder dat jaar succesvol te lijf. Na een diensttijd van 41 jaar bij het CWI, dat voorheen het Mathematisch Centrum heette, gaat hij per 1 januari 2012 met pensioen. Te Riele kreeg het lintje vrijdag uitgereikt door burgemeester Pieter Broertjes van Hilversum, de woonplaats van Te Riele.

Reacties (41)

[Verwijderd]

Netjes! Een soort John Nash van eigen bodem

Eindelijk iemand die een lintje overduidelijk verdiend en niet omdat hij zoals diverse bekende Nederlanders alleen maar met het (zonnebank bruin) hoofd op tv de avond loopt vol te blèren.

Edit: Volgens (Prof. M. Du Sautoy in) een docu van BBC Horizon was er een soort verband zichtbaar tussen priemgetallen en de Rieman-hypothese, indien je een kogeltje tegen een glazen bol aan gooit, geven de microfoons eronder een amplitude weer (qua geluidsgolf), welke sterk verwant is aan de (ζ) verdeling in de Rieman-reeks. Dat maakt deze hypothese i.c.m. prime-numbers alleen maar mysterieuzer...

Docu kon ik even niet vinden met het fragment, maar hij heeft schijnbaar ook zelf een podcast gemaakt hierover: http://www.youtube.com/watch?v=bo82tQO4j5E

[Reactie gewijzigd door Verwijderd op 23 juli 2024 21:44]

[Ted_W]

Proficiat !!

Ik vraag me altijd af of een slimme manier van oplossen het zal blijven winnen van brute force methode m.b.v. steeds snellere computers.

[bwerg]

De benodigde rekenkracht voor de meeste beveiligingsalgoritmen gaat exponentieel omhoog. Tegenwoordig is een 512bit RSA-sleutel prima te brute-forcen, maar het kraken van een 8192 bit sleutel duurt waarschijnlijk 100.000 jaar (gokje, mogelijk langer). Heel leuk dat een computer over een tijdje misschien honderd keer zo snel is, maar dan duurt het nog steeds 1000 jaar. Een algoritme dat te brute forcen is is dus sowieso als zwak te bestempelen, en algoritmen die écht niet te brute forcen zijn, zitten wel goed. Of de rekenkracht van computers moet ook nog een tijdje flink exponentieel blijven groeien, maar ik vraag me af hoe lang we dat nog kunnen blijven doen.

Grappig om te zien dat 512bit-RSA al 12 jaar geleden gekraakt was, en dat het nog steeds door moderne OS'en wordt geaccepteerd. Shame on you, windows en consorten. En natuurlijk ook niet best van degenen die deze sleutels nog maken...

[Reactie gewijzigd door bwerg op 23 juli 2024 21:44]

[curry684]

Grappig om te zien dat 512bit-RSA al 12 jaar geleden gekraakt was, en dat het nog steeds door moderne OS'en wordt geaccepteerd. Shame on you, windows en consorten. En natuurlijk ook niet best van degenen die deze sleutels nog maken...

Je gaat voorbij aan het beginsel wat je zelf omschrijft - dat de bruteforcetijd ook relevant is voor de bruikbaarheid van een sleutel. Als een algoritme 'compromised' is waardoor de bruteforce 'halfwaardetijd' dik afneemt hoeft het algoritme nog niet afgeschreven te zijn, het kan op andere manieren ingezet worden of op plaatsen waar het simpelweg niet lang genoeg gebruikt wordt.

Als praktijkvoorbeeld: toen WEP compromised was werd WPA bedacht. Is intern exact hetzelfde, maar genereert zelf om de paar minuten een nieuwe WEP-key. Leuk dan dat je met een dagje data afluisteren WEP kunt kraken, behalve dat je inherent maximaal 5 minuten kunt afluisteren voor de key verlopen is.

[bwerg]

Klopt, maar dan moet je wel voorzichtig zijn waar je die keys dan accepteert. 512bit RSA wordt ook voor PKI-certificaten gebruikt, en dat is toch echt inherent onveilig. Een gehele ban op een algoritme is inderdaad zinloos maar dat kunnen makers van OS'en en browsers dan ook niet afdwingen.

Ik had eigenlijk moeten zeggen: Slecht dat het 12 jaar geleden gekraakt was, en nog steeds gebruikt wordt voor langdurige en belangrijke communicatiekanalen.

[Reactie gewijzigd door bwerg op 23 juli 2024 21:44]

[Yoshi]

grappig vind ik het ook... Ik zou vooral de gezichten willen zien van zowat 3/4 van computergebruikers als sites die ze willen gebruiken niet meer werken (waaronder overheden btw) gewoonweg omdat bepaalde mensen te lui, te laks of weet ik veel zijn...

Dit ligt niet alleen aan de os ontwikkelaars (weliswaar ook mede door hun) maar aan heeeeeel veeeeeel mensen...

[bwerg]

Als de grote OS'en geen onveilige methodes (zoals 512bit RSA) meer zouden accepteren, dan zouden de verstrekkers van certificaten e.d. als de bliksem overstappen naar betrouwbare producten, niemand zou hun keys immers meer willen hebben. De thuisgebruiker valt niets te verwijten, controleren of alle versleutelingen die je gebruikt wel veilig zijn kost veel tijd, is voor de meeste mensen onbegrijpelijk en bovendien zou het niet nodig moeten zijn.

[TD-er]

Tegenwoordig is een 512bit RSA-sleutel prima te brute-forcen, maar het kraken van een 8192 bit sleutel duurt waarschijnlijk 100.000 jaar (gokje, mogelijk langer). Heel leuk dat een computer over een tijdje misschien honderd keer zo snel is, maar dan duurt het nog steeds 1000 jaar.

1000 jaar klinkt heel lang, maar zet er een botnet op van 1 miljoen computers en je hebt het ruw geschat binnen 8 uur gekraakt.

En grappig dat je begint over die 512 bit sleutels.
Bericht van pak 'm beet een maand geleden

[bbob]

Als er geen slimme manier van oplossen meer is wil het zeggen dat je een perfecte encryptie hebt die idd alleen door bruteforce op te lossen is.

Maar het blijkt steeds weer dat er in veel encrypties kleine foutjes zitten en deze foutjes maakt het mogelijk om binnendoor te gaan om de boel te kraken. Bij sommige encrypties zijn ze nog niet gevonden, misschien komt het ooit of misschien nooit.

[Stannieman]

Het probleem met brute force is dat als de computers het aankunnen om te brute forcen, de sleutel gewoon langer gemaakt wordt, waardoor de brute force tijd opnieuw omhoog gaat.

Vergelijk het met een codeslot van 4 cijfers. Als jij om één of andere reden zo snel bent dat je alle 10000 combinaties in 5min kan nagaan, hoeft er alleen een cijfer bijgezet te worden. Er zijn dan opeens 10x zoveel mogelijkheden waardoor je gemiddeld 10x zolang bezig bent.

[Verwijderd]

Inderdaad, en dan moet je ook nagaan dat encryptiecodes natuurlijk niet alleen van een 10-cijfers digit uitgaat, maar hier ook een hele reeks unicode characters bij betrokken is.

Dan is het geen 10^4 meer, maar - bij wijze van, het zijn er veel meer - 200^4, doe daar dan een extra digit bij en je krijgt 200^5. Zelfde principe, maar natuurlijk vele malen groter dan in jouw voorbeeld.

Dit is ook de regel voor wachtwoorden, hoe langer, hoe beter.
Sterker nog, een wachtwoord kan beter een eenvoudig te onthouden (dus dat je hem niet ergens noteert!) zinnetje of regeltje zijn met vele characters, dan een kort maar moeilijk wachtwoord.

LookAtMyHorseItIsAmazing is veiliger dan "Horse#12", om maar een voorbeeld te noemen, maar val niet in de kuil van 'standaardzinnetjes'. Zo heeft 'password' meer characters dan 'pass#1' en zijn vergelijkbare scenarios te bedenken voor zinnetjes, maar password wordt natuurlijk eerder geraden wegens t veel voorkomen ervan.

Anders wat, kan iemand aanvulling geven over de betrekking van priemgetallen?
Olaf is helaas wat terughoudend geweest met deze informatie, ik kan weinig interessants uit dit artikel terughalen erover. En dan doel ik met name op de hypotheses van genoemde historische figuren, en de bijbehorende weerleggingen.

[Reactie gewijzigd door Verwijderd op 23 juli 2024 21:44]

[bwerg]

Inderdaad, en dan moet je ook nagaan dat encryptiecodes natuurlijk niet alleen van een 10-cijfers digit uitgaat, maar hier ook een hele reeks unicode characters bij betrokken is.

Dan is het geen 10^4 meer, maar - bij wijze van, het zijn er veel meer - 200^4, doe daar dan een extra digit bij en je krijgt 200^5. Zelfde principe, maar natuurlijk vele malen groter dan in jouw voorbeeld.

Hoe je je getallen ook uitleest, het blijven gewoon bits hoor, en daarmee altijd 2^x. met gebruik van characters i.p.v. hexadecimale cijfers of bits laat je x gewoon sneller toenemen (wat trouwens op hetzelfde neerkomt als een hoger grondtal). Doorgaans wordt er vaak helemaal geen selectie gemaakt in welke bitcombinaties wel en niet worden gebruikt, ze worden gewoon allemaal gebruikt. Voor wachtwoorden e.d. worden er natuurlijk wél alleen makkelijk in te typen characters gebruikt, maar encryptiesleutels voert een gebruiker toch niet met zijn toetsenbord in.

[Reactie gewijzigd door bwerg op 23 juli 2024 21:44]

[supersnathan94]

het ging ook helemaal niet om bits, maar om de mogelijke combinaties van letters, getallen en andere tekens. en dat dan voor 5 posities. dat kunnen er dus makkelijk 200 of meer zijn.

[.oisyn]

Het gaat helemaal niet om tekens. Denk je echt dat zo'n 512 bits RSA sleutels is opgebouwd uit leesbare tekens? Natuurlijk niet, het is gewoon een getal van 512 bits. Door een getal te nemen wat 1 bit langer is heb je al 2x zoveel mogelijkheden. Maar ze voegen niet slechts 1 bit toe, ze verdubbelen meestal het aantal bits. Een 1024 bits getal heeft 2⁵¹² meer mogelijkheden dan een 512 bits getal - het kwadrateerd dus op die manier.

[taeke18]

ze kunnen het wel omzetten naar trits maar dan moet je hele andere systemen gebruiken

[Hoopje]

Het is wel degelijk gemiddeld tien keer zo lang. Je moet namelijk ook in de oude situatie de gemiddelde tijd nemen. In de oude situatie had je na gemiddeld 5000 pogingen de juiste te pakken, in de nieuwe situatie na gemiddeld 50000 pogingen, dus 10x zo veel.

[Darkstriker]

Deze redenering slaat natuurlijk nergens op.

Als het wachtwoord/code compleet random is dan zou je statistisch naar gemiddeld 50% van de gevallen gepobeerd te hebben het antwoord hebben.
Echter kan je niet afzonderlijk eerst kijken wat de geode combinatie is voor de eerste vier en dan die combinatie met de 10 mogelijkheden voor de 5e proberen. Dat is natuurlijk onzin.
Je moet elke combinatie van die vier uitprobere met elke van die 5 om aan de goede sleuten te komen an dan wordt het aantal gevallen due tien keer groter en de gemiddelde tijd voor de kraak zal nog steeds net zo met een factor 10 stijgen.

Jij maakt de redeneringsfout daarbij dat je aanneemt dat je voor het vinden van de eerste vier cijfers niet het gemiddelde nodig hebt maar het maximale (wat natuurlijk ook niet klopt). Het gemiddelde zal wel degelijk met een factor 10 groter worden. En de redenering dat een brute force bij 0 begint is natuurlijk ook niet altijd goed. Hij kan best bij 7 beginnen en toevallig doorgaan of bij 4 beginnen en richting 0 gaan en dan van 9 tot 5. Dat is iets wat je ook totaal niet meeneemt.

Meer digits toevoegen zal dus voor een behoorlijke tijd een oplossing blijven. Op bepaald moment worden wachtwoorden dan te lang om te onthouden maar papier kan voor zover ik weet niet gehackt worden en heb je daar dus nog altijd een stevige oplossing ookal moet je wachtwoord 100 tekens zijn. Alleen wordt het dan wat onhandig.
Dan komen we bij vingerafdrukken en die zijn uniek aan de mens en je kan die met duizenden meetpunten meten en dus weer een behoorlijke tijd door met je vinger als wachtwoord. Daarna misschien met je DNA maar tegen die tijd zijn wij allemaal al lang dood en wellicht dat na zoveel jaar onze overgrootkinderen armoede en hebzucht hebben overkomen en a la Star Trek het melkwegstelsel verkennen.

[Reactie gewijzigd door Darkstriker op 23 juli 2024 21:44]

[supersnathan94]

vinger als wachtwoord is niet handig. er zijn hele simpele methodes waardoor je je vingerafdruk kan verwijderen. zelfs met een zak appels kan het nog. het kopieren van iemand anders zijn afdruk in silliconen is ook niet erg moeilijk. je hebt alleen de juiste spulletjes nodig en die zijn gewoon op internet te halen.

[centr1no]

Ik dacht ik google even "het vermoeden van Mertens" uit nieuwsgierigheid.
Man
Ik vind dat je al een lintje zou moeten krijgen als je alleen al snapt wat er staat.
Respect voor deze meneer.

[AugmentoR]

Het principe is best wel simpel (zoals de meeste moeilijke wiskundige stellingen Er is een functie F(n) (de Mertens functie) die, volgens Stieltes in 1885, áltijd tussen de -1 en 1 blijft voor iedere n.

Onze te Riele heeft in 1985 (samen met ene Odlyzko) bepaald dat de stelling érgens niet opgaat, en in 2006 bepaald dat deze in ieder geval bóven de 10^14 moet liggen...

Pinz heeft overigens in 1987 al bewezen dat deze ónder de 3*10^64 moet liggen, dus de gezochte n kan nog wel even op zich laten wachten.....

Deze is wel (een beetje) verhelderend: http://mathworld.wolfram.com/MertensConjecture.html

[Reactie gewijzigd door AugmentoR op 23 juli 2024 21:44]

[Joppiesaus2]

Ik kan er naast zitten, maar die brute force waar ted_W het over heeft is zeker een heel belangrijke factor in het breken van codes wanneer quantum computing realiteit wordt. Ik meen dat de kracht van quantum computing is dat deze zeer veel lookups kan doen per seconden, veel meer dan een klassieke computer ooit kan. Dit kan belangrijk zijn bij het kraken van codes.

[kaas-schaaf]

Het voordeel van quantum computing is vooral het probleem van integer factorisatie. Het algoritme van Shor kan met ~ 300 qbits geimplementeerd worden welke polynomiaal (behoorlijk) sneller is dan de brute force manier.
Omdat veel encryptie/hashing van integer factorisatie gebruik maakt geeft dit dus problemen met die algoritmes.

Er zijn overigens genoeg encryptie alternatieven die niet factorisatie gebruiken in hun berekeningen.

[pakka680]

Meest hightech factorisatie door quantum computer is het ontbinden van 15. Daar zijn 7 qubits voor nodig. Stabiliteit blijft één van de grootste uitdagingen van quantum computer.

[Verwijderd]

Nou, inmiddels zijn ze alweer een stuk verder.
Op de University van Bristol hebben ze inmiddels al weer 21 weten te ontbinden. http://en.wikipedia.org/wiki/Quantum_computer

Het ontbinden van 15 is zóó oktober .

[Poecke]

Het ontbinden van 21 is al zóóó 2010, volgens je eigen bron

De 7-qubit quantum-computer die 15 factoriseerde deed dat al in 2001.
http://computer.howstuffworks.com/quantum-computer2.htm

Ondertussen claimt D-wave al een quantum-computer met 128 qubits gelevert te hebben aan Lockheed-Martin, die al veel verder zou moeten komen. Moet wel de kanttekening bij gemaakt worden dat het discutabel was of het apparaat van D-wave ook echt quantum-verstrengeling toepaste.

Als deze trend doorgezet wordt is binnen 10 jaar 80% van wat wij doen op het internet onveilig, tenzij we fundamenteel andere encryptie gaan gebruiken.

Edit: wikipedia is onduidelijk met de verwijzing; 'in the same year'. Kan dus zijn dat je alsnog gelijk hebt.

[Reactie gewijzigd door Poecke op 23 juli 2024 21:44]

[Verwijderd]

"why should a brilant accademic person accept a price from stupid people, thats unlogical " in de geest van lennard... tenzij het de nobelprijs is natuurlijk (big bang)

[Onoffon]

Verrek, ik ken die vent ook. Vroeg me regelmatig wiskundige adviezen jaren geleden, blij dat hij het nu eindelijk een beetje begint te snappen.

[Verwijderd]

Ik heb het vermoeden dat 'afstand' een 'veld' is dat licht, beweging en chemische reactie vertraagt.

Wie kan dat weerleggen?

Hey, Herman, priema gedaan kerel!

[Reactie gewijzigd door Verwijderd op 23 juli 2024 21:44]

[qlum]

eindelijk weer eens lokaal nieuws dat niet over de media gaat.

[Phoib]

Geweldige man om mee te werken, bijzonder vriendelijke man. Gelukkig kan hij nog wel van zijn pensioen genieten, in tegenstelling tot Dik Winter...

[lezzmeister]

Verrek, ik ken die vent.
Die kwam een paar jaar terug vaak bij mijn oma langs, ook een te Riele, nu bijna nooit meer.
Zal het wel druk hebben zo te zien.