Глава 5. Основы криптографии
Зачем нужна криптография
Криптография бывает разная. Есть криптография, которая не позволяет вашему малолетнему сынишке насладиться созерцанием изображений обнаженной натуры, втайне переписанных вами ночью из сети Internet на домашний компьютер. Но кроме этого существует и криптография, которая не дает вашему правительству узнать про вас то, что вы не хотите, чтобы оно знало.
Если я напишу письмо, положу его в сейф, а сейф спрячу подальше от посторонних глаз и на спор попрошу вас прочесть мое письмо, — это не безопасность, а банальная игра в прятки. Но если я предоставлю вам свободный доступ не только к моему запертому сейфу, но и к сотне других подобных ему сейфов, к их ключевым комбинациям, позволю вам и лучшим взломщикам сейфов в мире во всех подробностях изучить конструкцию моего сейфа вместе с замком, но все равно никто не сможет открыть мой сейф и прочесть находящееся в нем письмо — вот это настоящая безопасность!
В течение многих лет такая криптография была прерогативой исключительно военных. Агентство национальной безопасности (АНБ) в США, а также соответствующие ведомства в Англии, России, и в других развитых странах тратили огромные деньги на обеспечение безопасности собственных линий связи и на добывание полезной информации из чужих. А простые граждане, не имея достаточных финансовых средств и не обладая необходимыми знаниями, были бессильны защитить свою частную жизнь от вмешательства со стороны государства.
За последние 20 лет положение в корне изменилось. Этому способствовали чрезвычайно интенсивные научные исследования в области криптографии, которые привели к тому, что современная компьютерная криптография "обитает" не только в стенах строго охраняемых военных учреждении, но и на страницах общедоступных журналов, монографии и учебников. Теперь при желании кто угодно может зашифровать свои данные таким образом. чтобы защитить их от самого могущественного противника — правительственных ведомств, специализирующихся на краже информации.
Нуждается ли рядовой обыватель в подобной защите? Конечно, нуждается. Под ее прикрытием он может вести учет своих финансовых затрат, не опасаясь, что с ними ознакомятся налоговые службы. Он может разрабатывать новое изделие для последующей выгодной продажи на рынке, надежно пряча детали своей разработки от конкурентов. Он может завести любовницу и не бояться, что волей случая жена окажется посвященной в подробности его тайной любовной переписки. Ведь любой не застрахован от ситуации, котла он занимается какой-то деятельностью, которую он сам не считает незаконной, но которая впоследствии может быть объявлена кем-то вне закона. Каковы бы ни были причины, человек имеет право на частную жизнь, в том числе — на сохранение в тайне любых сведений, которые он сочтет нужным не предавать огласке. И никому, в том числе и государству, не должно быть до них никакого дела.
На практике все обстоит совершенно иначе. Своим Указом № 334 от 3 апреля 1995 г. президент России строго-настрого запретил "деятельность юридических и физических лиц, связанную с разработкой, производством, реализацией и эксплуатацией шифровальных средств, |...| предоставлением услуг в области шифрования информации", без государственных лицензий. А российские спецслужбы обязал "осуществлять выявление юридических и физических лиц, нарушающих требования настоящего Указа". Что с такими лицами будут делать — вырывать им ноздри или просто ставить клеймо на лоб, чтобы другим неповадно было, — в президентском Указе не сказано. Но и без этого у государственных чиновников в России появились все необходимые полномочия, чтобы при необходимости можно было воспрепятствовать внедрению надежных систем криптографической защиты информации. Надо сказать, что аналогично действует и американское правительство, которое путем введения государственного стандарта шифрования с передачей ключей на хранение пытается узаконить для себя право шпионить за своими гражданами.
Таким образом, становится совершенно очевидно, что надежность шифровальных средств — традиционно лишнее качество для "Большого брата", независимо от его национальной принадлежности. Совершенно в духе знаменитого романа "1984", принадлежащего перу английского писателя Джорджа Оруэлла, звучат аргументы сторонников введения ничем не ограниченного права государства на перехват информации частного характера. Они заявляют, что с человеком, которому есть что скрывать от собственного государства, происходит что-то неладное, поэтому к нему необходимо как следует присмотреться.
В любом демократическом государстве правоохранительным органам традиционно предоставлялась возможность на законных основаниях вести слежку, если разрешение на нее было получено в судебном порядке. Ныне этого недостаточно: правительства принуждают своих граждан самих принять все необходимые меры, чтобы можно было без помех вести за ними наблюдение. Тем самым государственная власть узурпирует права, которые в демократическом государстве должны принадлежать народу. И если в такой стране начнет править диктатор, его власть будет неограниченном. Свергнуть его будет невозможно, ибо любая попытка граждан объединиться вместе, чтобы противостоять диктатуре, станет ему известна. Настолько всемогущей является современная технология.
В связи с вышесказанным необходимо, чтобы все спецслужбы, которые обладают правом доступа к современным техническим средствам слежки зa гражданами своей страны, действовали в рамках законности и под контролем компетентных органов, подотчетных народу, ибо пересечь обратно границу, один раз перейденную в направлении от демократии к диктатуре, будет уже невозможно. Ведь даже в США — стране с самой развитой, по общему признанию, демократией в мире, никто не имеет достаточных гарантий того, что не разделит судьбу многих честных соотечественников, которые в разное время подвергались преследованию только потому, что по убеждения были неугодны властям.
Самая затяжная и беспощадная война нашего столетия ведется поразительно тихо. В ней обходятся без ракетно-бомбовых ударов и без расстрела заложников. Однако и здесь порочат, калечат и уничтожают людей точно так же, как и на обычной войне. А отвоевываются не чужие территории или право распоряжаться судьбами побежденных, а информация. И противостоят друг другу не "хорошие" и "плохие" парни, даже не озверевшие наемники. а государство и его граждане.
В информационной войне государство пользуется двумя основными видами оружия. Во-первых, в любую сертифицированную государством систему защиты информации встраивается так называемый потайной ход. который иногда еще именуют лазейкой. Еще в 1991 г. в сенат США был внесен законопроект, который требовал, чтобы любое американское криптографическое оборудование содержало потайной ход, известный АН Б. Поэтому совершенно не удивительно, что один из крупнейших разработчиков криптографического оборудования в США — компания AT&T — нисколько не скрывает того факта, что у американского правительства есть "ключики" "потайных ходов", ведущих во все ее системы вне зависимости от тою. насколько сложные пароли придумают неискушенные пользователи.
Второй способ обмана граждан является более изощренным и состоит в применении системы с депонированием ключей. В этом случае прочесть сообщение можно только при наличии всех частей ключа, использованного для засекречивания этого сообщения. Тайна переписки гарантируется до тех пор, пока государству не понадобится с ней ознакомиться. Тогда стоит заручиться согласием, скажем, тех доверенных лиц или организаций, которым были отданы на хранение части ключа, — и тайное станет явным. В США данный подход был подвергнут справедливой критике со стороны большинства специалистов, а корпоративные пользователи с негодованием отвергли саму идею довериться правительству в таком деликатном вопросе, как коммерческая тайна. И это в законопослушной Америке, где ставшие явными попытки спецслужб вторгнуться в частную жизнь своих граждан встречают немедленный и достойный отпор!
Из сказанного следует сделать один важный вывод. Недостаточно уметь защищать себя с помощью закона, непременно требуется еще и криптографическая защита. Шифрование играет слишком большую роль в современном мире, чтобы отдать его на откуп государству.
Криптографические средства можно объявить вне закона. Но ваша личная информация всегда будет легальной, и, следовательно, должна быть надежно защищена от посторонних.
Терминология
Шифрование и расшифрование
Предположим, что отправитель хочет послать сообщение получателю. Более того, отправитель желает засекретить это сообщение, чтобы никто, кроме получателя, не смог его прочитать.
Сообщение состоит из открытого текста. Процесс преобразования открытого текста с целью сделать непонятным его смысл для посторонних называется шифрованием. В результате шифрования сообщения получается шифр-текст. Процесс обратного преобразования шифртекста в открытый текст называется расшифрованием.
Наука, которая учит, как следует поступать, чтобы сохранить содержание сообщений в тайне, называется криптографией. Людей, занимающихся криптографией, зовут криптографами. Криптоаналитики являются специалистами в области криптоанализа — науки о вскрытии шифров, которая отвечает на вопрос о том, как прочесть открытый текст, скрывающийся пол шифрованным. Раздел науки, объединяющий криптографию и криптоанализ, именуется криптологией.
Обозначим открытый текст буквой Р (от английского слова plaintext). Это может быть текстовый файл, битовое изображение, оцифрованный звук — что угодно. Единственное ограничение связано с тем, что, поскольку, прел метом изложения является компьютерная криптография, под Р понимание;; исключительно двоичные данные.
Шифртекст обозначается буквой С (от английского слова ciphertext) и также представляет собой двоичные данные. Объем полученного шифртекста иногда совпадает с объемом соответствующего открытого текста, а иногда превышает его. После зашифрования преобразованный открытый текст может быть передан по каналам компьютерной сети или сохранен в памяти компьютера.
На вход функции шифрования Е подается Р, чтобы на выходе получить С.
В обозначениях, принятых в математике, это записывается как:
Е(Р) = C
При обратном преобразовании шифртекста в открытый текст на вход функции расшифрования D поступает С, а на выходе получается Р:
D(C) = М
Поскольку смысл любого криптографического преобразования открытого текста состоит в том, чтобы потом этот открытый текст можно было восстановить в первозданном виде, верно следующее соотношение:
D(E(P)) = Р
Аутентификация, целостность и неоспоримость
Помогая сохранить содержание сообщения в тайне, криптография может быть использована, чтобы дополнительно обеспечить решение следующих задач:
Перечисленные задачи часто приходится решать на практике для организации взаимодействия людей при помощи компьютеров и компьютерных сетей. Подобные же задачи возникают и в случае личностного человеческого общения: часто требуется проверить, а действительно ли ваш собеседник тот, за кого он себя выдает, и подлинны ли предъявленные им документы. будь то паспорт, водительское удостоверение или страховой полис. Вот почему в обыденной жизни не обойтись без аутентификации, проверки целостности и доказательства неоспоримости, а значит и без криптографии.
Шифры и ключи
Криптографический алгоритм, также называемый шифром или алгоритмом шифрования, представляет собой математическую функцию, используемую для шифрования и расшифрования. Если быть более точным, таких функций две: одна применяется для шифрования, а другая — для расшифрования.
Когда надежность криптографического алгоритма обеспечивается за счет сохранения в тайне сути самого алгоритма, такой алгоритм шифрования называется ограниченным. Ограниченные алгоритмы представляют значительный интерес с точки зрения истории криптографии, однако совершенно непригодны при современных требованиях, предъявляемых к шифрованию. Ведь в этом случае каждая группа пользователей, желающих обмениваться секретными сообщениями, должна обзавестись своим оригинальным алгоритмом шифрования. Применение готового оборудования и стандартных программ исключено, поскольку тогда любой сможет приобрести это оборудование и эти программы и ознакомиться с заложенным в них алгоритмом шифрования. Придется разрабатывать собственный криптографический алгоритм, причем делать это надо будет каждый раз, когда кто-то из пользователей группы захочет ее покинуть или когда детали алгоритма случайно станут известны посторонним.
В современной криптографии эти проблемы решаются с помощью использования ключа, который обозначается буквой К (от английского слова key). Ключ должен выбираться среди значений, принадлежащих множеству, которое называется ключевым пространством. И функция шифрования Е, и функция расшифрования D зависят от ключа. Сей факт выражается присутствием К в качестве подстрочного индекса у функций Е и D:
Е к (Р) = С
D к (С) = Р
По-прежнему справедливо следующее тождество:
D k (E k (P)) = P
Некоторые алгоритмы шифрования используют различные ключи для шифрования и расшифрования. Это означает, что ключ шифрования К 1 отличается от ключа расшифрования К 2 . В этом случае справедливы следующие соотношения:
Е к 1 ( P ) = С
D k2 (С) = Р
D k2 (E k1 (Р) ) = Р
Надежность алгоритма шифрования с использованием ключей достигается., за счет их надлежащего выбора и последующего хранения в строжайшем секрете. Это означает, что такой алгоритм не требуется держать в тайне. Можно организовать массовое производство криптографических средств, основу функционирования которых положен данный алгоритм. Знание криптографического алгоритма не позволит злоумышленнику прочесть зашифрованные сообщения, поскольку он не знает секретный ключ, использованный для их зашифрования.
Под криптосистемой понимается алгоритм шифрования, а также можно всевозможных ключей, открытых и шифрованных текстов.
Симметричные алгоритмы шифрования
Существуют две разновидности алгоритмов шифрования с использованием ключей — симметричные и с открытым ключом. Симметричным называют криптографический алгоритм, в котором ключ, используемый для шифрования сообщений, может быть получен из ключа расшифрования и наоборот. В большинстве симметричных алгоритмов применяют всего один ключ. Такие алгоритмы именуются одноключевыми, или алгоритмами с секретным ключом, и требуют, чтобы отправитель сообщений и их получатель и рапсе условились о том, каким ключом они будут пользоваться. Надежность одноключевого алгоритма определяется выбором ключа, поскольку его значение дает возможность злоумышленнику без помех расшифровывать все перехваченные сообщения. Поэтому выбранный ключ следует хранить в тайне от посторонних.
Шифрование и расшифрование в симметричных криптографических алгоритмах задаются уже знакомыми формулами:
Е к (Р) = С
D к (С) = Р
Симметричные алгоритмы шифрования бывают двух видов. Одни из них обрабатывают открытый текст побитно. Они называются потоковыми алгоритмами, или потоковыми шифрами. Согласно другим, открытый текст разбивается на блоки, состоящие из нескольких бит. Такие алгоритмы называются блочными, или блочными шифрами. В современных компьютерных алгоритмах блочного шифрования обычно длина блока составляет 64 бита.
Алгоритмы шифрования с открытым ключом
Алгоритмы шифрования с открытым ключом, также называемые асимметричными алгоритмами шифрования, устроены так, что ключ, используемый для шифрования сообщений, отличается от ключа, применяемого для их расшифрования. Более того, ключ расшифрования не может быть за обозримое время вычислен , ходя из ключа шифрования. Свое название алгоритмы с открытым ключом получили благодаря тому, что ключ шифрования не требуемся держать в тайне. Любой может им воспользоваться, чтобы зашифровать свое сообщение, но только обладатель соответствующего секретного ключа расшифрования будет в состоянии прочесть это шифрованное сообщение. Ключ шифрования обычно называют открытым ключом, а ключ расшифрования — тайным ключом. Иногда тайный ключ называют также секретным, однако чтобы избежать путаницы с симметричными алгоритмами, это название не будет использоваться при дальнейшем изложении.
Несмотря на юг факт, что сообщения шифруются с помощью открытого ключа, а расшифровываются с помощью тайного ключа, процесс шифрования и расшифрования все равно записывается так:
Е k (Р) - С
D к (С) = Р
Иногда сообщения шифруются с использованием тайного ключа, а расшифровываются посредством открытого ключа. Несмотря на возможную путаницу, этот факт математически по-прежнему выражается в виде:
Е к (Р) = С
D k (C) = Р
Криптоаналитические атаки
Криптография ставит своей целью сохранение переписки в тайне от посторонних людей, которые захотят с ней ознакомиться. Таких людей криптографы называют злоумышленниками, противниками, перехватчиками или просто врагами. При этом предполагается, что они могут перехватывать любые сообщения, которыми обмениваются отправитель и получатель.
Криптоанализ заключается в получении доступа к открытому тексту шифрованного сообщения. В ходе успешного криптоаналитического исследования криптосистемы может быть найден не только открытый текст, но и сам ключ. Криптоаналитик занимается поисками слабостей в криптосистеме, которые могут позволить ему прочесть шифрованное сообщение, или отыскать ключ, или и то, и другое вместе. Если противник узнал ключ не с помощью криптоанализа, а каким-то другим способом (выкрал или купил), то говорят, что ключ был скомпрометирован.
Попытка криптоанализа называется атакой. Успешная криптоаналитическая атака зовется взломом, или вскрытием.
В современной криптологии принято считать, что надежность шифра определяется только секретностью используемого ключа. Правило, впервые сформулированное голландцем А. Керкхоффом (1835—1903), гласит о том, что весь механизм шифрования, за исключением значения ключа, предположительно известен противнику. Это предположение является довольно естественным. Например, хотя ФАПСИ вряд ли знакомит АНБ со своими криптографическими алгоритмами, какое-то представление о них там вес равно имеется. Следовательно, правило Керкхоффа является относительно хорошим допущением при рассмотрении надежности алгоритмов шифрования. Если шифр невозможно взломать, зная абсолютно все детали алгоритма шифрования, значит это тем более нельзя сделать, не обладая подобными знаниями во всей их полноте.
Известны 4 основных типа криптоаналитических атак. При рассмотрении каждой из них подразумевается, что криптоаналитик в курсе всех детален подвергаемого криптоанализу алгоритма шифрования.
1. Атака со знанием только шифртекста. В распоряжении криптоанадитпка имеются несколько сообщений, которые были зашифрованы с использованием одного и того же алгоритма шифрования. Задача криптоаналитика состоит в нахождении открытого текста наибольшего числа перехваченных сообщений. Он может также попытаться найти ключи, которые применялись для шифрования этих сообщений, чтобы потом прочесть другие сообщения, зашифрованные с использованием тех же ключей.
Дано:
С 1 = E k1 (P 1 ), С 2 = E k2 (P 2 ),..., С i = E ki (P i ).
Найти:
P 1 , P 2 , ..., Р i или К 1 , К 2 , ..., K i .
2. Атака со знанием открытого текста. Криптоаналитик имеет доступ не только к шифрованным текстам нескольких сообщений, но и знает их открытые тексты. От него требуется найти ключи, которые использовались для шифрования этих сообщений.
Дано:
P 1 , C 1 = E k1 (P 1 ), P 2 , C 2 = E k2 (P 2 ),..., P i , C i = E ki (P i ).
Найти:
K 1 , K 2 , . . , K i .
3. Атака с выбранным открытым текстом. Криптоаналитик не только знает шифрованные и открытые тексты нескольких сообщений, но и может определять содержание этих сообщений. Данная разновидность крипто-аналитической атаки является более мощной по сравнению с атакой со знанием открытого текста, поскольку здесь криптоаналитик может по своему усмотрению выбирать открытый текст, подлежащий зашифрованию, и, тем самым, получать больше информации об используемых ключах. Его задача по-прежнему состоит в нахождении ключей.
Дано:
P 1 , C 1 = E k 1 (P 1 ), P 2 , C 2 = E k 2 (P 2 ),..., P i ,
где С i = Е к i ( P i ), где P 1 , P 2 ,. . . , Pi выбраны криптоаналитиком.
Найти: К 1 , К 2 , . . . , K i .
4. Адаптивная атака с выбранным открытым текстом. Эта атака является разновидностью атаки с выбранным открытым текстом. Криптоаналитик не только выбирает открытые тексты посылаемых шифрованных сообщений, но и может менять свой выбор в зависимости от результатов их шифрования.
Имеются по крайней мере еще 3 разновидности криптоаналитических атак.
1. Атака с выбранным шифртекстом. Криптоаналитику предоставлена возможность выбора шифртекстов, подлежащих расшифрованию получателем. Он также имеет доступ к соответствующим открытым текстам. Требуется найти ключи.
Дано:
С 1 , P 1 = D k1 ( C 1 ) , С 2 , P 2 = D k2 ( C 2 ) , ..., С i , P i = D ki ( C i ).
Найти :
K 1 , K 2, . . . , K i . Этой криптоаналитической атаке, как правило, подвергаются алгоритмы шифрования с открытым ключом. Хотя иногда она эффективна и против симметричных криптосистем. Атаку с выбранным открытым текстом и с выбранным шифртектом называют атакой с выбранным текстом.
2. Атака с выбранным ключом. В ходе этой атаки криптоаналитик обладает некоторыми знаниями относительно правил, по которым отправитель и получатель сообщений выбирают ключи шифрования.
3. Атака с применением грубой силы. Криптоаналитик занимается подкупом, шантажом или пытками, чтобы получить сведения, необходимые ему для взлома криптосистемы. Подкуп иногда выделяют в отдельную категорию и называют атакой с покупкой ключа. Эти атаки являются очень эффективными и зачастую предоставляют наиболее легкий путь для получении доступа к открытым текстам шифрованных сообщений.
Атаки со знанием открытого текста и с выбранным открытым текстом не так уж редко встречаются на практике, как можно подумать. Известны случаи, когда криптоаналитику удавалось подкупить шифровальщика, чтобы он зашифровал сообщение, открытый текст которого известен криптоаналитику. Иногда даже не требуется никого подкупать, поскольку открытые тексты многих сообщений начинаются и заканчиваются стандартными фразами.
С этой точки зрения зашифрованная программа на языке С особенно уязвима, поскольку содержит множество зарезервированных слов типа # define, # include, if, then и do.
Не следует забывать и о правиле Керкхоффа. Попытка добиться высоко-надежности криптографического алгоритма за счет сохранения в тайне принципов его работы является малопродуктивной. Криптоаналитпк может выполнить дизассемблирование любой сверхсложной программы шифрования и методом обратного проектирования воспроизвести алгоритм, положенный в основу ее функционирования. Такое случается довольно част. Лучшие алгоритмы шифрования являются общественным достоянием уже в течение многих лет, и над их взломом продолжают безуспешно трудиться самые способные криптоаналитики в мире.
Надежность алгоритма шифрования
Различные криптографические алгоритмы обладают разной надежностью, чаще называемой стойкостью алгоритма шифрования или стойкостью шифра. Стойкость зависит от того, насколько легко криптоаналитик может взломам, шифр. Если при этом стоимость затрат превышает ценность полученной в 4 результате информации, то владельцу этого шифра, возможно, и беспокоиться не о чем. Если время, потраченное на взлом шифра, больше, чем период, и течение которого ваши данные должны храниться в секрете, то они вероятно вне опасности. Если противник не накопил достаточного количества ваших сообщений, зашифрованных с помощью одного ключа, чтобы суметь определить этот ключ, время его менять, может быть, еще и не пришло.
Слова "может быть", "вероятно" и "возможно" употреблены здесь не зря. Ведь всегда существует шанс, что в криптоанализе произойдут революционные изменения. Свести к минимуму вредные последствия очередного такого прорыва поможет соблюдение простого правила: ценность секретных данных должна быть всегда ниже, чем стоимость преодоления защитных средств, используемых для сохранения этих данных в тайне.
Под вскрытием (взломом) шифра обычно понимается решение одной из перечисленных ниже задач:
Криптографический алгоритм называется безусловно стойким, если вне зависимости от того каким объемом перехваченного шифртекста располагает криптоаналитик, у него нет достаточной информации, чтобы восстановить исходный открытый текст. Существует всего один безусловно стойкий шифр (о нем речь пойдет ниже). Все остальные шифры можно вскрыть с помощью атаки со знанием только шифртекста: достаточно перебрать все возможные ключи и проверить, имеет ли смысл открытый текст, полученный с их помощью.
Сложность криптоаналитической атаки
Сложность криптоаналитической атаки на алгоритм шифрования может быть охарактеризована с помощью трех величин:
Часто под сложностью криптоаналитической атаки понимается максимальная среди этих величин. А для некоторых атак приходится искать компромисс между сложностью по данным, вычислительной сложностью и сложностью по памяти. Например, для реализации более быстрой атаки может потребоваться дополнительная память.
Сложность криптоаналитической атаки, как правило, выражается в виде экспоненциальной функции. К примеру, если атака имеет сложность 2 128 , то это значит, что для взлома шифра требуется выполнить 2 128 операций.
При оценке сложности атаки часто приходится оперировать очень большими числами. Чтобы было понятно, насколько они велики, в табл. 5.1 для них приведены некоторые физические аналогии.
Таблица 5.1. Физические аналогии для очень больших чисел
| Физическая аналогия |
Число |
|
Время, оставшееся до наступления следующего ледникового периода |
16-10 3 (2 14 ) лет |
|
Время, оставшееся до превращения Солнца в новую звезду |
10 9 (2 30 ) лет |
|
Возраст Земли |
10 9 (2 30 ) лет |
|
Возраст Вселенной |
10 10 (2 32 ) лет |
|
Количество атомов, из которых состоит Земля |
10 51 (2 170 ) |
| Количество атомов, из которых состоит Солнце | 10 57 (2 190 ) |
| Количество атомов, из которых состоит наша Галактика | 10 67 (2 223 ) |
| Количество атомов, из которых состоит Вселенная | 10 77 (2 265 ) |
| Объем Вселенной | 10 84 (2 280 )см 3 |
В то время как сложность атаки на данный алгоритм шифрования является постоянной величиной (по крайней мере, до тех пор, пока криптоаналитик не придумает более эффективный метод взлома), вычислительная мощь современных компьютеров растет буквально не по дням, а по часам. Такой феноменальный рост наблюдается в течение последних пятидесяти лет, и есть все основания полагать, что в ближайшее время данная тенденция сохранится. Большинство криптоаналитических атак идеально подходят для реализации на параллельных компьютерах: полномасштабная атака на шифр разбивается на миллионы крошечных атак, которые ведутся независимо друг от друга и, следовательно, не требуют организации взаимодействия между процессорами. Поэтому в корне неверно заявлять о достаточной вычислительной стойкости алгоритма шифрования только потому, что его невозможно взломать при современном уровне развития технологии. Хорошая криптосистема всегда проектируется с достаточным запасом на будущее.
При этом необходимо принимать во внимание прогнозируемый рост компьютерной производительности, чтобы алгоритм шифрования оставался вычислительно стойким в течение многих лет.
Шифры замены и перестановки
Шифры появились на свет задолго до изобретения компьютера. Получившие широкое распространение криптографические алгоритмы выполняли либо замену одних букв на другие, либо переставляли буквы друг с другом. Самые стойкие шифры делали одновременно и то, и другое, причем многократно.
Шифры замены
Шифром замены называется алгоритм шифрования, который производит замену каждой буквы открытого текста на какой-то символ шифрованного текста. Получатель сообщения расшифровывает его путем обратной замены.
В классической криптографии различают 4 разновидности шифров замены:
Примером шифра простой замены может служить программа ROT13, которую обычно можно найти в операционной системе UNIX. С ее помощью буква "А" открытого текста на английском языке заменяется на букву "N", "В" — на "О" и так далее. Таким образом, ROT13 циклически сдвигает каждую букву английского алфавита на 13 позиций вправо. Чтобы получить исходный открытый текст надо применить функцию шифрования ROT 13 дважды:
Р = ROT13(ROT13(P))
Все упомянутые шифры замены легко взламываются с использованием современных компьютеров, поскольку замена недостаточно хорошо маскирует стандартные частоты встречаемости букв в открытом тексте.
Разновидностью шифра замены можно считать код, который вместо букв осуществляет замену слов, фраз и даже целых предложений. Например, кодовый текст "ЛЕДЕНЕЦ" может соответствовать фразе открытого текста "ПОВЕРНУТЬ ВПРАВО НА 90°". Однако коды применимы только при определенных условиях: если, например, в коде отсутствует соответствующее значение для слова "МУРАВЬЕД", то вы не можете использовать это слово в открытом тексте своего сообщения, предназначенном для кодирования.
Шифры перестановки
В шифре перестановки буквы открытого текста не замещаются на другие, а меняется сам порядок их следования. Например, в шифре простой колонной перестановки исходный открытый текст записывается построчно (число букв в строке фиксировано), а шифртекст получается считыванием букв по колонкам. Расшифрование производится аналогично: шифртекст записывается поколонно, а открытый текст можно затем прочесть по горизонтали.
Для повышения стойкости полученный шифртекст можно подать на вход второго шифра перестановки. Существуют еще более сложные шифры перестановки, однако почти все они легко взламываются с помощью компьютера.
Хотя во многих современных криптографических алгоритмах и используется перестановка, ее применение ограничено узкими рамками, поскольку в этом случае требуется память большого объема, а также накладываются ограничения на длину шифруемых сообщений. Замена получила значительно большее распространение.
Роторные машины
В 20-е годы были изобретены разнообразные механические устройства призванные автоматизировать процесс шифрования и расшифрования. Большинство из них состояло из клавиатуры для ввода открытого текста набора роторов — специальных вращающихся колес, каждое из которых реализовывало простую замену. Например, ротор мог заменять "А" на "Ф". "Б" на "У", "С" на "Л" и т. д. При этом выходные контакты одного ротора подсоединялись к входным контактам следующего за ним.
Тогда, например, если на клавиатуре 4-роторной машины нажималась клавиша "А", то первый ротор мог превратить ее в "Ф", которая, пройдя через второй ротор, могла стать буквой "Т", которую третий ротор мог заменить на букву "К", которая могла быть преобразована четвертым ротором в букву "F" шифртекста. После этого роторы поворачивались, и в следующий раз заме на была иной. Чтобы сбить с толку криптоаналитиков, роторы вращались с разной скоростью.
Наиболее известной роторной машиной стала немецкая "Энигма", которую Германия использовала для засекречивания своей переписки во время Второй мировой войны.
Операция сложения по модулю 2
Операция сложения по модулю 2, которая в языке программирования С обозначается знаком ^ , а в математике — знаком Å , представляет собой стандартную операцию над битами:
0 Å 0 = 0
0 Å 1 = 1
1 Å 0 = 1
1 Å 1 = 0
С помощью сложения по модулю 2 можно выполнять многоалфавитную замену, прибавляя к битам ключа соответствующие биты открытого текста. Этот алгоритм шифрования является симметричным. Поскольку двойное прибавление одной и той же величины по модулю 2 восстанавливает исходное значение, шифрование и расшифрование выполняются одной и тон же программой.
К сожалению, данный алгоритм обладает очень слабой стойкостью. Тем не менее АНБ одобрило его использование в цифровых сотовых телефонах американских производителей для засекречивания речевых переговоров. Он также часто встречается в различных коммерческих программных продуктах.
Следует помнить, что с помощью данного алгоритма вы можете надежно спрятать от человека, не сведущего в криптоанализе, содержание своей переписки, однако опытному криптоаналитику понадобится всего несколько минут, чтобы его взломать. Делается это очень просто, если предположить. например, что открытый текст сообщения написан на английском языке.
1. Сначала следует определить длину ключа. Шифртекст последовательно складывается по модулю 2 со своей копией, сдвинутой на различное число байт, и в полученном векторе подсчитывается число совпадающих компонентов. Когда величина сдвига кратна длине ключа, это число превысит 6% от общей длины исследуемого шифртекста. Если не кратна, то совпадений будет меньше 0,4%. Проанализировав полученные данные, можно сделать обоснованный вывод о длине ключа.
2. Затем надо сложить шифртекст по модулю 2 со своей копией, сдвинутой на величину длины ключа. Эта операция аннулирует ключ и оставит в наличии открытый текст сообщения, сложенный по модулю 2 со своей копией, сдвинутой на величину длины ключа.
Хотите верьте, хотите нет, но на самом деле все-таки существует алгоритм шифрования, который невозможно вскрыть. Зовется он одноразовым блокнотом. В классическом виде одноразовый блокнот представляет собой очень длинную последовательность случайных букв, записанную на листах бумаги, которые скреплены между собой в блокнот. Отправитель использует каждую букву из блокнота, чтобы зашифровать ровно одну букву открытого текста сообщения. Шифрование состоит в сложении буквы открытого текста и буквы из одноразового блокнота по модулю N, где N — количество букв в алфавите. После зашифрования отправитель уничтожает использованный одноразовый блокнот. Чтобы отправить новое сообщение, ему придется изготовить или найти новый одноразовый блокнот.
Получатель, владеющий копией одноразового блокнота, которым воспользовался отправитель сообщения, получает открытый текст путем сложения букв шифртекста и букв, извлеченных из имеющейся у него копии одноразового блокнота. Эту копию он затем уничтожает.
Если предположить, что у криптоаналитика нет доступа к одноразовому блокноту, данный алгоритм шифрования абсолютно надежен. Перехваченному шифрованному сообщению с одинаковой вероятностью соответствует произвольный открытый текст той же длины, что и сообщение.
Однако у алгоритма шифрования с помощью одноразового блокнота есть весьма существенный недостаток. Последовательность букв, которая содержится в одноразовом блокноте, должна быть по-настоящему случайной, а не просто псевдослучайной, поскольку любая криптоаналитическая атака на него будет, в первую очередь, направлена против метода генерации содержимого этого блокнота.
Другая важная особенность применения одноразового блокнота состоит в том, чтобы никогда не пользоваться им дважды, поскольку криптоанадитпк может отыскать участки сообщений, для шифрования которых был применен один и тот же одноразовый блокнот. Делается это следующим образом. Нужно последовательно сдвигать одно сообщение относительно другою и подсчитывать количество совпадений. Как только это количество резко увеличится, значит, случайная последовательность, использованная для зашифрования двух различных отрезков сообщений, была одной и той же. Дальнейший криптоанализ осуществляется достаточно просто.
Одноразовые блокноты могут состоять не из байтов, а из битов. Тогда шифрование будет заключаться в выполнении сложения по модулю 2. Для получения открытого текста достаточно опять сложить по модулю 2 шифртекст и содержимое одноразового блокнота. Надежность будет по-прежнему такой же, как при посимвольном модульном сложении.
Еще один недостаток блокнотного способа шифрования заключается в том, что случайная последовательность должна быть той же длины, что и само сообщение. Чтобы послать короткую шифровку резиденту, одноразовый блокнот еще сгодится, но как быть с каналом связи, пропускная способность которого измеряется десятками мегабит в секунду?
Конечно, при необходимости можно для хранения случайных последовательностей воспользоваться компакт-дисками с многократной перезаписью или цифровой магнитной лентой. Однако это будет достаточно дорогостоящее решение проблемы. Кроме того, необходимо будет обеспечить синхронную работу приемной и передающей аппаратуры, а также отсутствие искажений при передаче. Ведь даже если несколько бит сообщения пропущены при его пересдаче, получатель так и не сможет прочесть открытый текст.
Несмотря на все перечисленные выше недостатки, в настоящее время одноразовые блокноты активно используются для шифрования сверхсекретных сообщений. Не имея в своем распоряжении соответствующего блокнота, эти сообщения невозможно прочитать вне зависимости от того, насколько быстро работают суперкомпьютеры, которые используются в ходе криптоана-литической атаки. Даже инопланетные пришельцы со своими сверхсветовыми звездолетами и чудо-компьютерами не смогут их прочесть, если. конечно, не вернутся в прошлое на машине времени и не добудут одноразовые блокноты, использованные для шифрования этих сообщений.
Существует великое множество алгоритмов шифрования, придуманных специально в расчете на реализацию в виде компьютерных программ. Среди наиболее известных можно упомянуть: