Comment vérifier le numéro avec Bob sans Eve savoir?

Question

Vous devez vérifier que votre ami, Bob, votre numéro de téléphone correct, mais vous ne pouvez pas lui demander directement. Vous devez écrire la question sur une carte qui et à Eve qui prendra la carte à Bob et retourner la réponse à vous donner. Que devez-vous écrire sur la carte, en plus de la question, afin d'assurer Bob peut coder le message pour que Eve ne peut pas lire votre numéro de téléphone?

Note: Cette question est sur une liste de "google questions d'entrevue". En conséquence, il y a des tonnes de versions de cette question sur le web, et beaucoup d'entre eux n'ont pas de réponses claires, voire corriger.

Note 2: La réponse snarky à cette question est que Bob devrait écrire "appelez-moi". Oui, c'est très intelligent, sortir des sentiers battus »et tout, mais ne pas utiliser de techniques de terrain CS où nous appelons notre héros « Bob » et son adversaire de l'écoute clandestine « Eve ».

Mise à jour: Les points bonus pour un algorithme que vous et Bob pouvait raisonnablement à la fois complet à la main.

Mise à jour 2: Notez que Bob n'a pas de vous envoyer tout message arbitraire, mais seulement confirmer qu'il a votre numéro de téléphone correct sans Eve être en mesure de le décoder, ce qui peut ou ne peut pas conduire à des solutions plus simples.

Answer 1

Tout d'abord, nous devons supposer que Eve est seulement passif. Par cela, je veux dire qu'elle envoie franchement la carte à Bob, et tout ce qu'elle ramène à Alice est en effet la réponse de Bob. Si Eve peut modifier les données dans l'une ou les deux directions (et son geste reste inaperçue), alors tout va.

(Pour l'honneur des traditions de longue date, les deux parties honnêtes impliqués dans la conversation sont appelés Alice et Bob. Dans votre texte, vous avez dit « vous ». Vrai nom Mon est pas « Alice », mais je vais répondre comme si vous avez écrit que Alice veut vérifier le numéro de téléphone de Bob.)

Le simple (mais faible) réponse est d'utiliser une fonction de hachage. Alice écrit sur la carte: « retour à moi le hachage SHA-256 de votre numéro de téléphone ». SHA-256 est une fonction de hachage cryptographique, qui est considérée comme sûre, dans la mesure où fonctions de hachage vont. Son calcul à la main serait fastidieux, mais encore faisable (qui est à peu près 2500 opérations 32 bits, où chaque opération est un ajout, un changement de mot ou rotate, ou une combinaison de bits de bits, Bob devrait être en mesure de le faire en un jour ou so).

Maintenant, ce qui est faible à ce sujet? SHA-256, qui est une fonction de hachage cryptographique, est résistant à la « préimages »: cela signifie que, étant donné un résultat de hachage, il est très difficile de récupérer une entrée (qui est le problème qui fait face à Eve) correspondant. Cependant, « très dur » signifie « la méthode la plus simple est la force brute: essayer les entrées possibles jusqu'à ce qu'une correspondance soit trouvée ». Le problème est que la force brute est facile ici: il n'y a pas tant de numéros de téléphone possibles (en Amérique du Nord, qui est de 10 chiffres, à savoir que 10 milliards). Bob veut faire des choses à la main, mais nous ne pouvons pas supposer que Eve est si limitée. Un PC de base peut essayer quelques millions SHA-256 hash par seconde si Eve sera fait en moins d'une heure (moins de 5 minutes si elle utilise un GPU).

Ceci est une question générique: si Bob est déterministe (par exemple pour un message donné d'Alice, il retournerait toujours la même réponse), Eve peut le simuler. A savoir, Eve sait tout sur Bob sauf le numéro de téléphone, donc elle court pratiquement 10 milliards de Bobs, qui ne diffèrent que par leur numéro de téléphone repris; et elle attend l'un des Bobs virtuels quel que soit le retour réel Bob réellement retourné. Le défaut affecte de nombreux types de solutions « intelligentes » impliquant des nonces aléatoires et chiffrement symétrique et whatsnot. Il est une faille forte, et ses mensonges racines dans la différence énorme dans le calcul de la puissance entre Eve et Bob (maintenant, si Bob aussi avait un ordinateur aussi grand que Eve, il pourrait alors utiliser un lent fonction de hachage à l'aide de nombreuses itérations, qui est plus ou moins ce mot de passe est sur le hachage, avec le numéro de téléphone au lieu du mot de passe, voir bcrypt et aussi cette réponse ).

Par conséquent, une solution non faible doivent impliquer un certain caractère aléatoire de la part de Bob: Bob doit retourner une pièce de monnaie ou de jeter des dés à plusieurs reprises, et injecter les valeurs dans ses calculs. De plus, Eve ne doit pas être en mesure de démêler ce que Bob a fait, mais Alice doit pouvoir, si certaines informations sont confidentialy convoyée de Bob à Alice. Ceci est appelé chiffrement asymétrique ou, au moins, un accord clé asymétrique. L'algorithme le plus simple de cette classe à calculer, mais toujours raisonnablement sûr, est alors RSA avec le PKCS # 1 v1.5 rembourrage . RSA peut utiliser $ e = 3 $ comme exposant public. Ainsi, le protocole va ainsi:

• Alice génère un grand entier $ n = pq $ où $ p $ et $ q $ sont de la même taille nombre premier, de sorte que la taille de n $ est suffisante pour assurer la sécurité(À savoir au moins 1024 bits, à partir de 2012). En outre, Alice doit prendre des dispositions pour $ p-1 $ et $ q-1 $ pas pour être des multiples de 3.

• Alice écrit $ n $ sur la carte.

• Bob premier pads son numéro de téléphone dans une séquence d'octets tant que $ n $, tel que décrit par PKCS # 1 (ce qui signifie: 00 02 xx xx ... xx 00 bb bb .. bb, où « bb » sont les dix octets qui codent le numéro de téléphone, et le « xx » sont des valeurs d'octets non nuls aléatoires, pour une longueur totale de 128 octets si $ n $ est un nombre entier de 1024 bits) .

• Bob interprète sa séquence d'octets comme une grande valeur entière $ $ m (big-endian encodage) et calcule $ m ^ 3 \ mathrm {\ mod \} n $ (c'est donc deux multiplications avec très grand des nombres entiers, puis une division, le résultat étant le reste de la division). C'est encore faisable à la main (mais, là encore, il faudra probablement la meilleure partie d'un jour). Le résultat est ce que Bob renvoie à Alice.

• Alice utilise sa connaissance de $ p $ et $ q $ pour récupérer $ m $ de la m $ ^ 3 \ mathrm {\ mod \ n} $ envoyé par Bob. La page Wikipedia sur RSA a des explications raisonnablement claires sur ce processus. Une fois que Alice a $ m $, elle peut enlever le rembourrage (le « xx » sont non nuls, de sorte que le premier « bb » octet peut être clairement situé) et elle a alors le numéro de téléphone, qu'elle peut se comparer à celui qu'elle a.

Le calcul d'Alice, il faudra un ordinateur (quel ordinateur fait est toujours élémentaire et faisables à la main, mais un ordinateur est diablement rapide à elle, de sorte que le « faisables » pourrait prendre trop de temps pour faire dans la pratique. RSA décryptage à la main prendrait plusieurs semaines)

(En fait, on pourrait avoir le calcul plus rapide par la main en utilisant McEliece cryptage , mais . la clé publique - ce que Alice écrit sur la carte - serait énorme, et une carte serait tout simplement pas le faire, Eve aurait à transporter un livre plein de chiffres)

Answer 2

On dirait une application classique de Public Key Cryptosystem comme RSA .

Vous envoyez votre clé publique le long, BoB encrypte votre numéro de téléphone de sa liste de contacts et de nouveau à vous envoie.

Answer 3

L'une des choses les plus élémentaires que vous pouvez faire est un échange de clés Diffie-Hellman . Il ne nécessite pas d'avoir des clés mises en place avant que la communication commence comme elle négocie une façon que les auditeurs ne peuvent pas déduire la clé eux-mêmes. Voir la Wikipedia article pour plus de détails.

Vous envoyez Bob DH paramètres $ p $ et $ g $ ($ p $ est un parfait grand convenable, et $ g $ généralement un petit nombre) et votre clé publique $ g ^ {a} \ mathop {\ mathrm { mod}} p $, où $ a $ est un grand numéro secret (c'est votre clé privée), ainsi que des instructions pour Bob de renvoyer ce qui suit:

• sa clé publique $ g ^ {b} \ mathop {\ mathrm {mod}} p $, où $ b $ est un grand nombre secret de son choix;
• ce qu'il croit est votre numéro de téléphone, crypté en utilisant un algorithme de chiffrement symétrique avec une clé dérivée à partir du secret $ g partagé ^ {a \ b} \ mathop {\ mathrm {mod}} p $.

Eve peut voir $ g ^ {a} \ mathop {\ mathrm {mod}} p $ et $ g ^ {b} \ mathop {\ mathrm {mod}} p $, mais efficace ne peut pas calculer $ g ^ { a \ b} \ mathop {\ mathrm {mod}} p $.

Tant que mis en œuvre correctement et les communicateurs et les attaquant ont de la même puissance de calcul à leur disposition, cela est sûr.

Answer 4

Bob n'a pas d'envoyer des messages que vous pouvez déchiffrer. Il n'a qu'à vous prouver qu'il a votre numéro de téléphone. Par conséquent, fonctions de hachage cryptographique (cryptage à sens unique) offre une alternative à un cryptosystème à clé publique. SHA-2 est actuellement un exemple populaire d'une telle fonction.

Dans cette stratégie, vous ne devez jamais déchiffrer le dos de message de Bob à vous. Vous dites Bob qui fonction de hachage que vous le souhaitez utiliser, par exemple « Bob, s'il vous plaît utiliser SHA-2 pour chiffrer mon numéro de téléphone et ont Eve passer le dos de résultat pour moi. » Ensuite, vous utilisez le même algorithme de hachage votre numéro de téléphone, et vérifier si vous obtenez le même hachage que Bob a. Il est extrêmement peu probable que deux numéros de téléphone différents entraînerait le même hachage, et donc vous pouvez déterminer si Bob a votre numéro de téléphone correct.

Si vous, Bob et Eve n'ont pas d'ordinateurs disponibles pour calculer la fonction de hachage (ou effectuer une attaque de force brute), il est possible d'utiliser la fonction de hachage qui sacrifie une certaine sécurité contre les attaques de force brute, mais est beaucoup plus facile pour vous et Bob à calculer.

Answer 5

Une solution simple serait:

Alice et Bob conviennent de la même couleur. et il n'y a pas de problème si Eve sait que l'on, nous appellerons le dire de ce P. Soit il est jaune. Maintenant, Alice et Bob choisissent au hasard une couleur privée, disent « x ». Alice choisit le rouge, et Bob choisit bleu. Maintenant, ils les mélangent avec le P. Alice a maintenant orange, et Bob a vert. Alice envoie la couleur orange à Bob, et Bob envoie sa couleur verte à Alice Eve connaît maintenant jaune, orange et vert, mais Alice sait aussi sa couleur rouge privée, et Bob connaît son bleu de couleur privée, que personne ne sait. Alice et Bob prennent leurs couleurs originales privées et les ajouter à ceux qu'ils échangeaient juste. Maintenant, s'ils mélangent leurs couleurs privées originales, rouge et bleu, dans la couleur commune, ils ont tous deux finissent avec la même couleur, sorte de brun, ou rouge brique.

Au lieu de mélanger les couleurs ensemble, vous pouvez utiliser $ g ^ x \ pmod {p} $ tel que p est un grand nombre premier et g est une racine primitive de p parce que si vous faites $ g ^ x \ pmod {p} $ pour tout x, le résultat (un nombre compris entre zéro et p - 1) est équiprobables pour être l'un de ceux, qui est la raison pour laquelle il y a une racine primitive. si p est un nombre premier 2n + 1 tel que n est premier, alors vous savez que 2 est une racine primitive de p (ce qui signifie que vous ne devez pas déranger le calcul de la racine primitive, ce qui est un peu difficile) ainsi la secret partagé = $ A ^ x \ pmod {p} $ pour Bob, et B $ ^ y \ pmod {p} $ pour Alice.

---

Je pense que vous pouvez écrire quelque chose comme ça sur la carte:

  

Le nombre est multiple de 3,5 et 7 (par exemple).

Il y a $ (10) $ ^ n ($ n $ est le nombre de chiffres) possibilités et cette idée sera simplement invalider quelques peu de possibilités pour celui qui a savoir idée à ce sujet. Ainsi, le déchiffrement par Eve ne se produira pas.

Answer 6

Il suffit de demander Bob à multiplier le nombre par 2 ou 3 ou quoi que ce soit d'autre et XOR ce nombre avec le nombre lui-même. Il est faisable à la main et réversible si le nombre est connu. Non sha, rsa ou md5. mathématiques. Tout simplement

Answer 7

Envoyer Bob un mot de code crypté avec votre numéro de téléphone; s'il vous renvoie le mot de code que vous savez qu'il a le bon numéro.

La faiblesse est que Eve peut simuler Bob, donc juste essayer chaque numéro de téléphone jusqu'à ce qu'elle obtienne celui qui donne les quelques-uns comme Bob retourne mot de code.

Alors obtenir Bob à ajouter un très grand nombre aléatoire au mot de code, puis chiffrez avant de l'envoyer à vous. Cela rend la recherche Eves espace aussi grand que vous le souhaitez.

Answer 8

Je vais écrire quelques 10 numéros de téléphone dans la carte et parmi ceux que je ferai en sorte que Mon numéro viendrait à côté du numéro de Bob  et je cite: « Hé Bob, mon numéro est à côté de votre numéro, s'il vous plaît vérifier »:)

Answer 9

Je pense que la question est beaucoup plus simple que tout le monde pense. Nous sommes tenus de vérifier que le numéro a Bob est correct (ou il pourrait être, incorrect). Puisque nous « Vérification » si le numéro est correct, on peut supposer que Bob a déjà votre numéro. Par conséquent, il n'y a pas besoin d'envoyer Bob votre numéro dans un code. Ma réponse serait, « Cher Bob, s'il vous plaît mon numéro de téléphone. Merci, Alice »

Answer 10

essayer de faire un jeu de Trik comme ceci

solution1: si le nombre est de 37 la carte de hachage ressemblerait à ceci

01 07

15 12

25 20

31 36

49 43

53 50

60 62

72 72

85 82

91 94

et faire la même chose pour les 10 chiffres ou encore plus simplement Confondre: P

Solution2: ou construire un polynôme dans lequel votre numéro devient un autre numéro unique

solution3: écrire dans la lettre « appel mec me »

solution4: écrire une fonction manière telle qu'elle effectue des opérations sur chaque chiffre et retourne 0 puis il envoie vrai ou faux solution5: si les deux extrémités partagent une fonction de hachage commune ... il rend la vie très facile

Answer 11

Je pense que nous pouvons le faire en utilisant des opérations de sages bits de base ou peut être le personnalisant pour le travail du papier et un crayon. Si le nombre de alice est par ex: 663 qu'elle peut simplement convertir le numéro à l'aide de cette méthode. Convertir chaque chiffre à la représentation binaire équivalent dire que A 663-> 110 110 011 à inverser les bits correspondants pour chaque numéro individuel dire que B> 011 011 110 Maintenant, faites A et B> 010 010 010 Maintenant envoyer ce numéro à Bob et demander de le faire même si le résultat est même lui demander de dire oui ou bien No. Dans ce cas, la veille ne sera pas en mesure de décoder le nombre et il y a une très faible probabilité d'avoir un nombre différent qui se terminent cette même représentation. Seule la veille de façon devinait est en écrivant toutes les combinaisons possibles, puis de les essayer tous, mais pour répondre que nous pouvons compliquer plus en utilisant décalage à gauche ou à droite et en ajoutant des bits fictifs.

Answer 12

S'il vous plaît appelez-moi (mon nom est 1001001). Si vous ne pouvez pas me joindre, s'il vous plaît notez le numéro de téléphone que vous avez et demander Eve me revenir.

Explication: si Bob a obtenu mon bon #, il peut me joindre alors je sais qu'il est un bon #; si Bob n'a pas obtenu mon droit #, Eve ne peut pas lire mon (correct) numéro de téléphone ainsi. De cette façon, je l'ai déjà vérifié que mon ami, Bob, a mon numéro de téléphone correct ou non.