alt text

Исправленное решение по совету falcao:

Итак было предложено составить матричное уравнение $%AB = C$%, после домножения обоих частей на $%{B^{ - 1}}$% получаем $%A = {B^{ - 1}}C$%. Это справедливо так как $%B{B^{ - 1}} = 1$%. Матрица $%B$% состоит из столбцов векторов открытого текста, матрица $%C$% состоит из столбцов векторов зашифрованного текста. Далее идет модульная арифметика в поле $%{\mathbb{F}_{16}} = {\mathbb{F}_2}[x]/\left\langle {{x^4} + x + 1} \right\rangle$% :

$%{B^{ - 1}} = \frac{1}{{\det \,B}} \cdot {\text{adj}}\,B,\,\,\,\,B = \begin{bmatrix}d & 3 \\5 & 1 \end{bmatrix} = \begin{bmatrix}{{x^3} + {x^2} + 1} & {x + 1} \\{{x^2} + 1} & 1 \end{bmatrix}$% $%{\text{adj}}\,B = \begin{bmatrix}1 & {x + 1} \\{{x^2} + 1} & {{x^3} + {x^2} + 1} \end{bmatrix} ,\,\,\,\det \,B = {x^3} + {x^2} + 1 - ({x^2} + 1)(x + 1) = x $%

Далее через алгоритм Евклида находим $%{x^4} + x + 1 = x \cdot ({x^3} + 1) + 1 \Leftrightarrow {x^{ - 1}} = {x^3} + 1$%

$%{B^{ - 1}} = ({x^3} + 1) \cdot \begin{bmatrix}1 & {x + 1} \\{{x^2} + 1} & {{x^3} + {x^2} + 1} \end{bmatrix} = \begin{bmatrix}{x^3} + 1 & {x^3} \\{x^3} + x + 1 & {x^3} + {x^2} + x + 1 \end{bmatrix} = \begin{bmatrix}9 & 8 \\b & f \end{bmatrix}$%

$%{C} = \begin{bmatrix}{{x^2} + x + 1} & {{x^3} + {x^2} + 1} \\{x^2} & {{x^3} + {x^2}} \end{bmatrix}$%

$%{A}=C{B^{ - 1}} = \begin{bmatrix}{{x^2} + x + 1} & {{x^3} + {x^2} + 1} \\{x^2} & {{x^3} + {x^2}} \end{bmatrix} \cdot \begin{bmatrix}{x^3} + 1 & {x^3} \\{x^3} + x + 1 & {x^3} + {x^2} + x + 1 \end{bmatrix} = \begin{bmatrix}c & a \\f & e \end{bmatrix}$%

Проверка:

Положим два вектора открытого текста: $%m = \begin{bmatrix}d \\5 \end{bmatrix} = \begin{bmatrix}{x^3} + {x^2} + 1 \\{x^2} + 1 \end{bmatrix}$% и $%n = \begin{bmatrix}3 \\1 \end{bmatrix}=\begin{bmatrix}x+1 \\1 \end{bmatrix}$%

Для шифрования используем формулу аффинного шифра: $%{e_K}(x) = A \cdot x + b,\, n = 2,\,\,\,\mathcal{P} = \mathcal{C} = {\mathbb{F}_{16}^2}$%

В данном случае нулевой вектор $%b$% не играет роли поэтому:

$%{e_K}(m) = A \cdot m = \begin{bmatrix}{x^3} + 1 & {x^3} \\{x^3} + x + 1 & {x^3} + {x^2} + x + 1 \end{bmatrix} \cdot \begin{bmatrix}{x^3} + {x^2} + 1 \\{x^2} + 1 \end{bmatrix} = \begin{bmatrix} {x^2} + x + 1\\{x^2} \end{bmatrix}=\begin{bmatrix}7 \\4 \end{bmatrix}$%

$%{e_K}(n) = A \cdot n = \begin{bmatrix}{x^3} + 1 & {x^3} \\{x^3} + x + 1 & {x^3} + {x^2} + x + 1 \end{bmatrix} \cdot \begin{bmatrix}x+1 \\1 \end{bmatrix}= \begin{bmatrix} {x^3} + {x^2} + 1\\{x^3}+{x^2} \end{bmatrix}=\begin{bmatrix}d \\c \end{bmatrix}$%

Проверка показала что $%{A} = \begin{bmatrix}c & a \\f & e \end{bmatrix}$% искомая часть ключа $%K = \{ A,b\} $%

alt text

задан 30 Сен '14 9:29

изменен 30 Сен '14 22:40

10|600 символов нужно символов осталось
1

Надо составить матричное уравнение $%AB=C$%, где $%A$% -- неизвестная матрица, $%B$% состоит из столбцов d, 5 и 3, 1 (то есть по строкам идут d, 3, 5, 1), а $%C$% состоит из столбцов 7, 4 и d, c. Тогда $%A$% выражается как $%A=CB^{-1}$%.

Для нахождения обратной матрицы сначала находим определитель. Он равен $%\det B=(x^3+x^2+1)\cdot1-(x^2+1)(x+1)=x$%. При вычислениях над данным полем учитываем то, что оно имеет характеристику 2, то есть нет разницы между сложением и вычитанием. Кроме того, учитываем уравнение $%x^4=x+1$%, из которого при необходимости выражаются все степени выше третьей. Например, $%x^5=x^2+x$% и так далее.

Обратная матрица находится по обычным правилам: надо у $%B$% поменять местами элементы главной диагонали и разделить полученную матрицу на определитель $%x$%. Из равенства $%x(x^3+1)=1$% следует, что $%x^{-1}=x^3+1$%. Остаётся перемножить две матрицы и упростить полученные выражения, избавляясь от больших степеней. В конце делим все матричные элементы на $%x$%, и получаем ответ.

ссылка

отвечен 30 Сен '14 17:28

Спасибо Огромное! Вы меня выручили. Скоро я оформлю исправленное решение и у меня есть пару вопросов, которые я добавлю к решению)

(30 Сен '14 20:54) night-raven

@void_pointer: если $%b$% ненулевой, то неизвестных становится уже 6 вместо 4. Тогда надо три условия на $%e_K$% вместо двух. Беря две разности, мы получаем задачу без сдвига. Решая, находим A. Потом подставляем в третье условие, находя $%b$%.

Второй пункт я не понимаю. Что означает равенство $%\mathbb R=\mathbb Z_{26}$%? "Множество действительных чисел равно кольцу вычетов по модулю 26". Как такое возможно?

Сводить вычисления в поле из 16 элементов к вычислениям по модулю 26 -- такой приём если и имеется, но мне он не известен. Как и за счёт чего это осуществляется?

(30 Сен '14 23:28) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,005
×468
×120
×56
×9

задан
30 Сен '14 9:29

показан
1361 раз

обновлен
30 Сен '14 23:28

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru