Глава
18.
Криптографическая
защита
вые
(|A|, |A|)
-
СРС
только для минимальных разрешенных множеств
А
, т
е для
А
∈
Г
min
, где
Г
min
— совокупность минимальных
(
относительно включения
) мно
- жеств из
Г
Тем не менее
, для пороговой
(n, n/2)
-
СРС
размер
“
проекции
” (
изме
- ренный
, например
, в
битах
) будет в
C
n
n/2
2n/ 2πn
раз больше размера секрета
(
это наихудший случай для рассматриваемой конструкции
).
С
другой стороны
, как мы убедимся чуть позже
, любая пороговая структура доступа может быть реализована идеально
, т
е при совпадающих размерах
“
проекции
” и
секрета
Поэтому естественно возникает вопрос о
том
, каково максимально возможное превышение размера
“
проекции
” над размером секрета для наихудшей структу
- ры доступа при наилучшей реализации
Формально
,
R(n) = max R( Г)
, где
max
берется по всем структурам доступа
Г
на
n
участниках
, а
R(Г) = min max
log |S
i
|
log |S
0
|
, где
min
берется по всем
СРС
, реализующим данную структуру доступа
Г
, а
max
— по
і = 1, ..., n
Приведенная конструкция показывает
, что
R(n)
≤
C
n
n/2n
С
дру
- гой стороны
,
R(n)
≥
n/log n
Такой огромный
“
зазор
” между верхней и
нижней оценкой дает достаточный простор для исследований
(
предполагается
, что
R(n)
зависит от
n
экспоненциально
).
Линейное
разделение
секрета
Начнем с
предложенной
Шамиром элегантной схемы разделения секрета для пороговых структур доступа
Пусть
К = GF(q)
— конечное поле из
q
элементов
(
например
,
q = p
— простое число и
К = Z
p
) и
q > n
Сопоставим участникам
n
различных ненулевых элементов поля
{a
1
, …, a
n
}
и положим
a
0
= 0
При распре
- делении секрета
s
0
дилер
СРС
генерирует
k–1
независимых равномерно рас
- пределенных на
GF(q)
случайных величин
f
j
(j = 1, …, k–1)
и посылает
і
- му учаснику
(і = 1, ..., n)
“
его
” значение
s
i
= f(a
i
)
многочлена
f(x) = f
0
+ f
1
x + …
+ f
k-1
x
k-1
, где
f
0
= s
0
Поскольку любой многочлен степени
k-1
однозначно вос
- станавливается по его значениям в
произвольных
k
точках
(
например
, по интер
- поляционной формуле
Лагранжа
), то любые
k
участников вместе могут восста
- новить многочлен
f(x)
и
, следовательно
, найти значение секрета как
s
0
= f(0)
По этой же причине для любых
k–1
участников
, любых полученных ими значений проекций
s
i
и любого значения секрета
s
0
существует ровно один
“
соответст
- вующий
” им многочлен
, т
е такой
, что
s
i
= f(a
i
)
и
s
0
= f(0)
Следовательно
, эта схема является совершенной в
соответствии с
определением
2. “
Линейность
” данной схемы становится ясна
, если записать
“
разделение секрета
” в
векторно
- матричном виде
:
s = fH,
(18.3) где
s = (s
0
, …, s
n
), f = (f
0
, …, f
k–1
), k × (n+1)
— матрица
H = (h
ij
) = (a
i
j-1
)
и
h
00
= 1
Заметим
, что любые
k
столбцов этой матрицы линейно независимы
, а
макси
- мально возможное число столбцов матрицы
H
равно
q
, чтобы добиться обе
- щанного значения
q+1
надо добавить столбец
, соответствующий точке
“
беско
- нечность
”.
Математикаразделениясекрета365Возьмем в (18.3) в качестве Hпроизвольную r × (n + 1)- матрицу с элемента - ми из поля KПолучаемую СРС , будем называть одномернойлинейнойСРСОна является совершенной комбинаторной СРС со структурой доступа Г, со - стоящей из множеств Атаких , что вектор h0представим в виде линейной комби - нации векторов {hj: j ∈ A}, где hj — это j- ый столбец матрицы HСтроками мат - рицы V, соответствующей данной СРС , являются , как видно из (18.3), линейные комбинации строк матрицы HПерепишем (18.3) в следующем виде sj = (f, hj) для j = 0, 1, …, n, где (f, hj) — скалярное произведение векторов fи hjЕсли А ∈ Г, т е если h0= Σλjhj, то s0 = (f, h0) = ( ) f, Σλjhj = Σλj(f, hj) = Σλjsjи , следовательно , значение секрета однозначно находится по его “ проекциям ”. Рассмотрим теперь случай , когда вектор h0не представим в виде линейной ком - бинации векторов {hj: j ∈ A}Нам нужно показать , что в этом случае для любых заданных значений координат из множества Ачисло строк матрицы Vс данным значением любой координаты не зависит от этого значения В этом не трудно убедится , рассмотрев (18.3) как систему линейных уравнений относительно не - известных fiи воспользовавшись тем , что система совместна тогда и только то - гда , когда ранг матрицы коэффициентов равен рангу расширенной матрицы , а число решений у совместных систем одинаково и равно числу решений одно - родной системы Указание. Рассмотрите две системы : c “ нулевым ” уравнением и без него ( т е со свободным членом ). Так как вектор h0не представим в виде линейной комби - нации векторов {hj: j ∈ A}, то ранг матрицы коэффициентов второй системы на 1 больше ранга матрицы коэффициентов первой системы Отсюда немедленно следует , что если первая система совместна , то совместна и вторая при любом s0Эта конструкция подводит нас к определению общей линейной СРС Пусть секрет и его “ проекции ” представляются как конечномерные векторы si = (si1, …, simi)и генерируются по формуле si = fHi, где Hi — некоторые r × mi- матрицы Со - поставим каждой матрице Hiлинейное пространство Liее столбцов ( т е со - стоящее из всех линейных комбинаций вектор- столбцов матрицы Hi). Неслож - ные рассуждения , аналогичные приведенным выше для одномерного случая ( все mi = 1), показывают , что данная конструкция дает совершенную СРС тогда и только тогда , когда семейство линейных подпространств {L0, …, Ln}конечно - мерного векторного пространства Krудовлетворяет упомянутому выше свойству “ все или ничего ”. При этом множество Аявляется разрешенным {La: a ∈ A}со - держит подпространство L0целиком С другой стороны , множество Аявляется неразрешенным ( А ∉ Г), если и только если линейная оболочка подпространств {La: a ∈ A}пересекается с подпространством L0только по вектору 0Отметим , 366Глава 18. Криптографическаязащитачто если бы для некоторого Апересечение L0и линейной оболочки {La: a ∈ A}было нетривиальным , то участники Ане могли бы восстановить секрет одно - значно , но получали бы некоторую информацию о нем , т е схема не была бы совершенной Пример 18.3. Рассмотрим следующую структуру доступа для случая четырех участников , задаваемую Гmin = {{1,2}, {2,3}, {3,4}}Она известна как первый по - строенный пример структуры доступа , для которой не существует идеальной реализации Более того , было доказано , что для любой ее совершенной реали - зации R(Г) ≥ 3/2С другой стороны , непосредственная проверка показывает , что выбор матриц H0, H1, ..., H4, приведенных на рис . 18.2, дает совершенную ли - нейную СРС с R = 3/2, реализующую эту структуру , которая , следовательно , яв - ляется и оптимальной ( наиболее экономной ) СРС Рис. 18.2. Матрицы , реализующие совершенную линейную СРС ИдеальноеразделениесекретаиматроидыНачнем с определения идеальных СРС Для этого вернемся к комбинаторно - му определению совершенной СРС Следующее определение совершеннойСРС является даже более общим , чем вероятностное определение 1, поскольку условие (18.2) заменено в нем на более слабое Для произвольного множества В ⊆ {0, 1, …, n}обозначим через VB M × |B|- матрицу , полученную из матрицы Vудалением столбцов , номера которых не принадлежат множеству ВПусть ||W||обозначает число различных строк в мат - рице WОпределение 18.3 Матрица Vзадает БД - совершенную СРС , реализующую структуру доступа Г, если ||VA∪ 0|| = ||VA|| × ||V0||δГ (А), (18.4) где δГ (А) = 0, если А ∈ Г, и δГ (А) = 1 в противном случае Это определение отличается от определений 1 и 2 тем , что на неразрешен - ные множества Анакладываются довольно слабое условие , а именно , если множество строк Vс данными значениями координат из множества Анепусто , то все возможные значения секрета встречаются в нулевой координате этих строк ( без требований “ одинаково часто ” как в комбинаторном определении 2 Математикаразделениясекрета367или же “ с априорной вероятностью ” как в вероятностном определении 1). Легко видеть , что матрица любой совершенной вероятностной СРС задает БД - совершенную СРС , но обратное неверно Для произвольной комбинаторной СРС , задаваемой матрицей V, определим на множествах А ⊆ {0, 1, …, n}функцию h(A) = logq ||VA||, где q = |S0|Легко проверить , что max{h(A), h(B)} ≤ h(A ∪ B) ≤ h(A) + h(B)для любых множеств Аи В, а условие (184) может быть переписано в виде hq(VA∪ 0) = hq(VA) + δГ (А) hq(V0) ЛеммаДля любой БД - совершенной СРС если А ∉ Ги {A ∪ i} ∈ Г, то h(i) ≥ h(0). ДоказательствоПо условиям леммы h(A ∪ 0) = h(A) + h(0) и h(A ∪ i ∪ 0) = h(A ∪ і)Следовательно , h(A) + h(i) ≥ h (A ∪ і) = h (A ∪ і ∪ 0) ≥ h(A ∪ 0) = h(A) + h(0) Так мы предполагаем , что все точки і ∈ {1, …, n}существенные , т е для лю - бого інайдется подмножество Атакое , что А ∉ Ги {A ∪ і} ∈ Г, то из леммы вы - текает Следствие. Для любой БД - совершенной СРС |Si| ≥ |S0|для всех і = 1, ..., nСледствие означает , как отмечалось выше , что для совершенных СРС “ раз - мер ” проекции не может быть меньше “ размера ” секрета Поэтому БД - совершенная СРС называется идеальной , если |Si| = |S0|для всех і = 1, ..., nЗамечаниеНеравенство |Si| ≥ |S0|справедливо и для совершенных вероятно - стных СРС , поскольку их матрицы задают БД - совершенные СРС Естественный вопрос состоит в том , для каких структур доступа Г сущест - вуют реализующие их идеальные ( вероятностные или комбинаторные ) СРС Как уже отмечалось , наилучший на сегодняшний день ответ использует словоматроидНапомним определение матроидов и некоторые их основные свой - ства Матроидомназывается конечное множество Хи семейство Iего подмно - жеств , называемых независимыми ( остальные множества называются зависи - мыми ), если выполнены следующие свойства : ∅ ∈ I; (18.5.1) Если A ∈ I и B ⊂ A, то B ∈ I; (18.5.2) Если A, B ∈ I и |A| = |B| + 1, то существует a ∈ A\B такое, что a ∪ B ∈ I. (18.5.3) 368Глава 18. КриптографическаязащитаПример 18.4. Множество Х — это множество векторов в некотором линейном векторном пространстве , а независимые подмножества — это линейно незави - симые подмножества векторов Собственно с этого примера и началась теория матроидов , вначале как по - пытка дать аксиоматическое определение линейной независимости векторов че - рез “ внутренние свойства ”, т е не апеллируя к понятию вектора К счастью , по - пытка не удалась , так как нашлись матроиды , не представимые как линейные ( т е как системы векторов ), а сама теория матроидов разрослась далеко за пре - делы линейной алгебры Пример 18.5. (матроидВамоса). Рассмотрим следующее множество : Х = {1, 2, 3, 4, 5, 6, 7, 8}и положим a = {1, 2}, b = {3, 4}, c = {5, 6}и d = {7, 8}Матро - ид Вамоса определяется как матроид , в котором множества a ∪ c, a ∪ d, b ∪ c, b ∪ d, c ∪ d, а также все подмножества из пяти или более элементов являются зависимыми Известно , что этот матроид не является линейным Матроид также можно определить через так называемую ранговую функцию r(A)матроида , определяемую как максимальная мощность независимого подмножества В ⊆ АОчевидно , что независимые множества ( и только они ) задаются условием r(A) = |A|Ранговая функция матроида обладает свойствами r(A) ∈ Z; r(∅ ) = 0; (18.6.1) r(A) ≤ r(A ∪ b) ≤ r(A) + 1; (18.6.2) Если r(A ∪ b) = r (A ∪ c) = r(A), то r (A ∪ b ∪ c) = r(A). (18.6.3) Обратно , пусть некоторая функция r(A)обладает свойствами (18.6). Назовем независимыми те множестваА, для которых r(A) = |A|Тогда эти множества за - дают матроид , а функция rявляется его ранговой функцией Возможно также определить матроид через минимальные зависимые множества , называемые циклами Матроид называется связным, если для любых двух его точек сущест - вует содержащий их цикл Теперь мы можем сформулировать основной результат ТеоремаДля любой БД - совершенной идеальной СРС , реализующей струк - туру доступа Г, независимые множества , определяемые условием log|S0| ||VA|| = |A|, задают связный матроид на множестве {0, 1,…, n}Все циклы этого матроида , содержащие точку 0, имеют вид 0 ∪ А, где А ∈ ГminДоказательство теоремы приведено в соответствующей литературе и выхо - дит за рамки данной книги Главным в доказательстве теоремы является “ про - верка ” целочисленности функции h(A)В самом деле , h(A)очевидно обладает остальными свойствами (6) и , следовательно , при условии целочисленности яв - ляется ранговой функцией и задает матроид Отметим , что из второй части утверждения теоремы следует , что разным идеальным СРС , реализующим данную структуру доступа Г, всегда соответст - вует один и тот же матроид , поскольку матроид однозначно определяется всеми Секретностьиимитостойкость369циклами , проходящими через фиксированную точку Тем самым , каждой иде - альной реализуемой структуре доступа соответствует однозначно определенный матроид В связи с теоремой возникает несколько естественных вопросов Прежде все - го , не порождают ли идеальные СРС все матроиды ? Нет , например , матроид Вамоса не может быть получен как матроид идеальнойСРС С другой стороны линейные матроиды есть ни что иное , как рассмотренные идеальные одномер - ные линейные СРС В связи с этим возникает вопрос о существовании структуры доступа Г, которую невозможно реализовать в виде идеальной одномерной ли - нейной СРС , но можно в виде идеальной многомерной линейной СРС Такие примеры имеются , и , значит , мы можем говорить о многомерных линейных мат - роидах как классе матроидов более общем , чем линейные Итак , идеальных СРС больше , чем линейных матроидов , но меньше , чем всех матроидов Уточнить , насколько больше , представляется довольно слож - ной задачей В частности , существует ли идеально реализуемая структура дос - тупа Г, которую невозможно реализовать как идеальную линейную многомерную СРС ? СекретностьиимитостойкостьКриптографические преобразования обеспечивают решение двух главных проблем ЗИ : проблемысекретности ( лишение противника возможности из - влечь информацию из канала связи ) и проблемыимитостойкости ( лишение противника возможности ввести ложную информацию в канал связи или изме - нить сообщение так , чтобы изменился его смысл ). В случае телефонной связи главной является проблемаимитостойкости, поскольку вызванная сторона не может часто определить , кто звонит Подслу - шивание , требующее подключения к проводам , технически более сложно и юри - дически более опасно , чем вызов корреспондента и выдача себя за кого - то дру - гого В случае радиосвязи ситуация прямо противоположная Перехват здесь является пассивным и сопряжен с незначительной юридической опасностью , то - гда как введение информации связано с риском обнаружения незаконного пере - датчика и юридического преследования ПроблемасекретностиПроблемы секретности и имитостойкости между собой тесно связаны, поэто - му методы решения одной из них часто применимы для решения другой Из двух названных проблем проблема секретности обычно рассматривается первой , как более старая и шире известная Рассмотрим схему прохождения потока инфор - мации в криптографической системе , обеспечивающей секретность ( рис . 18.3). |
Скачать 4.86 Mb.