Теоретические сведения. Исследование схем разделения секрета

Лабораторная работа 5

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

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

Теоретические сведения

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

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

n

x º S a_iM_iN_i

i = 1

Кроме того, это решение единственное, т.е. любое другое решение 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), ( 1 )

и max(k-1) < c < min(k), (2)

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

Неравенство (1) примет вид: 941094 – 10403 = 930691 > 3*10403 = 31209.

Секретное число с должно лежать в пределах (2). Пусть оно известно некоторому сотруднику, разделяющему секрет, который вычислил значения 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 определяется как целая часть дроби: