Криптография

Материал из MachineLearning.

Данная статья является непроверенным учебным заданием. Студент: Участник:Лошкарёв Сергей Преподаватель: Участник:Константин Воронцов Срок: 8 января 2010 До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

Криптогра́фия (от κρυπτός — скрытый и γράφω — пишу) — наука о методах обеспечения конфиденциальности (невозможности прочтения информации посторонним) и аутентичности (целостности и подлинности авторства, а также невозможности отказа от авторства) информации.

Изначально криптография изучала методы шифрования информации — обратимого преобразования открытого (исходного) текста на основе секретного алгоритма и/или ключа в шифрованный текст (шифртекст). Традиционная криптография образует раздел симметричных криптосистем, в которых зашифрование и расшифрование проводится с использованием одного и того же секретного ключа. Помимо этого раздела современная криптография включает в себя асимметричные криптосистемы, системы электронной цифровой подписи (ЭЦП), хеш-функции, управление ключами, получение скрытой информации, квантовую криптографию.

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

Криптография — одна из старейших наук, ее история насчитывает несколько тысяч лет.

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

• Открытый (исходный) текст — данные (не обязательно текстовые), передаваемые без использования криптографии.
• Шифрованный (закрытый) текст — данные, полученные после применения криптосистемы с указанным ключом
• Криптосистема — семейство обратимых преобразований открытого текста в шифрованный.
• Ключ — параметр шифра, определяющий выбор конкретного преобразования данного текста. В современных шифрах алгоритм шифрования известен, и криптографическая стойкость шифра целиком определяется секретностью ключа (Принцип Керкгоффса).
• Криптоанализ — наука, изучающая математические методы нарушения конфиденциальности и целостности информации.
• Криптоаналитик — человек, создающий и применяющий методы криптоанализа.
• Криптография и криптоанализ составляют криптологию, как единую науку о создании и взломе шифров (такое деление привнесено с запада, до этого в СССР и России не применялось специального деления).
• Криптографическая атака — попытка криптоаналитика вызвать отклонения в атакуемой защищенной системе обмена информацией. Успешную криптографическую атаку называют взлом или вскрытие.
• Шифрование — процесс нормального применения криптографического преобразования открытого текста на основе алгоритма и ключа, в результате которого возникает шифрованный текст.
• Расшифровывание — процесс нормального применения криптографического преобразования шифрованного текста в открытый.
• Дешифрование (дешифровка) — процесс извлечения открытого текста без знания криптографического ключа на основе известного шифрованного. Термин дешифрование обычно применяют по отношению к процессу криптоанализа шифротекста (криптоанализ сам по себе, вообще говоря, может заключаться и в анализе шифросистемы, а не только зашифрованного ею открытого сообщения).
• Криптографическая стойкость — способность криптографического алгоритма противостоять криптоанализу.
• Имитозащита — защита от навязывания ложной информации. Имитозащита достигается обычно за счет включения в пакет передаваемых данных имитовставки.
• Имитовставка — блок информации, применяемый для имитозащиты, зависящий от ключа и данных. В частном случае обеспечивается ЭЦП.
• Асимметричный шифр - шифр, являющийся асимметричной криптографической системой.

История

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

Основные классические виды шифрования ― это перестановочное шифрование, при котором буквы сообщения переставляются (например «помоги мне» превращается в «опомиг нме» при простейшей схеме перестановки) и замещающий шифр, когда буквы или группы букв по определённому правилу заменяются на другие буквы или группы букв (например «fly at once» становится «gmz bu podf» при замене каждой буквы следующей за ней в алфавите). Простейшие версии обоих шифров — не более чем небольшая защита от любопытных. Первым замещающим шифром был шифр Цезаря, в котором каждая буква исходного текста заменялась буквой, стоящей на некоторое фиксированное число мест дальше в алфавите. Назван этот шифр в честь Юлия Цезаря, который, как сообщается, использовал шифр со смещением 3 при связи со своими полководцами во время военных кампаний.

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

Шифротексты, получающиеся после применения классических шифров (а также и некоторых современных), всегда выдают статистическую информацию об исходном тексте, которая может быть использована для их взлома. После разработки частотного анализа (возможно арабским энциклопедистом ал-Кинди) в IX веке, практически все такие шифры стали взламываемыми достаточно квалифицированным взломщиком. Однако классические шифры до сих пор пользуются популярностью, правда больше как головоломки. По существу, все шифры оставались уязвимы для криптоанализа с использованием этой техники до изобретения полиалфавитных шифров наиболее вероятно Леоном Баттистой Альберти около 1467 года (есть некоторые указания на то, что они были известны арабам несколько ранее). Нововведение Альберти состояло в том, чтобы использовать различные шифры (то есть замещающие алфавиты) для разных частей сообщения (возможно, для каждого последовательного исходного текста в некотором наборе). Он также изобрёл, вероятно, первую автоматическую шифровальную машину — колесо, которое осуществляло частичную реализацию его изобретения. В полиалфавитном шифре Виженера для шифрования используется ключевое слово, которое контролировало замену буквы в зависимости от того, какая использовалась буква ключевого слова. В середине 1800-х годов Бэббидж показал, что полиалфавитные шифры этого типа содержат частичную уязвимость к технике частотного анализа.

Хотя частотный анализ является мощным средством, шифрование до сих пор остаётся эффективным на практике, так как многие потенциальные криптоаналитики не знакомы с этой техникой. Взлом сообщения без частотного анализа обычно требует знания используемого шифра, то есть является следствием шпионажа, взятки, кражи или измены для его определения. В XIX веке стало окончательно ясно, что секретность алгоритма шифрования не является гарантией от взлома, более того в дальнейшем было понято, что адекватная крипографическая схема (включая шифр) должна оставаться защищённой даже, если противник полностью узнал алгоритм шифрования. Секретность ключа должна быть достаточна для хорошего шифра, чтобы сохранить стойкость к попыткам взлома. Этот фундаментальный принцип впервые ясно сформулировал в 1883 Огюстом Керкгоффсом и обычно называется Принципом Керкгоффса; альтернативно и более прямо принцип был также сформулирован Клодом Шенноном как Максима Шеннона — «враг знает нашу систему».

Для облегчения шифрования были разработаны различные вспомогательные устройства. Одним из самых первых является скитала, придуманная в Древней Греции, представляющая собой простую палочку. Придумано оно было предположительно в Спарте для осуществления перестановочного шифрования. В средние века были придуманы другие вспомогательные средства, такие как решётка для шифрования, использовавшаяся для различных видов стеганографии. С появлением полиалфавитных шифров вспомогательные устройства стали усложняться, как, например, диск с шифротекстом Альберти, квадратная доска (tabula recta) Тритемиуса и дисковый шифр Томаса Джефферсона (переоткрытый независимо Этьеном Базери около 1900). Различные механические шифраторы/дешифраторы были разработаны уже в XX веке. Принцип действия многих из них был запатентован (например, роторная машина).

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

Развитие академических криптографических исследований началось относительно недавно — начиная примерно с середины 1970-х годов с открытой публикации спецификации стандарта шифрования DES от NBS в статье Диффи — Хеллмана «New Directions in Cryptography» и открытия алгоритма RSA. После этого криптография начинает широко использоваться в коммуникациях, компьютерных сетях и вообще компьютерной безопасности.

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

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

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

Ссылки

• Википедия о криптографии
• Ященко В. В. Введение в криптографию. СПб.: Питер, 2001.