Литвиненко А.В. Методы и средства защиты информации

Подождите немного. Документ загружается.

Классификация криптографических методов 341

Под шифрованием в данном случае понимается такой вид криптографического за-

крытия, при котором преобразованию подвергается каждый символ защищаемого сооб-

щения. Все известные способы шифрования разбиты на пять групп: подстановка (заме-

на), перестановка, аналитическое преобразование, гаммирование и комбинированное

шифрование. Каждый из этих способов может иметь несколько разновидностей.

Под кодированием понимается такой вид

криптографического закрытия, когда неко-

торые элементы защищаемых данных (не обязательно отдельные символы) заменяются

заранее выбранными кодами (цифровыми, буквенными, буквенно-цифровыми сочета-

ниями и т.д.). Этот метод имеет две разновидности: смысловое и символьное кодирова-

ние. При смысловом кодировании кодируемые элементы имеют вполне определенный

смысл (слова, предложения, группы предложений). При символьном

кодировании коди-

руется каждый символ защищаемого текста. Символьное кодирование по существу сов-

падает с подстановочным шифрованием.

К отдельным видам криптографии относятся методы рассечения-разнесения и сжа-

тия данных. Рассечение-разнесение заключается в том, что массив защищаемых данных

делится (рассекается) на такие элементы, каждый из которых в отдельности не позволяет

раскрыть содержание

защищаемой информации. Выделенные таким образом элементы

данных разносятся по разным зонам памяти или располагаются на разных носителях.

Сжатие данных представляет собой замену часто встречающихся одинаковых строк

данных или последовательностей одинаковых символов некоторыми заранее выбранны-

ми символами.

342 Глава 18. Криптографическая защита

Рис. 18.1. Классификация криптографических методов

Требования к криптографическим методам защиты информации

Раскрытие зашифрованных текстов (в первую очередь нахождение ключа) осуществ-

ляется при помощи методов криптоанализа. Основными методами криптоанализа явля-

ются:

• статистические, при которых зная статистические свойства открытого текста пы-

таются исследовать статистические закономерности шифротекста и на основании об-

наруженных закономерностей раскрыть текст;

• метод вероятных слов, в котором при сопоставлении некоторой небольшой части

шифротекста с известным фрагментом открытого текста пытаются найти ключ и с

его помощью расшифровать весь текст. Требуемый фрагмент открытого текста мож-

но найти с помощью статистических методов или просто угадать, исходя из предпо-

лагаемого содержания или структуры открытого текста.

Классификация криптографических методов 343

Поскольку криптографические методы ЗИ применяются давно, то уже сформулиро-

ваны основные требования к ним.

1. Метод должен быть надежным, т.е. восстановление открытого текста при владении

только шифротекстом, но не ключом должно быть практически невыполнимой зада-

чей

2. Из-за трудности запоминания объем ключа не должен быть большим.

3. Из-за трудностей, связанных со сложными преобразованиями, процессы шифрования

должны быть простыми.

4. Из-за возможности появления ошибок передачи дешифрование шифротекста, содер-

жащего отдельные ошибки, не должно привести к бесконечному увеличению ошибок

в полученном предполагаемом открытом тексте.

5. Из-за трудностей передачи объем шифротекста не должен быть значительно больше

открытого текста.

Перечисленные требования были разработаны для традиционной криптографии.

При современном развитии техники необходимость удовлетворения перечисленным

требованиям претерпевает существенные изменения.

В связи с развитием технологии, позволяющей с большой плотностью записать и

длительное время надежно хранить большие объемы информации, условие небольшого

объема ключа может быть ослаблено (по существу это условие, как и все остальные,

приобретает новый смысл, соответствующий достигнутому уровню техники). В связи с

развитием микроэлектроники появляется возможность разработки дешевых устройств,

осуществляющих быстро и точно сравнительно сложные преобразования информации. С

другой стороны, возможность увеличения скорости передачи отстает от возможности

увеличения скорости

обработки информации. Это, несомненно, позволяет ослабить тре-

бование п. 3 без ущерба для практически достигаемой скорости передачи. В настоящее

время связное оборудование является высоконадежным, а методы обнаружения и ис-

правления ошибок — хорошо развитыми. К тому же, обычно используемые в компью-

терных сетях протоколы сеансов связи предусматривают передачу любого текста даже

при наличии

сбоев во время передачи. Поэтому требование п. 4 в значительной мере по-

теряло свою актуальность. В отдельных случаях, если каналы связи не перегружены,

может быть ослаблено и требование п. 5.

Таким образом, не затронутым осталось требование п. 1, при рассмотрении которого

следует учесть два обстоятельства.

Во-первых, в автоматизированных системах (АС) циркулируют большие

объемы ин-

формации, а наличие большого объема шифротекста облегчает задачу криптоанализа.

Во-вторых, для решения задачи криптоанализа можно использовать ЭВМ. Это позво-

ляет в новых условиях требовать значительного увеличения надежности. Другим важ-

ным отрицательным фактором применения криптографии в АС является то, что часто

используются языки с весьма ограниченным запасом слов и

строгим синтаксисом (языки

программирования).

344 Глава 18. Криптографическая защита

В связи с новыми специфическими применениями криптографических методов могут

быть выдвинуты также другие требования. Так, например, второй важной областью

применения криптографических методов ЗИ являются системы управления базами дан-

ных (СУБД). В этом случае к криптографическим методам ЗИ предъявляются следую-

щие дополнительные требования.

1. Из-за невозможности чтения и возобновления записей с середины файла, шифрова-

ние и дешифрование каждой записи должны производиться независимо от других за-

писей.

2. Для создания больших удобств обработки и во избежание излишней перегрузки сис-

темы вспомогательными преобразованиями необходимо все операции с файлами

проводить с данными в зашифрованном виде.

Специфика СУБД оказывает влияние на надежность защиты по следующим причи-

нам:

• данные в СУБД продолжительное время находятся в зашифрованном виде. Это за-

трудняет или даже делает невозможной частую смену ключей, и в связи с этим ЗИ

становится менее надежной;

• ключи могут не передаваться по разным адресам, а храниться все в одном месте. Это

повышает надежность системы из-за уменьшения возможности овладения ключами

посторонними лицами.

В файловых системах вероятность появления ошибки гораздо меньше, чем в каналах

связи, поэтому требование п. 4 для файловых систем не имеет большого практического

значения.

Появление быстродействующих ЭВМ

способствует возникновению так называемой

вычислительной криптографии, тесно связанной с вычислительной техникой.

Математика разделения секрета

Рассмотрим следующую, в наше время вполне реальную ситуацию. Два совладельца

драгоценности хотят положить ее на хранение в сейф. Сейф современный, с цифровым

замком на 16 цифр. Так как совладельцы не доверяют друг другу, то они хотят закрыть

сейф таким образом, чтобы они могли открыть его вместе, но никак не порознь. Для это

го они приглашают третье лицо, называемое дилером, которому они оба доверяют (на-

пример, потому что оно не получит больше доступ к сейфу). Дилер случайно выбирает

16 цифр в качестве “ключа”, чтобы закрыть сейф, и затем сообщает первому совладель-

цу втайне от второго первые 8 цифр “ключа”, а второму совладельцу втайне от первого

— последние 8 цифр “ключа”. Такой способ представляется с точки здравого смысла оп-

тимальным, ведь каждый из совладельцев, получив “полключа”, не сможет им восполь-

зоваться без второй половины, а что может быть лучше?! Недостатком данного примера

является то, что любой из совладельцев, оставшись наедине с сейфом, может за пару

минут найти недостающие

“полключа” с помощью несложного устройства, предназна-

ченного для перебора ключей и работающего на тактовой частоте 1 МГц. Кажется, что

единственный выход — в увеличении размера “ключа”, скажем, вдвое. Но есть другой

Математика разделения секрета 345

математический выход, опровергающий (в данном случае — к счастью) соображения

здравого смысла. А именно, дилер независимо выбирает две случайные последователь-

ности по 16 цифр в каждой, сообщает каждому из совладельцев втайне от другого “его”

последовательность, а в качестве “ключа”, чтобы закрыть сейф, использует последова-

тельность, полученную сложением по модулю 10 соответствующих цифр двух выбран

ных последовательностей. Довольно очевидно, что для каждого из совладельцев все 10

возможных “ключей” одинаково вероятны и остается только перебирать их, что потре-

бует в среднем около полутора лет для устройства перебора ключей, оборудованного

процессором с частотой 100 МГц.

И с математической, и с практической точки зрения неинтересно останавливаться на

случае двух участников и следует рассмотреть общую ситуацию. Неформально говоря,

схема, разделяющая секрет (

СРС) позволяет “распределить” секрет между n участни-

ками таким образом, чтобы заранее заданные разрешенные множества участников могли

однозначно восстановить секрет (совокупность этих множеств называется структурой

доступа), а неразрешенные — не получали никакой дополнительной к имеющейся ап-

риорной информации о возможном значении секрета. СРС с последним свойством назы-

ваются совершенными.

История СРС начинается с 1979 года, когда эта проблема

была поставлена и во мно-

гом решена Блейкли и Шамиром для случая пороговых

(n, k)-СРС (т.е. разрешенными

множествами являются любые множества из

k или более элементов). Особый интерес

вызвали так называемые идеальные СРС, т.е.такие, где объем информации, предостав-

ляемой участнику, не больше объема секрета. Оказалось, что любой такой СРС соответ-

ствует матроид и, следовательно, не для любой структуры доступа возможно идеальное

разделение секрета. С другой стороны, было показано, что для любого

набора разрешен-

ных множеств можно построить совершенную СРС, однако известные построения весь-

ма неэкономны. Рассмотрим некоторые алгебро-геометрические и комбинаторные зада-

чи, возникающие при математическом анализе СРС.

Будем говорить, что семейство подпространств

, …, L

} конечномерного век-

торного пространства

L над полем K удовлетворяет свойству “все или ничего”, если

для любого множества

A ⊂ {1, …, n} линейная оболочка подпространств {L

: a ∈ A}

либо содержит подпространство

целиком, либо пересекается с ним только по век-

тору

0. В подразделе “Линейное разделение секрета” мы увидим, что такое семейство

задает “линейную” СРС, у которой множество

A ⊂ {1, …, n} является разрешенным,

если и только если линейная оболочка подпространств

: a ∈ A} содержит подпро-

странство

целиком. В связи с этим понятием возникает ряд вопросов. Например,

если поле

K конечно (|K| = q) и все подпространства {L

, …, L

} одномерны, то ка-

ково максимально возможное число участников

n для линейных пороговых (n, k)-СРС

(

k > 1)? Иначе говоря, каково максимально возможное число векторов {h

, …, h

} та-

ких, что любые

k векторов, содержащие вектор h

, линейно независимы, а любые k +

векторов, содержащие вектор h

, линейно зависимы. Оказывается, что это свойство

эквивалентно следующему, на первый взгляд более сильному, свойству: любые

k век-

торов линейно независимы, а любые

k + 1 — линейно зависимы. Такие системы век-

346 Глава 18. Криптографическая защита

торов изучались в геометрии как N-множества (N = n + 1) в конечной проективной

геометрии

PG(k–1, q), в комбинаторике — как ортогональные таблицы силы k и ин-

декса

λ = 1, в теории кодирования — как проверочные матрицы МДР кодов. В подраз-

деле “Линейное разделение секрета” мы приведем известную конструкцию таких

множеств с

N = q + 1. Существует довольно старая гипотеза о том, что это и есть мак-

симально возможное

N, за исключением двух случаев: случая q < k, когда N = k + 1,

и случая

q = 2m, k = 3 или k = q – 1, когда N = q + 2.

Разделение секрета для произвольных структур доступа

Начнем с формальной математической модели. Имеется n+1 множество S

, S

, …, S

и (совместное) распределение вероятностей

P на их декартовом произведении S = S

…* S

. Соответствующие случайные величины обозначаются через S

. Имеется также

некоторое множество

Г подмножеств множества {1, …, n}, называемое структурой дос-

тупа.

Определение 18.1

Пара (P,S) называется совершенной вероятностной СРС, реализующей структуру

доступа

Г, если

P(S

= c

| S

= c

, i ∈ A) ∈ {0, 1} для A ∈ Г, (18.1)

P(S0 = c0 | Si = ci, i ∈ A) = P(S0 = c0) для A ∉ Г (18.2)

Это определение можно истолковать следующим образом. Имеется множество S

всех возможных секретов, из которого секрет

выбирается с вероятностью p(s

), и

имеется СРС, которая “распределяет” секрет

между n участниками, посылая “про-

екции”

, …, s

секрета с вероятностью P

, …, s

). Отметим, что і-ый учасник

получает свою “проекцию”

∈ S

и не имеет информации о значениях других “проек-

ций”, однако знает все множества

, а также оба распределения вероятностей p(s

) и

, …, s

). Эти два распределения могут быть эквивалентны заменене на одно: P(s

, …, s

) = p(

, …, s

), что и было сделано выше. Цель СРС, как указывалось во

введении, состоит в том, чтобы:

• участники из разрешенного множества A (т. е. A ∈ Г) вместе могли бы однозначно

восстановить значение секрета — это отражено в свойстве (18.1);

• участники, образующие неразрешенное множество А (А ∉ Г), не могли бы получить

дополнительную информацию об

, т.е., чтобы вероятность того, что значение сек-

рета

= c

, не зависела от значений “проекций” S

при і ∈ А — это свойство (18.2).

Замечание о терминологии. В англоязычной литературе для обозначения “порции”

информации, посылаемой участнику СРС, были введены термины share (А. Шамир)

и shadow (Г. Блейкли). Первый термин оказался наиболее популярным, но неадек-

ватная (во всех смыслах) замена в данной работе акции на проекцию может быть

несколько оправдана следующим примером.

Математика разделения секрета 347

Пример 18.1. Множество S

всех возможных секретов состоит из 0, 1 и 2, “представ-

ленных”, соответственно: шаром; кубом, ребра которого параллельны осям координат;

цилиндром, образующие которого параллельны оси

Z. При этом диаметры шара и осно-

вания цилиндра, и длины ребра куба и образующей цилиндра, равны. Первый участник

получает в качестве своей “доли” секрета его проекцию на плоскость

XY, а второй — на

плоскость

XZ. Ясно, что вместе они однозначно восстановят секрет, а порознь — нет.

Однако эта СРС не является совершенной, так как любой из участников получает ин-

формацию о секрете, оставляя только два значения секрета как возможные при данной

проекции (например, если проекция — квадрат, то шар невозможен).

Еще одно замечание. Элемент (участник)

x ∈ {1, …, n} называется несущественным

(относительно

Г), если для любого неразрешенного множества А множество А ∪ x также

неразрешенное. Очевидно, что несущественные участники настолько несущественны для

разделения секрета, что им просто не нужно посылать никакой информации. Поэтому да-

лее, без ограничения общности, рассматриваются только такие структуры доступа

Г, для

которых все элементы являются существенными. Кроме того, естественно предполагать,

что

Г является монотонной структурой, т.е. из А ⊂ В, А ∈ Г следует В ∈ Г.

Пример 18.2. Рассмотрим простейшую структуру доступа —

(n,n)-пороговую схему,

т.е. все участники вместе могут восстановить секрет, а любое подмножество участников

не может получить дополнительной информации о секрете. Будем строить идеальную

СРС, выбирая и секрет, и его проекции из группы

вычетов по модулю q, т.е. S

= S

= … = S

= Z

. Дилер генерирует n–1 независимых равномерно распределенных на Z

случайных величин

и посылает і-му учаснику (і = 1, ... , n-1) его “проекцию” s

= x

, а

n-му участнику — s

= s

– (s

+ … + s

n-1

). Кажущееся “неравноправие” n-ого участни-

ка тут же исчезает, если мы выпишем распределение

,…, s

), которое очевидно

равно

1/qn–1, если s

= s

+ … + s

, а в остальных случаях равно 0. Теперь легко про-

веряется и свойство (18.2), означающее в данном случае независимость случайной вели-

чины

от случайных величин {S

: і ∈ А} при любом собственном подмножестве А.

Данное выше определение СРС, оперирующее понятием распределение вероятно-

стей, ниже переведено, почти без потери общности, на комбинаторный язык, который

представляется более простым для понимания. Произвольная

M * (n + 1)-матрица V,

строки которой имеют вид

v = (v

, v

, …, v

), где v

∈ S

, называется матрицей комби-

наторной СРС, а ее строки — правилами распределения секрета. Для заданного значе-

ния секрета

дилер СРС случайно и равновероятно выбирает строку v из тех строк

матрицы

V, для которых значение нулевой координаты равно s

Определение 18.2

Матрица V задает совершенную комбинаторную СРС, реализующую структуру дос-

тупа

Г, если, во-первых, для любого множества А ∈ Г нулевая координата любой стро-

ки матрицы

V однозначно определяется значениями ее координат из множества А, и, во-

вторых, для любого множества

А ∉ Г и любых заданных значений координат из множе-

ства

А число строк матрицы V с данным значением α нулевой координаты не зависит от

α.

348 Глава 18. Криптографическая защита

Сопоставим совершенной вероятностной СРС, задаваемой парой (P, S), матрицу V,

состоящую из строк

s ∈ S, таких что P(s) > 0. Заметим, что если в определении 1 поло-

жить все ненулевые значения

P одинаковыми, а условия (18.1) и (18.2) переформулировать

на комбинаторном языке, то получится определение 2. Это комбинаторное определение

несколько обобщается, если допустить в матрице

V повторяющиеся строки, что эквива-

лентно вероятностному определению 1, когда значения вероятностей

P(s) — рациональ-

ные числа.

Продолжение примера 18.2 (из предыдущего раздела). Переформулируем данную

выше конструкцию

(n,n)-пороговой СРС на комбинаторном языке. Строками матрицы

V являются все векторы s такие, что s

+ s

+ … + s

= 0. Очевидно, что матрица V за-

дает совершенную комбинаторную СРС для

Г={1, …, n}, так как для любого собствен-

ного подмножества

А ⊂ {1, …, n} и любых заданных значений координат из множества

А число строк матрицы V с данным значением нулевой координаты равно q

n–1 – |A|

Удивительно, но простой схемы примера 2 оказывается достаточно, чтобы из нее, как

из кирпичиков, построить совершенную СРС для произвольной структуры доступа. А

именно, для всех разрешенных множеств, т.е. для

А ∈ Г, независимо реализуем описан-

ную только что пороговую

(|A|, |A|)-СРС, послав тем самым і-му учаснику cтолько

“проекций”

, скольким разрешенным множествам он принадлежит. Это словесное

описание несложно перевести на комбинаторный язык свойств матрицы

V и убедиться,

что эта СРС совершенна. Как это часто бывает, “совершенная” не значит “экономная”, и

у данной СРС размер “проекции” оказывается, как правило, во много раз больше, чем

размер секрета. Эту схему можно сделать более экономной, так как достаточно реализо-

вать пороговые

(|A|, |A|)-СРС только для минимальных разрешенных множеств А, т.е.

для

А ∈ Г

min

, где Г

min

— совокупность минимальных (относительно включения) мно-

жеств из

Г. Тем не менее, для пороговой (n, n/2)-СРС размер “проекции” (измеренный,

например, в битах) будет в

n/2

~ 2n/ 2πn раз больше размера секрета (это наихудший

случай для рассматриваемой конструкции). С другой стороны, как мы убедимся чуть

позже, любая пороговая структура доступа может быть реализована идеально, т.е. при

совпадающих размерах “проекции” и секрета. Поэтому естественно возникает вопрос о

том, каково максимально возможное превышение размера “проекции” над размером

секрета для

наихудшей структуры доступа при наилучшей реализации. Формально, R(n)

= max R(Г)

, где max берется по всем структурам доступа Г на n участниках, а R(Г) =

min max

log |S

, где min берется по всем СРС, реализующим данную структуру доступа

Г, а max — по і = 1, ..., n. Приведенная конструкция показывает, что R(n) ≤ C

n/2n

. С

другой стороны,

R(n) ≥ n/log n. Такой огромный “зазор” между верхней и нижней

оценкой дает достаточный простор для исследований (предполагается, что

R(n) зависит

от

n экспоненциально).

Линейное разделение секрета

Начнем с предложенной Шамиром элегантной схемы разделения секрета для порого-

вых структур доступа. Пусть

К = GF(q) — конечное поле из q элементов (например, q

= p

— простое число и К = Z

) и q > n. Сопоставим участникам n различных ненуле-

Математика разделения секрета 349

вых элементов поля {a

, …, a

} и положим a

= 0. При распределении секрета s

дилер

СРС генерирует

k–1 независимых равномерно распределенных на GF(q) случайных ве-

личин

(j = 1, …, k–1) и посылает і-му учаснику (і = 1, ..., n) “его” значение s

f(a

) многочлена f(x) = f

+ f

x + … + f

k-1

, где f

= s

. Поскольку любой много-

член степени

k-1 однозначно восстанавливается по его значениям в произвольных k

точках (например, по интерполяционной формуле Лагранжа), то любые

k участников

вместе могут восстановить многочлен

f(x) и, следовательно, найти значение секрета как

= f(0). По этой же причине для любых k–1 участников, любых полученных ими зна-

чений проекций

и любого значения секрета s

существует ровно один “соответст-

вующий” им многочлен, т.е. такой, что

= f(a

) и s

= f(0). Следовательно, эта схема

является совершенной в соответствии с определением 2. “Линейность” данной схемы

становится ясна, если записать “разделение секрета” в векторно-матричном виде:

s = fH, (18.3)

где s = (s

, …, s

), f = (f

, …, f

k–1

), k × (n+1) — матрица H = (h

) = (a

j-1

) и h

= 1.

Заметим, что любые

k столбцов этой матрицы линейно независимы, а максимально воз-

можное число столбцов матрицы

H равно q, чтобы добиться обещанного значения q+1

надо добавить столбец, соответствующий точке “бесконечность”.

Возьмем в (18.3) в качестве

H произвольную r × (n + 1)-матрицу с элементами из

поля

K. Получаемую СРС, будем называть одномерной линейной СРС. Она является со-

вершенной комбинаторной СРС со структурой доступа

Г, состоящей из множеств А та-

ких, что вектор

представим в виде линейной комбинации векторов {h

: j ∈ A}, где h

— это

j-ый столбец матрицы H. Строками матрицы V, соответствующей данной СРС,

являются, как видно из (18.3), линейные комбинации строк матрицы

H. Перепишем

(18.3) в следующем виде

= (f, h

) для j = 0, 1, …, n,

где (f, h

) — скалярное произведение векторов f и h

. Если А ∈ Г, т.е. если h

Σλ

, то

= (f, h

) =

()

f, Σλ

= Σλ

(f, h

) = Σλ

и, следовательно, значение секрета однозначно находится по его “проекциям”. Рассмот-

рим теперь случай, когда вектор

не представим в виде линейной комбинации векто-

ров

: j ∈ A}. Нам нужно показать, что в этом случае для любых заданных значений

координат из множества

А число строк матрицы V с данным значением любой коорди-

наты не зависит от этого значения. В этом не трудно убедится, рассмотрев (18.3) как

систему линейных уравнений относительно неизвестных

и воспользовавшись тем, что

система совместна тогда и только тогда, когда ранг матрицы коэффициентов равен рангу

расширенной матрицы, а число решений у совместных систем одинаково и равно числу

решений однородной системы.

Указание. Рассмотрите две системы: c “нулевым” уравнением и без него (т.е. со сво-

бодным членом). Так как вектор

не представим в виде линейной комбинации векто-

350 Глава 18. Криптографическая защита

ров {h

: j ∈ A}, то ранг матрицы коэффициентов второй системы на 1 больше ранга

матрицы коэффициентов первой системы. Отсюда немедленно следует, что если первая

система совместна, то совместна и вторая при любом

Эта конструкция подводит нас к определению общей линейной СРС. Пусть секрет и

его “проекции” представляются как конечномерные векторы

= (s

, …, s

) и генериру-

ются по формуле

= fH

, где H

— некоторые r × m

-матрицы. Сопоставим каждой

матрице

линейное пространство L

ее столбцов (т.е. состоящее из всех линейных

комбинаций вектор-столбцов матрицы

). Несложные рассуждения, аналогичные при-

веденным выше для одномерного случая (все

= 1), показывают, что данная конструк-

ция дает совершенную СРС тогда и только тогда, когда семейство линейных подпро-

странств

, …, L

} конечномерного векторного пространства K

удовлетворяет упо-

мянутому выше свойству “все или ничего”. При этом множество

А является

разрешенным

: a ∈ A} содержит подпространство L

целиком. С другой стороны,

множество

А является неразрешенным (А ∉ Г), если и только если линейная оболочка

подпространств

{La: a ∈ A} пересекается с подпространством L

только по вектору 0.

Отметим, что если бы для некоторого

А пересечение L

и линейной оболочки {L

: a ∈

было нетривиальным, то участники А не могли бы восстановить секрет однозначно,

но получали бы некоторую информацию о нем, т.е. схема не была бы совершенной.

Пример 18.3. Рассмотрим следующую структуру доступа для случая четырех участ-

ников, задаваемую

min

= {{1,2}, {2,3}, {3,4}}. Она известна как первый построенный

пример структуры доступа, для которой не существует идеальной реализации. Более то-

го, было доказано, что для любой ее совершенной реализации

R(Г) ≥ 3/2. С другой сто-

роны, непосредственная проверка показывает, что выбор матриц

, H

, ..., H

, приве-

денных на рис. 18.2, дает совершенную линейную СРС с

R = 3/2, реализующую эту

структуру, которая, следовательно, является и оптимальной (наиболее экономной) СРС.

Рис. 18.2. Матрицы, реализующие совершенную линейную СРС

Идеальное разделение секрета и матроиды

Начнем с определения идеальных СРС. Для этого вернемся к комбинаторному опре-

делению совершенной СРС. Следующее определение совершенной СРС является даже

более общим, чем вероятностное определение 1, поскольку условие (18.2) заменено в

нем на более слабое.

Для произвольного множества

В ⊆ {0, 1, …, n} обозначим через V

M × |B|-

матрицу, полученную из матрицы

V удалением столбцов, номера которых не принадле-

жат множеству

В. Пусть ||W|| обозначает число различных строк в матрице W.