Реферат: Баричев С. Криптография без секретов

От автора

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

Язык книги делался по возможности доступным, но не освобождает Читателяот необходимости владения элементарными основами математики, в частностиалгебры и теории групп и полей.

Многие вопросы к сожалению остались за обложками этой книги. В частностипосле долгих сомнений Автор решил отказаться от рассмотрения DES, ввиду его крайней непрактичности инеуживчивости на российской почве[1]

Массу полезной информации можно найти на сервере

ftp.rsa.com. В faq5.docВы если и не найдете ответ на любой вопрос по криптографии, то обнаружитебольшое количество ссылок на другие источники.

Автор будет признателен за любые замечания и вопросы, которые прощевсего направить по адресу: bar@glasnet.ru

Баричев Сергей

Введение

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

С широким распространением письменности криптография стала формироватьсякак самостоятельная наука. Первые криптосистемы встречаются уже в начале нашейэры. Так, Цезарь в своей переписке использовал уже более менее систематическийшифр, получивший его имя.

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

Почему проблема использования криптографических методовв информационных системах (ИС) стала в настоящий момент особо актуальна?

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

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

Проблемой защиты информации путем ее преобразования занимаетсякриптология (kryptos — тайный, logos — наука).Криптология разделяется на два направления — криптографию и криптоанализ.Цели этих направлений прямо противоположны.

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

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

В этой книге основное внимание будет уделено криптографическимметодам.

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

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

Терминология

Итак,криптография дает возможность преобразовать информацию таким образом, что еепрочтение (восстановление) возможно только при знании ключа.

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

Алфавит — конечное множествоиспользуемых для кодирования информации знаков.

Текст — упорядоченный набор из элементовалфавита.

В качествепримеров алфавитов, используемых в современных ИС можно привести следующие:

*

алфавит Z33 — 32 буквы русского алфавита и пробел;

*

алфавит Z256 — символы, входящие в стандартные коды ASCII и КОИ-8;

*

бинарный алфавит- Z2 = {0,1};

*

восьмеричныйалфавит или шестнадцатеричный алфавит;

Шифрование — преобразовательныйпроцесс: исходный текст, которыйносит также название открытого текста,заменяется шифрованным текстом.

исходный

текст

шифрованный

текст

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

КЛЮЧ

Дешифрование — обратный шифрованиюпроцесс. На основе ключа шифрованный текст преобразуется в исходный.

шифрованный

текст

исходный

текст

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

КЛЮЧ

Ключ — информация, необходимаядля беспрепятственного шифрования и дешифрования текстов.

Криптографическая система представляетсобой семейство T преобразованийоткрытого текста. Члены этого семейства индексируются, или обозначаютсясимволом k; параметр k является ключом. Пространство ключей K — это набор возможных значений ключа. Обычно ключ представляетсобой последовательный ряд букв алфавита.

Криптосистемыразделяются на симметричные и с открытым ключом.

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

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

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

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

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

·

ПреобразованиеTk определяется соответствующималгоритмом и значением параметра k.Эффективность шифрования с целью защиты информации зависит от сохранениятайны ключа и криптостойкости шифра.

Требования к криптосистемам

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

Для современных криптографических систем защиты информациисформулированы следующие общепринятые требования:

·

Симметричные криптосистемы

Все многообразие существующих криптографических методовможно свести к следующим классам преобразований:

Симметричные

криптосистемы

Гаммирование

Подстановки

Блочные шифры

Перестановки

Моно- и многоалфавитные подстановки.

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

Перестановки.

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

Гаммирование.

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

Блочные шифры.

Представляют собой последовательность (с возможным повторениеми чередованием) основных методов преобразования, применяемую кблоку (части) шифруемого текста. Блочные шифры на практике встречаютсячаще, чем “чистые” преобразования того или иного класса в силу их болеевысокой криптостойкости. Российский и американский стандарты шифрованияоснованы именно на этом классе шифров.

Перестановки

Перестановкой s

набора целых чисел (0,1,...,N-1) называется его переупорядочение. Для тогочтобы показать, что целое i перемещеноиз позиции i в позицию s(i), где 0 £(i) < n, будем использовать запись

s

=(s(0), s(1),..., s(N-1)).

Число перестановок из (0,1,...,N-1) равно n!=1*2*...*(N-1)*N. Введем обозначение s

для взаимно-однозначного отображения (гомоморфизма) набора S={s0,s1,...,sN-1}, состоящего из n элементов, на себя.

s

: S ® S

s

:si ® ss(i), 0 £ i < n

Будем говорить, что вэтомсмысле s

является перестановкой элементов S.И, наоборот, автоморфизм S соответствует перестановке целых чисел (0,1,2,.., n-1).

Криптографическим преобразованиемT для алфавита Zmназывается последовательность автоморфизмов: T={T(n):1£

n<¥}

T(n): Zm,n

®Zm,n,1£n<¥

Каждое T(n)является, таким образом,перестановкой n-грамм из Zm,n.

Поскольку T(i)и T(j) могутбыть определены независимо при i¹

j,число криптографических преобразований исходного текста размерности n равно (mn)![2].Оно возрастает непропорционально при увеличении m и n: так, при m=33и n=2 число различныхкриптографических преобразований равно 1089!.. Отсюда следует, что потенциальносуществует большое число отображений исходного текста в шифрованный.

Практическая реализация криптографических систем требует, чтобы преобразования {Tk:kÎ

K} были определены алгоритмами,зависящими от относительно небольшого числа параметров (ключей). Системы подстановок

ОпределениеПодстановкой p

на алфавите Zmназывается автоморфизм Zm, при котором буквы исходного текста tзамещены буквами шифрованного текста p(t):

Zm

à Zm;p: t à p(t).

Набор всех подстановокназывается симметрической группой Zmè будет вдальнейшем обозначаться какSYM(Zm).

УтверждениеSYM(Zm) c операцией произведения является группой, т.е.операцией, обладающей следующими свойствами:

Замкнутость:произведение подстановок p1p2 является подстановкой:

p

: tàp1(p2(t)).

Ассоциативность:результат произведения p1p2p3 не зависит от порядка расстановки скобок:

(p

1p2)p3=p1(p2p3)

Существованиенейтрального элемента: постановка i, определяемая как i(t)=t, 0£t<m, является нейтральнымэлементом SYM(Zm)по операции умножения: ip=pi для "pÎSYM(Zm).

Существованиеобратного: для любой подстановки p существует единственная обратнаяподстановка p-1,удовлетворяющая условию

pp

‑1=p‑1p=i.

Число возможных подстановок в симметрической группе Zmназывается порядком SYM(Zm)и равно m! .

Определение.Ключом подстановки k для Zmназывается последовательность элементов симметрической группы Zm:

k

=(p0,p1,...,pn-1,...), pnÎSYM(Zm), 0£n<¥

Подстановка, определяемая ключом k, является криптографическим преобразованием Tk, при помощи которогоосуществляется преобразование n-граммыисходного текста (x0,x1 ,..,xn-1) в n-грамму шифрованного текста (y0,y1 ,...,yn-1):

yi=p(xi),

0£i<n

где n – произвольное(n=1,2,..). Tk называетсямоноалфавитной подстановкой, если pнеизменно при любом i, i=0,1,..., в противном случае Tkназывается многоалфавитной подстановкой.

Примечание. К наиболеесущественным особенностям подстановки Tkотносятся следующие:

1. Исходный текст шифруетсяпосимвольно. Шифрования n-граммы(x0,x1 ,..,xn-1) и ее префикса (x0,x1 ,..,xs-1)связаны соотношениями

Tk(x0,x1,..,xn-1)=(y0,y1 ,...,yn-1)

Tk(x0,x1,..,xs-1)=(y0,y1 ,...,ys-1)

2. Буква шифрованного текстаyi является функцией только i-й компоненты ключа pi и i-й буквы исходного текста xi.

Подстановка Цезаря

Подстановка Цезаря является самым простым вариантом подстановки.Она относится к группе моноалфавитныхподстановок.

Определение.Подмножество Cm={Ck:0£

k<m} симметрической группы SYM(Zm),содержащее m подстановок

Ck: j

®(j+k) (mod m), 0£k < m,

называется подстановкой Цезаря.

Умножение коммутативно, CkCj=CjCk=Cj+k, C0– идентичнаяподстановка, а обратной к Cк является Ck-1=Cm-k, где 0<k<m. Семейство подстановок Цезаря названо по имени римскогоимператора Гая Юлия Цезаря, который поручал Марку Туллию Цицерону составлятьпослания с использованием 50-буквенного алфавита и подстановки C3.

Подстановка определяется по таблице замещения, содержащей пары соответствующихбукв “исходный текст – шифрованный текст”. Для C3 подстановкиприведены в Табл. 1. Стрелка (à

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

Определение. СистемойЦезаря называется моноалфавитная подстановка, преобразующая n-грамму исходного текста (x0, x1 ,..,xn-1) в n‑грамму шифрованного текста (y0,y1 ,...,yn-1) в соответствии с правилом

y

i=Ck(xi),0£i<n.

Например, ВЫШЛИТЕ_НОВЫЕ_УКАЗАНИЯ посредством подстановки C3преобразуется в еюыолхиврсеюивцнгкгрлб.

Таблица 1.

Аà

Йà

Тà

Ыà

Бà

Кà

Уà

Ьà

Вà

Лà

Фà

Эà

Гà

Мà

Хà

Юà

Дà

Нà

Цà

Яà

Еà

Оà

Чà

_à

Жà

Пà

Шà

Зà

Рà

Щà

Иà

Сà

Ъà

При своей несложности система легко уязвима. Если злоумышленник имеет

1) шифрованный и соответствующий исходный текст или

2) шифрованный текст выбранного злоумышленником исходного текста,

то определение ключа и дешифрование исходного текста тривиальны.

Болееэффективны обобщения подстановки Цезаря — шифрХилла и шифр Плэйфера. Ониоснованы на подстановке не отдельных символов, а 2-грамм (шифр Плэйфера) или n-грамм[3]

(шифр Хилла). При более высокой криптостойкости они значительно сложнее дляреализации и требуют достаточно большого количества ключевой информации.Многоалфавитныесистемы. Системы одноразового использования.

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

Многоалфавитная подстановкаопределяется ключом p

=(p1,
p2,...), содержащим не менее двух различных подстановок. В начале рассмотрим многоалфавитныесистемы подстановок с нулевым начальным смещением.

Пусть {Ki: 0£

i<n}- независимые случайные переменные с одинаковым распределением вероятностей,принимающие значения на множестве Zm

Pкл{(K0, K1,..., Kn-1)=(k0, k1, ..., kn-1)}=(1/m)n

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

X=(X0, x1, ..., xn-1)

в шифрованный текст

Y=(Y0, y1, ..., yn-1)

при помощи подстановки Цезаря

Yi=CKi(xi)=(Ki+Xi) (mod m) i=0...n-1 (1)

Для такой системы подстановки используют также термин “одноразоваялента” и “одноразовый блокнот”. Пространство ключей К системы одноразовойподстановки является вектором рангов (K0,K1, ..., Kn-1) и содержит mn точек.

Рассмотрим небольшой примершифрования с бесконечным ключом. В качестве ключа примем текст

“БЕСКОНЕЧНЫЙ_КЛЮЧ....”.

Зашифруем с его помощью текст“ШИФР_НЕРАСКРЫВАЕМ”. Шифрование оформим в таблицу:

ШИФРУЕМЫЙ_ТЕКСТ

БЕСКОНЕЧНЫЙ_КЛЮЧ

ЩРДЪАТТССЦЪЫДФЬП

=SUM(ABOVE) 25

=SUM(ABOVE) 13

=SUM(ABOVE)-33 4

=SUM(ABOVE) 26

=SUM(ABOVE)-33 0

=SUM(ABOVE) 18

=SUM(ABOVE) 17

=SUM(ABOVE)-33 17

=SUM(ABOVE) 22

=SUM(ABOVE)-33 26

=SUM(ABOVE) 27

=SUM(ABOVE)-33 4

=SUM(ABOVE) 20

=SUM(ABOVE) 28

=SUM(ABOVE)-33 15

Исходный текст невозможно восстановить безключа.

Наложение белого шума в виде бесконечного ключа на исходный текстменяет статистические характеристики языка источника. Системы одноразовогоиспользования теоретически не расшифруемы[4]

,так как не содержат достаточной информации для восстановления текста.

Почему же э

еще рефераты

Еще работы по компьютерам. программированию

Реферат по компьютерам. программированию

Теория вероятностей (факультатив)

29 Августа 2013

Реферат по компьютерам. программированию

Экзаменационные билеты по "Информатика"

29 Августа 2013

Реферат по компьютерам. программированию

Экзаменационные билеты по информатике

29 Августа 2013

Реферат по компьютерам. программированию

Микроконтроллеры семейства MCS51 Intel

29 Августа 2013