Криптография — это метод защиты информации и коммуникаций с помощью кодов, так что только тот человек, для которого предназначена информация, может ее понять и обработать. Таким образом предотвращается несанкционированный доступ к информации. Приставка «крипта» означает «скрытый», а суффикс «графи» означает «письмо».
В этой статье обсуждается тип криптографической техники, алгоритм разделения секрета Шамира.
Алгоритм обмена секретами Шамира: Обмен секретами Шамира — это алгоритм в криптографии, созданный Ади Шамиром. Основная цель этого алгоритма — разделить секрет, который необходимо зашифровать, на различные уникальные части. И криптографические алгоритмы активно используются в облачном шифровании данных, такое шифрование активно используют и в торговом программном обеспечении (для маркировки, ЕГАИСа, продуктовых и непродуктовых магазинах и сетей и прочее) и для облачного хранения данных.
- Скажем, S — это секрет, который мы хотим закодировать.
- Он разделен на N частей: S1, S2, S3,…., Sn.
- После его деления пользователь выбирает число K , чтобы расшифровать части и найти исходный секрет.
- Он выбран таким образом, что если мы знаем менее K частей, то мы не сможем найти секрет S (т.е. секрет S не может быть восстановлен с помощью (K — 1) частей или меньше.
- Если мы знаем K или более частей из S1, S2, S3,…., Sn, то мы можем легко вычислить / восстановить наш секретный код S. Это условно называется пороговой схемой (K, N).
Подход: Основная идея алгоритма обмена секретами Шамира лежит в основе концепции, согласно которой для заданных K точек мы можем найти полиномиальное уравнение со степенью (K — 1).
Пример:
- Для данных двух точек (x1, y1) и (x2, y2) мы можем найти линейный многочлен ax + by = c .
- Аналогично для данных трех точек мы можем найти квадратичный многочлен ax 2 + bx + cy = d .
Итак, идея состоит в том, чтобы построить многочлен со степенью (K — 1) так, чтобы постоянный член был секретным кодом, а остальные числа были случайными, и этот постоянный член можно было бы найти, используя любые K точек из N точек, сгенерированных из этот многочлен с помощью базисного многочлена Легранжа.
Например: пусть секретный код S = 65, N = 4, K = 2.
- Первоначально, чтобы зашифровать секретный код, мы строим многочлен степени (K — 1).
- Поэтому пусть многочлен y = a + bx . Здесь постоянная часть «а» — это наш секретный код.
- Пусть b — любое случайное число, скажем, b = 15.
- Следовательно, для этого многочлена y = 65 + 15x мы генерируем из него N = 4 точки.
- Пусть эти 4 точки будут (1, 80), (2, 95), (3, 110), (4, 125). Ясно, что мы можем сгенерировать исходный полином из любых двух из этих 4 точек, и в полученном полиноме постоянный член a является требуемым секретным кодом.
Чтобы восстановить заданный многочлен обратно, используется базисный многочлен Лагранжа .
Основная концепция полинома Лагранжа состоит в том, чтобы сначала сформировать тождества Лагранжа, и суммирование этих тождеств дает нам требуемую функцию, которую нам нужно найти по заданным точкам. Следующие уравнения показывают, как их вычислить.
