DFC
|
|
DFC (Decorrelated Fast Cipher) — блочный симметричный криптоалгоритм, созданный в 1998 году совместно криптографами Парижской Высшей нормальной школы, Национального центра научных исследований (CNRS) и телекоммуникационного гиганта France Telecom под руководством известного криптолога Сержа Воденэ (англ.), специально для участия в конкурсе AES. Относится к семейству PEANUT (Pretty Encryption Algorithm with n-Universal Transformation) шифров. [1]
Содержание
Общая структура
DFC — блочный шифр с длинной блока 128 бит, представляющий 8-ми раундовую Сеть Фейстеля. Используется 64-битовая функция шифрования с восемью различными раундовыми ключами <math>K_{i}, i=1\ldots n, n=8</math> по 128 бит, получаемыми из одного исходного ключа шифрования. Каждый раунд функция шифрования использует левую половину исходного текста (блока) и два 64-битных ключа, являющихся половинами соответствующего раундового, для получения 64-битного шифрованного текста. Полученная зашифрованная левая половина блока прибавляется к правой. Затем, согласно идее сети Фейстеля, левая и правая части блока меняются местами[2]. Расшифровывание происходит так же как и шифрование с использованием раундовых ключей в обратном порядке. Длина исходного ключа шифрования не ограничивается тремя фиксированными размерами, предусмотренными конкурсом AES (128, 192 и 256 битов), и может быть переменного размера от 0 до 256 бит[3].
Функция шифрования [2][4]
|
Вход: <math>X</math> — 64-битная левая половина исходного текста (блока); <math>K_{i}</math> — соответствующий раундовый ключ.
Выход: <math>Y</math> — 64-битная зашифрованная левая половина исходного текста.
Этап 1: Вычисление
Раундовый ключ <math>K_{i}</math> делится на две половины: <math>A_{i}</math> и <math>B_{i}</math>. Далее производится следующее вычисление:
- <math>Z=(A_{i}\cdot X + B_{i}\mod (2^{64} + 13))\mod 2^{64}</math>
Этап 2: «Запутывающая перестановка»
«Запутывающая перестановка» (Confusion Permutation) использует S-box, трансформирующий входные 6 бит в 32 бита с помощью таблицы замены RT (Далее считаем <math>RT()</math> функцией данного преобразования).
Пусть <math>Z_{l}</math> и <math>Z_{r}</math> — левая и правая части полученного <math>Z</math> по 32 бита каждая (обозначим это как <math>Z=Z_{l}|Z_{r}</math>), <math>KC</math> и <math>KD</math> — заданные константы длиной 32 и 64 бита соответственно, а <math>trunc_{n}()</math> — функция, оставляющая <math>n</math> крайних левых бит аргумента, тогда результат функции шифрования:
- <math>Y=(Z_{r}\oplus RT(trunc_{6}(Z_{l})))|(Z_{l}\oplus KC) + KD\mod 2^{64}</math>
Таблица поиска (S-box)
S-блок — основной компонент симметричных криптоалгоритмов, производящий замену n входных бит на m выходных по некоторой таблице поиска. Используется для максимального устранения зависимостей между ключом шифрования и шифротекстом, что позволяет выполнить свойство Шеннона о запутанности криптоалгоритма. Обычно используются S-блоки с фиксированной таблицей поиска (DES,Rijndael), но в некоторых криптоалгоритмах таблица поиска генерируется с использованием входного ключа шифрования (Blowfish,Twofish). В DFC используется фиксированная таблица поиска RT, её значения будут описаны ниже. Необходимым критерием таблицы поиска является инъективность.
Раундовые ключи[4]
Для повышения стойкости шифра каждый раунд функция шифрования использует разные раундовые ключи <math>K_i</math>. Для их получения используется основной ключ шифра <math>K</math>. Алгоритм получения состоит в следующем.
Шаг 1
Сначала дополним основной ключ шифра <math>K</math> (длина которого колеблется от 0 до 256 бит) заданной константой <math>KS</math> длиной 256 бит, отрезая лишние символы.
- <math>PK=trunc_{256}(K|KS)</math>.
Полученный <math>PK</math> разрезаем на 8 32-битных частей <math>PK_{i},i=1\ldots8</math>.
- <math>PK=PK_{1}|\ldots|PK_{8}</math>
Шаг 2
Определим несколько вспомогательных переменных, используя полученные <math>PK_{i}</math>:
- <math>OA_{1}=PK_{1}|PK_{8};</math>
- <math>OB_{1}=PK_{5}|PK_{4};</math>
- <math>EA_{1}=PK_{2}|PK_{7};</math>
- <math>EB_{1}=PK_{6}|PK_{3};</math>
а также для i=2,3,4
- <math>OA_{i}=OA_{1}\oplus KA_{i-1};</math>
- <math>OB_{i}=OB_{1}\oplus KB_{i-1};</math>
- <math>EA_{i}=EA_{1}\oplus KA_{i-1};</math>
- <math>EB_{i}=EB_{1}\oplus KB_{i-1};</math>
где <math>KA_{1}, KB_{1}, KA_{2}, KB_{2}, KA_{3}, KB_{3}</math> — заданные 64-битные константы.
Шаг 3
Таким образом мы получили из исходного ключа <math>K</math> длиной 256 бит два ключа <math>OK(K), EK(K)</math> длиной по 512 бит каждый.
- <math>OK(K)=OA_{1}|OB_{1}|\ldots|OA_{4}|OB_{4}</math>
- <math>EK(K)=EA_{1}|EB_{1}|\ldots|EA_{4}|EB_{4}</math>
Пусть <math>Enc_{OK(K)}(), Enc_{EK(K)}()</math> — функции шифрования, описанные в пункте 2, только с 4-мя раундами вместо 8-ми, использующие для <math>i</math>-го раунда <math>i=1\ldots4</math> раундовые ключи <math>OA_{i}|OB_{i}</math> и <math>EA_{i}|EB_{i}</math> соответственно. Тогда полагая что <math>K_{0}=0|_{128}</math> получаем искомые раундовые ключи:
Если <math>i</math> — нечетное, то:
- <math>K_{i}=Enc_{OK(K)}(K_{i-1})</math>
Если <math>i</math> — четное, то:
- <math>K_{i}=Enc_{EK(K)}(K_{i-1})</math>
Раундовые ключи найдены.
Фиксированные параметры[4]
Для проведения операции шифрования шифром DFC, как показано выше, требуются следующие фиксированные параметры:
| Наименование | Длина (бит) | Назначение |
|---|---|---|
| <math>KD</math> | 64 | Функция Шифрования, Этап 2 |
| <math>KC</math> | 32 | Функция Шифрования, Этап 2 |
| <math>KA_{1},KA_{2},KA_{3}</math> | 64 | Получение раундовых ключей, Шаг 2 |
| <math>KB_{1},KB_{2},KB_{3}</math> | 64 | Получение раундовых ключей, Шаг 2 |
| <math>KS</math> | 256 | Получение раундовых ключей, Шаг 1 |
| Таблица поиска <math>RT_{i}, i=0\ldots63</math> | 64x32 | Функция Шифрования, Этап 2 |
Для задания фиксированных параметров обычно используется шестнадцатеричная запись числа e:
- e = 2.b7e151628aed2a6abf7158…
Далее будем считать <math>EC</math> только дробную часть шестнадцатеричной записи числа e.
- <math>trunc_{2144} (EC)=RT_{0}|RT_{1}|RT_{2}|\ldots|RT_{63}|KC|KD</math>
- <math>trunc_{640} (EC)=KA_{1}|KA_{2}|KA_{3}|KB_{1}|KB_{2}|KB_{3}|KS</math>
Таким образом получим следующее (данные представлены в шестнадцатеричной системе исчисления):
| Входная последовательность бит(6): | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 0A | 0B | |||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Выходная последовательность бит (32): | b7e15162 | 8aed2a6a | bf715880 | 9cf4f3c7 | 62e7160f | 38b4da56 | a784d904 | 5190cfef | 324e7738 | 926cfbe5 | f4bf8d8d | 8c31d763 | |||
| 0C | 0D | 0E | 0F | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 1A | 1B |
| da06c80a | bb1185eb | 4f7c7b57 | 57f59594 | 90cfd47d | 7c19bb42 | 158d9554 | f7b46bce | d55c4d79 | fd5f24d6 | 613c31c3 | 839a2ddf | 8a9a276b | cfbfa1c8 | 77c56284 | dab79cd4 |
| 1C | 1D | 1E | 1F | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 2A | 2B |
| c2d3293d | 20e9e5ea | f02ac60a | cc93ed87 | 4422a52e | cb238fee | e5ab6add | 835fd1a0 | 753d0a8f | 78e537d2 | b95bb79d | 8dcaec64 | 2c1e9f23 | b829b5c2 | 780bf387 | 37df8bb3 |
| 2C | 2D | 2E | 2F | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 3A | 3B |
| 00d01334 | a0d0bd86 | 45cbfa73 | a6160ffe | 393c48cb | bbca060f | 0ff8ec6d | 31beb5cc | eed7f2f0 | bb088017 | 163bc60d | f45a0ecb | 1bcd289b | 06cbbffea | 21ad08e1 | 847f3f73 |
| 3C | 3D | 3E | 3F | ||||||||||||
| 78d56ced | 94640d6e | f0d3d37b | e6700831 |
Константы:
KD = 86d1bf27 5b9b251d KC = eb64749a KA1 = b7e15162 8aed2a6a KA2 = bf715880 9cf4f3c7 KA3 = 62e7160f 38b4da56 KB1 = a784d904 5190cfef KB2 = 324e7738 926cfbe5 KB3 = f4bf8d8d 8c31d763 KS = da06c80a bb1185eb 4f7c7b57 57f59584 90cfd47d 7c19bb42 158d9554 f7b46bce
Криптостойкость
Криптостойкость — способность алгоритма шифрования противостоять возможным атакам на него. Структура DFC основана на декорреляционном методе[1], разработанном Сержом Ваденэ, с доказуемой стойкостью к известным криптографическим атакам. Однако уже существуют аналитические результаты, показывающие обратное.
Слабые ключи и константы[4]
Для удобства возьмем, что <math>LK_i</math> — левая половина i-го раундового ключа K, <math>RK_i</math> — правая половина. Если <math>RK_i</math> равна 0, то на выходе функции шифрования <math>Z_{K_i} \left( X \right)</math> будет некая константа, независящая от <math>X</math>. Следовательно, взяв <math>LK_2</math>, <math>LK_4</math>, <math>LK_6</math> равными 0, шифр становится уязвимым к distinguishing attack (англ.) (более подробно о такой атаке с примером[5]). Шанс появления таких ключей равен 2−192.
Следует отметить ещё одну особенность шифра, связанную с плохим выбором констант <math>KA_i</math> и <math>KB_i</math>. (см. «Раундовые ключи») Если <math>KA_3 = KB_3 = 0</math>, <math>KA_2 = KA_4</math>, <math>KB_2 = KB_4</math>, то получим <math>OA_1 = OA_3 </math>, <math>OA_2 = EA_2 = 0</math>, <math>OA_2 = OA_4 = 0</math>. А значит
- <math>Enc_{OK\left( K \right)} \left( {X_L |X_R } \right) = X_R |X_L </math>
- <math>Enc_{EK\left( K \right)} \left( {X_L |X_R } \right) = X_R |X_L </math>
Таким образом получаем нулевые раундовые ключи для всех раундов, значит
- <math>DFC_K(U|V)=(V \oplus C)|(U \oplus C)</math>, где <math>C</math> — некая константа.
По получившемуся закрытому тексту можно восстановить исходный текст.
Атака по времени
Атака по времени — одна из разновидностей атаки по сторонним каналам. Реализации устойчивых шифров (DFC не исключение) должны быть такими, чтобы время вычисления операций по модулю (mod) не зависело от входных данных. В противном случае возможно применение атаки Кочера (англ.) по времени[6].
Атака «Photofinishing Attack»
Эли Бихам предложил эффективную технологию реалиции шифра, основанную на 1-битновом SIMD микропроцессоре. Этот вид реализации не подвержен атаке Шамира «Photofinishing attack»[7].
Напишите отзыв о статье "DFC"
Ссылки
- [lasecwww.epfl.ch/memo/dfc.shtml LASEC. Информация о DFC]
- [citeseerx.ist.psu.edu/viewdoc/download;jsessionid=30FFFA0BF5790195A366053821E1729D?doi=10.1.1.23.9355&rep=rep1&type=pdf DFCv2]
Примечания
- ↑ 1 2 S. Vaudenay (англ.) [citeseerx.ist.psu.edu/viewdoc/download;jsessionid=6ECC4FBB8EBF4D3293B64A3F1EBF40C9?doi=10.1.1.56.9229&rep=rep1&type=pdf Provable security for block Ciphers by deccorelation (1998)]
- ↑ 1 2 Ларс Кнудсен, Vincent Rijmen (англ.) (Март 1999) [www.cosic.esat.kuleuven.be/publications/article-367.pdf «On the Decorrelated Fast Cipher (DFC) and Its Theory»]
- ↑ [www.all4web.ru/art.aspx?id=41 Материалы книги Сергея Панасенко «Алгоритмы шифрования»]
- ↑ 1 2 3 4 Henri Gilbert, Marc Girault, Philippe Hoogvorst, Fabrice Noilhan, Thomas Pornin, Guillaume Poupard, Jacques Stern (англ.) and Serge Vaudenay (англ.) [lasecwww.epfl.ch/pub/lasec/doc/GG+98.ps Decorrelated Fast Cipher: an AES Candidate. Full version]
- ↑ Simon Künzli, Willi Meier (2009) [www.ecrypt.eu.org/stream/papersdir/053.pdf Distinguishing Attack on MAG]
- ↑ Paul C. Kocher (англ.) [www.cryptography.com/public/pdf/TimingAttacks.pdf Timing Attacks on Implementations of Diffie-Hellman, PSA, DSS, and Other Systems]
- ↑ A. Shamir. Visual cryptanalysis in Cryptology EUROCRYPT’98 (1998)
| ||||||||||||||||||
Отрывок, характеризующий DFC
– Постойте, огня зажгу. Куда ты, проклятый, всегда засунешь? – обращаясь к денщику, сказал тянувшийся человек. Это был Щербинин, адъютант Коновницына. – Нашел, нашел, – прибавил он.Денщик рубил огонь, Щербинин ощупывал подсвечник.
– Ах, мерзкие, – с отвращением сказал он.
При свете искр Болховитинов увидел молодое лицо Щербинина со свечой и в переднем углу еще спящего человека. Это был Коновницын.
Когда сначала синим и потом красным пламенем загорелись серники о трут, Щербинин зажег сальную свечку, с подсвечника которой побежали обгладывавшие ее прусаки, и осмотрел вестника. Болховитинов был весь в грязи и, рукавом обтираясь, размазывал себе лицо.
– Да кто доносит? – сказал Щербинин, взяв конверт.
– Известие верное, – сказал Болховитинов. – И пленные, и казаки, и лазутчики – все единогласно показывают одно и то же.
– Нечего делать, надо будить, – сказал Щербинин, вставая и подходя к человеку в ночном колпаке, укрытому шинелью. – Петр Петрович! – проговорил он. Коновницын не шевелился. – В главный штаб! – проговорил он, улыбнувшись, зная, что эти слова наверное разбудят его. И действительно, голова в ночном колпаке поднялась тотчас же. На красивом, твердом лице Коновницына, с лихорадочно воспаленными щеками, на мгновение оставалось еще выражение далеких от настоящего положения мечтаний сна, но потом вдруг он вздрогнул: лицо его приняло обычно спокойное и твердое выражение.
– Ну, что такое? От кого? – неторопливо, но тотчас же спросил он, мигая от света. Слушая донесение офицера, Коновницын распечатал и прочел. Едва прочтя, он опустил ноги в шерстяных чулках на земляной пол и стал обуваться. Потом снял колпак и, причесав виски, надел фуражку.
– Ты скоро доехал? Пойдем к светлейшему.
Коновницын тотчас понял, что привезенное известие имело большую важность и что нельзя медлить. Хорошо ли, дурно ли это было, он не думал и не спрашивал себя. Его это не интересовало. На все дело войны он смотрел не умом, не рассуждением, а чем то другим. В душе его было глубокое, невысказанное убеждение, что все будет хорошо; но что этому верить не надо, и тем более не надо говорить этого, а надо делать только свое дело. И это свое дело он делал, отдавая ему все свои силы.
Петр Петрович Коновницын, так же как и Дохтуров, только как бы из приличия внесенный в список так называемых героев 12 го года – Барклаев, Раевских, Ермоловых, Платовых, Милорадовичей, так же как и Дохтуров, пользовался репутацией человека весьма ограниченных способностей и сведений, и, так же как и Дохтуров, Коновницын никогда не делал проектов сражений, но всегда находился там, где было труднее всего; спал всегда с раскрытой дверью с тех пор, как был назначен дежурным генералом, приказывая каждому посланному будить себя, всегда во время сраженья был под огнем, так что Кутузов упрекал его за то и боялся посылать, и был так же, как и Дохтуров, одной из тех незаметных шестерен, которые, не треща и не шумя, составляют самую существенную часть машины.
Выходя из избы в сырую, темную ночь, Коновницын нахмурился частью от головной усилившейся боли, частью от неприятной мысли, пришедшей ему в голову о том, как теперь взволнуется все это гнездо штабных, влиятельных людей при этом известии, в особенности Бенигсен, после Тарутина бывший на ножах с Кутузовым; как будут предлагать, спорить, приказывать, отменять. И это предчувствие неприятно ему было, хотя он и знал, что без этого нельзя.
Действительно, Толь, к которому он зашел сообщить новое известие, тотчас же стал излагать свои соображения генералу, жившему с ним, и Коновницын, молча и устало слушавший, напомнил ему, что надо идти к светлейшему.
Кутузов, как и все старые люди, мало спал по ночам. Он днем часто неожиданно задремывал; но ночью он, не раздеваясь, лежа на своей постели, большею частию не спал и думал.
Так он лежал и теперь на своей кровати, облокотив тяжелую, большую изуродованную голову на пухлую руку, и думал, открытым одним глазом присматриваясь к темноте.
С тех пор как Бенигсен, переписывавшийся с государем и имевший более всех силы в штабе, избегал его, Кутузов был спокойнее в том отношении, что его с войсками не заставят опять участвовать в бесполезных наступательных действиях. Урок Тарутинского сражения и кануна его, болезненно памятный Кутузову, тоже должен был подействовать, думал он.
«Они должны понять, что мы только можем проиграть, действуя наступательно. Терпение и время, вот мои воины богатыри!» – думал Кутузов. Он знал, что не надо срывать яблоко, пока оно зелено. Оно само упадет, когда будет зрело, а сорвешь зелено, испортишь яблоко и дерево, и сам оскомину набьешь. Он, как опытный охотник, знал, что зверь ранен, ранен так, как только могла ранить вся русская сила, но смертельно или нет, это был еще не разъясненный вопрос. Теперь, по присылкам Лористона и Бертелеми и по донесениям партизанов, Кутузов почти знал, что он ранен смертельно. Но нужны были еще доказательства, надо было ждать.
«Им хочется бежать посмотреть, как они его убили. Подождите, увидите. Все маневры, все наступления! – думал он. – К чему? Все отличиться. Точно что то веселое есть в том, чтобы драться. Они точно дети, от которых не добьешься толку, как было дело, оттого что все хотят доказать, как они умеют драться. Да не в том теперь дело.
И какие искусные маневры предлагают мне все эти! Им кажется, что, когда они выдумали две три случайности (он вспомнил об общем плане из Петербурга), они выдумали их все. А им всем нет числа!»
Неразрешенный вопрос о том, смертельна или не смертельна ли была рана, нанесенная в Бородине, уже целый месяц висел над головой Кутузова. С одной стороны, французы заняли Москву. С другой стороны, несомненно всем существом своим Кутузов чувствовал, что тот страшный удар, в котором он вместе со всеми русскими людьми напряг все свои силы, должен был быть смертелен. Но во всяком случае нужны были доказательства, и он ждал их уже месяц, и чем дальше проходило время, тем нетерпеливее он становился. Лежа на своей постели в свои бессонные ночи, он делал то самое, что делала эта молодежь генералов, то самое, за что он упрекал их. Он придумывал все возможные случайности, в которых выразится эта верная, уже свершившаяся погибель Наполеона. Он придумывал эти случайности так же, как и молодежь, но только с той разницей, что он ничего не основывал на этих предположениях и что он видел их не две и три, а тысячи. Чем дальше он думал, тем больше их представлялось. Он придумывал всякого рода движения наполеоновской армии, всей или частей ее – к Петербургу, на него, в обход его, придумывал (чего он больше всего боялся) и ту случайность, что Наполеон станет бороться против него его же оружием, что он останется в Москве, выжидая его. Кутузов придумывал даже движение наполеоновской армии назад на Медынь и Юхнов, но одного, чего он не мог предвидеть, это того, что совершилось, того безумного, судорожного метания войска Наполеона в продолжение первых одиннадцати дней его выступления из Москвы, – метания, которое сделало возможным то, о чем все таки не смел еще тогда думать Кутузов: совершенное истребление французов. Донесения Дорохова о дивизии Брусье, известия от партизанов о бедствиях армии Наполеона, слухи о сборах к выступлению из Москвы – все подтверждало предположение, что французская армия разбита и сбирается бежать; но это были только предположения, казавшиеся важными для молодежи, но не для Кутузова. Он с своей шестидесятилетней опытностью знал, какой вес надо приписывать слухам, знал, как способны люди, желающие чего нибудь, группировать все известия так, что они как будто подтверждают желаемое, и знал, как в этом случае охотно упускают все противоречащее. И чем больше желал этого Кутузов, тем меньше он позволял себе этому верить. Вопрос этот занимал все его душевные силы. Все остальное было для него только привычным исполнением жизни. Таким привычным исполнением и подчинением жизни были его разговоры с штабными, письма к m me Stael, которые он писал из Тарутина, чтение романов, раздачи наград, переписка с Петербургом и т. п. Но погибель французов, предвиденная им одним, было его душевное, единственное желание.
В ночь 11 го октября он лежал, облокотившись на руку, и думал об этом.
В соседней комнате зашевелилось, и послышались шаги Толя, Коновницына и Болховитинова.
– Эй, кто там? Войдите, войди! Что новенького? – окликнул их фельдмаршал.
Пока лакей зажигал свечу, Толь рассказывал содержание известий.
– Кто привез? – спросил Кутузов с лицом, поразившим Толя, когда загорелась свеча, своей холодной строгостью.
– Не может быть сомнения, ваша светлость.
– Позови, позови его сюда!
Кутузов сидел, спустив одну ногу с кровати и навалившись большим животом на другую, согнутую ногу. Он щурил свой зрячий глаз, чтобы лучше рассмотреть посланного, как будто в его чертах он хотел прочесть то, что занимало его.
– Скажи, скажи, дружок, – сказал он Болховитинову своим тихим, старческим голосом, закрывая распахнувшуюся на груди рубашку. – Подойди, подойди поближе. Какие ты привез мне весточки? А? Наполеон из Москвы ушел? Воистину так? А?
