Hier ein Beitrag um zu beweisen, dass Informatik sich mit viel mehr beschäftigt als nur mit Computern. Beispielsweise auch mit ganz profanen Türschlössern.
Nehmen wir an, jemand besitzt eine Maschine zum Fräsen von Schlüsseln, und beliebig viele Rohlinge. Um nun einen Schlüssel für ein Schloss anzufertigen, dessen Code man nicht kennt, kann man natürlich einfach alle Möglichkeiten durchprobieren, bis man den korrekten Schlüssel erwischt hat. Bei einem klassischen österreichischen(*) Türschloss sind das etwa 100000 mögliche Kombinationen, nämlich 5 Stellen mit Werten zwischen 0 und 9. Die Schlüssel lassen sich entsprechend bezeichnen mit 00000 bis 99999.
Entsprechend wird man durchschnittlich 50000.5 Schlüssel anfertigen müssen, bis man den richtigen erwischt. Wenn man für einen Schlüssel und das Ausprobieren desselben eine Minute benötigt, dann dauert das (im Durchschnitt) etwa 35 Tage -- essen und schlafen noch nicht mitgerechnet. Für eine praktische Umsetzung ist das viel zu langwierig, daher "sicher". Außerdem fällt es auf, wenn jemand 35 Tage lang vor einer fremden Wohnungstür sitzt und Schlüssel ausprobiert.
Nehmen wir nun aber an, die Wohnung befindet sich in einem Mehrparteienwohnhaus mit einem Schließsystem und einer gemeinsam gesperrten Haupteingangstür. Das heißt, jeder Bewohner hat einen Schlüssel, der seine eigene Wohnung sperrt und die gemeinsame Tür.
Nun müssen wir uns ein wenig damit befassen, wie so eine Schließanlage funktioniert. Beginnen wir einmal mit der Funktionsweise eines normalen Zylinderschlosses. Dieses besteht aus Federn und Stiften. Der richtige Schlüssel drückt die Stifte genau so weit hinein, dass der Spalt zwischen Feder und Stift genau an der Kante zwischen Schloss und drehbarem Zylinder ist; Nur dann kann der Zylinder gedreht werden. Die nächsten Bilder verdeutlichen diese Beschreibung.
Skizze 1: Zylinderschloss
Skizze 2: Zylinderschloss mit richtigem Schlüssel
Skizze 3: Zylinderschloss mit falschem Schlüssel
Um zu erreichen, dass eine Tür von mehreren verschiedenen Schlüsseln gesperrt werden kann, werden statt der durchgehenden Stifte solche Stifte verwendet, die sich aus mehreren Teilen zusammensetzen. Der Zylinder kann dann gedreht werden, wenn sich an jeder der fünf Schlüsselpositionen
eine der Spalten im Stift an der Kante zwischen Zylinder und Schloss befindet. Im Folgenden sind Skizzen von einem Schloss, das mit zwei Schlüsseln gesperrt werden kann.
Skizzen 4 und 4a: Zylinderschloss mit zwei sperrenden Schlüsseln
Die beiden Schlüssel in Skizzen 4 und 4a haben die Nummern 851
73 und 851
43 -- beschriftet von links nach rechts, größere Ziffern bedeuten längere Stifte / tiefere Kerben. Offensichtlich müssen vier der fünf Stellen gleich sein.
Bei dem Schloss aus Skizzen 4 und 4a gibt es zwei mögliche Schlüssel, folglich könnte man es als gemeinsam gesperrte Tür für zwei Wohnungen verwenden. Für mehr Wohnungen braucht man entsprechend mehr unterteilte Stifte. Beispielsweise könnte man den bereits geteilten vierten Stift ein weiteres Mal unterteilen, sodass die drei Kombinationen 851
43, 851
73 und 851
93 möglich sind. Oder man könnte einen weiteren Stift teilen, zum Beispiel den ersten, um die Kombinationen
251
43,
251
73,
851
43 und
851
73 zu erhalten.
Kurz und gut, wie auch immer man es anstellt, die Schlüssel, die die gemeinsame Tür sperren, weisen ein Muster auf. Und genau das nutzen wir nun aus.
Nehmen wir an, ich besitze einen gültigen Schlüssel für die gemeinsam gesperrte Tür -- nämlich den meiner eigenen Wohnung. Habe dieser zum Beispiel die Nummer 12345. Um herauszufinden, wie das Schloss der gemeinsamen Eingangstür aufgebaut ist, brauche ich lediglich 45 Schlüssel, nämlich jene, die entstehen, wenn man jeweils nur genau eine Stelle verändert. Wenn 12345 ein gültiger Schlüssel ist, dann erfahre ich durch Durchprobieren der Schlüssel
22345,
32345,
42345, ...,
92345, 1
1345, 1
3345, ..., 1
9345, 12
145, 12
245, ..., 12
945, ...... 1234
9 die Positionen aller Spalten in den Stiften des gemeinsamen Türschlosses. (Von den vier unveränderten Stellen weiß ich mit Sicherheit, dass ein Spalt an der richtigen Stelle ist. Falls der Schlüssel mit einer veränderten Position nicht sperrt, muss also diese eine veränderte Stelle diejenige sein, bei der der Stift nicht in einer richtigen Position ist. Sperrt der Schlüssel, so ist auch für die veränderte Stelle ein Spalt im Stift vorhanden.)
Aus den Positionen dieser Spalten in den Stiften lassen sich nun wiederum alle Schlüssel konstruieren, die das Schloss sperren, selbst wenn sich diese noch nicht unter den durchprobierten Schlüsseln befanden. Wenn 1
8345 und 1234
7 nämlich beide sperren, dann muss auch 1
834
7 ein gültiger Schlüssel sein.
Jetzt bleibt zu hoffen, dass die gemeinsame Tür so gebaut ist, dass möglichst wenige Schlüssel sie sperren. Das ist auch üblicherweise der Fall. Bei 8 Wohnungen wird man zum Beispiel drei Stifte in je zwei Teile teilen, bei 24 Wohnungen einen vierten Stift in drei Teile zerlegen. Bei 37 Wohnungen wird man nicht umhin kommen, das Schloss so zu bauen, dass mindestens 40 Schlüssel sperren. (Man kann keinen Stift in mehr als 10 Teile teilen. 37 ist eine Primzahl, 38 = 2*19 enthält einen zu großen Primfaktor, 39 = 3*13 ebenso, und 40 = 2*2*2*5 ist möglich.)
Wie auch immer, im Normalfall wird es etwa gleich viele mögliche Schlüssel geben wie Wohnungen. Und Wohnblöcke mit mehr als 50 oder 100 Wohnungen sind nicht gerade häufig. Folglich fertigt man nun diese höchstens 100 möglichen Schlüssel an, und einer davon wird die Nachbarwohnung sperren.
Wenn man wie oben etwa 1 Minute für jeden gefertigten Schlüssel annimmt, kommt man mit den 45 + ca. 100 Schlüsseln auf etwas mehr als zwei Stunden Arbeit. Das ist etwas, wofür der Nachbar noch nicht einmal auf Urlaub sein muss. Soviel zum Untertitel.
Setzen wir den Gedanken noch ein wenig fort. Nehmen wir an, jemand, der nicht einmal einen Wohnungsschlüssel für eine andere Wohnung im gleichen Haus besitzt, will einen Schlüssel fälschen. Sobald wir einen gültigen Schlüssel für
irgendeine Wohnung im Haus haben (oder auch nur für die gemeinsame Eingangstür), kann mit der oben beschriebenen Methode offensichtlich recht effizient auch ein Schlüssel gefunden werden für diejenige Wohnung, in die eingebrochen werden soll. (Entsprechend müssten eigentlich jedes Mal, wenn irgendwer seinen Schlüssel zu
einer Wohnung verliert, die Schlösser bei
allen Wohnungen ausgetauscht werden.)
Wie lange dauert es nun also, einen Schlüssel für die gemeinsame Eingangstür zu finden? Offensichtlich ist das leichter als bei einer einzelnen Wohnung, da es mehr gültige Schlüssel gibt. Nehmen wir an, es gibt
k Wohnungen, und das gemeinsame Schloss lässt sich von genau
k Schlüsseln sperren. Dann braucht man im Durchschnitt 100001/(
k+1) Versuche, bis man einen dieser Schlüssel erraten hat.
Um in eine bestimmte Wohnung einzubrechen braucht man nun also im Durchschnitt 100001/(
k+1) + 45 + (
k+1)/2 Schlüssel. (Erraten eines Schlüssels für die gemeinsame Tür + Bestimmen des Aufbaus des gemeinsamen Schlosses + Erraten des richtigen der
k gültigen Wohnungsschlüssel.) Im Gegensatz zu einer einzelnen Wohnung (für die man wie oben beschrieben im Durchschnitt 50000.5 Schlüssel braucht), benötigt man für eine Wohnung in einem Wohnblock mit 2 Wohnungen nur noch durchschnittlich 33380.17 Schlüssel, also um 33% weniger. Bei 10 Wohnungen benötigt man nur mehr 9141.5 Versuche, also 81% weniger als bei einer einzelnen Wohnung.
Einige weitere Zahlen:
| Anzahl Wohnungen | Durchschnittliche Versuche | Sicherheitsverlust in Prozent |
| 2 | 33380,17 | 33,24 |
| 3 | 25047,25 | 49,91 |
| 4 | 20047,7 | 59,91 |
| 5 | 16714,83 | 66,57 |
| 10 | 9141,5 | 81,72 |
| 20 | 4817,45 | 90,37 |
| 50 | 2031,3 | 95,94 |
| 100 | 1085,61 | 97,83 |
| 200 | 643,02 | 98,71 |
Bei 446 Wohnungen schließlich benötigt man durchschnittlich nur noch 492 Schlüssel, etwa 8 Stunden und somit um 99% weniger als wenn es keine gemeinsame Eingangstür gäbe.
Gibt es noch mehr Wohnungen im Wohnblock, so steigt die Schwierigkeit langsam wieder, da zwar die Eingangstür nun leichter zu erraten ist, danach aber umso mehr gültige Schlüssel existieren.
Daraus folgt, passend zum ersten Titel: Obwohl bei einer gemeinsamen Eingangstür zwei versperrte Türen zwischen dem Einbrecher und der Wohnung stehen statt nur einer, ist die Sicherheit
geringer. So gesehen wäre es am sichersten, gar keine gemeinsame Eingangstür zu haben, oder zumindest eine, bei der jeder Schlüssel sperrt. (Natürlich nur aus informatisch-theoretischer Sicht. Praktisch braucht man bei zwei Türen trotzdem einmal öfter das Brecheisen als bei einer.)
Noch allgemeiner betrachtet kann man statt der 100000 Möglichkeiten ein Schlüsselsystem annehmen, in dem es
n mögliche Schlüssel gibt (beispielsweise durch zusätzliche Stellen oder mehr Ziffern pro Stelle). Sei wie oben
k die Anzahl der Wohnungen im Wohnblock. Dann beträgt die durchschnittliche Anzahl der Versuche (
n+1)/(
k+1) + (
k+1)/2 +
C, wobei
C die Konstante für das Austesten des gemeinsamen Schlosses ist, im obigen Sonderfall also 45. Die geringste Sicherheit besteht dann genau dann, wenn die Anzahl der Wohnungen
k gleich ((
Wurzel[2*
n+2])-1) ist, und beträgt dann ((
Wurzel[2*
n+2])+
C). Größenordnungsmäßig reduziert sich die Schwierigkeit im schlimmsten Fall also von
O(n) auf
O(Wurzel[n]).
Übrigens besteht die Reaktion der Hersteller von Schließsystemen bislang nicht im Entwurf neuer Systeme, sondern schlicht und einfach in der Erhöhung der Anzahl der Möglichkeiten. Mit bis zu 8 seitlichen Einkerbungen produziert Winkhaus beispielsweise ein Schloss mit 256000000 Möglichkeiten. Andere Schließsysteme verwenden Magneten für zusätzliche Stellen.
Eine der wenigen Möglichkeiten, die tatsächlich das Grundproblem beheben, sind elektronische Schließsysteme, bei denen einfach jeder Schlüssel eine Nummer hat und jedes Schloss eine Liste derjenigen Nummern speichert, bei denen es sperren soll.
lG Birgit
... die übrigens keine Schlüsselfräse besitzt.
(*) Deshalb österreichisch, weil jedes Land etwas andere Schlüsselnormen verwendet. Die meisten Prinzipien dieses Artikels funktionieren aber auch dort.
P.S.: Als Zuckerl für alle, die bis hierher gelesen haben:
http://www.xkcd.com/538/
