Пусть для передачи информации используется криптосистема Мак-Элиса. Ваш секретный ключ составляют невырожденная матрица M, порождающая матрица G и матрица S, соответству- ющая перестановке π. Секретная информация представлена двоичными блоками длины 3. Сгенерируйте открытый ключ криптосистемы. Дешифруйте зашифрованное сообщение b = (101100) и восстановите конфиденциальную информацию при условии, что ваш секретный ключ составляют матрицы M =1 0 1 0 1 0 0 1 1,

G =1 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1

и перестановка π =1 2 3 4 5 6 1 4 2 5 3 6

задан 10 Янв 17:22

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

Это стандартная учебно-тренировочная задачка из криптографии.

Условие задачи (переписываю для удобства)

Полный секретный (приватный) ключ составляют следующие объекты:

  • $%M$% — невырожденная матрица размера $%3\times3$%;
  • $%G$% — порождающая матрица размера $%3\times6$% линейного кода, для которого существует некоторый эффективный алгоритмом декодирования;
  • $%\pi$% — перестановка заданная на $%6$%-и элементах или соответствующая ей матрица перестановки $%P$% размера $%6\times6$%, в которой в каждой строке и в каждом столбце находится только одна единица, а остальные элементы равны нулю.

Согласно приведенному условию, имеем: $$M=\begin{pmatrix} 1&0&1\\ 0&1&0\\ 0&1&1 \end{pmatrix},$$ $$G=\begin{pmatrix} 1&0&0&1&1&0\\ 0&1&0&1&0&1\\ 0&0&1&0&1&1 \end{pmatrix},$$ $$\pi=\begin{pmatrix} 1&2&3&4&5&6\\ 1&4&2&5&3&6 \end{pmatrix} \text{ или } P=\begin{pmatrix} 1&0&0&0&0&0\\ 0&0&0&1&0&0\\ 0&1&0&0&0&0\\ 0&0&0&0&1&0\\ 0&0&1&0&0&0\\ 0&0&0&0&0&1 \end{pmatrix}.$$

1. Поиск открытого ключа

Полный открытый (публичный) ключ составляют порождающая матрица $%G'$% линейного кода такая, что $$G'=M\cdot G\cdot P,$$ и параметр $%t$%, указывающий на максимальное количество ошибок, исправляемых кодом, заданным порождающей матрицей $%G'$%.

Произведение матриц для вычисления $%G'$% оставим в качестве мелкого упражнения, а вот определение параметра $%t$% может потребовать некоторых знаний из теории кодов, исправляющих ошибки. Прежде всего, следует отметить, что кодовое расстояние $%d$% исходного кода с порождающей матрицей $%G$% совпадает с кодовым расстоянием кода, заданного порождающей матрицей $%G'$%. Таким образом, максимальное количество ошибок $%t$%, исправляемых заданным кодом с кодовым расстоянием $%d$%, равно $%\lfloor\frac{d-1}{2}\rfloor$%.

Для определения кодового расстояния $%d$% строим из порождающей матрицы $%G$% линейного кода его проверочную матрицу $%H$% с помощью теоремы о связи между проверочной и порождающей матрицами линейного кода. Далее минимальное количество линейно зависимых столбцов проверочной матрицы $%H$% — это и есть кодовое расстояние $%d$% согласно теореме о столбцах проверочной матрицы линейного кода.

Теорема о связи между проверочной и порождающей матрицами линейного кода. Если порождающая матрица линейного кода в каноническом виде имеет вид $$G=(E_k|A_{k,n-k}),$$ то проверочная матрица данного кода имеет вид: $$H=(-A_{k,n-k}^\top|E_{n-k}).$$ Верно и обратное.

Теорема о столбцах проверочной матрицы линейного кода. Линейный код, заданный проверочной матрицей, имеет кодовое расстояние $%d$% тогда и только тогда, когда любые $%d-1$% столбцов его проверочной матрицы линейно независимы, и существует $%d$% линейно зависимых столбцов.

Кодовое расстояние линейного кода также можно определить методом "пристального взгляда" на порождающую матрицу. Дело в том, что кодовое расстояние линейного кода совпадает с наименьшим весом ненулевого кодового слова данного кода.

Воспользовавшись приведенной теорией можно обнаружить, что кодовое расстояние данного в условии кода равно $%3$%, то есть код исправляет одну ошибку ($%t=1$%).

2. Дешифование

Итак, с публичным ключом разобрались, перейдем к дешифрованию шифротекста $%b=(101100)$%. Заметим, что шифротекст получен следующим образом $$b=u\cdot G'+e,$$ где $%u$% — исходное секретное сообщение, $%e$% — случайный вектор ошибок веса не более, в нашем случае $%t=1$%. Применим к шифротексту $%b$% обратную перестановку: $$b\cdot P^{-1}=u\cdot G'\cdot P^{-1}+e\cdot P^{-1}=u\cdot M\cdot G\cdot P\cdot P^{-1}+e\cdot P^{-1}=u'\cdot G+e',$$ где $%u'=u\cdot M$% — преобразованное исходное секретное сообщение, $%e'=e\cdot P$% — вектор ошибок с переставленными координатными позициями согласно перестановки $%\pi$%.

Следует отметить, что выражение $%u'\cdot G+e'$% представляет собой не что иное, как кодирование информационного блока $%u'$% кодом с порождающей матрицей $%G$% с одновременным внесением не более $%t$% ошибок, поскольку вектор ошибок $%e'$% имеет тот же вес, что и вектор ошибок $%e$%. Таким образом, применяя существующий для исходного кода эффективный алгоритм декодирования (в нашем случае следует воспользоваться методом синдромов), исправляем ошибки и получаем преобразованное исходное секретное сообщение $%u'$%. Далее остается воспользоваться обратной матрицей к невырожденной матрице $%M$% для вычисления исходного секретного сообщения: $$u=u'\cdot M^{-1}.$$

Применяя приведенную схему дешифрования, получим: $$b\cdot P^{-1}=(110010), e'=(000001), u'=(110), u=(101).$$

ссылка

отвечен 14 Июл 23:00

изменен 14 Июл 23:14

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×40

задан
10 Янв 17:22

показан
240 раз

обновлен
14 Июл 23:14

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

по почте:

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

по RSS:

Ответы

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

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