Содержание

    Исторические  основы криптографии

    Принципы  криптографии

    Идея  криптосистемы с открытым ключом

    Особенности системы

    Роторные  машины

      Описание

      Устройство машины

      Шифрование

      Расшифровка

      Математическое описание  алгоритма

      Шифровальная машина Enigma

    Список  использованных источников 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    Исторические  основы криптографии

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

    Широко  известным историческим примером криптосистемы  является так называемый шифр Цезаря, который представляет из себя простую замену каждой буквы открытого текста третьей следующей за ней буквой алфавита (с циклическим переносом, когда это необходимо). Например, "A" заменялась на "D", "B" на "E", "Z" на "C".

    Несмотря  на значительные успехи математики за века, прошедшие со времён Цезаря, тайнопись  вплоть до середины 20 века не сделала  существенных шагов вперёд. В ней  бытовал дилетантский, умозрительный, ненаучный подход.

    Например, в 20 веке широко применялись профессионалами "книжные" шифры, в которых в  качестве ключа использовалось какое-либо массовое печатное издание. Надо ли говорить, как легко раскрывались подобные шифры! Конечно, с теоретической  точки зрения, "книжный" шифр выглядит достаточно надёжным, поскольку множество  его ключей - множество всех страниц  всех доступных двум сторонам книг, перебрать которое вручную невозможно. Однако, малейшая априорная информация резко суживает этот выбор.

    Кстати, об априорной информации. Во время  Великой Отечественной войны, как  известно, у нас уделяли значительное внимание организации партизанского  движения. Почти каждый отряд в  тылу врага имел радиостанцию, а  также то или иное сообщение с "большой землёй". Имевшиеся  у партизан шифры были крайне нестойкими - немецкие дешифровщики "раскалывали" их достаточно быстро. А это, как  известно, выливается в боевые поражения  и потери. Партизаны оказались  хитры и изобретательны и в  этой области тоже. Приём был предельно  прост. В исходном тексте сообщения  делалось большое количество грамматических ошибок, например, писали: "прошсли тры эшшелона з тнками". При верной расшифровке для русского человека всё было понятно. Но криптоаналитики противника перед подобным приёмом оказались бессильны: перебирая возможные варианты, они встречали невозможное для русского языка сочетание "тнк" и отбрасывали данный вариант как заведомо неверный. Этот, казалось бы, доморощенный приём, на самом деле, очень эффективен и часто применяется даже сейчас. В исходный текст сообщения подставляются случайные последовательности символов, чтобы сбить с толку криптоаналитические программы, работающие методом перебора или изменить статистические закономерности шифрограммы, которые также могут дать полезную информацию противнику. (Подробнее - см. в параграфе о криптоанализе.) Но в целом всё же можно сказать, что довоенная криптография была крайне слаба и на звание серьёзной науки не тянула.

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

    Тогда же, в период второй мировой войны  появились и первые профессиональные службы дешифровки. Самая извесная из них - "Блечли-парк", подразделение английской службы разведки "МИ-5" 

    Принципы  криптографии

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

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

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

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

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

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

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

    Идея  криптосистемы с  открытым ключом

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

    Но  сама односторонняя функция бесполезна в применении: ею можно зашифровать  сообщение, но расшифровать нельзя. Поэтому  криптография с открытым ключом использует односторонние функции с лазейкой. Лазейка — это некий секрет, который помогает расшифровать. То есть существует такой y, что зная f(x) и y, можно вычислить x. К примеру, если разобрать часы на множество составных частей, то очень сложно собрать вновь работающие часы. Но если есть инструкция по сборке (лазейка), то можно легко решить эту проблему.

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

Вход в систему  теперь выглядит так:

    Когда Алиса вводит «секретный» пароль, компьютер проверяет, даёт или нет  функция, применяемая к ГЛАДИОЛУС, правильный результат РОМАШКА, хранящийся на диске компьютера. Стоит изменить хотя бы одну букву в имени или в пароле, и результат функции будет совершенно другим. «Секретный» пароль не хранится в компьютере ни в каком виде. Файл паролей может быть теперь просмотрен другими пользователями без потери секретности, так как функция практически необратимая.

    В предыдущем примере используется односторонняя  функция без лазейки, поскольку  не требуется по зашифрованному сообщению  получить исходное. В следующем примере рассматривается схема с возможностью восстановить исходное сообщение с помощью «лазейки», то есть труднодоступной информации. Для шифрования текста можно взять большой абонентский справочник, состоящий из нескольких толстых томов (по нему очень легко найти номер любого жителя города, но почти невозможно по известному номеру найти абонента). Для каждой буквы из шифруемого сообщения выбирается имя, начинающееся на ту же букву. Таким образом букве ставится в соответствие номер телефона абонента. Отправляемое сообщение, например «КОРОБКА», будет зашифровано следующим образом:

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

Примеры таких криптотекстов:

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

Схема шифрования с открытым ключом

Пусть K — пространство ключей, а e и d — ключи шифрования и расшифрования соответственно. E_e — функция шифрования для произвольного ключа e   K, такая что:

E_e(m) = c

Здесь c   C, где C — пространство шифротекстов, а m   M, где M — пространство сообщений.

D_d — функция расшифрования, с помощью которой можно найти исходное сообщение m, зная шифротекст c :

D_d(c) = m

{E_e: e   K} — набор шифрования, а {D_d: d   K} — соответствующий набор для расшифрования. Каждая пара (E,D) имеет свойство: зная E_e, невозможно решить уравнение E_e(m) = c, то есть для данного произвольного шифротекста c   C, невозможно найти сообщение m   M. Это значит, что по данному e невозможно определить соответствующий ключ расшифрования d. E_e является односторонней функцией, а d — лазейкой. 

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

1. Боб выбирает пару (e,d) и шлёт ключ шифрования e (открытый ключ) Алисе по открытому каналу, а ключ расшифрования d (закрытый ключ) защищён и секретен (он не должен передаваться по открытому каналу).
2. Чтобы послать сообщение m Бобу, Алиса применяет функцию шифрования, определённую открытым ключом e: E_e(m) = c, c — полученный шифротекст.
3. Боб расшифровывает шифротекст c, применяя обратное преобразование D_d, однозначно определённое значением d.

    В этой модели Ева перехватывает открытый ключ e, посланный Бобом Алисе. Затем создает пару ключей e' и d', «маскируется» под Боба, посылая Алисе открытый ключ e', который, как думает Алиса, открытый ключ, посланный ей Бобом. Ева перехватывает зашифрованные сообщения от Алисы к Бобу, расшифровывает их с помощью секретного ключа d', заново зашифровывает открытым ключом e Боба и отправляет сообщение Бобу. Таким образом, никто из участников не догадывается, что есть третье лицо, которое может как просто перехватить сообщение m, так и подменить его на ложное сообщение m'. Это подчеркивает необходимость аутентификации открытых ключей. Для этого обычно используют сертификаты. Распределённое управление ключами в PGP решает возникшую проблему с помощью поручителей.

    Еще одна форма атаки — вычисление закрытого ключа, зная открытый (рисунок ниже). Криптоаналитик знает алгоритм шифрования E_e, анализируя его, пытается найти D_d. Этот процесс упрощается, если криптоаналитик перехватил несколько криптотекстов с, посланных лицом A лицу B.   

    Большинство криптосистем с открытым ключом основаны на проблеме факторизации больших чисел. К примеру, RSA использует в качестве открытого ключа n произведение двух больших чисел. Сложность взлома такого алгоритма состоит в трудности разложения числа n на множители. Но эту задачу решить реально. И с каждым годом процесс разложения становится все быстрее. Ниже приведены данные разложения на множители с помощью алгоритма «Квадратичное решето».

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

    Особенности системы

    Применение

    Алгоритмы криптосистемы с открытым ключом можно использовать

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

    Преимущества

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

    Недостатки

• Преимущество алгоритма симметричного шифрования над несимметричным заключается в том, что в первый относительно легко внести изменения.
• Хотя сообщения надежно шифруются, но «засвечиваются» получатель и отправитель самим фактом пересылки шифрованного сообщения.
• Несимметричные алгоритмы используют более длинные ключи, чем симметричные. Ниже приведена таблица, сопоставляющая длину ключа симметричного алгоритма с длиной ключа несимметричного алгоритма (RSA) с аналогичной криптостойкостью:

• Процесс шифрования-расшифрования с использованием пары ключей проходит на два-три порядка медленнее, чем шифрование-расшифрование того же текста симметричным алгоритмом.
• В чистом виде асимметричные криптосистемы требуют существенно больших вычислительных ресурсов, потому на практике используются в сочетании с другими алгоритмами.
1. Для ЭЦП сообщение предварительно подвергается хешированию, а с помощью асимметричного ключа подписывается лишь относительно небольшой результат хеш-функции.
2. Для шифрования они используются в форме гибридных криптосистем, где большие объёмы данных шифруются симметричным шифром на сеансовом ключе, а с помощью асимметричного шифра передаётся только сам сеансовый ключ.

    Роторные  машины

    В 20-х годах XX века были изобретены электромеханические  устройства шифрования, автоматизирующие процесс шифрования. Принцип работы таких машин основан на многоалфавитной замене символов исходного текста по длинному ключу согласно версии шифра Вижинера. Большинство из них - американская машина SIGABA (М-134), английская TYPEX, немецкая ENIGMA, японская PURPLE были роторными машинами.

    Главной деталью роторной машины является ротор (или колесо) с проволочными перемычками  внутри. Ротор имеет форму диска (размером с хоккейную шайбу). На каждой стороне диска расположены равномерно по окружности m электрических контактов, где m - число знаков алфавита (в случае латинского алфавита m = 26). Каждый контакт на передней стороне диска соединен с одним из контактов на задней стороне. В результате электрический сигнал, представляющий знак, будет переставлен в соответствии с тем, как он проходит через ротор от передней стороны к задней. Например, ротор можно закоммутировать проволочными перемычками для подстановки G вместо A, U вместо В, L вместо С и т.д.

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

    T = C j p C -j, (15) 

    где p - подстановка, реализуемая ротором в его начальном положении; С - циклический сдвиг на одну позицию; C j - циклический сдвиг на j позиций.

    Например, если начальная подстановка ротора p(А) = G и ротор сдвигается на три позиции (j = 3), то открытый текст D будет против того контакта ротора, который используется для представления открытого текста А, а шифрованный текст J окажется против того контакта ротора, который используется для представления шифрованного текста G , и результирующая подстановка Т(D) = G при j = 3. Алгебраически это записывается в виде:

    Т (D) = С3pС-3 (D) = С3 p (А) = С3 (G) = J.

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

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

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

    Простейшее  из возможных движений ротора - это  движение по принципу одометра; оно  использовалось в немецкой машине Enigma во время второй мировой войны. При шифровании одного знака правое крайнее колесо поворачивается на одну позицию. Когда это (и любое другое) колесо переместится на m позиций и совершит полный оборот, колесо, расположенное слева от него, передвинется на одну позицию, и процесс будет повторяться. Этот процесс проведет банк роторов сквозь все его возможные положения, прежде чем цикл повторится. Поскольку все роторы перемещаются с разными скоростями, период n-роторной машины составляет 26n (при m = 26).

    Для закона движения ротора желательны следующие  характеристики:

    • период должен быть большим;

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

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

    Другое  решение заключается в ограничении  числа допустимых остановочных мест для каждого ротора за счет введения внешнего фиксирующего кольца, на котором  определенным способом зафиксированы  места остановок. При использовании  латинского алфавита можно заставить  машины поворачиваться и останавливаться  следующим образом. Первому колесу разрешается останавливаться в  каждой из 26 позиций, второму колесу - только в 25 позициях, третьему колесу - только в 23 позициях, и так далее до шестого колеса, которому разрешается останавливаться только в 17 позициях. Период такой роторной машины теперь составляет 101 млн, а не 266»309 млн, как в случае движения по принципу одометра. Потеря в длине периода с успехом окупается полученной сложностью движения роторов. Теперь второе требование удовлетворяется довольно хорошо, поскольку каждое из колес перемещается после шифрования каждого знака и многие колеса могут двигаться друг относительно друга.

    Роторная  машина может быть настроена по ключу  изменением любых ее переменных:

    •роторов;

    •порядка  расположения роторов;

    •числа  мест остановки на колесо;

    •характера  движения и т.д.

    Поскольку перекоммутировать роторы трудно, то обычно на практике машины обеспечивали комплектом роторов, в котором находилось больше роторов, чем можно одновременно поместить в машину. Первичная настройка по ключу производилась выбором роторов, составляющих комплект. Вторичная настройка по ключу производилась выбором порядка расположения роторов в машине и установкой параметров, управляющих движением машины. С целью затруднения расшифрования шифртекстов противником роторы ежедневно переставляли местами или заменяли. Большая часть ключа определяла начальные положения роторов (2б3=17576 возможных установок) и конкретные перестановки на коммутационной доске, с помощью которой осуществлялась начальная перестановка исходного текста до его шифрования (26!= 4·1026 возможностей).