Учебное пособие Ставрополь сф мггу им. М. А. Шолохова 2009
 Скачать 5.26 Mb.
|
|
) должны быть взаимно простыми. Далее, вычисляют секретный ключ k в , такой, что: (k B ∙K B ) mod φ(N) = 1 или B B 1 k = mod (P-1)(Q-1) K Это можно осуществить, так как получатель В знает пару простых чисел (P, Q) и может легко найти φ(N). Заметим, что k в и N должны быть взаимно простыми. Открытый ключ К в используют для шифрования данных, а секретный ключ k в - для расшифрования. Преобразование шифрования определяет криптограмму С через пару (открытый ключ К в , сообщение М) в соответствии со следующей формулой: B B K K C = E M = M mod N В качестве алгоритма быстрого вычисления значения С используют ряд последовательных возведений в квадрат целого М и умножений на М с приведением по модулю N. Обращение функции C = B K M mod N, т.е. определение значения М по известным значениям С, К в и N, практически не осуществимо при N≈2 512 129 Однако обратную задачу, т.е. задачу расшифрования криптограммы С, можно решить, используя пару (секретный ключ k в , криптограмма С) по следующей формуле: B B k -1 k M = E C = mod N C Таким образом, получатель В, который создает криптосистему, защищает два параметра: - секретный ключ k в - пару чисел (P, Q), произведение которых дает значение модуля N. С другой стороны, получатель В открывает значение модуля N и открытый ключ К в Противнику известны лишь значения К в и N. Если бы он смог разложить число N на множители Р и Q, то он узнал бы «потайной ход» - тройку чисел {Р, Q, К в }, вычислил значение функции Эйлера φ(N) = (P-1)(Q-1) и определил значение секретного ключа k в . Однако, как уже отмечалось, разложение очень большого N на множители вычислительно не осуществимо (при условии, что длины выбранных Р и Q составляют не менее 100 десятичных знаков). 11.3.1 Процедуры шифрования и расшифрования в криптосистеме RSA Предположим, что пользователь А хочет передать пользователю В сообщение в зашифрованном виде, используя криптосистему RSA. В таком случае пользователь А выступает в роли отправителя сообщения, а пользователь В - в роли получателя. Как отмечалось выше, криптосистему RSA должен сформировать получатель сообщения, т.е. пользователь В. Рассмотрим последовательность действий пользователя В и пользователя А. 1. Пользователь В выбирает два произвольных больших простых числа Р и Q. 2. Пользователь В вычисляет значение модуля N = Р∙Q. 3. Пользователь В вычисляет функцию Эйлера: φ(N) = (P-1)(Q-1) и выбирает случайным образом значение большого случайного числа, которое назовем k в . Это число должно быть взаимно простым с функцией Эйлера (т.е. результатом умножения φ(N) = (P-1)(Q-1) ) 4. Определяется такое число K B , для которого является истинным следующее соотношения (K B ∙ k в ) mod ( φ(N) ) = 1 и 1 < K B ≤ φ(N). 130 5. Пара чисел (N, К в ) является открытым ключом и может быть передана по незащищенному каналу. А пара чисел (N, k в ) – закрытым ключом, он держится в секрете и используется для дешифрации. Если пользователь А хочет передать пользователю В сообщение М, он выполняет следующие шаги. 6. Пользователь А разбивает исходный открытый текст М на блоки (только до N-1), каждый из которых может быть представлен в виде числа М i = 0, 1, 2, … , N-1. 7. Пользователь А шифрует текст, представленный в виде последовательности чисел M i по формуле mod B K i i C M N и отправляет криптограмму C 0 , C 1 , … C N-1 8. Чтобы расшифровать эти данные, используя секретный ключ (N, k в ), необходимо выполнить следующие вычисления: mod B k i i M C N В результате будет получена последовательность чисел М i , которые представляют собой исходное сообщение М. Чтобы алгоритм RSA имел практическую ценность, необходимо иметь возможность без существенных затрат генерировать большие простые числа, уметь оперативно вычислять значения ключей К в и k в 11.3.2 Пример использования алгоритма RSA Зашифруем и расшифруем сообщение «САВ» по алгоритму RSA. Для простоты будут использованы маленькие числа. На практике применяются очень большие числа (см. следующий раздел). 1. Выберем Р = 3 и Q = 11. 2. Определим N = P∙Q = 3∙11 = 33. 3. Найдем φ(N) = (P-1)(Q-1) = (3-1)(11-1) = 20. Выбираем случайным образом значение числа k в . Это число должно быть взаимно простым с функцией Эйлера (т.е. у φ(N) = 20 и k в не должно быть общих делителей кроме 1). Пусть k в = 3. 4. Выберем число K B по следующей формуле: (k B ∙K B ) mod 20 = 1, т. е. произведение k B ∙K B при целочисленном делении на φ(N) = 20 должно в остатке давать 1. 131 Пусть K B = 7 т.к.: 7∙3=21 и (21 mod 20) = 1 21 20 20 1 1 5. Представим шифруемое сообщение как последовательность чисел в диапазоне от 0 до 32 (кончается на N-1). Буква А =1, В=2, С=3. 6. Зашифруем сообщение, используя открытый ключ (K B =7, N=33): C 1 = 3 7 mod 33 = 2187 mod 33 = 9; 2187 33 2178 66 9 C 2 = 1 7 mod 33 = 1 mod 33 = 1; 1 33 0 0 1 C 3 = 2 7 mod 33 = 128 mod 33 = 29; 128 33 99 3 29 Т.е. криптограмма представляет собой С = 09 01 29 7. Расшифруем эти данные, используя закрытый ключ (N=33, k в =3). M 1 =9 3 mod 33 =729 mod 33 = 3 (С); 729 33 726 22 3 M 2 =1 3 mod 33 =1 mod 33 = 1 (А); 1 33 0 0 1 M 3 =29 3 mod 33 = 24389 mod 33 = 2 (В); 24389 33 24387 739 2 Данные расшифрованы. 11.3.3 Безопасность и быстродействие криптосистемы RSA Безопасность алгоритма RSA базируется на трудности решения задачи факторизации больших чисел, являющихся произведениями двух больших 132 простых чисел. Действительно, криптостойкость алгоритма RSA определяется тем, что после формирования секретного ключа k в и открытого ключа К в «стираются» значения простых чисел Р и Q, и тогда исключительно трудно определить секретный ключ k в по открытому ключу К в , поскольку для этого необходимо решить задачу нахождения делителей Р и Q модуля N. Разложение величины N на простые множители Р и Q позволяет вычислить функцию φ(N) = (P-T) (Q-T) и затем определить секретное значение k B используя уравнение (K B ∙ k в ) mod ( φ(N) ) = 1. Другим возможным способом криптоанализа алгоритма RSA является непосредственное вычисление или подбор значения функции φ(N) = (P -T) (Q-T). Если установлено значение φ(N), то сомножители Р и Q вычисляются достаточно просто. В самом деле, пусть Зная φ(N), можно определить х и затем у; зная х и у, можно определить числа Ри Q из следующих соотношений: Однако эта атака не проще задачи факторизации модуля N. Задача факторизации является трудно разрешимой задачей для больших значений модуля N. Сначала авторы алгоритма RSA предлагали для вычисления модуля N выбирать простые числа Р и Q случайным образом, по 50 десятичных разрядов каждое. Считалось, что такие большие числа N очень трудно разложить на простые множители. Один из авторов алгоритма RSA, Р. Райвест, полагал, что разложение на простые множители числа из почти 130 десятичных цифр, приведенного в их публикации, потребует более 40 квадриллионов лет машинного времени. Однако этот прогноз не оправдался из-за сравнительно быстрого прогресса компьютеров и их вычислительной мощности, а также улучшения алгоритмов факторизации. Один из наиболее быстрых алгоритмов, известных в настоящее время, алгоритм NFS (Number Field Sieve) может выполнить факторизацию большого числа N (с числом десятичных разрядов больше 120) за число шагов, оцениваемых величиной В 1994 г. было факторизовано число со 129 десятичными цифрами. Это удалось осуществить математикам А. Ленстра и М. Манасси посредством организации распределенных вычислений на 1600 компьютерах, объединенных сетью, в течение восьми месяцев. По мнению А. Ленстра и М. Манасси, их работа компрометирует криптосистемы RSA и создает большую угрозу их дальнейшим применениям. Теперь разработчикам криптоалгоритмов с открытым ключом на базе RSA приходится избегать 133 применения чисел длиной менее 200 десятичных разрядов. Самые последние публикации предлагают применять для этого числа длиной не менее 250-300 десятичных разрядов. Оценка безопасных длин ключей асимметричных криптосистем на ближайшие 20 лет исходя из прогноза развития компьютеров и их вычислительной мощности, а также возможного совершенствования алгоритмов факторизации приведена в таблице 11.1 даны (для трех групп пользователей - индивидуальных пользователей, корпораций и государственных организаций), в соответствии с различием требований к их информационной безопасности. Конечно, данные оценки следует рассматривать как сугубо приблизительные, как возможную тенденцию изменений безопасных длин ключей асимметричных криптосистем со временем. Таблица 11.1 - Оценки длин ключей для асимметричных криптосистем, бит Год Отдельные пользователи Корпорации Государственные организации 1995 768 1280 1536 2000 1024 1280 1536 2005 1280 1536 2048 2010 1280 1536 2048 2015 1536 2048 2048 11.4 Аутентификация данных и электронная цифровая подпись При обмене электронными документами по сети связи существенно снижаются затраты на обработку и хранение документов, убыстряется их поиск. Но при этом возникает проблема аутентификации автора документа и самого документа, т.е. установления подлинности автора и отсутствия изменений в полученном документе. В обычной (бумажной) информатике эти проблемы решаются за счет того, что информация в документе и рукописная подпись автора жестко связаны с физическим носителем (бумагой). В электронных документах на машинных носителях такой связи нет. Целью аутентификации электронных документов является их защита от возможных видов злоумышленных действий, к которым относятся: - активный перехват - нарушитель, подключившийся к сети, перехватывает документы (файлы) и изменяет их; - маскарад - абонент С посылает документ абоненту В от имени абонента А; - ренегатство - абонент А заявляет, что не посылал сообщения абоненту В, хотя на самом деле послал; 134 - подмена - абонент В изменяет или формирует новый документ и заявляет, что получил его от абонента А; - повтор - абонент С повторяет ранее переданный документ, который абонент А посылал абоненту В. Эти виды злоумышленных действий могут нанести существенный ущерб банковским и коммерческим структурам, государственным предприятиям и организациям, частным лицам, применяющим в своей деятельности компьютерные информационные технологии. При обработке документов в электронной форме совершенно непригодны традиционные способы установления подлинности по рукописной подписи и оттиску печати на бумажном документе. Принципиально новым решением является электронная цифровая подпись (ЭЦП). Электронная цифровая подпись используется для аутентификации текстов, передаваемых по телекоммуникационным каналам. Функционально она аналогична обычной рукописной подписи и обладает ее основными достоинствами: 1. удостоверяет, что подписанный текст исходит от лица, поставившего подпись; 2. не дает самому этому лицу возможности отказаться от обязательств, связанных с подписанным текстом; 3. гарантирует целостность подписанного текста. Цифровая подпись представляет собой относительно небольшое количество дополнительной цифровой информации, передаваемой вместе с подписываемым текстом. Система ЭЦП включает две процедуры: 1. процедуру постановки подписи; 2. процедуру проверки подписи. В процедуре постановки подписи используется секретный ключ отправителя сообщения, в процедуре проверки подписи - открытый ключ отправителя. При формировании ЭЦП отправитель прежде всего вычисляет хэш- функцию h(М) подписываемого текста М. Вычисленное значение хэш- функции h(М) представляет собой один короткий блок информации т, характеризующий весь текст М в целом. Затем число m шифруется секретным ключом отправителя. Получаемая при этом пара чисел представляет собой ЭЦП для данного текста М. При проверке ЭЦП получатель сообщения снова вычисляет хэш- функцию m = h(M) принятого по каналу текста М, после чего при помощи открытого ключа отправителя проверяет, соответствует ли полученная подпись вычисленному значению m хэш-функции. 135 Принципиальным моментом в системе ЭЦП является невозможность подделки ЭЦП пользователя без знания его секретного ключа подписывания. В качестве подписываемого документа может быть использован любой файл. Подписанный файл создается из неподписанного путем добавления в него одной или более электронных подписей. Каждая подпись содержит следующую информацию: - дату подписи; - срок окончания действия ключа данной подписи; - информацию о лице, подписавшем файл (Ф.И.О.. должность. краткое наименование фирмы); - идентификатор подписавшего (имя открытого ключа); - собственно цифровую подпись. Технология применения системы ЭЦП предполагает наличие сети абонентов, посылающих друг другу подписанные электронные документы. Для каждого абонента генерируется пара ключей: секретный и открытый. Секретный ключ хранится абонентом в тайне и используется им для формирования ЭЦП. Открытый ключ известен всем другим пользователям и предназначен для проверки ЭЦП получателем подписанного электронного документа. Иначе говоря, открытый ключ является необходимым инструментом, позволяющим проверить подлинность электронного документа и автора подписи. Открытый ключ не позволяет вычислить секретный ключ. Для генерации пары ключей (секретного и открытого) в алгоритмах ЭЦП, как и в асимметричных системах шифрования, используются разные математические схемы, основанные на применении однонаправленных функций. Эти схемы разделяются на две группы. В основе такого разделения лежат известные сложные вычислительные задачи: - задача факторизации (разложения на множители) больших целых чисел; - задача дискретного логарифмирования. 11.5 Алгоритм цифровой подписи RSA Первой и наиболее известной во всем мире конкретной системой ЭЦП стала система RSA, математическая схема которой была разработана в 1977 г. в Массачуссетском технологическом институте США. Сначала необходимо вычислить пару ключей (секретный ключ и открытый ключ). Для этого отправитель (автор) электронных документов вычисляет два больших простых числа Р и Q, затем находит их произведение N = P∙Q и значение функции φ(N) = (P-1)(Q-1). 136 Далее отправитель вычисляет число Е из условий: и число D из условий: Пара чисел (E, N) является открытым ключом. Эту пару чисел автор передает партнерам по переписке для проверки его цифровых подписей. Число D сохраняется автором как секретный ключ для подписывания. Обобщенная схема формирования и проверки цифровой подписи RSA показана на рис. 11.2. Рис. 11.2 - Обобщенная схема формирования и проверки ЭЦП RSA Допустим, что отправитель хочет подписать сообщение М перед его отправкой. Сначала сообщение М (блок информации, файл, таблица) сжимают с помощью хэш-функции h(∙) в целое число m: m = h(М). Затем вычисляют цифровую подпись S под электронным документом М, используя хэш-значение m и секретный ключ D: S = m D mod N. Пара (M, S) передается партнеру-получателю как электронный документ М, подписанный цифровой подписью S, причем подпись S сформирована обладателем секретного ключа D, После приема пары (М, S) получатель вычисляет хэш-значение сообщения М двумя разными способами. Прежде всего он восстанавливает 137 хэш-значение m', применяя криптографическое преобразование подписи S с использованием открытого ключа Е: m'=S E mod N. Кроме того, он находит результат хэширования принятого сообщения М с помощью такой же хэш-функции h(∙): m = h(M). Если соблюдается равенство вычисленных значений, т.е. SE mod N = h(M), то получатель признает пару (М, S) подлинной. Доказано, что только обладатель секретного ключа D может сформировать цифровую подпись S по документу М, а определить секретное число D по открытому числу Е не легче, чем разложить модуль N на множители. Кроме того, можно строго математически доказать, что результат проверки цифровой подписи S будет положительным только в том случае, если при вычислении S был использован секретный ключ D, соответствующий открытому ключу Е. Поэтому открытый ключ Е иногда называют «идентификатором» подписавшего. Недостатки алгоритма цифровой подписи RSA. - При вычислении модуля N, ключей Е и D для системы цифровой подписи RSA необходимо проверять большое количество дополнительных условий, что сделать практически трудно. Невыполнение любого из этих условий делает возможным фальсификацию цифровой подписи со стороны того, кто обнаружит такое невыполнение. При подписании важных документов нельзя допускать такую возможность даже теоретически. - Для обеспечения криптостойкости цифровой подписи RSA по отношению к попыткам фальсификации на уровне, например, национального стандарта США на шифрование информации (алгоритм DES), т.е. 10 , необходимо использовать при вычислениях N, D и Е целые числа не менее 2 512 (или около 10 154 ) каждое, что требует больших вычислительных затрат, превышающих на 20...30% вычислительные затраты других алгоритмов цифровой подписи при сохранении того же уровня криптостойкости. - Цифровая подпись RSA уязвима к так называемой мультипликативной атаке. Иначе говоря, алгоритм цифровой подписи RSA позволяет злоумышленнику без знания секретного ключа D сформировать подписи под теми документами, у которых результат хэширования можно вычислить как произведение результатов хэширования уже подписанных документов. 138 12. СИММЕТРИЧНЫЕ КРИПТОСИСТЕМЫ 12.1 Понятие о симметричной криптосистеме Большинство средств защиты информации базируется на использовании криптографических шифров и процедур шифрования – расшифрования осуществляющихся в рамках некоторой криптосистемы. Характерной особенностью симметричной криптосистемы является применение одного и того же секретного ключа как при шифровании, так и при расшифровании сообщений. Как открытый текст, так и шифртекст образуются из букв, входящих в конечное множество символов, называемых алфавитом. Примерами алфавитов являются конечное множество всех заглавных букв, конечное множество всех заглавных и строчных букв и цифр и т. п. В общем виде некоторый алфавит можно представить так: 0 1 1 , ,..., m a a a Объединяя по определенному правилу буквы из алфавита можно создать новые алфавиты: - алфавит 2 , содержащий m 2 биграмм 0 0 0 1 1 1 , , ...., m m a a a a a a - алфавит 3 , содержащий m 3 триграмм 0 0 0 0 0 1 1 1 1 , , ...., m m m a a a a a a a a a В общем случае, объединяя по n букв, получаем алфавит n содержащий m n n-грамм. Например, английский алфавит = {ABCDEFGH ... WXYZ} объемом m=26 букв позволяет сгенерировать посредством операции конкатенации алфавит из 26 2 =676 биграмм: AA, AB, … ,XZ, ZZ, алфавит из 26 3 =17576 триграмм: AAA, AAB, … ,XZZ, ZZZ и т.д. При выполнении криптографических преобразований полезно заменить буквы алфавита целыми числами 0, 1, 2, 3,... . Это позволяет упростить выполнение необходимых алгебраических манипуляций. Например, можно установить взаимно однозначное соответствие между русским алфавитом = {АБВГД ... ЮЯ} и множеством целых 32 {0,1, 2,3,...,31}; Z между английским алфавитом { } англ ABCDEF YZ и множеством целых 26 {0,1, 2, 3,..., 25} Z (см. табл. 12.1 и 12.2). В дальнейшем будет обычно использоваться алфавит 26 {0,1, 2, 3,..., 25} Z содержащий m «букв» (в виде чисел). 139 Замена букв традиционного алфавита числами позволяет более четко сформулировать основные концепции и приемы криптографических преобразований. В то же время в большинстве иллюстраций будет использоваться алфавит естественного языка. Таблица 12.1 - Соответствие между русским алфавитом и множеством целых 32 {0,1,2,3,...,31} Z Таблица 12.2 - Соответствие между английским алфавитом и множеством целых 26 {0,1, 2, 3,..., 25} Z Текст с n буквами из алфавита Z m можно рассматривать как n-грамму 0 1 2 1 ( , , ,..., ), n x x x x x где i m x Z 0 i n , для некоторого целого n = 1, 2, 3, … .Через , m n Z будем обозначать множество n-грамм, образованных из букв множества m Z Криптографическое преобразование Е представляет собой совокупность преобразований ( ) { :1 } n E E п ( ) , , : n m n m n E Z Z 140 Преобразование E (n) определяет, как каждая n-грамма открытого текста , m n x Z заменяется n-граммой шифртекста y , т. е. ( ) ( ) n y E x , причем , , m n x y Z , при этом обязательным является требование взаимной однозначности преобразования E (n) на множестве , m n Z Криптографическая система может трактоваться как семейство криптографических преобразований { : }, k E E K K помеченных параметром К, называемым ключом. Множество значений ключа образует ключевое пространство K Далее рассматриваются традиционные (классические) методы шифрования, отличающиеся симметричной функцией шифрования. К ним относятся шифры перестановки, шифры простой и сложной замены, а также некоторые их модификации и комбинации. Следует отметить, что комбинации шифров перестановок и шифров замены образуют все многообразие применяемых на практике симметричных шифров. 12.2 Шифры перестановки При шифровании перестановкой символы шифруемого текста переставляются по определенному правилу в пределах блока этого текста. Шифры перестановки являются самыми простыми и, вероятно, самыми древними шифрами. 12.2.1 Шифрующие таблицы С начала эпохи Возрождения (конец XIV столетия) начала возрождаться и криптография. Наряду с традиционными применениями криптографии в политике, дипломатии и военном деле появляются и другие задачи - защита интеллектуальной собственности от преследований инквизиции или заимствований злоумышленников. В разработанных шифрах перестановки того времени применяются шифрующие таблицы, которые в сущности задают правила перестановки букв в сообщении. В качестве ключа в шифрующих таблицах используются: 1. размер таблицы; 2. слово или фраза, задающие перестановку; 3. особенности структуры таблицы. 141 Одним из самых примитивных табличных шифров перестановки является простая перестановка, для которой ключом служит размер таблицы. Этот метод шифрования сходен с шифром скитала. Например, сообщение ТЕРМИНАТОР ПРИБЫВАЕТ СЕДЬМОГО В ПОЛНОЧЬ записывается в таблицу поочередно по столбцам. Результат заполнения таблицы из 5 строк и 7 столбцов показан на рисунке 12.1. Т Н П В Е Г Л Е А Р А Д О Н Р Т И Е Ь В О М О Б Т М П Ч И Р Ы С О О Ь Рис. 12.1 - Заполнение таблицы из 5 строк и 7 столбцов После заполнения таблицы текстом сообщения по столбцам для формирования шифртекста считывают содержимое таблицы по строкам. Если шифртекст записывать группами по пять букв, получается такое шифрованное сообщение: ТНПВЕ ГЛЕАР АДОНР ТИЕЬВ ОМОБТ МПЧИР ЫСООЬ Естественно, отправитель и получатель сообщения должны заранее условиться об общем ключе в виде размера таблицы. Следует заметить, что объединение букв шифртекста в 5-буквенные группы не входит в ключ шифра и осуществляется для удобства записи несмыслового текста. При расшифровании действия выполняют в обратном порядке. Несколько большей стойкостью к раскрытию обладает метод шифрования, называемый одиночной перестановкой по ключу. Этот метод отличается от предыдущего тем, что столбцы таблицы переставляются по ключевому слову, фразе или набору чисел длиной в строку таблицы. Применим в качестве ключа, например, слово ПЕЛИКАН, а текст сообщения возьмем из предыдущего примера. На рисунке 12.2 показаны две таблицы, заполненные текстом сообщения и ключевым словом, при этом левая таблица соответствует заполнению до перестановки, а правая таблица-заполнению после перестановки. В верхней строке левой таблицы записан ключ, а номера под буквами ключа определены в соответствии с естественным порядком соответствующих букв ключа в алфавите. Если бы в ключе встретились одинаковые буквы, они бы были понумерованы слева направо. В правой таблице столбцы переставлены в соответствии с упорядоченными номерами букв ключа. 142 Рис. 12.2 – Шифрование с ключом При считывании содержимого правой таблицы по строкам и записи шифртекста группами по пять букв получим шифрованное сообщение: ГНВЕП ЛТООА ДРНЕВ ТЕЬИО РПОТМ БЧМОР СОЫЬИ Для обеспечения дополнительной скрытности можно повторно зашифровать сообщение, которое уже прошло шифрование. Такой метод шифрования называется двойной перестановкой. В случае двойной перестановки столбцов и строк таблицы перестановки определяются отдельно для столбцов и отдельно для строк. Сначала в таблицу записывается текст сообщения, а потом поочередно переставляются столбцы, а затем строки. При расшифровании порядок перестановок должен быть обратным. Пример выполнения шифрования методом двойной перестановки показан на рисунке 12.3. Рис. 12.3 - Пример выполнения шифрования методом двойной перестановки Если считывать шифртекст из правой таблицы построчно блоками по четыре буквы, то получится следующее: ТЮАЕ ООГМ РЛИП ОЬСВ Ключом к шифру двойной перестановки служит последовательность номеров столбцов и номеров строк исходной таблицы (в нашем примере последовательности 4132 и 3142 соответственно). 143 Число вариантов двойной перестановки быстро возрастает при увеличении размера таблицы: - для таблицы 3x3 - 36 вариантов; - для таблицы 4x4 - 576 вариантов; - для таблицы 5x5 - 14400 вариантов. Однако двойная перестановка не отличается высокой стойкостью и сравнительно просто "взламывается" при любом размере таблицы шифрования. 12.2.2 Система шифрования Цезаря Шифр Цезаря является частным случаем шифра простой замены (одноалфавитной подстановки). Свое название этот шифр получил по имени римского императора Гая Юлия Цезаря, который использовал этот шифр при переписке с Цицероном (около 50 г. до н.э.). При шифровании исходного текста каждая буква заменялась на другую букву того же алфавита по следующему правилу. Заменяющая буква определялась путем смещения по алфавиту от исходной буквы на К букв. При достижении конца алфавита выполнялся циклический переход к его началу. Цезарь использовал шифр замены при смещении К=3. Такой шифр замены можно задать таблицей подстановок, содержащей соответствующие пары букв открытого текста и шифртекста. Совокупность возможных подстановок для К= 3 показана на рисунке 12.4. Рис. 12.4 - Совокупность возможных подстановок для К= 3 Например, послание Цезаря: VENI VIDI VICI (в переводе на русский означает "Пришел, Увидел, Победил"), направленное его другу Аминтию после победы над понтийским царем Фарнаком, сыном Митридата, выглядело бы в зашифрованном виде так: YHQL YLGL YLFL Достоинством системы шифрования Цезаря является простота шифрования и расшифрования. 144 К недостаткам системы Цезаря следует отнести следующие: - подстановки, выполняемые в соответствии с системой Цезаря, не маскируют частот появления различных букв исходного открытого текста; - сохраняется алфавитный порядок в последовательности заменяющих букв; при изменении значения К изменяются только начальные позиции такой последовательности; - число возможных ключей К мало; - шифр Цезаря легко вскрывается на основе анализа частот появления букв в шифртексте. Криптоаналитическая атака против системы одноалфавитной замены начинается с подсчета частот появления символов: определяется число появлений каждой буквы в шифртексте. Затем полученное распределение частот букв в шифртексте сравнивается с распределением частот букв в алфавите исходных сообщений, например в английском. Буква с наивысшей частотой появления в шифртексте заменяется на букву с наивысшей частотой появления в английском языке и т.д. Вероятность успешного вскрытия системы шифрования повышается с увеличением длины шифртекста. 12.2.3 Аффинная система подстановок Цезаря В данном преобразовании буква, соответствующая числу t, заменяется на букву, соответствующую числовому значению (at +b) по модулю m. Следует заметить, что преобразование E a,b (t) является взаимно однозначным отображением на множестве m Z только в том случае, если наибольший общий делитель чисел а и т, обозначаемый как НОД (а, m), равен единице, т.е. а и m должны быть взаимно простыми числами. Например, пусть m = 26, а = 3, b = 5. Тогда, очевидно, НОД (3, 26) = 1, и мы получаем следующее соответствие между числовыми кодами букв: Преобразуя числа в буквы английского языка, получаем следующее соответствие для букв открытого текста и шифртекста: Исходное сообщение НОРЕ преобразуется в шифртекст AVYR Достоинством аффинной системы является удобное управление ключами - ключи шифрования и расшифрования представляются в компактной форме в виде пары чисел (а, b). Недостатки аффинной системы аналогичны недостаткам системы шифрования Цезаря. 145 12.2.4 Система Цезаря с ключевым словом Система шифрования Цезаря с ключевым словом является одноалфавитной системой подстановки. Особенностью этой системы является использование ключевого слова для смещения и изменения порядка символов в алфавите подстановки. Выберем некоторое число k, 0 Ключевое слово записывается под буквами алфавита, начиная с буквы, числовой код которой совпадает с выбранным числом k: Оставшиеся буквы алфавита подстановки записываются после ключевого слова в алфавитном порядке: Теперь мы имеем подстановку для каждой буквы произвольного сообщения. Исходное сообщение SEND MORE MONEY, шифруется как HZBY TCGZ TCBZS. Следует отметить, что требование о различии всех букв ключевого слова не обязательно. Можно просто записать ключевое слово (или фразу) без повторения одинаковых букв. Например, ключевая фраза КАК ДЫМ ОТЕЧЕСТВА НАМ СЛАДОК И ПРИЯТЕН и число k = 3 порождают следующую таблицу подстановок: Несомненным достоинством системы Цезаря с ключевым словом является то, что количество возможных ключевых слов практически неисчерпаемо. Недостатком этой системы является возможность взлома шифртекста на основе анализа частот появления букв. 146 12.3 Шифры сложной замены Шифры сложной замены называют многоалфавитными, так как для шифрования каждого символа исходного сообщения применяют свой шифр простой замены. Многоалфавитная подстановка последовательно и циклически меняет используемые алфавиты. При r-алфавитной подстановке символ x o исходного сообщения заменяется символом y o из алфавита B o , символ x 1 - символом y 1 из алфавита B 1 , и так далее, символ x r-1 заменяется символом y r-1 из алфавита B r-1 , символ x r заменяется символом y r из алфавита B 0 и т.д. Общая схема многоалфавитной подстановки для случая r = 4 показана на рисунке 12.5. Рис. 12.5 - Схема r-алфавитной подстановки для случая r = 4 Эффект использования многоалфавитной подстановки заключается в том, что обеспечивается маскировка естественной статистики исходного языка, так как конкретный символ из исходного алфавита А может быть преобразован в несколько различных символов шифровальных алфавитов B j Степень обеспечиваемой защиты теоретически пропорциональна длине периода r в последовательности используемых алфавитов B j Многоалфавитные шифры замены предложил и ввел в практику. криптографии Леон Батист Альберти, который также был известным архитектором и теоретиком искусства. Его книга "Трактат о шифре", написанная в 1566 г., представляла собой первый в Европе научный труд по криптологии. Кроме шифра многоалфавитной замены, Альберти также подробно описал устройства из вращающихся колес для его реализации. Криптологи всего мира почитают Л. Альберти основоположником криптологии. 12.4 Одноразовая система шифрования Почти все применяемые на практике шифры характеризуются как условно надежные, поскольку они могут быть в принципе раскрыты при наличии неограниченных вычислительных возможностей. Абсолютно надежные шифры нельзя разрушить даже при использовании неограниченных вычислительных возможностей. Существует единственный такой шифр, применяемый на практике, - одноразовая система шифрования. Характерной особенностью одноразовой системы шифрования является одноразовое использование ключевой последовательности. 147 Одноразовая система шифрует исходный открытый текст 0 1 1 ( , ,..., ) n X x x x в шифртекст 0 1 1 ( , ,..., ) n Y y y y посредством подстановки Цезаря ( ) mod , 0 , i i i Y X K m i n где K i - i-й элемент случайной ключевой последовательности. Ключевое пространство K одноразовой системы представляет собой набор дискретных случайных величин из m Z и содержит m n значений. Процедура расшифрования описывается соотношением ( ) mod , i i i X Y K m где K i - i-й элемент той же самой случайной ключевой последовательности. Одноразовая система изобретена в 1917 г. американцами Дж. Моборном и Г. Вернамом. Для реализации этой системы подстановки иногда используют одноразовый блокнот. Этот блокнот составлен из отрывных страниц, на каждой из которых напечатана таблица со случайными числами (ключами) K j . Блокнот выполняется в двух экземплярах: один используется отправителем, а другой - получателем. Для каждого символа X j сообщения используется свой ключ K j из таблицы только один раз. После того как таблица использована, она должна быть удалена из блокнота и уничтожена. Шифрование нового сообщения начинается с новой страницы. Этот шифр абсолютно надежен, если набор ключей K i действительно случаен и непредсказуем. Если криптоаналитик попытается использовать для заданного шифртекста все возможные наборы ключей и восстановить все возможные варианты исходного текста, то они все окажутся равновероятными. Не существует способа выбрать исходный текст, который был действительно послан. Теоретически доказано, что одноразовые системы являются не-раскрываемыми системами, поскольку их шифртекст не содержит достаточной информации для восстановления открытого текста. Казалось бы, что благодаря данному достоинству одноразовые системы следует применять во всех случаях, требующих абсолютной информационной безопасности. Однако возможности Применения одноразовой системы ограничены чисто практическими аспектами. Существенным моментом является требование одноразового использования случайной ключевой последовательности. Ключевая последовательность с длиной, не меньшей длины сообщения, должна передаваться получателю сообщения заранее или отдельно по некоторому секретному каналу. Это требование не будет слишком обременительным для передачи действительно важных одноразовых сообщений, например, по горячей линии Вашингтон- Москва. Однако такое требование практически неосуществимо для 148 современных систем обработки информации, где требуется шифровать многие миллионы символов. 12.5 Шифрование методом гаммирования Под гаммированием понимают процесс наложения по определенному, закону гаммы шифра на открытые данные. Гамма шифр - это псевдослучайная последовательность, выработанная по заданному алгоритму для зашифрования открытых данных и расшифрования зашифрованных данных. Процесс зашифрования заключается в генерации гаммы шифра и наложении полученной гаммы на исходный открытый текст обратимым образом, например с использованием операции сложения по модулю 2. Следует отметить, что перед зашифрованием открытые данные разбивают на блоки T 0 (i) одинаковой длины, обычно по 64 бита. Гамма шифр вырабатывается в виде последовательности блоков Г ш (i) аналогичной длины. Уравнение зашифрования можно записать в виде ( ) ( ) ( ) 0 , 1... , i i i ш ш T Г T i M где T ш (i) - i-й блок шифртекста; Г ш (i) - i-й блок гаммы шифра; T 0 (i) - i-й блок открытого текста; М - количество блоков открытого текста. Процесс расшифрования сводится к повторной генерации Гаммы шифра и наложению этой гаммы на зашифрованные данные. Уравнение расшифрования имеет вид ( ) ( ) ( ) 0 i i i ш ш T Г T Получаемый этим методом шифр-текст достаточно труден для раскрытия, поскольку теперь ключ является переменным. По сути дела гамма шифра должна изменяться случайным образом для каждого шифруемого блока. Если период гаммы превышает длину всего шифруемого текста и злоумышленнику неизвестна никакая часть исходного текста, то такой шифр можно раскрыть только прямым перебором всех вариантов ключа. В этом случае крипто-стойкость шифра определяется длиной ключа. 12.6 Стандарт шифрования данных DES Стандарт шифрования данных DES (Data Encryption Standard) опубликован в 1977 г. Национальным бюро стандартов США. Стандарт DES предназначен для защиты от несанкционированного доступа к важной, но несекретной информации в государственных и коммерческих организациях США. Алгоритм, положенный в основу стандарта, распространялся 149 достаточно быстро, и уже в 1980 г. был одобрен Национальным институтом стандартов и технологий США (НИСТ). С этого момента DES превращается в стандарт не только по названию (Data Encryption Standard), но и фактически. Появляются программное обеспечение и специализированные микро-ЭВМ, предназначенные для шифрования и расшифрования информации в сетях передачи данных. К настоящему времени DES является наиболее распространенным алгоритмом, используемым в системах защиты коммерческой информации. Более того, реализация алгоритма DES в таких системах становится признаком хорошего тона. Основные достоинства алгоритма DES: - используется только один ключ длиной 56 бит; - зашифровав сообщение с помощью одного пакета программ, для расшифровки можно использовать любой другой пакет программ. соответствующий стандарту DES; - относительная простота алгоритма обеспечивает высокую скорость обработки; - достаточно высокая стойкость алгоритма. Алгоритм DES использует комбинацию подстановок и перестановок. DES осуществляет шифрование 64-битовых блоков данных с помощью 64- битового ключа, в котором значащими являются 56 бит (остальные 8 бит - проверочные биты для контроля на четность). Дешифрование в DES является операцией, обратной Шифрованию, и выполняется путем повторения операций шифрования в обратной последовательности. Обобщенная схема процесса шифрования в алгоритме DES показана на рисунке 12.6 в. Процесс шифрования заключается в начальной перестановке битов 64- битового блока, шестнадцати циклах шифрования и, наконец, в конечной перестановке битов (рисунок 15.6, в). Следует сразу отметить, что все приводимые таблицы (на рисунке 15.6, а,б) являются стандартными и должны включаться в реализацию алгоритма DES в неизменном виде. Все перестановки и коды в таблицах подобраны разработчиками таким образом, чтобы максимально затруднить процесс расшифровки путем подбора ключа. При описании алгоритма DES (рисунок 15.6, в) применены следующие обозначения: 1. L и R - последовательности битов (левая (left) и правая (right)); 2. LR - конкатенация последовательностей L и R, т.е. такая последовательность битов, длина которой равна сумме длин L и R; в последовательности LR биты последовательности R следуют за битами последовательности L; 3. -операция побитового сложения по модулю 2. 150 а. б. в Рисунок 12.6 – Таблицы перестановки и алгоритм DES Пусть из файла исходного текста считан очередной 64-битовый (8- байтовый) блок Т. Этот блок Т преобразуется с помощью матрицы начальной перестановки IP (рисунок 12.6, а). Биты входного блока Т (64 бита) переставляются в соответствии с матрицей IP: бит 58 входного блока Т становится битом 1, бит 50-битом 2 и т.д. Эту перестановку можно описать выражением T o = IP(T). Полученная последовательность битов T o разделяется на две последовательности: L 0 - левые или старшие биты, R 0 - правые или младшие биты, каждая из которых содержит 32 бита. Затем выполняется итеративный процесс шифрования, состоящий из 16 шагов (циклов). Пусть Т i - результат i-й итерации: i i i T L R где 1 2 32 i L t t t (первые 32 бита); 33 34 64 i R t t t (последние 32 бита). 151 Тогда результат i-й итерации описывается следующими формулами: 1 1 1 , 1, 2,...,16; ( , ), 1, 2,...,16. i i i i i i L R i R L f R K i Функция fназывается функцией шифрования. Ее аргументами являются последовательность R i-1 , получаемая на предыдущем шаге итерации, и 48-битовый ключ K i , который является результатом преобразования 64-битового ключа шифра К. (Подробнее функция шифрования f и алгоритм получения ключа K i описаны ниже.) На последнем шаге итерации получают последовательности R 16 и L 16 (без перестановки местами), которые конкатенируются в 64-битовую последовательность R 16 L 16 По окончании шифрования осуществляется восстановление позиций битов с помощью матрицы обратной перестановки IP -1 (рисунок 12.6, б). Процесс расшифрования данных является инверсным по отношению к процессу шифрования. Все действия должны быть выполнены в обратном порядке. Это означает, что расшифровываемые данные сначала переставляются в соответствии с матрицей IP -1 , а затем над последовательностью битов R 16 L 16 выполняются те же действия, что и в процессе шифрования, но в обратном порядке: 1 1 , 1, 2,...,16; ( , ), 1, 2,...,16. i i i i i i R L i L R f L K i В настоящее время блочный алгоритм DES считается относительно безопасным алгоритмом шифрования. Он подвергался тщательному криптоанализу в течение 20 лет, и самым практичным способом его взламывания является метод перебора всех возможных вариантов ключа. Ключ DES имеет длину 56 бит, поэтому существует 2 55 возможных вариантов такого ключа. Если предположить, что суперкомпьютер может испытать миллион вариантов ключа за секунду, то потребуется 2285 лет для нахождения правильного ключа. Если бы ключ имел длину 128 бит, то потребовалось бы 10 25 лет (для сравнения: возраст Вселенной около 10 10 лет). |