Die Verteidigung meiner Diplomarbeit über RSA-PSS an der HU Berlin wird am 10. November stattfinden. Die Veranstaltung ist öffentlich (17:00 Uhr s. t., Rudower Chausee 25, Campus Berlin-Adlershof, Raum 3'113). Achtung: Termin und Ort verschoben.

Hier die Ankündigung:

Das Verschlüsselungs- und Signaturverfahren RSA ist das mit Abstand am häufigsten eingesetzte Public Key-Verfahren. RSA kann nicht in seiner ursprünglichen Form eingesetzt werden, da hierbei massive Sicherheitsprobleme auftreten. Zur Vorverarbeitung ist ein sogenanntes Padding notwendig. Bislang wird hierfür meist eine simple Hash-Funktion eingesetzt. Schon 1996 stellten Mihir Bellare und Philipp Rogaway für Signaturen ein verbessertes Verfahren mit dem Namen "Probabilistic Signature Scheme" (PSS) vor. Es garantiert unter bestimmten Annahmen "beweisbare" Sicherheit.

In der Diplomarbeit wurde untersucht, welche Vorteile RSA-PSS gegenüber früheren Verfahren bietet und inwieweit RSA-PSS in verbreiteten Protokollen bereits zum Einsatz kommt. Weiterhin wurde eine Implementierung des Verfahrens für X.509-Zertifikate für die nss-Bibliothek erstellt. nss wird unter anderem von Mozilla Firefox und Google Chrome eingesetzt.

Mich juckt es gerade in den Fingern, etwas zum Fall Guttenberg loszuwerden.

Was ich mich ja gerade die ganze Zeit frage: Warum wird eigentlich seine Uni und sein Doktorvater von der Kritik weitgehend verschont? Sein Doktorvater Peter Häberle hat sich ja inzwischen dazu bequemt, sich auch mal zu dem Fall zu äußern und Guttenberg nicht weiter in Schutz zu nehmen.

Ich meine: Wie glaubwürdig ist das denn eigentlich, dass ein Doktorvater in sieben Jahren nicht bemerkt, dass sich sein Schützling offensichtlich gar nicht selbst mit dem Thema beschäftigt? Ich gehe ja naiverweise davon aus, dass in so einem Fall regelmäßige Gespräche stattfinden, in denen man sich über das Thema unterhält und diese Gedanken fließen dann später in die Dissertation ein (zumindest läuft das so bei meiner Diplomarbeit, vielleicht mache ich ja was falsch).

Ich sehe eigentlich nur zwei realistische Erklärungen: Entweder war der Doktorvater direkt am Betrug beteiligt (halte ich für unwahrscheinlich), oder eine ernsthafte Betreuung hat schlicht nicht stattgefunden und er hat nur seinen Namen dafür hergegeben. Und das ist denke ich der zweite Skandal hier, der bislang zu wenig Beachtung gefunden hat.

(dass man eigentlich auch zumindest einen rudimentären Plagiatscheck erwarten sollte, kommt natürlich dazu, aber gut, die Bedienung von Google kann man vermutlich von einem Professor nicht erwarten)

Eine weitere Anmerkung kann ich mir nicht verkneifen: Die FAZ hat die Tage einen Ghostwriter interviewt. "Die meisten Kundenwünsche kommen sowieso aus der Betriebswirtschaft oder dem juristischen Bereich" heißt es dort - ich sags mal so, das überrascht mich jetzt nicht.

The Electronic Frontier Foundation is running a fascinating project called the SSL Observatory. What they basically do is quite simple: They collected all SSL certificates they could get via https (by scanning all possible IPs), put them in a database and made statistics with them.

For an introduction, watch their talk at the 27C3 - it's worth it. For example, they found a couple of "Extended Validation"-Certificates that clearly violated the rules for extended validation, including one 512-bit EV-certificate.

The great thing is: They provide the full mysql database for download. I took the time to import the thing locally and am now able to run my own queries against it.

Let's show some examples: I'm interested in crypto algorithms used in the wild, so I wanted to know which are used in the wild at all. My query:

SELECT `Signature Algorithm`, count(*) FROM valid_certs GROUP BY `Signature Algorithm` ORDER BY count(*);

shows all signature algorithms used on the certificates.
And the result:

+--------------------------+----------+
| Signature Algorithm      | count(*) |
+--------------------------+----------+
|  sha512WithRSAEncryption |        1 |
|  sha1WithRSA             |        1 |
|  md2WithRSAEncryption    |        4 |
|  sha256WithRSAEncryption |       62 |
|  md5WithRSAEncryption    |    29958 |
|  sha1WithRSAEncryption   |  1503333 |
+--------------------------+----------+

Nothing very surprising here. Seems nobody is using anything else than RSA. The most popular hash algorithm is SHA-1, followed by MD5. The transition to SHA-256 seems to go very slowly (btw., the most common argument I heared when asking CAs for SHA-256 certificates was that Windows XP before service pack 3 doesn't support that). The four MD2-certificates seem interesting, though even that old, it's still more secure than MD5 and provides a similar security margin as SHA-1, though support for it has been removed from a couple of security libraries some time ago.

This query was only for the valid certs, meaning they were signed by any browser-supported certificate authority. Now I run the same query on the all_certs table, which contains every cert, including expired, self-signed or otherwise invalid ones:

+-------------------------------------------------------+----------+
| Signature Algorithm                                   | count(*) |
+-------------------------------------------------------+----------+
|  1.2.840.113549.27.1.5                                |        1 |
|  sha1                                                 |        1 |
|  dsaEncryption                                        |        1 |
|  1.3.6.1.4.1.5849.1.3.2                               |        1 |
|  md5WithRSAEncryption ANDALSO  md5WithRSAEncryption   |        1 |
|  ecdsa-with-Specified                                 |        1 |
|  dsaWithSHA1-old                                      |        2 |
|  itu-t ANDALSO  itu-t                                 |        2 |
|  dsaWithSHA                                           |        3 |
|  1.2.840.113549.1.1.10                                |        4 |
|  ecdsa-with-SHA384                                    |        5 |
|  ecdsa-with-SHA512                                    |        5 |
|  ripemd160WithRSA                                     |        9 |
|  md4WithRSAEncryption                                 |       15 |
|  sha384WithRSAEncryption                              |       24 |
|  GOST R 34.11-94 with GOST R 34.10-94                 |       25 |
|  shaWithRSAEncryption                                 |       50 |
|  sha1WithRSAEncryption ANDALSO  sha1WithRSAEncryption |       72 |
|  rsaEncryption                                        |       86 |
|  md2WithRSAEncryption                                 |      120 |
|  GOST R 34.11-94 with GOST R 34.10-2001               |      378 |
|  sha512WithRSAEncryption                              |      513 |
|  sha256WithRSAEncryption                              |     2542 |
|  dsaWithSHA1                                          |     2703 |
|  sha1WithRSA                                          |    60969 |
|  md5WithRSAEncryption                                 |  1354658 |
|  sha1WithRSAEncryption                                |  4196367 |
+-------------------------------------------------------+----------+

It seems quite some people are experimenting with DSA signatures. Interesting are the number of GOST-certificates. GOST was a set of cryptography standards by the former soviet union. Seems the number of people trying to use elliptic curves is really low (compared to the popularity they have and that if anyone cares for SSL performance, they may be a good catch). For the algorithms only showing numbers, 1.2.840.113549.1.1.10 is RSASSA-PSS (not detected by current openssl release versions), 1.3.6.1.4.1.5849.1.3.2 is also a GOST-variant (GOST3411withECGOST3410) and 1.2.840.113549.27.1.5 is unknown to google, so it must be something very special.

Yesterday I read via twitter that the HP researcher Vinay Deolalikar claimed to have proofen P!=NP. If you never heared about it, the question whether P=PN or not is probably the biggest unsolved problem in computer science and one of the biggest ones in mathematics. It's one of the seven millenium problems that the Clay Mathematics Institute announced in 2000. Only one of them has been solved yet (Poincaré conjecture) and everyone who solves one gets one million dollar for it.

The P/NP-problem is one of the candidates where many have thought that it may never be solved at all and if this result is true, it's a serious sensation. Obviously, that someone claimed to have solved it does not mean that it is solved. Dozends of pages with complex math need to be peer reviewed by other researchers. Even if it's correct, it will take some time until it'll be widely accepted. I'm far away from understanding the math used there, so I cannot comment on it, but it seems Vinay Deolalikar is a serious researcher and has published in the area before, so it's at least promising. As I'm currently working on "provable" cryptography and this has quite some relation to it, I'll try to explain it a bit in simple words and will give some outlook what this may mean for the security of your bank accounts and encrypted emails in the future.

P and NP are problem classes that say how hard it is to solve a problem. Generally speaking, P problems are ones that can be solved rather fast - more exactly, their running time can be expressed as a polynom. NP problems on the other hand are problems where a simple method exists to verify if they are correct but it's still hard to solve them. To give a real-world example: If you have a number of objects and want to put them into a box. Though you don't know if they fit into the box. There's a vast number of possibilitys how to order the objects so they fit into the box, so it may be really hard to find out if it's possible at all. But if you have a solution (all objects are in the box), you can close the lit and easily see that the solution works (I'm not entirely sure on that but I think this is a variant of KNAPSACK). There's another important class of problems and that are NP complete problems. Those are like the "kings" of NP problems, their meaning is that if you have an efficient algorithm for one NP complete problem, you would be able to use that to solve all other NP problems.

NP problems are the basis of cryptography. The most popular public key algorithm, RSA, is based on the factoring problem. Factoring means that you divide a non-prime into a number of primes, for example factoring 6 results in 2*3. It is hard to do factoring on a large number, but if you have two factors, it's easy to check that they are indeed factors of the large number by multiplying them. One big problem with RSA (and pretty much all other cryptographic methods) is that it's possible that a trick exists that nobody has found yet which makes it easy to factorize a large number. Such a trick would undermine the basis of most cryptography used in the internet today, for example https/ssl.

What one would want to see is cryptography that is provable secure. This would mean that one can proove that it's really hard (where "really hard" could be something like "this is not possible with normal computers using the amount of mass in the earth in the lifetime of a human") to break it. With todays math, such proofs are nearly impossible. In math terms, this would be a lower bound for the complexity of a problem.

And that's where the P!=NP proof get's interesting. If it's true that P!=NP then this would mean NP problems are definitely more complex than P problems. So this might be the first breakthrough in defining lower bounds of complexity. I said above that I'm currently working on "proovable" security (with the example of RSA-PSS), but provable in this context means that you have core algorithms that you believe are secure and design your provable cryptographic system around it. Knowing that P!=NP could be the first step in having really "provable secure" algorithms at the heart of cryptography.

I want to stress that it's only a "first step". Up until today, nobody was able to design a useful public key cryptography system around an NP hard problem. Factoring is NP, but (at least as far as we know) it's not NP hard. I haven't covered the whole topic of quantum computers at all, which opens up a whole lot of other questions (for the curious, it's unknown if NP hard problems can be solved with quantum computers).

As a final conclusion, if the upper result is true, this will lead to a whole new aera of cryptographic research - and some of it will very likely end up in your webbrowser within some years.

Zum Thema Rapid Prototyping und dessen möglicherweise gravierenden gesellschaftlichen Auswirkungen las ich das erste mal in einen Text der Zukunftswerkstatt Jena, der im sehr lesenswerten Büchlein »Herrschaftsfrei Wirtschaften« veröffentlicht wurde (welches es auch komplett zum Download gibt).

Aber der Reihe nach: In der Debatte um freie Software, speziell in eher politisierten Kreisen (Stichworte sind hier etwa Ökonux oder das Keimform-Blog), wird des öfteren die Frage aufgeworfen, ob die Art und Weise, wie freie Software produziert wird, nicht als Modell für gesellschaftliches Wirtschaften insgesamt herhalten kann. Dabei wird oft der Begriff »Keimform« aus der Wertkritik gebraucht, der etwas bezeichnet, was zwar im bestehenden Kapitalismus und dessen Kontext stattfindet, aber erste Züge anderer Strukturen aufweist.

Nun stellt sich naiverweise erstmal die Herausforderung, dass immaterielle Güter (Software, Musik, Text) mit vernachlässigbarem Aufwand kopiert werden können, insofern die Adaption der Prinzipien freier Software hier nahe liegt (bestes Beispiel die Wikipedia), im Gegensatz dazu natürlich materielle Güter hier herausfallen, weil sie immer noch einen vergleichsweise großen Produktionsaufwand pro Stück besitzen.

Die Science-Fiction-lastig anmutende Frage »Lässt sich das ändern?« bringt uns nun zurück zum Thema Rapid Prototyping. Damit werden Verfahren bezeichnet, komplett automatisiert Gegenstände zu erschaffen, im einfachsten Beispiel etwa die (schon länger technisch machbaren) 3D-Drucker, die Kunststoffgebilde nach Computervorbild erschaffen können. Weiter gedacht könnten derartige Gerätschaften, wenn sie mit unterschiedlichen Materialien arbeiten, auch zur Produktion komplexerer Geräte genutzt werden.

Das Ziel, was sich vor einigen Jahren der Wissenschaftler Adrian Bowyer setzte, lautet nun: Eine Maschine, welche in der Lage ist, sich selbst neu zu erschaffen. Sozusagen vergleichbar mit dem Schritt, als der erste Compiler lernte, sich selbst zu übersetzen.

Heute vermeldet Golem, dass es erstmals gelungen ist, einen sogenannten RepRap dazu zu bringen, sich selbst zu reproduzieren. Von der Gesellschaft freier Güter mögen wir sicher noch ein Stück entfernt sein, sollte der RepRap allerdings tatsächlich das leisten, was seine Erfinder vermeldeten, sind wir ihr möglicherweise ein gutes Stück näher.

Achja: Der RepRap steht mit der GPL selbstverständlich unter einer freien Lizenz.

Die Webseite Blasphemy Challenge (via boingboing) bietet, im Tausch gegen die eigene Seele, eine DVD des religionskritischen Films »The God who wasn't there«.
Das ganze läuft folgendermaßen: In der Bibel, Markus 3, Vers 28 und 29, ist nachzulesen:
Amen, das sage ich euch: Alle Vergehen und Lästerungen werden den Menschen vergeben werden, so viel sie auch lästern mögen; wer aber den Heiligen Geist lästert, der hat keine Vergebung in Ewigkeit, sondern ist ewiger Sünde schuldig. (Übersetzung nach Luther, Copyright abgelaufen)

Sprich: Gott vergibt viel, eigentlich fast alles. Aber wer die Existenz des heiligen Geistes verneint, der macht sich der ewigen Sünde (ich finde ja da das Englische schicker, »eternal sin« klingt viel gewaltiger) schuldig. Zum Beweis der ewigen Sünde empfielt die Seite, ganz modern, ein youtube-Video, in dem der Satz »I deny the holy spirit« ausgesprochen wird.

Nunja, Seele gegen DVD, ein fairer Tausch wie ich finde, weswegen man mich hier bewundern kann. Ich hatte zuerst überlegt, noch ein paar schlaue Worte zu sagen, hab mich dann aber entschieden, dass das Videoblogging nicht so meine Welt ist, auf Englisch schon garnicht, und ich mich doch lieber auf's Schreiben verlege. Deswegen ist das Video auch komplett belanglos, bevor mir aber jemand vorwirft, proprietäre Formate zu befördern, gibt's das ganze natürlich wie üblich als ogg theora/vorbis.

Als nicht-US-Bürger muss man 8 Dollar für den Versand abdrücken. Rezension des Films gibt's dann natürlich hier sobald die DVD da ist.

Wenn also Gott existierte, gäbe es für ihn nur ein einziges Mittel, der menschlichen Freiheit zu dienen: aufhören zu existieren. (Michael Bakunin, Gott und der Staat)

The God who wasn't there DVD

Ich gehör ja noch zu den Idealisten, die wegen Klimawandel, Lärm, Waldsterben, Fächenverbrauch und Co. kein Auto besitzen. Allerdings weiss ich gelegentlich die Nutzung eines fahrbaren Untersatzes doch zu schätzen, finde jedoch bei dem, was es gerade auf dem Markt gibt, nichts, was ansatzweise akzeptabel wär. Zwar hege ich keine seltsam nationalistischen Vorurteile gegen Toyota, finde den Verbrauch des Autos von Boris Palmer jedoch mit knapp 5 Litern immer noch weit über dem, was man eigentlich will. Kleiner 2l/100km wär schon Requirement.

Stefan bloggt über den Loremo, was schonmal deutlich besser klingt. Zwar Diesel (Rußpartikel, Feinstaub), aber immerhin mal ein Spritverbrauch, der für die nächsten 10 Jahre noch im akzeptablen Bereich liegt.

Still here at the 23C3, I'll try to summarize some things about the talks I've visited yesterday.

First was a presentation about the Trust model of GPG/PGP and an alternative approach. I wasn't so impressed, because I think the main lack from the web-of-trust-infrastructure is that it's too complex to understand for the masses.

The Lightning-Talks were quite nice, some guy presented some live-hacks to a poorly designed travel agency, which was very funny. I personally presented compiz and told some short things about the situation of 3D-graphics and desktops.
I saw about the last 10 minutes of a talk about Drones, camera-supplied small devices flying around, and thoughts what these devices could mean for the society. A group is working on creating such devices on quite small costs. I'll have to fully view that on video after the congress.

Another very interesting Talk: »The gift of sharing«, the referent presented thoughts what kind of »economy-structure« the free software development should be called. It was a bit difficult to follow the talk, as it was in english and I'm no native english speaker. There's a paper from the guy which is probably worth reading.

The last talk was about wiki knowledge and citing that in science. The referents plan to create an RFC for citing-URLs in Wikis.
What irritated me was a computer science professor telling that she wouldn't allow her students to cite wikis, with the stupid argument they should cite their sources from books, completely igonring that science can happen in wikis and it may be the original source of the knowledge, not just something that has been explored elsewhere. Ruediger Weiss gave good arguments against that and mentioned that he thinks wiki is really a new kind of doing science and should be handled as such.

To be continued.

Unter dem Titel »Hieroglyphen, Enigma, RSA - Eine Geschichte der Kryptographie« fanden heute an der Uni Karlsruhe zwei Vorträge, sowie eine anschließende Besichtigung der Sammlung von Klaus Kopacz.

Ich hatte zum ersten mal die Gelegenheit, originale Enigma-Maschinen zu sehen und bekam auch im Vortrag einen Eindruck, wie überhaupt genau der Verschlüsselungsalgorithmus der Enigma funktionierte.

Enigma-Bilder gibt's hier

Nachfolgender Artikel liegt schon viel zu lang unveröffentlicht auf meiner Platte. Wird warscheinlich im nächsten Grünen Blatt erscheinen und darf gern auch anderswo veröffetnlicht werden (officetaugliches Format auf Anfrage).

Vor circa einem halben Jahr hab ich Lars am Telefon erzählt, dass ich glaube, die katholische Kirche wird demnächst wieder zum Kreationismus zurückfallen. Er meinte damals, ich soll das bloggen, damit ich nachher behaupte kann, ich hätte es vorher gewußt.
Hab ich leider nicht gemacht. Der Guardian berichtet über Bestrebungen im Papst-Umfeld, sich die Intelligend Design-Theorie zu eigen zu machen (Intelligent Design ist letztendlich nichts anderes als die pseudowissenschaftliche Verpackung für Kreationismus).

Ich halte es ja nach wie vor mit dem fliegenden Spaghettimonster.

Found in the net, made me laugh:
PETA sues FermiLab for cruelty to Schrödinger's Cat; outcome uncertain
(from mplayer mailinglist)

From todays solar eclipse, which could be partially watched from Germany, I tried to take some pictures.

Good that I kept my special eclipse sun glasses from 1999 (when we had a total eclipse over south Germany I completely missed due to the bad weather back then). Most of the time it was cloudy, but I still managed to get some nice pics.

Second day, finally uploaded some pictures and just found some time to blog between two talks.

Yesterday the We lost the war talk. Maybe I'll write something more in german when I find time for it. In short: IMHO this was an obscure mixture of political nonsense. This should at least be clear when reading the article with similar content in the last »Datenschleuder«, where the author claims something like »till 9.11. hackers ruled the world and everything was good« (to cite, »The big corporations were at our merce, because we knew what the future would look like and we had the technology to built it).
Lars wrote very drastically about it.

Today, the first interesting talk was5 Thesis on Informational-Cognitive Capitalism. I think I didn't really get what the autor wanted to say (surely related to missing sleep and lack of motivation to listen to english), but he was at least quite entertaining.

Next was Hashing Trusted Computing by Rüdiger Weis, as always quite funny, Rüdiger maybe should become the first professional math comedian. The content is obvious, at least for regular readers of my blog: Trusted Computing is evil and SHA1 is broken.

There was a nice presentation by fukami and Markus Beckedahl about the Sony BMG rootkit. They presented a lot of information, Markus has also collected it in his blog.

Next one was Technological art off the trodden tracks by two media artists that presented art which is related to hacking subjects and suggested that media artists and hackers come more together to share thoughts and projects. I hope they'll put their materials online, they had a lot of videos from nice stuff.

Just came from Learning cryptography through handcyphers by Benno de Winter. It was a basic introduction to some simple algorithms, not really new to me, but the speaker was worth watching because of the fun factor.

More to come.

Das GIMPS-Projekt vermeldet die Entdeckung der 43. Mersenne-Primzahl und damit der bisher größten bekannten Primzahl. Die Zahl wird jetzt nochmal überprüft und dann in wenigen Tagen veröffentlicht.

Was ich heute zum Anlaß nehme, ein bißchen was über Primzahlen zu erzählen, weil ich das ein unheimlich spannendes Thema finde.

Einführung für Nicht-Mathematiker

Eine Primzahl ist eine natürliche Zahl, welche exakt zwei Teiler besitzt, die 1 und sich selbst. Primzahlen sind etwa 2, 3, 5, 7, 11, 13, ...

Relevanz von Primzahlen

Die größte Relevanz haben Primzahlen in der Public-Key-Kryptographie - so basiert etwa das weitverbreitete RSA-Verfahren auf der Tatsache, dass es einfach ist, zwei große Primzahlen miteinander zu multiplizieren, jedoch nur mit großen Rechenaufwand möglich, das Ergebnis wieder in seine Primzahlen zu zerlegen.
Die Kryptographie und die damit verbundene Zahlentheorie sind ein Beispiel für eine Wissenschaft, die lange Zeit aus rein theoretischen Erwägungen durchgeführt wurde und dann aufgrund der technischen Entwicklung plötzlich zu großer Relevanz führte.

Primzahlen erkennen

Ein bis vor wenigen Jahren ungelöstes Rätsel war es, ob ein ein effizienter (mathematisch: polynomialen) Algorithmus existiert, welcher eine Primzahl erkennt. Lange Zeit wurden hierfür lediglich Näherungsverfahren angewendet, die lediglich mit sehr hoher Warscheinlichkeit feststellen, ob eine Zahl prim ist. Erst 2001 gelang es drei indischen Wissenschaftlern mit dem AKS-Test einen solchen Algorithmus zu entwickeln.

Illegale Primzahl

Die erste bekannte Primzahl, die nach dem amerikanischen DMCA (inzwischen auch in der EU) illegal ist, enthält den Code des DVD-Entschlüsselungstools DeCSS.

Ungelöste Primzahl-Probleme

Die Beschäftigung mit Primzahlen bietet Perspektiven - es gibt eine ganze Reihe ungelöster Primzahl-Probleme:

Große Primzahlen: Die oben angesprochenen Mersenne-Primzahlen sind bislang die effizienteste Methode, extrem große Primzahlen (mit mehreren tausend Stellen) zu erzeugen. Dabei handelt es sich um Zahlen der Form 2^n-1. Obwohl es sehr leicht möglich ist, mit dem Euklidschen Primzahlbeweis zu zeigen, dass es unendlich viele und damit unendlich große Primzahlen gibt, gibt es bislang keine Methode, aus dem Euklidschen Beweis ein einfaches Verfahren zur Erzeugung beliebig großer Primzahlen zu entwickeln. Ein solches würde einem auch gleich die diversen Preise der EFF für die Entdeckung großer Primzahlen bescheren.
Primzahl-Zwillinge: Es ist bislang nicht bekannt, ob es unendlich viele Primzahl-Zwillinge gibt. Primzahl-Zwillinge sind zwei Primzahlen, die sich lediglich um 2 unterscheiden, also etwa 3 und 5, 11 und 13 etc. Daran schließt sich die Frage an, ob es unendlich viele Primzahlvierlinge, d. h. Primzahlen der Form n, n+2, n+6, n+8 gibt (beispielsweise 5, 7, 11, 13). Lässt sich natürlich beliebig fortsetzen.
Schneller Primzahltest: Zwar existiert mit dem AKS-Algorithmus ein polynomialer Algorithmus zur Bestimmung von Primzahlen, jedoch ist dieser noch sehr langsam - in allen praktischen Anwendungen, etwa in der Kryptographie, werden weiterhin Näherungsverfahren angewandt. Eine Optimierung des AKS-Algorithmus oder ein neuartiger Algorithmus, der auch in praktischen Anwendungen (Zahlen bis 4096 Bit) schnell ist, wäre hier eine spannende Entdeckung.
Goldbachsche Vermutung: Lässt sich jede Gerade Zahl größer 2 als Summe aus zwei Primzahlen darstellen (2+2=4, 3+3=6, 3+5=8, 3+7=10 etc.)? Funktioniert für alle getesteten Zahlenräume, indes, der Beweis fehlt, obwohl es so einfach aussieht.
Faktorisierung: Die wohl spannendste Frage, gibt es eine Möglichkeit, große Zahlen effizient in ihre Primfaktoren zu zerlegen? Ein solches würde fast die gesamte heute angewandte Kryotpgraphie unbrauchbar machen. Man geht heute davon aus, dass Primzahlen bis 1024 Bit mit großen finanziellen Aufwand brechbar sind (nach Twirl googeln oder mal den Wikipedia-Artikel dafür schreiben). Die Firma RSA-Security zahlt Preisgelder für die Faktorisierung großer Zahlen - die Zahl RSA-640 (steht für die Bit-Zahl) wurde bereits faktorisiert, als nächstes steht RSA-704 an. Das Thema wurde bereits in mehreren Filmen verarbeitet (Mercury-Puzzle, Sneakers).
Mit einem Quantencomputer wäre eine effiziente Faktorisierung möglich - mit dem SHOR-Algorithmus - ein solcher Quantencomputer existiert jedoch bislang nur in der Theorie.

Wikipedia hat noch ein paar Probleme parat. An einem anderen Problem war ich auch schonmal dran (hat aber nix mit Primzahlen zu tun), aber welches verrat ich jetzt nicht - sonst nimmt es mir noch jemand weg ;-)

Etwas, wozu ich bei kurzer Recherche keine verifizierbaren Infos gefunden hab: Es gibt immer wieder Berichte von Fällen, in denen Autisten mit großer Geschwindigkeit Primzahlen erkennen konnten - ebenfalls in einigen Filmen verwandt (The Cube, Rainman). Urban-Legend oder gibt's dazu wissenschaftliche Ergebnisse?


Ich hoffe alles war soweit inhaltlich richtig, Mathematiker mögen mich korrigieren.

Zu guter letzt ein Zitat aus dem heise-Forum. Ein Teilnehmer fragte
kann man mit dieser zahl jetzt irgendwas sinnvolles anfangen?
woraufhin ein anderer antwortete
Kann man mit der Fußball-WM irgendwas sinnvolles anfangen?
Genau!