Hoy, Bob, un colega mío, reveló accidentalmente que su contraseña contiene a . Alice se rió, pero entonces también dijo inadvertidamente su contraseña hace no contienen cualquier a .
¿Quién ha regalado más sobre su contraseña? En otras palabras, ¿la contraseña de quién es ahora más fácil de adivinar?
EDITAR: He hecho a propósito no proporcionó información sobre la longitud de cualquier contraseña, o incluso la longitud máxima. Se puede suponer que el máximo la longitud sea ilimitada. Es decir, que la variable m que representa la longitud máxima de la contraseña en cualquier fórmula, tiende a ser infinitiva.
EDIT2: Elegí "Alice" y "Bob" como homenaje/referencia a los problemas de los deberes de los libros de mi curso de licenciatura. Pero esto sucedió realmente. Un colega mío tiene un defecto a en su teclado.
EDIT3: Aquí está mi puñalada en la pregunta a la que llegué con mis colegas durante el almuerzo de ayer:
Escribamos las fórmulas para el número de contraseñas posibles dado un alfabeto de tamaño entero $\alpha$ y una longitud máxima de la contraseña de $m$
$\sum_{n=1}^m \alpha^n$
He llegado a esta conclusión sumando " $\alpha$ contraseñas de longitud 1" + " $\alpha^2$ contraseñas de longitud 2" + ... + " $\alpha^m$ contraseñas de longitud $m$ ".
Ahora, Alice ha revelado que no tiene un a en cualquier parte de su contraseña. Ella ha reducido el tamaño del alfabeto al atacante en 1. Así que el número total de contraseñas para ella es:
$N_{Alice}=\sum_{n=1}^m (\alpha-1)^n$
El número total de contraseñas posibles de Bob también ha disminuido:
$N_{Bob}=\sum_{n=1}^m \alpha^n -\sum_{n=1}^m (\alpha-1)^n$
En otras palabras, $N_B$ ha disminuido exactamente lo mismo que el número de contraseñas posibles para Alice, que tienen la carta a .
Ahora, si $m$ es [el valor totalmente irreal de] 1, Alice ha regalado claramente su contraseña por completo, mientras que Bob todavía tiene $\alpha - 1$ total de contraseñas.
Pero, como intuición como $m$ aumenta hacia el infinito, creo que $N_{Alice} << N_{Bob}$ Así que creo que ahora es Alice quien tiene más posibilidades de que su contraseña sea forzada.
Mi cálculo es un poco inestable :-) así que aún no sé si es cierto que $N_{Alice} << N_{Bob}$ como $m$ tiende al infinito. Si se reabre esta pregunta, quizás alguien pueda ayudarme.
EDIT4: El ensayo y error en un programa sencillo parece confirmar mi intuición. Para un tamaño de alfabeto de 26, si la longitud máxima de la contraseña es 17, Bob ha regalado más. Si es 18, gana (Alice ha regalado más).
5 votos
Suponiendo que Alice y Bob no sean amigos tuyos de verdad, esto huele a deberes del curso de Introducción a la Criptografía o algo parecido. Dado que esto es efectivamente una tarea, ¿qué has probado?
0 votos
Depende del alfabeto y de la longitud media de las contraseñas. Por ejemplo, en un alfabeto con sólo dos caracteres $a,b$ la contraseña de Alice debe tener la forma $b\dots b$ , por lo que es fácil de adivinar.
0 votos
Dada una contraseña de longitud $n$ que puede contener cualquiera de los siguientes elementos $m$ símbolos únicos cualquier número de veces: La probabilidad de adivinar la contraseña de Bob es $1-\left(\frac{m-1}{m}\right)^n$ . La probabilidad de adivinar la contraseña de Alices es $\left(\frac{m-1}{m}\right)^n$ . Así que esta respuesta depende básicamente de los valores de $m$ y $n$ .
0 votos
@barakmanos: seguro que suena a tarea, pero sorprendentemente no lo es' Esto ocurrió hace unas horas en una reunión. Pero Bob y Alice son un homenaje a los deberes, sí.
0 votos
Sólo una nota rápida, no creo que se pueda asumir una "longitud máxima de la contraseña del infinito", porque un "máximo" es algo obtenido, y si algo es ilimitado, entonces el máximo simplemente no existe. Creo que quieres decir que la contraseña tiene una longitud ilimitada.
0 votos
Eso no es exactamente lo que he dicho, he dicho la longitud máxima, digamos la variable
mes infinito. Quise decir que se debería obtener una respuesta haciendomir hacia el infinito. Pero bueno, voy a editar. Si se reabre la pregunta me gustaría responderla. ¿O debería añadirlo como una edición?