Асимметричные системы шифрования

ИНФОРМАЦИОННАЯ БЕЗОПАСНОСТЬ В МОБИЛЬНЫХ СИСТЕМАХ СВЯЗИ

В силу свободы доступа к радиоэфиру системы беспровод­ной связи потенциально уязвимы для разного рода злоумышлен­ников в плане как перехвата сообщения с последующим несанк­ционированным использованием чужой информации, так и попы­ток обмана сети и абонентов. Поэтому стандарты систем мобиль­ной связи предусматривают различные механизмы защиты инте­ресов законных пользователей и самой сети от подобных дейст­вий. К таким механизмам относятся шифрование данных и про­цедуры аутентификации.

Методы шифрования

Шифрование состоит в преобразовании исходного, откры­того текста в криптограмму (шифртекст) по некоторому прави­лу (алгоритму шифрования) с целью скрыть смысл сообщения. Некоторые параметры этого алгоритма, называемые ключом шифрования, известны только законным абонентам и неизвестны (секретны) для злоумышленников. Законный пользователь легко может осуществить обратное преобразование шифровки в ис­ходный текст, а криптоаналитик, т.е. субъект, пытающийся не­санкционированно получить открытый текст, будет вынужден уга­дывать значение ключа.

В зависимости от степени секретности сведений, содержа­щихся в сообщении (государственных, военных, коммерческих, личных и т.п.), разрабатываются и используются различные систе­мы шифрования. При их создании учитываются и возможности аналитика как интеллектуальные, так и технические. Ясно, что за­крыть информацию от злоумышленника-одиночки проще, чем от другого государства, располагающего возможностью привлекать для раскрытия ключа крупных специалистов и новейшую технику.

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

Для оценки стойкости выдвигаются различные критерии. Наиболее объективный - это сложность (число умножений) суще­ствующего алгоритма вскрытия ключа. Если известны только ал­горитмы вскрытия экспоненциальной сложности, у которых число операций пропорционально а^п, где а - целое, а n - число неиз­вестных параметров, то считается, что система шифрования об­ладает совершенной стойкостью. Подобные алгоритмы решения задачи реализуют прямой перебор вариантов. Так как аналитик при любых условиях может воспользоваться подбором парамет­ров (силовой атакой), то нельзя разработать систему, обладаю­щую стойкостью, превышающей совершенную. Другие системы шифрования, для которых известны алгоритмы вскрытия ключа меньшей сложности, - например, полиномиальная (линейная) с числом операций, пропорциональным n^а, - считаются система­ми малой стойкости.

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

Множество систем шифрования разделяют на симметрич­ные, одноключевые, и асимметричные, двухключевые, или сис­темы с открытым ключом [47-49].

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

8.1.1. Симметричные системы шифрования

Структурная схема системы секретной связи показана на рис. 8.1.

На передающей стороне исходный текст X = (Х₁, Х₂,..., Х_п)

с помощью известного алгоритма и секретного ключа
Z = (Z_1, Z₂,...,Z_k) преобразуется в шифрограмму Y =(Y₁,Y_2,...,Y_m). Компоненты этих последовательностей могут быть битами, символами, взятыми из одного или нескольких ал­фавитов разных объемов. Обычно это биты. На приемной сторо­не по известным Y' и Z восстанавливается исходный текст X .

Аналитик, перехватив шифрограмму, пытается понять ис­ходный текст или определить ключ шифрования. Кроме того, он может внедрить в систему собственную, фальшивую криптограм­му с целью обмана абонента Б. Таким образом, система шифро­вания должна обеспечить не только секретность связи, но и за­щиту от несанкционированного изменения, подмены сообщения X. Последняя задача, называемая аутентификацией сообщения или контролем целостности, обсуждается в § 8.2.

Из этой схемы видно, что для оперативной доставки ключа шифрования на приемную сторону должен быть предусмотрен специальный, защищенный канал. Возникает задача распределе­ния ключей шифрования между пользователями или задача управления ключами. При большом числе абонентов, желающих установить секретную связь, распределение ключей становится серьезной проблемой при использовании симметричных систем шифрования. Решение этой задачи и стимулировало разработку асимметричных методов шифрования.

Теория и многовековая практика позволили сформулиро­вать ряд требований к ключам систем шифрования повышенной стойкости. С позиций теории информации наибольшие трудности по вскрытию криптограммы без знания ключа возникают, если _в ней отсутствует информация о X, что означает использование преобразований, обеспечивающих статистическую независимость случайных процессов X и Y.

Анализ этого требования приводит к следующим рекомен­дациям. Конкретное значение ключа должно использоваться только один раз для шифрования одного сообщения. Значения ключа должны выбираться с одинаковой вероятностью 1/L , где I - объем алфавита символов ключа. Длина ключа к должна быть не меньше длины сообщения п.

На практике из-за сложности реализации и стоимости не все перечисленные требования могут быть выполнены. Для по­строения практических систем шифрования используются прин­ципы рассеяния и перемешивания. Первый требует, чтобы изме­нение одного символа исходного текста приводило к изменению большого числа символов криптограммы. Второй направлен на поиск преобразований, разрушающих статистические связи

между Y и X

Общий подход к построению практически стойких шифров состоит в многократном применении простых методов шифрова­ния путем подстановки (замены) и перестановки символов исход­ного текста, а также скремблирования.

Метод подстановки заключается в том, что символ исход­ного текста заменяется другим, выбранным из этого или другого алфавита по правилу, задаваемому ключом шифрования. Место­положение символа в тексте при этом не изменяется.

При перестановке в соответствии с ключом изменяется по­рядок следования символов открытого текста. Значение символа при этом сохраняется. Шифры перестановки являются блочными, т.е. исходный текст предварительно разбивается на блоки, в которых и осуществляется заданная ключом перестановка.

Под скремблированием понимается процесс наложения на коды символов открытого текста кодов случайной последова­тельности чисел, которую называют также гаммой (по названию буквы у греческого алфавита, используемой в математических формулах для обозначения случайного процесса). Гаммирование относится к поточным методам шифрования, когда следующие Друг за другом символы открытого текста последовательно пре­вращаются в символы шифрограммы, что повышает скорость преобразования.

В качестве гаммы широко используются псевдослучайные последовательности (ПСП). Коды символов криптограммы у, есть поразрядная сумма по модулю 2 кодов X, и Z,. Расшифровка производится по правилу: X = Y+Z = X + Z + Z = X , так что на при­емной стороне должна генерироваться такая же ПСП и с той же фазой. Стойкость скремблирования определяется параметрами ПСП, главным из которых является период последовательности. На практике используются генераторы ПСП с периодом в не­сколько недель. Из-за простоты генерации хороших ПСП и высо­кой скорости шифрования - дешифрования скремблирование предусмотрено многими стандартами мобильной связи (GSM TETRA, IS-95).

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

Сначала передается преамбула, в которой содержится ин­формация о параметрах генерируемой ПСП, в том числе и о зна­чении начальной фазы Z_oo. По каждым n сформированным сим­волам шифрограммы вычисляется и устанавливается в генера­торе новое значение фазы Z_0i. Обратная связь делает метод гаммирования чувствительным к искажениям криптограммы. Так, из-за помех в канале связи могут исказиться некоторые принятые символы, что приведет к вычислению ошибочного значения фазы ПСП и затруднит дальнейшую расшифровку. В то же время такое искажение можно объяснить попыткой злоумышленника навязать ложные данные.

 

Следует отметить, что в отечественном стандарте на шиф­рование предусмотрено использование подстановок, перестано­вок и гаммирования.

Распределение ключей в симметричных системах шифро­вания является серьезной задачей, если число законных пользо­вателей велико. Протокол распределения ключей должен преду­сматривать запрет на передачу по радиоканалу сеансового ключа и возможность оперативно изменять ключ.

Обычно протокол распределения включает два этапа. При регистрации МС в сети центр аутентификации (ЦА) выделяет ей секретное число К,, которое хранится у нее в стандартном иден­тификационном модуле (SIM). Второй этап протокола в упрощен­ном варианте для стандарта GSM показан на рис. 8.3.

При необходимости осуществить секретную связь МС по­сылает запрос на шифрование. ЦКМС генерирует случайное чис­ло RAND (random number), которое передается на МС и исполь­зуется на обеих сторонах для вычисления единого сеансового ключа K_s по алгоритму А8. Из-за помех в радиоканале возможно искажение RAND, и ключ на МС будет отличаться от вычисленно­го ЦКМС. Для проверки идентичности ключей служит числовая последовательность ключа (ЧПК), являющаяся кодом его хэш-функции (см. § 8.2). Любые изменения ключа K_s с большой веро­ятностью приводят к изменению ЧПК, но по ЧПК трудно опреде­лить значение K_s. Поэтому перехват ЧПК в радиоканале не сни­жает стойкости шифра. После подтверждения правильности ус­тановки ключей производится поточное шифрование данных по алгоритму А5.

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

Асимметричные системы шифрования

В асимметричных системах шифрования каждый абонент имеет два связанных между собой ключа: открытый и секретный. При необходимости установления секретной связи абоненты об­мениваются открытыми ключами по незащищенным каналам, и, следовательно, открытые ключи могут быть известны всем пользователям (и злоумышленнику). Секретный ключ хранится абонентом в тайне. Определение секретного ключа по открытому практически невозможно, так как требует несоизмеримых с цен­ностью получаемой информации вычислительных затрат.

Любой абонент может послать шифрованное сообщение другому абоненту, используя его открытый ключ. Вскрыть такое сообщение может только адресат по своему секретному ключу. Таким образом, отпадает необходимость в распределении клю­чей шифрования между абонентами.

Предложено много асимметричных систем шифрования (RSA, ранцевая система, Эль-Гамаля, Мак-Элиса и др.), основан­ных на использовании односторонних или однонаправленных функций. Функция Y = f(X) называется односторонней, если для вы­числения У по X существует алгоритм полиномиальной сложности, а для определения X по У известны только алгоритмы экспоненци­альной сложности. Иначе, найти У по X легко, а Х по У трудно.

Строгого доказательства, что данная функция является од­носторонней, не существует, так как прогресс в математике может привести в будущем к получению решения приемлемой сложности для задач, ранее считавшихся трудноразрешимыми. Известны многие функции, претендующие на звание односторонних.

Ярким представителем этого множества является показа­тельная функция в кольце вычетов по некоторому модулю (8.1)

где а, n - известные натуральные числа.

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

Пример 8.1. Пусть для простоты n = 10000 , X = 4101. Чис­ло X представим в двоичной позиционной системе счисления

4101 = 2¹²+2²+2⁰.

Тогда

У₃ У₂ У₁ У₀ –остаток от деления а⁴¹⁰¹ на 10000.

Видно, что для вычисления У потребовалось всего 16 ум­ножений и делений, которые при выбранном модуле сводятся просто к удержанию 4 младших разрядов результатов возведения в квадрат.

Обратная задача - вычисление дискретного логарифма -практически неразрешима. Действительно, если, например, У = 5678 , то сравнение (8.2) иначе записывается как равенство а^х =**...*5678 , где символ * обозначает неизвестную десятич­ную цифру. Значения этих неизвестных цифр можно восстано­вить лишь одновременно со значением X, перебрав все варианты последнего, количество которых зависит от используемой раз­рядности чисел. При разрядности в 100 - 300 десятичных цифр подобный перебор на самых мощных ЭВМ занял бы время, не выражаемое даже геологическими эпохами.

Однако функция (8.1) "в одиночку" для целей шифрования непригодна, так как законный получатель, определяя исходный текст X по шифрограмме Y, будет испытывать те же трудности, что и криптоаналитик. Поэтому для законного абонента вводится лазейка (потайной ход), использование которой приводит к рез­кому снижению затрат на вычисление обратной функции.

Односторонней функцией с лазейкой называется функция Y= /z(X), обладающая следующими свойствами:

• для вычисления У по X существует алгоритм полиномиальной сложности;

• для вычисления Х по Упри известном Zтакже существует алгоритм полиномиальной сложности;

• для вычисления X по У при неизвестном Z существует только алгоритм экспоненциальной сложности.

Из определения видно, что Z играет роль секретного ключа, находящегося у законного получателя шифрограммы. Отсюда ясен механизм создания шифров с открытым ключом. Для труд­норазрешимой задачи формулируются условия, знание которых позволяет создать алгоритм ее решения полиномиальной слож­ности. Эти условия и составляют секрет законного пользователя.

В качестве примера рассмотрим асимметричную систему шифрования RSA (Ривест, Шамир, Адлеман). В ее основу поло­жена трудноразрешимая задача разложения (факторизации) большого числа на простые множители. Сложность факторизации числа иллюстрирует следующий факт. Для разложения числа, содержащего около 130 десятичных цифр, потребовалась работа 1600 ЭВМ в течение 8 месяцев.

Пусть n = pq , где р и q - простые числа, т.е. не имеющие де­лителей, кроме 1 и самих себя. Каждый пользователь, выбрав р и q и случайное d, находит соответствующее е как решение сравнения

т.е. получает свои открытый (е,n) и секретный (d,n) ключи. Для криптоаналитика определение d по известному (открытому) е оз­начает факторизацию л, сложность которой уже обсуждалась.

Шифрованию открытого текста X предшествует преобразо­вание его по определенному правилу в целое число X (в простей­шем виде оно поясняется в примере 8.2). Вычисление криптограм­мы в адрес данного пользователя производится по формуле

что согласно сказанному ранее не позволяет аналитику получить X по известному У. Адресат же по своему секретному ключу легко находит сначала целое X

а затем по нему восстанавливает исходный текст X, т.е. d являет­ся той лазейкой, которой пользуется законный абонент при рас­шифровке У.

Авторы системы RSA рекомендуют для обеспечения высо­кой стойкости использовать числа, содержащие около 200 деся­тичных цифр. Хотя разработаны специальные вычислители, по­зволяющие быстро возводить числа в большие степени, быстро­действие RSA считается низким.

Асимметричные системы шифрования характеризуются высокой теоретической стойкостью. Однако их внедрение сдер­живается недоверием со стороны практиков. Как уже указыва­лось, всегда существует опасность, что успехи математиков при­ведут к приемлемому по сложности решению задачи, ранее счи­тавшейся трудной. И история шифрования знает такие примеры. Так, для ранцевой системы шифрования, основанной на односто­роннем преобразовании У = X^TN, где X, N - столбцы целых чи­сел, был найден алгоритм определения X по У с числом опера­ций меньшим, чем при прямом переборе значений X.

В то же время в асимметричных системах не требуется распределять ключи шифрования. Поэтому считаются перспек­тивными гибридные системы, в которых асимметричная система служит для распределения сеансовых ключей, а шифрование данных выполняется с помощью симметричной системы. Класси­ческий протокол распределения ключей, основанный на односто­ронней функции (8.1), показан в табл. 8.1.

Абоненты случайно и независимо выбирают числа d_A и d_Б и держат их в секрете. По (8.1) каждый вычисляет свой открытый ключ (е_А или е_Б) и посылает его другому абоненту.

 

Из-за одно­сторонности (8.1) по открытым ключам трудно определить сек­ретные. При установлении режима шифрования каждый из або­нентов вычисляет сеансовый ключ. Для этого открытый ключ дру­гого абонента возводится в степень, равную своему секретному ключу. Из табл. 8.1 видно, что такие вычисления дают одинако­вый результат Z_AБ = Z_БA, который можно использовать как сеансо­вый ключ в симметричной системе шифрования. Важно отметить, что распределение ключей произошло без передачи секретных параметров по каналу связи.