Lo que está describiendo aquí es un bucle anidado:
Para hashed_password en contraseñas:
para dictionary_word en el diccionario:
If hash (dictionary_word) == hashed_password
volver dictionary_word y salir
Si establecemos el número de contraseñas en la lista para que sea [math] n [/ math], el número de palabras en el diccionario para que sea [math] m [/ math], el tiempo que lleva descifrar una palabra del diccionario por [math] t [/ math], y el tiempo que lleva hacer una comparación por [math] c [/ math], su tiempo de ejecución se convierte en [math] n * m * t * c [/ math]. La única razón por la que puedo pensar dónde tiene sentido trabajar así es si cada contraseña de la lista se ha cifrado con Salt (que debería ser el caso para una aplicación real, pero supongo que esta es una pregunta de tarea).
- ¿Cómo es que Stack Exchange no utiliza una conexión segura (TLS) a pesar de que es un sitio web popular con una comunidad activa de usuarios?
- ¿Qué conocimiento tienen los desarrolladores web de pila completa sobre ciberseguridad, cifrado, algoritmos, etc., o son temas separados?
- ¿Cuál debería ser mi carrera profesional para ser un experto en seguridad cibernética?
- ¿Kali Linux tiene RDP disponible? ¿Cómo edito esa configuración si es así?
- ¿Qué es lo más perjudicial que uno podría esperar / hacer (por ejemplo, ataques DDOS masivos) justo antes de las elecciones de 2016?
Lo que está haciendo actualmente es comparar cada contraseña con todas las palabras del diccionario. Como las palabras del diccionario no cambian, tendría más sentido comparar cada palabra del diccionario con todas las contraseñas.
Considere la siguiente mejora:
hashed_dictionary = []
para dictionary_word en el diccionario:
hashed_dictionary.add ({hash (dictionary_word), dictionary_word})
para candidato_contraseña en hashed_dictionary:
si candidato_contraseña está en hashed_passwords:
volver dictionary_word
Su tiempo de ejecución ahora se reduce a [matemática] m * t + m * n * c [/ matemática] que ya mejorará su tiempo de ejecución. El segundo término ([matemática] m * n * c [/ matemática]) es el costo de comparar dos listas, que es un problema informático de libros de texto. Puede buscar algoritmos en línea para mejorar aún más el tiempo de ejecución de esta parte. Por ejemplo, si ordena una de las listas, puede reducir el tiempo de ejecución a [matemáticas] m * t + m * log_2 (m) + log_2 (m) * n * c [/ matemáticas] o [matemáticas] m * t + n * log_2 (n) + m * log (n) * c [/ math] (según la lista que haya decidido ordenar). Estoy seguro de que si busca en línea puede encontrar algoritmos aún mejores para comparar las listas.
Dos comentarios finales:
- Tenga en cuenta que un orden significativo no tiene que ser lexicográfico. Puede valer la pena ordenar la lista hashed_dictionary de acuerdo con la probabilidad de cada contraseña (tendrá que definir una métrica para eso, pero confío en que esto esté dentro de sus capacidades).
- Puede ser suficiente no hacer una comparación completa entre palabras. Por ejemplo, puede comenzar comparando todos los prefijos y crear una nueva lista de candidatos para una inspección más profunda.
Editar: naturalmente, alguien ya le preguntó a Quora ¿Cuál es el algoritmo de clasificación más rápido?