ICe-Cream-Van-bar

Today I am going to introduce a simple asymmetric encryption system. It’s not suitable for practical use, but very helpful for explaining how public key cryptography works.

Suppose we have a map showing 12 cross sections, which are connected via a number of streets.

Ice-Cream-Van-02

Now the question is: Can you place three ice cream vans on three of the cross sections such that every van serves exactly for cross sections (i.e., the cross section it stands on and three cross sections that are connected to this one). Every cross section that doesn’t have an ice cream van of its own needs to be connected to exactly one cross section that has one.

 

Ice Cream Van puzzles

Here’s a solution to this puzzle:

Ice-Cream-Van-01

As you see, every ice cream van serves the cross section it stands upon and is connected to exacly three others. If you’re standing on a cross section that doesn’t have an ice cream van, you will find one on a cross section that is directly connected.

The Ice Cream Van problem (also known as the Minimum Dominating Set problem) is quite difficult to solve, especially if we deal with, say, a few hundred cross sections with each ice cream van needing to be connected to, say, exactly ten of them.

Readers with a mathematical background certainly know that the Ice Cream Van problem belongs to graph theory. It is NP-complete.

While an Ice Cream Van puzzle is hard to solve, it is quite easy to create one. Just draw a number of ice cream vans and connect, say, three cross sections with each one. Then connect some of the cross sections with each other such that every ice cream van and every cross section has exactly three connections.

 

The Ice Cream Van crypto system

Based on the Ice Cream Van problem one can define a public key encryption system (a more detailed description is available here).

In the first step, Alice creates an Ice Cream Van puzzle. She uses the map with the ice cream vans as her private key, while the map version with no vans shown serves as public key. We’ll use the maps shown above.

Now suppose that Bob wants to encrypt the message “71” to Alice (this is a very short message consisting of only one number; if we use larger maps, larger numbers can be encrypted). To do so, Bob marks each cross section in Alice’s public key with a number, such that all 12 numbers sum up to 71.

Ice-Cream-Van-03

In the next step Bob adds to each number the sum of this number and the numbers of the three neighbors:

Ice-Cream-Van-04

Next, Bob deletes the original numbers and sends the map with the sums to Alice:

Ice-Cream-Van-05

For an eavesdropper it is not possible (or at least pretty difficult) to derive the message (“71”) from this infomation. However, for Alice it is easy. All she needs to do is sum up the bracketed numbers asserted to the ice cream vans (note that the position of the vans is only known to Alice):

Ice-Cream-Van-06

As you see, these numbers (23, 28 and 20) sum up to 71. Alice has decrypted the message.

In theory, the Ice Cream Van crypto system works quite well. For instance, it can be used to transmit an encrypted key for a symmetric cipher. However, mathematicians have found a way to break this method (this attack is explained in the paper I used as the source for this post). Nevertheless, the Ice Cream Van crypto system is very helpful for explaining how public key encryption works. Even school children can understand this algorithm. So, before you try to explain RSA or Elliptic Curve crypto systems to somebody, it might make sense to give an introduction to the Ice Cream Van algorithm first.


Further reading: How a spy hid a message in an alleged chess problem

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

Subscribe to Blog via Email

Gib Deine E-Mail-Adresse an, um diesen Blog zu abonnieren und Benachrichtigungen über neue Beiträge via E-Mail zu erhalten.

1 / 2 / Auf einer Seite lesen

Kommentare (3)

  1. #1 user unknown
    https://demystifikation.wordpress.com/2017/07/08/cmc-sns/
    15. Juli 2017

    Hm. Soweit ich sehe gibt es für den gezeigten Graphen überhaupt nur eine Möglichkeit, drei Eiswaffeln (Eiswägen) zu positionieren. Dass das Beispiel nicht so schwer sein soll ist mir schon klar, aber ist es nicht zu einfach, wenn es nur eine mögliche Platzierung der Wägen gibt? Und dass es bei 100 Knoten entsprechend mehr Möglichkeiten gibt, möglichst sehr viel mehr?

  2. #2 Klaus Schmeh
    15. Juli 2017

    @User unknown:
    Entscheidend ist nicht, wie viele Lösungen es gibt, sondern wie schnell man die von Alice verwendete Lösung findet. Im gezeigten Beispiel ist es in der Tat recht einfach. In der Praxis müsste man deutlich größere Zahlen verwenden.

  3. #3 Chemiker
    16. Juli 2017

    Irgendwie habe ich den Eindruck, daß dieser Algorith­mus nicht wirklich sicher ist — denn es gibt ja i.a. viele Lö­sun­gen (=Positio­nen der Eis­wagen), und jede davon ist gleich gut, um die Nach­richt zu entschlüsseln.

    Und noch schlimmer, der Codiervorgang liefert Hinweise auf den Schlüssel. In Abb. Ice-Cream-Van-01 sieht man sofort weitere Lösungen: Statt des Eis­wagens links oben hätte man auch den Knoten im linken oberen Eck nehmen können, und den rechten Eis­wagen kann man auch eine Kreuzung nach rechts schieben.

    Abb. Ice-Cream-Van-04 weist folglich für diese Paare von Kreuzungen identi­sche Summen (23 bzw. 28) aus. Das ist schlecht, weil auf diese Art etwas über den Schlüssel aus­gesagt wird. Da jede Lösung des Eiswagen­problems die Ent­schlüs­se­lung der Nach­richt er­laubt, kann ein Angreifer diese Art von In­forma­tion dazu ver­wenden, einen mög­lichen Schlüs­sel ef­fizien­ter zu finden.