Симметричные криптосистемы

Симметри́чные криптосисте́мы (также симметричное шифрование, симметричные шифры) (англ. symmetric-key algorithm) — способ шифрования, в котором для шифрования и расшифровывания применяется один и тот же криптографический ключ. До изобретения схемы асимметричного шифрования единственным существовавшим способом являлось симметричное шифрование. Ключ алгоритма должен сохраняться в секрете обеими сторонами. Алгоритм шифрования выбирается сторонами до начала обмена сообщениями.

Основные сведения

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

Классическими примерами таких алгоритмов являются симметричные криптографические алгоритмы, перечисленные ниже:

• Простая перестановка
• Одиночная перестановка по ключу
• Двойная перестановка
• Перестановка "Магический квадрат"

Простая перестановка

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

Одиночная перестановка по ключу

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

Двойная перестановка

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

Перестановка «Магический квадрат»

Магическими квадратами называются квадратные таблицы со вписанными в их клетки последовательными натуральными числами от 1, которые дают в сумме по каждому столбцу, каждой строке и каждой диагонали одно и то же число. Подобные квадраты широко применялись для вписывания шифруемого текста по приведенной в них нумерации. Если потом выписать содержимое таблицы по строкам, то получалась шифровка перестановкой букв. На первый взгляд кажется, будто магических квадратов очень мало. Тем не менее, их число очень быстро возрастает с увеличением размера квадрата. Так, существует лишь один магический квадрат размером 3 х 3, если не принимать во внимание его повороты. Магических квадратов 4 х 4 насчитывается уже 880, а число магических квадратов размером 5 х 5 около 250000. Поэтому магические квадраты больших размеров могли быть хорошей основой для надежной системы шифрования того времени, потому что ручной перебор всех вариантов ключа для этого шифра был немыслим.

В квадрат размером 4 на 4 вписывались числа от 1 до 16. Его магия состояла в том, что сумма чисел по строкам, столбцам и полным диагоналям равнялась одному и тому же числу — 34. Впервые эти квадраты появились в Китае, где им и была приписана некоторая «магическая сила».

16	3	2	13
5	10	11	8
9	6	7	12
4	15	14	1

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

16.	3 и	2 р	13 д
5 з	10 е	11 г	8 ю
9 С	6 ж	7 а	12 о
4 е	15 я	14 н	1 П

После этого шифрованный текст записывается в строку (считывание производится слева направо, построчно):
.ирдзегюСжаоеянП

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

Требования

Полная утрата всех статистических закономерностей исходного сообщения является важным требованием к симметричному шифру. Для этого шифр должен иметь «эффект лавины» — должно происходить сильное изменение шифроблока при 1-битном изменении входных данных (в идеале должны меняться значения 1/2 бит шифроблока).

Также важным требованием является отсутствие линейности (то есть условия f(a) xor f(b) == f(a xor b)), в противном случае облегчается применение дифференциального криптоанализа к шифру.

Общая схема

В настоящее время симметричные шифры — это:

• блочные шифры. Обрабатывают информацию блоками определённой длины (обычно 64, 128 бит), применяя к блоку ключ в установленном порядке, как правило, несколькими циклами перемешивания и подстановки, называемыми раундами. Результатом повторения раундов является лавинный эффект — нарастающая потеря соответствия битов между блоками открытых и зашифрованных данных.
• поточные шифры, в которых шифрование проводится над каждым битом либо байтом исходного (открытого) текста с использованием гаммирования. Поточный шифр может быть легко создан на основе блочного (например, ГОСТ 28147-89 в режиме гаммирования), запущенного в специальном режиме.

Большинство симметричных шифров используют сложную комбинацию большого количества подстановок и перестановок. Многие такие шифры исполняются в несколько (иногда до 80) проходов, используя на каждом проходе «ключ прохода». Множество «ключей прохода» для всех проходов называется «расписанием ключей» (key schedule). Как правило, оно создается из ключа выполнением над ним неких операций, в том числе перестановок и подстановок.

Типичным способом построения алгоритмов симметричного шифрования является сеть Фейстеля. Алгоритм строит схему шифрования на основе функции F(D, K), где D — порция данных размером вдвое меньше блока шифрования, а K — «ключ прохода» для данного прохода. От функции не требуется обратимость — обратная ей функция может быть неизвестна. Достоинства сети Фейстеля — почти полное совпадение дешифровки с шифрованием (единственное отличие — обратный порядок «ключей прохода» в расписании), что значительно облегчает аппаратную реализацию.

Операция перестановки перемешивает биты сообщения по некоему закону. В аппаратных реализациях она тривиально реализуется как перепутывание проводников. Именно операции перестановки дают возможность достижения «эффекта лавины». Операция перестановки линейна — f(a) xor f(b) == f(a xor b)

Операции подстановки выполняются как замена значения некоей части сообщения (часто в 4, 6 или 8 бит) на стандартное, жестко встроенное в алгоритм иное число путём обращения к константному массиву. Операция подстановки привносит в алгоритм нелинейность.

Зачастую стойкость алгоритма, особенно к дифференциальному криптоанализу, зависит от выбора значений в таблицах подстановки (S-блоках). Как минимум считается нежелательным наличие неподвижных элементов S(x) = x, а также отсутствие влияния какого-то бита входного байта на какой-то бит результата — то есть случаи, когда бит результата одинаков для всех пар входных слов, отличающихся только в данном бите.

Параметры алгоритмов

Существует множество (не менее двух десятков) алгоритмов симметричных шифров, существенными параметрами которых являются:

• стойкость
• длина ключа
• число раундов
• длина обрабатываемого блока
• сложность аппаратной/программной реализации
• сложность преобразования

Виды симметричных шифров

блочные шифры

• AES (англ. Advanced Encryption Standard) - американский стандарт шифрования
• ГОСТ 28147-89 — советский и российский стандарт шифрования, также является стандартом СНГ
• DES (англ. Data Encryption Standard) - стандарт шифрования данных в США
• 3DES (Triple-DES, тройной DES)
• RC2 (Шифр Ривеста (Rivest Cipher или Ron’s Cipher))
• RC5
• Blowfish
• Twofish
• NUSH
• IDEA (International Data Encryption Algorithm, международный алгоритм шифрования данных)
• CAST (по инициалам разработчиков Carlisle Adams и Stafford Tavares)
• CRAB
• 3-WAY
• Khufu и Khafre
• Kuznechik

потоковые шифры

• RC4 (алгоритм шифрования с ключом переменной длины)
• SEAL (Software Efficient Algorithm, программно-эффективный алгоритм)
• WAKE (World Auto Key Encryption algorithm, всемирный алгоритм шифрования на автоматическом ключе)

Сравнение с асимметричными криптосистемами

Достоинства

• скорость
• простота реализации (за счёт более простых операций)
• меньшая требуемая длина ключа для сопоставимой стойкости
• изученность (за счёт большего возраста)

Недостатки

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

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

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

Литература

• Гатчин Ю.А., Коробейников А.Г. Основы криптографических алгоритмов. Учебное пособие. - СПб.: СПбГИТМО(ТУ), 2002.
• Кон П. Универсальная алгебра. - М.: Мир. - 1968.
• Коробейников А. Г. Математические основы криптографии. Учебное пособие. СПб: СПб ГИТМО (ТУ), 2002.

Ссылки

• [www.enlight.ru/crypto сайт А.Винокурова, посвященный блочным шифрам]
• [www.mpgu.ru/crypto справочник, рассматривающий в том числе симметричное шифрование]
• [www.password-crackers.ru/articles/15/ статья «Почему криптосистемы ненадежны?», П. Семьянов]
• [www.connect.ru/article.asp?id=5113 Алгоритмы шифрования]

Отрывок, характеризующий Симметричные криптосистемы

Физические силы его и поворотливость были таковы первое время плена, что, казалось, он не понимал, что такое усталость и болезнь. Каждый день утром а вечером он, ложась, говорил: «Положи, господи, камушком, подними калачиком»; поутру, вставая, всегда одинаково пожимая плечами, говорил: «Лег – свернулся, встал – встряхнулся». И действительно, стоило ему лечь, чтобы тотчас же заснуть камнем, и стоило встряхнуться, чтобы тотчас же, без секунды промедления, взяться за какое нибудь дело, как дети, вставши, берутся за игрушки. Он все умел делать, не очень хорошо, но и не дурно. Он пек, парил, шил, строгал, тачал сапоги. Он всегда был занят и только по ночам позволял себе разговоры, которые он любил, и песни. Он пел песни, не так, как поют песенники, знающие, что их слушают, но пел, как поют птицы, очевидно, потому, что звуки эти ему было так же необходимо издавать, как необходимо бывает потянуться или расходиться; и звуки эти всегда бывали тонкие, нежные, почти женские, заунывные, и лицо его при этом бывало очень серьезно.
Попав в плен и обросши бородою, он, видимо, отбросил от себя все напущенное на него, чуждое, солдатское и невольно возвратился к прежнему, крестьянскому, народному складу.
– Солдат в отпуску – рубаха из порток, – говаривал он. Он неохотно говорил про свое солдатское время, хотя не жаловался, и часто повторял, что он всю службу ни разу бит не был. Когда он рассказывал, то преимущественно рассказывал из своих старых и, видимо, дорогих ему воспоминаний «христианского», как он выговаривал, крестьянского быта. Поговорки, которые наполняли его речь, не были те, большей частью неприличные и бойкие поговорки, которые говорят солдаты, но это были те народные изречения, которые кажутся столь незначительными, взятые отдельно, и которые получают вдруг значение глубокой мудрости, когда они сказаны кстати.
Часто он говорил совершенно противоположное тому, что он говорил прежде, но и то и другое было справедливо. Он любил говорить и говорил хорошо, украшая свою речь ласкательными и пословицами, которые, Пьеру казалось, он сам выдумывал; но главная прелесть его рассказов состояла в том, что в его речи события самые простые, иногда те самые, которые, не замечая их, видел Пьер, получали характер торжественного благообразия. Он любил слушать сказки, которые рассказывал по вечерам (всё одни и те же) один солдат, но больше всего он любил слушать рассказы о настоящей жизни. Он радостно улыбался, слушая такие рассказы, вставляя слова и делая вопросы, клонившиеся к тому, чтобы уяснить себе благообразие того, что ему рассказывали. Привязанностей, дружбы, любви, как понимал их Пьер, Каратаев не имел никаких; но он любил и любовно жил со всем, с чем его сводила жизнь, и в особенности с человеком – не с известным каким нибудь человеком, а с теми людьми, которые были перед его глазами. Он любил свою шавку, любил товарищей, французов, любил Пьера, который был его соседом; но Пьер чувствовал, что Каратаев, несмотря на всю свою ласковую нежность к нему (которою он невольно отдавал должное духовной жизни Пьера), ни на минуту не огорчился бы разлукой с ним. И Пьер то же чувство начинал испытывать к Каратаеву.
Платон Каратаев был для всех остальных пленных самым обыкновенным солдатом; его звали соколик или Платоша, добродушно трунили над ним, посылали его за посылками. Но для Пьера, каким он представился в первую ночь, непостижимым, круглым и вечным олицетворением духа простоты и правды, таким он и остался навсегда.
Платон Каратаев ничего не знал наизусть, кроме своей молитвы. Когда он говорил свои речи, он, начиная их, казалось, не знал, чем он их кончит.
Когда Пьер, иногда пораженный смыслом его речи, просил повторить сказанное, Платон не мог вспомнить того, что он сказал минуту тому назад, – так же, как он никак не мог словами сказать Пьеру свою любимую песню. Там было: «родимая, березанька и тошненько мне», но на словах не выходило никакого смысла. Он не понимал и не мог понять значения слов, отдельно взятых из речи. Каждое слово его и каждое действие было проявлением неизвестной ему деятельности, которая была его жизнь. Но жизнь его, как он сам смотрел на нее, не имела смысла как отдельная жизнь. Она имела смысл только как частица целого, которое он постоянно чувствовал. Его слова и действия выливались из него так же равномерно, необходимо и непосредственно, как запах отделяется от цветка. Он не мог понять ни цены, ни значения отдельно взятого действия или слова.


Получив от Николая известие о том, что брат ее находится с Ростовыми, в Ярославле, княжна Марья, несмотря на отговариванья тетки, тотчас же собралась ехать, и не только одна, но с племянником. Трудно ли, нетрудно, возможно или невозможно это было, она не спрашивала и не хотела знать: ее обязанность была не только самой быть подле, может быть, умирающего брата, но и сделать все возможное для того, чтобы привезти ему сына, и она поднялась ехать. Если князь Андрей сам не уведомлял ее, то княжна Марья объясняла ото или тем, что он был слишком слаб, чтобы писать, или тем, что он считал для нее и для своего сына этот длинный переезд слишком трудным и опасным.
В несколько дней княжна Марья собралась в дорогу. Экипажи ее состояли из огромной княжеской кареты, в которой она приехала в Воронеж, брички и повозки. С ней ехали m lle Bourienne, Николушка с гувернером, старая няня, три девушки, Тихон, молодой лакей и гайдук, которого тетка отпустила с нею.
Ехать обыкновенным путем на Москву нельзя было и думать, и потому окольный путь, который должна была сделать княжна Марья: на Липецк, Рязань, Владимир, Шую, был очень длинен, по неимению везде почтовых лошадей, очень труден и около Рязани, где, как говорили, показывались французы, даже опасен.
Во время этого трудного путешествия m lle Bourienne, Десаль и прислуга княжны Марьи были удивлены ее твердостью духа и деятельностью. Она позже всех ложилась, раньше всех вставала, и никакие затруднения не могли остановить ее. Благодаря ее деятельности и энергии, возбуждавшим ее спутников, к концу второй недели они подъезжали к Ярославлю.
В последнее время своего пребывания в Воронеже княжна Марья испытала лучшее счастье в своей жизни. Любовь ее к Ростову уже не мучила, не волновала ее. Любовь эта наполняла всю ее душу, сделалась нераздельною частью ее самой, и она не боролась более против нее. В последнее время княжна Марья убедилась, – хотя она никогда ясно словами определенно не говорила себе этого, – убедилась, что она была любима и любила. В этом она убедилась в последнее свое свидание с Николаем, когда он приехал ей объявить о том, что ее брат был с Ростовыми. Николай ни одним словом не намекнул на то, что теперь (в случае выздоровления князя Андрея) прежние отношения между ним и Наташей могли возобновиться, но княжна Марья видела по его лицу, что он знал и думал это. И, несмотря на то, его отношения к ней – осторожные, нежные и любовные – не только не изменились, но он, казалось, радовался тому, что теперь родство между ним и княжной Марьей позволяло ему свободнее выражать ей свою дружбу любовь, как иногда думала княжна Марья. Княжна Марья знала, что она любила в первый и последний раз в жизни, и чувствовала, что она любима, и была счастлива, спокойна в этом отношении.
Но это счастье одной стороны душевной не только не мешало ей во всей силе чувствовать горе о брате, но, напротив, это душевное спокойствие в одном отношении давало ей большую возможность отдаваться вполне своему чувству к брату. Чувство это было так сильно в первую минуту выезда из Воронежа, что провожавшие ее были уверены, глядя на ее измученное, отчаянное лицо, что она непременно заболеет дорогой; но именно трудности и заботы путешествия, за которые с такою деятельностью взялась княжна Марья, спасли ее на время от ее горя и придали ей силы.
Как и всегда это бывает во время путешествия, княжна Марья думала только об одном путешествии, забывая о том, что было его целью. Но, подъезжая к Ярославлю, когда открылось опять то, что могло предстоять ей, и уже не через много дней, а нынче вечером, волнение княжны Марьи дошло до крайних пределов.
Когда посланный вперед гайдук, чтобы узнать в Ярославле, где стоят Ростовы и в каком положении находится князь Андрей, встретил у заставы большую въезжавшую карету, он ужаснулся, увидав страшно бледное лицо княжны, которое высунулось ему из окна.
– Все узнал, ваше сиятельство: ростовские стоят на площади, в доме купца Бронникова. Недалече, над самой над Волгой, – сказал гайдук.
Княжна Марья испуганно вопросительно смотрела на его лицо, не понимая того, что он говорил ей, не понимая, почему он не отвечал на главный вопрос: что брат? M lle Bourienne сделала этот вопрос за княжну Марью.
– Что князь? – спросила она.
– Их сиятельство с ними в том же доме стоят.
«Стало быть, он жив», – подумала княжна и тихо спросила: что он?
– Люди сказывали, все в том же положении.
Что значило «все в том же положении», княжна не стала спрашивать и мельком только, незаметно взглянув на семилетнего Николушку, сидевшего перед нею и радовавшегося на город, опустила голову и не поднимала ее до тех пор, пока тяжелая карета, гремя, трясясь и колыхаясь, не остановилась где то. Загремели откидываемые подножки.
Отворились дверцы. Слева была вода – река большая, справа было крыльцо; на крыльце были люди, прислуга и какая то румяная, с большой черной косой, девушка, которая неприятно притворно улыбалась, как показалось княжне Марье (это была Соня). Княжна взбежала по лестнице, притворно улыбавшаяся девушка сказала: – Сюда, сюда! – и княжна очутилась в передней перед старой женщиной с восточным типом лица, которая с растроганным выражением быстро шла ей навстречу. Это была графиня. Она обняла княжну Марью и стала целовать ее.
– Mon enfant! – проговорила она, – je vous aime et vous connais depuis longtemps. [Дитя мое! я вас люблю и знаю давно.]
Несмотря на все свое волнение, княжна Марья поняла, что это была графиня и что надо было ей сказать что нибудь. Она, сама не зная как, проговорила какие то учтивые французские слова, в том же тоне, в котором были те, которые ей говорили, и спросила: что он?