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