Материал: metod_cripto_n

Лабораторная работа n3 Исследование схем разделения секрета

Цель работы: Ознакомить студентов с различными схемами разделения секретных ключей, которые используются в криптографических системах для предотвращения их несанкционированного использования.

Теоретические пояснения

Рассмотрим случай, когда руководитель банка или какой-либо другой организации не полностью доверяет своим сотрудникам и хочет подстраховаться при использовании секретного ключа. Он может разделить весь секретный ключ (двоичная или десятичная последовательность символов) на отдельные фрагменты и эти фрагменты раздать нескольким сотрудникам так, чтобы при общем числе сотрудников n полный ключ мог быть ими составлен, если соберутся вместе не менее h сотрудников.

1. Наиболее просто поставленная задача решается при h = n, т.е. когда ключ раздается n сотрудникам и требуется наличие всех n фрагментов ключа, чтобы собрать полностью секретный ключ S [1]. Выберем некоторое простое число p, и пусть секретный ключ представляется в виде набора (s₁,s₂,s₃,…,s_k) , где все s_i являются элементами поля Галуа – GF(p) [4]. Разделим секретный ключ на n фрагментов следующим образом. Будем генерировать произвольные случайные числа:

(a₁₁, a₁₂, a₁₃,…., a_1k) - фрагмент секретного ключа 1-го сотрудника,

(a₂₁, a₂₂, a₂₃,…., a_2k) - фрагмент секретного ключа 2-го сотрудника,

………..

(a_n-11,a_n-12,a_n-13,…, a_n-1k) - фрагмент секретного ключа n-1 –го сотрудника.

А последнему n-му сотруднику вычислим элементы его фрагмента секретного ключа по следующему правилу:

a_n1 = (s₁ - a₁₁ - a₂₁ - a₃₁ - … - a_n1) mod p.

a_n2 = (s₂ - a₁₂ - a₂₂ - a₃₂ - … - a_n2) mod p.

…………………………………………

a_nk = (s_k - a_1k - a_2k - a_3k - … - a_nk) mod p.

В этом случае только при сложении всех фрагментов ключа по модулю p получим полный секретный ключ.

Пример. Пусть p = 29 и секретный ключ имеет вид: (26,13,21,8,0,18). Требуется разделить его на 5 фрагментов для раздачи 5 сотрудникам. Для первых четырех из них генератор случайных чисел по модулю 29 пусть выработал фрагменты:

(26, 0, 13, 11, 23, 25)

(2, 7, 15, 12, 27, 6)

(1, 3 , 24, 6, 0, 16)

(12, 2, 7, 0, 7, 0)

Для последнего, пятого сотрудника вычисленный фрагмент имеет вид:

(14, 1, 20, 8, 1, 0).

Легко проверяется, что сложение всех фрагментов (каждый элемент складывается по модулю 29) дает полный секретный ключ (26,13,21,8,0,18).

Следует заметить, что сложность подбора секретного ключа в рассмотренном случае зависит только от значения модуля p и числа элементов k и практически не зависит от количества сотрудников n.

2. Рассмотрим случай, когда h  n. Имеется несколько вариантов решения такой пороговой задачи. Приведем алгоритм, описанный в [2]. Он основан на модульной арифметике и китайской теореме об остатках.

Имеется n участников A₁,A₂,A₃,…,A_n. Пусть m_i, i = 1,2,…n, целые числа, большие 1, такие, что (m_i,m_j) = 1 при i j. В данном случае запись (m_i,m_j) = 1 означает, что числа m_i и m_j взаимно простые, т.е. не имеют общих множителей. Например, к взаимно простым числам относятся все простые числа [4].

Обозначим за М – произведение всех чисел m_i, т.е. М = m₁m₂m₃…,m_i,…m_t. Обозначим также M_i – произведение всех m_j (j = 1,2,…, i-1,i+1,…,n), кроме m_i, т.е.M_i = M/m_i. Вычислим значения N_i из условия: M_iN_i  1 mod m_i. Так как (M_i,m_i) = 1, то решение всегда существует, и все N_i будут найдены.

Если имеется n сравнений вида: x  a_i mod m_i, i = 1,2,…,n, a_i – целые, то общее решение этих сравнений имеет вид:

Кроме того, это решение единственное, т.е. любое другое решение y удовлетворяет сравнению: y  x mod M.

Пусть теперь k фиксированный порог, 1  k  n. Обозначим через min(k) – наименьшее из k произведений m_i, а max(k-1) – наибольшее из k-1 произведений m_i. Если выполнены условия:

min(k) – max(k-1)  3 max(k-1) (2)

и max(k-1)  c  min(k), (3)

то множество {a₁,a₂,…,a_t}, где a_i  c mod m_i, образует (k,n) пороговую схему для c [2]. Это означает, что если c – некоторый секретный ключ, а a_i – фрагменты ключа, розданные n участникам, то любые k из участников смогут восстановить значение c по его фрагментам, а любые k-1 участников сделать это не смогут (без перебора вариантов). При этом, чем больше в (2) разность, тем труднее k-1 участникам подобрать секретный ключ по своим фрагментам.

Пример. Пусть n = 5 и m₁ = 97; m₂ = 98, m₃ = 99, m₄ = 101, m₅ = 103. Возьмем k = 3 и вычислим min(3) = (97*98*99) = 941094; max(2) = (101*103) = 10403. Неравенство (2) примет вид: 941094 – 10403 = 930691  3*10403 = 31209.

Секретное число с должно лежать в пределах (3). Пусть оно известно некоторому сотруднику, разделяющему секрет, который вычислил значения a_i (i = 1,2,…,5) из условий a_ic mod m_i и раздал фрагменты секрета пяти участникам: a₁ = 62, a₂ = 4, a₃ = 50, a₄ = 50, a₅ = 38. Пусть теперь трое из пяти участников, например, A₂,A₃ и A₄ пытаются восстановить секретный ключ c по своим фрагментам. Поскольку каждый участник знает только свое значение m_i, то они вычисляют: M₂’= m₃ m₄ = 9999; M₃’= m₂ m₄ = 9898; M₄’= m₂ m₃ = 9702, а затем соответствующие значения N_i: N₂ = 33, N₃ = 49, N₄ = 17. После чего находят значение x = 4*9999*33 + 50*9898*49 + 50*9702*17 = 33816668. Секретный ключ вычисляется из сравнения: c  x mod (m₂ m₃ m₄), т.е. c  33816668 mod (98*99*101)  500000 mod 979902.

Если взять любую другую тройку клиентов, например, A₁,A₄,A₅, то они вычислят тот же секретный ключ с = 500000.

Пусть теперь двое клиентов, например, A₂ и A₅ пытаются найти секретный ключ с. Они вычисляют значения y = 4*103*59 + 38*98*41 = 176992  5394  с mod 10094. Они понимают, что истинный секретный ключ находится из условий: 5394 + i 10094, но значения i не знают. Количество значений i определяется как целая часть дроби:

Для рассматриваемого примера целая часть дроби равна 89, т.е. двум участникам потребуется перебрать 89 вариантов ключа. В реальных условиях количество вариантов может быть сделано существенно большим.

3. Рассмотрим еще один пример разделения секретного ключа, описанный в [4]. Пусть к приему сообщения допущено n сотрудников, из которых не все могут оказаться на месте во время приема. Фрагменты ключа распределяются между сотрудниками по определенному правилу, причем так, что ни один сотрудник не имеет полного набора фрагментов ключа. Сообщение может быть расшифровано, если соберутся h или более сотрудников (т.е. h сотрудников должны иметь полный набор фрагментов), при этом 1 h  n. В дальнейшем слова “фрагмент ключа” будем заменять на слово “фрагмент, имея в виду, что это фрагмент общего секретного ключа.

Требуется по заданным параметрам n и h определить число фрагментов k и дать правило распределения этих фрагментов между сотрудниками.

Сначала рассмотрим случай, когда n – нечетное число и h = (n+1)/2.

1. Мажоритарный принцип.

Замечание 1. Известно, что n - разрядными равновесными кодами веса q называют двоичные n- разрядные комбинации, содержащие ровно q единиц и n - q нулей. Полным равновесным кодом длины n веса q будем называть набор всех кодов, отвечающих данным условиям и обозначать R(n,q).

Замечание 2. P( a,b ) - обозначают количество перестановок из a объектов 1-го вида и b объектов второго, это число равно:

(4)

Для R(n,q) число комбинаций равно P(n-q,q).

Рассмотрим поставленную задачу в случае, когда n - нечетное число, а порог

h = (n+1)/2.

Теорема 1: Если n - нечетное число и порог h = (n+1)/2, тогда количество фрагментов ключа k равно числу n разрядных двоичных кодов веса h, а именно

,

а правило распределения ключей между сотрудниками соответствует столбцам полного равновесного кода R(n,q).

Доказательство необходимости и достаточности приведено ниже.

Пример 1. Пусть n = 5 и h = 3. Построим таблицу равновесных 5 -и разрядных кодов веса 3 , т.е. R (5,3)

Таблица 1

1 2 3 4 5

----------------------

1) 1 1 1 0 0

2) 1 1 0 1 0

3) 1 1 0 0 1

4) 1 0 1 1 0

5) 1 0 1 0 1

6) 1 0 0 1 1

7) 0 1 1 1 0

8) 0 1 1 0 1

9) 0 1 0 1 1

10) 0 0 1 1 1

В таблице цифрами 1,2,3,4,5 обозначены члены приемной команды, а 1),2),3),... обозначены номера фрагментов. Возьмем для примера 3-го члена команды. Он имеет фрагменты с номерами 1),4),5),7),8),10). Любая тройка членов приемной команды имеет полный набор фрагментов и может составить полный секретный ключ S. При этом никакие пары членов приемной команды не имеют полного набора. Количество фрагментов в данном примере равно 10. Единицы в вертикальном коде соответствуют номерам фрагментов, которые имеет данный член команды.

2.Принцип с произвольным порогом

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

Теорема 2: Если максимальное число людей, имеющих ключи равно n (здесь уже n - любое целое положительное число) и требуется обеспечить решение при пороге h, то количество фрагментов равно числу кодовых комбинаций в R(n, n-h+1)

.

Пример 2. Пусть n = 6, h = 2. Построим равновесный двоичный код R(6,5)

Таблица 2.

1 2 3 4 5 6

-------------------

1) 1 1 1 1 1 0

2) 1 1 1 1 0 1

3) 1 1 1 0 1 1

4) 1 1 0 1 1 1

5) 1 0 1 1 1 1

6) 0 1 1 1 1 1

Дизъюнкция любых двух столбцов дает код, содержащий все единицы.

Доказательство необходимости и достаточности приведено ниже.

Теорема 2 является обобщением теоремы 1. Действительно, если положить в теореме 2 значение h = (n +1)/2, то получим R(n,(n +1)/2).

Обе теоремы являются конструктивными, так как дают правило распределения ключей между членами принимающей команды.

Доказательство. Возьмем i -й столбец из R(n,h) и обозначим его r(i). Его вес будем определять как число единиц в коде и обозначать r(i) Определим операцию дизъюнкции столбцов r(i) и r(j) в виде результирующего вектора той же размерности, все компоненты которого получены путем дизъюнкции соответствующих компонентов векторов r(i) и r(j).Аналогично введем операцию дизъюнкции "v" над s векторами: r(i₁) v r(i₂) v r(i₃) v...v r(i_s).

Возьмем полную таблицу кодов длины n веса q, которую мы обозначали R(n,q). Из этой таблицы выберем произвольный столбец с номером i, т.е. r(i). Определим его вес. Легко видеть, что при любом i. .

Вес кода дизъюнкции любых s столбцов с номерами i₁,i₂,i₃,...i_s при 1 < s < n-q+1

(5)

Если s = n-q+1, то сумма (5) точно равна количеству кодов в R(n,q),

Действительно, последний член в (5) равен 1.

Если число членов s ряда (5) меньше n-q+1, то сумма (5) меньше значения (4), что доказывает теорему, так как никакие члены команды, если их меньше, чем n-q+1 не имеют полного набора ключей. В частном случае, если q = (n+1)/2, имеем, что при s = (n+1)/2 в совокупности имеется полный набор ключей для расшифровки сообщения.

Приведенный алгоритм распределения фрагментов общего секретного ключа достаточно прост и позволяет найти распределения секрета при любых значениях n и любых h (1  h  n ). Это является достоинством приведенного алгоритма. Этот алгоритм имеет существенный недостаток, если общий ключ просто разделять на отдельные участки: чем больше соберется сотрудников (хотя их может быть и меньше h), тем легче им будет подобрать значения недостающих фрагментов. Например, если общий ключ представлял собой 20 разрядное десятичное число и его разделить на фрагменты по 2 разряда, то когда соберутся любые 2 сотрудника, им достаточно будет подобрать значения двух недостающих разрядов, т.е. проверить всего 10² вариантов.

Секретность приведенного алгоритма можно существенно усилить, если формировать фрагменты также как формировались фрагменты в первом примере (при h = n).

Пример 3. Пусть секретный ключ S (S₁,S₂,S₃) имеет вид S = (23,8,11), т.е. представляет собой совокупность трех элементов, где каждый элемент – произвольное положительное целое меньшее некоторого простого числа p.

Девять из десяти фрагментов получим с помощью генератора случайных чисел, при этом совершенно необязательно, чтобы элементы находились в пределах 0 – p-1. Например,

1. ( 5,32,18)

2. (0,19,3)

3. (36,7,16)

4. (9,11,35)

5. (16,1,28)

6. (25,39,46)

7. (3,0,21)

8. (15,14,2)

9. (35,20,20)

А десятый фрагмент (a₁₀,b₁₀,c₁₀) получим по следующему правилу:

a₁₀ = (S₁ – a₁ – a₂ - … - a₉₎ mod p

b₁₀ = (S₂ – b₁ – b₂ - … - b₉₎ mod p

c₁₀ = (S₃ – c₁ – c₂ - … - с₉₎ mod p

Для рассматриваемого примера получаем: