На Хабре есть несколько статей про схему разделения Шамира, я решил попробовать описать реализацию, которую встретил в Hashicorp vault. Hashicorp - компания, известная тем, что разрабатывает инструменты - terraform, consul, nomand, vault. Vault - зашифрованное хранилище с доступом по политикам и возможностью писать свои дополнения. Ключ шифрования можно разбить на несколько частей с указанием порогового кол-ва для получения исходного ключа с помощью схемы разделения ключа Шамира.

• Реализация

• Файл с комментариями на русском

Eсть 2 основные функции - Split() и Combine(). Разбить ключ и собрать из частей исходный ключ.

1. Split()

Разбить ключ можно с помощью полиномов (Еще одно объяснение - раздел Полиномиальная интерполяция). Я кратко объясню схему ниже.

Байт можно представить в качестве числа, например, 42. Разбиваем байт, например, на 2 ключа с пороговым кол-вом в 2.

1. Требуется полиномиальная функция(многочлен или полином) 1 степени со случайным коэффициентом y , но свободный член должен быть нашим байтом - 2x + 42 = y.

2. Выбираем случайные x и находим y. 1 точка - (x=1, y=44), 2 точка - (x=2, y=46).

3. В итоге разбили байт на 2 ключа [1,44], [2,46]. Как получить искомый байт? В математике есть инструмент - интерполяция Лагранжа - этот инструмент позволяет получить полином по заданным точкам. Здесь можно потренироваться - https://planetcalc.ru/8692

4. Ввели на planetcalc.ru/8692 2 точки и получили исходный полином 2x+42=y. Свободный член найти легко, при x = 0, равен свободному члену. В итоге 2*0+42=42, получили наш байт - 42.

5. Суть заключается в том, что для получения полинома, нужно пороговое кол-во x и y. Для многочлена 1 степени нужно 2 точки, для 2 степени - 3. Это можно понять, нарисовав график 2x + 42=y, получится прямая, для прямой требуется не меньше 2 точек. Полином 2 степени это парабола, нужно уже 3 (через 2 можно провести большое кол-во парабол).

6. Т.е. для порога в 2 ключа - берем многочлен 1 степени и по алгоритму, с порогом 3 - полином 2 степени и т.д. Самих частей может быть сколько угодно(ну, как и точек), но больше и равно порогу соответственно.

7. В 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) 

Валидация:

1. Общее кол-во частей не должно быть меньше порогового.

2. Кол-во частей не должно быть больше 255. У нас есть только один байт, т.е. 256 комбинаций(от 0 до 255) то последующие ключи будут повторяться, т.к. при одинаковых x на конце ключей, все значения под каждым многочленом одинаковы.

3. Порог не должен быть меньше 2.

4. Порог не должен быть больше 255.

5. Ключ не должен быть пустым.

	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 до кол-ва ключей. https://github.com/hashicorp/vault/commit/b4602fc2443dc3de451cd9aeac7c4d79390adbd8

Слайсы для каждого ключа размером с ключ + 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. В лоб при больших степенях считать сложно. Есть инструмент - схема Горнера. Подробнее о ней - https://youtu.be/H9teIpb62iI?t=180

Кратко: полином 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 предоставляют эту ссылку - http://www.samiam.org/galois.html если интересно устройство этих операций.

2.Combine()

Сигнатура: parts - это ключи для объединения, возвращаемые значения - это исходный ключ и ошибка.

func Combine(parts [][]byte) ([]byte, error) 

Combine() также можно разделить на 2 части:

1. Валидаия и подготовка дынных

2. Нахождения исходного ключа

Валидация:

1. Кол-во частей не должно быть меньше двух

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 - это при котором полином равен свободному члену). Подробно об полиноме Лагранжа - https://www.youtube.com/watch?v=nj2RBZ6xFeY Не пугайтесь базисного полинома, если уделить минут 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 в комментах оставили ссылку. Продублирую.