Криптографические системы

. Защиты данных

1.КРИПТОГРАФИЧЕСКИЕ СИСТЕМЫ, ОСНОВАННЫЕ НА МЕТОДЕ ПОДСТАНОВКИ

Криптографические системы, основанные на методе подстановки, разделяются на четыре основных класса:

1) monoalphabetic;

2) homophonic;

3) polyalphabetic;

4) polygram.

В системах класса monoalphabetic символ исходного текста заменяется другим символом таким образом, что между ними существует однозначное соответствие. То есть каждый символ исходного текста однозначно заменяется его подстановкой. Криптографическим ключем такой системы является таблица соответствия исходного алфавита алфавиту подстановки. Например, для английского алфавита существует 26! = 4*1026 различных криптографических систем первого класса. Наиболее простые системы данного класса предполагают аналитическое описание подстановок. Так, простейший шифратор, основанный на принципе подстановки, сдвигает каждую букву английского алфавита на k позиций, где k является ключом шифра. В так называемом алгоритме Цезаря i-я буква алфавита заменяется (i+k)-й буквой по модулю 26. Юлий Цезарь использовал подобную систему для k=3. Аналитически криптосистема Цезаря описывается выражением

Ek(i) = (i+k) mod 26. (1.1)

Например, в соответствии с приведенным выражением буква A исходного английского алфавита, имеющая номер i=0, заменяется буквой D, имеющей номер (i+k) mod 26 = (0+3) mod 26 = 3, а буква z (i=25) заменяется буквой C, имеющей номер (i+k) mod 26 = (25+3) mod 26 = 2. Следующий пример иллюстрирует алгоритм шифрования Цезаря:

Исходный текст :CRYPTOGRAPHYANDDATASECURITY.

Шифротекст :FUBSWRJUDSKBDQSGDWDVHFXULWB.

Алгоритм дешифрования имеет вид

Dk(i) = (i+26-k) mod 26. (1.2)

Существуют более сложные методы подстановки. Шифраторы, основанные на умножении номера каждого символа исходного текста на значение ключа k, описываются следующим отношением:

Ek(i) = (i*k) mod n, (1.3)

где i - номер символа исходного текста, n - количество символов в исходном алфавите (n=26 для английского алфавита и n=256 для ASCII-кодов), k - ключ, n и k должны быть взаимно простыми.

Шифраторы, основанные на сдвиге и умножении, описываются выражением

Ek(i) = (i*k1+k0) mod n. (1.4)

Любой шифратор класса monoalphabetic может быть представлен в виде полиномиального преобразования порядка t:

Ek(i) = (k0 + k1*i + k2*i2 +...+ kt-1*it-1 + kt*it) mod n. (1.5)

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

В криптографических системах класса homophonic имеется несколько вариантов замены исходного символа. Например, буква A может быть заменена цифрами 24, 35, 37, а буква B - цифрами 41, 17, 76. Тогда слово ABBA может быть зашифровано как (37, 17, 76, 24), или (35, 41, 76, 37) и т. д. Подобные системы характеризуются значительно большей криптографической стойкостью, чем системы класса homophonic.

Криптографические системы класса polyalphabetic основаны на использовании нескольких различных ключей . Большинство шифраторов подобного типа являются периодическими с периодом P. Исходный текст вида

X = x1 x2 x3 x4 ... xp xp+1 ... x2p ...

шифруется с помощью ключей k1, k2, ..., kp:

Ek(X)= Ek1(x1) Ek2(x2) ... Ekp(xp) Ek1(xp+1) ... Ekp(x2p) (1.6)

Для p=1 будем иметь шифр класса monoalphabetic.

Один из таких алгоритмов был предложен в XVI веке французом Вигеном (Vigenere).

В данном случае ключ K представляется последовательностью

K = k1 k2 ... kp,

где ki (1 <= i <= p) представляет собой число сдвигов в исходном алфавите.

Символы исходного текста шифруются по формуле

Ek(i)=(i+kj) mod n, (1.7)

где i -номер символа исходного текста, Kj - ключ, jÎ {1, ..., n}.

Пусть ключем является слово BAD. Тогда слово CRYPTOGRAPHY будет зашифровано следующим образом:

i= CRY PTO GRA PHY,

K= BAD BAD BAD BAD,

Ek(i)=DRB QTR HRD QHB.

Криптосистемы третьего класса, основанные на полиалфавитной подстановке, широко использовались и используются на практике. На их основе разработано целое семейство роторных шифраторов, которые широко применялись во время второй мировой войны и в послевоенное время. Среди них можно выделить машину Хагелина M-209 (США), немецкую шифровальную машина “Энигма”, японский “Пурпурный код”.

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

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

A 0.0804 H 0.0549 O 0.0760 U 0.0271

B 0.0154 I 0.0726 P 0.0200 V 0.0099

C 0.0306 J 0.0016 Q 0.0011 W 0.0192

D 0.0399 K 0.0067 R 0.0612 X 0.0019

E 0.1251 L 0.0414 S 0.0654 Y 0.0173

F 0.0230 M 0.0253 T 0.0925 Z 0.0009

G 0.0196 N 0.0709

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

2.ПОТОКОВЫЕ КРИПТОСИСТЕМЫ

Синхронные потоковые шифраторы формируют ключ в виде потока (последовательности) символов K=k1k2... , который несложным образом комбинируется с последовательностью символов исходного текста M=m1m2... . Алгоритм формирования К должен быть детерминированным и воспроизводимым, а сама последовательность - случайной или псевдослучайной.

I0- начальное состояние генераторовключа. Оба генератора должны иметь одинаковое начальное состояние и функционировать синхронно.

Каждый символ шифротекста Ci является функцией от соответствующих символов исходного текста и ключа:

Ci = Eki(mi) = mi Å ki.

При дешифрации выполняется обратное преобразование D:

Dki(ci) = ci Å ki = ( mi Å ki ) Å ki = mi. mi , ki ,ci Криптографические системы{0,1}.

 

Генераторы M-последовательностей.

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

ai =Криптографические системыÅ ak ai-k, k=0,1,2,... , (2.1)

где k - номер такта; akКриптографические системыКриптографические системыКриптографические системы{0,1} - биты формируемой последовательности; ai Криптографические системы {0,1} - постоянные коэффициенты; Криптографические системыÅ - операция суммирования по модулю 2. Генератор, описываемый отношением (2.1), показан на рис. 2.1.

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

g(x) = 1 Å a1 x Å a2 x2 Å ...Å am-1 xm-1 Å am xm.

При соответствующем выборе коэффициентов генерируемая последовательность { ai } будет иметь максимально возможный период, равный 2m-1, где m - разрядность сдвигового регистра и одновременно старшая степень порождающего полинома. Последовательность максимально возможного периода называется M-последовательностью. Основная задача синтеза генератора рассматриваемого типа - нахождение характеристического полинома, формирующего М-последовательность.

Полиномы, формирующие последовательность максимального периода, называются примитивными. С ростом m их количество становится очень большим. Среди множества примитивных полиномов степени m можно найти полиномы с наименьшим числом единичных коэффициентов ai. Генераторы, построенные на их основе, имеют наиболее простую техническую реализацию. В табл. 2.1 приведен перечень полиномов с минимальным количеством ненулевых коэффициентов для значений m <=16.

Схема четырехразрядного ГК, описываемого примитивным полиномом g(x)=1Å x3 Å x4, приведена на рис. 2.2; его работа показана в табл. 2.2.

Для формирования M-последовательности наряду с примитивным полиномом g(x) может использоваться и обратный ему полином g-1(x)=xmg(x-1). Полученная в этом случае последовательность максимальной длины будет инверсной по отношению к последовательности, формируемой g(x). Например, для полинома g(x)=1Å x3Å x4 обратным полиномом будет g-1(x) = x4(1Å x-3Å x-4 )=1 Å x Å x4 .

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

Состояние разрядов регистра на каждом такте можно представить в виде m-мерных векторов A(k)=a1(k)a2(k)a3(k)...am(k), где k=0,1,2,... - номер такта, ai(k) - состояние i-го разряда, i=1,m,

Последовательное применение соотношений (1) или (2) для s = 0 позволяет формировать соответственно одно- или многоразрядные псевдослучайные последовательности, которые характеризуется рядом статических свойств.

Рассмотрим наиболее важные свойства М-последовательностей.

1. Период последовательности, описываемой выражением (1), определяется старшей степенью порождающего полинома g(x) и равен L= 2m -1.

2. Для заданного полинома g(x) существует L различных M-последовательностей, отличающихся фазовым сдвигом. Так, полиному g(x)=1Å x3Å x4 соответствует 15 M-последовательностей.

3. Количество единичных и нулевых символов ak, k=0,1,..., L-1, M-последовательности соответственно равно 2m-1 и 2m-1 -1. Вероятностная оценка частоты их появления определяется следующими выражениями:

p(ak=1)=2m-1 /(2m-1)=1/2 + 1/(2m+1-2),

p(ak=0)=(2m-1-1)/(2m-1) = 1/2-(2m+1 -2)

и при увеличении m достигает значений, сколь угодно близких к 1/2.

4. Вероятности появления серий из r, r Криптографические системы {1,2,...,m-1}, одинаковых символов ( нулей или единиц ) в M-последовательности максимально близки к соответствующим вероятностям для случайной последовательности.

5. Для любого значения s ( 1Криптографические системыs<L ) существует такое r Криптографические системы s ( 1Криптографические системыr<L), что {ak} + {ak-s}={ak-r}. Данное свойство обычно называют свойством сдвига и сложения.

Использование линейных сдвиговых регистров для создания криптосистем предполагает их уязвимость, если взломщик обладает парой: исходный текст - шифротекст длиной не менее 2m бит. Действительно, имея исходный текст M=(m1,m2,...,m2m) и соответствующий шифротекст C=(c1,c2,...,c2m), мы можем получить К=MÅ C=(m1Å c1,m2Å c2,...,m2mÅ c2m)=(k1,k2,k3,...,k2m). Тогда задача взлома криптосистемы при известном начальном состоянии сводится к решению системы из m линейных уравнений с m неизвестными, где неизвестными являются коэффициенты порождающего полинома.

Данная система имеет вид

Криптографические системы1k1 Å Криптографические системы2k2Å Криптографические системы3k3 Å ... Å Криптографические системыmkm =km+1

Криптографические системы1k2Å Криптографические системы2k3Å Криптографические системы3k4 Å ... Å Криптографические системыmkm+1 =km+2

Криптографические системы1k3 Å Криптографические системы2k4Å Криптографические системы3k5 Å ... Å Криптографические системыmkm+2 =km+3

.... ....

Криптографические системы1kmÅ Криптографические системы2km+1Å Криптографические системы3km+2 Å ... Å Криптографические системыmkm+m-1 =k2m .

3. КРИПТОГРАФИЧЕСКИЕ СИСТЕМЫ С ОТКРЫТЫМ КЛЮЧОМ

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

В настоящее время лучшим криптографическим алгоритмом с открытым ключем считается RSA (по имени создателей: Rivest, Shamir, Adelman). Перед изложением метода RSA определим некоторые термины.

Под простым числом будем понимать такое число, которое делится только на 1 и на само себя.

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

Под результатом операции i mod j будем понимать остаток от целочисленного деления i на j.

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

1. Случайным образом выбираются два секретных простых числа, p и q, p¹ q.

2. Вычисляется r=p* q.

3. Вычисляется f =(p-1)* (q-1).

4. Выбираются открытый (Ко) и секретный (Кс) ключи, которые являются взаимно простыми с f и удовлетворяют условию (Ко* Кс) mod f = 1.

Чтобы зашифровать данные открытым ключем Ко, необходимо:

1) разбить исходный текст на блоки, каждый из которых может быть представлен в виде числа M(i)=0, 1, ..., n-1;

2) зашифровать последовательность чисел M(i) по формуле

C(i)=(M(i)Ко) mod n,

где последовательность чисел C(i) представляет шифротекст.

Чтобы расшифровать эти данные секретным ключем Кс, необходимо выполнить следующие вычисления:

M(i)=(C(i)Кс) mod n.

В результате будет получено множество чисел M(i), которые представляют собой исходный текст.

Приведем простой пример использования метода RSA для шифрования сообщения “CAB”. Для простоты будем использовать малые числа (на практике используются намного большие числа).

1. Выберем p=3, q=11.

2. Вычислим r=3*11=33.

3. Вычислим f =(p-1)*(q-1)=20.

4. Выберем секретный ключ Кс, который является взаимно простым с f , например Кс=3.

5. На основе Кс и f вычислим открытый ключ Ко. Для этого можно использовать расширение алгоритма Евклида:

BEGIN

g0=f ; g1=Kc;

u0=1; u1=0;

v0=0; v1=1;

i=1;

while gi¹ 0 do

begin

gi=uif +viKc;

y=gi-1 div gi;

gi+1=gi-1-ygi;

ui+1=ui-1-yui;

vi+1=vi-1-yvi;

i=i+1;

end;

Kо=vi-1;

if Kо<0 then Kо=Kо+f ;

END.

В соответствии с алгоритмом получаем Ко=7.

6. Представим шифруемое сообщение как последовательность целых чисел в диапазоне 2...28. Пусть букве А соответствует число 2, букве В - число 3, а букве С - число 4. Тогда сообщение “CAB” можно представить в виде последовательности чисел {5, 3, 4}. Зашифруем сообщение, используя открытый ключ Ко=7:

C1 =

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

Похожие рефераты: