Шифр — какая-либо система
преобразования текста с секретом (ключом) для обеспечения секретности
передаваемой информации.
Шифры могут использовать один
ключ для шифрования и дешифрования или
два различных ключа. По этому признаку
различают:
- Cимметричные шифр — способ шифрования, в котором для шифрования
и расшифрования применяется один и тот же криптографический ключ.
До изобретения схемы асимметричного
шифрования единственным существовавшим
способом являлось симметричное шифрование.
Ключ алгоритма должен сохраняться в
секрете обеими сторонами. Ключ алгоритма
выбирается сторонами до начала обмена
сообщениями.
- Асимметричный шифр - шифр, использующий различные ключи для шифрования и дешифрования, называемые соответсвенно открытым (публичным, общим) и закрытым (личным) ключом. Асимметричные
шифры являются довольно медленными, но
им не свойственна проблема симметричных шифров
с распространением ключа. Открытый ключ
можно свободно распространять по незащищенным
каналам, так как им можно только зашифровать,
но не расшифровать текст.
Возможность создания подобных шифров
появилась с развитием теории чисел, а
практическое их применение — с развитием
вычислительной техники, из-за необходимости
вычислений над очень длинными числами
(тысячи двоичных разрядов).
Шифры могут быть сконструированы
так, чтобы либо шифровать сразу весь текст,
либо шифровать его по мере поступления.
Таким образом, существуют:
Блочный шифр - шифрует сразу целый блок текста,
выдавая шифротекст после получения всей информации.
Поточный шифр - шифрует информацию и выдает шифротекст по мере поступления, таким образом имея возможность обрабатывать текст неограниченного размера, используя фиксированный объем памяти.
Естественно, что блочный шифр
можно превратить в поточный, разбивая
входные данные на отдельные блоки и шифруя
их по отдельности.
Также существуют неиспользуемые
сейчас подстановочные шифры, обладающие (в своём большинстве)
слабой криптостойкостью.
В качестве информации, подлежащей
шифрованию и расшифрованию, а также электронной
подписи будут рассматриваться тексты
(сообщения), построенные на некотором
алфавите.
Алфавит – конечное множество
используемых для кодирования информации
знаков.
Текст (сообщение) – упорядоченный
набор из элементов алфавита.
Основные задачи (сервисы) криптографии:
1) Обеспечение конфиденциальности
– защита информации от ознакомления
с ней со стороны лиц, не имеющих доступа
к ней (конфиденциальная информация = секретная,
ограниченного доступа информация);
2) Аутентификация – это подтверждение
подлинности сторон (идентификация) и
самой информации в процессе информационного
обмена (получатель сообщения хочет убедиться,
что сообщение пришло именно от определенного
лица, а не от кого-либо другого, даже если
это лицо захочет это отрицать);
3) Обеспечение целостности
– гарантирование, что информация
при хранении или передаче
не изменилась.
4) Обеспечение невозможности
отказаться от авторства –
предотвращение отказа субъектов
от факта передачи сообщения
и других совершенных ими действий.
Когда сообщение отправлено, получатель
может убедиться, что это сделал
легальный отправитель. Аналогично,
когда сообщение пришло, отправитель
может убедиться, что оно получено
легальным получателем.
5) Контроль доступа –
возможность ограничить и контролировать
доступ к системам и приложениям
по коммуникационным линиям.
Таким образом, наука криптология
– это важнейшая часть всех информационных
систем. Она предотвращает попытки мошенничества
в электронной коммерции и обеспечивает
юридическую силу финансовых транзакций.
1.4 История
криптографии
О важности сохранения
информации в тайне знали уже в древние
времена, когда с появлением письменности
появилась и опасность прочтения ее нежелательными
лицами. Более того, первоначально письменность
сама по себе была криптографической системой,
так как в древних обществах ею владели
только избранные. С широким распространением
письменности криптография стала формироваться
как самостоятельная наука. В документах
древних цивилизаций - Индии, Египта, Месопотамии
- есть сведения о системах и способах
составления шифрованных писем.
Историки полагают,
что первые протокриптографические приемы
появились в Древнем Египте около 4 тыс.
лет назад.
Разработкой методов преобразования
информации с целью ее защиты от несанкционированного
прочтения занимается криптография.
В истории развития криптографии можно
выделить три этапа :
- наивная криптография;
- формальная криптография;
- математическая криптография.
Наивная криптография
Для наивной криптографии (до начала
XVI в.) характерно использование любых,
обычно примитивных, способов запутывания
противника относительно содержания передаваемых
сообщений. Шифровальные системы сводились
к использованию перестановки или замены
букв на различные символы (другие буквы,
знаки, рисунки, числа и т.п.).
Одним из первых зафиксированных примеров
является шифр
Цезаря, состоящий в замене каждой
буквы исходного текста на другую, отстоящую
от нее в алфавите на определенное число
позиций. Другой шифр, полибианский
квадрат, авторство которого приписывается
греческому писателю Полибию, является шифром
простой однозначной замены. В квадрат выписывались буквы алфавита
(для греческого алфавита размер составлял
5x5). Каждая буква исходного текста заменялась
на пару цифр – номер строки и столбца
на пересечении которых стояла шифруемая
буква.
С VIII века н. э. развитие криптографии
происходит в основном в арабских странах. В
словарь криптологии арабы внесли такие
понятия как алгоритм и шифр.
В древние времена широкое применение
нашли различные простейшие криптографические
устройства:
- Греческим поэтом Архилохом, жившим в VII веке до н. э. упоминается устройство под названием сцитала (греч. σκυτάλη - жезл). Оно представляет собой цилиндр (иногда жезл командующего) и узкую полоску пергамента, обматывавшуюся вокруг него по спирали, на которой в свою очередь писалось сообщение .
Рис.2.1. Сцитала
Шифруемый текст писался на пергаментной
ленте по длине палочки, после того как
длина палочки оказывалась исчерпанной,
она поворачивалась и текст писался далее,
пока либо не заканчивался текст, либо
не исписывалась вся пергаментная лента.
Однако такой шифр может быть легко взломан.
Например, метод взлома сциталы был предложен
ещё Аристотелем.
- Другим широко известным криптографическим
устройством защиты информации был «диск Энея», придуманный Энеем Тактиком в IV веке до н. э. Устройство представляло собой диск диаметром 13-15 см и толщиной 1-2 см с проделанными в нём отверстиями, количество которых равнялось числу букв в алфавите. Каждому отверстию ставилась в соответствие конкретная буква. В центре диска находилась катушка с намотанной на неё ниткой.
Рис.2.2. Диск Энея
Для того, чтобы зашифровать
послание, необходимо было поочерёдно
протягивать свободный конец нити через
отверстия обозначающие буквы исходного
не зашифрованного сообщения. В итоге,
сам диск, с продетой в его отверстия ниткой,
и являлся зашифрованным посланием.
Формальная
криптография
Этап формальной криптографии (конец
XV – начало XX вв.) связан с появлением формализованных
и относительно стойких к ручному криптоанализу
шифров.
К концу XIV в. между итальянскими городами-государствами
в переписке уже применялись «номенклаторы»1 (лат. nomen — «имя» и calator — «раб», «слуга»).
Они состояли из кодовых обозначений для
слогов, слов и имен, а также алфавитов
шифрозамен. Вплоть до XIX в. номенклаторы
оставались самой широко используемой
системой сокрытия содержания сообщений. Симеоне де Крема (Simeone de Crema) был первым
(1401 г.), кто использовал таблицы омофонов
для сокрытия частоты появления гласных
в тексте при помощи более чем одной шифрозамены
(шифры многозначной замены).
Отцом западной криптографии
называют учёного эпохи Возрождения Леона
Баттисту Альберти. Он предложил вместо
единственного секретного алфавита, как
в моноалфавитных шифрах, использовать
два или более, переключаясь между ними
по какому-либо правилу. Он же первым заметил,
что шифровать можно и по две буквы за
раз - биграммами (хотя первый биграммный шифр Playfair был предложен лишь
в XIX веке).
В 1550 г. итальянский
математик Джероламо Кардано, состоящий
на службе у папы римского, предложил новую
технику шифрования - решётку Кардано.
Этот способ сочетал в себе как стеганографию
(искусство скрытого письма), так и криптографию.
Затруднение составляло даже понять, что
сообщение содержит зашифрованный текст,
а расшифровать его, не имея ключа (решётки)
в то время было практически невозможно. Решётку Кардано считают первым транспозиционным
шифром, или, как ещё называют,
геометрическим шифром, основанным на
положении букв в шифротексте.
Значительный толчок
криптографии дало изобретение телеграфа.
Сама передача данных перестала быть секретной,
и сообщение, в теории, мог перехватить
кто угодно.
В 1883 г. голландец Огюст
Керкгоффс сформулировал известный «принцип
Керкгоффса» - правило разработки
криптографических систем, согласно которому
в засекреченном виде держится только
определённый набор параметров алгоритма,
называемый ключом, а сам алгоритм шифрования
должен быть открытым.
В 1920 г. вышла монография
американского криптографа российского
происхождения Уильяма Ф. Фридмана «Индекс
совпадения и его применение в криптографии»
(англ. «Index of Coincidence and Its Applications in Cryptography»).
Двумя годами позже Фридман ввёл в научный
обиход термины криптология и криптоанализ. Перед началом Второй
мировой войны ведущие мировые державы
имели электромеханические шифрующие
устройства, результат работы которых
считался невскрываемым. Эти устройства
делились на два типа - роторные машины
и машины на цевочных дисках. К первому
типу относят «Энигму», использовавшуюся
войсками Германии и её союзников, второго
типа - американская M-209. В СССР производились
оба типа машин.
Успешные криптоатаки
на подобного рода криптосистемы стали
возможны только с появлением ЭВМ.
Математическая
криптография
После Первой мировой войны
правительства стран засекретили все
работы в области криптографии. Наибольший
прогресс в криптографии достигается
в военных ведомствах. Ключевой вехой в развитии криптографии
является фундаментальный труд Клода
Шеннона «Теория связи в секретных системах»
(англ. Communication Theory of Secrecy Systems) - секретный
доклад, представленный автором в 1945 г.,
и опубликованный им в «Bell System Technical Journal»
в 1949 г. В этой работе, по мнению многих
современных криптографов, был впервые
показан подход к криптографии в целом
как к математической науке.
В 1960-х годах начали появляться различные блочные
шифры, которые обладали большей криптостойкостью
по сравнению с результатом работы роторных
машин. Однако они предполагали обязательное
использование цифровых электронных устройств
- ручные или полумеханические способы
шифрования уже не использовались.
Примерно в это время Хорст Фейстель
после перехода из ВВС США на работу в
лабораторию корпорации IBM, занимается
разработкой новых методов в криптографии
и разрабатывает ячейку
Фейстеля, ставшего первым в мире открытого государственного
стандарта на шифрование данных. На основе
ячейки Фейстеля были созданы и другие
блочные шифры, в том числе TEA (1994 год), Twofish
(1998 год), IDEA (2000 год), а также ГОСТ
28147-89, являющийся стандартом шифрования в
России.
В 1976 г. публикуется работа Уитфилда Диффи
и Мартина Хеллмана «Новые направления
в криптографии» (англ. «New Directions in Cryptography»).
Данная работа открыла новую область в
криптографии, теперь известную как криптография
с открытым ключом. Также в работе содержалось описание алгоритма
Диффи - Хеллмана, позволявшего сторонам сгенерировать
общий секретный ключ, используя открытый
канал связи.
Первой реальной криптосистемой с открытым
ключом считают алгоритм RSA(названный
по имени авторов - Рон Ривест (R. Rivest), Ади
Шамир (A. Shamir) и Леонард Адлеман (L. Adleman)).
Опубликованная в августе 1977 года, работа
позволила сторонам обмениваться секретной
информацией, не имея заранее выбранного
секретного ключа.
В России для шифрования с открытым ключом
стандарт отсутствует, однако для электронной
цифровой подписи (органически связанной с шифрованием
с открытым ключом) принят ГОСТ
Р 34.10-2001, использующий криптографию
на эллиптических кривых.
Создание ассиметричных криптосистем
подтолкнуло математиков и криптоаналитиков
к изучению способов факторизации, дискретного
логарифмирования, операций над эллиптическими
кривыми в конечном поле и т.д.
Относительно новым методом является вероятностное
шифрование. Вероятностное шифрование предложили
Шафи Гольдвассер (Goldwasser) и Сильвио Микэли
(Micali). Шифрование было названо «вероятностным»
в связи с тем, что один и тот же исходный
текст при шифровании с использованием
одного и того же ключа может преобразовываться
в совершенно различные шифротексты. При
использовании криптосистем с открытым
ключом существует возможность подбора
открытого текста сопоставлением перехваченного
шифротекста с результатом шифрования.
Вероятностное шифрование позволяет на
порядки увеличить сложность такого вида
атаки.
Беннет (Bennet) и Брассард (Brassard), опираясь
на работу Уиснера (Wiesner), разработали теорию квантовой криптографии, которая базируется скорее на квантовой
физике, нежели на математике. Процесс
отправки и приёма информации выполняется
посредством объектов квантовой механики,
например, при помощи электронов в электрическом
токе, или фотонов в линиях волоконно-оптической
связи. Основанная на принципах квантовой
механики, эта система, в отличие от обычной
криптографии, теоретически позволяет
гарантированно защитить информацию от
злоумышленника, даже если тот обладает
самой современной технологией и неограниченными
вычислительными мощностями. На данный
момент, разрабатываются только прототипы
квантовых криптосистем.