Sobre la generación de los grupos aleatoriamente

El procedimiento que seguimos en la ultima clase para elegir los grupos es en realidad un proceso muy estudiado y permite que dos partes que no se fían una de la otra puedan generar un numero aleatorio de forma que ambas estén de acuerdo que se ha generado correctamente y sin trampas.

Por si a alguien le interesa la explicación de por que funciona la dejo aquí junto con el programa usado para que podáis examinarlo o usarlo para otras cosas.

Se necesita un programa que genere los números aleatorios o en nuestro caso la lista desordenada de alumnos con un generador pseudoaleatorio (como el que tenemos en cualquier lenguaje con la funcion rand()). Los numeros siguen un desorden poco previsible pero que en realidad es totalmente determinista con una semilla que se le pasa como entrada al programa. La pagina que genera el PHP que os pongo hace eso, genera una desordenación de vuestra lista que depende totalmente de un numero. Si pones los mismos números de entrada siempre genera lo mismo y lo podéis comprobar. Sin embargo con que cambie un solo bit de la semilla el resultado es una lista totalmente diferente y que no hay manera de predecir (vamos no se cumple que para numeros cercanos las listas son parecidas, en ese sentido la lista es parcida a un hash)

Así que el problema se reduce a que entre dos partes que no se fián entre si puedan decidir de forma aleatoria la semilla y las dos estén de acuerdo en que la otra no les puede hacer trampa.

Para esto solo hace falta que cada parte genere un numero aleatorio sin saber que numero va a generar la otra parte. Luego se mezclan los dos números con un XOR binario y así cada bit es aleatorio con tal de que cualquiera de los dos números elegidos sea aleatorio. Y como cada parte no sabe como va a generar su numero la otra parte el otro numero siempre es aleatorio. A cada parte le vale con poder garantizar que la otra parte ha generado el numero sin saber cual es el que va a generar ella.

Una forma de conseguir esto es como se hizo en clase. Una parte primero (yo en ese caso) escribe un numero en un papel sin que la otra lo vea. Asi se garantiza que ese numero se ha generado sin saber el segundo.
La segunda parte genera un numero y lo dice en voz alta. Los dos numeros se les hace XOR y se usan para alimentar al generador.

Si cualquiera de las partes sabe de antemano el numero que la otra va a generar y tiene disponible el programa para generar la lista es trivial elegir el numero para conseguir el orden que quieres. Por eso es muy importante en este proceso que cada uno elija el numero sin saber el que elegira el otro y que no pueda cambiarlo al saber el numero que elige el otro.

Una forma de hacer trampa es por supuesto que las dos partes estén de acuerdo a la hora de elegir el numero... pero eso no tiene sentido si no se fían entre si. En nuestro caso se puede pensar que el profesor este compinchado con un alumno. Para eso es facil extender el algoritmo haciendo que se elijan mas numeros aleatorios entre varios alumnos y que se haga el XOR de todos. O bien que no elija yo a quien tiene que decir el numero aleatorio sino que lo elijais por consenso (o que lo traigais preparado de antes pero entonces esta el problema de garantizar que el numero no llegue a mis manos porque entonces podría haber preparado mi numero teniendo en cuenta ese)

Por otra parte no importa que forma de generar el numero siga cada parte siempre que sea desconocida para la otra. Lo que si que importa es que la parte que genera el numero primero no pueda cambiarlo justo en el ultimo momento una vez que el otro diga su numero... y eso no pudo pasar el ultimo dia, verdad?

Para garantizar ese tipo de cosas puede usarse la criptografia. De hecho puede usarse algo que ya sabeis, los hashes. Por ejemplo

Digamos que yo genero ahora mismo el numero del profesor que usare en la siguiente clase. Y para la proxima clase que haya un problema por grupos os pedire que digais uno en voz alta.
Para que todo funcione tengo que garantizar que vosotros lo generis sin saber el que he generado yo o sea que no puedo deciroslo. Pero para que vosotros os fieis tengo que probaros que yo no cambio el numero que he generado ahora. Como os convenzo de que no cambio el numero en el ultimo momento una vez que ya se el vuestro sin deciros mi numero? Usando un hash. Os digo ahora mismo el hash MD5 del numero que acabo de generar.

Es este


0c4033c4ab2117e808f1b11a8181ef98


Para que podais verificarlo el proximo dia, ese en realidad es el MD5 del numero que he generado escrito en ASCII y sin salto de linea detras. Esto es que podreis verificar que el numero que introduzca en la proxima clase en mi casilla (llamemosle X) cumplira que


mikel$ echo -n "X" | md5
0c4033c4ab2117e808f1b11a8181ef98

mikel$ echo -n "X" | openssl dgst -md5
0c4033c4ab2117e808f1b11a8181ef98

mikel$ php
<?php $hash=md5('X'); echo $hash; ?>
0c4033c4ab2117e808f1b11a8181ef98


Asi que en la próxima clase os pediré un numero aleatorio y yo cumpliré mi promesa y usare el que he elegido que cumple eso.
No puedo hacer trampa y cambiar mi numero para conseguir la lista que yo quiera porque tengo que cumplir esa condicion. No puedo cambiar el programa porque es publico y esta ahi para que verifiqueis que con los numeros que se elijan salga lo que debe.
Y vosotros no podeis hacer trampa porque no sabreis mi numero hasta ese dia.

O hay alguna manera de que esto falle?

Eso es mas un problema de la otra asignatura, Seguridad en Sistemas Informaticos.
Podeis hacer trampas en este procedimiento?

Lo consideraremos un ejercicio de SSI

Digamos que a los primeros que demuestren que pueden hacer trampa y llevar preparado un numero que les beneficie para intentar que se elija ese numero y conseguir la lista deseada les daremos medio punto a sumar a la nota de SSI

Mas informacion en el foro de SSI