¿Cómo verificar el número con Bob sin que Eve lo sepa?

Debe verificar que su amigo, Bob, tenga su número de teléfono correcto, pero no puede preguntarle directamente. Debe escribir la pregunta en una tarjeta y dársela a Eve, quien se la llevará a Bob y le devolverá la respuesta. ¿Qué debe escribir en la tarjeta, además de la pregunta, para asegurarse de que Bob pueda codificar el mensaje para que Eve no pueda leer su número de teléfono?

Nota: Esta pregunta está en una lista de "preguntas de la entrevista de google". Como resultado, hay toneladas de versiones de esta pregunta en la web, y muchas de ellas no tienen respuestas claras o correctas.

Nota 2: La respuesta sarcástica a esta pregunta es que Bob debe escribir "llámame". Sí, eso es muy inteligente, 'fuera de la caja' y todo, pero no utiliza ninguna técnica de ese campo de CS donde llamamos a nuestro héroe "Bob" y su adversario de espionaje "Eva".

Actualización:
puntos de bonificación para un algoritmo que usted y Bob podrían completar razonablemente a mano.

Actualización 2:
Tenga en cuenta que Bob no tiene que enviarle ningún mensaje arbitrario, pero solo confirme que tiene su número de teléfono correcto sin que Eve pueda decodificarlo, lo que puede o no conducir a soluciones más simples.

Primero debemos suponer que Eva es solo pasiva. Con esto, quiero decir que sinceramente le envía la tarjeta a Bob, y lo que sea que ella le devuelva a Alice es la respuesta de Bob. Si Eve puede alterar los datos en una o ambas direcciones (y su acción permanece sin ser detectada), entonces todo vale.

(Para honrar las tradiciones de larga data, las dos partes honestas involucradas en la conversación se llaman Alice y Bob. En su texto, usted dijo "usted". Mi verdadero nombre no es "Alice", pero responderé como si escribiera que Alice quiere verificar el número de teléfono de Bob.)

La respuesta simple (pero débil) es usar una función hash. Alice escribe en la tarjeta: "devuélveme el hash SHA-256 de tu número de teléfono". SHA-256 es una función hash criptográfica que se considera segura, en lo que respecta a las funciones hash. Calcularlo a mano sería tedioso pero aún factible (eso es alrededor de 2500 operaciones de 32 bits, donde cada operación es una adición, un desplazamiento o rotación de palabras, o una combinación de bits a nivel de bits; Bob debería poder hacerlo en un día o entonces).

Ahora, ¿qué hay de débil en eso? SHA-256, al ser una función hash criptográfica, es resistente a las "preimágenes": esto significa que dada una salida hash, es muy difícil recuperar una entrada correspondiente (ese es el problema que enfrenta Eve). Sin embargo, "muy difícil" significa "el método más fácil es la fuerza bruta: probar posibles entradas hasta que se encuentre una coincidencia". El problema es que la fuerza bruta es fácil aquí: no hay tantos números de teléfono posibles (en América del Norte, eso es 10 dígitos, es decir, solo 10 mil millones). Bob quiere hacer las cosas a mano, pero no podemos suponer que Eva es tan limitada. Una PC básica puede probar algunos millones de hashes SHA-256 por segundo, por lo que Eve se realizará en menos de una hora (menos de 5 minutos si usa una GPU).

Este es un problema genérico: si Bob es determinista (es decir, para un mensaje dado de Alice, siempre devolverá la misma respuesta), Eve puede simularlo. Es decir, Eve sabe todo sobre Bob, excepto el número de teléfono, por lo que prácticamente maneja 10 mil millones de Bobs, que difieren solo por su número de teléfono supuesto; y ella espera que uno de los Bobs virtuales devuelva lo que el verdadero Bob haya devuelto. La falla afecta a muchos tipos de soluciones "inteligentes" que implican nonces aleatorios y cifrado simétrico y todo lo demás. Es una falla fuerte, y su raíz radica en la gran diferencia en el poder de cómputo entre Eve y Bob (ahora, si Bob también tuviera una computadora tan grande como la de Eve, entonces podría usar una cámara lentafunción hash mediante el uso de muchas iteraciones; de eso se trata más o menos el hashing de contraseñas, con el número de teléfono en lugar de la contraseña; ver bcrypt y también esta respuesta ).

Por lo tanto, una solución no débil debe involucrar algo de aleatoriedad por parte de Bob: Bob debe lanzar una moneda o lanzar dados repetidamente e inyectar los valores en sus cálculos. Además, Eve no debe ser capaz de desentrañar lo que hizo Bob, pero Alice debe poder hacerlo, por lo que parte de la información se transmite con confianza de Bob a Alice. Esto se denomina cifrado asimétrico o, al menos, acuerdo de clave asimétrica. El algoritmo más simple de esa clase para calcular, pero aún razonablemente seguro, es RSA con el relleno PKCS # 1 v1.5 . RSA puede usar como exponente público. Entonces el protocolo va así:$e = 3$

• Alice genera un gran número entero , donde y son enteros prime de tamaño similar, de manera que el tamaño de es suficiente para garantizar la seguridad (es decir, al menos 1024 bits, a partir de 2012). Además, Alice debe hacer arreglos para que y no sean múltiplos de 3.p q n p - 1 q - $n = pq$$p$$q$$n$$p-1$$q-1$

• Alice escribe en la tarjeta.$n$

• Bob primeras almohadillas de su número de teléfono en una secuencia de bytes, siempre que , tal como se describe por PKCS # 1 (que significa: 00 02 xx xx xx ... 00 bb bb bb .., donde 'BB' son los bytes que codifican diez el número de teléfono y el 'xx' son valores de bytes aleatorios distintos de cero, para una longitud total de 128 bytes si es un entero de 1024 bits).$n$$n$

• Bob interpreta su secuencia de bytes como un valor entero grande (codificación big-endian) y calcula (entonces eso es un par de multiplicaciones con enteros muy grandes, luego una división, el resultado es el resto de la división). Eso todavía se puede hacer a mano (pero, nuevamente, probablemente tomará la mayor parte del día). El resultado es lo que Bob le envía a Alice.m 3 m o d$m$$m^3 \mathrm{\ mod\ } n$

• Alice usa su conocimiento de y para recuperar de enviado por Bob. La página de Wikipedia sobre RSA tiene algunas explicaciones razonablemente claras sobre ese proceso. Una vez que Alice tiene , puede quitar el relleno (los 'xx' no son cero, por lo que el primer byte 'bb' puede ubicarse sin ambigüedades) y luego tiene el número de teléfono, que puede comparar con el que tenía.q m m 3 m o d n $p$$q$$m$$m^3 \mathrm{\ mod\ } n$$m$

El cálculo de Alice requerirá una computadora (lo que hace una computadora es siempre elemental y factible a mano, pero una computadora es endiabladamente rápida, por lo que el "factible" puede tomar demasiado tiempo en la práctica; el descifrado RSA a mano tomaría muchos semanas).

(En realidad, podríamos tener un cómputo manual más rápido usando el cifrado McEliece , pero luego la clave pública, lo que Alice escribe en la tarjeta, sería enorme, y una tarjeta simplemente no lo haría; Eve tendría que transportar un libro completo de dígitos)

Parece una aplicación clásica de Public Key Cryptosystem como RSA .

Usted envía su clave pública, BoB cifra su número de teléfono de su lista de contactos y se lo devuelve.

Una de las cosas más básicas que puede hacer es un intercambio de claves Diffie-Hellman . No requiere que tenga claves configuradas antes de que comience la comunicación, ya que negocia una de manera que los oyentes no puedan derivar la clave por sí mismos. Vea el artículo completo de Wikipedia para más detalles.

Envías los parámetros de Bob DH, y ( es un número primo grande adecuado, y generalmente un número pequeño) y tu clave pública , donde es un número secreto grande (es su clave privada), así como las instrucciones para que Bob envíe lo siguiente:g p g g a m o d p $p$$g$$p$$g$$g^{a} \mathop{\mathrm{mod}} p$$a$

• su clave pública , donde es un gran número secreto de su elección;$g^{b} \mathop{\mathrm{mod}} p$$b$
• lo que él cree es su número de teléfono, cifrado usando un algoritmo de cifrado simétrico con una clave derivada del secreto compartido .$g^{a\,b} \mathop{\mathrm{mod}} p$

Eve puede ver y , pero efectivamente no puede calcular .g b m o d p g $g^{a} \mathop{\mathrm{mod}} p$$g^{b} \mathop{\mathrm{mod}} p$$g^{a\,b} \mathop{\mathrm{mod}} p$

Siempre que se implemente correctamente y tanto los comunicadores como el atacante tengan aproximadamente el mismo poder de cálculo a su disposición, esto es seguro.

Bob no tiene que enviar ningún mensaje que pueda descifrar. Solo tiene que demostrarte que tiene tu número de teléfono. Por lo tanto, Cryptographic Hash Functions (encriptación unidireccional) ofrece una alternativa a un criptosistema de clave pública. SHA-2 es actualmente un ejemplo popular de tal función.

En esta estrategia, nunca tendrá que descifrar el mensaje de Bob. Le dice a Bob qué función hash le gustaría que usara, por ejemplo, "Bob, usa SHA-2 para encriptar mi número de teléfono y que Eve me devuelva el resultado". Luego, usa el mismo algoritmo para cambiar su número de teléfono y verifica si obtiene el mismo algoritmo que obtuvo Bob. Es extremadamente improbable que dos números de teléfono diferentes den como resultado el mismo hash, por lo que puede determinar si Bob tiene o no su número de teléfono correcto.

Si usted, Bob y Eve no tienen computadoras disponibles para calcular la función hash (o realizar un ataque de fuerza bruta), es posible usar la función hash que sacrifica algo de seguridad contra los ataques de fuerza bruta, pero es mucho más fácil para usted y Bob calcular.

Una solución simple sería:

Tanto Alice como Bob están de acuerdo en el mismo color. y no hay problema si Eve lo sabe, lo llamaremos P. Digamos que es amarillo. Ahora, Alice y Bob eligen al azar un color privado, digamos "x". Alice elige rojo, y Bob elige azul. Ahora los mezclan con el P. Alice ahora tiene naranja y Bob tiene verde. Alice envía el color naranja a Bob, y Bob envía su color verde a Alice Eve ahora sabe sobre amarillo, naranja y verde, pero Alice también sabe su color privado rojo, y Bob sabe su color privado azul, que nadie más sabe. Tanto Alice como Bob toman sus colores privados originales y los agregan a los que acaban de intercambiar. Ahora, si mezclan sus colores privados originales, rojo y azul, en el color compartido, ambos terminan con el mismo color, marrón o rojo ladrillo.

En lugar de mezclar colores, puede usar modo que p sea un número primo grande, y g es una raíz primitiva de p porque si hace para cualquier x, el resultado (un número entre cero y p - 1) es igualmente probable que sea cualquiera de esos, por eso hay una raíz primitiva. si p es un número primo 2n + 1, de modo que n también es primo, entonces sabe que 2 es una raíz primitiva de p (lo que significa que no tiene que molestarse en calcular la raíz primitiva, que es un poco difícil) por lo tanto, secreto compartido = para Bob, y para Alice.$g^x\pmod{p}$$g^x\pmod{p}$$A^x\pmod{p}$$B^y\pmod{p}$

Creo que puedes escribir algo como esto en la tarjeta:

El número es múltiplo de 3,5 y 7 (por ejemplo).

Hay ( es el número de dígitos) posibilidades y esa idea invalidará algunas pocas posibilidades para el que tiene una idea al respecto. Entonces el descifrado por Eva no sucederá.$(10)^n$$n$

Solo pídale a Bob que multiplique el número por 2 o 3 o cualquier otra cosa y que xor ese número con el número mismo. Es factible a mano y reversible si se conoce el número. Sin sha, rsa o md5. Solo matemáticas simples.

Envíele a Bob una palabra encriptada encriptada con su número de teléfono; si él te devuelve la palabra clave, sabes que tiene el número correcto.

La debilidad es que Eve puede simular a Bob, así que solo prueba cada número de teléfono hasta que obtenga el que le da la palabra clave cuando Bob regresó.

Por lo tanto, haga que Bob agregue un número aleatorio muy grande a la palabra de código y luego encripte antes de enviárselo. Esto hace que el espacio de búsqueda de Eves sea tan grande como desee.

Escribiré unos 10 números de teléfono en la tarjeta y entre ellos me aseguraré de que Mi número aparezca junto al número de Bob y mencionaré "Hola Bob, mi número está al lado de tu número, verifica" :)

Creo que la pregunta es mucho más simple de lo que todos piensan. Estamos obligados a verificar que el número que Bob tiene es correcto (o como podría ser, incorrecto). Como estamos "verificando" si el número es correcto, se puede suponer que Bob ya tiene su número. Por lo tanto, no es necesario enviarle a Bob su número en algún código. Mi respuesta sería: "Querido Bob, por favor llama a mi número. Gracias, Alice".

intenta hacer una jugada trik como esta

solución1: si el número es 37, el mapa hash se vería así

01 07

15 12

25 20

31 36

49 43

53 50

60 62

72 72

85 82

91 94

y hacer lo mismo para 10 dígitos o incluso más solo para confundir: P

solución2: o construya un polinomio en el que su número se convierta en otro número único

solution3: escribe esto en la carta "amigo llámame"

solución4: escribe una función de tal manera que realice operaciones en cada dígito y devuelva 0, luego envía una solución verdadera o falsa5: si ambos extremos comparten una función hash común ... hace la vida muy fácil

Creo que podemos hacer esto usando operaciones básicas en cuanto a bits o podemos personalizarlo para trabajos en papel y lápiz. Si el número de Alice es para ex: 663, entonces ella puede convertir el número usando esta metodología. Convierta cada dígito a una representación binaria equivalente, diga esto como A 663-> 110110011 que invierta los bits correspondientes para cada número individual, diga esto como B-> 011 011 110 Ahora haga A y B-> 010 010 010 Ahora envíe este número a Bob y pida que haga lo mismo si el resultado es el mismo, pídale que diga sí o no. En este caso, Eve no podrá decodificar el número y hay una probabilidad muy baja de que diferentes números terminen en esta misma representación. La única forma en que Eve podría adivinar es escribiendo todas las combinaciones posibles y luego probándolas todas, pero para tener en cuenta que podemos complicar más esto usando el desplazamiento hacia la izquierda o hacia la derecha y agregando bits ficticios.

Por favor llámame (mi nombre es 1001001). Si no puede comunicarse conmigo, escriba el número de teléfono que tiene y pídale a Eve que me devuelva.

Explicación: si Bob obtuvo mi # correcto, puede comunicarse conmigo, entonces sé que es un # correcto; si Bob no obtuvo mi número correcto, Eve no puede leer mi número de teléfono (correcto) también. De esta manera, ya verifiqué que mi amigo, Bob, tiene mi número de teléfono correcto o no.