Wie überprüfen Sie die Nummer mit Bob ohne Eve zu wissen?

Question

Sie müssen überprüfen, ob Ihr Freund Bob Ihre korrekte Telefonnummer hat, aber Sie können ihn nicht direkt fragen. Sie müssen die Frage auf eine Karte schreiben, die Eve geben wird, die die Karte zu Bob nimmt und die Antwort an Sie zurücksetzt. Was müssen Sie neben der Frage auf die Karte schreiben, um sicherzustellen, dass Bob die Nachricht so codieren kann, dass Eve Ihre Telefonnummer nicht lesen kann?

Notiz: Diese Frage steht auf einer Liste von "Google -Interview -Fragen". Infolgedessen gibt es Unmengen von Versionen dieser Frage im Internet, und viele von ihnen haben keine klaren oder gar korrekten Antworten.

Anmerkung 2: Die snarky Antwort auf diese Frage ist, dass Bob "Call Me" schreiben sollte. Ja, das ist sehr klug, 'außerhalb des Kastens' und alles, verwendet aber keine Techniken, in denen wir unseren Helden "Bob" und seinen Abhören "Eva" nennen.

Aktualisieren:
Bonuspunkte für einen Algorithmus, den Sie als auch Bob von Hand vernünftigerweise vervollständigen konnten.

Update 2:
Beachten Sie, dass Bob Ihnen keine willkürliche Nachricht senden muss, sondern nur bestätigen, dass er Ihre korrekte Telefonnummer hat, ohne dass Eva sie dekodieren kann, was zu einfacheren Lösungen führen kann oder nicht.

Answer 1

Zuerst müssen wir annehmen, dass Eva nur passiv ist. Damit meine ich, dass sie die Karte wahrheitsgemäß an Bob schickt und was auch immer sie zu Alice zurückbringt, in der Tat Bobs Antwort ist. Wenn Eva die Daten in einer oder beiden Richtungen ändern kann (und ihre Aktion bleibt unentdeckt), dann geht alles.

(Um langjährige Traditionen zu ehren, werden die beiden ehrlichen Parteien, die an dem Gespräch beteiligt sind das Alice will Bobs Telefonnummer überprüfen.)

Die einfache (aber schwache) Antwort ist die Verwendung einer Hash -Funktion. Alice schreibt auf der Karte: "Kehre zu mir den SHA-256-Hash deiner Telefonnummer zurück." SHA-256 ist eine kryptografische Hash -Funktion, von der angenommen wird, dass sie sicher ist, was die Hash -Funktionen tun. Das Berechnen von Hand wäre mühsam, aber immer noch machbar (das sind etwa 2500 32-Bit-Operationen, bei denen jede Operation eine Addition, eine Wortverschiebung oder eine drehende oder eine bitweise Kombination von Bits ist; Bob sollte es an einem Tag oder an einem Tag oder an einem Tag tun können können Also).

Was ist daran nun schwach? SHA-256, eine kryptografische Hash-Funktion, ist resistent gegen "Vorbereitungen": Dies bedeutet, dass es bei einem Hash-Ausgang sehr schwierig ist, einen entsprechenden Eingang wiederherzustellen (das ist das Problem, mit dem Eva konfrontiert ist). "Sehr hart" bedeutet jedoch "die einfachste Methode ist brutale Kraft: Versuch möglich, bis eine Übereinstimmung gefunden wird". Das Problem ist, dass Brute Force hier einfach ist: Es gibt nicht so viele mögliche Telefonnummern (in Nordamerika, das sind 10 Ziffern, dh nur 10 Milliarden). Bob will Dinge von Hand tun, aber wir können nicht davon ausgehen, dass Eva so begrenzt ist. Ein grundlegender PC kann ein paar Millionen SHA-256-Hashes ausprobieren pro Sekunde Also wird Eva in weniger als einer Stunde durchgeführt (weniger als 5 Minuten, wenn sie eine GPU verwendet).

Dies ist ein generisches Problem: Wenn Bob deterministisch ist (dh für eine bestimmte Nachricht von Alice, würde er immer dieselbe Antwort zurückgeben), kann Eva ihn simulieren. Eva weiß nämlich alles über Bob außer der Telefonnummer, daher führt sie praktisch 10 Milliarden Bobs aus, die sich nur durch ihre angenommene Telefonnummer unterscheiden. Und sie wartet darauf, dass eines der virtuellen Bobs alles zurückgibt, was der wahre Bob tatsächlich zurückgekehrt ist. Der Fehler betrifft viele Arten von "intelligenten" Lösungen, die zufällige Nonces und symmetrische Verschlüsselung und Whatsnot betreffen. Es ist ein starker Fehler und seine Wurzel liegt in dem großen Unterschied in der Rechenleistung zwischen Eva und Bob (jetzt, wenn Bob Auch Hatte einen Computer so groß wie Eva, dann konnte er einen benutzen langsam Hash -Funktion durch die Verwendung vieler Iterationen; Das ist mehr oder weniger das, worum es beim Passwort mit der Telefonnummer anstelle des Passworts geht. sehen Bcrypt und auch Diese Antwort).

Daher eine nicht schwierige Lösung muss Beben Sie ein gewisses Zufälligkeit von Bobs Teil ein: Bob muss eine Münze drehen oder Würfel wiederholt werfen und die Werte in seine Berechnungen injizieren. Darüber hinaus darf Eva nicht in der Lage sein, das zu entwirren, was Bob getan hat, aber Alice muss in der Lage sein, so einige Informationen sind selbstbewusst übertragen Von Bob nach Alice. Das nennt man Asymmetrische Verschlüsselung Oder zumindest asymmetrische Schlüsselvereinbarung. Der einfachste Algorithmus dieser Klasse, um zu berechnen, aber immer noch einigermaßen sicher, ist dann RSA mit dem PKCS#1 v1.5 Polsterung. RSA kann $ e = 3 $ als öffentlicher Exponent verwenden. Das Protokoll geht also so:

• Alice generiert eine große Ganzzahl $ n = pq $, wobei $ p $ und $ q $ eine ähnlich große Prime Ganzzahl sind, so dass die Größe von $ n $ ausreicht, um die Sicherheit zu gewährleisten (dh mindestens 1024 Bit ab 2012). Außerdem muss Alice $ P-1 $ und $ $ q-1 $ arrangieren nicht Vielfache von 3 sein.

• Alice schreibt $ n $ auf der Karte.

• Bob zuerst Pads Seine Telefonnummer in eine Byte -Sequenz, bis $ n $, wie in PKCS#1 beschrieben Telefonnummer und die 'xx' sind zufällige Byte-Werte ungleich Null für eine Gesamtlänge von 128 Bytes, wenn $ n $ eine 1024-Bit-Ganzzahl ist).

• Bob interpretiert seine Byte-Sequenz als einen großen Ganzzahlwert $ M $ (Big-Endian-Codierung) und berechnet $ M^3 mathrm { mod } n $ (das sind also ein paar Multiplikationen mit sehr großen Ganzzahlen, dann als Teilung. Das Ergebnis ist der Rest der Teilung). Das ist immer noch von Hand machbar (aber dort wird es wahrscheinlich den größten Teil eines Tages dauern). Das Ergebnis ist das, was Bob an Alice zurücksendet.

• Alice verwendet ihr Wissen über $ p $ und $ q $, um $ M $ aus dem von Bob gesendeten $ M^3 mathrm { mod } n $ zu erhalten. Die Wikipedia -Seite auf RSA hat einige einigermaßen klare Erklärungen zu diesem Prozess. Sobald Alice $ M $ hat, kann sie die Polsterung entfernen (die 'xx' sind ungleich Null, sodass das erste 'BB' -Byte eindeutig gelegen sein kann) und sie hat dann die Telefonnummer, die sie mit dem sie vergleichen kann, den sie vergleichen kann hatte.

Die Berechnung von Alice erfordert einen Computer (was ein Computer tut stets Elementar und machbar von Hand, aber ein Computer ist teuflisch schnell darin, so dass das "machbare" in der Praxis zu viel Zeit in Anspruch nehmen kann. RSA Entschlüsselung von Hand würde viele Wochen dauern).

(Eigentlich könnten wir schneller berechnen, indem wir verwenden McEliece -Verschlüsselung, Aber dann wäre der öffentliche Schlüssel - was Alice auf der Karte schreibt - riesig, und eine Karte würde es einfach nicht tun; Eva müsste ein vollständiges Ziffernbuch transportieren.)

Answer 2

Sieht aus wie eine klassische Anwendung von Public Key Cryptosystem wie RSA.

Sie senden Ihren öffentlichen Schlüssel mit, verschlüsselt Bob Ihre Telefonnummer aus seiner Kontaktliste und sendet sie an Sie zurück.

Answer 3

Eines der grundlegendsten Dinge, die Sie tun können, ist a Diffie-Hellman Key Exchange. Es erfordert nicht, dass Sie Schlüssel einrichten lassen, bevor die Kommunikation beginnt, da sie so verhandelt, dass die Zuhörer den Schlüssel selbst nicht ableiten können. Siehe das umfassende Wikipedia -Artikel für Details.

Sie senden Bob DH -Parameter $ p $ und $ g $ ($ p $ als geeignetes großes Prime und $ g $ typischerweise eine kleine Nummer) und Ihr öffentlicher Schlüssel $ g^{a} mathop { mathhrm {mod}} P $, wobei $ a $ eine große geheime Nummer ist (es ist Ihr privater Schlüssel) sowie Anweisungen für Bob, die Folgendes zurücksenden können:

• Sein öffentlicher Schlüssel $ g^{b} mathop { mathem {mod}} p $, wobei $ b $ eine große geheime Anzahl seiner Wahl ist;
• Was er glaubt, ist Ihre Telefonnummer, die mit einem symmetrischen Verschlüsselungsalgorithmus mit einem Schlüssel verschlüsselt wird, der aus dem freigegebenen geheimen $ g^{a , b} mathop { mathrm {mod}} p $ abgeleitet ist.

Eve kann $ g^{a} mathop { mathrm {mod}} p $ und $ g^{b} mathop { mathrm {mod}} p $ sehen, kann aber $ g^{a , nicht berechnen, $ g^{a , B} mathop { mathhrm {mod}} p $.

Solange sowohl Kommunikatoren als auch Angreifer ungefähr die gleiche Berechnungsleistung zur Verfügung haben, ist dies sicher.

Answer 4

Bob muss keine Nachrichten senden, die Sie entschlüsseln können. Er muss Ihnen nur beweisen, dass er Ihre Telefonnummer hat. Deswegen, Kryptografische Hash -Funktionen, (Einwegverschlüsselung) bietet eine Alternative zu einem öffentlichen Schlüsselkryptosystem. SHA-2 ist derzeit ein beliebtes Beispiel für eine solche Funktion.

In dieser Strategie müssen Sie Bobs Nachricht an Sie nie entschlüsseln. Sie sagen Bob, welche Hash-Funktion Sie verwenden möchten, z. "Bob, bitte verwenden Sie SHA-2, um meine Telefonnummer zu verschlüsseln und das Ergebnis das Ergebnis an mich zurückzugeben." Dann verwenden Sie denselben Algorithmus, um Ihre Telefonnummer zu hassten, und prüfen Sie, ob Sie den gleichen Hash wie Bob erhalten. Es ist äußerst unwahrscheinlich, dass zwei verschiedene Telefonnummern zu demselben Hash führen, und Sie können daher feststellen, ob Bob Ihre korrekte Telefonnummer hat oder nicht.

Wenn Sie, Bob und Eve keine Computer zur Verfügung haben, um die Hash -Funktion zu berechnen (oder einen Brute -Force -Angriff auszuführen), kann es möglich sein, die Hash -Funktion zu verwenden, die eine gewisse Sicherheit gegen Brute -Force -Angriffe opfert, aber für Sie und Bob viel einfacher ist berechnen.

Answer 5

Eine einfache Lösung wäre:

Sowohl Alice als auch Bob sind sich auf die gleiche Farbe ein. Und es ist kein Problem, wenn Eve das weiß, wir nennen das P., sagen wir, es ist gelb. Jetzt wählen Alice und Bob beide zufällig eine private Farbe, sagen "x". Alice wählt Rot und Bob wählt Blue. Jetzt mischen sie sie zusammen mit dem P. Alice, der jetzt Orange hat und Bob grün. Alice schickt die orangefarbene Farbe an Bob, und Bob schickt seine grüne Farbe nach Alice Eva, die sich jetzt über Gelb, Orange und Grün kennt, aber Alice kennt auch ihre private Farbe rot, und Bob kennt seine private Farbe blau, was niemand sonst kennt. Sowohl Alice als auch Bob nehmen ihre ursprünglichen privaten Farben an und fügen sie zu denen hinzu, die sie gerade ausgetauscht haben. Wenn sie nun ihre ursprünglichen privaten Farben, rot und blau, in die gemeinsame Farbe mischen, haben beide die gleiche Farbe, eine Art brauner oder backiger Rot.

Anstatt Farben zu mischen, können Sie $ g^x pmod {p} $ verwenden, so dass p eine große Primzahl ist und G eine primitive Wurzel von P ist, denn wenn Sie $ g^x pmod {p} $ tun Für jedes x ist das Ergebnis (eine Zahl zwischen Null und P - 1) ist ebenso wahrscheinlich Um eine davon zu sein, gibt es eine primitive Wurzel. Wenn P eine Primzahl 2n+1 ist, so dass n auch Prim ist, dann wissen Sie, dass 2 eine primitive Wurzel von P ist (was bedeutet, dass Sie sich nicht die Mühe machen müssen Shared Secret = $ a^x pmod {p} $ für Bob und $ b^y pmod {p} $ für Alice.

---

Ich denke, Sie können so etwas auf die Karte schreiben:

Die Zahl ist vielfältig von 3,5 und 7 (zum Beispiel).

Es gibt $ (10)^n $ ($ n $ ist die Anzahl der Ziffern) und diese Idee wird nur einige wenige Möglichkeiten für diejenigen ungültig machen, die die Idee darüber wusste. Die Entschlüsselung durch Eva wird also nicht passieren.

Answer 6

Bitten Sie Bob einfach, die Nummer mit 2 oder 3 oder irgendetwas anderes zu multiplizieren und diese Zahl mit der Nummer selbst zu XOR. Es ist von Hand machbar und reversibel, wenn die Zahl bekannt ist. Kein SHA, RSA oder MD5. Einfach nur Mathematik.

Answer 7

Senden Sie Bob A Codewort, der mit Ihrer Telefonnummer verschlüsselt ist. Wenn er Ihnen das Code -Wort zurücksendet, wissen Sie, dass er die richtige Nummer hat.

Die Schwäche ist, dass Eva Bob simulieren kann. Probieren Sie also jede Telefonnummer aus, bis sie diejenige erhält, die das Codewort gibt, als Bob zurückkehrte.

Bringen Sie Bob dazu, eine sehr große Zufallszahl an das Codewort anzuhängen und dann zu verschlüsseln, bevor Sie sie an Sie zurücksenden. Dies macht EVES -Suchraum so groß, wie Sie möchten.

Answer 8

Ich werde einige 10 Telefonnummern in die Karte schreiben und unter denen werde ich sicherstellenMeine Nummer würde neben Bobs Nummer kommenUnd ich werde erwähnen "Hey Bob, meine Nummer ist neben deiner Nummer, bitte überprüfen Sie" :) :) :)

Answer 9

Ich denke, die Frage ist viel einfacher als jeder denkt. Wir müssen überprüfen, ob die Zahl, die Bob hat, korrekt ist (oder wie es vielleicht auch sein mag). Da wir "prüfen", ob die Nummer korrekt ist, kann angenommen werden, dass Bob bereits Ihre Nummer hat. Daher müssen Bob Ihre Nummer in einem Code nicht senden. Meine Antwort lautete: "Lieber Bob, bitte ruf meine Nummer an. Danke, Alice"

Answer 10

Versuchen Sie, ein Trikspiel wie dieses zu spielen

Lösung1: Wenn die Zahl 37 ist, würde die Hash -Karte so aussehen

01 07

15 12

25 20

31 36

49 43

53 50

60 62

72 72

85 82

91 94

und das Gleiche für 10 Ziffern oder sogar noch mehr tun, um zu verwechseln: P.

Lösung2: oder konstruieren Sie ein Polynom, bei dem Ihre Nummer zu einer anderen eindeutigen Zahl wird

Lösung3: Schreiben Sie dies in den Brief "Typ Call Me".

Lösung4: Schreiben Sie eine Funktion so, dass sie Operationen in jeder Ziffer ausführt und 0 zurückgibt. Dann sendet er echte oder falsche Lösung5: Wenn beide Enden eine gemeinsame Hash -Funktion teilen ... macht es das Leben sehr einfach

Answer 11

Ich denke, wir können dies tun, indem wir grundlegende bitbezogene Operationen verwenden oder es möglicherweise für Papier- und Bleistiftarbeiten anpassen. Wenn die Anzahl der Alice für Ex: 663 ist, kann sie die Nummer nur mit dieser Methodik konvertieren. Konvertieren Sie jede Ziffer in eine äquivalente binäre Darstellung, sagen Sie dies als 663-> 110 110 011, als die entsprechenden Bits für jede einzelne Zahl umzukehren. Bob und bitten um das Gleiche, wenn das Ergebnis dieselbe Bitten Sie ihn, Ja zu sagen, oder Nein. In diesem Fall kann Eva die Nummer nicht dekodieren, und es besteht eine sehr geringe Wahrscheinlichkeit, dass unterschiedliche Zahlen dieselbe Darstellung haben. Nur wie Eva könnte vermuten, dass alle möglichen Kombinationen geschrieben werden und sie dann versuchen, dies zu tun, um dies durch die Verwendung der linken oder rechten Verschiebung mehr zu komplizieren und Dummy -Bits hinzuzufügen.

Answer 12

Bitte rufen Sie mich an (mein Name ist 1001001). Wenn Sie mich nicht erreichen können, schreiben Sie bitte die Telefonnummer auf, die Sie haben, und bitten Sie Eva, mich zurückzugeben.

Erläuterung: Wenn Bob meine richtige #hat, kann er mich erreichen, dann weiß ich, dass es eine korrekte #ist; Wenn Bob meine rechte #nicht bekam, kann Eve meine (richtige) Telefonnummer auch nicht lesen. Auf diese Weise habe ich bereits überprüft, ob mein Freund Bob meine korrekte Telefonnummer hat oder nicht.