На протяжении всей своей истории человек испытывал потребность в шифровке той или иной информации. Неудивительно, что из этой потребности выросла целая наука - криптография. И если раньше криптография по большей части служила исключительно государственным интересам, то с приходом интернета ее методы стали достоянием частных лиц и широко используются хакерами, борцами за свободу информации и любыми лицами, желающими в той или иной степени зашифровать свои данные в сети.
FURFUR начинает серию статей о криптографии и методах ее использования. Первый материал - вводный: история вопроса и базовые термины.
Формально криптография (с греческого - «тайнопись») определяется как наука, обеспечивающая секретность сообщения. Пионером, написавшим первый научный труд о криптографии, считается Эней Тактик, завершивший свой земной путь задолго до Рождества Христова. Свои данные пытались шифровать еще Индия и Месопотамия, но первые надежные системы защиты были разработаны в Китае. Писцы Древнего Египта часто использовали изощренные способы письма, чтобы привлечь внимание к своим текстам. Чаще всего шифровка информации использовалась в военных целях: широко известен шифр «Скитала», примененный Спартой против Афин в V веке до н. э.
Криптография активно развивалась в Средние века, шифровками пользовались многочисленные дипломаты и купцы. Одним из самых известных шифров Средних веков называют кодекс Copiale - изящно оформленную рукопись с водяными знаками, не расшифрованную до сих пор. Эпоха Возрождения стала золотым веком криптографии: ее изучением занимался Фрэнсис Бэкон, описавший семь методов скрытого текста. Он же предложил двоичный способ шифрования, аналогичный использующемуся в компьютерных программах в наше время. Значительное влияние на развитие криптографии оказало появление телеграфа: сам факт передачи данных перестал быть секретным, что заставило отправителей сосредоточиться на шифровке данных.
Во время Первой мировой войны криптография стала признанным боевым инструментом. Разгаданные сообщения противников вели к ошеломляющим результатам. Перехват телеграммы немецкого посла Артура Циммермана американскими спецслужбами привел к вступлению США в боевые действия на стороне союзников.
Вторая мировая война послужила своеобразным катализатором развития компьютерных систем - через криптографию. Использованные шифровальные машины (немецкая «Энигма», английская «Бомба Тьюринга») ясно показали жизненную важность информационного контроля. В послевоенное время правительства многих стран наложили мораторий на использование криптографии. Ключевые работы публиковались исключительно в виде секретных докладов - таких, как, например книга Клода Шеннона «Теория связи в секретных системах», подходящая к криптографии как к новой математической науке.
Правительственная монополия рухнула только в 1967 году с выходом книги Дэвида Кана «Взломщики кодов». Книга подробно рассматривала всю историю криптографии и криптоанализа. После ее публикации в открытой печати стали появляться и другие работы по криптографии. В это же время сформировался современный подход к науке, четко определились основные требования к зашифрованной информации: конфиденциальность, неотслеживаемость и целостность. Криптография была разделена на две взаимодействующие части: криптосинтез и криптоанализ. То есть криптографы обеспечивают информации защиту, а криптоаналитики, напротив, ищут пути взлома системы.
Wehrmacht Enigma («Энигма»)
Шифровальная машина Третьего рейха. Код, созданный при помощи «Энигмы»,
считается одним из сильнейших из использованных во Второй мировой.
Turing Bombe («Бомба Тьюринга»)
Разработанный под руководством Алана Тьюринга дешифратор. Его использование
позволило союзникам расколоть казавшийся монолитным код «Энигмы».
Cовременные методы использования криптографии
Появление доступного интернета перевело криптографию на новый уровень. Криптографические методы стали широко использоваться частными лицами в электронных коммерческих операциях, телекоммуникациях и многих других средах. Первая получила особенную популярность и привела к появлению новой, не контролируемой государством валюты - биткойна.
Многие энтузиасты быстро смекнули, что банковский перевод - штука, конечно, удобная, однако, для покупки таких приятных в быту вещей, как оружие или «вещества», он не подходит. Не подходит он и при запущенных случаях паранойи, ибо требует от получателя и отправителя обязательной аутентификации.
Аналоговую систему расчета предложил один из «шифропанков», о которых речь пойдет ниже, молодой программист Вэй Дай. Уже в 2009 году Сатоши Накамото (которого многие свято считают целой хакерской группировкой) разработал платежную систему нового типа - BitCoin. Так родилась криптовалюта. Ее транзакции не требуют посредника в виде банка или другой финансовой организации, отследить их невозможно. Сеть полностью децентрализована, биткойны не могут быть заморожены или изъяты, они полностью защищены от государственного контроля. В то же время биткойн может использоваться для оплаты любых товаров - при условии согласия продавца.
Новые электронные деньги производят сами пользователи, предоставляющие вычислительные мощности своих машин для работы всей системы BitCoin. Такой род деятельности называется майнинг (mining - добыча полезных ископаемых). Заниматься майнингом в одиночку не очень выгодно, гораздо проще воспользоваться специальными серверами - пулами. Они объединяют ресурсы нескольких участников в одну сеть, а затем распределяют полученную прибыль.
Крупнейшей площадкой купли-продажи биткойнов является японская Mt. Gox, через которую проводятся 67% транзакций в мире. Заядлые анонимы предпочитают ей российскую BTC-E: регистрация здесь не требует идентификации пользователя. Курс криптовалюты довольно-таки нестабилен и определяется только балансом спроса и предложения в мире. Предостережением новичкам может служить известная история о том, как 10 тысяч единиц, потраченых одним из пользователей на пиццу, превратились через некоторое время в 2,5 миллиона долларов.
«Главная проблема обычной валюты в том, что она требует доверия. Центральный банк требует доверия к себе и своей валюте, однако сама история фиатных денег полна примеров подрыва доверия. С появлением электронной валюты, основанной на надежной криптографии, нам больше не нужно доверять «честному дяде», деньги наши могут быть надежно сохранены, а использование их становится простым и удобным»
Сатоши Накамото, хакер
Терминология
Основными операторами являются исходное сообщение (открытый текст, plaintext) и его изменение (шифротекст, ciphertext). Дешифровкой (decryption) называется сам процесс трансформации шифротекста в текст открытый. Для начинающего криптографа важно запомнить и несколько других терминов:
АЛИСА, ЕВА И БОБ (ALICE)
Свести описание криптопротокола к математической формуле помогают определенные имена участников игры: Алиса и Боб. Противник в действующей криптосистеме обозначен как Ева (eavesdropper - подслушивающий). В редких случаях имя меняется, однако противник всегда остается женского рода.
АВТОНОМНАЯ СИСТЕМА ЭЛЕКТРОННЫХ ПЛАТЕЖЕЙ (OFF-LINE E-CASH SYSTEM)
Благодаря ей покупатель и продавец могут работать напрямую, без участия банка-эмитента. Минус этой системы заключается в дополнительной транзакции, которую совершает продавец, переводящий полученные деньги на свой банковский счет.
АНОНИМНОСТЬ (ANONYMITY)
Это понятие означает, что участники акции могут работать конфиденциально. Анонимность бывает абсолютной и отзываемой (в системах, подразумевающих участие третьего лица, арбитра). Арбитр может при определенных условиях идентифицировать любого игрока.
ПРОТИВНИК (ADVERSARY)
Нарушитель. Он стремится нарушить периметр конфиденциальности протокола. Вообще, использующие криптопротокол участники воспринимают друг друга как потенциальных противников - по умолчанию.
ЧЕСТНЫЙ УЧАСТНИК (HONEST PARTY)
Честный игрок, обладающий необходимой информацией и строго следующий протоколу системы.
ЦЕНТР ДОВЕРИЯ (AUTHORITY (TRUSTED AUTHORITY))
Своеобразный арбитр, который пользуется доверием всех участников системы. Необходим в качестве меры предосторожности, гарантирующей участникам соблюдение оговоренного протокола.
БОЛЬШОЙ БРАТ (BIG BROTHER)
Да, именно он. Действия Большого Брата не контролируются и не отслеживаются другими участниками криптопротокола. Доказать нечестную игру Большого Брата невозможно, даже если все в этом уверены.
Анонимность
Начинающие ревнители конфиденциальности сохраняют инкогнито при помощи специальных сайтов - веб-прокси. Они не требуют отдельного программного обеспечения и не забивают голову пользователя сложной настройкой. Искомый адрес юзер вводит не в браузере, а в адресной строке сайта-анонимайзера. Тот обрабатывает информацию и передает от своего имени. Заодно такой сервер получает чудесную возможность скопировать проходящие через него данные. В большинстве случаев так и происходит: информация лишней не бывает.
Продвинутые анонимы предпочитают использовать средства посерьезнее. Например, Tor (The Onion Router). Этот сервис использует целую цепочку прокси-серверов, контролировать которую практически невозможно из-за ее разветвленности. Система многослойной (на сленге - луковой) маршрутизации обеспечивает пользователям Tor высокий уровень безопасности данных. Кроме того, The Onion Router мешает анализировать проходящий через него трафик.
Шифропанк
Впервые термин прозвучал из уст известной хакерши Джуд Милхон в адрес чрезмерно увлеченных идеей анонимности программистов. Основная идея шифропанка (cypherpunk) - возможность обеспечения анонимности и безопасности в сети самими пользователями. Достигнуть этого можно посредством открытых криптографических систем, которые в большинстве своем разрабатываются активистами шифропанка. Движение имеет неявную политическую окраску, большей части участников близок криптоанархизм и многие либертарные социальные идеи. Известнейший представитель шифропанка - Джулиан Ассанж, на радость всем мировым державам основавший WikiLeaks. У шифропанков есть официальный манифест .
«Новая большая игра - это отнюдь не война за нефтепроводы... Новое всемирное сокровище - это контроль
над гигантскими потоками данных, соединяющими целые континенты и цивилизации, связывающими в единое целое коммуникацию миллиардов людей и организаций»
Джулиан Ассанж
Джулиан Ассанж
На своем портале WikiLeaks публично продемонстрировал всем желающим изнанку многих государственных структур. Коррупция, военные преступления, сверхсекретные тайны - вообще все, до чего дотянулся деятельный либертарианец, стало достоянием общественности. Помимо этого, Ассанж - создатель адской криптосистемы под названием «Отрицаемое шифрование» (Deniable encryption). Это способ компоновки зашифрованной информации, который обеспечивает возможность правдоподобного отрицания ее наличия.
Брэм Коэн
Американский программист, родом из солнечной Калифорнии. На радость всему миру придумал протокол BitTorrent, которым небезуспешно пользуются и по сей день.
Необходимость обеспечить секретность информации возникла с самых древних времен. Во многом роль средства переноса секретной информации в древние времена играл язык жрецов. На этом языке записывали сакральные знания, он был доступен только крайне малому числу людей.
Большинство ученых связывают появление криптографии с появлением письменности. Используемое в древнейших государствах клинопись, рисуночное и иероглифическое письмо было крайне сложно и требовало длительного обучения, круг грамотных лиц был весьма ограничен. Это позволяло использовать для передачи секретной информации ее письменную запись.
Некоторые из сохранившихся глиняных табличек позволяют предположить что древним был известен прием когда исходное письмо, написанное на глиняной табличке и закрепленное обжигом, покрывалось вторым слоем глины на котором писалось сообщение не содержащие секретных сведений. Подобный прием использовал строитель Александрийского маяка Сострат, который по указанию правителя Египта Птолемея Филадельфа установил в стене табличку с его именем, но сделал ее из штукатурки покрашенной под мрамор. Спустя многие годы слой штукатурки рассыпался и открыл подлинное имя автора одно из чудес света выбитое на камне. Другой подобный прием использовался при отправки писем: рабу брили наголо волосы, писали на голове послание а когда волосы отрастали, отправляли к адресату с маловажным сообщением.
Таким образом, уже в древнем мире люди использовали два основных приема используемых до сих пор:
скрытия самого факта передачи (наличия) тайного сообщения – стеганография ;
шифрования сообщения – криптография .
Первые шифры
Большинство исследователей связывают появление криптографии с появлением фонетического письма, значительно более простого и доступного большему количеству людей, чем рисуночное и иероглифическое письмо.
Древнейшим зашифрованным сообщением, сохранившимся до наших дней, является история жизни египетского сановника, записанная его писцом на стенах гробницы в городе Менет-Хуфу примерно в 1900 году до нашей эры. Примененная писцом система основывалась на изменении начертания отдельных иероглифов. Фактически она не была тайнописью в полном понимании этого слова. По египетским верованиям, тот, кто читал надписи на гробнице, способствовал загробной жизни человека. Фактически это была головоломка, требующая больше времени, заставляющая задуматься и взывающая желание разгадать скрытый смысл.
Криптография в государствах Азии
Сведения о способах шифрования применявшихся в государствах Азии в нашей литературе встречаются не часто.
В Индии, стране с древней высокоразвитой цивилизацией, люди с незапамятных времен пользовались несколькими разновидностями тайнописи. В древнеиндийском трактате об искусстве управлять государством, написанном примерно в 300 году до н. э., говорится о использовании тайнописи для служебной переписки служб безопасности, дипломатии. Кроме того упоминается о необходимости вскрытия чужих зашифрованных писем с целью получения конфиденциальной информации как частных лиц, так и секретов других государств.
В ходе эволюции человек учился защищаться от холода, голода, диких зверей и капризов погоды. На каком-то из этапов своего развития он понял важность своевременного получения достоверной и правильно отобранной информации. И, наконец, осознал необходимость информацию эту защищать.
В условиях соперничества (военного, научного или коммерческого - не важно) знания существуют в двух формах - «у меня и у моего врага». И для того чтобы победить или хотя бы выжить, первую форму желательно довести до максимума, а вторую - до минимума. Защищая свою информацию, мы стремимся сохранить в тайне имеющийся у нас запас знаний, а рассекречивая чужую - увеличить этот запас за счет конкурентов.
История защиты информации начинается, по всей вероятности, где-то в то время, когда люди начали учиться общаться при помощи переписки. Естественно, им потребовались способы обеспечить ее секретность. Точных дат и достоверных данных о тайнописи в древности никто не приводит.
Известно, например, что в Древней Греции голову раба брили, писали на его голове, ждали, когда волосы вновь вырастут, после чего отправляли с поручением к адресату. Что и говорить, время было такое - расстояния большие, скорости малые, плюс-минус два месяца роли не играли.
Знатокам поэзии хорошо известен такой довольно широко используемый в то время прием тайнописи, как акростих, в котором скрываемое сообщение образуют начальные буквы стихотворных строк.
Для создания скрытого сообщения можно применять специальные технические средства (передать в конкретную точку пространства по радиоканалу остронаправленным лучом, предельно сжать информацию и передать в мгновенном импульсе, написать бесцветными чернилами, проявляющимися лишь после некоторого физического или химического воздействия). Кто из нас не читал, как в царских застенках революционеры писали письма молоком …
Все вышеперечисленные и подобные им способы защиты информации относят к стеганографическим или симпатическим, при которых сама информация остается неизменной, ее стараются сделать невидимой и тем самым скрыть факт ее передачи.
Стеганогра́фия (от греч. στεγανός - скрытый + γράφω - пишу; буквально «тайнопись» ) - это наука о скрытой передаче информации путём сохранения в тайне самого факта передачи.
Симпати́ческие (невидимые) черни́ла - это чернила, записи которыми являются изначально невидимыми и становятся видимыми только при определенных условиях (нагрев, освещение, химический проявитель и т. д.)
Методы эти развивались и усложнялись вместе с ходом технического прогресса. Вершиной развития этих методов можно считать, вероятно, технологию создания сверхминиатюрных фотографий - так называемых микроточек, - которая появилась после Второй мировой войны. Такая микроточка размером с точку печатного текста могла содержать сотни документов, и найти ее в книге, журнале или газете было ненамного проще, чем иголку в стоге сена. Современная микросхемотехника сверхбольшой интеграции позволяет записать текст так мелко, что без электронного микроскопа прочесть его будет невозможно. Широкое распространение компьютеров позволяет применять другие способы сокрытия информации. Например, «нестандартное» форматирование дисков, запись на технические дорожки, замешивание информации в большие объемы данных и т. д.
Однако явным недостатком симпатических методов является то, что скрытность созданных с их помощью сообщений обеспечивается лишь на данном этапе развития техники. Любой способ создания симпатического текста будет вскоре разрушен. А что за секретность без гарантии стойкости?
Интересно, что в глубокой древности тайнопись считалась одним из 64-х искусств, которым следует владеть как мужчинам, так и женщинам. Сведения о способах шифрованного письма можно обнаружить уже в документах древних цивилизаций Индии, Египта, Месопотамии. Среди самых простых - иероглифическое письмо, написание знаков не по порядку, а вразброс по некоторому правилу.
Первое исторически достоверное применение технических средств шифровки приписывается древним грекам и датируется примерно V–VI веками до нашей эры. Таким техническим средством был специальный брусок, называемый «скитала»(сцитала). Его оборачивали узкой полоской бумаги и писали сообщение вдоль бруска. Затем полоску снимали и отправляли адресату. Предполагалось, что прочесть сообщение, не зная толщины бруска - которая служила здесь ключом шифрования - было невозможно.
Кроме того, Эней в работе «Об обороне укрепленных мест» описывает так называемый «книжный шифр» и способ перестановки букв в тексте по специальной таблице.
Известна также система шифрования под названием «квадрат Полибия», в которой каждая буква заменяется парой чисел - ее координатами в квадрате 5x5, куда предварительно в заранее заданном порядке вписаны буквы алфавита.
Уже тогда шифрованная переписка использовалась не только полководцами, но и церковью, и учеными. Жрецы шифровали тексты прорицателей, а ученые - свои открытия. Например, у Эдуарда Шюре в книге «Великие посвященные» встречается фраза о том, что «с великим трудом и большой ценой добыл Платон один из манускриптов Пифагора, который никогда не записывал свое учение иначе, как тайными знаками и под различными символами».
Классический пример с шифром Цезаря описан во всех учебниках по криптографии: не доверяя гонцам, Юлий Цезарь шифровал свои депеши, используя способ, который впоследствии получит название шифра прямой замены . В своих письмах он заменял каждую A на D, каждую B на E, и т. д. И его послание мог дешифровать только тот, кто знал правило «смещения на 3».
Словом, к началу нашей эры люди знали о криптографии довольно много и использовали ее достаточно широко. Последующие 19 веков были потрачены на изобретение более или менее хитроумных способов шифрования, надежность которых во многом была призрачной и зависела, главным образом, от того, насколько им доверяли те, кто ими пользовался.
Довольно мало сведений о применяемых шифрах можно найти до эпохи Возрождения. Известен ряд значковых шифров, при котором буквы открытого текста заменяются специальными знаками (помните «танцующих человечков» Конана Дойля?). Таким является шифр Карла Великого, применявшийся в IX веке нашей эры.
Период расцвета арабских государств (VIII век н. э.) - поистине эпоха великих открытий в области криптографии. Не зря ведь слово «шифр», как и слово «цифра», имеет арабские корни. В появившейся в 855 году арабской «Книге о стремлении человека разгадать загадки древней письменности» описываются различные системы защиты информации, в том числе и несколько классических шифралфавитов. Один такой шифралфавит, называвшийся «дауди» (по имени израильского царя Давида), использовался для шифрования трактатов по черной магии. Он был составлен из видоизмененных букв древнееврейского алфавита.
Следующие сведения о криптографии также относятся к арабскому миру. В 1412 году на свет появляется произведение Шехаба Калкашанди - 14-томная «Энциклопедия всех наук», содержащая и сведения о методах засекречивания переписки. Раздел под общим заголовком «Относительно сокрытия в буквах тайных сообщений» состоял из двух частей: одна касалась символических действий, намеков и иносказаний, во второй описывались симпатические чернила и криптология.
Здесь не только впервые подробно рассказывалось о шифрах перестановок и шифрах замены, но и упоминался шифр, использующий несколько замен букв открытого текста. Но не этим известна книга. Все остальное затмевается первым в истории описанием криптоанализа на основе частоты появления знаков в исходном и шифрованном текстах. Автор даже приводит список букв арабского алфавита с указанием частоты их встречаемости в текстах Корана. Уже тогда частотный анализ сообщения позволял достаточно просто раскрывать шифры простой подстановки.
Криптоло́гия - наука, занимающаяся методами шифрования и дешифрования. Криптология состоит из двух частей - криптографии и криптоанализа.
Криптогра́фия - наука о методах обеспечения конфиденциальности (невозможности прочтения информации посторонним) и аутентичности (целостности и подлинности авторства, а также невозможности отказа от авторства) информации.
Изначально криптография изучала методы шифрования информации - обратимого преобразования открытого (исходного) текста на основе секретного алгоритма и/или ключа в шифрованный текст (шифротекст).
Криптография и шифрование тысячи лет используются людьми для защиты своих секретов. С некоторой долей условности эту историю можно начать с Древнего Египта.
Древний Египет
Самый древний текст с элементами криптографии найден в гробнице древнеегипетского вельможи Хнумхотепа II, наследного князя и номарха города Менат-Хуфу, жившего почти 4000 лет назад. Где-то около 1900 г до н.э. писарь Хнумхотепа описывал жизнь своего господина в его гробнице. Среди иероглифов он использовал несколько необычных символов, которые скрывают прямое значение текста. Такой метод шифрования фактически представляет собой шифр подстановки, когда элементы исходного текста заменяются другими элементами по определённым правилам.Символы из гробницы Хнумхотепа II и их расшифровка
По мере развития египетской культуры замены иероглифов встречались всё чаще. Есть разные версии, почему египтяне использовали такую систему шифрования. По одной версии, они хотели охранить свои религиозные ритуалы от обычных людей. По другой версии, таким образом писцы придавали тексту некий формальный вид, как в наше время юристы используют специфические выражения для замены обычных слов. Как и сейчас, египетская криптография тоже могла быть способом писца впечатлить других людей - показать, что он может изъясняться на более высоком уровне, чем они.
Древняя Греция
Примерно в 500 г до н.э. спартанцы разработали устройство под названием скитала, созданное для отправки и получения секретных сообщений. Оно представляло собой цилиндр, обёрнутый по спирали узкой полоской пергамента. Послание писалось вдоль скиталы, но если полоску развернуть, оно становилось нечитаемым. Для прочтения текста требовалась скитала такого же диаметра. Только в этом случае буквы становились в ряд, чтобы восстановить оригинальное сообщение.
Пример скиталы
Скитала является примером перестановочного шифра, в котором элементы исходного текста меняют местами, а не заменяют другими символами. По современным стандартам скиталу было бы очень просто взломать, но 2500 лет назад очень мало людей умели читать и писать. Скитала обеспечила спартанцам защищённую связь.
Древний Рим
Самый ранний известный способ военного применения криптографии принадлежит Юлию Цезарю. Около 2000 лет назад Цезарь, будучи полководцем римской армии, решил проблему безопасных коммуникаций со своими полками. Проблема была в том, что гонцы с секретными военными сообщениями часто перехватывались неприятелем. Цезарь разработал шифр подстановки, в котором заменял одни буквы другими. Только тот, кто знал таблицу подстановки, мог расшифровать секретное сообщение. Теперь, даже если гонец попадёт в руки врага, шифровки не будут рассекречены. Это дало римлянам огромное преимущество в войне.
Пример шифра подстановки
В отличие от примера на этой иллюстрации, Цезарь обычно просто сдвигал буквы на некое определённое число. Это число было шифровальным ключом для его алгоритма. Случайный порядок замены символов обеспечивает гораздо лучшую безопасность благодаря большему количеству возможных таблиц замены.
Шифр Альберти-Виженера
В середине 15 века итальянский учёный, архитектор, скульптор, художник и математик Леон Батиста Альберти изобрёл систему шифрования на основе шифровального диска. Это было механическое устройство со скользящими дисками, которые допускали много разных методов подстановки символов. Это базовая концепция многоалфавитного шифра, в котором метод шифрования меняется непосредственно в процессе шифрования. В своей книге «Взломщики кодов» Дэвид Кан называет Альберти «отцом западной криптографии». Альберти никогда не реализовал свою концепцию шифровального диска, она осталась только на бумаге.
Шифровальный диск
В 16 веке французский дипломат Блез Виженер на основе концепции многоалфавитного шифра Альберти создал шифр, который получил название шифра Виженера. Он работает точно как система Цезаря за исключением того, что ключ меняется в процессе шифрования. В шифре Виженера применяется решётка из букв, которая задаёт метод подстановки. Её называют квадратом Виженера или таблицей Виженера. Решётка состоит из 26 строк алфавита со смещением на один символ друг относительно друга.
Метод смены одного ключа на другой следует простому шаблону. В качестве ключа шифрования выбирается специальное секретное слово. Каждый символ в исходном тексте заменяется с использованием таблицы. Чтобы определить, на какую букву нужно заменить первый символ, мы совмещаем первый символ исходного текста (по одной оси) с первым символом секретного слова (по другой оси). Метод повторяется для второй и каждой последующей букв, секретное слово используется многократно, пока не закончатся символы в исходном тексте.
Предположим, что нужно зашифровать такую фразу:
ATTACKATDAWN («Нападение на рассвете»)
Отправитель послания выбирает секретное слово и повторяет его до окончания исходного текста. Например, LEMON.
LEMONLEMONLE
Для зашифровки первого символа нужно совместить строку A со столбцом L (в результате получается L), для шифрования второго символа - строку T со столбцом E (в результате получается X) и так далее. Вот как выглядит результат:
Исходный текст: ATTACKATDAWN
Ключевое слово: LEMONLEMONLE
Шифротекст: LXFOPVEFRNHR
Расшифровка выполняется таким же способом: буква в тексте послания (диагональные строки таблицы) совмещается с буквой секретного слова в столбцах или строках таблицы.
Дисковый шифр Джефферсона
В конце 18 века Томас Джефферсон придумал шифровальную систему, очень похожую на шифр Виженера, но с лучшей защитой. Его шифратор состоял из 26 дисков с буквами алфавита, случайно размещёнными на каждом. Диски были пронумерованы и установлены на цилиндр в определённом порядке. Ключом является порядок дисков на оси.
Дисковый шифр Джефферсона
Чтобы зашифровать сообщение, нужно составить исходный текст в одной из строк цилиндра. Зашифрованным текстом будет любая другая строка. Получатель сообщения должен расположить диски в правильном порядке, после чего составить строку зашифрованного текста на цилиндре. Затем быстрый визуальный осмотр цилиндра сразу выявит текст исходного сообщения. Практически нулевая вероятность, что в строках цилиндра появится два не лишённых смысла сообщения.
Как и Альберти, Джефферсон никогда не использовал свою систему шифрования. В начале 20 века шифровальщики американской армии придумали заново цилиндр Джефферсона, ничего не зная об этом изобретении. Джефферсон опередил своё время более чем на сто лет. Армия США использовала такую систему шифрования с 1923 по 1942 годы.
ВВЕДЕНИЕ…………………………………………………….3
Теоретическая часть…………………………………...4
Криптология в Древнем мире……………………………………..4
Криптология в средние века………………………………………5
Криптология в позднее средневековье и эпоху Возрождения…..6
Криптология в период с XVIII века до середины XX века……….9
Криптография и криптоанализ в России………………………...12
ЗАКЛЮЧЕНИЕ………………………………………………...14
ПРАКТИЧЕСКАЯ ЧАСТЬ………………………………….16
Общая характеристика задачи…………………………………...16
Описание алгоритма решения задачи…………………………….17
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ…………….22
ПРИЛОЖЕНИЯ………………………………………………...23
ВВЕДЕНИЕ
Криптография - тайнопись, специальная система изменения обычного письма, используемая с целью сделать текст понятным лишь для ограниченного числа лиц, знающих эту систему.
Криптография в прошлом использовалась лишь в военных целях. Однако сейчас, по мере образования информационного общества, криптография становится одним из основных инструментов, обеспечивающих конфиденциальность, доверие, авторизацию, электронные платежи, корпоративную безопасность и бесчисленное множество других важных вещей. Справедливости ради надо отметить, что криптография - не панацея от всех бед. Криптографические методы могут помочь обеспечить безопасность, но только на эти методы надеяться не следует. Криптографические методы могут применяться для решений следующих проблем безопасности:
Конфиденциальности передаваемых/хранимых данных;
Аутентификации;
Целостности хранимых и передаваемых данных;
Обеспечения подлинности документов Базовых методов преобразования информации, которыми располагает криптография, среди них встречаются: шифрование (симметричное и несимметричное), вычисление хэш функций, генерация электронной цифровой подписи, генерация последовательности псевдослучайных чисел.
История развития криптографии: выделение этапов эволюции науки;
История развития криптографии в России.
1 Теоретическая часть
1.1 Криптология в Древнем мире
Некоторые системы шифрования дошли до нас из глубокой древности. Вероятнее всего, они появились одновременно с письменностью в 4 тысячелетии до нашей эры. Методы секретной переписки были изобретены во многих древних обществах, таких как Египет, Шумер и Китай, но детальное состояние криптологии в них неизвестно. С развитием фонетического письма письменность резко упростилась. Что послужило стимулом для развития криптографии. Примеры шифровок можно найти даже в Библии. Тексты в ней шифровались простой заменой: вместо первой буквы алфавита писалась последняя, вместо второй - предпоследняя и так далее.
Принципиально иной шифр, более древний, был связан с перестановкой букв сообщения по определенному, известному отправителю и получателю правилу. Для прочтения шифровки нужно было знать не только систему засекречивания, но и обладать ключом в виде палочки, принятого диаметра. Этот шифр назывался скитала.
За два века до нашей эры греческий писатель и историк Полибий изобрел так называемый полибианский квадрат размером 5х5, заполненный алфавитом в случайном порядке. Для шифрования на квадрате находили букву текста и вставляли в шифровку нижнюю от нее в том же столбце. Если буква была в нижней строке, то брали верхнюю из того же столбца.
Приборы для шифрования тоже существовали с древних времен. Одно из наиболее воинственных греческих государств, Спарта, имела хорошо проработанную систему секретной военной связи еще в V веке до нашей эры. С помощью скитала, первого известного криптографического устройства, спартанские эфоры шифровали послания, используя метод простой перестановки. Римляне в IV веке до нашей эры, чтобы упростить процедуру шифрования, стали применять шифрующие диски. Данные приборы использовались вплоть до эпохи Возрождения.
1.2 Криптология в средние века
С упадком античной цивилизации и образованием в Европе варварских государств, криптография потеряла свои позиции. Грамотность в то время была крайне низка, поэтому зашифровывать сообщения не было необходимости. К тому же и самих письменных сообщений практически не было. Только в период позднего средневековья криптография начинает постепенно возрождаться, становясь одним из важнейших инструментов политики, дипломатии и военного дела в раннее Новое время.
Помимо вышеперечисленных причин, криптография находилась в упадке еще и потому, что в ней видели элементы колдовства. Набор непонятных букв или символов, сам по себе похожий на заклинание, воспринимался как нечто магическое, а люди, извлекающие из этого набора символов смысл, расценивались как колдуны, что не могло не наложить свой отпечаток на отношение к ним в христианской Европе.
Однако в арабском мире криптография не только не пришла в упадок, а продолжала развиваться, достигнув значительных успехов. Первым дошедшим до нас источником арабского происхождения по криптографии можно считать книгу Абу-Бакра Набати «О большом стремлении человека разгадать загадки древней письменности», в которой автор изложил несколько известных ему шифралфавитов. Но познание арабов в области криптографии характеризует 14-ти томная энциклопедия Шебаха Калкашанди (1412 г.). Автор изложил все известные ему на тот момент криптографические системы, существовавшие в арабском мире. Калкандаши впервые предложил расшифровывать сообщения на основе статистики использования букв и их сочетаний в арабском алфавите, полученной в результате изучения Корана. Для расшифровки сообщения автор предлагал пересчитать все знаки сообщения и составить их статистику. Потом, соотнести ее со статистикой Корана и начать подстановку букв с наиболее часто встречающегося символа. На основе предположений выделяются сначала возможные двухбуквенные слова, затем трехбуквенные и т.д. Данный метод лежит в основе всей современной криптоаналитики.
Проблема использования криптографии и криптоаналитических методов арабами до сих пор остается неизученной, однако примерно с XV века уровень ее постепенно падает, а со временем наследие Калкандаши было почти полностью утрачено.
1.3 Криптология в позднее средневековье и эпоху Возрождения
В эпоху позднего средневековья криптография в Европе обретает «второе рождение», прежде всего в среде интеллектуальной элиты того времени. Средневековые ученые, сделав открытие, не всегда спешили публиковать его в письмах коллегам, как это было тогда принято при отсутствии периодических научных изданий. Они записывали свои открытия с помощью шифрования. Так ученые выяснили, что выдающимся английским ученым Р. Бэконом, был найден состав черного пороха. Однако считают его изобретателем Б. Шварца. Дело в том, что в труде Бэкона состав пороха был записан в виде зашифрованной анаграммы, которую до появления электронных вычислительных машин (ЭВМ) не удавалось вскрыть, и поэтому слава открытия приписывалась Шварцу.
Так какими же шифрами пользовались средневековые ученые? Главным образом, это были магические квадраты - квадратные таблицы с вписанными в их клетки последовательными натуральными числами от 1, которые дают в сумме по каждому столбцу, каждой строке и каждой диагонали одно и то же число. Магические квадраты больших размеров могли быть хорошей основой для надежной системы шифрования того времени, потому что ручной перебор всех вариантов ключа для этого шифра был очень велик.
Однако широкое развитие торговли в средние века потребовало использования более специфических шифров, предельно простых и удобных. Это были простые шифры, заключавшиеся в замене цифр на буквы, основанные на ключевом слове. Торговцы заранее договаривались об использовании общего ключевого слова, буквы которого соответствовали бы цифрам.
«Архитекторы и исследователи Италии эпохи Возрождения считают, что один из самых важных этапов ренессансной архитектуры связан с именем Леона Батиста Альберти. С другой стороны, криптологи всего мира признают его отцом своей науки. Главным достижением Альберти в криптологии было изобретение многоалфавитной замены, сделавшей шифровку очень устойчивой к вскрытию. В компьютере такая операция соответствует сложению кодов ASCII символов сообщения и ключа по некоторому модулю. Кажется, что если таблица будет более сложной, чем циклическое смещение строк, то шифр станет надежнее. Это действительно так, если ее менять чаще, например, от слова к слову. Но составление таких таблиц, представляющих собой латинские квадраты, где любая буква встречается в строке или столбце один раз, трудоемко и его стоит делать лишь на ЭВМ».
Вторым отцом современной криптологии, по мнению многих историков, считается Иоганн Трисемус, аббат из Германии. В 1508 году он написал "Полиграфию", первую печатную работу по криптологии, в которой систематически описал применение шифрующих таблиц, заполненных алфавитом в случайном порядке. Для получения такого шифра обычно использовались ключевое слово или фраза и таблица, которая для русского языка может иметь размер 5 х 6. Ключевое слово вписывалось в таблицу по строкам, а повторяющиеся буквы отбрасывались. Таблица дозаполнялась не вошедшими в нее буквами алфавита по порядку. Поскольку ключевое слово легко хранить в памяти, то такой подход упрощал процессы шифрования и дешифрования. Такие табличные шифры называются монограммными, так как шифрование ведется по одной букве. Трисемус первым заметил, что можно шифровать по две буквы за раз. Такие шифры были названы биграммными. Наиболее известный шифр биграммами называется Playfair. Шифрование биграммами резко усилило стойкость шифров к вскрытию.
Сами папы Римские пользовались услугами криптографов и выдающийся итальянский математик Джероламо Кардано состоял у них на службе. Он написал несколько книг по криптографии и дал описание метода трафаретов. Увлечение теорией магических квадратов привело Кардано к открытию нового класса шифров перестановок, названных решетками или трафаретами, которые представляют собой квадратные таблицы, где четверть ячеек прорезана так, что при четырех поворотах они покрывают весь квадрат. Вписывание в прорезанные ячейки текста и повороты решетки продолжаются до тех пор, пока весь квадрат не будет заполнен.
В конце XVII века Френсис Бекон, английский криптолог и мыслитель, обобщил все накопленные до него знания в области криптографии и окончательно выделил эту область знаний как самостоятельную научную дисциплину. Именно он впервые предложил и осуществил на практике кодирование букв латинского алфавита с помощью двузначных цифр, и сделал систему числовых обозначений общепринятой (хотя арабы использовали подобную систему более пяти веков назад, а в Европе об этом почти ничего не знали).
Таким образом, к концу XVII века криптография окончательно складывается как научная дисциплина. Появляются профессиональные криптоаналитики, соответствующие службы почти в каждой европейской стране, системы обучения профессиональных криптографов, появилось большое количество работ по криптографии и криптоанализу. Хотя в данный период господствовали номенклаторы, которые не являются шифрами в чистом виде, но, тем не менее, появление многоалфавитной замены, использование решеток, биграмм и цифровых обозначений стало огромным шагом вперед по сравнению с древнейшим периодом и олицетворяло наступление новой эры в развитии криптографии, вплотную приблизившейся к своему современному виду.
1.4 Криптология в период с XVIII века до середины XX века
XVIII век стал для криптологии периодом застоя, можно даже сказать ее упадка. Большой скачок, который эта наука сделала в предшествующий период, позволил в течение почти 150 лет не вводить никаких нововведений в способы шифрования и дешифровки сообщений. Разработанные ранее криптографические системы успешно применялись на практике, а трактаты XVI-XVII вв. служили учебными пособиями для криптоаналитиков. «Существовавшие шифры замены были довольно устойчивы, но и квалификация криптоаналитиков была высокой настолько, что большинство значимых сообщений расшифровывалось. Это время стало периодом расцвета номенклаторов. Этот тип криптографической системы, постепенно усложнявшийся на протяжении трех предшествующих веков, достиг в XVIII пика своего развития. Стандартным был размер номенклатора в 400-500 символов, но были и такие, которые достигали 5-6 тысяч, заменяя особыми символами практически все значимые понятия, имена, названия и целые предложения. В этот период номенклаторы стали походить больше не на шифр, а на форму иероглифического письма, и, несмотря на это, их все же взламывали».
К началу XIX века ситуация не изменилась, несмотря на бурные события, происходившие в Европе. Она начинает меняться только в середине XIX века вместе с появлением новых средств связи и значительной активизации дипломатических связей в Европе после революций 1830-1840-х годов. На успешное развитие криптографии оказало большое влияние рост коммерции и активность средств массовой информации, тщательно хранящих свои секреты. При этом к новым шифрсистемам предъявлялись все более высокие требования по устойчивости и одновременно простоте и возможности массового использования.
В 1854 году англичанин Чарльз Уинстон изобрел новую криптографическую систему, которая значительно повысила устойчивость шифров к взлому. Для шифрования биграмм он применил так называемый «двойной квадрат», в котором использовалось сразу две горизонтально расположенных таблицы, а шифрование сообщения происходило, как и в шифре Трисемуса.
Во второй половине XIX века применение криптографии становится по-настоящему массовым. В Англии и США появляются даже специальные периодические издания по криптографии, выходит множество специальных трудов, посвященных различным аспектам этой науки. В это время закладываются основные принципы криптографии, определившие ее развитие в течение первой половины ХХ века.
Примерно в это же время начинают появляться и первые шифрующие машины. Это было связано с необходимостью оперативной шифровки и дешифровки телеграфных сообщений. Следует заметить, что прообраз такой машины был предложен еще Томасом Джефферсоном в 1790 году, но он не использовался на практике вплоть до начала ХХ века. В 1891 году Этьен Базери предложил довольно простую машину для шифрования сообщений, получившую название «цилиндр Базери» и широко применявшуюся в начале ХХ века как во французской армии, так и в коммерческих структурах. 20 колес, с нанесенным на них в случайной последовательности алфавитом, одевались в определенном ключом порядке на одну ось, поворачивались до тех пор, пока в одном ряду не набирали первые 20 букв сообщения, после чего шифровку считывали с другого ряда, также определяемого ключом, после чего операция повторялась. На этом, весьма простом принципе создавались большинство шифровальных машин вплоть до Второй мировой войны.
Однако в 1917 году Эдвард Хеберн совершил революцию механизации криптографического дела, заложив в свою машину принцип, который до сих пор является основным при создании подобного типа устройств. Его машина под названием «Энигма» стала самой известной шифровальной машиной за всю историю криптографии, а благодаря ряду усовершенствований, не затрагивающих самого принципа работы, также с большим успехом использовалась до конца Второй мировой войны, несмотря на то, что шифровки можно было с легкостью взламывать как с помощью устройства, так и не прибегая к нему, то есть вручную.
Создание сложных и эффективных шифровальных машин и использование ЭВМ в криптоаналитической работе обозначили наступление нового, современного этапа развития криптологии, теоретическое оформление которого дал Элвуд Шелдон, встроив криптографию в общую теорию информации. Согласно его теории случайная последовательность символов не несет никакого смысла, но путем анализа статистических свойств самой шифровки, ключа, языка и предполагаемого содержания сообщения можно выявить конкретное содержание зашифрованного сообщения.
Несмотря на появление ЭВМ и использования их в криптографии и криптоанализе, нельзя говорить о том, что ручной шифр стал в наши дни неэффективен. Тот же полибианский квадрат, известный уже более двух тысяч лет, при незнании ключа и довольно незначительной длине сообщения крайне сложно расшифровать, даже с применением самых современных систем, не говоря уже о других, более совершенных шифрсистемах.
Для этого этапа развития криптографии характерно следующее:
защите подвергались только текстовые сообщения, написанные на естественных языках;
шифрование поначалу осуществлялось вручную, а позднее были изобретены простые механические приспособления, поэтому использовавшиеся тогда шифры были несложными;
криптография и криптоанализ были скорее искусством, чем наукой, научный подход к построению шифров и их раскрытию отсутствовал;
криптография использовалась в очень узких сферах - только для верхушек государства и военных целей;
основная задача криптографии состояла в защите передаваемых сообщений от несанкционированного ознакомления с ними.
1.5 Криптография и криптоанализ в России
Ученые не могут точно сказать использовались ли методы шифрования в Древней Руси. Однако дошедшие до наших дней письменные памятники свидетельствуют о том, что русские в то время для сокрытия информации использовали, в основном, греческую азбуку. Другим распространенным методом шифрования информации была так называемая тахиграфия – изменение начертаний букв, когда писалась или часть буквы, или наоборот, ее написание дополнялось новыми элементами. Также применялись более простые методы шифрования, например, замена согласных на противоположную.
«Однако информации об использовании криптографии до XVI века на Руси нет. Только с конца XVI века русские послы начинают использовать простейшие методы шифрования в своих донесениях. Однако они были примитивны. В XVII веке ситуация немного налаживается, но потребность в криптографии становится более острой. И в начале XVIII века достигает своего пика. Ее решение было связано с именем Петра I. Он создал регулярную криптографическую службу. Однако Петр понимал, что Россия отстает по своему развитию от западных стран и складывающейся службе необходим был опыт. Он решил пригласить в Россию ведущих криптологов».
Не смотря на все усилия Петра, российская криптология и сделала гигантский рывок вперед, однако вышла на уровень западных стран только в 40-е годы XVIII века. В некоторых моментах она даже превосходила криптологию европейского уровня.
В течение второй половины XVIII века никаких существенных изменений в российской криптологии не происходило. И система, созданная Петром, работала вплоть до второй половины XIX века. В 1860-х годах для более эффективного использования криптографических систем в армии и полиции в соответствующих министерствах были созданы криптологические отделы, призванные активнее внедрять криптографию с существующие системы связи. Но все их шифровки были основаны на принципе простой замены.
Появление в начале ХХ века радиосвязи значительно повысило требования к стойкости армейских шифров, в условиях, когда почти каждое сообщение могло быть перехвачено противником. К началу Первой мировой войны для русской армии был создан сложный шифр двойной перестановки с частой сменой ключей, представлявший проблему для самых опытных криптоаналитиков того времени. В период с конца Первой мировой войны до начала Второй мировой войны русские криптологии совершенствовали свои методы шифрования и уже с окончанием Второй мировой войны, Советский Союз вступил в острое противостояние с Западом, что в значительной степени способствовало развитию отечественной криптологии, занявшей лидирующие позиции в ХХ веке, однако это был уже новый, современный этап развития криптологической науки.(.......)
