Как стать автором
Обновить

Схема разделения секрета Шамира в Hashicorp Vault

Время на прочтение9 мин
Количество просмотров4.3K

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

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

1. Split()

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

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

  1. Требуется полиномиальная функция(многочлен или полином) 1 степени со случайным коэффициентом y x, но свободный член должен быть нашим байтом - 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, y равен свободному члену. В итоге 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 и высчитывают для них yпри случайном x(для каждого ключа свой xна конце). x для всех полиномов в одном ключе один.

примерная схема того, как это реализовано в hashicorp vault(1 степень полинома в качестве примера)
примерная схема того, как это реализовано в hashicorp vault(1 степень полинома в качестве примера)

Зная степень полинома, могли бы и сами составить 2 уравнения a1 + b = 44, a2 + b = 46 и найти наши коэффициенты, но если взять многочлен, например, 10 степени, все окажется сложнее, поэтому используем интерполяцию Лагранжа. Также вычислять результат полинома n степени для y мы будем через схему Горнера - тоже чуть легче чем в лоб. Разбор кода далее.

Функцию Split() можно разделить на 2 части: Валидация, подготовка и сама разбивка ключа на несколько частей.

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

func Split(secret []byte, parts, threshold int) ([][]byte, error) 

Валидация:

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

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

  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 до кол-ва ключей. Важное замечание - я видел в некоторых библиотеках на rust именно использование номера ключа в качестве x. Это дает понимание о том, каково минимальное кол-во ключей существует.

Слайсы для каждого ключа размером с ключ + 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 с концов ключей(из того же массива случайных xи вычисляем для каждого ключа его y. Один ключ это набор из одного xна конце и множества y для каждого построенного полинома для каждого байта искомого ключа.

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 степени - 2x^4 + 7x^3 - 2x^2 - 13x + 6 x умножаем на коэффициент с начала уравнения и прибавляем следующий, далее умножаем x на результат и прибавляем следующий коэффициент и т.д., т.е. x=1:

1) 1*2+7=9

2) 1*9+(-2)=7

3) 1*7+(-13)=-6

4) 1*(-6)+6=0

Наш y=0(может быть и не равен 0, с видео взял пример). Соответственно при x=0 у нас получится наш свободный член, поэтому не считая сразу его вернем.

Мы берем последний элемент(в нашем слайсе коэффициенты расположены с большего индекса к меньшему, соответствуя коэффициентам у многочлена от большей степени к меньшей) и умножаем на xприбавляя следующий коэффициент. Так проходимся по всем коэффициентам, умножая xна результат и прибавляя следующий, пока не получим наш y.

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 части:

  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для которого нужно найти yв многочлене. Нужен свободный коэффициент - исходный байт, а он получается при 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 - этоxи соответствующие имy(т.е набор точек, 0 - это xпри котором полином равен свободному члену). Подробно об полиноме Лагранжа Не пугайтесь базисного полинома, если уделить минут 15 для разбора, все окажется легче. Формула из видео:

Нужно последовательно умножить все yна так называемый базисный полином и сложить результаты.

Первый цикл - занимается умножением 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
}

Базисный полином для y это несколько перемножаемых дробей:

num - результат вычисления числителя для n дроби. Во всех дробях x минус последовательно перебираемые значения точек x, пропуская то значение x которое соответствует y(условие i==j). В нашем случае x известен, мы хотим получить результат для x=0, поэтому 0 - перебираемые значения...

denom - результат вычисления знаменателя для n дроби. Значение точки x минус последовательно итерируемые значения x, пропуская тот x который соответствует y(условие i==j).

Примерно так выглядит для значения x под индексом 1 в слайсе:(x-x[0])/(x[1]-x[0]) * (x-x[2])/(x[1]-x[2]) * (x-x[3])/(x[1]-x[3])

Пропустили  (x-x[1])/(x[1]-x[1]) по правилу, да и ноль в знаменателе получается к тому же.

Поскольку нужен результат полинома при x=0, чтобы получить свободный член, то базисный полином получается:(0-x[0])/(x[1]-x[0]) * (0-x[2])/(x[1]-x[2]) * (0-x[3])/(x[1]-x[3])

term - результат деления num на denom, т.е. результат одной дроби. К примеру (x-x[0])/(x[1]-x[0])

basis - все результаты дробей(term) базисного полинома перемножаются.

Результатом функции будет свободный коэффициент, т.е исходный байт ключа, который мы разбили. Так для каждого байта этого ключа передают набор из x, y, высчитывают полином и его значение при x=0 с помощью интерполяции Лагранжа.

Заключение

Я писал статью не для математиков или программистов, которые давно в сфере криптографии. Мне показалось, что реализация схемы разделения Шамира довольно простая для обычного программиста как я и полезна в плане безопасности. Если статья не поможет для понимая и картинки в голове, то хотя бы для карты (куда копать).

Не описал конечное поля или поле Галуа. Они довольно сложны для меня. Ограничиваться тем, что операции сложения и вычитания - это операция xor не хотел. Но кому будет интересно, в hashicorp в комментах оставили ссылку. Продублирую.

Теги:
Хабы:
Всего голосов 10: ↑10 и ↓0+10
Комментарии1

Публикации

Истории

Работа

Ближайшие события

7 – 8 ноября
Конференция byteoilgas_conf 2024
МоскваОнлайн
7 – 8 ноября
Конференция «Матемаркетинг»
МоскваОнлайн
15 – 16 ноября
IT-конференция Merge Skolkovo
Москва
22 – 24 ноября
Хакатон «AgroCode Hack Genetics'24»
Онлайн
28 ноября
Конференция «TechRec: ITHR CAMPUS»
МоскваОнлайн
25 – 26 апреля
IT-конференция Merge Tatarstan 2025
Казань