Comments 71
Камень, ножницы, бумага… (ящерица, Спок)
Простите, почему-то вспомнилось, как способ разрешения проблемы «кто идёт за Клинским» :)
Простите, почему-то вспомнилось, как способ разрешения проблемы «кто идёт за Клинским» :)
+12
простите, но мне осталось непонятным 2 момента:
1) зачем им распределенный протокол, если они все в одной комнате? (это как бы шутка)
2) может это и очевидно, но в тексте не сказано как принять решение о том кому бежать на основании сделанного выбора
заранее спасибо за терпеливый и благожелательный тон ответа. :)
1) зачем им распределенный протокол, если они все в одной комнате? (это как бы шутка)
2) может это и очевидно, но в тексте не сказано как принять решение о том кому бежать на основании сделанного выбора
заранее спасибо за терпеливый и благожелательный тон ответа. :)
+1
может это и очевидно, но в тексте не сказано как принять решение о том кому бежать на основании сделанного выбораБежать первому или последнему из списка. Об этом надо договориться до фазы расшифровки…
0
Алиса же в конце выбирает одно имя. Ему и бежать.
+2
А как бросить жребий на то, в каком порядке кто шифрует? :)
0
Алиса может все 4 раза написать «Боб». Они ведь не будут напряжённо расшифровывать все остальные строчки, чтобы это исключить.
А чтобы получились разные шифрованные тексты, немного варьировать написание. «Боб», «Бобби», «Роберт», «Конечно, Боб!»
А чтобы получились разные шифрованные тексты, немного варьировать написание. «Боб», «Бобби», «Роберт», «Конечно, Боб!»
+6
UFO just landed and posted this here
>>И спасибо моей музе за помощь в подготовке статьи
Вы серьезно? Вы считаете необходимым заниматься подкаблучничеством на хабре за помощь в подготовке этого кусочка текста, размером меньше сочинения школьника? Или вы вообще считаете необходимым заикаться о какой-либо подготовке статьи такого размера и сомнительного содержания?
Вы серьезно? Вы считаете необходимым заниматься подкаблучничеством на хабре за помощь в подготовке этого кусочка текста, размером меньше сочинения школьника? Или вы вообще считаете необходимым заикаться о какой-либо подготовке статьи такого размера и сомнительного содержания?
-7
Почитайте другие статьи из хаба в который Вы поместили Вашу. Пусть Вам будет стыдно, хоть чуть-чуть.
Зачем высасывать проблему из пальца и придумывать самое неадекватное решение из возможных? Жребий? 4 бумажки с именами в помощь.
Зачем высасывать проблему из пальца и придумывать самое неадекватное решение из возможных? Жребий? 4 бумажки с именами в помощь.
-8
С таким подходом вы сможете раскритиковать половину алгоритмов в книге Брюса Шнайера
+4
алгоритмы на то и алгоритмы чтобы их применять там, где нужно. а не в компании алкашей.
-11
Участники нужны для наглядности. И на решении их проблемы демонстрируются шаги алгоритма. Конечно можно было бы формализовать алгоритм и записать все взаимодействия в алгебраическом виде. Это хорошо для проверки протокола, но не для его понимания
+4
Согласитесь, для алкашей, которые решают споры между собой при помощи криптографии, еще не всё потеряно!
+14
Можно же проще.
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 выбирается идущий за пивом.
+3
Кажется это работает только при N = 2 ^ k.
0
Не только. Пусть разрядность результата 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
Участники нумеруются по порядку. Затем скрытно записывают на бумаге число от 0 до N-1 (N — число участников). Числа открываются, складываются по модулю N. Участник, номер которого получен в результате этого, идет за пивом.
0
Никто из участников не должен узнать числа других, пока не отправит собственное. Для этого нужная третья доверенная сторона. В реальном мире ее роль исполняет шапка, куда кидают бумажки, но по условиям задачи такой стороны нет. Участники могут только пересылать сообщения друг другу.
0
Последний кто показывает своё число может подменить его и подобрать такое, что жребий его не выберет
0
Неплохо бы объяснить, чем поэтапное шифрование/дешифровка лучше шляпы с бумажками.
0
Понял. Другой вопрос: как насчёт варианта заготовки первым участником N алгоритмов для дешифровки в нужный вариант, чтобы не зависить от других?
0
Для этого можно сразу договориться с алгоритмом. Другой вопрос что для слабого алгоритма можно подобрать разные ключи, которые будут давать нужные результаты. Но это решается добавлением случайной строки в сообщение и выбором стойкого алгоритма шифрования
0
То есть Алиса должна подготовить N разных шифротекстов и N! ключей так, чтобы расшифровка первым ключом давала {«Алиса», «Боб», «Дейв», «Кэрол»}, вторым — {«Боб», «Дейв», «Кэрол», «Алиса»} (в другом порядке) и т.д. Для сильных алгоритмов это нереально.
Но даже если Алиса это сделает, как она узнает, какой из ключей публиковать? Ведь строки перемешаны другими участниками и зашифрованы ими.
Но даже если Алиса это сделает, как она узнает, какой из ключей публиковать? Ведь строки перемешаны другими участниками и зашифрованы ими.
0
Насколько я понял, публикация ключа происходит после получения 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
В таком случае при выбранном коде можно определить любой из объектов.
+1
Алгоритм действительно нуждается в корректировке! Ключи должны публиковаться в том же порядке, в котором шло шифрование, то есть начиная с Алисы.
Насчет циклических кодов — вы правы.
Насчет циклических кодов — вы правы.
+1
Тогда тот, кто последним шифровал, сможет выбрать нужные ему ключи.
0
Не сможет, ведь все знают и входное сообщение этого участника, и выходное.
Единственное, что может сделать Дейв — узнать раньше остальных результат броска, и если за клинским выпало бежать именно ему, просто сорвать голосование, назвав вместо валидного ключа мусор. И делать так, пока не выпадет удовлетворительный результат. Тоже, кстати, уязвимость!
Единственное, что может сделать Дейв — узнать раньше остальных результат броска, и если за клинским выпало бежать именно ему, просто сорвать голосование, назвав вместо валидного ключа мусор. И делать так, пока не выпадет удовлетворительный результат. Тоже, кстати, уязвимость!
+2
Кстати, да, уязвимость. Причем похоже, что общая для всех систем, использующих ключи — тот, кто раскрывает свой ключ последним, всегда может сорвать голосование в случае неблагоприятного для себя варианта.
0
Пожалуй, единственное, что тут можно сделать — автоматически признавать проигравшим участника, сорвавшего процедуру.
Но тогда никто не захочет становиться крайним (т.к. технический сбой тоже будет приводить к плачевному для него результату). Значит, нужен алгоритм, честно определяющий порядок участников. Замкнутый круг!
Но тогда никто не захочет становиться крайним (т.к. технический сбой тоже будет приводить к плачевному для него результату). Значит, нужен алгоритм, честно определяющий порядок участников. Замкнутый круг!
+1
Прикол в том, что потенциально сорвать процедуру может любой из участников, и определить, кто именно сорвал — невозможно.
0
С таким же успехом технический сбой может любой результат испортить
0
Верно. Но если сбой на любом из промежуточных этапов не приносит выгоды никому из участников, его (сбой) можно признать техническим и просто начать процедуру заново. А вот сбой на последнем этапе (когда опубликованы все ключи, кроме ключа Дейва) может быть как техническим, так и результатом нечестной игры Дейва. Так как различить эти случаи невозможно, мы вынуждены предположить худшее — что Дейв жульничает, и признать его проигравшим.
То есть все, кроме Дейва, за сбой не штрафуются, а Дейв — штрафуется. Значит, последним в цепочке быть невыгодно.
То есть все, кроме Дейва, за сбой не штрафуются, а Дейв — штрафуется. Значит, последним в цепочке быть невыгодно.
0
Вот только последней расшифровывает Алиса.
Да и они могут проверить что всё зашифровалось правильно, попытавшить расшифровать до того, как был выбран один из результатов. Тогда если они вовремя не сказали о сбое — то это их вина.
Да и они могут проверить что всё зашифровалось правильно, попытавшить расшифровать до того, как был выбран один из результатов. Тогда если они вовремя не сказали о сбое — то это их вина.
0
Мы сейчас обсуждаем версию алгоритма, в которой ключи публикуются по порядку следования участников (А->B->C->D), а расшифровка идет в обратном порядке. В ней Дейв может узнать результат раньше других, и если ему не понравилось, сбросить всю процедуру.
В изначальной версии этой дыры (вроде) нет. Зато есть другая, с подбором коллизий Алисой.
В изначальной версии этой дыры (вроде) нет. Зато есть другая, с подбором коллизий Алисой.
0
В начальной версии эта дыра тоже есть — Алиса так же может все сорвать, выдав неправильный ключ. Да и в конечной версии Дейв может подобрать коллизии, хотя ему это сделать труднее — он может подбирать только ключи.
Вообще-то, проблема коллизий — это проблема алгоритма шифрования, а не алгоритма жребия. Кроме того, все участники могут сообщить свои идентификаторы, с условием использования Алисой исключительно их, это сравняет Алису и Дейва по возможностям.
А по поводу последнего в цепочке — тут решение простое: при обнаружении сбоя нужно штрафовать виноватого, а не перезапускать алгоритм снова. Это, в частности, исключит возможность сговора Кэрола с Дейвом, при котором Дейв говорит свой ключ Кэрол, а Кэрол решает (в интересах себя и Дейва), сорвать процесс или нет.
Вообще-то, проблема коллизий — это проблема алгоритма шифрования, а не алгоритма жребия. Кроме того, все участники могут сообщить свои идентификаторы, с условием использования Алисой исключительно их, это сравняет Алису и Дейва по возможностям.
А по поводу последнего в цепочке — тут решение простое: при обнаружении сбоя нужно штрафовать виноватого, а не перезапускать алгоритм снова. Это, в частности, исключит возможность сговора Кэрола с Дейвом, при котором Дейв говорит свой ключ Кэрол, а Кэрол решает (в интересах себя и Дейва), сорвать процесс или нет.
+1
Дейву шифровать необязательно, может просто перемешать
0
Вобщем-то показанный алгоритм не соответствует решаемой задаче. (Насколько я понимаю это алгоритм Честных выборов Меррита). В той же прикладной криптографии есть алгоритм честного бросания монетки, и в данном конкретном случае, вполне себе достаточно обобщить его на количество участников > 2.
Например так:
Каждый участник голосования пишет имя, добавляет к нему рандомную строку. Шифрует произвольным ключом.
Показывает всем хеш и рандомную строку.
После того, как все показали свою значения hash + Random — можно публично оглашать результаты + в подтверждение показывать свой ключ для проверки.
В данном конкретном случае такой алгоритм позволит уберечься от каких-то лишних телодвижений.
Например так:
Каждый участник голосования пишет имя, добавляет к нему рандомную строку. Шифрует произвольным ключом.
Показывает всем хеш и рандомную строку.
После того, как все показали свою значения hash + Random — можно публично оглашать результаты + в подтверждение показывать свой ключ для проверки.
В данном конкретном случае такой алгоритм позволит уберечься от каких-то лишних телодвижений.
0
Да, я начинал размышления с алгоритма подбрасывания монетки и расширил его на такой случай
0
> Каждый участник голосования пишет имя
Своё имя?
>После того, как все показали свою значения hash + Random — можно публично оглашать результаты
Кажется, у вас пропущен какой-то важный этап. Вот есть четыре хеша и четыре соли, а как результат броска-то вычислить?
Своё имя?
>После того, как все показали свою значения hash + Random — можно публично оглашать результаты
Кажется, у вас пропущен какой-то важный этап. Вот есть четыре хеша и четыре соли, а как результат броска-то вычислить?
0
Ах боже мой, прошу прощения — в пылу сражений я неверно осознал для себя задачу и предложил решение для честного открытого голосования. для отправки гонца.
По сей причине приношу свои извинения.
По сути своей я просто предложил публичную проверку по примеру авторизации в Unix.
По сей причине приношу свои извинения.
По сути своей я просто предложил публичную проверку по примеру авторизации в Unix.
+1
UPD — для решения исходной задачи — делаем то же самое, но пишем вместо имени избранника рандомное число. В конце считаем что-то наподобие div 4 от суммы всех чисел и отправляем участника под сим гордым номером за пивом.
+1
А как это случайное число выбрать так, чтобы все верили что их не подставили?
0
А по сути своей не важно как будет выбираться ЗНАЧАЩЕЕ число(то которое будет складываться в общую сумму). Ведь мы же не будем знать такие числа для других участников голосования. Его достоверность мы в конце просто проверим сложив с солью и применив к ним ключ — на выходе должны получить заявленный в начале hash.
Ну а сумма рандомных чисел от каждого участника — есть величина случайная(если не брать во внимание возможность любимых чисел и прочих индивидуальных особенностей).
Ну а сумма рандомных чисел от каждого участника — есть величина случайная(если не брать во внимание возможность любимых чисел и прочих индивидуальных особенностей).
+1
Ага, я такой алгоритм уже предложил. Только без соли.
0
Да, посыпаю голову пеплом, в вашем алгоритме хеш считается только один раз, хотя меня и смущает доверие одному человеку функции держателя секрета (то-есть когда от его данных зависит результат).
0
Меня тоже смущает, но ошибок пока не вижу. Секрет Алисы проверяется всеми остальными участниками, так что возможностей смухлевать у нее вроде бы нет.
0
По дороге домой размышлял, каким бы образом я пытался мухлевать в данной ситуации и таки придумал, что можно сделать.
Если Алиса состоит в сговоре с кем-то, то она может либо вбить число состоящее из одних только нулей и таким образом отказаться от своего голоса, либо сообщить последнему голосующему свое число(по сути то же самое, но на одну операцию вычисления больше).
В чистом остатке — Алиса + последний голосующий решают кого отправить в поход. Стойкость алгоритма должна гарантироваться невозможностью менять результат в процессе объявления.
Если Алиса состоит в сговоре с кем-то, то она может либо вбить число состоящее из одних только нулей и таким образом отказаться от своего голоса, либо сообщить последнему голосующему свое число(по сути то же самое, но на одну операцию вычисления больше).
В чистом остатке — Алиса + последний голосующий решают кого отправить в поход. Стойкость алгоритма должна гарантироваться невозможностью менять результат в процессе объявления.
+2
От этого можно защититься, если вместо простого xor применять, например, конкатенацию + хэш. Чтобы зная некоторые части, было вычислительно сложно подобрать оставшуюся часть так, чтобы получить нужный результат.
Хотя при небольшом числе участников, даже для сильной хэш-функции достаточно непродолжительного брутфорса.
Решить проблему сговора можно также, проведя несколько раундов, в каждом из которых меняя порядок участников. Так как исказить исход раунда могут только первый+последний, для подтасовки всех раундов необходим сговор всех участников. Надо только хорошо продумать алгоритм перестановки, чтобы минимизировать необходимое число раундов.
Хотя при небольшом числе участников, даже для сильной хэш-функции достаточно непродолжительного брутфорса.
Решить проблему сговора можно также, проведя несколько раундов, в каждом из которых меняя порядок участников. Так как исказить исход раунда могут только первый+последний, для подтасовки всех раундов необходим сговор всех участников. Надо только хорошо продумать алгоритм перестановки, чтобы минимизировать необходимое число раундов.
0
Ну если абстрагироваться от конкретной ситуации — если известен алгоритм расчета значений — просчитать результат не проблема. Если алгоритм неизвестен, то рано или поздно он станет известен :)
Несколько раундов опять же решают проблему только частично — при сговоре вероятность выбора неугодного человека все-равно в несколько раз больше честного голосования(прямо пропорционально количеству заговорщиков), т.к достаточно только выпасть паре — сговорщик с шифрованным сообщением+сговорщик голосующий последним и результат определен.
В варианте, который я предложил, даже если 3 из 4 человек участвуют в сговоре, они не могут предугадать, что конкретно загадает жертва + секрет не зависит от вариантов алгоритма подсчета.
Этот алгоритм конечно не защищен с точки зрения отрицания(можно конечно добавить неотрицаемые подписи), но для данной задачи это не принципиально.
Несколько раундов опять же решают проблему только частично — при сговоре вероятность выбора неугодного человека все-равно в несколько раз больше честного голосования(прямо пропорционально количеству заговорщиков), т.к достаточно только выпасть паре — сговорщик с шифрованным сообщением+сговорщик голосующий последним и результат определен.
В варианте, который я предложил, даже если 3 из 4 человек участвуют в сговоре, они не могут предугадать, что конкретно загадает жертва + секрет не зависит от вариантов алгоритма подсчета.
Этот алгоритм конечно не защищен с точки зрения отрицания(можно конечно добавить неотрицаемые подписи), но для данной задачи это не принципиально.
0
Итоговый результат не выбирается большинством голосов (у нас же не голосование, мы жребий бросаем). Результаты раундов ксорятся между собой, или еще как-нибудь перемешиваются. Таким образом, если хотя бы один раунд проведен честно, результат будет абсолютно случайным.
Но ваш вариант лучше.
По поводу неотрицаемости: я не уверен, что ее вообще можно обеспечить в среде, где никто никому не доверяет, и возможен сговор всех участников против одного.
Но ваш вариант лучше.
По поводу неотрицаемости: я не уверен, что ее вообще можно обеспечить в среде, где никто никому не доверяет, и возможен сговор всех участников против одного.
0
В плане сложности алгоритма — если использовать алгоритм с шифрованием голоса каждого участника то получаем N вычислений
Если использовать конкатенацию + hash на этапе вычисления результатов — это те же самые N вычислений хэша, но при этом мы не решаем проблему, если последним голосует заговорщик — ему всего-лишь нужно будет в онлайне просчитывать хэши а не суммы или xor-ы
Если использовать конкатенацию + hash на этапе вычисления результатов — это те же самые N вычислений хэша, но при этом мы не решаем проблему, если последним голосует заговорщик — ему всего-лишь нужно будет в онлайне просчитывать хэши а не суммы или xor-ы
0
Это не «честный жребий».
Алиса может придумать 4 разных ключа, чтобы в зависимости от ключа при расшифровке получились разные имена. И когда придёт её очередь расшифровывать — она выберет тот ключ который ей выгоден. Никто не следит за ней пока она зашифровывает, по этому никто не может заподозрить что она использует не тот ключ.
Если я конечно правильно понял условие.
Алиса может придумать 4 разных ключа, чтобы в зависимости от ключа при расшифровке получились разные имена. И когда придёт её очередь расшифровывать — она выберет тот ключ который ей выгоден. Никто не следит за ней пока она зашифровывает, по этому никто не может заподозрить что она использует не тот ключ.
Если я конечно правильно понял условие.
0
промахнулся
0
А если тролем является Дейв, то он может наугад отбросить три варианта и зашифровать четвертый четырьмя разными ключами, так результаты будут разными, и в зависимости от того что выберет Алиса открыть тот или иной ключ.
-1
Участникам даётся порядковый номер: 0… n-1. Каждый участник придумывает число. Затем, эти числа складываются и вычисляется остаток от деления на n. Результат — номер участника, который бежит за пивом.
+1
Sign up to leave a comment.
Честный жребий