21 agosto 2008

La paradoja del cumpleaños

Según la teoría matemática, si juntamos a 23 personas en una habitación existe en torno a un 50% de posibilidades de que 2 de ellas tengan el mismo cumpleaños. Si en vez de 23 juntamos 75 la probabilidad sube al 99.9%. ¡Ojo!, no se trata de que alguien tenga el mismo cumpleaños que nosotros (en ese caso impondríamos como condición una fecha concreta lo que supone una restricción más fuerte) sino que dos personas cualesquiera coincidan en su cumpleaños (puede resultar ser cualquier fecha). Las matemáticas que se encuentran detrás de esto pueden resultar complejas si no se ha estudiado nada de probabilidad, pero vamos a intentar explicarlas. Para empezar debemos tener claro cuantos posibles emparejamientos se pueden dar en una sala de n personas: Por ejemplo, en una sala con 23 personas hay 253 parejas posibles. La probabilidad de que una única pareja tenga el mismo cumpleaños es: Su complementario es la probabilidad de que una única pareja NO tenga el mismo cumpleaños: La probabilidad de que NO exista ninguna pareja con un cumpleaños coincidente es: Dado que la base es inferior a 1 esta probabilidad decrecerá conforme aumente el número de personas de la muestra, o dicho de otra manera: cuanta más gente haya más difícil será que no se de una coincidencia con los cumpleaños. Dicho lo cual, la probabilidad (P) de que SÍ se de una coincidencia es la complementaria a la anterior, es decir: Si le damos a P el valor 0.5 (límite a partir del cual las probabilidades de encontrar una coincidencia se ponen de nuestro lado) y despejamos la n, obtenemos precisamente 23. Hasta ahí la teoría, sin embargo hay que advertir (a los que pretendan lucirse en una fiesta) de que la práctica difiere bastante ya que las fechas de nuestros nacimientos hace ya un tiempo que dejaron de ser equiprobables porque los médicos programan los partos cada vez con más frecuencia ¡y no los programan para los fines de semana, lo que rompe la equiprobabilidad!. Pero el interés del resultado que hemos obtenido no se limita a la anécdota en una reunión sino que si generalizamos la fórmula veremos que tiene interesantes aplicaciones en el campo de la seguridad informática, entre otros. Así, si denominamos p a la probabilidad de que a una única pareja le pase algo y p (añádase una barra superior) a su complementaria, es decir a la probabilidad de que a esa pareja no le ocurra lo que estamos evaluando, tenemos entonces que la fórmula anterior generalizada es:De esta manera P es la probabilidad de que se de un suceso cuando el número de elementos de la base de muestra es n. Si despejamos la n la fórmula queda de la siguiente manera:Para el ejemplo del cumpleaños querríamos hallar el número n de personas a partir de las cuales P>0.5. Para ello sustituiríamos P por 0.5, y p (con barra arriba) por 364/365 y veríamos que n es efectivamente 23. Pero pongamos otro ejemplo más interesante del mundo de la seguridad informática. Supongamos que nos llega un comercial para vendernos un sistema de reconocimiento facial. El cacharro se colocaría a la entrada del recinto y sustituiría a la clásica máquina de fichar, lo que eliminaría las colas cuando los 5.000 empleados de nuestra organización llegasen cada mañana. El comercial nos dice muy seguro de si mismo que la máquina tiene una probabilidad de confundir a dos personas de 1 entre 1.000.000 (es decir, una probabilidad de acierto de 0.999999) , por lo que se queda atónito cuando rechazamos su sistema por inseguro. ¿Por qué es inseguro?, porque si aplicamos los datos anteriores a la fórmula (teniendo en cuenta que p(barra) es 0.999999) veremos que las posibilidades de error del equipo son superiores a 0.5 una vez que han pasado por ella 1178 empleados. Dicho de otra manera, no habría manera de acabar la mañana sin que la maquinita se equivocase. Un truco muy útil es que, cuando tratamos con grandes números, se puede aproximar la fórmula general a esta otra: Siendo N el inverso de p (probabilidad de ocurrencia con una única pareja de elementos). En el caso del cumpleaños N sería 365, por lo que la aproximación daría n=19.10 y en el caso del reconocimiento facial N sería 1.000.000 y obtendríamos una aproximación de n=1000. Esta aproximación se utiliza mucho en el mundo de la criptografía donde la paradoja del cumpleaños se tiene muy presente. Por ejemplo, supongamos que tenemos una tabla de contraseñas cifradas con un algoritmo de hash de 64 bits y estamos tranquilos porque creemos que un ataque de diccionario tendría que hacer 2^64 intentos antes de dar con nuestra contraseña... pues no, nada más lejos de la realidad ya que la paradoja del cumpleaños nos demuestra que el atacante seguramente dará con nuestra contraseña cuando haya hecho poco más de 2^32 intentos. Como se puede ver por todo lo anterior la paradoja del cumpleaños trasciende de lo meramente anecdótico convirtiéndose en una herramienta importantísima de cualquier ingeniero de seguridad que se precie.