КРИПТОГРАФИЯ НА ОСНОВЕ КОДОВ ИСПРАВЛЕНИЯ ОШИБОК

Введение

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

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

В отличии от кодов исправления ошибок, коды их обнаружения могут только проверить существование ошибки, но не исправить. Но обнаружить их могут и используемые коды исправления, так как они принадлежат одним классам кодов.

K_об > К_исп, где K_об - количество обнаруженных ошибок, а К_исп - исправленных.

На основании кодов исправления ошибок существуют криптосистемы с открытыми ключами. Самыми распространенными являются алгоритмы шифрования McEliece и Niederreiter.

Криптосистема McEliece

Криптосистема с открытыми ключами McEliece была разработана Робертом Мак-Элисом в 1978 году. В ней впервые использовалась рандомизация в процессе зашифровки. Кроме того, основанием алгоритма является сложность процесса декодирования полных линейных кодов.

Открытый ключ получается путем перемножения производящей матрицы G на невырожденные случайные матрицы S и P. В качестве закрытого ключа выступает код исправления ошибок, количество которых равно t, а также применяется эффективный алгоритм декодирования. Обычно в алгоритме оперируют двоичные коды Гоппа.

McElice с использованием кодов Гоппы до сих пор не поддается криптоанализу.

Алгоритм работы McEliece

Криптосистема использует 3 этапа:

1) Генерация ключа, выдающего открытый и закрытый ключ.

  а) Выбирается двоичный (n,k) - линейный код C, который исправляет t ошибок. Для кода С вычисляется k x n производящая матрица G.

  б) Генерируются случайные n x n матрица перестановки P и невырожденная k x k матрица S.

  в) Высчитывается k x n матрица G"=SGP.

  г) Закрытый ключ представляет собой набор (S,G,P), а открытый ключ пару (G",t).

2) Шифрование передаваемого сообщения.

  а) Сообщение m представляется в виде последовательности бинарных символов длины k.

  б) Вычисляется вектор с"=mG".

  в) Генерирование случайного вектора z длины n, содержащий в себе t единиц.

  г) Вычисляется зашифрованное сообщение c=c" + z.

3) Расшифровка принятого зашифрованного сообщения.

  а) Вычисление обратных матриц P^-1 и S^-1.

  б) Вычисление с'=c P^-1.

  в) Используется алгоритм расшифровки для кода С (двоичные коды Гоппа легко декодируются с помощью алгоритма Петерсона), для получения m' из с'.

  г) Вычисление исходного сообщения m=m'S^-1.

Пример работы McEliece

Пусть используется (7,4) код Хемминга, исправляющий все единичные ошибки. 

Рисунок 1. G - производящая 4 x 7 матрица, S - случайная невырожденная 4 x 4 матрица, P - случайная 7 x 7 матрица перестановки.

Далее высчитывается 4 x 7  матрица G"= SGP, являющаяся частью открытого ключа.

Рисунок 2. Матрица G"

Пусть необходимо послать сообщение m = (1101), тогда сначала генерируется вектор z с весом 1. Например, z = (0000100). Затем вычисляется зашифрованный текст c = mG" + z = (0110010) + (0000100) = (0110110).

Для расшифровки сообщения используются обратные матрицы P^-1 и S^-1.

Рисунок 3. Обратные матрицы P^-1 и S^-1

Сначала вычисляется с'=cP^-1= (1000111). Далее с помощью быстрого алгоритма декодирования (алгоритма Хэмминга) расшифровывается с'. Синдромом c' является (1110)^T, значит в 7 позиции произошла ошибка. Сообщение будет y' = (1000110). Отбрасывая лишние биты у у', получается сообщение m' = (1000). Так как производящая матрица G была выбрана верно, а так же зная, что m' = (1000) и m'=mS, можно найти исходное сообщение m=m'S^-1=(1000)=(1101).

Недостатки криптосистемы McEliece

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

Перспективы использования McEliece

Учеными неустанно ведутся разработки по созданию квантовых компьютеров. Естественно рано или поздно они достигнут в этом успеха, и будут созданы квантовые компьютеры.

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

Как только их работоспособность перейдет в полную силу, всей современной популярной криптографии с открытыми ключами придет конец. RSA, DH, ECC, DSA и другие криптоалгоритмы для обмена цифровых подписей и ключей утратят свою силу.

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

Список литературы:

1. Jesse R. Robert McEliece. Москва, издательство “Книга по требованию”, 2012