Раскрытие информации на основе консенсуса

Question

Описание проблемы

Меня интересует решение следующей проблемы:

Есть некоторая секретная информация, которая группа из n людей хотела бы заблокировать до некоторого минимального числа 1 <= <em>m <= <em>n из них соглашается выпустить его. Например, скажем, имена всех участники группы.

Как мы можем зашифровать эту информацию и распределить n «ключи» к нему так что информация остается конфиденциальной навсегда, если в какой-то момент, по крайней мере, m отправить свои ключи, чтобы разблокировать информацию?

1024 * Ограничения *

Крайне важно, чтобы для любого k <<em> m (даже m-1 ) была крайне низкая вероятность успешного извлечения информации с помощью только ключи k . Не менее важно, что для любого k > = m вероятность успеха должна быть чрезвычайно высокой.

И оптимально (но не обязательно), я бы хотел решение, которое имеет эти свойства:

• является функционально масштабируемым (решает проблему для любого m , * n *).
• скорость / память масштабируемость (для шифрования / дешифрования требуется разумное количество времени).

---

Изначально я думал, что хорошее решение может заключаться в простом шифровании информации и раздаче (частного) ключа по частям, но я не могу придумать хороший способ разделения ключа.

В частности, проблема, похоже, усугубляется, когда m и n становятся действительно большими, поскольку грань между наличием и отсутствием> = m желающий член группы становится все тоньше и тоньше (так сказать).

Если вы знаете решение, толчок в правильном направлении предпочтительнее полного ответа .

Answer 1

Для разделения ключей, посмотрите вверх Секретный обмен Шамира .Это классический метод (опубликован в 1979 г.).

Answer 2

Вы можете использовать разделение на основе XOR, вот как это работает:

Вы предоставляете необходимое количество частей - n, а секретный ключ - K. Чтобы сгенерировать n частей вашего ключа, вам нужно создать (n - 1) случайные числа: R1, R2, R3,. , , , Rn − 1. Для этого вы можете использовать генератор чисел SecureRandom, который предотвратит дублирование. Когда вы используете функцию XOR для этих частей Rn-1 и ваш ключ - K:
Rn = R1 ⊕ R2 ⊕ R3 ⊕. , , ⊕ Rn − 1 ⊕ K

Теперь у вас есть n фигур: R1, R2, R3,…, Rn-1, Rn, и вы можете уничтожить K. Эти фрагменты могут быть распространены в вашем коде или отправлены пользователям.

Чтобы собрать ключ, мы используем операцию XOR на наших Rn-компонентах:
K = R1 ⊕ R2 ⊕ R3 ⊕. , , ⊕ Rn − 1 ⊕ Rn

При использовании функции XOR (⊕) каждый фрагмент по своей сути важен для восстановления ключа; если какие-либо биты в любом из фрагментов изменены, ключ не подлежит восстановлению.

Для получения дополнительной информации вы можете взглянуть на утилиту Android, которую я написал для этой цели:
Проект GitHub: https://github.com/aivarsda/Secret-Key-Split-Util

Также вы можете попробовать демонстрационное приложение Secret Key Splitter, которое использует эту Утилиту:
GooglePlay: https://play.google.com/store/apps/details?id=com.aivarsda.keysplitter