#Das Fischteich-Problem – Cipherbrain

English version (translated with DeepL)

Am Sonntag gibt es wieder einen Online Vortrag bei ICCH. Cipherbrain-Leser Jerry McCarthy wird zum Thema “A Simulator for the Welchman-Turing and US Navy Bombes” referieren. Wer zuschauen will, kann mir gerne eine Mail schicken, dann leite ich den Einwahl-Link weiter. Die Teilnahme ist kostenlos.

Mein letzter Vortrag fand am 3. Oktober statt. Zusammen mit Elonka Dunin trug ich über das Lösen alter Verschlüsselungen mit modernen Methoden vor. Unter anderem ging es um Hill Climbing und Simulated Annealing. Veranstalter war das National Museum of Computing in Bletchley Park. Moderiert wurde die Veranstaltung vom oben erwähnten Jerry McCarthy.

Ballistisches Hill Climbing

Unter den Zuschauern bei meinem Vortrag war auch Colin Wright, ein Mathematik-Professor aus Liverpool. Colin hat eine Mathematik des Jonglierens entwickelt, die er in sehr unterhaltsamen Vorträgen vorstellt. Davon hatte ich schon gehört. Auch Kryptografie-Vorträge gehören zu seinem Repertoire. Wie ich inzwischen weiß, wohnt Colin nicht weit vom Otterspool Park entfernt, doch die Bedeutung des dortigen Schilds, über das ich kürzlich gebloggt habe, kennt auch er nicht.

Nach dem Vortrag kam ich mit Colin ins Gespräch. Er fragte mich, ob ich schon einmal von Ballistic Hill Climbing gehört hätte. Dies war nicht der Fall. Er erklärte mir, dass man beim Ballistic Hill Climbing annimmt, dass der Bergsteiger eine gewisse Trägheit hat. Wenn der Bergsteiger einen Gipfel erreicht hat, bleibt er dort nicht einfach stehen, sondern geht noch ein Stück in die entsprechende Richtung weiter, obwohl es wieder abwärts geht. Durch diese Trägheit erreicht man, dass der Bergsteiger auf einem lokalen Maximum (also bei einer Falschen Lösung) nicht notwendigerweise stehen bleibt, sondern die Chance hat, ein anderes Maximum zu erreichen.

Außerdem wies mich Colin darauf hin, dass man Hill Climbing auch umdrehen kann, indem man nicht nach einem Maximum (also einem Gipfel), sondern einem Minimum (also einer Talsohle) sucht. Diese Technik nennt man Valley Descending. Auch das war mir neu.

Sowohl das ballistische Hill Climbing als auch das Valley Descending lassen sich laut Colin für das Lösen von Verschlüsselungen nutzen. Hat ein Leser schon einmal Erfahrungen damit gemacht? Falls ja, würde sich Colin auf über einen Kommentar oder eine Kontaktaufnahme freuen. Vielleicht kommt ein Erfahrungsaustausch zu Stande.

Das Fischteich-Problem

Im Nachgang schickte mir Colin ein Rätsel zu:

Gegeben sei ein Fischteich. Dieser habe einen flachen Boden, vertikale Wände und sei mit Wasser gefüllt. Außerdem gebe es drei Würfel aus Beton, die alle gleich groß sind.

Stellt man den ersten Würfel in den Teich, dann steigt das Wasser um weniger als 12 Zentimeter. Beim zweiten Würfel steigt das Wasser um genau 12 Zentimeter. Beim dritten Würfel steigt das Wasser erneut um genau 12 Zentimeter. Die Würfel stehen nebeneinander im Wasser.

Frage: Wie tief unter der Wasserobefläche liegen nun die Oberseiten der Würfel?

Findet ein Leser die Lösung? Es gibt sicherlich verschiedene Methoden dafür. Laut Colin lässt sich eine Kombination aus ballistischem Hill Climbing und Valley Descending (quasi ballistisches Valley Descending) nutzen. Er hat mir dazu folgendes geschrieben:

We let the area of the pond, depth of water, size of cube, etc, all be variables, then starting with some values compute the amounts of water rise, and compare with the amounts stated. Then “jiggle” the variables, and perform valley-descending on the error. We can think of the “jiggle” J as a modification vector added to our state S, and if our error E(S+J) is less than E(J) then we set J’ = J+S and repeat.

But wait! If moving by J was good, why not try moving by kJ, for k some multiple. So we compute E(S+kJ), and we are moving in direction J with some “momentum”.

Then use a shotgun (start at 100 different places) and we find that there are a few local minima, but the solution drops out nicely.

Lässt sich diese Technik auch für das Lösen von Verschlüsselungen nutzen? Colin schreibt:

But there are problems if your K key is “jiggled” by swapping letters, because there’s no concept of “carrying on in the same direction”, so the “ballistic” aspect doesn’t work for that.

Anyway, I was wondering if (a) anyone had heard of this idea (which has even more modifications) and (b) it had some way of being used in the context of ciphers.

Ich würde mich über ein paar entsprechende Kommentare freuen.
Follow @KlausSchmeh

Further reading: A DES challenge inspired by a conversation with Whitfield Diffie

Linkedin: https://www.linkedin.com/groups/13501820
Facebook: https://www.facebook.com/groups/763282653806483/