Протокол фиата шамира python

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Shamir’s Secret Sharing Scheme implemented in Python

rodrigo-castellon/shamir

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

This short Python program implements Shamir’s Secret Sharing Scheme (SSS).

First, make sure that NumPy is installed.

To run with the default configuration (n=50, k=20, K=1337, p=2**127-1), run

Run with the help command to find how to configure

Run with the -v flag for verbose mode, which prints out all of the keys:

Running in verbose mode with 5 individuals and 3 necessary to unlock the secret key:

$ python shamir.py -v -n 10 -k 3 

#### Shamir's Secret Sharing Scheme #### p=170141183460469231731687303715884105727 K=1337 (the key) ######################################### Distributed public keys: [159295934112048856104943720797459882023 3897499456721215129662485829517641142 106359069303894237915449798553830341915 96436624917505388534534964576808954655 82558760913992608939958392144080638617] Distributed secret keys: [47118056962547522296047871559126950388 60504585901425677614619790584313779760 104434369299853073791090724686225969560 161648570216194248714687996555632176004 49688957303007089389437824881931699753] submitted: public keys: [159295934112048856104943720797459882023 96436624917505388534534964576808954655 82558760913992608939958392144080638617] private keys: [47118056962547522296047871559126950388 161648570216194248714687996555632176004 49688957303007089389437824881931699753] recovered K=1337 

High-level Overview of SSS

Suppose you have nuclear launch codes that should stay locked with a key, K, unless k of n generals decide to obtain the launch codes and use them. SSS allows a dealer to distribute public and private keys (one pair per general) such that when k private keys and their corresponding public keys are known, one can recover the key K.

Algorithm Step-by-Step Explanation

The algorithm proceeds by the following steps.

1. Randomly generate n x_i’s (public keys).
2. Randomly generate k a_i’s (except for a_0, which is designated to be THE secret key a_0 = K), which correspond to the coefficients in

1. Compute f(x_i) = y_i for all x_i’s and designate those as secret keys to be distributed for every individual.

Part 2: Recover the secret key K

1. Obtain any combination k of the n y_i’s and their corresponding x_i’s.
2. Define the Lagrange Polynomial basis for such a data set:

This implementation uses a finite field of cardinality p = 2**127 — 1 by default (can be changed with an argument). See more explanation about how SSS works here: https://en.wikipedia.org/wiki/Shamir’s_Secret_Sharing

About

Shamir’s Secret Sharing Scheme implemented in Python

Источник

Спасите пароль: сказочная реализация схемы разделения секрета Шамира на Python

Этот алгоритм, использующий язык Python и Схему разделения секрета Шамира, защищает ваш мастер-пароль от хакеров и вашей собственной забывчивости.

Для безопасного хранения множества уникальных паролей многие из нас используют менеджеры паролей. Вся их работа по сути завязана на мастер-пароле. Этот пароль защищает все остальные пароли, и, таким образом, несёт весь риск на себе. Любой, кто подберёт его или получит к нему доступ, может притвориться вами в самый неподходящий момент. Естественно, вы стараетесь сделать свой мастер-пароль максимально сложным, а затем запоминаете или где-то ещё фиксируете его.

Но вдруг что-то случится, и вы забудете или потеряете мастер-пароль? Например, вы взяли отпуск, отправились на прекрасный далекий чудо-остров и месяц не пользовались компьютером и смартфоном. И вот, после ежедневного веселья и употребления ананасов вы не можете вспомнить свой пароль. Так… «длинные ноги быстро ходят»? Нет, не то. Или там было что-то вроде «острые ложки быстро едят»? Нет, неверно. Вы явно были в ударе, когда придумывали свой мастер-пароль, но теперь это вышло вам боком.

Конечно же, вы никогда и никому не сообщали свой пароль. Ну да, это же первое правило управления паролями! Разве может быть по-другому? Оказывается, может.

Схема разделения секрета Шамира позволяет распределить данные между участниками некой группы, разделив эти данные на части, которые можно использовать только в сочетании друг с другом.

Давайте посмотрим на схему Шамира в деле, а я заодно расскажу вам сказку. Для это вам потребуется освежить некоторые познания в криптографии, в частности, об открытых ключах.

Сказка о короле и его ужасном секрете

В некотором царстве в некотором государстве жил король. У короля был ужасный секрет:

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 простое число, числа по модулю P образуют алгебраическое поле: их можно складывать, умножать, вычитать и делить, если делитель не равен нулю.

Король — человек достаточно занятой, поэтому он использовал пакет арифметики из PyPI.

Он удостоверился, что его ужасный секрет (в числовом выражении) меньше чем P:

И вместо секрета решил использовать его сравнение по модулю 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)

И действительно, не все его дети оказались честными и правдивыми. Двое из них, вскоре после его смерти сговорились и попытались собрать ужасный секрет из частей, которые они имели. Естественно, у них ничего не получилось. Однако, когда другие узнали об этом, они изгнали их из королевства навсегда:

Двадцать лет спустя, как приказал король, старший брат и два младших собрались вместе, чтобы выяснить ужасный секрет своего отца. Для начала они объединили свои части:

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-атак! А ещё у нас есть вечные серверы:

Источник