Для безопасного хранения множества уникальных паролей многие из нас используют менеджеры паролей. Вся их работа по сути завязана на мастер-пароле. Этот пароль защищает все остальные пароли, и, таким образом, несёт весь риск на себе. Любой, кто подберёт его или получит к нему доступ, может притвориться вами в самый неподходящий момент. Естественно, вы стараетесь сделать свой мастер-пароль максимально сложным, а затем запоминаете или где-то ещё фиксируете его.
Но вдруг что-то случится, и вы забудете или потеряете мастер-пароль? Например, вы взяли отпуск, отправились на прекрасный далекий чудо-остров и месяц не пользовались компьютером и смартфоном. И вот, после ежедневного веселья и употребления ананасов вы не можете вспомнить свой пароль. Так… «длинные ноги быстро ходят»? Нет, не то. Или там было что-то вроде «острые ложки быстро едят»? Нет, неверно. Вы явно были в ударе, когда придумывали свой мастер-пароль, но теперь это вышло вам боком.
Конечно же, вы никогда и никому не сообщали свой пароль. Ну да, это же первое правило управления паролями! Разве может быть по-другому? Оказывается, может.
Схема разделения секрета Шамира позволяет распределить данные между участниками некой группы, разделив эти данные на части, которые можно использовать только в сочетании друг с другом.
Давайте посмотрим на схему Шамира в деле, а я заодно расскажу вам сказку. Для это вам потребуется освежить некоторые познания в криптографии, в частности, об открытых ключах.
Сказка о короле и его ужасном секрете
В некотором царстве в некотором государстве жил король. У короля был ужасный секрет:
def int_from_bytes(s):
acc = 0
for b in s:
acc = acc * 256
acc += b
return acc
secret = int_from_bytes("terrible secret".encode("utf-8"))Секрет был настолько ужасным, что король не мог доверить его никому из своих детей. У него их было пятеро, но он предвидел, что впереди их ждут опасности. Король знал, что через 20 лет после его смерти детям понадобится секрет, чтобы защитить королевство. Но король не мог смириться с мыслью что в течение двух десятилетий, пока дети будут оплакивать его, им будет известен ужасный секрет.
Поэтому он использовал мощную магию, чтобы разделить секрет на пять частей. Он знал, что возможно, один или даже два сына не будут ждать 20 лет и попытаются раньше узнать его секрет. Однако он верил, что трое из них не нарушат его волю:
from mod import Mod
from os import urandomКороль хорошо разбирался в магическом искусстве конечных полей и стохастических вычислений. Как мудрый король, для разделения секрета он использовал Python.
Первым делом он выбрал большое простое число — 13-е простое Мерсенна (2 ** 521 — 1) — и приказал, чтобы его отлили из золота символами высотой 10 футов и выставили перед дворцом на всеобщее обозрение:
P = 2**521 - 1Король знал, что, если P простое число, числа по модулю P образуют алгебраическое поле: их можно складывать, умножать, вычитать и делить, если делитель не равен нулю.
Король — человек достаточно занятой, поэтому он использовал пакет арифметики из PyPI.
Он удостоверился, что его ужасный секрет (в числовом выражении) меньше чем P:
secret < P
TRUEИ вместо секрета решил использовать его сравнение по модулю P:
secret = mod.Mod(secret, P)Чтобы позволить трём сыновьям воссоздать секрет, король должен был сгенерировать ещё две части, чтобы впоследствии смешать их:
polynomial = [secret]
for i in range(2):
polynomial.append(Mod(int_from_bytes(urandom(16)), P))
len(polynomial)
3
Затем королю нужно было оценить значения многочлена в случайных точках — то есть, вычислить polynomial[0] + polynomial[1]*x + polynomial[2]*x**2…
Хотя существуют сторонние модули для оценки полиномов, они не работают с конечными полями. Поэтому король написал код оценки вручную:
def evaluate(coefficients, x):
acc = 0
power = 1
for c in coefficients:
acc += c * power
power *= x
return accЗатем король оценил полином в пяти разных точках, чтобы выдать по одному кусочку каждому сыну:
shards = {}
for i in range(5):
x = Mod(int_from_bytes(urandom(16)), P)
y = evaluate(polynomial, x)
shards[i] = (x, y)И действительно, не все его дети оказались честными и правдивыми. Двое из них, вскоре после его смерти сговорились и попытались собрать ужасный секрет из частей, которые они имели. Естественно, у них ничего не получилось. Однако, когда другие узнали об этом, они изгнали их из королевства навсегда:
del shards[2]
del shards[3]Двадцать лет спустя, как приказал король, старший брат и два младших собрались вместе, чтобы выяснить ужасный секрет своего отца. Для начала они объединили свои части:
retrieved = list(shards.values())Но всё оказалось не так просто: 40 дней и 40 ночей они бились над этой задачей. Как и король, они знали Python, но никто из них не был таким же мудрым, как он.
Наконец, решение было найдено.
Восстановление секрета можно выполнить с помощью интерполяционного многочлена Лагранжа. Для этого оценим многочлен в (0), а затем в n других точках (n — степень многочлена). Формулу многочлена можно записать в явном виде. В нуле многочлен равен 1, в остальных точках он равен 0. Так как оценка многочлена — это линейная функция, можно оценивать и интерполировать оценки на тех же точках.
from functools import reduce
from operator import mul
def retrieve_original(secrets):
x_s = [s[0] for s in secrets]
acc = Mod(0, P)
for i in range(len(secrets)):
others = list(x_s)
cur = others.pop(i)
factor = Mod(1, P)
for el in others:
factor *= el * (el - cur).inverse()
acc += factor * secrets[i][1]
return accНеудивительно, что это заняло у них 40 дней и 40 ночей — этот код достаточно сложный!
retrieved_secret = retrieve_original(retrieved)Бинго!
retrieved_secret == secret
TRUEПрелесть математической магии в том, что она даже через 20 лет продолжает работать стабильно. Дети, теперь уже взрослые и способные понять выбор своего отца, использовали ужасный секрет, чтобы защитить королевство, которое с тех пор вновь стало процветать и расширяться.
Жизнь
В наше время многие из нас также обременены страшной тайной: мастер-паролем нашего менеджера паролей. Мало кто может найти одного человека, которому можно полностью доверить свои тайны, но найти группу из пяти человек, в которой как минимум трое окажутся ответственными людьми, вполне реально.
Благодаря современной технологии с открытым исходным кодом, мы можем использовать уже существующее решение и не писать всё с нуля.
Допустим, у вас есть пять человек, которым вы доверяете (не полностью, но хотя бы немного): ваш лучший друг, супруга, ваша мама, коллега и ваш адвокат.
Для разделения вашего ключа вы можете установить и запустить программу ssss:
$ echo 'long legs travel fast' | ssss-split -t 3 -n 5
Generating shares using a (3,5) scheme with dynamic security level.
Enter the secret, at most 128 ASCII characters: Using a 168 bit security level.
1-797842b76d80771f04972feb31c66f3927e7183609
2-947925f2fbc23dc9bca950ef613da7a4e42dc1c296
3-14647bdfc4e6596e0dbb0aa6ab839b195c9d15906d
4-97c77a805cd3d3a30bff7841f3158ea841cd41a611
5-17da24ad63f7b704baed220839abb215f97d95f4f8Придумываем мастер-пароль: «длинные ноги ходят быстро». Никогда нельзя полностью доверить кому-то одному, но вы можете отправить пять фрагментов пяти доверенным лицам.
- Вы отправляете 1 своему лучшему другу.
- Вы посылаете 2 своей супруге.
- Вы отправляете 3 своей маме.
- Вы отправляете 4 своему коллеге.
- Вы отправляете 5 своему адвокату.
Теперь, скажем, вы едете на отдых. В течение месяца вы резвитесь на пляже. Пока вы резвитесь, вы не пользуетесь ни одним электронным устройством. Достаточно скоро ваш мастер-пароль будет забыт.
Предположим, что супруга и мама тоже были на отдыхе и забыли все пароли, потеряв доступ к фрагментам вашего мастер-пароля, хранящимся в их менеджере паролей.
Отлично.
Тогда вы обращаетесь к лучшему другу, и он выдаёт вам свой фрагмент: 1-797842b76d80771f04972feb31c66f3927e7183609.
Обращаетесь к коллеге: 4-97c77a805cd3d3a30bff7841f3158ea841cd41a611.
Ну и к адвокату, который берёт $150 долларов в час:
5-17da24ad63f7b704baed220839abb215f97d95f4f8.
А затем запускаете:
$ ssss-combine -t 3
Enter 3 shares separated by newlines:
Share [1/3]: 1-797842b76d80771f04972feb31c66f3927e7183609
Share [2/3]: 4-97c77a805cd3d3a30bff7841f3158ea841cd41a611
Share [3/3]: 5-17da24ad63f7b704baed220839abb215f97d95f4f8
Resulting secret: long legs travel fastВот и всё: раз-два-три, и вы в дамках. Точнее, в королях -)
Пользуйтесь на здоровье
Управление паролями — важный навык в современной онлайн-жизни. Конечно, пароли должны быть достаточно сложными. Но не останавливайтесь на этом. Вы можете использовать схему разделения секрета Шамира, чтобы сделать хранение паролей по-настоящему безопасным.
На правах рекламы
VDSina предлагает надёжные серверы с посуточной оплатой, каждый сервер подключён к интернет-каналу в 500 Мегабит и бесплатно защищён от DDoS-атак! А ещё у нас есть вечные серверы:
