Материал: Раздел 3. Криптографические протоколы
941094 – 10403 = 930691 > 3* 10403 = 31209.
Секретное число c должно лежать в пределах (**). Пусть оно известно сотруднику, разделяющему секрет, который вычисляет значения ai (I = 1,2,3,4,5) из условий ai ≡ c mod mi и раздает фрагменты секрета пяти участникам a1 = 62, a2 = 4, a3 = 50, a4 = 50, a5 = 38.
Пусть теперь трое из 5 участников, например, А2,А3 и А4 пытаются восстановить секретный ключ c по своим фрагментам. Поскольку каждый участник знает только свое значение mi, то они вычислят:
M2’ = m3*m4 = 9999; M3’ = m2*m4 = 9898; M4’ = m2*m3 = 9702, а затем соответствующие значения Ni’: N2’= 33; N3’ = 49. N4’ = 17. После чего найдут значение y = 4*9999*33 + 50*9898* 49 + 50 * 9702* 17 = 33816668. Секретный ключ можно вычислить из сравнения:
C ≡ y mod ( m2* m3*m4)
Таким образом, C ≡ 33816668 mod (98*99*101) ≡ 500000 mod 979902.
Если взять любую другую тройку участников, например, А1,А4,А5, то они вычислят тот же секретный ключ C = 500000.
Пусть теперь двое участников, например, А2 и А5 пытаются найти секретный ключ C. Они вычисляют y = 4*103*59 + 38*98*41 = 176992 ≡ 5394 ≡ C mod 10094/ Они понимают, что истинный секретный ключ C находится из условий : C = 5394 + t* 10094, но значения t не знают. Количество значений t определяется как целая часть дроби:
Для рассматриваемого примера целая часть дроби равна 89, т.е. двум участникам потребуется перебрать 89 вариантов ключа. В реальных условиях количество вариантов можно существенно увеличить.
Пороговая схема разделение секрета, основанная на свойствах равновесных кодов [ 12 ] ( Схема предложена И.Л.Ерошем)
Как и в предыдущих случаях имеется n участников, которым раздаются
фрагменты некоторого ключа. Требуется раздать фрагменты так, чтобы, как только соберутся h участников, ключ должен быть легко найден, а если соберется меньшее число участников, ключ можно найти только путем перебора.
Пусть R(n,k) класс равновесных двоичных кодов длины n веса k, т.е.все
коды, содержащие k единиц и n – k нулей. Число таких кодов определяется формулой перестановки с повторениями (переставляется k единиц и n-k нулей, т.е
Так для n = 5 и k = 3 получаем
Выпишем в таблицу все равновесные коды длины 5 веса 3:
Таблица 1 равновесных кодов при n = 5, k = 3.
Фраг- мент |
I |
II |
III |
IV |
V |
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 |
Можно заметить, что если взять любые три столбца Таблицы и поставить их рядом, то в каждой строке полученной уменьшенной таблицы будет находиться хотя бы одна единица. Если же взять любые два столбца этой таблицы, то всегда в уменьшенной таблице будет находиться строка из всех нулей. Можно интерпретировать этот результат следующим образом. Каждому столбцу пусть соответствует один из 5 участников. А каждой строке некоторый фрагмент ключа. Тогда у любых трех участников всегда будет все фрагменты ключа, а у любых двух никогда не будет всех фрагментов ключа. Т.е эта таблица соответствует пороговой схеме разделения секрета с 5 участниками и порогом 3. Можно доказать в общем случае, что для построения пороговой схемы с n участниками при пороге h нужно построить таблицу равновесных кодов R (n, n-h+1), т.е. кодов содержащих n –h +1 единиц и h -1 ноль. Длина кода будет равна (n –h +1) + (h-1) = n. В этом случае в таблице таких равновесных кодов h любых столбцов не будут содержать нулевых строк, а любые h-1 столбца всегда будут содержать нулевую строку.
Пример.
Пусть требуется построить пороговую схему с n = 6 и h = 3. Построим таблицу равновесных кодов длины 6 веса 6-3+1 = 4.
Число таких R(6,4)
кодов равно
Таблица 2 равновесных кодов (6,4)
Фраг- мент |
I |
II |
III |
IV |
V |
V1 |
1) |
1 |
1 |
1 |
1 |
0 |
0 |
2) |
1 |
1 |
1 |
0 |
1 |
0 |
3) |
1 |
1 |
1 |
0 |
0 |
1 |
4) |
1 |
1 |
0 |
1 |
1 |
0 |
5) |
1 |
1 |
0 |
1 |
0 |
1 |
6) |
1 |
1 |
0 |
0 |
1 |
1 |
7) |
1 |
0 |
1 |
1 |
1 |
0 |
8) |
1 |
0 |
1 |
1 |
0 |
1 |
9) |
1 |
0 |
1 |
0 |
1 |
1 |
10) |
1 |
0 |
0 |
1 |
1 |
1 |
11) |
0 |
1 |
1 |
1 |
1 |
0 |
12) |
0 |
1 |
1 |
1 |
0 |
1 |
13) |
0 |
1 |
1 |
0 |
1 |
1 |
14) |
0 |
1 |
0 |
1 |
1 |
1 |
15) |
0 |
0 |
1 |
1 |
1 |
1 |
В этой таблице любые три столбца не содержат нулевой строки. А любые 2 столбца обязательно содержат нулевую строку. Следовательно, эта схема пороговая из шести участников и пороге 3.
Можно доказать в общем случае, что любая полная таблица равновесных кодов длины n веса k реализует пороговую схему с n участниками и порогом h = n – k + 1.
В таблице приведены данные некоторых пороговых схем, использующих полные таблицы равновесных кодов.
Таблица 3 общих параметров
пороговых схем.
-
Равновесный
код
R (n,k)
Число кодовых
комбинаций
Пороговая
Схема
(n, h = n-k+1)
R (3,2)
3
(3,2)
R (4.2)
6
(4,3)
R (5,2)
10
(5,4)
R (6,2)
15
(6,5)
R (4,3)
4
(4,2)
R (5,3)
10
(5,3)
R (6,3)
20
(6,4)
R (7,3)
35
(7,5)
R (8,3)
56
(8, 6)
R (5,4)
5
(5,2)
R (6,4)
15
(6,3)
R (7,4)
35
(7,4)
R (8,4)
70
(8,5)
Может показаться, что в данной схеме как и в предыдущей при приближении снизу к порогу упрощается подбор секретного ключа. Однако если воспользоваться идеей схемы (n,n), описанной выше, этот недостаток полностью устраняется. Так, например, в Таблице 1 первым 9 фрагментам сопоставим случайные значения, полученные с помощью генератора случайных чисел: a1,a2,a3,…,a9. А значение фрагмента a10 вычислим следующим образом:
a10 = C – a1-a2-…-a9 mod P, где C – секретный ключ, P – большое простое число. Тогда сложив все фрагменты ключей, получим секретный ключ C. Если же не хватает хотя бы одного фрагмента ключа, то ключ можно найти только полным перебором.