На Хабре есть несколько статей про схему разделения Шамира, я решил попробовать описать реализацию, которую встретил в Hashicorp vault. Hashicorp - компания, известная тем, что разрабатывает инструменты - terraform, consul, nomand, vault. Vault - зашифрованное хранилище с доступом по политикам и возможностью писать свои дополнения. Ключ шифрования можно разбить на несколько частей с указанием порогового кол-ва для получения исходного ключа с помощью схемы разделения ключа Шамира.
Eсть 2 основные функции - Split() и Combine(). Разбить ключ и собрать из частей исходный ключ.
1. Split()
Разбить ключ можно с помощью полиномов (Еще одно объяснение - раздел Полиномиальная интерполяция). Я кратко объясню схему ниже.
Байт можно представить в качестве числа, например, 42. Разбиваем байт, например, на 2 ключа с пороговым кол-вом в 2.
Требуется полиномиальная функция(многочлен или полином) 1 степени со случайным коэффициентом y , но свободный член должен быть нашим байтом - 2x + 42 = y.
Выбираем случайные x и находим y. 1 точка - (x=1, y=44), 2 точка - (x=2, y=46).
В итоге разбили байт на 2 ключа [1,44], [2,46]. Как получить искомый байт? В математике есть инструмент - интерполяция Лагранжа - этот инструмент позволяет получить полином по заданным точкам. Здесь можно потренироваться - https://planetcalc.ru/8692
Ввели на planetcalc.ru/8692 2 точки и получили исходный полином 2x+42=y. Свободный член найти легко, при x = 0, равен свободному члену. В итоге 2*0+42=42, получили наш байт - 42.
Суть заключается в том, что для получения полинома, нужно пороговое кол-во x и y. Для многочлена 1 степени нужно 2 точки, для 2 степени - 3. Это можно понять, нарисовав график 2x + 42=y, получится прямая, для прямой требуется не меньше 2 точек. Полином 2 степени это парабола, нужно уже 3 (через 2 можно провести большое кол-во парабол).
Т.е. для порога в 2 ключа - берем многочлен 1 степени и по алгоритму, с порогом 3 - полином 2 степени и т.д. Самих частей может быть сколько угодно(ну, как и точек), но больше и равно порогу соответственно.
В hashicorp vault проходятся по всем байтам ключа, строят для каждого свой полином с степенью - порог минус 1 и высчитывают для них при случайном (для каждого ключа свой на конце). для всех полиномов в одном ключе один.
Зная степень полинома, могли бы и сами составить 2 уравнения a1 + b = 44, a2 + b = 46 и найти наши коэффициенты, но если взять многочлен, например, 10 степени, все окажется сложнее, поэтому используем интерполяцию Лагранжа. Также вычислять результат полинома n степени для мы будем через схему Горнера - тоже чуть легче чем в лоб. Разбор кода далее.
Функцию Split() можно разделить на 2 части: Валидация, подготовка и сама разбивка ключа на несколько частей.
Сигнатура: secret - это наш ключ представленный в виде байтов, parts - общее кол-во частей, threshold - пороговое кол-во частей, возвращаемые значения - это наши ключи и ошибка.
func Split(secret []byte, parts, threshold int) ([][]byte, error)
Валидация:
Общее кол-во частей не должно быть меньше порогового.
Кол-во частей не должно быть больше 255. У нас есть только один байт, т.е. 256 комбинаций(от 0 до 255) то последующие ключи будут повторяться, т.к. при одинаковых x на конце ключей, все значения под каждым многочленом одинаковы.
Порог не должен быть меньше 2.
Порог не должен быть больше 255.
Ключ не должен быть пустым.
if parts < threshold {
return nil, fmt.Errorf("parts cannot be less than threshold")
}
if parts > 255 {
return nil, fmt.Errorf("parts cannot exceed 255")
}
if threshold < 2 {
return nil, fmt.Errorf("threshold must be at least 2")
}
if threshold > 255 {
return nil, fmt.Errorf("threshold cannot exceed 255")
}
if len(secret) == 0 {
return nil, fmt.Errorf("cannot split an empty secret")
}
Создаем слайсы для наших ключей и слайс случайных x. Ранее использовали последовательность от 0 до кол-ва ключей. Важное замечание - я видел в некоторых библиотеках на rust именно использование номера ключа в качестве . Это дает понимание о том, каково минимальное кол-во ключей существует.
Слайсы для каждого ключа размером с ключ + 1 байт для x на конце. Ставим x из случайного набора в конец слайса.
mathrand.Seed(time.Now().UnixNano())
xCoordinates := mathrand.Perm(255) // генерирование слайса точек x
out := make([][]byte, parts)
for idx := range out {
out[idx] = make([]byte, len(secret)+1) //слайсы для ключей + байт для x
out[idx][len(secret)] = uint8(xCoordinates[idx]) + 1 // заполняем x
} // на концах ключей
Вторая часть это проход по каждому байту ключа, создание полинома со степенью порог-1 для этого байта, где наш байт это свободный член.
Далее берем наши x с концов ключей(из того же массива случайных и вычисляем для каждого ключа его . Один ключ это набор из одного на конце и множества для каждого построенного полинома для каждого байта искомого ключа.
1. Строим полином для байта - передали байт и степень полинома(порог-1) в функцию makePolynomial
2. Вычисляем для каждого ключа свой байт при заданном для этого ключа x(он один для ключа) - evaluate
функция
Далее разберем makePolynomial
и
evaluate
for idx, val := range secret {
p, err := makePolynomial(val, uint8(threshold-1)) // заполняем полином
if err != nil {
return nil, fmt.Errorf("failed to generate polynomial: %w", err)
}
for i := 0; i < parts; i++ { // проходимся по каждому ключу
x := uint8(xCoordinates[i]) + 1 // берем x для каждого ключа
y := p.evaluate(x) // высчитываем y для каждого ключа
out[i][idx] = y // заполняем в каждом ключе y
}
}
makePolynomial - intercept наш байт, он же свободный член, degree - степень:
func makePolynomial(intercept, degree uint8) (polynomial, error)
Здесь все просто, степень полинома нам известна - это degree. все полиномы выглядят одинаково:
Т.е. нам нужно заполнить случайными коэффициентами у каждого x. Создаем слайс с размером degree+1, т.к. нужно сохранить наш байт(он же свободный член) и заполняем его случайнымы байтами, кроме нашего байта или свободного члена в полиноме.
func makePolynomial(intercept, degree uint8) (polynomial, error) {
p := polynomial{
coefficients: make([]byte, degree+1),
}
p.coefficients[0] = intercept // первое значение - наш байт(свобод.коэф.)
if _, err := rand.Read(p.coefficients[1:]); err != nil { // заполняем
return p, err // случайными
} // коэффициентами
return p, nil
}
evaluate - x uint8 это значение x для которого нужно найти y в этом полиноме
func (p *polynomial) evaluate(x uint8) uint8
Нам передают x и нам нужно для этого полинома посчитать значение y. В лоб при больших степенях считать сложно. Есть инструмент - схема Горнера. Подробнее о ней
Кратко: полином 4 степени - x умножаем на коэффициент с начала уравнения и прибавляем следующий, далее умножаем x на результат и прибавляем следующий коэффициент и т.д., т.е. x=1:
1) 1*2+7=9
2) 1*9+(-2)=7
3) 1*7+(-13)=-6
4) 1*(-6)+6=0
Наш (может быть и не равен 0, с видео взял пример). Соответственно при x=0 у нас получится наш свободный член, поэтому не считая сразу его вернем.
Мы берем последний элемент(в нашем слайсе коэффициенты расположены с большего индекса к меньшему, соответствуя коэффициентам у многочлена от большей степени к меньшей) и умножаем на прибавляя следующий коэффициент. Так проходимся по всем коэффициентам, умножая на результат и прибавляя следующий, пока не получим наш .
func (p *polynomial) evaluate(x uint8) uint8 {
if x == 0 { // при x=0 результат равен свободному члену
return p.coefficients[0]
}
degree := len(p.coefficients) - 1 // берем индекс последнего элемента
out := p.coefficients[degree] // сам последний элемент по индексу
for i := degree - 1; i >= 0; i-- {
coeff := p.coefficients[i]
out = add(mult(out, x), coeff) // прибавляем следующий коэффициент
} // умножая x на результат
return out
}
Итак, мы нашли для каждого байта из искомого ключа свои наборы точек в виде байтов других ключей. Теперь можно перейти к функции, которая получает исходные байты используя интерполяцию Лагранжа.
ВАЖНАЯ ЧАСТЬ: функции add(a, b uint8) mult(a, b uint8) div(a, b uint8) используются для сложения вычитания умножения и деления, add() - для сложения и вычитания. Мы не должны выходить за пределы байта, т.е. 256 значений, поэтому все операции происходят в так называемом конечном поле.Это довольно долгая история, поэтому я решил остановиться на том, что у нас есть эти функции. Сами hashicorp предоставляют ссылку, если интересно устройство этих операций.
2.Combine()
Сигнатура: parts - это ключи для объединения, возвращаемые значения - это исходный ключ и ошибка.
func Combine(parts [][]byte) ([]byte, error)
Combine() также можно разделить на 2 части:
Валидаия и подготовка дынных
Нахождения исходного ключа
Валидация:
Кол-во частей не должно быть меньше двух
Первый ключ в списке не должен быть меньше 2 байт(y,x - минимально 2 точки нужны) и все ключи должны иметь равную длину(сравнивают все с первым)
if len(parts) < 2 { // 1 пункт - кол-во частей не должно быть меньше 2
return nil, fmt.Errorf("less than two parts cannot be used to reconstruct the secret")
}
firstPartLen := len(parts[0]) // берем 1 ключ
if firstPartLen < 2 { // кол-во байтов в нем не должно быть меньше 2
return nil, fmt.Errorf("parts must be at least two bytes")
}
for i := 1; i < len(parts); i++ { // все ключи должны быть одного размера
if len(parts[i]) != firstPartLen {
return nil, fmt.Errorf("all parts must be the same length")
}
}
secret - наш исходный ключ, поскольку у нас x на конце каждого ключа, иходный будет на один байт меньше. Далее строится список из точек(для x один слайс для y второй слайс). ключи(например):
[23,7,2,45...5]
[32,2,3,21...2]
[18,9,32,1...15]
Берем с концов x - 5, 2, 15 и заполняем для x слайс. (проверям чтобы x не совпадали иначе ключи тоже будут одинаковы)
secret := make([]byte, firstPartLen-1) // слайс для иходного ключа
x_samples := make([]uint8, len(parts)) // слайс для x точек
y_samples := make([]uint8, len(parts)) // слайс для y точек
checkMap := map[byte]bool{} // мапа для проверки на дубли
for i, part := range parts {
samp := part[firstPartLen-1] // samp - x с конца слайса
if exists := checkMap[samp]; exists { // проверяем чтобы x на дубли
return nil, fmt.Errorf("duplicate part detected")
}
checkMap[samp] = true
x_samples[i] = samp
}
Нахождения исходного ключа. Нам нужно восстановить каждый байт исходного ключа, набор из x есть. Для первого байта заполняем y. Ключи(например):
[23,7,2,45...5]
[32,2,3,21...2]
[18,9,32,1...15]
Для первого исходного байта нам нужен первый столбец, получаются точки - [5,23],[2,32],[15,18], Для второго - второй столбец [5,7],[2,2],[15,9] и т.д. Далее мы прокидываем в фукнцию interpolatePolynomial наш список из x и y. 3 - аргумент - это точка для интерполяции, т.е. для которого нужно найти в многочлене. Нужен свободный коэффициент - исходный байт, а он получается при x = 0. Т.е могли бы получить многочлен и далее при x=0 наш байт(он же свободный коэффициент). Но зачем, если с помощью интерполяции Лагранжа это можно сделать сразу.
for idx := range secret {
for i, part := range parts { // выбираем нужный y с каждого ключа
y_samples[i] = part[idx] // для нашего байта, idx - номер столбика
}
val := interpolatePolynomial(x_samples, y_samples, 0)
secret[idx] = val
}
Разберем interpolatePolynomial - x_samples, y_samples - этои соответствующие им(т.е набор точек, 0 - это при котором полином равен свободному члену). Подробно об полиноме Лагранжа Не пугайтесь базисного полинома, если уделить минут 15 для разбора, все окажется легче. Формула из видео:
Нужно последовательно умножить все на так называемый базисный полином и сложить результаты.
Первый цикл - занимается умножением y на базисный полином и сложением - т.е. отражение формулы внизу: group - умножение y на базисный полином, result - результат сложения. Второй(вложенный) - высчитывет базисный полином - это формулы сверху. Напомню: add(a, b uint8) - это сложение и вычитание в конечном поле, они одинаковы, div(a, b uint8) - деление, mult(a, b uint8) - умножение.
func interpolatePolynomial(x_samples, y_samples []uint8, x uint8) uint8 {
limit := len(x_samples)
var result, basis uint8
for i := 0; i < limit; i++ {
// б.п. - базисный полином
basis = 1
for j := 0; j < limit; j++ { // вычисление б.п. для y
if i == j { // пропускаем тот x, который соответствует y для
continue // которого вычисляем б.п.
}
num := add(x, x_samples[j]) // результат числителя в дроби в б.п.
denom := add(x_samples[i], x_samples[j]) // результат знаменателя
term := div(num, denom) // результат деления одной дроби
basis = mult(basis, term) // перемножение дробей и получение б.п.
}
group := mult(y_samples[i], basis) // умножение y на б.п.
result = add(result, group) // сложение результатов умножения y на б.п.
}
return result
}
Базисный полином для это несколько перемножаемых дробей:
num - результат вычисления числителя для n дроби. Во всех дробях x минус последовательно перебираемые значения точек x, пропуская то значение x которое соответствует y(условие i==j). В нашем случае x известен, мы хотим получить результат для x=0, поэтому 0 - перебираемые значения...
denom - результат вычисления знаменателя для n дроби. Значение точки x минус последовательно итерируемые значения x, пропуская тот x который соответствует y(условие i==j).
Примерно так выглядит для значения x под индексом 1 в слайсе:
Пропустили по правилу, да и ноль в знаменателе получается к тому же.
Поскольку нужен результат полинома при x=0, чтобы получить свободный член, то базисный полином получается:
term - результат деления num на denom, т.е. результат одной дроби. К примеру
basis - все результаты дробей(term) базисного полинома перемножаются.
Результатом функции будет свободный коэффициент, т.е исходный байт ключа, который мы разбили. Так для каждого байта этого ключа передают набор из , высчитывают полином и его значение при x=0 с помощью интерполяции Лагранжа.
Заключение
Я писал статью не для математиков или программистов, которые давно в сфере криптографии. Мне показалось, что реализация схемы разделения Шамира довольно простая для обычного программиста как я и полезна в плане безопасности. Если статья не поможет для понимая и картинки в голове, то хотя бы для карты (куда копать).
Не описал конечное поля или поле Галуа. Они довольно сложны для меня. Ограничиваться тем, что операции сложения и вычитания - это операция xor не хотел. Но кому будет интересно, в hashicorp в комментах оставили ссылку. Продублирую.