Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 71
Камень, ножницы, бумага… (ящерица, Спок)
Простите, почему-то вспомнилось, как способ разрешения проблемы «кто идёт за Клинским» :)
Простите, почему-то вспомнилось, как способ разрешения проблемы «кто идёт за Клинским» :)
простите, но мне осталось непонятным 2 момента:
1) зачем им распределенный протокол, если они все в одной комнате? (это как бы шутка)
2) может это и очевидно, но в тексте не сказано как принять решение о том кому бежать на основании сделанного выбора
заранее спасибо за терпеливый и благожелательный тон ответа. :)
1) зачем им распределенный протокол, если они все в одной комнате? (это как бы шутка)
2) может это и очевидно, но в тексте не сказано как принять решение о том кому бежать на основании сделанного выбора
заранее спасибо за терпеливый и благожелательный тон ответа. :)
может это и очевидно, но в тексте не сказано как принять решение о том кому бежать на основании сделанного выбораБежать первому или последнему из списка. Об этом надо договориться до фазы расшифровки…
Алиса может все 4 раза написать «Боб». Они ведь не будут напряжённо расшифровывать все остальные строчки, чтобы это исключить.
А чтобы получились разные шифрованные тексты, немного варьировать написание. «Боб», «Бобби», «Роберт», «Конечно, Боб!»
А чтобы получились разные шифрованные тексты, немного варьировать написание. «Боб», «Бобби», «Роберт», «Конечно, Боб!»
>>И спасибо моей музе за помощь в подготовке статьи
Вы серьезно? Вы считаете необходимым заниматься подкаблучничеством на хабре за помощь в подготовке этого кусочка текста, размером меньше сочинения школьника? Или вы вообще считаете необходимым заикаться о какой-либо подготовке статьи такого размера и сомнительного содержания?
Вы серьезно? Вы считаете необходимым заниматься подкаблучничеством на хабре за помощь в подготовке этого кусочка текста, размером меньше сочинения школьника? Или вы вообще считаете необходимым заикаться о какой-либо подготовке статьи такого размера и сомнительного содержания?
Почитайте другие статьи из хаба в который Вы поместили Вашу. Пусть Вам будет стыдно, хоть чуть-чуть.
Зачем высасывать проблему из пальца и придумывать самое неадекватное решение из возможных? Жребий? 4 бумажки с именами в помощь.
Зачем высасывать проблему из пальца и придумывать самое неадекватное решение из возможных? Жребий? 4 бумажки с именами в помощь.
С таким подходом вы сможете раскритиковать половину алгоритмов в книге Брюса Шнайера
алгоритмы на то и алгоритмы чтобы их применять там, где нужно. а не в компании алкашей.
Участники нужны для наглядности. И на решении их проблемы демонстрируются шаги алгоритма. Конечно можно было бы формализовать алгоритм и записать все взаимодействия в алгебраическом виде. Это хорошо для проверки протокола, но не для его понимания
Согласитесь, для алкашей, которые решают споры между собой при помощи криптографии, еще не всё потеряно!
Можно же проще.
0) Для любого количества участников задача сводится к совместной генерации случайного числа (достаточно большой разрядности), т.к. его легко привести к нужному диапазону (в случае N=4 — к [1;4]).
1) Алиса генерирует случайное число X0 и вычисляет его хеш H(X0) при помощи стойкой функции.
2) Алиса публикует H(X0).
3) Остальные участники генерируют каждый по случайному числу X1, X2… XN-1 и публикуют эти числа.
4) Алиса вычисляет результат броска жребия как Y = X0 xor X1 xor X2… xor XN-1 и публикует его.
5) Алиса публикует X0, чтобы каждый мог проверить ее честностьи побить канделябром в случае обмана, сравнив H(X0) с опубликованным на шаге 2.
6) На основе Y выбирается идущий за пивом.
0) Для любого количества участников задача сводится к совместной генерации случайного числа (достаточно большой разрядности), т.к. его легко привести к нужному диапазону (в случае N=4 — к [1;4]).
1) Алиса генерирует случайное число X0 и вычисляет его хеш H(X0) при помощи стойкой функции.
2) Алиса публикует H(X0).
3) Остальные участники генерируют каждый по случайному числу X1, X2… XN-1 и публикуют эти числа.
4) Алиса вычисляет результат броска жребия как Y = X0 xor X1 xor X2… xor XN-1 и публикует его.
5) Алиса публикует X0, чтобы каждый мог проверить ее честность
6) На основе Y выбирается идущий за пивом.
Кажется это работает только при N = 2 ^ k.
Не только. Пусть разрядность результата Z, а число участников N, и 2Z не делится на N.
Выбираем делящееся на N число M < 2Z, максимально близкое к 2Z. Если Y < M, то номер гонца определяется как Y mod N.
Если Y >= M, значит выпало одно из «запрещенных» значений, которых может быть не более (N-1). При достаточно большом Z вероятность такого исхода исчезающе мала. Можно повторить бросок, а можно признать это знаком свыше и прекратить пьянку.
Выбираем делящееся на N число M < 2Z, максимально близкое к 2Z. Если Y < M, то номер гонца определяется как Y mod N.
Если Y >= M, значит выпало одно из «запрещенных» значений, которых может быть не более (N-1). При достаточно большом Z вероятность такого исхода исчезающе мала. Можно повторить бросок, а можно признать это знаком свыше и прекратить пьянку.
Участники нумеруются по порядку. Затем скрытно записывают на бумаге число от 0 до N-1 (N — число участников). Числа открываются, складываются по модулю N. Участник, номер которого получен в результате этого, идет за пивом.
Никто из участников не должен узнать числа других, пока не отправит собственное. Для этого нужная третья доверенная сторона. В реальном мире ее роль исполняет шапка, куда кидают бумажки, но по условиям задачи такой стороны нет. Участники могут только пересылать сообщения друг другу.
Последний кто показывает своё число может подменить его и подобрать такое, что жребий его не выберет
Неплохо бы объяснить, чем поэтапное шифрование/дешифровка лучше шляпы с бумажками.
Написал выше. Шляпа с бумажками — это доверенная сторона, которая принимает сообщения от всех участников и не раскрывает их раньше времени.
Понял. Другой вопрос: как насчёт варианта заготовки первым участником N алгоритмов для дешифровки в нужный вариант, чтобы не зависить от других?
Для этого можно сразу договориться с алгоритмом. Другой вопрос что для слабого алгоритма можно подобрать разные ключи, которые будут давать нужные результаты. Но это решается добавлением случайной строки в сообщение и выбором стойкого алгоритма шифрования
То есть Алиса должна подготовить N разных шифротекстов и N! ключей так, чтобы расшифровка первым ключом давала {«Алиса», «Боб», «Дейв», «Кэрол»}, вторым — {«Боб», «Дейв», «Кэрол», «Алиса»} (в другом порядке) и т.д. Для сильных алгоритмов это нереально.
Но даже если Алиса это сделает, как она узнает, какой из ключей публиковать? Ведь строки перемешаны другими участниками и зашифрованы ими.
Но даже если Алиса это сделает, как она узнает, какой из ключей публиковать? Ведь строки перемешаны другими участниками и зашифрованы ими.
Насколько я понял, публикация ключа происходит после получения feedback'а. То есть, первый человек видит коды, мысленно перебирает подготовленные ключи, находит нужный из них с совпадением кода и шифровки целевого объекта И ТОЛЬКО ПОТОМ достаёт ключ из кармана.
Да и не нужно N! ключей (если выбор происходит только для одного объекта), достаточно N с циклическими кодами. Пример:
А Б В Г
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
В таком случае при выбранном коде можно определить любой из объектов.
Да и не нужно N! ключей (если выбор происходит только для одного объекта), достаточно N с циклическими кодами. Пример:
А Б В Г
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
В таком случае при выбранном коде можно определить любой из объектов.
Алгоритм действительно нуждается в корректировке! Ключи должны публиковаться в том же порядке, в котором шло шифрование, то есть начиная с Алисы.
Насчет циклических кодов — вы правы.
Насчет циклических кодов — вы правы.
Тогда тот, кто последним шифровал, сможет выбрать нужные ему ключи.
Не сможет, ведь все знают и входное сообщение этого участника, и выходное.
Единственное, что может сделать Дейв — узнать раньше остальных результат броска, и если за клинским выпало бежать именно ему, просто сорвать голосование, назвав вместо валидного ключа мусор. И делать так, пока не выпадет удовлетворительный результат. Тоже, кстати, уязвимость!
Единственное, что может сделать Дейв — узнать раньше остальных результат броска, и если за клинским выпало бежать именно ему, просто сорвать голосование, назвав вместо валидного ключа мусор. И делать так, пока не выпадет удовлетворительный результат. Тоже, кстати, уязвимость!
Кстати, да, уязвимость. Причем похоже, что общая для всех систем, использующих ключи — тот, кто раскрывает свой ключ последним, всегда может сорвать голосование в случае неблагоприятного для себя варианта.
Пожалуй, единственное, что тут можно сделать — автоматически признавать проигравшим участника, сорвавшего процедуру.
Но тогда никто не захочет становиться крайним (т.к. технический сбой тоже будет приводить к плачевному для него результату). Значит, нужен алгоритм, честно определяющий порядок участников. Замкнутый круг!
Но тогда никто не захочет становиться крайним (т.к. технический сбой тоже будет приводить к плачевному для него результату). Значит, нужен алгоритм, честно определяющий порядок участников. Замкнутый круг!
Прикол в том, что потенциально сорвать процедуру может любой из участников, и определить, кто именно сорвал — невозможно.
С таким же успехом технический сбой может любой результат испортить
Верно. Но если сбой на любом из промежуточных этапов не приносит выгоды никому из участников, его (сбой) можно признать техническим и просто начать процедуру заново. А вот сбой на последнем этапе (когда опубликованы все ключи, кроме ключа Дейва) может быть как техническим, так и результатом нечестной игры Дейва. Так как различить эти случаи невозможно, мы вынуждены предположить худшее — что Дейв жульничает, и признать его проигравшим.
То есть все, кроме Дейва, за сбой не штрафуются, а Дейв — штрафуется. Значит, последним в цепочке быть невыгодно.
То есть все, кроме Дейва, за сбой не штрафуются, а Дейв — штрафуется. Значит, последним в цепочке быть невыгодно.
Вот только последней расшифровывает Алиса.
Да и они могут проверить что всё зашифровалось правильно, попытавшить расшифровать до того, как был выбран один из результатов. Тогда если они вовремя не сказали о сбое — то это их вина.
Да и они могут проверить что всё зашифровалось правильно, попытавшить расшифровать до того, как был выбран один из результатов. Тогда если они вовремя не сказали о сбое — то это их вина.
Мы сейчас обсуждаем версию алгоритма, в которой ключи публикуются по порядку следования участников (А->B->C->D), а расшифровка идет в обратном порядке. В ней Дейв может узнать результат раньше других, и если ему не понравилось, сбросить всю процедуру.
В изначальной версии этой дыры (вроде) нет. Зато есть другая, с подбором коллизий Алисой.
В изначальной версии этой дыры (вроде) нет. Зато есть другая, с подбором коллизий Алисой.
В начальной версии эта дыра тоже есть — Алиса так же может все сорвать, выдав неправильный ключ. Да и в конечной версии Дейв может подобрать коллизии, хотя ему это сделать труднее — он может подбирать только ключи.
Вообще-то, проблема коллизий — это проблема алгоритма шифрования, а не алгоритма жребия. Кроме того, все участники могут сообщить свои идентификаторы, с условием использования Алисой исключительно их, это сравняет Алису и Дейва по возможностям.
А по поводу последнего в цепочке — тут решение простое: при обнаружении сбоя нужно штрафовать виноватого, а не перезапускать алгоритм снова. Это, в частности, исключит возможность сговора Кэрола с Дейвом, при котором Дейв говорит свой ключ Кэрол, а Кэрол решает (в интересах себя и Дейва), сорвать процесс или нет.
Вообще-то, проблема коллизий — это проблема алгоритма шифрования, а не алгоритма жребия. Кроме того, все участники могут сообщить свои идентификаторы, с условием использования Алисой исключительно их, это сравняет Алису и Дейва по возможностям.
А по поводу последнего в цепочке — тут решение простое: при обнаружении сбоя нужно штрафовать виноватого, а не перезапускать алгоритм снова. Это, в частности, исключит возможность сговора Кэрола с Дейвом, при котором Дейв говорит свой ключ Кэрол, а Кэрол решает (в интересах себя и Дейва), сорвать процесс или нет.
Дейву шифровать необязательно, может просто перемешать
Вобщем-то показанный алгоритм не соответствует решаемой задаче. (Насколько я понимаю это алгоритм Честных выборов Меррита). В той же прикладной криптографии есть алгоритм честного бросания монетки, и в данном конкретном случае, вполне себе достаточно обобщить его на количество участников > 2.
Например так:
Каждый участник голосования пишет имя, добавляет к нему рандомную строку. Шифрует произвольным ключом.
Показывает всем хеш и рандомную строку.
После того, как все показали свою значения hash + Random — можно публично оглашать результаты + в подтверждение показывать свой ключ для проверки.
В данном конкретном случае такой алгоритм позволит уберечься от каких-то лишних телодвижений.
Например так:
Каждый участник голосования пишет имя, добавляет к нему рандомную строку. Шифрует произвольным ключом.
Показывает всем хеш и рандомную строку.
После того, как все показали свою значения hash + Random — можно публично оглашать результаты + в подтверждение показывать свой ключ для проверки.
В данном конкретном случае такой алгоритм позволит уберечься от каких-то лишних телодвижений.
Да, я начинал размышления с алгоритма подбрасывания монетки и расширил его на такой случай
> Каждый участник голосования пишет имя
Своё имя?
>После того, как все показали свою значения hash + Random — можно публично оглашать результаты
Кажется, у вас пропущен какой-то важный этап. Вот есть четыре хеша и четыре соли, а как результат броска-то вычислить?
Своё имя?
>После того, как все показали свою значения hash + Random — можно публично оглашать результаты
Кажется, у вас пропущен какой-то важный этап. Вот есть четыре хеша и четыре соли, а как результат броска-то вычислить?
Ах боже мой, прошу прощения — в пылу сражений я неверно осознал для себя задачу и предложил решение для честного открытого голосования. для отправки гонца.
По сей причине приношу свои извинения.
По сути своей я просто предложил публичную проверку по примеру авторизации в Unix.
По сей причине приношу свои извинения.
По сути своей я просто предложил публичную проверку по примеру авторизации в Unix.
UPD — для решения исходной задачи — делаем то же самое, но пишем вместо имени избранника рандомное число. В конце считаем что-то наподобие div 4 от суммы всех чисел и отправляем участника под сим гордым номером за пивом.
А как это случайное число выбрать так, чтобы все верили что их не подставили?
А по сути своей не важно как будет выбираться ЗНАЧАЩЕЕ число(то которое будет складываться в общую сумму). Ведь мы же не будем знать такие числа для других участников голосования. Его достоверность мы в конце просто проверим сложив с солью и применив к ним ключ — на выходе должны получить заявленный в начале hash.
Ну а сумма рандомных чисел от каждого участника — есть величина случайная(если не брать во внимание возможность любимых чисел и прочих индивидуальных особенностей).
Ну а сумма рандомных чисел от каждого участника — есть величина случайная(если не брать во внимание возможность любимых чисел и прочих индивидуальных особенностей).
Ага, я такой алгоритм уже предложил. Только без соли.
Да, посыпаю голову пеплом, в вашем алгоритме хеш считается только один раз, хотя меня и смущает доверие одному человеку функции держателя секрета (то-есть когда от его данных зависит результат).
Меня тоже смущает, но ошибок пока не вижу. Секрет Алисы проверяется всеми остальными участниками, так что возможностей смухлевать у нее вроде бы нет.
По дороге домой размышлял, каким бы образом я пытался мухлевать в данной ситуации и таки придумал, что можно сделать.
Если Алиса состоит в сговоре с кем-то, то она может либо вбить число состоящее из одних только нулей и таким образом отказаться от своего голоса, либо сообщить последнему голосующему свое число(по сути то же самое, но на одну операцию вычисления больше).
В чистом остатке — Алиса + последний голосующий решают кого отправить в поход. Стойкость алгоритма должна гарантироваться невозможностью менять результат в процессе объявления.
Если Алиса состоит в сговоре с кем-то, то она может либо вбить число состоящее из одних только нулей и таким образом отказаться от своего голоса, либо сообщить последнему голосующему свое число(по сути то же самое, но на одну операцию вычисления больше).
В чистом остатке — Алиса + последний голосующий решают кого отправить в поход. Стойкость алгоритма должна гарантироваться невозможностью менять результат в процессе объявления.
От этого можно защититься, если вместо простого xor применять, например, конкатенацию + хэш. Чтобы зная некоторые части, было вычислительно сложно подобрать оставшуюся часть так, чтобы получить нужный результат.
Хотя при небольшом числе участников, даже для сильной хэш-функции достаточно непродолжительного брутфорса.
Решить проблему сговора можно также, проведя несколько раундов, в каждом из которых меняя порядок участников. Так как исказить исход раунда могут только первый+последний, для подтасовки всех раундов необходим сговор всех участников. Надо только хорошо продумать алгоритм перестановки, чтобы минимизировать необходимое число раундов.
Хотя при небольшом числе участников, даже для сильной хэш-функции достаточно непродолжительного брутфорса.
Решить проблему сговора можно также, проведя несколько раундов, в каждом из которых меняя порядок участников. Так как исказить исход раунда могут только первый+последний, для подтасовки всех раундов необходим сговор всех участников. Надо только хорошо продумать алгоритм перестановки, чтобы минимизировать необходимое число раундов.
Ну если абстрагироваться от конкретной ситуации — если известен алгоритм расчета значений — просчитать результат не проблема. Если алгоритм неизвестен, то рано или поздно он станет известен :)
Несколько раундов опять же решают проблему только частично — при сговоре вероятность выбора неугодного человека все-равно в несколько раз больше честного голосования(прямо пропорционально количеству заговорщиков), т.к достаточно только выпасть паре — сговорщик с шифрованным сообщением+сговорщик голосующий последним и результат определен.
В варианте, который я предложил, даже если 3 из 4 человек участвуют в сговоре, они не могут предугадать, что конкретно загадает жертва + секрет не зависит от вариантов алгоритма подсчета.
Этот алгоритм конечно не защищен с точки зрения отрицания(можно конечно добавить неотрицаемые подписи), но для данной задачи это не принципиально.
Несколько раундов опять же решают проблему только частично — при сговоре вероятность выбора неугодного человека все-равно в несколько раз больше честного голосования(прямо пропорционально количеству заговорщиков), т.к достаточно только выпасть паре — сговорщик с шифрованным сообщением+сговорщик голосующий последним и результат определен.
В варианте, который я предложил, даже если 3 из 4 человек участвуют в сговоре, они не могут предугадать, что конкретно загадает жертва + секрет не зависит от вариантов алгоритма подсчета.
Этот алгоритм конечно не защищен с точки зрения отрицания(можно конечно добавить неотрицаемые подписи), но для данной задачи это не принципиально.
Итоговый результат не выбирается большинством голосов (у нас же не голосование, мы жребий бросаем). Результаты раундов ксорятся между собой, или еще как-нибудь перемешиваются. Таким образом, если хотя бы один раунд проведен честно, результат будет абсолютно случайным.
Но ваш вариант лучше.
По поводу неотрицаемости: я не уверен, что ее вообще можно обеспечить в среде, где никто никому не доверяет, и возможен сговор всех участников против одного.
Но ваш вариант лучше.
По поводу неотрицаемости: я не уверен, что ее вообще можно обеспечить в среде, где никто никому не доверяет, и возможен сговор всех участников против одного.
В плане сложности алгоритма — если использовать алгоритм с шифрованием голоса каждого участника то получаем N вычислений
Если использовать конкатенацию + hash на этапе вычисления результатов — это те же самые N вычислений хэша, но при этом мы не решаем проблему, если последним голосует заговорщик — ему всего-лишь нужно будет в онлайне просчитывать хэши а не суммы или xor-ы
Если использовать конкатенацию + hash на этапе вычисления результатов — это те же самые N вычислений хэша, но при этом мы не решаем проблему, если последним голосует заговорщик — ему всего-лишь нужно будет в онлайне просчитывать хэши а не суммы или xor-ы
Это не «честный жребий».
Алиса может придумать 4 разных ключа, чтобы в зависимости от ключа при расшифровке получились разные имена. И когда придёт её очередь расшифровывать — она выберет тот ключ который ей выгоден. Никто не следит за ней пока она зашифровывает, по этому никто не может заподозрить что она использует не тот ключ.
Если я конечно правильно понял условие.
Алиса может придумать 4 разных ключа, чтобы в зависимости от ключа при расшифровке получились разные имена. И когда придёт её очередь расшифровывать — она выберет тот ключ который ей выгоден. Никто не следит за ней пока она зашифровывает, по этому никто не может заподозрить что она использует не тот ключ.
Если я конечно правильно понял условие.
промахнулся
А если тролем является Дейв, то он может наугад отбросить три варианта и зашифровать четвертый четырьмя разными ключами, так результаты будут разными, и в зависимости от того что выберет Алиса открыть тот или иной ключ.
Участникам даётся порядковый номер: 0… n-1. Каждый участник придумывает число. Затем, эти числа складываются и вычисляется остаток от деления на n. Результат — номер участника, который бежит за пивом.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Честный жребий