 Gedankenspielerei: Karten geheim verteilen |
Crotaphytus
Mitglied
Dabei seit: 18.09.2006
Beiträge: 45
 |
|
| Gedankenspielerei: Karten geheim verteilen |
     |
Erstmal hoff ich, der Thread ist hier richtig, ansonsten bitte verschieben.
----
Um was geht es? Beim letzten Skatabend hab ich mir einige Gedanken gemacht. Mal angenommen, ich würde ein Skatspiel programmieren wollen, mit dem man übers Netzwerk spielen kann. Dann müsste man irgendwie das Problem lösen, wie man die Karten verteilt. Wenn man keinen Server haben will, muss das einer der am Spiel beteiligten Rechner erledigen. Die Frage ist: Wie tut man das am Besten, ohne dass einer der Rechner die Karten der anderen kennt?
Die naive Idee, dass einer einfach Karten zufällig an die anderen verteilt, funktioniert ja offensichtlich nicht. Denn dann kennt dieser Rechner (auch wenn er sie dem Spieler vielleicht nicht anzeigt) die Karten aller anderen Spieler auf jeden Fall.
Die Frage, die ich mir gestellt habe, ist: Kann man diesen Prozess so durchführen, dass keiner der beteiligten Rechner irgendwelche Karten kennt, die er nicht kennen sollte?
Ich hab ne Weile drüber nachgedacht und bin zu ner Lösung gekommen, von der ich ziemlich sicher bin, dass sie funktioniert. Allerdings würd mich mal interessieren, auf was für Ideen andere kommen, deswegen stell ich diese Aufgabe hier rein.
Würde mich interessieren, ob ihr in der gleichen Richtung denkt wie ich oder ob sich vollkommen andere Lösungsansätze ergeben. Entsprechend werd ich von meinen Überlegungen erst mal nichts schreiben.
Viel Spaß!
PS: Das ist ne rein hypothetische Aufgabe. Ich will weder so ein Programm schreiben noch fand sich das Ding auf irgendwelchen Übungszetteln.
PPS: Für alle, die Skat nicht kennen, die Verteilung der Karten läuft so ab: Es gibt 32 Karten und 3 Spieler. Zunächst erhält jeder Spieler 10 Karten. Die beiden übrigen werden zunächst nicht benutzt, erst zu einem späteren Zeitpunkt steht fest, welcher der drei Spieler diese zwei Karten noch zusätzlich erhält (eine Feinheit, die die Aufgabe nicht unbedingt leichter macht...
)
__________________
Das ist keine Signatur.
|
|
20.10.2006 18:32 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
Find grad mein Schneier-Buch nicht, aber es gibt eine Möglichkeit mit kommutativer Verschlüsselung. In etwa so:
Für jede Karte gibt es eine Datei. Ein Spieler mischt die Dateien und verschlüsselt sie mit seinem Schlüssel, danach gibt er sie an den nächsten Spieler weiter.
Wenn jeder Spieler die Prozedur durchlaufen hat werden die Karten verteilt. Jeder Spieler lässt sich seine Karten von seinen Gegnern entschlüsseln und kann dann am Ende mit seinem eigenen Schlüssel entschlüsseln und sehen welche Karte es ist.
Wichtig ist, daß das Verschlüsselungsverfahren ein kommutatives ist, also )=E_{k_2}(E_{k_1}(M)))
Ein Problem, daß Du vermutlich nicht rauskriegen wirst ist, daß sich die Contra-Spieler absprechen können.
Gruss,
ED
PS: Ich find das Buch nicht und hatte schon ein paar Bier, also sind meine Angaben ohne gewähr 
|
|
|
21.10.2006 01:01 |
|
|
Crotaphytus
Mitglied
Dabei seit: 18.09.2006
Beiträge: 45
|
|
Die Absprache wird man wohl in der Tat nie komplett verhindern können, aber das ist beim normalen Spielen ja auch so...
Deine Antwort war schon mal was in der Art, das ich erhofft hab - der Ansatz geht nämlich in ne komplett andere Richtung wie das, was mir eingefallen ist. Das Verfahren hat auch den entscheidenden Vorteil, dass es ohne weiteres auf beliebig viele Spieler erweiterbar ist, ohne dass man groß nachdenken muss, und dass es auch problemlos Sonderfälle wie den Skat abdeckt. Da hab ichs mir doch irgendwie unnötig schwer gemacht...^^
__________________
Das ist keine Signatur.
|
|
|
22.10.2006 20:30 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
Dennoch wüsst ich gerne wie du es nun löst
|
|
|
23.10.2006 11:22 |
|
|
Crotaphytus
Mitglied
Dabei seit: 18.09.2006
Beiträge: 45
|
|
Na gut, hab zwar auf noch ein paar mehr Antworten gehofft, aber nachdem sich hier wohl nix mehr tut...
Allerdings is das Ganze nicht so schön zu erklären wie das von dir vorgestellte. Es braucht kein kompliziertes Verschlüsselungsverfahren, dafür is der Rest deutlich komplexer...
Wir haben drei Spieler A, B und C. Spieler A hat zunächst mal sämtliche Karten, die er verschlüsselt - jedoch jede Karte mit einem eigenen Schlüssel. Nun übermittelt er an Spieler B sämtliche Karten, an Spieler C sämtliche Schlüssel.
Im zweiten Schritt wählt Spieler C 10 aus den Schlüsseln 10 aus, die er an Spieler A zurückgibt, sowie 10 an Spieler B.
Da A und B einen vollständigen Kartensatz besitzen, können sie durch einfaches Testen, welche Karten sich durch diese Schlüssel entschlüsseln lassen, ihr Blatt ermitteln.
Nun teilt Spieler A Spieler B mit, welche Karten er besitzt - allerdings natürlich nur die verschlüsselte Variante. Spieler B kann mit diesen Informationen nix anfangen, da er nur seine 10 Schlüssel hat. Zusammen mit seinem Blatt (und dem vollständigen Satz verschlüsselter Karten, über den er verfügt) kann er jedoch herausfinden, welche 12 Karten noch nicht verteilt worden sind.
Von diesen wählt er 10 und schickt sie an Spieler C. Da dieser sämtliche Schlüssel hat, kann er die auf jeden Fall entschlüsseln.
Damit wären dann schon einmal 30 der 32 Karten verteilt. Für die letzten beiden wirds noch mal richtig lustig...
Wenn Spieler A oder C die letzten beiden Karten erhalten soll ist es einfach, dann schickt B ihnen einfach die verschlüsselten Karten zu (beide verfügen ja über komplette Schlüsselsätze).
Wenn jedoch B diese beiden Karten entschlüsseln soll, muss zunächst Spieler A Spieler C mitteilen, welche Schlüssel er im Endeffekt benutzt hat (C kann mit dieser Information nichts anfangen, er kennt nur die 10 verschlüsselten Karten, die er für sich entschlüsselt hat). Dieser kann das mit seinen eigenen benutzen Schlüsseln kombinieren und an Hand des vorliegenden kompletten Schlüsselsatzes ermitteln, welche 12 Schlüssel noch nicht benutzt worden sind. Diese Information schickt er nun an B weiter, wodurch der das notwendige Werkzeug erhält, die letzten beiden Karten zu entschlüsseln.
Der Vorteil ist, dass man damit auf jeden Fall (die Kommunikation zwischen den einzelnen Beteiligten mal ausgenommen) ein sicheres Verfahren hat, da man zur Verschlüsselung der Karten auch One-Time-Pads, deren Schlüssellänge der zu verschlüsselnden Information entspricht, verwenden könnte.
Nachteil, das Verfahren ist kompliziert und erfordert sehr viel Kommunikation untereinander, dürfte also auch n gutes Stück langsamer laufen.
So... Und jetzt dürft ihr euch dran verlustieren und suchen, ob ich irgendwo noch was übersehen hab, das die ganzen Gedanken zunichte macht. Ich mein, man verliert da doch leicht den Überblick, aber ich glaub nicht, dass ein Spieler dabei ist, der von irgendeiner verschlüsselten Karte den Schlüssel hat und weiß, an welchen Spieler die gegangen ist...
__________________
Das ist keine Signatur.
|
|
|
24.10.2006 18:59 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
Du hast recht, das ist kompliziert
Auf anhieb find ich keinen Fehler im Protokoll, aber beweisen daß es sicher ist wollte ich bei dem Ding auch nicht
|
|
|
24.10.2006 22:40 |
|
|
kurellajunior 
Support
Dabei seit: 07.09.2006
Beiträge: 42
Herkunft: Von hier
|
|
Coole Idee! 
Aber was hindert A daran, nicht alle Karten wieder zu entschlüsseln? Keiner der REchner kann überprüfen, ob A nicht eine Kopie sämtlicher Schlüssel und verschlüsselter Karten behält. - edit - sehe gerade, dass A sämtliche Schlüssel behält! na dann ist die Sicherheit futsch - edit -
Daher ist die Sicherheit nicht gegeben (zumindest beim Kartengeber)
Du wirst nicht drumherum kommen, dass tatsächlich alle drei Ihre Finger im Spiel haben müssen beim verschlüsseln.
Ansonsten lässt sich Dein System ebenfalls problemlos auf n Spieler aufbohren. Die Rolle, die Dein Spieler C hat, können beliebig viele Spieler inne haben.
Jan
|
|
|
25.10.2006 09:30 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
A hat zwar alle Karten und Schlüssel (und damit auch die verschlüsselten Karten), weiss aber nicht wie C verteilt.
A erhält von C zufällig 10 Karten, und wie der Rest verteilt ist weiss A nicht.
|
|
|
25.10.2006 13:31 |
|
|
kurellajunior
Support
Dabei seit: 07.09.2006
Beiträge: 42
Herkunft: Von hier
|
|
:ditsch:
Na denn. sieht gut aus. Dann ist es wirklich ohne Problem auf beliebig viele Teilnehmer aufbohrbar.
Und ab einer bestimmten Teilnehmerzahl sogar zwingend besser als der von Peter vorgeschlagene, da nur eine Verschlüsselung stattfindet.
Um das Trial and Error-verfahren beim entschlüsseln zu optimieren, könnten die Karten und Schlüssel indiziert werden, dann wissen alle immer sofort, welcher Schlüssel auf welche Karte anzuwenden ist (so sie beides haben)
|
|
|
25.10.2006 17:46 |
|
|
Crotaphytus
Mitglied
Dabei seit: 18.09.2006
Beiträge: 45
|
|
| Zitat: |
| Auf anhieb find ich keinen Fehler im Protokoll, aber beweisen daß es sicher ist wollte ich bei dem Ding auch nicht |
Genau so gehts mir auch...
Mir ist auch grad noch eingefallen, dass man ein paar der "Rückmeldungen", die hin und wieder auftauchen, eigentlich gar nicht braucht, da das (wenn ich das jetzt nicht falsch im Kopf hab) ja eigentlich schon Informationen sind, die der betreffende Spieler bereits hat. Vermutlich kann man da also noch ein paar Sachen optimieren.
__________________
Das ist keine Signatur.
|
|
|
26.10.2006 00:31 |
|
|
|
