WikiSort.ru - Не сортированное

Генерация ключа

1. Алиса выбирает ${\displaystyle (n,k)}$ код ${\displaystyle C}$ над полем Галуа ${\displaystyle GF(q)}$ , исправляющий ${\displaystyle t}$ ошибок. Этот код должен обладать эффективным алгоритмом декодирования^[3].
2. Алиса генерирует ${\displaystyle (n-k)\times n}$ проверочную матрицу ${\displaystyle H}$ кода ${\displaystyle C}$ .
3. Алиса выбирает случайную ${\displaystyle (n-k)\times (n-k)}$ невырожденную матрицу ${\displaystyle S}$ над полем ${\displaystyle GF(q)}$ и некоторую ${\displaystyle n\times n}$ матрицу перестановки ${\displaystyle P}$ ^[3].
4. Алиса вычисляет ${\displaystyle (n-k)\times n}$ матрицу ${\displaystyle H_{pub}=SHP}$
5. Открытым ключом Алисы является пара ${\displaystyle (H_{pub},t)}$ . Закрытым ключом является набор ${\displaystyle (S^{-1},H,P^{-1})}$ .

Шифрование сообщения

В данном случае сообщения — это все ${\displaystyle n-}$ векторы с координатами из поля ${\displaystyle GF(q)}$ с весом, не превосходящим ${\displaystyle t}$ . Таким образом, сообщениями являются все возможные ошибки, которые выбранный код в состоянии исправить^[2].
Предположим, что Боб хочет отправить сообщение Алисе, чей открытый ключ ${\displaystyle (H_{pub},t)}$ .

1. Боб представляет своё сообщение в виде двоичной последовательности ${\displaystyle m}$ длины ${\displaystyle n}$ , имеющей вес ${\displaystyle t}$ .
2. Боб вычисляет шифротекст по формуле: ${\displaystyle c=mH_{pub}^{T}}$ . Таким образом, шифротекстом в криптосистеме Нидеррайтера является зашумленный синдром шифруемого вектора ошибки^[2].

Расшифровывание сообщения

После получения сообщения ${\displaystyle c}$ , Алиса выполняет следующие действия:

1. Алиса вычисляет ${\displaystyle s=c{(S^{T})}^{-1}=mP^{T}H^{T}S^{T}(S^{T})^{-1}=(mP^{T})H^{T}={\hat {m}}H^{T}}$ . Заметим, что, так как ${\displaystyle P}$  — матрица перестановки, вес ${\displaystyle {\hat {m}}=(mP^{T})}$ совпадает с весом ${\displaystyle m}$ и не превосходит ${\displaystyle t}$ , и потому алгоритм декодирования для ${\displaystyle C}$ может найти вектор ошибки, соответствующий синдрому ${\displaystyle s}$ ^[3].
2. Алиса использует алгоритм быстрого декодирования для кода ${\displaystyle C}$ , чтобы найти ${\displaystyle {\hat {m}}}$ ^[3].
3. Алиса вычисляет сообщение ${\displaystyle {\hat {m}}P^{-1}=mPP^{-1}=m}$ .

Преимущества

• В отличие от McEliece, в криптосистеме Нидеррайтера не используются случайные параметры. Таким образом, результат шифрования одного и того же текста будет одинаковым. Этот факт позволяет использовать именно систему Нидеррайтера, а не McEliece, для создания электронно-цифровой подписи.
• Размер открытого ключа в криптосистеме Нидеррайтера в ${\displaystyle {\frac {n-k}{n}}}$ раз меньше, чем в McEliece^[6].
• По сравнению с RSA, скорость шифрования выше приблизительно в 50 раз, а дешифрования — в 100 раз^[6].

Недостатки

• Для шифрования произвольного сообщения необходим алгоритм перевода в ${\displaystyle q}$ -арный вектор длиной ${\displaystyle n}$ веса не более ${\displaystyle t}$ .
• Размер ключей больше, чем в классических криптосистемах с открытым ключом (RSA, Схема Эль-Гамаля, ГОСТ Р 34.10-2012).
• Размер шифротекста намного больше, чем размер шифруемого сообщения (если сообщение размера ${\displaystyle t}$ переводится в вектор длиной ${\displaystyle n}$ и шифруется, то получается шифротекст размером ${\displaystyle n-k}$ , что не менее, чем в 2 раза превосходит ${\displaystyle t}$ ).

Ниже в таблице приведены различные параметры для криптосистем McEliece, Нидеррайтера и RSA, наглядно показывающие их преимущества и недостатки^[6].

Подпись сообщения

Пусть ${\displaystyle H_{pub}}$  — открытый ключ криптосистемы Нидеррайтера, использующей ${\displaystyle (n,k,d)}$ -линейный код. Для подписи документа ${\displaystyle D}$ необходимо:

1. Выбрать хеш-функцию ${\displaystyle h()}$ , дающей ${\displaystyle n-k}$ символов на выходе. Таким образом, результат данной хеш-функции можно представить в виде синдрома и попытаться декодировать;
2. Вычислить хеш ${\displaystyle s=h(D)}$ ;
3. Для каждого ${\displaystyle i=0,1,2,...}$ вычислить ${\displaystyle s_{i}=h(s|i)}$ ;
4. Найти наименьший номер ${\displaystyle i_{min}}$ такой, что синдром ${\displaystyle s_{i_{min}}}$ будет возможно декодировать. Пусть ${\displaystyle z}$  — результат декодирования синдрома ${\displaystyle s_{i_{min}}}$ ;
5. Подписью документа ${\displaystyle D}$ является пара ${\displaystyle (z,i_{min})}$ .

Проверка подписи

1. Вычислить ${\displaystyle s_{1}=zH_{pub}^{T}}$ ;
2. Вычислить ${\displaystyle s_{2}=h(h(D)|i_{min})}$ ;
3. Сравнить ${\displaystyle s_{1}}$ и ${\displaystyle s_{2}}$ : если они совпадают — подпись верна.

Генерация ключей

Пусть выбрана матрица ${\displaystyle S={\begin{pmatrix}4&1&3&5\\7&1&5&2\\2&6&5&4\\1&7&2&1\end{pmatrix}}}$ . Тогда обратная к ней матрица ${\displaystyle S^{-1}={\begin{pmatrix}1&5&2&7\\7&5&0&7\\4&4&1&5\\1&0&0&4\end{pmatrix}}}$

Пусть выбрана матрица перестановки ${\displaystyle P={\begin{pmatrix}0&1&0&0&0&0&0\\0&0&0&1&0&0&0\\0&0&0&0&1&0&0\\1&0&0&0&0&0&0\\0&0&0&0&0&0&1\\0&0&1&0&0&0&0\\0&0&0&0&0&1&0\\\end{pmatrix}}}$

В этом случае открытым ключом системы будет матрица: ${\displaystyle H_{pub}=SHP={\begin{pmatrix}1&3&7&5&6&0&2\\0&1&0&1&1&3&5\\2&5&1&0&6&2&0\\6&5&6&4&2&4&6\end{pmatrix}}}$

Шифрование

Пусть выбранное сообщение было представлено в виде вектора ${\displaystyle m={\begin{pmatrix}0&2&0&0&0&5&0\end{pmatrix}}}$ веса 2.

Зашифрованное сообщение: ${\displaystyle M=mH_{pub}^{T}={\begin{pmatrix}7&2&7&7\end{pmatrix}}}$

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

Принятый вектор ${\displaystyle M={\begin{pmatrix}7&2&7&7\end{pmatrix}}}$

Для него вычислим декодируемый синдром ${\displaystyle s=M(S^{-1})^{T}={\begin{pmatrix}0&1&3&6\end{pmatrix}}}$

Используя алгоритм декодирования кода Рида-Соломона, декодируем ${\displaystyle s}$ .

Получится вектор ${\displaystyle {\hat {m}}={\begin{pmatrix}2&0&0&0&0&0&5\end{pmatrix}}}$

После чего вычислим исходный вектор ${\displaystyle m=~{\hat {m}}P^{-1}={\begin{pmatrix}0&2&0&0&0&5&0\end{pmatrix}}}$