Jak zweryfikować numer z Bobem bez wiedzy Eve?

Musisz sprawdzić, czy twój przyjaciel, Bob, ma poprawny numer telefonu, ale nie możesz go zapytać bezpośrednio. Musisz zapisać pytanie na karcie, która zostanie przekazana Eve, która zabierze kartę do Boba i zwróci ci odpowiedź. Co musisz napisać na karcie oprócz pytania, aby Bob mógł zakodować wiadomość, aby Ewa nie mogła odczytać twojego numeru telefonu?

Uwaga: to pytanie znajduje się na liście „pytań do wywiadu Google”. W rezultacie w sieci jest mnóstwo wersji tego pytania, a wiele z nich nie ma jasnych, a nawet poprawnych odpowiedzi.

Uwaga 2: Mroczna odpowiedź na to pytanie brzmi: Bob powinien napisać „zadzwoń do mnie”. Tak, to bardzo sprytne, „nieszablonowe” i tak dalej, ale nie korzysta z żadnych technik tego pola CS, w którym nazywamy naszego bohatera „Bob”, a jego podsłuchującego przeciwnika „Eve”.

Aktualizacja:
Punkty bonusowe za algorytm, który ty i Bob moglibyście rozsądnie ręcznie ukończyć.

Aktualizacja 2:
Zauważ, że Bob nie musi wysyłać ci dowolnych wiadomości, a jedynie potwierdza, że ​​ma twój poprawny numer telefonu, a Ewa nie może go odkodować, co może, ale nie musi, prowadzić do prostszych rozwiązań.

Najpierw musimy założyć, że Ewa jest tylko pasywna. Rozumiem przez to, że zgodnie z prawdą wysyła kartę do Boba, a wszystko, co przyniesie Alice, jest rzeczywiście odpowiedzią Boba. Jeśli Ewa może zmienić dane w jednym lub obu kierunkach (a jej działanie pozostanie niewykryte), wszystko pójdzie dobrze.

(Aby uhonorować wieloletnie tradycje, dwie uczciwe strony zaangażowane w rozmowę nazywają się Alice i Bob. W swoim tekście powiedziałeś „ty”. Moje prawdziwe imię to nie „Alice”, ale odpowiem tak, jakbyś napisał że Alice chce zweryfikować numer telefonu Boba).

Prostą (ale słabą) odpowiedzią jest użycie funkcji skrótu. Alice pisze na karcie: „zwróć mi skrót SHA-256 swojego numeru telefonu”. SHA-256 to kryptograficzna funkcja skrótu, która jest uważana za bezpieczną, jeśli chodzi o funkcje skrótu. Obliczenie go ręcznie byłoby żmudne, ale wciąż wykonalne (to około 2500 32-bitowych operacji, gdzie każda operacja jest dodatkiem, przesunięciem słowa lub rotacją lub bitową kombinacją bitów; Bob powinien być w stanie to zrobić w ciągu jednego dnia lub więc).

Co jest w tym słabego? SHA-256, będący kryptograficzną funkcją skrótu, jest odporny na „preimages”: oznacza to, że biorąc pod uwagę dane wyjściowe skrótu, bardzo trudno jest odzyskać odpowiednie dane wejściowe (to problem, przed którym stoi Eve). Jednak „bardzo trudny” oznacza „najłatwiejszą metodą jest brutalna siła: próbowanie możliwych danych wejściowych, aż do znalezienia dopasowania”. Problem polega na tym, że brutalna siła jest tutaj łatwa: nie ma tak wielu możliwych numerów telefonów (w Ameryce Północnej to 10 cyfr, czyli zaledwie 10 miliardów). Bob chce robić rzeczy ręcznie, ale nie możemy zakładać, że Ewa jest tak ograniczona. Podstawowy komputer PC może wypróbować kilka milionów skrótów SHA-256 na sekundę, więc Ewa będzie gotowa w mniej niż godzinę (mniej niż 5 minut, jeśli używa GPU).

Jest to ogólny problem: jeśli Bob jest deterministyczny (tzn. Dla danej wiadomości od Alicji zawsze zwraca tę samą odpowiedź), Ewa może go zasymulować. Mianowicie, Ewa wie wszystko o Bobie z wyjątkiem numeru telefonu, więc praktycznie obsługuje 10 miliardów Bobów, które różnią się tylko swoim przypuszczalnym numerem telefonu; i czeka, aż jeden z wirtualnych Bobów zwróci wszystko, co rzeczywiście wrócił Bob. Wada wpływa na wiele rodzajów „inteligentnych” rozwiązań obejmujących losowe elementy jednorazowe i szyfrowanie symetryczne i tak dalej. Jest to silna wada, a jego korzeń leży w ogromnej różnicy w mocy obliczeniowej między Ewą i Bob (obecnie, jeśli Bob również posiadało komputer tak duży jak Eve, to mógłby użyć powolnyfunkcja skrótu za pomocą wielu iteracji; mniej więcej o to chodzi w haszowaniu hasła, z numerem telefonu zamiast hasła; zobacz bcrypt, a także tę odpowiedź ).

Dlatego też słabe rozwiązanie musi wiązać się z pewną przypadkowością ze strony Boba: Bob musi kilkakrotnie rzucić monetą lub rzucać kostką i wstrzykiwać wartości w swoich obliczeniach. Co więcej, Ewa nie może być w stanie odkryć tego, co zrobił Bob, ale Alice musi być w stanie, więc niektóre informacje są poufnie przekazywane od Boba do Alice. Nazywa się to szyfrowaniem asymetrycznym lub przynajmniej asymetryczną zgodą klucza. Najprostszym algorytmem tej klasy do obliczenia, ale wciąż dość bezpiecznym, jest RSA z wypełnieniem PKCS # 1 v1.5 . RSA może używać jako wykładnika publicznego. Tak więc protokół działa w następujący sposób:$e = 3$

• Alicja generuje dużą liczbę całkowitą gdzie i są liczbą całkowitą o podobnej wielkości, tak że rozmiar jest wystarczający do zapewnienia bezpieczeństwa (tj. Co najmniej 1024 bity, według stanu na 2012 r.). Alicja musi również ustalić, aby i nie były wielokrotnościami 3.p q n p - 1 q - $n = pq$$p$$q$$n$$p-1$$q-1$

• Alice zapisuje na karcie.$n$

• Bob najpierw wpisuje swój numer telefonu w sekwencję bajtów tak długo, jak , jak opisano w PKCS # 1 (oznacza to: 00 02 xx xx ... xx 00 bb bb .. bb, gdzie „bb” to dziesięć bajtów, które kodują numer telefonu i „xx” to losowe niezerowe wartości bajtów, dla całkowitej długości 128 bajtów, jeśli jest 1024-bitową liczbą całkowitą).$n$$n$

• Bob interpretuje swoją sekwencję bajtów jako dużą liczbę całkowitą (kodowanie big-endian) i oblicza (więc to kilka mnożenia z bardzo dużymi liczbami całkowitymi, a następnie dzielenie, czego wynikiem jest pozostała część podziału). Nadal można to zrobić ręcznie (ale tam też prawdopodobnie zajmie to większą część dnia). W rezultacie Bob odsyła Alice.m 3 m o d$m$$m^3 \mathrm{\ mod\ } n$

• Alicja wykorzystuje swoją wiedzę o i odzyskać z wysyłane przez Boba. Strona Wikipedii na temat RSA zawiera pewne dość jasne wyjaśnienia tego procesu. Kiedy Alice ma , może usunąć dopełnienie („xx” są niezerowe, więc pierwszy bajt „bb” można jednoznacznie zlokalizować), a następnie ma numer telefonu, który może porównać z tym, który miała.q m m 3 m o d n $p$$q$$m$$m^3 \mathrm{\ mod\ } n$$m$

Obliczenia Alicji będą wymagały komputera (to, co robi komputer, jest zawsze elementarne i wykonalne ręcznie, ale komputer jest diabelnie szybki, więc „wykonalne” może zająć zbyt wiele czasu w praktyce; ręczne odszyfrowanie RSA zajęłoby wiele tygodni).

(Właściwie moglibyśmy mieć szybsze obliczenia ręczne przy użyciu szyfrowania McEliece , ale wtedy klucz publiczny - co Alice zapisuje na karcie - byłby ogromny, a karta po prostu nie zrobiłaby; Ewa musiałaby przetransportować pełną książkę cyfr.)

Wygląda jak klasyczna aplikacja Cryptosystem klucza publicznego, taka jak RSA .

Wysyłasz swój klucz publiczny, BoB szyfruje Twój numer telefonu z jego listy kontaktów i odsyła go z powrotem.

Jedną z najbardziej podstawowych rzeczy, jaką możesz zrobić, jest wymiana kluczy Diffie-Hellmana . Nie wymaga to skonfigurowania kluczy przed rozpoczęciem komunikacji, ponieważ negocjuje się je w taki sposób, że słuchacze nie mogą sami uzyskać klucza. Szczegółowe informacje można znaleźć w obszernym artykule w Wikipedii .

Wysyłasz parametry Bob DH i ( jest odpowiednią dużą liczbą pierwszą zazwyczaj małą liczbą) i klucz publiczny , gdzie jest dużą tajną liczbą (jest to Twój klucz prywatny), a także instrukcje dla Boba, aby odesłać:g p g g a m o d p $p$$g$$p$$g$$g^{a} \mathop{\mathrm{mod}} p$$a$

• jego klucz publiczny , gdzie jest dużą tajną liczbą jego wyboru;$g^{b} \mathop{\mathrm{mod}} p$$b$
• wierzy, że to twój numer telefonu, zaszyfrowany przy użyciu symetrycznego algorytmu szyfrowania z kluczem pochodzącym ze wspólnego tajnego .$g^{a\,b} \mathop{\mathrm{mod}} p$

Ewa widzi i , ale skutecznie nie może obliczyć .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$

Tak długo, jak odpowiednio wdrożone i zarówno komunikatory, jak i atakujący mają do dyspozycji około tej samej mocy obliczeniowej, jest to bezpieczne.

Bob nie musi wysyłać żadnych wiadomości, które można odszyfrować. Musi ci tylko udowodnić, że ma twój numer telefonu. Dlatego funkcje kryptograficzne Hash (szyfrowanie jednokierunkowe) stanowią alternatywę dla kryptosystemu klucza publicznego. SHA-2 jest obecnie popularnym przykładem takiej funkcji.

W tej strategii nigdy nie musisz odszyfrowywać wiadomości Boba. Mówisz Bobowi, z której funkcji skrótu chcesz korzystać, np. „Bob, użyj SHA-2 do zaszyfrowania mojego numeru telefonu i niech Ewa przekaże mi wynik”. Następnie używasz tego samego algorytmu do mieszania numeru telefonu i sprawdzania, czy masz taki sam skrót, jak Bob. Jest bardzo mało prawdopodobne, że dwa różne numery telefonów spowodują ten sam skrót, więc możesz ustalić, czy Bob ma poprawny numer telefonu.

Jeśli ty, Bob i Ewa nie macie dostępnych komputerów do obliczenia funkcji skrótu (lub przeprowadzenia ataku siłowego), może być możliwe użycie funkcji skrótu, która poświęca pewne zabezpieczenia przed atakami siłowymi, ale jest znacznie łatwiejsza dla ciebie i Boba liczyć.

Prostym rozwiązaniem byłoby:

Zarówno Alice, jak i Bob zgadzają się co do tego samego koloru. i nie ma problemu, jeśli Ewa to zna, nazwiemy to P. Powiedzmy, że jest żółty. Teraz zarówno Alice, jak i Bob losowo wybierają prywatny kolor, powiedz „x”. Alice wybiera kolor czerwony, a Bob wybiera kolor niebieski. Teraz mieszają je razem z P. Alice ma teraz pomarańczowy, a Bob ma zielony. Alice wysyła pomarańczowy kolor do Boba, a Bob wysyła zielony kolor do Alice Eve wie teraz o żółtym, pomarańczowym i zielonym, ale Alice zna również swój prywatny kolor czerwony, a Bob zna swój prywatny kolor niebieski, którego nikt inny nie zna. Zarówno Alice, jak i Bob przyjmują swoje oryginalne prywatne kolory i dodają je do tych, które właśnie wymienili. Teraz, jeśli zmieszają swoje oryginalne prywatne kolory, czerwony i niebieski, z wspólnym kolorem, oba kończą tym samym kolorem, brązowym lub ceglastym.

Zamiast mieszać kolory razem, możesz użyć taki sposób, że p jest dużą liczbą pierwszą, a g jest pierwotnym pierwiastkiem p, ponieważ jeśli użyjesz dla dowolnego x, wynik (liczba od zera do p - 1) równie dobrze może być dowolnym z nich, dlatego istnieje prymitywny pierwiastek. jeśli p jest liczbą pierwszą 2n + 1 taką, że n jest również liczbą pierwszą, to wiesz, że 2 jest pierwotnym pierwiastkiem p (co oznacza, że ​​nie musisz zawracać sobie głowy obliczaniem pierwotnego pierwiastka, co jest dość trudne), więc wspólny sekret = dla Boba i dla Alicji.g $g^x\pmod{p}$A $g^x\pmod{p}$B $A^x\pmod{p}$$B^y\pmod{p}$

Myślę, że możesz napisać coś takiego na karcie:

Liczba jest wielokrotnością 3,5 i 7 (na przykład).

Istnieje ( to liczba cyfr) i ten pomysł po prostu unieważnia kilka możliwości dla tego, kto wie o nim. Odszyfrowanie przez Eve nie nastąpi.$(10)^n$$n$

Poproś Boba, aby pomnożył liczbę przez 2 lub 3 lub cokolwiek innego i xor tę liczbę z samym numerem. Można to zrobić ręcznie i można je odwrócić, jeśli numer jest znany. Bez Sha, RSA lub MD5. Po prostu matematyka.

Wyślij Bobowi słowo kodowe zaszyfrowane twoim numerem telefonu; jeśli odeśle ci słowo kodowe, wiesz, że ma poprawny numer.

Słabość polega na tym, że Ewa może symulować Boba, więc po prostu wypróbuj każdy numer telefonu, aż dostanie ten, który podaje jakieś słowo kodowe po powrocie Boba.

Niech Bob doda bardzo dużą liczbę losową do słowa kodowego, a następnie zaszyfruje ją przed odesłaniem do ciebie. To sprawia, że ​​przestrzeń wyszukiwania Evesa jest tak duża, jak chcesz.

Napiszę na karcie około 10 numerów telefonów, a wśród nich upewnię się, że mój numer będzie obok numeru Boba i wspomnę „Hej, Bob, mój numer jest obok twojego numeru, proszę zweryfikuj” :)

Myślę, że pytanie jest o wiele prostsze niż wszyscy myślą. Jesteśmy zobowiązani do zweryfikowania, czy numer, który ma Bob, jest poprawny (lub, być może, nieprawidłowy). Ponieważ „sprawdzamy”, czy numer jest poprawny, można założyć, że Bob ma już twój numer. Dlatego nie ma potrzeby wysyłania Bobowi swojego numeru w jakimś kodzie. Moja odpowiedź brzmiałaby: „Drogi Bobie, proszę zadzwonić pod mój numer. Dzięki, Alice”

spróbuj zagrać w trik tak

rozwiązanie 1: jeśli liczba wynosi 37, mapa mieszania wyglądałaby tak

01 07

15 12

25 20

31 36

49 43

53 50

60 62

72 72

85 82

91 94

i zrób to samo dla 10 cyfr lub nawet więcej, aby pomylić: P

rozwiązanie2: lub zbuduj wielomian, w którym Twój numer stanie się inną unikalną liczbą

rozwiązanie 3: napisz to w liście „koleś, zadzwoń do mnie”

rozwiązanie4: napisz funkcję w taki sposób, że wykonuje operacje na każdej cyfrze i zwraca 0, a następnie wyśle ​​true lub false rozwiązanie5: jeśli oba końce mają wspólną funkcję skrótu ... to bardzo ułatwia życie

Myślę, że możemy to zrobić za pomocą podstawowych operacji bitowych lub dostosować go do pracy na papierze i ołówku. Jeśli liczba alice jest na przykład: 663, to może po prostu przekonwertować liczbę przy użyciu tej metodologii. Konwertuj każdą cyfrę na równoważną reprezentację binarną, powiedz to jako A 663-> 110 110 011, niż odwróć odpowiednie bity dla każdej indywidualnej liczby, powiedz to jako B-> 011 011 110 Teraz zrób A i B-> 010 010 010 Teraz wyślij ten numer na bob i poproś o zrobienie tego samego, jeśli wynik przyjdzie tak samo, poproś go, aby powiedział tak lub nie. W tym przypadku wigilia nie będzie w stanie dekodować numeru i istnieje bardzo małe prawdopodobieństwo, że różne liczby zakończą tę samą reprezentację. Jedynym sposobem, w jaki mogliby się domyślić, jest napisanie wszystkich możliwych kombinacji, a następnie wypróbowanie ich wszystkich, ale w celu zaspokojenia, że ​​możemy to jeszcze bardziej skomplikować, używając przesunięcia w lewo lub w prawo i dodając atrapy.

Proszę do mnie zadzwonić (nazywam się 1001001). Jeśli nie możesz się ze mną skontaktować, zapisz swój numer telefonu i poproś Eve o zwrot.

Objaśnienie: jeśli Bob dostał mój poprawny #, może do mnie dotrzeć, to wiem, że to poprawny #; jeśli Bob nie dostał mojego poprawnego #, Ewa nie może również odczytać mojego (poprawnego) numeru telefonu. W ten sposób już sprawdziłem, czy mój przyjaciel, Bob, ma mój prawidłowy numer telefonu, czy nie.