CRYPTON

CRYPTON
	CRYPTON
Создатель:	Че Хун Лим (Future Systems, Inc.)
Создан:	1998 г.
Опубликован:	1998 - 1999
Размер ключа:	128, 192, 256 бит
Размер блока:	128 бит
Число раундов:	12
Тип:	Подстановочно-перестановочная сеть

CRYPTON — алгоритм симметричного блочного шифрования (размер блока 128 бит, ключ длиной до 256 бит), разработанный южнокорейским криптологом Че Хун Лим (англ. Chae Hoon Lim) из южнокорейской компании Future Systems, с конца 1980-х годов работающая на рынке сетевого обеспечения и защиты информации. Алгоритм был разработан в 1998 году в качестве шифра — участника конкурса AES. Как признавался автор, конструкция алгоритма опирается на алгоритм SQUARE. В алгоритме Crypton нет традиционных для блочных шифров сети Фейстеля. Основу данного шифра составляет так называемая SP-сеть (повторяющаяся цикловая функция из замен-перестановок, ориентированная на распараллеленную нелинейную обработку всего блока данных). Кроме высокой скорости, преимуществами таких алгоритмов является облегчение исследования стойкости шифра к методам дифференциального и линейного криптоанализа, являющимся на сегодня основными инструментами вскрытия блочных шифров. На конкурс AES была изначально представлена версия алгоритма Crypton v0.5. Однако, как говорил Че Хун Лим, ему не хватало времени для разработки полной версии. И уже в первом этапе конкурса AES в ходе анализа алгоритмов, версия Crypton v0.5 была заменена на версию Crypton v1.0. Отличие новой версии от первоначальной заключались в изменении таблиц замен, в модификации процесса расширения ключа.

Содержание

1 Структура алгоритма. Основные характеристики
- 1.1 Шифрование
- 1.2 Расшифрование
2 Процедура расширения ключа
- 2.1 Формирование расширенных ключей
- 2.2 Вычисление ключей раундов
3 Безопасность
4 Конкурс AES
5 Версии алгоритма Crypton
6 Ссылки и Литература

Структура алгоритма. Основные характеристики

Как и другие участники конкурса AES, Crypton предназначен для шифрования 128-битовых блоков данных. При шифровании используются ключи шифрования нескольких фиксированных размеров — от 0 до 256 бит с кратностью 8 битов. Структура алгоритма Crypton — структура «Квадрата» — во многом похожа на структуру алгоритма Square, созданного в 1997 году. Криптографические преобразования для алгоритмов с данной структурой могут быть выполнены как над целыми строками и столбцами массива, так и над отдельными его байтами. (Стоит отметить, что алгоритм Square был разработан авторами будущего победителя конкурса AES — авторами алгоритма Rijndael — Винсентом Риджменом и Джоан Дейменом.)

Шифрование

Алгоритм Crypton представляет 128-битовый блок шифруемых данных в виде байтового массива 4×4, над которыми в процессе шифрования производится несколько раундов преобразований. В каждом раунде предполагается последовательное выполнение следующих операций:

Табличная замена <math>\gamma</math>;
Линейное преобразование <math>\pi</math>;
Байтовая перестановка <math>\tau</math>;
Операция <math>\sigma</math>.

Табличная замена <math>\gamma</math>

Алгоритм Crypton использует 4 таблицы замен. Каждая из которых замещает 8-битовое входное значение на выходное такого же размера.

Все таблицы <math>S_{0}...S_{3}</math> являются производными от основной таблицы <math>S</math> (см. рисунок - вычисление производных таблиц замен).

Ниже представлен пример таблиц:

Таблица <math>S_{0}</math>:

63	ec	59	aa	db	8e	66	c0	37	3c	14	ff	13	44	a9	91
3b	78	8d	ef	c2	2a	f0	d7	61	9e	a5	bc	48	15	12	47
ed	42	1a	33	38	c8	17	90	a6	d5	5d	65	6a	fe	8f	a1
93	c2	2f	0c	68	58	df	f4	45	11	a0	a7	22	96	fb	7d
1d	b4	84	e0	bf	57	e9	0a	4e	83	cc	7a	71	39	c7	32
74	3d	de	50	85	06	6f	53	e8	ad	82	19	e1	ba	36	cb
0e	28	f3	9b	4a	62	94	1f	bd	f6	67	41	d8	d1	2d	a4
86	b7	01	c5	b0	75	02	f9	2c	29	6e	d2	f5	8b	fc	5a
e4	7f	dd	07	55	b1	2b	89	72	18	3a	4c	b6	e3	80	ce
49	cf	6b	b9	f2	0d	dc	64	95	46	f7	10	9a	20	a2	3f
d6	87	70	3e	21	fd	4d	7b	3c	ae	09	8a	04	b3	54	f8
30	00	56	d4	e7	25	bb	ac	98	73	ea	c9	9d	4f	7e	03
ab	92	a8	43	0f	fa	24	5c	1e	60	31	97	cd	c6	79	f5
5e	e5	34	76	1c	81	b2	af	0b	5d	d9	e2	27	6d	d0	88
c1	51	e6	9c	77	be	99	23	da	eb	52	2e	b5	08	05	6c
b8	1b	a3	69	8c	d3	40	26	f1	c4	9f	35	ee	7c	4b	16

Таблица <math>S_{1}</math>

8d	b3	65	aa	6f	3a	99	03	dc	f0	50	ff	4c	11	a6	46
ec	e1	36	bf	0b	a8	c3	5f	85	7a	96	f2	21	54	48	1d
b7	09	68	cc	e0	23	5c	42	9a	57	75	95	a9	fb	3e	86
4e	2b	bc	30	a1	61	7f	d3	15	44	82	9e	88	5a	Ef	f5
74	d2	12	83	fe	5d	a7	28	39	0e	33	e9	c5	e4	1f	c8
d1	f4	7b	41	16	18	bd	4d	a3	b6	0a	64	87	ea	d8	2f
38	a0	cf	6e	29	89	52	7c	f6	db	9d	05	63	47	b4	92
1a	de	04	17	c2	d5	08	e7	b0	a4	b9	4b	7d	2e	f3	69
93	fd	77	1c	55	c6	ac	26	c9	60	e8	31	da	8f	02	3b
25	3f	ad	e6	cb	34	73	91	56	19	df	40	6a	80	8a	fc
5b	1e	c1	f8	84	f7	35	ed	0f	ba	24	2a	10	ce	51	e3
c0	00	59	53	9f	94	ee	b2	62	cd	ab	27	76	3d	f9	0c
ae	4a	a2	0d	3c	eb	90	71	78	81	c4	5e	37	1b	e5	d7
79	97	d0	d9	70	06	ca	be	2c	6d	67	8b	9c	b5	43	22
07	45	9b	72	dd	fa	66	8c	6b	af	49	b8	d6	20	14	b1
e2	6c	8e	a5	32	4f	01	98	c7	13	7e	d4	bb	f1	2d	58

Таблица <math>S_{2}</math>

b1	72	76	bf	ac	ee	55	83	ed	aa	47	d8	33	95	60	c4
9b	39	1e	0c	0a	1d	ff	26	89	5b	22	f1	d4	40	c8	67
9d	a4	3c	e7	c6	b5	f7	dc	61	79	15	86	78	6e	eb	32
b0	ca	4f	23	d2	fb	5e	08	24	4d	8a	10	09	51	a3	9f
f6	6b	21	c3	0d	38	99	1f	1c	90	64	fe	8b	a6	48	bd
53	e1	ea	57	ae	84	b2	45	35	02	7f	d9	c7	2a	d0	7c
c9	18	65	00	97	2b	06	6a	34	f3	2c	92	ef	dd	7a	56
a2	c4	88	b9	50	75	d3	e4	11	ce	4b	a7	fd	3f	be	81
8e	d5	5a	49	42	54	70	a1	df	87	ab	7d	f4	12	05	2e
27	0f	c1	30	66	98	3d	cb	b8	e6	9c	63	e3	bc	19	fa
3a	2f	9e	f2	6f	1a	28	3b	c2	0e	03	c0	b7	59	a9	d7
74	85	d6	ad	41	ec	8c	71	f0	93	5d	b6	1b	68	e5	44
07	e0	14	8a	f9	73	cd	4e	25	bb	31	5f	4a	cc	8f	91
de	6d	7b	f5	b3	29	a0	17	6c	da	e8	04	96	82	52	36
43	5c	db	8d	80	d1	e2	b4	58	46	ba	e9	01	20	fc	13
16	f8	94	62	37	cf	69	9a	af	77	c5	3e	7e	a5	2d	0b

Таблица <math>S_{3}</math>:

b1	f6	8e	07	72	6b	d5	e0	76	21	5a	14	bf	c3	49	a8
ac	0d	42	f9	ee	38	54	73	55	99	70	cd	83	1f	a1	4e
ed	1c	df	25	aa	90	87	bb	47	64	ab	31	d8	fe	7d	5f
33	8b	f4	4a	95	a6	12	cc	60	48	05	8f	c4	bd	2e	91
9b	53	27	de	39	e1	0f	6d	1e	ea	c1	7b	0c	57	30	f5
0a	ae	66	b3	1d	84	98	29	ff	b2	3d	a0	26	45	cb	17
89	35	b8	6c	5b	02	e6	da	22	7f	9c	e8	f1	d9	63	04
d4	c7	e3	96	40	2a	bc	82	c8	d0	19	52	67	7c	fa	36
9d	c9	3a	43	a4	18	2f	5c	3c	65	9e	db	e7	00	f2	8d
c6	97	6f	80	b5	2b	1a	d1	f7	06	28	e2	dc	6a	3b	b4
61	34	c2	58	79	f3	0e	46	15	2c	03	ba	86	92	c0	e9
78	ef	b7	01	6e	dd	59	20	eb	7a	a9	fc	32	56	d7	13
b0	a2	74	16	ca	4c	85	f8	4f	88	d6	94	23	b9	ad	62
d2	50	41	37	fb	75	ec	cf	5e	d3	8c	69	08	e4	71	9a
24	11	f0	af	4d	ce	93	77	8a	4b	5d	c5	10	a7	b6	3e
09	fd	1b	7e	51	3f	68	a5	a3	be	e5	2d	9f	81	44	0b

В четных раундах используется операция <math>\gamma_{e}</math>, в нечетных - <math>\gamma_{o}</math>. Эти операции и таблицы замен обладают рядом свойств, которые важны, особенно для унификации операций шифрования и расшифрования. Свойства таблиц и операций:

<math>\gamma_{e}(\gamma_{o}(A))=\gamma_{o}(\gamma_{e}(A))=A;</math>

где <math>A</math> — текущее значение блока шифруемых данных. Операции <math>\gamma_{e}</math> и <math>\gamma_{o}</math> можно определить следующим образом:

<math>\gamma_{e}:b_{ij}=S_{(j+2+imod4)}(a_{ij});</math>

<math>\gamma_{o}:b_{ij}=S_{(j+imod4)}(a_{ij}).</math>

где:

<math>a_{ij}</math> — текущее значение конкретного байта данных;
<math>b_{ij}</math> — значение байта данных после выполнения операции;

Линейное преобразование <math>\pi</math>

Здесь используется 4 специальных константы, шестнадцатеричные значения которых указанны ниже:

Эти константы объединены в маскирующие последовательности, перечисленные ниже:

<math>M_{0}=m_{3}\bullet m_{2} \bullet m_{1} \bullet m_{0};</math>

<math>M_{1}=m_{0}\bullet m_{3} \bullet m_{2} \bullet m_{1};</math>

<math>M_{2}=m_{1}\bullet m_{0} \bullet m_{3} \bullet m_{2};</math>

<math>M_{3}=m_{2}\bullet m_{1} \bullet m_{0} \bullet m_{3};</math>

где <math>\bullet</math> — операция конкатенации.

Сама же операция <math>\pi</math> — представляет собой битовую перестановку. В нечетных раундах используется операция <math>\pi_{o}</math>:

<math>B[0]=(A[3] \& M_{3})\oplus(A[2] \& M_{2})\oplus(A[1] \& M_{1})\oplus(A[0] \& M_{0});</math>

<math>B[1]=(A[3] \& M_{0})\oplus(A[2] \& M_{3})\oplus(A[1] \& M_{2})\oplus(A[0] \& M_{1});</math>

<math>B[2]=(A[3] \& M_{1})\oplus(A[2] \& M_{0})\oplus(A[1] \& M_{3})\oplus(A[0] \& M_{2});</math>

<math>B[3]=(A[3] \& M_{2})\oplus(A[2] \& M_{1})\oplus(A[1] \& M_{0})\oplus(A[0] \& M_{3});</math>

где:

<math>\&</math> — логическая побитовая операция «и»;
<math>A[i]</math> и <math>B[i]</math> — значение i-ой строки обрабатываемых данных до и после выполнения операции соответственно.

В четных раундах используется операция <math>\pi_{e}</math>:

<math>B[0]=(A[3] \& M_{1})\oplus(A[2] \& M_{0})\oplus(A[1] \& M_{3})\oplus(A[0] \& M_{2});</math>

<math>B[1]=(A[3] \& M_{2})\oplus(A[2] \& M_{1})\oplus(A[1] \& M_{0})\oplus(A[0] \& M_{3});</math>

<math>B[2]=(A[3] \& M_{3})\oplus(A[2] \& M_{2})\oplus(A[1] \& M_{1})\oplus(A[0] \& M_{0});</math>

<math>B[3]=(A[3] \& M_{0})\oplus(A[2] \& M_{3})\oplus(A[1] \& M_{2})\oplus(A[0] \& M_{1});</math>

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

Байтовая перестановка <math>\tau</math>

Данная перестановка преобразует простейшим образом строку данных в столбец:

Операция <math>\sigma</math>

Данная операция является побитовым сложением всего массива данных с ключом раунда:

<math>\sigma:B = A \oplus K_{r}</math>

где: <math>B</math> — новое значение блока шифруемых данных; <math>K_{r}</math> — ключ текущего раунда <math>r</math>.

Заметим, именно 12 раундов шифрования рекомендуется автором алгоритма Че Хун Лимой, однако строгое количество раундов не установлено. Кроме 12 раундов шифрования, перед первым раундом алгоритма выполняется предварительная операция <math>\sigma</math>, а по завершении 12 раундов выполняется выходное преобразование <math>\phi_{e}</math>, состоящее из последовательно выполняемых операций <math>\tau</math>, <math>\pi_{e}</math> и <math>\tau</math>.

Расшифрование

Расшифрование выполняется применением обратных операций в обратной последовательности. Все операции, кроме <math>\gamma_{e}</math> и <math>\gamma_{o}</math> являются обратными самим себе, а сами <math>\gamma_{e}</math> и <math>\gamma_{o}</math> связаны следующими соотношениями:

<math>\gamma_{e}^{-1} = \gamma_{o};</math>

<math>\gamma_{o}^{-1} = \gamma_{e},</math>

поэтому при расшифровании <math>\gamma_{o}</math> — используется в четных раундах, а <math>\gamma_{e}</math> — в нечетных.

Стоит отметить ещё одну особенность: каждый этап может быть выполняется параллельно, что важно при реализации на современных многоядерных и мультипоточных системах. Алгоритм имеет структуру SP-сети, как и Rijndael (который является победителем конкурса AES) Также особенностью шифра является то, что для зашифрования и расшифрования может использоваться одна и та же процедура, но с разными подключами. Алгоритм эффективен как при программной, так и при аппаратной реализации. Шифр достаточно быстр — на конкурсе AES при использовании компилятора Borland C показал наилучшие результаты среди всех участников.

Процедура расширения ключа

Алгоритм Crypton требует наличие 128 — битового ключа для каждого раунда, а также 128 битового ключа для предварительной операции σ. Расширение ключа происходит в два этапа:

на первом этапе происходит формирование восьми расширенных ключей;
на втором этапе происходит вычисление ключей раундов из расширенных ключей.

Формирование расширенных ключей

Формирование расширенных ключей происходит так:

Если ключ шифрования имеет размер, меньший 256 бит, он дополняется битовыми нулями, пока не достигнет 32-байтового исходного ключа <math>K</math>:

<math>K = k_{31} \bullet ... \bullet k_{1} \bullet k_{0}</math>

Ключ K разбирается на последовательности <math>U</math> и <math>V</math>, первая из которых содержит только четные байты ключа, вторая — только нечетные:

<math>U = U_{3} \bullet U_{2} \bullet U_{1} \bullet U_{0};</math>

<math>V = V_{3} \bullet V_{2} \bullet V_{1} \bullet V_{0};</math>

<math>U = k_{8i+6} \bullet k_{8i+4} \bullet k_{8i+2} \bullet k_{8i};</math>

<math>V = k_{8i+7} \bullet k_{8i+5} \bullet k_{8i+3} \bullet k_{8i+1};</math>

Над последовательностями <math>U</math> и <math>V</math> выполняется один раунд шифрования алгоритма Crypton с использованием ключа раунда, состоящего из нулевых битов. Соответственно для <math>U</math> выполняются преобразования нечетного раунда, для <math>V</math> происходит преобразование четного раунда. Результирующие последовательности обозначаются как <math>U'</math> и <math>V'</math>.
Происходит вычисление 8 расширенных ключей:

<math>Ke_{i} = U'_{i} \oplus T_{1};</math>

<math>Ke_{i+4} = U'_{i} \oplus T_{0};</math>

для <math>i=0,1,2,3,</math> где <math>T_{1}</math> и <math>T_{0}</math> — последовательности, которые определяются следющими формулами:

<math>T_{0} = U'_{0} \oplus U'_{1} \oplus U'_{2} \oplus U'_{3};</math>

<math>T_{1} = V'_{0} \oplus V'_{1} \oplus V'_{2} \oplus V'_{3}.</math>

Вычисление ключей раундов

Для вычисления из расширенных ключей — ключей раундов, используются следующие константы:

<math>Mc_{0} = ACACACAC;</math>

Заметим, что псевдослучайные константы A54FF53A и 3C6EF372 получаются из дробных частей от чисел <math>\sqrt{7}</math> и <math>\sqrt{5}</math> соответственно.

Сначала вычисляются ключи для предварительной операции σ и первого раунда:

<math>K_{0}[i]=Ke_{i} \oplus C_{0} \oplus Mc_{i};</math>

<math>K_{0}[i]=Ke_{i+4} \oplus C_{1} \oplus Mc_{i};</math>

где <math>K_{r}[i]</math> — i-ая строка ключа раунда <math>r</math>. Как и для шифруемых данных, ключ предоставляется в виде таблицы..

Константы <math>Mc_{i}[i]</math> вычисляются путём побитового циклического сдвига каждого байта константы <math>Mc_{i-1}</math> на 1 бит влево.

Для второго и каждого последующего четного раунда ключ вычисляется следующим образом:

Выполняется модификация первых четырёх расширенных ключей:

<math>\mathcal{f} Ke_{3},Ke_{2},Ke_{1},Ke_{0} \mathcal{g} \leftarrow \mathcal{f} Ke_{0}<<<6, Ke_{3}<<<6, Ke_{2}<<16, Ke_{1}<<24 \mathcal{g};</math>

где знаком <<< обозначена операция побитового циклического сдвига каждого байта (раздельно) расширенного ключа на указанное число битов влево, а << — побитового циклического сдвига всего ключа на указанное число битов влево.

Вычисление ключа раунда с помощью модифицированных расширенных ключей:

<math>K_{r}[i]=Ke_{i} \oplus C_{r} \oplus Mc_{i};</math>

Аналогично происходит вычисление ключей для нечетных раундов:

<math>\mathcal{f} Ke_{7},Ke_{6},Ke_{5},Ke_{4}\mathcal{g} \leftarrow \mathcal{f} Ke_{6}<<16, Ke_{5}<<8, Ke_{4}<<<2, Ke_{7}<<<2 \mathcal{g};</math>

<math>K_{r}[i]=Ke_{i+4} \oplus C_{r} \oplus Mc_{i};</math>

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

Безопасность

Недостатки алгоритма Crypton

При анализе исходной версии алгоритма, Crypton v0.5, сразу двое экспертов независимо обнаружили класс слабых ключей: таковых оказалось 2 в степени 32 256-битовых ключей. Также, была обнаружена атака на шестираундовую версию алгоритма Crypton, похожая на атаку на алгоритм Square. Это было одной из причин появления новой версии алгоритма — Crypton v1.0.

Достоинства алгоритма Crypton

Однако по мнению экспертов института NIST, вышеперечисленные недостатки не являются грубыми. Кроме того, плюсов у алгоритма было вполне достаточно:

алгоритм эффективен на программном и аппаратном уровне благодаря высокой степени параллельности и использованию очень простых логических операций ANDS/XORS;
алгоритм не подвержен атакам по времени выполнения и потребляемой мощности;
хорошая стойкость к существующим атакам;
возможность распараллеливания операций в процессе шифрования;
быстрое расширение ключа, быстрое формирование ключей: шифрование со списоком ключей идет намного быстрее чем шифрование с одним блоком, так что это очень эффективно в приложениях, требующих частые замены ключей (например, в хеш-режиме).
достаточно высока скорость на всех целевых платформах;
небольшие требования к оперативной памяти и возможность расширения ключа «на лету» позволяют использовать алгоритм Crypton в смарткартах с минимальными ресурсами;
алгоритм поддерживает дополнительные размеры ключей, помимо тех, что были установлены конкурсом (128, 192, 256 битов).

Разработчиком была заявлена гарантированная устойчивость к линейному и дифференциальному криптоанализу и, в целом, всем существующим на момент разработки атакам. Переработанное ключевое расписание и новые таблицы S-Box исключили все обнаруженные недостатки и уязвимости.

Интегральная атака на шифр Crypton (4-х раундовый)

Анализ безопасности блочно-симметричного шифра (БСШ) Crypton показывает, что 12-раундовый самозаменяемый шифр (с одинаковыми процессами для кодирования и расшифрования) с длиной блока 128 битов и длиной ключа до 128 битов обладает хорошей стойкостью к существующим атакам. Интегральная атака на 4-х раундовый БСШ Crypton намного эффективнее, чем полный перебор по всему ключевому пространству.

Краткое описание шифра

Crypton представляет собой блочный шифр. Длина ключа и длина блока 128 бит. Четыре преобразования работают с промежуточным результатом, называемым Состоянием (State). Состояние можно представить в виде прямоугольного массива из 16 байт:

Обозначим столбец из 4 байт как <math>A_{j} = (A_{0j},A_{1j},A_{2j},A_{3j}) </math>

Так же представим ключ шифрования:

<math>(K_{i,j})</math> где <math>K \in \{0,...,3\}</math> и <math>K_{j} = (K_{0j},K_{1j},K_{2j},K_{3j})</math>.

В шифре определено поле Галуа <math>GF(2^8)</math>, элементами которого являются байты. Байты рассматриваются как многочлены над <math>Z_2</math>

<math>b \leftrightarrow b_{7}x^7 + b_{6}x^6 + b_{5}x^5 + b_{4}x^4 + b_{3}x^3 + b_{2}x^2 + b_{1}x^1+ b_{0}</math>

Операция сложения <math>\oplus</math> — при сложении байт соответствующие им многочлены складываются над <math>Z_2</math>.

Операция умножения — при умножении соответствующие им многочлены перемножаются над <math>Z_2</math> и результирующий многочлен берется по модулю от простого многочлена

В процессе работы алгоритма, ключ <math>(K_{i,j})</math> расширяется (Key Schedule, Key Expansion). Первые 4 столбца (по 4 байта) являются исходным ключом <math>K^0</math>. Каждый последующий <math>r</math>-й набор из 4 столбцов вычисляется из предыдущего набора и используется для <math>r</math>-ого раунда, обозначим его <math>K^r = (K_{i,j}^r)</math>. Раунд состоит из четырёх различных элементарных преобразований, которые преобразуют состояние <math>A = (A_{i,j})</math> в состояние <math>B = (B_{i,j})</math> :

Замена байт — BS (Byte Substitution): применение перестановки <math>S</math> или <math>B_{i,j} = S(A_{i,j})</math>
Сдвиг строк — SR (Shift Rows): циклический сдвиг байт по правилу: <math>B_{i,j} = A_{i,(j+1)mod4}</math>
Замешивание столбцов — MC (Mix Columns: каждый столбец состояния изменяется линейным преобразованием <math>\mu : (0,1)^{32} \rightarrow (0,1)^{32} </math>

Иначе говоря, это есть ничто иное, как умножение столбцов на матрицу слева: <math>B = \mu (A) = E = \begin{pmatrix} 2 & 3 & 1 & 1 \\ 1 & 2 & 3 & 1 \\ 1 & 1 & 2 & 3 \\ 3 & 1 & 1 & 2 \end{pmatrix}</math>

Операция <math>\mu </math> обратима : <math>A_{j} = \mu^{-1}(B_{j})</math>

Добавление раундового ключа — KA (Key Addition): к текущему состоянию прибавляется раундовый ключ.

Финальный раунд не содержит операции MC. Формулы, связывающие состояния <math>A^r</math> и <math>A^{r-1}</math>:

<math>A^r = MC(SR(S(A^{r-1}))) \oplus K^ {r-1}</math>;

<math>A^{r-1} = S^{-1}(SR^{-1}(MC^{-1}(A^r \oplus K^ {r-1}))) </math>;

Алгоритм реализации интегральной атаки

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

Введем определения.

<math>\Lambda</math> — набор из 256 входных блоков (массивов State), каждый из которых имеет байты (назовем их активными), значения которых различны для всех 256 блоков. Остальные байты (пассивные) остаются одинаковыми для всех 256 блоков из <math>\Lambda</math>-набора. То есть для любых <math>A,B \in \Lambda</math> то <math>A_{ij} \ne B_{ij}</math> если байт с индексом (i, j) активный и иначе <math>A_{ij} = B_{ij}</math>.

<math>\Lambda^r</math> — <math>\Lambda</math> c k активными байтами.

<math>P_r</math> — множество состояний в конце раунда r.

<math>\Lambda</math>-набор. После элементарных преобразований BS и KA блоки <math>\Lambda</math>-набора дадут в результате другой <math>\Lambda</math>-набор с активными байтами в тех же позициях, что и у исходного. Преобразование SR сместит эти байты соответственно заданным в ней смещениям. После преобразования MC <math>\Lambda</math>-набора в общем случае необязательно останется <math>\Lambda</math>-набором (результат операции может перестать удовлетворять определению <math>\Lambda</math>-набора). Так как каждый байт <math>B_{ij}</math> результата MC является линейной комбинацией (с обратимыми коэффициентами) четырёх входных байт того же столбца <math>B_{ij} = 2A_{ij} \oplus 3A_{i+1mod4j} \oplus A_{i+2mod4j} \oplus A_{i+3mod4j}</math>, то столбец с единственным активным байтом на входе даст в результате на выходе столбец со всеми четырьмя активными байтами.

Рассмотрим шифрование <math>\Lambda^1</math>-набора. Во всех блоках будет активен только один байт. Значение этого байта различно во всех 256 блоках, а остальные байты одинаковы. В первом раунде преобразование MC преобразует один активный байт в столбец из 4 активных байт, то есть <math>P_1</math> является <math>\Lambda^4</math>. Во втором раунде эти 4 байта разойдутся по 4 различным столбцам в результате преобразования SR, <math>P_2</math> является <math>\Lambda^{16}</math>-набором. Преобразование MC следующего, третьего раунда преобразует эти байты в 4 столбца, содержащие активные байты. Этот набор все ещё остается <math>\Lambda</math>-набором до того момента, когда он поступает на вход MC третьего раунда.

Основное свойство <math>\Lambda</math>-набора — поразрядная сумма по модулю 2 (<math>\oplus</math>) всех байтов, находящихся на одних и тех же местах, по всему набору равна нулю (поразрядная сумма неактивных (с одинаковыми значениями) байт равна нулю по определению операции «<math>\oplus</math>», а активные байты, пробегая все 256 значений, также при поразрядном суммировании дадут нуль)

Результат преобразования MC в третьем раунде байтов входного массива данных <math>A</math> в байты выходного массива данных <math>B</math> — поразрядная сумма всех блоков выходного набора будет равна нулю:

<math>\oplus_{B=MC(A),A \in \Lambda^16} B_{ij} = \oplus_{A \in \Lambda^16}(2A_{ij} \oplus 3A_{i+1mod4j} \oplus A_{i+2mod4j} \oplus A_{i+3mod4j}) = 0</math>

Таким образом <math>P_3</math> есть <math>\Lambda^{16}</math>. Полная сумма данных на входе равна нулю. Это равнество нарушается последующим преобразованием BS.

Ключ <math>K^r</math> однозначно задается в R представлении:

Для проведения атаки потребуется множество <math>Q_4</math>, состоящее из 256 состояний. <math>Q_r = SR^{-1}(MC^{-1}(A)), A \in P_r</math> Множество <math>Q_4</math> можно получить применением 2 обратных преобразований SR и MC из входных данных шифра <math>P_4</math>.

Схема базовой интегральной атаки на 4-раундовый Crypton:

Для всех <math>i,j \in {0,1,2,3}</math>

для <math>k \ in GF(2^8) </math>

если <math>\oplus_{Z \in Q} S^{-1} (Z_{ij} \oplus k) \ne 0</math>,

то <math>L^4_{ij} \ne k</math>

В этой схеме инвертируется 4-й раунд шаг за шагом, чтобы получить байты <math>P_3</math>, полная сумма которых равна 0. При <math>L^4_{ij} = k</math> сумма <math>\oplus_{Z \in Q} S^{-1} (Z_{ij} \oplus k) = 0</math>

Если предполагаемое значение байта ключа было верно, то оно будет включено в возможные варианты на место <math>L^4</math>. Большая часть неверных значений байта будет отсеяно. За счет того, что поиск может производиться отдельно (параллельно) для каждого байта ключа, скорость подбора всего значения раундового ключа весьма велика. Далее по значению <math>L^4</math> можно найти <math>K^4</math>, а потом и <math>K^0</math> — исходный ключ.

Конкурс AES

Первыми шагами навстречу изменению стандартов шифрования было создание конкурса AES. Это был открытый конкурс, проводимый институтом стандартов и технологий США — NIST (National Institute of Standart and Technology). Победитель этого конкурса должен был стать новым стандартом шифрования США. В конкурсе могли принимать частные лица, компании как внутри США так и за пределами страны. Основные требования:

128 бит — размер блока шифруемых данных.
Три или более размеров ключей должно поддерживаться алгоритмом (128, 256, 192 — бит — обязательные размеры ключей для конкурса).

Однако несмотря на малое количество требований для алгоритмов, было много пожеланий:

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

Заметим, что участникам конкурса AES разрешалось вносить изменения в алгоритмы в ходе конкурса, если это незначительные модификации. Для алгоритма Crypton при предоставлении новой версии, жюри сочли изменения значительными, так как они касались таблицы замен, процедуру расширения ключа. В результате, на конкурсе участвовала версия Crypton v0.5.

Отсутствие явных минусов и наличие достоинств у алгоритма Crypton все равно не позволило ему выйти в финал конкурса AES. Причиной тому было участие в конкурсе двух алгоритмов: Rijndael и Twofish. Эти алгоритмы не имели проблем слабых ключей как у алгоритма Crypton. Более того они были быстрее чем Crypton на целевых платформах. Было решено, что в дальнейшем Crypton проиграет в любом случае этим алгоритмам, поэтому эксперты конкурса не пропустили Crypton в финал. (Rijndael — будущий победитель конкурса).

Версии алгоритма Crypton

В конкурсе участвовала первичная редакция алгоритма, которая получила индекс 0.5 через некоторое время. Через некоторое время было предложено ещё несколько редакций, последней из которой стала версия 1.0 с переработанным ключевым расписанием и новыми таблицами подстановки.

Напишите отзыв о статье "CRYPTON"

Ссылки и Литература

[citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.52.5771&rep=rep1&type=pdf A New 128-bit Block Cipher. Specification and Analysis.] (англ)
[cs.usu.edu.ru/crypto/CRYPTON/crypton-final.pdf A New 128-bit Block Cipher Specification and Analysis Other] (англ)
[www.securitytechnet.com/resource/research/crypton/crypton-final.pdf Спецификация алгоритма]
Chae Hoon Lim CRYPTON: a new 128-bit Block Cipher–Specification and Analysis. — 1998. — DOI:10.1.1.52.5771.
Алгоритмы Шифрования. Специальный Справочник/ Автор: Сергей Петрович Панасенко/ Изд: «БХВ-Санкт-Петербург», 2009

Отрывок, характеризующий CRYPTON

– Это гадость! Это мерзость! – закричала она. – Это не может быть, чтобы вы приказали.
Берг и графиня недоумевающе и испуганно смотрели на нее. Граф остановился у окна, прислушиваясь.
– Маменька, это нельзя; посмотрите, что на дворе! – закричала она. – Они остаются!..
– Что с тобой? Кто они? Что тебе надо?
– Раненые, вот кто! Это нельзя, маменька; это ни на что не похоже… Нет, маменька, голубушка, это не то, простите, пожалуйста, голубушка… Маменька, ну что нам то, что мы увезем, вы посмотрите только, что на дворе… Маменька!.. Это не может быть!..
Граф стоял у окна и, не поворачивая лица, слушал слова Наташи. Вдруг он засопел носом и приблизил свое лицо к окну.
Графиня взглянула на дочь, увидала ее пристыженное за мать лицо, увидала ее волнение, поняла, отчего муж теперь не оглядывался на нее, и с растерянным видом оглянулась вокруг себя.
– Ах, да делайте, как хотите! Разве я мешаю кому нибудь! – сказала она, еще не вдруг сдаваясь.
– Маменька, голубушка, простите меня!
Но графиня оттолкнула дочь и подошла к графу.
– Mon cher, ты распорядись, как надо… Я ведь не знаю этого, – сказала она, виновато опуская глаза.
– Яйца… яйца курицу учат… – сквозь счастливые слезы проговорил граф и обнял жену, которая рада была скрыть на его груди свое пристыженное лицо.
– Папенька, маменька! Можно распорядиться? Можно?.. – спрашивала Наташа. – Мы все таки возьмем все самое нужное… – говорила Наташа.
Граф утвердительно кивнул ей головой, и Наташа тем быстрым бегом, которым она бегивала в горелки, побежала по зале в переднюю и по лестнице на двор.
Люди собрались около Наташи и до тех пор не могли поверить тому странному приказанию, которое она передавала, пока сам граф именем своей жены не подтвердил приказания о том, чтобы отдавать все подводы под раненых, а сундуки сносить в кладовые. Поняв приказание, люди с радостью и хлопотливостью принялись за новое дело. Прислуге теперь это не только не казалось странным, но, напротив, казалось, что это не могло быть иначе, точно так же, как за четверть часа перед этим никому не только не казалось странным, что оставляют раненых, а берут вещи, но казалось, что не могло быть иначе.
Все домашние, как бы выплачивая за то, что они раньше не взялись за это, принялись с хлопотливостью за новое дело размещения раненых. Раненые повыползли из своих комнат и с радостными бледными лицами окружили подводы. В соседних домах тоже разнесся слух, что есть подводы, и на двор к Ростовым стали приходить раненые из других домов. Многие из раненых просили не снимать вещей и только посадить их сверху. Но раз начавшееся дело свалки вещей уже не могло остановиться. Было все равно, оставлять все или половину. На дворе лежали неубранные сундуки с посудой, с бронзой, с картинами, зеркалами, которые так старательно укладывали в прошлую ночь, и всё искали и находили возможность сложить то и то и отдать еще и еще подводы.
– Четверых еще можно взять, – говорил управляющий, – я свою повозку отдаю, а то куда же их?
– Да отдайте мою гардеробную, – говорила графиня. – Дуняша со мной сядет в карету.
Отдали еще и гардеробную повозку и отправили ее за ранеными через два дома. Все домашние и прислуга были весело оживлены. Наташа находилась в восторженно счастливом оживлении, которого она давно не испытывала.
– Куда же его привязать? – говорили люди, прилаживая сундук к узкой запятке кареты, – надо хоть одну подводу оставить.
– Да с чем он? – спрашивала Наташа.
– С книгами графскими.
– Оставьте. Васильич уберет. Это не нужно.
В бричке все было полно людей; сомневались о том, куда сядет Петр Ильич.
– Он на козлы. Ведь ты на козлы, Петя? – кричала Наташа.
Соня не переставая хлопотала тоже; но цель хлопот ее была противоположна цели Наташи. Она убирала те вещи, которые должны были остаться; записывала их, по желанию графини, и старалась захватить с собой как можно больше.

Во втором часу заложенные и уложенные четыре экипажа Ростовых стояли у подъезда. Подводы с ранеными одна за другой съезжали со двора.
Коляска, в которой везли князя Андрея, проезжая мимо крыльца, обратила на себя внимание Сони, устраивавшей вместе с девушкой сиденья для графини в ее огромной высокой карете, стоявшей у подъезда.
– Это чья же коляска? – спросила Соня, высунувшись в окно кареты.
– А вы разве не знали, барышня? – отвечала горничная. – Князь раненый: он у нас ночевал и тоже с нами едут.
– Да кто это? Как фамилия?
– Самый наш жених бывший, князь Болконский! – вздыхая, отвечала горничная. – Говорят, при смерти.
Соня выскочила из кареты и побежала к графине. Графиня, уже одетая по дорожному, в шали и шляпе, усталая, ходила по гостиной, ожидая домашних, с тем чтобы посидеть с закрытыми дверями и помолиться перед отъездом. Наташи не было в комнате.
– Maman, – сказала Соня, – князь Андрей здесь, раненый, при смерти. Он едет с нами.
Графиня испуганно открыла глаза и, схватив за руку Соню, оглянулась.
– Наташа? – проговорила она.
И для Сони и для графини известие это имело в первую минуту только одно значение. Они знали свою Наташу, и ужас о том, что будет с нею при этом известии, заглушал для них всякое сочувствие к человеку, которого они обе любили.
– Наташа не знает еще; но он едет с нами, – сказала Соня.
– Ты говоришь, при смерти?
Соня кивнула головой.
Графиня обняла Соню и заплакала.
«Пути господни неисповедимы!» – думала она, чувствуя, что во всем, что делалось теперь, начинала выступать скрывавшаяся прежде от взгляда людей всемогущая рука.
– Ну, мама, все готово. О чем вы?.. – спросила с оживленным лицом Наташа, вбегая в комнату.
– Ни о чем, – сказала графиня. – Готово, так поедем. – И графиня нагнулась к своему ридикюлю, чтобы скрыть расстроенное лицо. Соня обняла Наташу и поцеловала ее.
Наташа вопросительно взглянула на нее.
– Что ты? Что такое случилось?
– Ничего… Нет…
– Очень дурное для меня?.. Что такое? – спрашивала чуткая Наташа.
Соня вздохнула и ничего не ответила. Граф, Петя, m me Schoss, Мавра Кузминишна, Васильич вошли в гостиную, и, затворив двери, все сели и молча, не глядя друг на друга, посидели несколько секунд.
Граф первый встал и, громко вздохнув, стал креститься на образ. Все сделали то же. Потом граф стал обнимать Мавру Кузминишну и Васильича, которые оставались в Москве, и, в то время как они ловили его руку и целовали его в плечо, слегка трепал их по спине, приговаривая что то неясное, ласково успокоительное. Графиня ушла в образную, и Соня нашла ее там на коленях перед разрозненно по стене остававшимися образами. (Самые дорогие по семейным преданиям образа везлись с собою.)
На крыльце и на дворе уезжавшие люди с кинжалами и саблями, которыми их вооружил Петя, с заправленными панталонами в сапоги и туго перепоясанные ремнями и кушаками, прощались с теми, которые оставались.
Как и всегда при отъездах, многое было забыто и не так уложено, и довольно долго два гайдука стояли с обеих сторон отворенной дверцы и ступенек кареты, готовясь подсадить графиню, в то время как бегали девушки с подушками, узелками из дому в кареты, и коляску, и бричку, и обратно.
– Век свой все перезабудут! – говорила графиня. – Ведь ты знаешь, что я не могу так сидеть. – И Дуняша, стиснув зубы и не отвечая, с выражением упрека на лице, бросилась в карету переделывать сиденье.
– Ах, народ этот! – говорил граф, покачивая головой.
Старый кучер Ефим, с которым одним только решалась ездить графиня, сидя высоко на своих козлах, даже не оглядывался на то, что делалось позади его. Он тридцатилетним опытом знал, что не скоро еще ему скажут «с богом!» и что когда скажут, то еще два раза остановят его и пошлют за забытыми вещами, и уже после этого еще раз остановят, и графиня сама высунется к нему в окно и попросит его Христом богом ехать осторожнее на спусках. Он знал это и потому терпеливее своих лошадей (в особенности левого рыжего – Сокола, который бил ногой и, пережевывая, перебирал удила) ожидал того, что будет. Наконец все уселись; ступеньки собрались и закинулись в карету, дверка захлопнулась, послали за шкатулкой, графиня высунулась и сказала, что должно. Тогда Ефим медленно снял шляпу с своей головы и стал креститься. Форейтор и все люди сделали то же.
– С богом! – сказал Ефим, надев шляпу. – Вытягивай! – Форейтор тронул. Правый дышловой влег в хомут, хрустнули высокие рессоры, и качнулся кузов. Лакей на ходу вскочил на козлы. Встряхнуло карету при выезде со двора на тряскую мостовую, так же встряхнуло другие экипажи, и поезд тронулся вверх по улице. В каретах, коляске и бричке все крестились на церковь, которая была напротив. Остававшиеся в Москве люди шли по обоим бокам экипажей, провожая их.
Наташа редко испытывала столь радостное чувство, как то, которое она испытывала теперь, сидя в карете подле графини и глядя на медленно подвигавшиеся мимо нее стены оставляемой, встревоженной Москвы. Она изредка высовывалась в окно кареты и глядела назад и вперед на длинный поезд раненых, предшествующий им. Почти впереди всех виднелся ей закрытый верх коляски князя Андрея. Она не знала, кто был в ней, и всякий раз, соображая область своего обоза, отыскивала глазами эту коляску. Она знала, что она была впереди всех.
В Кудрине, из Никитской, от Пресни, от Подновинского съехалось несколько таких же поездов, как был поезд Ростовых, и по Садовой уже в два ряда ехали экипажи и подводы.
Объезжая Сухареву башню, Наташа, любопытно и быстро осматривавшая народ, едущий и идущий, вдруг радостно и удивленно вскрикнула:
– Батюшки! Мама, Соня, посмотрите, это он!
– Кто? Кто?
– Смотрите, ей богу, Безухов! – говорила Наташа, высовываясь в окно кареты и глядя на высокого толстого человека в кучерском кафтане, очевидно, наряженного барина по походке и осанке, который рядом с желтым безбородым старичком в фризовой шинели подошел под арку Сухаревой башни.
– Ей богу, Безухов, в кафтане, с каким то старым мальчиком! Ей богу, – говорила Наташа, – смотрите, смотрите!
– Да нет, это не он. Можно ли, такие глупости.
– Мама, – кричала Наташа, – я вам голову дам на отсечение, что это он! Я вас уверяю. Постой, постой! – кричала она кучеру; но кучер не мог остановиться, потому что из Мещанской выехали еще подводы и экипажи, и на Ростовых кричали, чтоб они трогались и не задерживали других.
Действительно, хотя уже гораздо дальше, чем прежде, все Ростовы увидали Пьера или человека, необыкновенно похожего на Пьера, в кучерском кафтане, шедшего по улице с нагнутой головой и серьезным лицом, подле маленького безбородого старичка, имевшего вид лакея. Старичок этот заметил высунувшееся на него лицо из кареты и, почтительно дотронувшись до локтя Пьера, что то сказал ему, указывая на карету. Пьер долго не мог понять того, что он говорил; так он, видимо, погружен был в свои мысли. Наконец, когда он понял его, посмотрел по указанию и, узнав Наташу, в ту же секунду отдаваясь первому впечатлению, быстро направился к карете. Но, пройдя шагов десять, он, видимо, вспомнив что то, остановился.
Высунувшееся из кареты лицо Наташи сияло насмешливою ласкою.
– Петр Кирилыч, идите же! Ведь мы узнали! Это удивительно! – кричала она, протягивая ему руку. – Как это вы? Зачем вы так?
Пьер взял протянутую руку и на ходу (так как карета. продолжала двигаться) неловко поцеловал ее.
– Что с вами, граф? – спросила удивленным и соболезнующим голосом графиня.
– Что? Что? Зачем? Не спрашивайте у меня, – сказал Пьер и оглянулся на Наташу, сияющий, радостный взгляд которой (он чувствовал это, не глядя на нее) обдавал его своей прелестью.
– Что же вы, или в Москве остаетесь? – Пьер помолчал.
– В Москве? – сказал он вопросительно. – Да, в Москве. Прощайте.
– Ах, желала бы я быть мужчиной, я бы непременно осталась с вами. Ах, как это хорошо! – сказала Наташа. – Мама, позвольте, я останусь. – Пьер рассеянно посмотрел на Наташу и что то хотел сказать, но графиня перебила его:
– Вы были на сражении, мы слышали?
– Да, я был, – отвечал Пьер. – Завтра будет опять сражение… – начал было он, но Наташа перебила его:
– Да что же с вами, граф? Вы на себя не похожи…
– Ах, не спрашивайте, не спрашивайте меня, я ничего сам не знаю. Завтра… Да нет! Прощайте, прощайте, – проговорил он, – ужасное время! – И, отстав от кареты, он отошел на тротуар.
Наташа долго еще высовывалась из окна, сияя на него ласковой и немного насмешливой, радостной улыбкой.

Пьер, со времени исчезновения своего из дома, ужа второй день жил на пустой квартире покойного Баздеева. Вот как это случилось.
Проснувшись на другой день после своего возвращения в Москву и свидания с графом Растопчиным, Пьер долго не мог понять того, где он находился и чего от него хотели. Когда ему, между именами прочих лиц, дожидавшихся его в приемной, доложили, что его дожидается еще француз, привезший письмо от графини Елены Васильевны, на него нашло вдруг то чувство спутанности и безнадежности, которому он способен был поддаваться. Ему вдруг представилось, что все теперь кончено, все смешалось, все разрушилось, что нет ни правого, ни виноватого, что впереди ничего не будет и что выхода из этого положения нет никакого. Он, неестественно улыбаясь и что то бормоча, то садился на диван в беспомощной позе, то вставал, подходил к двери и заглядывал в щелку в приемную, то, махая руками, возвращался назад я брался за книгу. Дворецкий в другой раз пришел доложить Пьеру, что француз, привезший от графини письмо, очень желает видеть его хоть на минутку и что приходили от вдовы И. А. Баздеева просить принять книги, так как сама г жа Баздеева уехала в деревню.
– Ах, да, сейчас, подожди… Или нет… да нет, поди скажи, что сейчас приду, – сказал Пьер дворецкому.
Но как только вышел дворецкий, Пьер взял шляпу, лежавшую на столе, и вышел в заднюю дверь из кабинета. В коридоре никого не было. Пьер прошел во всю длину коридора до лестницы и, морщась и растирая лоб обеими руками, спустился до первой площадки. Швейцар стоял у парадной двери. С площадки, на которую спустился Пьер, другая лестница вела к заднему ходу. Пьер пошел по ней и вышел во двор. Никто не видал его. Но на улице, как только он вышел в ворота, кучера, стоявшие с экипажами, и дворник увидали барина и сняли перед ним шапки. Почувствовав на себя устремленные взгляды, Пьер поступил как страус, который прячет голову в куст, с тем чтобы его не видали; он опустил голову и, прибавив шагу, пошел по улице.
Из всех дел, предстоявших Пьеру в это утро, дело разборки книг и бумаг Иосифа Алексеевича показалось ему самым нужным.
Он взял первого попавшегося ему извозчика и велел ему ехать на Патриаршие пруды, где был дом вдовы Баздеева.
Беспрестанно оглядываясь на со всех сторон двигавшиеся обозы выезжавших из Москвы и оправляясь своим тучным телом, чтобы не соскользнуть с дребезжащих старых дрожек, Пьер, испытывая радостное чувство, подобное тому, которое испытывает мальчик, убежавший из школы, разговорился с извозчиком.
Извозчик рассказал ему, что нынешний день разбирают в Кремле оружие, и что на завтрашний народ выгоняют весь за Трехгорную заставу, и что там будет большое сражение.
Приехав на Патриаршие пруды, Пьер отыскал дом Баздеева, в котором он давно не бывал. Он подошел к калитке. Герасим, тот самый желтый безбородый старичок, которого Пьер видел пять лет тому назад в Торжке с Иосифом Алексеевичем, вышел на его стук.
– Дома? – спросил Пьер.
– По обстоятельствам нынешним, Софья Даниловна с детьми уехали в торжковскую деревню, ваше сиятельство.
– Я все таки войду, мне надо книги разобрать, – сказал Пьер.
– Пожалуйте, милости просим, братец покойника, – царство небесное! – Макар Алексеевич остались, да, как изволите знать, они в слабости, – сказал старый слуга.
Макар Алексеевич был, как знал Пьер, полусумасшедший, пивший запоем брат Иосифа Алексеевича.
– Да, да, знаю. Пойдем, пойдем… – сказал Пьер и вошел в дом. Высокий плешивый старый человек в халате, с красным носом, в калошах на босу ногу, стоял в передней; увидав Пьера, он сердито пробормотал что то и ушел в коридор.
– Большого ума были, а теперь, как изволите видеть, ослабели, – сказал Герасим. – В кабинет угодно? – Пьер кивнул головой. – Кабинет как был запечатан, так и остался. Софья Даниловна приказывали, ежели от вас придут, то отпустить книги.
Пьер вошел в тот самый мрачный кабинет, в который он еще при жизни благодетеля входил с таким трепетом. Кабинет этот, теперь запыленный и нетронутый со времени кончины Иосифа Алексеевича, был еще мрачнее.
Герасим открыл один ставень и на цыпочках вышел из комнаты. Пьер обошел кабинет, подошел к шкафу, в котором лежали рукописи, и достал одну из важнейших когда то святынь ордена. Это были подлинные шотландские акты с примечаниями и объяснениями благодетеля. Он сел за письменный запыленный стол и положил перед собой рукописи, раскрывал, закрывал их и, наконец, отодвинув их от себя, облокотившись головой на руки, задумался.
Несколько раз Герасим осторожно заглядывал в кабинет и видел, что Пьер сидел в том же положении. Прошло более двух часов. Герасим позволил себе пошуметь в дверях, чтоб обратить на себя внимание Пьера. Пьер не слышал его.
– Извозчика отпустить прикажете?
– Ах, да, – очнувшись, сказал Пьер, поспешно вставая. – Послушай, – сказал он, взяв Герасима за пуговицу сюртука и сверху вниз блестящими, влажными восторженными глазами глядя на старичка. – Послушай, ты знаешь, что завтра будет сражение?..
– Сказывали, – отвечал Герасим.
– Я прошу тебя никому не говорить, кто я. И сделай, что я скажу…
– Слушаюсь, – сказал Герасим. – Кушать прикажете?
– Нет, но мне другое нужно. Мне нужно крестьянское платье и пистолет, – сказал Пьер, неожиданно покраснев.
– Слушаю с, – подумав, сказал Герасим.
Весь остаток этого дня Пьер провел один в кабинете благодетеля, беспокойно шагая из одного угла в другой, как слышал Герасим, и что то сам с собой разговаривая, и ночевал на приготовленной ему тут же постели.
Герасим с привычкой слуги, видавшего много странных вещей на своем веку, принял переселение Пьера без удивления и, казалось, был доволен тем, что ему было кому услуживать. Он в тот же вечер, не спрашивая даже и самого себя, для чего это было нужно, достал Пьеру кафтан и шапку и обещал на другой день приобрести требуемый пистолет. Макар Алексеевич в этот вечер два раза, шлепая своими калошами, подходил к двери и останавливался, заискивающе глядя на Пьера. Но как только Пьер оборачивался к нему, он стыдливо и сердито запахивал свой халат и поспешно удалялся. В то время как Пьер в кучерском кафтане, приобретенном и выпаренном для него Герасимом, ходил с ним покупать пистолет у Сухаревой башни, он встретил Ростовых.

1 го сентября в ночь отдан приказ Кутузова об отступлении русских войск через Москву на Рязанскую дорогу.
Первые войска двинулись в ночь. Войска, шедшие ночью, не торопились и двигались медленно и степенно; но на рассвете двигавшиеся войска, подходя к Дорогомиловскому мосту, увидали впереди себя, на другой стороне, теснящиеся, спешащие по мосту и на той стороне поднимающиеся и запружающие улицы и переулки, и позади себя – напирающие, бесконечные массы войск. И беспричинная поспешность и тревога овладели войсками. Все бросилось вперед к мосту, на мост, в броды и в лодки. Кутузов велел обвезти себя задними улицами на ту сторону Москвы.
К десяти часам утра 2 го сентября в Дорогомиловском предместье оставались на просторе одни войска ариергарда. Армия была уже на той стороне Москвы и за Москвою.
В это же время, в десять часов утра 2 го сентября, Наполеон стоял между своими войсками на Поклонной горе и смотрел на открывавшееся перед ним зрелище. Начиная с 26 го августа и по 2 е сентября, от Бородинского сражения и до вступления неприятеля в Москву, во все дни этой тревожной, этой памятной недели стояла та необычайная, всегда удивляющая людей осенняя погода, когда низкое солнце греет жарче, чем весной, когда все блестит в редком, чистом воздухе так, что глаза режет, когда грудь крепнет и свежеет, вдыхая осенний пахучий воздух, когда ночи даже бывают теплые и когда в темных теплых ночах этих с неба беспрестанно, пугая и радуя, сыплются золотые звезды.
2 го сентября в десять часов утра была такая погода. Блеск утра был волшебный. Москва с Поклонной горы расстилалась просторно с своей рекой, своими садами и церквами и, казалось, жила своей жизнью, трепеща, как звезды, своими куполами в лучах солнца.
При виде странного города с невиданными формами необыкновенной архитектуры Наполеон испытывал то несколько завистливое и беспокойное любопытство, которое испытывают люди при виде форм не знающей о них, чуждой жизни. Очевидно, город этот жил всеми силами своей жизни. По тем неопределимым признакам, по которым на дальнем расстоянии безошибочно узнается живое тело от мертвого. Наполеон с Поклонной горы видел трепетание жизни в городе и чувствовал как бы дыханио этого большого и красивого тела.
– Cette ville asiatique aux innombrables eglises, Moscou la sainte. La voila donc enfin, cette fameuse ville! Il etait temps, [Этот азиатский город с бесчисленными церквами, Москва, святая их Москва! Вот он, наконец, этот знаменитый город! Пора!] – сказал Наполеон и, слезши с лошади, велел разложить перед собою план этой Moscou и подозвал переводчика Lelorgne d'Ideville. «Une ville occupee par l'ennemi ressemble a une fille qui a perdu son honneur, [Город, занятый неприятелем, подобен девушке, потерявшей невинность.] – думал он (как он и говорил это Тучкову в Смоленске). И с этой точки зрения он смотрел на лежавшую перед ним, невиданную еще им восточную красавицу. Ему странно было самому, что, наконец, свершилось его давнишнее, казавшееся ему невозможным, желание. В ясном утреннем свете он смотрел то на город, то на план, проверяя подробности этого города, и уверенность обладания волновала и ужасала его.
«Но разве могло быть иначе? – подумал он. – Вот она, эта столица, у моих ног, ожидая судьбы своей. Где теперь Александр и что думает он? Странный, красивый, величественный город! И странная и величественная эта минута! В каком свете представляюсь я им! – думал он о своих войсках. – Вот она, награда для всех этих маловерных, – думал он, оглядываясь на приближенных и на подходившие и строившиеся войска. – Одно мое слово, одно движение моей руки, и погибла эта древняя столица des Czars. Mais ma clemence est toujours prompte a descendre sur les vaincus. [царей. Но мое милосердие всегда готово низойти к побежденным.] Я должен быть великодушен и истинно велик. Но нет, это не правда, что я в Москве, – вдруг приходило ему в голову. – Однако вот она лежит у моих ног, играя и дрожа золотыми куполами и крестами в лучах солнца. Но я пощажу ее. На древних памятниках варварства и деспотизма я напишу великие слова справедливости и милосердия… Александр больнее всего поймет именно это, я знаю его. (Наполеону казалось, что главное значение того, что совершалось, заключалось в личной борьбе его с Александром.) С высот Кремля, – да, это Кремль, да, – я дам им законы справедливости, я покажу им значение истинной цивилизации, я заставлю поколения бояр с любовью поминать имя своего завоевателя. Я скажу депутации, что я не хотел и не хочу войны; что я вел войну только с ложной политикой их двора, что я люблю и уважаю Александра и что приму условия мира в Москве, достойные меня и моих народов. Я не хочу воспользоваться счастьем войны для унижения уважаемого государя. Бояре – скажу я им: я не хочу войны, а хочу мира и благоденствия всех моих подданных. Впрочем, я знаю, что присутствие их воодушевит меня, и я скажу им, как я всегда говорю: ясно, торжественно и велико. Но неужели это правда, что я в Москве? Да, вот она!»