Напишите, есть ли алгоритмы жеребьевки для n участников. Иначе, говоря, генерации случайного числа, со случайностью которого согласны все участники протокола. Заранее извиняюсь за ламерский вопрос.
Для двух участников проблемы нет. Можно число сгенерить и на хэшах и на блочных шифрах и на произведении простых множителей.
Для n>2 теоретически есть проблемы сговора одних подгрупп участников против других и саботажа жеребьёвки. Но в большинстве случаев сойдёт что-то вроде этого:
1) Участники выбирают себе порядковые номера для жеребьёвки. Могут записываться в список по алфавиту, в порядке живой очереди или произвольно. Главное чтобы после объявления начала жеребьёвки нельзя было отказаться от своего номера.
Также участники публикуют данные для проверки своих сертификатов или подписей – если опасаются, что человек посредине в неподконтрольной сети или на недоверенном сервере будет создавать неверную картину для участников.
2) Каждый из участников генерирует случайное число, сохраняет его в тайне, публикует его криптостойкий хэш, вместе со своим порядковым номером, текущим временем, названием жеребьевки и заверяет всё это своей подписью.
3) После того как все учатники опубликовались и сверили подписи, они публикуют свои случайные числа.
4) Все проверяют, что случайные числа реально соответствуют хэшам.
5) Случайные числа участников объединяются в одну строку в соответствии с порядковыми номерами участников и подаются на вход хэш-функции или KDF (функции генерирования ключей).
6) Результат совместного хэширования используется в криптостойком генераторе псевдослучайных чисел в качестве ключа.
Дальше можно естестенно нагенерить совместных случайных чисел для чего угодно – жеребьёвки, лотереи, перестановки мест в очереди.
Проблема в том, что когда n-1 участников уже раскрыли свои данные, последний уже знает результат, а все остальные нет.
Если жеребьёвка имеет для него крайне нежелательные последствия он может придумать способ отказа от участия в процессе (комп сломался, связь прервалась, данные потерял) или саботажа,
тогда результаты будут недействительны и для всех остальных тоже.
В ряде случаев это неприемлимо, когда собирали много людей, затратили много времени, нужно получить результаты в заданный срок. Последний участник имеет как-бы право вето. Могут и несколько участников между собой сговориться на такой случай – под любым предлогом пройти в конец процесса и сделать его недействительным.
Есть какие-то более сложные протоколы на такой случай.
— Гость (26/03/2008 03:39)
Проблема в том, что когда n-1 участников уже раскрыли свои данные, последний уже знает результат, а все остальные нет.
Тогда он может использовать не случайное число а, зная числа других, подбирать своё так чтобы результат получлся как можно более выгодный ему (ибо нельзя организовать строго одновременную доставку всех полписанных случайных числе всем).
Тогда он может использовать не случайное число а, зная числа других, подбирать своё так чтобы результат получлся как можно более выгодный ему
А как он подгонит число к своему опубликованному ранее и подписанному хэшу?
Подразумевалось, что хэш-функция криптостойкая по всем параметрам, так что заранее заготовить или тем более на лету сгенерировать для одного пользователя множество текстов с одинаковым хэшем на одинаковом для всех цифровом бланке примерно такого вида маловероятно:
— Гость (26/03/2008 10:38)
А как он подгонит число к своему опубликованному ранее и подписанному хэшу?
Не в этом дело. Предположим, что все участники заведомо знают протокол по которому будет происходить жереьёвка. Допустим, для простоты генерят ключ трое: я, Владислав, и Вы. Допустим, вы с SATtva'ой сгенерили свои числа и отослали их с их хешами мне, и обменялись ими друг с другом. Сейчас я должен сгенерить число и отослать каждому из вас. Я – последний и знаю результаты всех остальных. Значит, я могу теперь сам посмотреть какой будет итоговый результат в зависимости от сгенерированного мною числа. Я подбираю то число какое даёт выгодгный мне результат, и только потом отсылаю его вам и Владиславу. если предположить что результат жеребьёвки – выбор в главу проекта, то есть орезульат – одно из чисел 1,2 или 3, то наверняка я могу подобрать такое число чтоб получить любой наперёд заданный ответ. Возможно, не понимаю протокол, но вы поясните...
— unknown (26/03/2008 10:58) Сначала надо опубликовать хэши!
Затем всё господа, ставки больше не принимаются. Все видели хэши друг друга и менять их нельзя.
после того как все участники списка опубликовали хэши и все в этом убедились, только после этого переходят к следующему шагу – раскрытию своих чисел для своих хэшей.
Для того чтобы осуществить подмену, нужно раскрыть число, не изменяя уже известный всем хэш.
Тут у вас или большая пачка заранее заготовленных хэшей с коллизиями (или даже мультиколлизиями по типу атаки Нострадамуса) должна быть или вы на основе чужих данных можете заданный результат получать, в общем ломать хэши надо.
Можно использовать блочный шифр в режиме с распространением ошибок – все шифруют строку, публикуют (как бы кладут карты на стол) и только после того как все их положили – раскрывают ключи (показывают карты путём переворачивания). Ну или на примере конвертов, как ещё объяснить. Сначала публикуют и только потом раскрывают. На ходу менять задуманное значение нельзя.
Допустим, вы с SATtva'ой сгенерили свои числа и отослали их с их хешами мне, и обменялись ими друг с другом. Сейчас я должен сгенерить число и отослать каждому из вас. Я – последний и знаю результаты всех остальных.
Так мы Вам и дадим ;-) Сначала скажем всем участникам – зарегистрируйтесь (выберите номера и подписи), чтобы вас было конечное число и левых людей не появилось, затем заканчивается дата регистрации – публикуется список:
Тогда второй этап: заполняйте бланк с числом и публикуйте хэши от него до даты первого апреля
1. Подпись (SHA512 от бланка с числом =<...> номер, дата, название жеребьёвки, служебные поля)
2. Подпись (SHA512 от бланка... =<...> номер, дата, название жеребьёвки, служебные поля)
3. Подпись (SHA512=<...> номер, дата, название жеребьёвки, служебные поля)
Все видели? Приём хэшей закончен.
Раскрываем бланки с числом:
1. SHA512 (бланк с числом) = <...> – значение хэша совпадает с предыдущим этапом и соответствует открытому бланку с числом
2. SHA512 (бланк с числом) = <...> – совпадает с предыдущим этапом и...
3. попробовал всякие коллизии и атаки, но нифига не вышло, так что
SHA512 (бланк с числом) = <...> – совпадает с предыдущим этапом и...
Все убедились?
Хэшируем числа из бланков с числом:
SHA512 (число1 || число 2 || число 3)
Используем это как ключ в ГПСЧ.
Все должны выполнять действия в отведенном для этого шаге, иначе это заметно для всех остальных и несогласные исключаются из протокола. вся проблема только в том, что последний участник может быть несогласным с результатом и аннулировать (сделать недействительным и бессысмысленным весь проделанный до него поэтапно протокол) результат своим отказом.
— SATtva (26/03/2008 14:26) А если обратиться за помощью к Дане Надю? На первом этапе мы не публикуем хэши, а передаём их Даниэлю. Он рапортует, когда получает хэши от всех зарегистрированных участников (или по истечении срока регистрации). Затем мы отсылаем Дане загаданные числа (никто из участников их не знает, только Даня, а ему всё равно, кто из нас будет признан самым большим дураком, ведь он сам на это звание не номинируется :-). Даня вычисляет итоговое число и передаёт его нам наряду со всеми хэшами и загаданными числами в целях проверки.
Единственное, что требуется здесь от Даниэля (Трента) — чтобы он не раскрыл полученное число противнику. А в саботаже протокола у него нет заинтересованности.
— unknown (26/03/2008 14:54)
Единственное, что требуется здесь от Даниэля (Трента) — чтобы он не раскрыл полученное число противнику.
Из числа неучаствующих? Это закрытая жеребъёвка в тайном клубе что-ли?
Тогда участники могут сначала договориться о случайном числе, которое не будет передаваться поверенному, но которое тоже будет участвовать в генерации ключа.
— Гость (28/03/2008 07:42)
2. spinore keyID=...
ыыы, unknown оттачивает мастерство ;-DD))
Ну я понял в общем, вы с самого начала не сделали акцент (но оговорили) на том что "сначала хеши, а только потом числа" а я при беглом чтении не заметил :)
А если обратиться за помощью к Дане Надю?
Не люблю централизованные схемы по типу УЦ, ибо здесь идёт аппеляция к авторитету и отсутствию сговора между ним и какими-либо из голосовальщиков.
— unknown (28/03/2008 08:55) Можно "жеребьеваться" в два этапа – сначала разыгрывать, кто будет последним, а затем проводить собственно жеребъёвку.
Заранее согласен, что тоже не слишком изящно и всех проблем не решает.
Есть более продвинутые протоколы для этого дела, где всё учтено, просто не могу вспомнить, где их найти.
Также как есть мысленный покер, тайное голосование, анонимные деньги и т.д. – но это уже сложные протоколы.
Для двух участников проблемы нет. Можно число сгенерить и на хэшах и на блочных шифрах и на произведении простых множителей.
Для n>2 теоретически есть проблемы сговора одних подгрупп участников против других и саботажа жеребьёвки. Но в большинстве случаев сойдёт что-то вроде этого:
1) Участники выбирают себе порядковые номера для жеребьёвки. Могут записываться в список по алфавиту, в порядке живой очереди или произвольно. Главное чтобы после объявления начала жеребьёвки нельзя было отказаться от своего номера.
Также участники публикуют данные для проверки своих сертификатов или подписей – если опасаются, что человек посредине в неподконтрольной сети или на недоверенном сервере будет создавать неверную картину для участников.
2) Каждый из участников генерирует случайное число, сохраняет его в тайне, публикует его криптостойкий хэш, вместе со своим порядковым номером, текущим временем, названием жеребьевки и заверяет всё это своей подписью.
3) После того как все учатники опубликовались и сверили подписи, они публикуют свои случайные числа.
4) Все проверяют, что случайные числа реально соответствуют хэшам.
5) Случайные числа участников объединяются в одну строку в соответствии с порядковыми номерами участников и подаются на вход хэш-функции или KDF (функции генерирования ключей).
6) Результат совместного хэширования используется в криптостойком генераторе псевдослучайных чисел в качестве ключа.
Дальше можно естестенно нагенерить совместных случайных чисел для чего угодно – жеребьёвки, лотереи, перестановки мест в очереди.
Проблема в том, что когда n-1 участников уже раскрыли свои данные, последний уже знает результат, а все остальные нет.
Если жеребьёвка имеет для него крайне нежелательные последствия он может придумать способ отказа от участия в процессе (комп сломался, связь прервалась, данные потерял) или саботажа,
тогда результаты будут недействительны и для всех остальных тоже.
В ряде случаев это неприемлимо, когда собирали много людей, затратили много времени, нужно получить результаты в заданный срок. Последний участник имеет как-бы право вето. Могут и несколько участников между собой сговориться на такой случай – под любым предлогом пройти в конец процесса и сделать его недействительным.
Есть какие-то более сложные протоколы на такой случай.
Тогда он может использовать не случайное число а, зная числа других, подбирать своё так чтобы результат получлся как можно более выгодный ему (ибо нельзя организовать строго одновременную доставку всех полписанных случайных числе всем).
А как он подгонит число к своему опубликованному ранее и подписанному хэшу?
Подразумевалось, что хэш-функция криптостойкая по всем параметрам, так что заранее заготовить или тем более на лету сгенерировать для одного пользователя множество текстов с одинаковым хэшем на одинаковом для всех цифровом бланке примерно такого вида маловероятно:
Не в этом дело. Предположим, что все участники заведомо знают протокол по которому будет происходить жереьёвка. Допустим, для простоты генерят ключ трое: я, Владислав, и Вы. Допустим, вы с SATtva'ой сгенерили свои числа и отослали их с их хешами мне, и обменялись ими друг с другом. Сейчас я должен сгенерить число и отослать каждому из вас. Я – последний и знаю результаты всех остальных. Значит, я могу теперь сам посмотреть какой будет итоговый результат в зависимости от сгенерированного мною числа. Я подбираю то число какое даёт выгодгный мне результат, и только потом отсылаю его вам и Владиславу. если предположить что результат жеребьёвки – выбор в главу проекта, то есть орезульат – одно из чисел 1,2 или 3, то наверняка я могу подобрать такое число чтоб получить любой наперёд заданный ответ. Возможно, не понимаю протокол, но вы поясните...
Сначала надо опубликовать хэши!
Затем всё господа, ставки больше не принимаются. Все видели хэши друг друга и менять их нельзя.
после того как все участники списка опубликовали хэши и все в этом убедились, только после этого переходят к следующему шагу – раскрытию своих чисел для своих хэшей.
Для того чтобы осуществить подмену, нужно раскрыть число, не изменяя уже известный всем хэш.
Тут у вас или большая пачка заранее заготовленных хэшей с коллизиями (или даже мультиколлизиями по типу атаки Нострадамуса) должна быть или вы на основе чужих данных можете заданный результат получать, в общем ломать хэши надо.
Можно использовать блочный шифр в режиме с распространением ошибок – все шифруют строку, публикуют (как бы кладут карты на стол) и только после того как все их положили – раскрывают ключи (показывают карты путём переворачивания). Ну или на примере конвертов, как ещё объяснить. Сначала публикуют и только потом раскрывают. На ходу менять задуманное значение нельзя.
Так мы Вам и дадим ;-) Сначала скажем всем участникам – зарегистрируйтесь (выберите номера и подписи), чтобы вас было конечное число и левых людей не появилось, затем заканчивается дата регистрации – публикуется список:
Жеребьёвка N0001 на звание самого большого дурака
1. SATtva keyID=...
2. spinore keyID=...
3. unknown keyID=...
Все согласны?
Тогда второй этап: заполняйте бланк с числом и публикуйте хэши от него до даты первого апреля
1. Подпись (SHA512 от бланка с числом =<...> номер, дата, название жеребьёвки, служебные поля)
2. Подпись (SHA512 от бланка... =<...> номер, дата, название жеребьёвки, служебные поля)
3. Подпись (SHA512=<...> номер, дата, название жеребьёвки, служебные поля)
Все видели? Приём хэшей закончен.
Раскрываем бланки с числом:
1. SHA512 (бланк с числом) = <...> – значение хэша совпадает с предыдущим этапом и соответствует открытому бланку с числом
2. SHA512 (бланк с числом) = <...> – совпадает с предыдущим этапом и...
3. попробовал всякие коллизии и атаки, но нифига не вышло, так что
SHA512 (бланк с числом) = <...> – совпадает с предыдущим этапом и...
Все убедились?
Хэшируем числа из бланков с числом:
SHA512 (число1 || число 2 || число 3)
Используем это как ключ в ГПСЧ.
Все должны выполнять действия в отведенном для этого шаге, иначе это заметно для всех остальных и несогласные исключаются из протокола. вся проблема только в том, что последний участник может быть несогласным с результатом и аннулировать (сделать недействительным и бессысмысленным весь проделанный до него поэтапно протокол) результат своим отказом.
А если обратиться за помощью к Дане Надю? На первом этапе мы не публикуем хэши, а передаём их Даниэлю. Он рапортует, когда получает хэши от всех зарегистрированных участников (или по истечении срока регистрации). Затем мы отсылаем Дане загаданные числа (никто из участников их не знает, только Даня, а ему всё равно, кто из нас будет признан самым большим дураком, ведь он сам на это звание не номинируется :-). Даня вычисляет итоговое число и передаёт его нам наряду со всеми хэшами и загаданными числами в целях проверки.
Единственное, что требуется здесь от Даниэля (Трента) — чтобы он не раскрыл полученное число противнику. А в саботаже протокола у него нет заинтересованности.
Из числа неучаствующих? Это закрытая жеребъёвка в тайном клубе что-ли?
Тогда участники могут сначала договориться о случайном числе, которое не будет передаваться поверенному, но которое тоже будет участвовать в генерации ключа.
ыыы, unknown оттачивает мастерство ;-DD))
Ну я понял в общем, вы с самого начала не сделали акцент (но оговорили) на том что "сначала хеши, а только потом числа" а я при беглом чтении не заметил :)
Не люблю централизованные схемы по типу УЦ, ибо здесь идёт аппеляция к авторитету и отсутствию сговора между ним и какими-либо из голосовальщиков.
Можно "жеребьеваться" в два этапа – сначала разыгрывать, кто будет последним, а затем проводить собственно жеребъёвку.
Заранее согласен, что тоже не слишком изящно и всех проблем не решает.
Есть более продвинутые протоколы для этого дела, где всё учтено, просто не могу вспомнить, где их найти.
Также как есть мысленный покер, тайное голосование, анонимные деньги и т.д. – но это уже сложные протоколы.