Есть ли алгоритм для безопасного разделения сообщения на х частей, требующих по крайней мере у частей для сборки?
Есть ли алгоритм для безопасного разделения сообщения на х частей, требующих по крайней мере у частей для сборки? Очевидно, что y <= x.
Пример:
Скажите, что у меня есть секретное сообщение, которое я хочу прочитать только в случае моей смерти. Как способ обеспечить это, я даю часть сообщения десяти друзьям. Теперь я не могу гарантировать, что все мои друзья смогут объединить свои сообщения, чтобы восстановить оригинал. Итак, я строю каждую часть сообщения таким образом, чтобы требовать от всех 5 друзей объединить их части для восстановления целого. Тем не менее, владение менее чем 5 частями ничего не даст о сообщении, кроме, возможно, длины.
Мой вопрос: возможно ли это? На какие алгоритмы я могу попытаться это сделать?
Редактирование разъяснений: важной частью этого является криптографическая сила. Злоумышленник не сможет восстановить сообщение, полностью или частично с меньшим количеством деталей.
Ответы
Ответ 1
Shamir Secret Sharing и Схема Blakley - это две скважины - установленный, доказуемо безопасный способ совместного использования тайны, с тем чтобы он мог быть восстановлен только тогда, когда объединено заранее определенное количество "акций".
Ответ 2
Отметьте http://parchive.sourceforge.net/. Существует спецификация и программное обеспечение, основанное на Код Рида-Соломона, чтобы разбить архив на х частей и создать y паритетных файлов.
Например. Вы разбиваете один 5-мегабайтный архив в пяти файлах данных размером 1 мб и создаете еще пять файлов с четностью 1 бит. Вы можете восстановить исходный файл, используя любую комбинацию данных и файлов четности, например, 1 файл данных и 4 файла четности или 5 файлов контроля четности.
Возможно, вы можете применить это.
EDIT: приложение будет разбивать ваш архив на X-части и создавать файлы контроля четности (X-Y), а затем предоставлять каждой части и всем файлам четности каждому получателю. Тогда любой Y из них может объединить свои части вместе с файлами четности, которые они все разделяют, для получения желаемого результата.
Ответ 3
Я чувствую, что вместо разделения сообщения на х частей вы действительно можете зашифровать сообщение и разделить ключ среди людей.
Аналогичной проблемой в реальном мире будет голосование. Для решения этой проблемы используется шифрование El gamal с повторной рандомизацией.
- Бала
Ответ 4
То, что вы ищете, - это "Алгоритм информационного разгона" Рабина. Здесь есть хорошее объяснение и пример кода: http://bryanmills.net/archives/2007/09/information-dispersal-algorithms/
Ответ 5
Звучит как RAID 5, который представляет собой x дисков, требующих y < x для сборки раздела. алгоритм коррекции ошибок Рида-Соломона является одной из реализаций этого типа отказоустойчивости.
Ответ 6
Да, это возможно. Он называется Прямой коррекцией ошибок. См. http://en.wikipedia.org/wiki/Forward_error_correction
Ответ 7
Пример кода Рида Соломона FEC, от Луиджи Риццо и обновленного командой UDPcast, от байт до гигабайт,
http://koders.com/c/fidD435475ABA35C752BC554D7D3E04208B2896D06C.aspx?s=fec#L3
Уменьшение масштаба, подсчет в битах, от ленточных до аудиоконтроллеров,
http://koders.com/cpp/fidF6CF3C208FBFE2EF0DAAD9CBFEC777068A81595D.aspx