Методы и средства защиты информации. Внимание!!! В книге могут встречаться существенные ошибки (в рисунках и формулах). Они не связаны ни со
 Скачать 4.86 Mb.
|
|
Глава 18. Криптографическая защита угадать , исходя из предполагаемого содержания или структуры открытого текста Поскольку криптографические методы ЗИ применяются давно , то уже сфор - мулированы основные требования к ним 1. Метод должен быть надежным , т е восстановление открытого текста при владении только шифротекстом , но не ключом должно быть практически не - выполнимой задачей 2. Из - за трудности запоминания объем ключа не должен быть большим 3. Из - за трудностей , связанных со сложными преобразованиями , процессы шифрования должны быть простыми 4. Из - за возможности появления ошибок передачи дешифрование шифротек - ста , содержащего отдельные ошибки , не должно привести к бесконечному увеличению ошибок в полученном предполагаемом открытом тексте 5. Из - за трудностей передачи объем шифротекста не должен быть значительно больше открытого текста Перечисленные требования были разработаны для традиционной крипто - графии При современном развитии техники необходимость удовлетворения перечис - ленным требованиям претерпевает существенные изменения В связи с развитием технологии , позволяющей с большой плотностью запи - сать и длительное время надежно хранить большие объемы информации , усло - вие небольшого объема ключа может быть ослаблено ( по существу это условие , как и все остальные , приобретает новый смысл , соответствующий достигнутому уровню техники ). В связи с развитием микроэлектроники появляется возмож - ность разработки дешевых устройств , осуществляющих быстро и точно сравни - тельно сложные преобразования информации С другой стороны , возможность увеличения скорости передачи отстает от возможности увеличения скорости об - работки информации Это , несомненно , позволяет ослабить требование п . 3 без ущерба для практически достигаемой скорости передачи В настоящее время связное оборудование является высоконадежным , а методы обнаружения и ис - правления ошибок — хорошо развитыми К тому же , обычно используемые в компьютерных сетях протоколы сеансов связи предусматривают передачу любо - го текста даже при наличии сбоев во время передачи Поэтому требование п . 4 в значительной мере потеряло свою актуальность В отдельных случаях , если ка - налы связи не перегружены , может быть ослаблено и требование п . 5. Таким образом , не затронутым осталось требование п . 1, при рассмотрении которого следует учесть два обстоятельства Во - первых , в автоматизированных системах ( АС ) циркулируют большие объ - емы информации , а наличие большого объема шифротекста облегчает задачу криптоанализа Математика разделения секрета 359 Во - вторых , для решения задачи криптоанализа можно использовать ЭВМ Это позволяет в новых условиях требовать значительного увеличения надежно - сти Другим важным отрицательным фактором применения криптографии в АС является то , что часто используются языки с весьма ограниченным запасом слов и строгим синтаксисом ( языки программирования ). В связи с новыми специфическими применениями криптографических мето - дов могут быть выдвинуты также другие требования Так , например , второй важ - ной областью применения криптографических методов ЗИ являются системы управления базами данных ( СУБД ). В этом случае к криптографическим мето - дам ЗИ предъявляются следующие дополнительные требования 1. Из - за невозможности чтения и возобновления записей с середины файла , шифрование и дешифрование каждой записи должны производиться незави - симо от других записей 2. Для создания больших удобств обработки и во избежание излишней пере - грузки системы вспомогательными преобразованиями необходимо все опе - рации с файлами проводить с данными в зашифрованном виде Специфика СУБД оказывает влияние на надежность защиты по следующим причинам : • данные в СУБД продолжительное время находятся в зашифрованном виде Это затрудняет или даже делает невозможной частую смену ключей , и в свя - зи с этим ЗИ становится менее надежной ; • ключи могут не передаваться по разным адресам , а храниться все в одном месте Это повышает надежность системы из - за уменьшения возможности овладения ключами посторонними лицами В файловых системах вероятность появления ошибки гораздо меньше , чем в каналах связи , поэтому требование п . 4 для файловых систем не имеет большо - го практического значения Появление быстродействующих ЭВМ способствует возникновению так назы - ваемой вычислительной криптографии , тесно связанной с вычислительной тех - никой Математика разделения секрета Рассмотрим следующую , в наше время вполне реальную ситуацию Два сов - ладельца драгоценности хотят положить ее на хранение в сейф Сейф совре - менный , с цифровым замком на 16 цифр Так как совладельцы не доверяют друг другу , то они хотят закрыть сейф таким образом , чтобы они могли открыть его вместе , но никак не порознь Для этого они приглашают третье лицо , называе - мое дилером , которому они оба доверяют ( например , потому что оно не получит больше доступ к сейфу ). Дилер случайно выбирает 16 цифр в качестве “ ключа ”, чтобы закрыть сейф , и затем сообщает первому совладельцу втайне от второго первые 8 цифр “ ключа ”, а второму совладельцу втайне от первого — последние 360 Глава 18. Криптографическая защита 8 цифр “ ключа ”. Такой способ представляется с точки здравого смысла опти - мальным , ведь каждый из совладельцев , получив “ полключа ”, не сможет им вос - пользоваться без второй половины , а что может быть лучше ?! Недостатком дан - ного примера является то , что любой из совладельцев , оставшись наедине с сейфом , может за пару минут найти недостающие “ полключа ” с помощью не - сложного устройства , предназначенного для перебора ключей и работающего на тактовой частоте 1 МГц Кажется , что единственный выход — в увеличении раз - мера “ ключа ”, скажем , вдвое Но есть другой математический выход , опровер - гающий ( в данном случае — к счастью ) соображения здравого смысла А имен - но , дилер независимо выбирает две случайные последовательности по 16 цифр в каждой , сообщает каждому из совладельцев втайне от другого “ его ” последо - вательность , а в качестве “ ключа ”, чтобы закрыть сейф , использует последова - тельность , полученную сложением по модулю 10 соответствующих цифр двух выбранных последовательностей Довольно очевидно , что для каждого из сов - ладельцев все 10 16 возможных “ ключей ” одинаково вероятны и остается только перебирать их , что потребует в среднем около полутора лет для устройства пе - ребора ключей , оборудованного процессором с частотой 100 МГц И с математической , и с практической точки зрения неинтересно останавли - ваться на случае двух участников и следует рассмотреть общую ситуацию Не - формально говоря , схема , разделяющая секрет ( СРС ) позволяет “ распреде - лить ” секрет между n участниками таким образом , чтобы заранее заданные раз - решенные множества участников могли однозначно восстановить секрет ( совокупность этих множеств называется структурой доступа ), а неразре - шенные — не получали никакой дополнительной к имеющейся априорной ин - формации о возможном значении секрета СРС с последним свойством называ - ются совершенными История СРС начинается с 1979 года , когда эта проблема была поставлена и во многом решена Блейкли и Шамиром для случая пороговых (n, k) - СРС ( т е разрешенными множествами являются любые множества из k или более эле - ментов ). Особый интерес вызвали так называемые идеальные СРС , т е такие , где объем информации , предоставляемой участнику , не больше объема секре - та Оказалось , что любой такой СРС соответствует матроид и , следовательно , не для любой структуры доступа возможно идеальное разделение секрета С другой стороны , было показано , что для любого набора разрешенных множеств можно построить совершенную СРС , однако известные построения весьма не - экономны Рассмотрим некоторые алгебро - геометрические и комбинаторные за - дачи , возникающие при математическом анализе СРС Будем говорить , что семейство подпространств {L 0 , …, L n } конечномерного векторного пространства L над полем K удовлетворяет свойству “ все или ни - чего ”, если для любого множества A ⊂ {1, …, n} линейная оболочка подпро - странств {L a : a ∈ A} либо содержит подпространство L 0 целиком , либо пере - секается с ним только по вектору 0 В подразделе “ Линейное разделение сек - Математика разделения секрета 361 рета ” мы увидим , что такое семейство задает “ линейную ” СРС , у которой мно - жество A ⊂ {1, …, n} является разрешенным , если и только если линейная оболочка подпространств {L a : a ∈ A} содержит подпространство L 0 целиком В связи с этим понятием возникает ряд вопросов Например , если поле K конеч - но ( |K| = q ) и все подпространства {L 0 , …, L n } одномерны , то каково макси - мально возможное число участников n для линейных пороговых ( n , k )- СРС ( k > 1 )? Иначе говоря , каково максимально возможное число векторов {h 0 , …, h n } таких , что любые k векторов , содержащие вектор h 0 , линейно независимы , а любые k + 1 векторов , содержащие вектор h 0 , линейно зависимы Оказывает - ся , что это свойство эквивалентно следующему , на первый взгляд более силь - ному , свойству : любые k векторов линейно независимы , а любые k + 1 — ли - нейно зависимы Такие системы векторов изучались в геометрии как 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 0 , S 1 , … , S n и ( совместное ) распределение вероятностей P на их декартовом про - изведении S = S 0 * …* S n Соответствующие случайные величины обозначаются через S i Имеется также некоторое множество Г подмножеств множества {1, …, n} , называемое структурой доступа Определение 18.1 Пара (P,S) называется совершенной вероятностной СРС , реализующей структуру доступа Г , если P(S 0 = c 0 | S i = c i , i ∈ A) ∈ {0, 1} для A ∈ Г, (18.1) P(S0 = c0 | Si = ci, i ∈ A) = P(S0 = c0) для A ∉ Г (18.2) Это определение можно истолковать следующим образом Имеется мно - жество S 0 всех возможных секретов , из которого секрет s 0 выбирается с веро - ятностью p(s 0 ) , и имеется СРС , которая “ распределяет ” секрет s 0 между n участниками , посылая “ проекции ” s 1 , … , s n секрета с вероятностью P S0 (s 1 , …, s n ) Отметим , что і - ый учасник получает свою “ проекцию ” s i ∈ S i и не имеет ин - формации о значениях других “ проекций ”, однако знает все множества S i , а также оба распределения вероятностей p(s 0 ) и P S0 (s 1 , …, s n ) Эти два распреде - ления могут быть эквивалентны заменене на одно : P(s 0 , s 1 , …, s n ) = p( S0 )P S0 (s 1 , 362 Глава 18. Криптографическая защита …, s n ) , что и было сделано выше Цель СРС , как указывалось во введении , со - стоит в том , чтобы : • участники из разрешенного множества A ( т е A ∈ Г ) вместе могли бы одно - значно восстановить значение секрета — это отражено в свойстве (18.1); • участники , образующие неразрешенное множество А ( А ∉ Г ), не могли бы получить дополнительную информацию об s 0 , т е ., чтобы вероятность того , что значение секрета S 0 = c 0 , не зависела от значений “ проекций ” S i при і ∈ А — это свойство (18.2). Замечание о терминологии В англоязычной литературе для обозначения “ порции ” информации , посылаемой участнику СРС , были введены термины share ( А Шамир ) и shadow ( Г Блейкли ). Первый термин оказался наиболее популярным , но неадек - ватная ( во всех смыслах ) замена в данной работе акции на проекцию может быть несколько оправдана следующим примером Пример 18.1 . Множество S 0 всех возможных секретов состоит из 0 , 1 и 2 , “ представленных ”, соответственно : шаром ; кубом , ребра которого параллельны осям координат ; цилиндром , образующие которого параллельны оси Z При этом диаметры шара и основания цилиндра , и длины ребра куба и образующей ци - линдра , равны Первый участник получает в качестве своей “ доли ” секрета его проекцию на плоскость XY , а второй — на плоскость XZ Ясно , что вместе они однозначно восстановят секрет , а порознь — нет Однако эта СРС не является совершенной , так как любой из участников получает информацию о секрете , ос - тавляя только два значения секрета как возможные при данной проекции ( на - пример , если проекция — квадрат , то шар невозможен ). Еще одно замечание Элемент ( участник ) x ∈ {1, …, n} называется несуще - ственным ( относительно Г ), если для любого неразрешенного множества А мно - жество А ∪ x также неразрешенное Очевидно , что несущественные участники настолько несущественны для разделения секрета , что им просто не нужно посы - лать никакой информации Поэтому далее , без ограничения общности , рассмат - риваются только такие структуры доступа Г , для которых все элементы являются существенными Кроме того , естественно предполагать , что Г является монотон - ной структурой , т е из А ⊂ В , А ∈ Г следует В ∈ Г Пример 18.2. Рассмотрим простейшую структуру доступа — (n,n) - пороговую схему , т е все участники вместе могут восстановить секрет , а любое подмноже - ство участников не может получить дополнительной информации о секрете Бу - дем строить идеальную СРС , выбирая и секрет , и его проекции из группы Z q вы - четов по модулю q , т е S 0 = S 1 = … = S n = Z q Дилер генерирует n–1 независи - мых равномерно распределенных на Z q случайных величин х i и посылает і - му учаснику (і = 1, ... , n-1) его “ проекцию ” s i = x i , а n - му участнику — s n = s 0 – (s 1 + … + s n-1 ) Кажущееся “ неравноправие ” n - ого участника тут же исчезает , если мы выпишем распределение P S0 ( s 1 , … , s n ), которое очевидно равно 1/qn–1 , если s 0 = s 1 + … + s n , а в остальных случаях равно 0 Теперь легко проверяется и свойство Математика разделения секрета 363 (18.2), означающее в данном случае независимость случайной величины S 0 от случайных величин { S i : і ∈ А } при любом собственном подмножестве А Данное выше определение СРС , оперирующее понятием распределение ве - роятностей , ниже переведено , почти без потери общности , на комбинаторный язык , который представляется более простым для понимания Произвольная M * (n + 1) - матрица V , строки которой имеют вид v = (v 0 , v 1 , …, v n ) , где v i ∈ S i , на - зывается матрицей комбинаторной СРС , а ее строки — правилами распре - деления секрета Для заданного значения секрета s 0 дилер СРС случайно и равновероятно выбирает строку v из тех строк матрицы V , для которых значение нулевой координаты равно s 0 Определение 18.2 Матрица V задает совершенную комбинаторную СРС , реализующую структу - ру доступа Г , если , во - первых , для любого множества А ∈ Г нулевая координата любой строки матрицы V однозначно определяется значениями ее координат из множества А , и , во - вторых , для любого множества А ∉ Г и любых заданных значений координат из множества А число строк матрицы V с данным значени - ем α нулевой координаты не зависит от α Сопоставим совершенной вероятностной СРС , задаваемой парой (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 0 + s 1 + … + s n = 0 Очевид - но , что матрица V задает совершенную комбинаторную СРС для Г={1, …, n} , так как для любого собственного подмножества А ⊂ {1, …, n} и любых заданных значений координат из множества А число строк матрицы V с данным значени - ем нулевой координаты равно q n–1 – |A| Удивительно , но простой схемы примера 2 оказывается достаточно , чтобы из нее , как из кирпичиков , построить совершенную СРС для произвольной структу - ры доступа А именно , для всех разрешенных множеств , т е для А ∈ Г , незави - симо реализуем описанную только что пороговую (|A|, |A|) - СРС , послав тем са - мым і - му учаснику c только “ проекций ” s i A , скольким разрешенным множествам он принадлежит Это словесное описание несложно перевести на комбинаторный язык свойств матрицы V и убедиться , что эта СРС совершенна Как это часто бывает , “ совершенная ” не значит “ экономная ”, и у данной СРС размер “ проек - ции ” оказывается , как правило , во много раз больше , чем размер секрета Эту схему можно сделать более экономной , так как достаточно реализовать порого - |