algorithm - tus - ¿Cómo generar un código/número de verificación?

obtén un código de seguridad de uno de tus dispositivos (9)

Debo tener un número razonable de combinaciones posibles (digamos 1M)
El código debe ser lo más corto posible para evitar errores del usuario

Bueno, si quieres que tenga al menos un millón de combinaciones, entonces necesitas al menos seis dígitos. ¿Es eso lo suficientemente corto?

Estoy trabajando en una aplicación donde los usuarios tienen que hacer una llamada y escribir un número de verificación con el teclado de su teléfono.

Me gustaría poder detectar si el número que escriben es correcto o no. El sistema telefónico no tiene acceso a una lista de números válidos, sino que validará el número contra un algoritmo (como un número de tarjeta de crédito).

Estos son algunos de los requisitos:

Debe ser difícil escribir un código aleatorio válido
Debe ser difícil tener un código válido si hago un error tipográfico (tranposición de dígitos, dígito incorrecto)
Debo tener un número razonable de combinaciones posibles (digamos 1M)
El código debe ser lo más corto posible para evitar errores del usuario

Teniendo en cuenta estos requisitos, ¿cómo generarías ese número?

EDITAR:

@Haaked: el código tiene que ser numérico, porque el usuario lo escribe con su teléfono.

@matt b: en el primer paso, el código se muestra en una página web, el segundo paso es llamar y escribir el código. No sé el número de teléfono del usuario.

Folowup: He encontrado varios algoritmos para verificar la validez de los números (Ver este interesante proyecto de Google Code: checkDigits ).

¿Tiene que ser solo números? Podrías crear un número aleatorio entre 1 y 1M (sugeriría aún más alto) y luego Base32 lo codificará . Lo siguiente que debe hacer es Hash ese valor (utilizando un valor secreto de sal) y base32 codificar el hash. Luego, agregue las dos cuerdas juntas, tal vez separadas por el tablero.

De esta forma, puede verificar el código entrante de forma algorítmica. Simplemente toma el lado izquierdo del código, hash usando su sal secreta y compara ese valor con el lado derecho del código.

Cuando está creando el código de verificación, ¿tiene acceso al número de teléfono de la persona que llama?

De ser así, utilizaría el número de teléfono de la persona que llama y lo ejecutaría a través de una función hash para que pueda garantizar que el código de verificación que dio a la persona que llamó en el paso 1 es el mismo que están ingresando en el paso 2 (para asegurarse no están usando el código de validación de un amigo o simplemente hicieron una conjetura muy afortunada).

Acerca del hashing, no estoy seguro de si es posible tomar un número de 10 dígitos y obtener un resultado hash que sería <10 dígitos (supongo que tendrías que vivir con una cierta cantidad de colisión) pero creo esto ayudaría a asegurar que el usuario sea quien dice ser.

Por supuesto, esto no funcionará si el número de teléfono utilizado en el paso 1 es diferente al que están llamando en el paso 2.

Para combinaciones de 1M, necesitarás 6 dígitos. Para asegurarse de que no haya códigos accidentalmente válidos, sugiero 9 dígitos con una posibilidad de 1 / 1.000 de que funcione un código aleatorio. También sugiero usar otro dígito (10 en total) para realizar una verificación de integridad . En cuanto a los patrones de distribución, aleatorio será suficiente y el dígito de verificación asegurará que un solo error no dará como resultado un código correcto.

Editar: Aparentemente, no leí completamente tu solicitud. Usando un número de tarjeta de crédito, puede realizar un hash (MD5 o SHA1 o algo similar). Luego truncas en un lugar apropiado (por ejemplo, 9 caracteres) y conviertes a la base 10. Luego agregas los dígitos de control y esto debería funcionar más o menos para tus propósitos.

Parece que tiene el requisito tácito de que debe determinarse rápidamente, a través del algoritmo, que el código es válido. Esto podría descartar que simplemente entregue una lista de números de una sola vez.

Hay varias formas en que las personas han hecho esto en el pasado.

Crea una clave pública y una clave privada. Codifique los números 0-999,999 con la clave privada y distribuya los resultados. Necesitará ingresar algunos números aleatorios para que el resultado salga a la versión más larga, y deberá convertir el resultado de la base 64 a la base 10. Cuando obtenga un número ingresado, conviértalo nuevamente a base64, aplique la clave privada y vea si los números interetantes están por debajo de 1,000,000 (descarte los números aleatorios).
Use una función hash reversible
Use los primeros millones de números de un PRN sembrado en un valor específico. La función de "comprobación" puede obtener la semilla, y saber que los próximos millones de valores son buenos. Puede generarlos cada vez y verificar uno por uno cuando se recibe un código, o al inicio del programa almacenarlos todos en una tabla, ordenarlos y luego usar la búsqueda binaria (máximo de comparaciones) ya que un millón de enteros no es mucho del espacio.

Hay muchas otras opciones, pero estas son comunes y fáciles de implementar.

-Adán

Quieres segmentar tu código. Parte de esto debería ser un CRC de 16 bits del resto del código.

Si todo lo que quiere es un número de verificación, simplemente use un número de secuencia (suponiendo que tenga un único punto de generación). De esa forma sabrá que no obtiene duplicados.

Luego, prefija la secuencia con un CRC-16 de ese número de secuencia Y alguna clave privada. Puede usar cualquier cosa para la clave privada, siempre y cuando la mantenga privada. Haga algo grande, al menos un GUID , pero podría ser el texto de War and Peace del proyecto Gutenberg . Solo necesita ser secreto y constante. Tener una clave privada impide que las personas puedan falsificar una clave, pero el uso de una CR de 16 bits hace que sea más fácil romperla.

Para validarlo, solo divida el número en sus dos partes y luego tome un CRC-16 del número de secuencia y la clave privada.

Si desea oscurecer más la parte secuencial, divida el CRC en dos partes. Coloque 3 dígitos en la parte delantera y 2 en la parte posterior de la secuencia (cero almohadilla para que la longitud del CRC sea consistente).

Este método le permite comenzar con teclas más pequeñas también. Las primeras 10 claves serán de 6 dígitos.

Suponiendo que ya sabe cómo detectar qué tecla golpeó el usuario, esto debería ser factible de manera razonablemente fácil. En el mundo de la seguridad, existe la noción de una contraseña de "una sola vez". Esto a veces se conoce como una "contraseña desechable". Normalmente, estos están restringidos a los valores ASCII (fácilmente tipables). Entonces, [a-zA-z0-9] y un montón de símbolos fácilmente tipables. como coma, punto, punto y coma y paréntesis. En su caso, sin embargo, probablemente quiera limitar el rango a [0-9] y posiblemente incluya * y #.

No puedo explicar todos los detalles técnicos de cómo se generan (o funcionan) estos códigos de un solo uso. Hay algunas matemáticas intermedias detrás de esto, que yo eliminaría sin revisarlo primero. Baste decir que usa un algoritmo para generar una secuencia de contraseñas de un solo uso. ¡No importa cuántos códigos previos conozcas, el siguiente debería ser imposible de adivinar! En su caso, simplemente usará cada contraseña en la lista como el código aleatorio del usuario.

En lugar de dejar de explicar los detalles de la implementación por mí mismo, lo dirigiré a un artículo de 9 páginas donde puede leerlo usted mismo: https://www.grc.com/ppp.htm

Usted se vinculó al proyecto de dígitos de verificación , y el uso de la función "codificar" parece una buena solución. Dice:

encode puede arrojar una excepción si se le pasan datos ''malos'' (por ejemplo, no numéricos), mientras que verify solo devuelve verdadero o falso. La idea aquí es que la codificación normalmente obtiene sus datos de fuentes internas ''confiables'' (una clave de base de datos, por ejemplo), por lo que debería ser bastante habitual, de hecho, es excepcional que se envíen datos incorrectos.

Parece que podría pasar la función de codificación a una clave de base de datos (5 dígitos, por ejemplo) y podría obtener un número que cumpliría con sus requisitos.

Después de algunas investigaciones, creo que seguiré con la fórmula ISO 7064 Mod 97,10 . Parece bastante sólido ya que se usa para validar IBAN (Número de cuenta bancaria internacional).

La fórmula es muy simple:

Tome un número: 123456
Aplique la siguiente fórmula para obtener la suma de comprobación de 2 dígitos: mod(98 - mod(number * 100, 97), 97) => 76
Número de Concat y suma de comprobación para obtener el código => 12345676
Para validar un código, verifique esa mod(code, 97) == 1

Prueba :

mod(12345676, 97) = 1 => BUENO
mod(21345676, 97) = 50 => ¡MALO!
mod(12345678, 97) = 10 => ¡MALO!

Aparentemente, este algoritmo capta la mayoría de los errores.

Otra opción interesante fue el algoritmo Verhoeff . Tiene solo un dígito de verificación y es más difícil de implementar (en comparación con la fórmula simple anterior).