encryption - Criptografía para juego de cartas P2P.
cryptography playing-cards (6)
El esquema tradicional de en.wikipedia.org/wiki/Mental_poker es una exageración. Tu situación es mucho más fácil ya que no hay un mazo compartido . Podrías hacer algo como esto:
El jugador A toma sus cartas y las cifra con clave Ka. Los envía a B, que los baraja, los cifra con la clave Kb. Cada vez que A quiere jugar una carta, le pide a B el descifrado (Kb) de la siguiente. A descifra esto para encontrar qué carta robó. Al final, A y B revelan Ka y Kb y los comparan con el registro del juego, lo que debería evitar las trampas.
Actualizado: Reflexionando, aquí hay una solución más simple: como antes, el jugador A encripta sus cartas y las envía a B. B las baraja. Cuando A quiere una carta, le dice a B de qué mazo está robando. B devuelve la tarjeta (encriptada) de la pila apropiada.
Estoy considerando escribir una adaptación de computadora de un juego de cartas semi-popular. Me gustaría que funcione sin un servidor central, y estoy tratando de encontrar un esquema que haga imposible el engaño sin tener que confiar en el cliente.
El problema básico que veo es que cada jugador tiene varios montones de cartas (mazo de robo, mano actual y mazo de descarte). Debe ser imposible para cualquiera de los jugadores alterar la composición de estas pilas, excepto cuando lo permitan las reglas del juego (es decir, robar o descartar cartas), ni los jugadores deben saber qué hay en sus pilas o las de sus oponentes.
Siento que debería haber alguna forma de usar algo como la criptografía de clave pública para lograr esto, pero sigo encontrando agujeros en mis esquemas. ¿Alguien puede sugerir un protocolo o indicarme algunos recursos sobre este tema?
[Editar] Ok, así que he estado pensando un poco más en esto, y he aquí una idea que se me ha ocurrido. Si puedes hacer agujeros, por favor házmelo saber.
En el momento de la reproducción aleatoria, un jugador tiene una pila de cartas cuyo valor les es conocido. Toman estos valores, concatenan una sal aleatoria para cada uno, luego los trocean. Registran las sales, y pasan los hashes a su oponente.
El oponente concatena una sal propia, vuelve a hacer hash, luego baraja los hashes y le devuelve el mazo al jugador original.
Creo que en este punto, el mazo ha sido aleatorio y ningún jugador puede tener ningún conocimiento de los valores. Sin embargo, cuando se roba una carta, el oponente puede revelar su sal, lo que permite al primer jugador determinar cuál es el valor original, y cuando se juega la carta, el jugador revela su propia sal, lo que le permite verificar el valor de la carta.
Esta es una adaptación del enfoque de Bellotas:
preparar:
cada jugador tiene su mazo (juego (s) de cartas totalmente ordenado) ... esas barajas son públicas y están en orden natural
cada jugador necesita un par de llaves asimétricas (firma), claves públicas intercambiadas
Ahora al problema de la aleatoriedad:
dado que un jugador no puede ver por adelantado qué cartas robará, el oponente será la fuente de nuestra aleatoriedad:
cuando necesitamos un valor aleatorio, le pedimos a nuestro oponente ... los valores aleatorios se almacenan junto con los movimientos que se verifican más adelante
Como nuestro oponente puede no ser capaz de manipular el orden de nuestras cartas, tomamos ese valor recibido al azar y lo firmamos con nuestra clave privada ... el valor de esa firma será nuestra semilla RNG (impredecible para el oponente), y más adelante el oponente puede verificar la firma contra el número aleatorio que él / ella generó (así que también almacenamos las firmas, y las intercambiamos después del juego)
ya que podemos hacer este intercambio de números aleatorios en cada ronda, los valores aleatorios no son conocidos por adelantado por el jugador -> no se asoma al orden de nuestra pila
y como ahora tenemos un RNG sembrado, podemos obtener valores aleatorios derivados de ese valor aleatorio "compartido" ... de esa manera podemos extraer cartas "aleatorias" (completamente deterministas, con resultados verificables repetibles) de nuestro mazo ... el mazo / stack no tendrá que ser barajado, ya que podemos obtener posiciones aleatorias de nuestro RNG
Ya que todos hemos intercambiado valores aleatorios, las firmas, los mazos iniciales (en orden total) y todos los movimientos, podemos volver a jugar todo el juego y verificar si hay irregularidades.
Quiero describir una idea que me vino a la mente con bastante rapidez. No sé si satisface todas sus necesidades, así que no dude en comentar sobre esto.
Supongamos que el jugador A tiene las tarjetas A1 , A2 , A3 , ... de un conjunto representado por los números 0 , 1 , ... N-1 . Estas tarjetas también pueden estar separadas en pilas, pero esto no cambia lo siguiente.
En lugar de manejar estas tarjetas con una sola lista [A1, A2, A3, ...] , puede usar dos de ellas [A1_a, A2_a, A3_a, ...] y [A1_b, A2_b, A3_b, ...] donde uno está con el jugador A y el otro con el jugador B Se generan de tal manera, que cada una es aleatoria (en el rango 0...N-1 ) pero ambas están correlacionadas de modo que A1_a + A1_b = A1 , A2_a + A2_b = A2 , ... (todas las operaciones módulo N ).
- Por lo tanto, ningún jugador conoce realmente las cartas sin acceso a la pila complementaria (es decir, no puede cambiar sus cartas razonablemente)
- Siempre que necesite saber una carta, ambos jugadores muestran su valor correspondiente y usted agrega esos módulos
N - puedes implementar cosas como "robar una carta" con bastante facilidad, ambas pilas solo tienen que ser tratadas de la misma manera
Si bien un servidor central sería la forma más fácil, si quieres evitarlo, puedes usar un sistema distribuido, en el que todos los jugadores juegan un juego de almacenamiento para las cubiertas de otros jugadores (no para él o para su oponente, sino para cualquier otro). . Creo que Limewire y Bittorrent funcionan de esta manera, por lo que puede obtener algunas ideas al estudiar esas fuentes.
Tal vez los jugadores podrían intercambiar hashes de sus pilas al comienzo del juego.
Luego, cuando se completa el juego, los jugadores intercambian la composición real que tenían sus pilas al comienzo del juego. Ahora el cliente del jugador puede verificar que coincida con el hash que recibió antes y luego verificar que todos los movimientos que se hicieron funcionen con esos mazos.
El único problema es cómo se barajan inicialmente las cubiertas. Debería asegurarse de que el jugador no pueda comenzar su mazo en el orden que elija.
Tal vez los jugadores generen su orden de mazo inicial obteniendo aleatoriedad de alguna fuente específica ... pero de una manera que el otro jugador no pueda determinar cuáles son las órdenes de mazo del otro jugador hasta el final del juego, pero aún puede verificar que el jugador No juguetearon sus cubiertas. No estoy seguro de cómo podrías lograr eso.
Editar:
Otra idea. Tal vez en lugar de generar los mazos aleatorios al comienzo del juego, podrían generarse a medida que el juego continúa.
Cada vez que un jugador necesita tomar una nueva carta de la pila, su oponente les envía una semilla al azar que se utiliza para elegir cuál será la próxima carta.
De esa manera, el usuario no tiene forma de saber en qué orden seguirán las tarjetas en sus mazos.
No estoy seguro de cómo impedirías que el otro jugador pudiera decir qué carta elegirían para su oponente. Si la semilla se usó para seleccionar una carta de algún tipo de lista ordenada al azar de las que el oponente tenía un hash para verificar ... podrían revisar todas las combinaciones posibles de cartas y descubrir cuál de ellas coincidía con el hash, por lo que capaces de dictar qué carta querían que el otro jugador robara enviándoles una semilla que haría que esa carta fuera seleccionada.
Tu problema es el famoso en.wikipedia.org/wiki/Mental_poker en criptografía (esta fue una de mis partes favoritas de la clase de criptografía en la universidad) . Es posible, y ha sido resuelto (en parte, como todas las cosas criptográficas, por Ron Rivest ) , siempre y cuando no te importe un gran impacto en el rendimiento.
Compruebe la página wiki para más detalles.