Русская Википедия:Криптосистема Нидеррайтера
Криптосистема Нидеррайтера — криптосистема с открытыми ключами, основанная на теории алгебраического кодирования, разработанная в 1986 году Харальдом НидеррайтеромШаблон:Source-ref. В отличие от криптосистемы McEliece, в криптосистеме Нидеррайтера используется проверочная матрица кода. Криптосистема Нидеррайтера позволяет создавать цифровые подписи и является кандидатом для постквантовой криптографии, поскольку устойчива к атаке с использованием алгоритма Шора.
Используемый в криптосистеме Нидеррайтера алгоритм основан на сложности декодирования полных линейных кодов.
Несмотря на то, что данная криптосистема была взломана, некоторые её модификации остаются криптостойкимиШаблон:Source-ref
Алгоритм работы
Генерация ключа
- Алиса выбирает <math>(n,k)</math> код <math>C</math> над полем Галуа <math>GF(q)</math>, исправляющий <math>t</math> ошибок. Этот код должен обладать эффективным алгоритмом декодированияШаблон:Source-ref.
- Алиса генерирует <math>(n-k) \times n</math> проверочную матрицу <math>H</math> кода <math>C</math>.
- Алиса выбирает случайную <math>(n-k) \times (n-k)</math> невырожденную матрицу <math>S</math> над полем <math>GF(q)</math> и некоторую <math>n \times n</math> матрицу перестановки <math>P</math>Шаблон:Source-ref.
- Алиса вычисляет <math>(n-k) \times n</math> матрицу <math>H_{pub}=SHP</math>
- Открытым ключом Алисы является пара <math>(H_{pub},t)</math>. Закрытым ключом является набор <math>(S^{-1},H,P^{-1})</math>.
Шифрование сообщения
В данном случае сообщения — это все <math>n-</math>векторы с координатами из поля <math>GF(q)</math> с весом, не превосходящим <math>t</math>. Таким образом, сообщениями являются все возможные ошибки, которые выбранный код в состоянии исправитьШаблон:Source-ref.
Предположим, что Боб хочет отправить сообщение Алисе, чей открытый ключ <math>(H_{pub},t)</math>.
- Боб представляет своё сообщение в виде двоичной последовательности <math>m</math> длины <math>n</math>, имеющей вес, не превосходящий <math>t</math>.
- Боб вычисляет шифротекст по формуле: <math>c = mH_{pub}^T</math>. Таким образом, шифротекстом в криптосистеме Нидеррайтера является зашумленный синдром шифруемого вектора ошибкиШаблон:Source-ref.
Расшифровывание сообщения
После получения сообщения <math>c</math>, Алиса выполняет следующие действия:
- Алиса вычисляет <math>s = c{(S^T)}^{-1} = mP^TH^TS^T(S^T)^{-1} = (mP^T)H^T = \hat mH^T</math>. Заметим, что, так как <math>P</math> — матрица перестановки, вес <math>\hat m = (mP^T)</math> совпадает с весом <math>m</math> и не превосходит <math>t</math>, и потому алгоритм декодирования для <math>C</math> может найти вектор ошибки, соответствующий синдрому <math>s</math>Шаблон:Source-ref.
- Алиса использует алгоритм быстрого декодирования для кода <math>C</math>, чтобы найти <math>\hat m</math>Шаблон:Source-ref.
- Алиса вычисляет сообщение <math>\hat mP^{-1} = mPP^{-1} = m</math>.
Оригинальная криптосистема и её модификации
В оригинальной криптосистеме Нидеррайтер предлагал использовать коды Рида-Соломона и не использовал матрицу перестановки <math>P</math>. Однако такая система оказалась нестойкой и была взломана Сидельниковым и Шестаковым в 1992 годуШаблон:Source-ref. Авторы показали, что возможно угадать структуру закрытого ключа по открытому и подобрать такие матрицы <math>{\hat H}</math> и <math>{\hat S}</math>, что <math>H_{pub} = {\hat S}{\hat H}</math>. После этого для повышения криптостойкости системы было предложено использовать матрицу перестановки <math>P</math>. Кроме того, появились различные модификации системы, например:
- использующие различные метрики, отличные от классической хэмминговой, например, ранговуюШаблон:Source-ref: примером этого является модифицированная система GPTШаблон:Source-ref
- использующие коды со специфическими свойствами. Так, модификации, основанные на кодах Гоппы, все ещё остаются криптостойкимиШаблон:Source-ref.
Преимущества и недостатки системы
Преимущества
- В отличие от McEliece, в криптосистеме Нидеррайтера не используются случайные параметры. Таким образом, результат шифрования одного и того же текста будет одинаковым. Этот факт позволяет использовать именно систему Нидеррайтера, а не McEliece, для создания электронно-цифровой подписи.
- Размер открытого ключа в криптосистеме Нидеррайтера в <math>\frac {n} {n - k}</math> раз меньше, чем в McElieceШаблон:Source-ref.
- По сравнению с RSA, скорость шифрования выше приблизительно в 50 раз, а дешифрования — в 100 разШаблон:Source-ref.
Недостатки
- Для шифрования произвольного сообщения необходим алгоритм перевода в <math>q</math>-арный вектор длиной <math>n</math> веса не более <math>t</math>.
- Размер ключей больше, чем в классических криптосистемах с открытым ключом (RSA, Схема Эль-Гамаля, ГОСТ Р 34.10-2012).
- Размер шифротекста намного больше, чем размер шифруемого сообщения (если сообщение размера <math>t</math> переводится в вектор длиной <math>n</math> и шифруется, то получается шифротекст размером <math>n-k</math>, что не менее, чем в 2 раза превосходит <math>t</math>).
Ниже в таблице приведены различные параметры для криптосистем McEliece, Нидеррайтера и RSA, наглядно показывающие их преимущества и недостаткиШаблон:Source-ref.
McEliece
|
Криптосистема Нидеррайтера
|
RSA
| |
|---|---|---|---|
Размер открытого ключа
|
67072 | 32750 | 256 |
Количество бит
|
512 | 276 | 1024 |
Число бинарных операций
|
514 | 50 | 2402 |
Число бинарных операций
|
5140 | 7863 | 738112 |
Эквивалентность криптостойкости системы Нидеррайтера и системы McEliece
Как показано в оригинальной статье о системе СидельниковаШаблон:Source-ref, атака на систему Нидеррайтера может быть полиномиально сведена к атаке на систему McEliece и обратно.
Пусть известен синдром <math>c = eD</math>. Тогда можно вычислить вектор <math>b = aE + e</math> с некоторым <math>a</math> таким, что <math>c = bD</math>. Вектор <math>b</math> будет рассматриваться как шифротекст в системе McEliece. Если найдена криптографическая атака со сложностью <math>T</math> для системы McEliece, то есть известен алгоритм вычисления вектора <math>a</math>, который является секретной информацией в этой системе, то вектор <math>e</math>, являющийся секретом для системы Нидеррайтера, можно представить в виде <math>e = aE + b</math>. Таким образом, сложность определения <math>e</math> совпадает со сложностью определения <math>a</math>.
Если же известна криптоатака со сложностью <math>T</math> для системы Нидеррайтера, то возможно, используя в качестве шифротекста вектор <math>(aE + e)D^T = eD^T</math>, вычислить векторы <math>e</math> и <math>a</math>.
Построение цифровой подписи
В 2001 году Николя Куртуа, Мэттью Финиаз и Николя Сандриер показалиШаблон:Source-ref, что криптосистема Нидеррайтера может быть использована для создания электронной подписи.
Подпись сообщения
Пусть <math>H_{pub}</math> — открытый ключ криптосистемы Нидеррайтера, использующей <math>(n,k,d)</math>-линейный код. Для подписи документа <math>D</math> необходимо:
- Выбрать хеш-функцию <math>h()</math>, дающей <math>n-k</math> символов на выходе. Таким образом, результат данной хеш-функции можно представить в виде синдрома и попытаться декодировать;
- Вычислить хеш <math>s = h(D)</math>;
- Для каждого <math>i = 0,1,2,...</math> вычислить <math>s_i = h(s|i)</math>;
- Найти наименьший номер <math>i_{min}</math> такой, что синдром <math>s_{i_{min}}</math> будет возможно декодировать. Пусть <math>z</math> — результат декодирования синдрома <math>s_{i_{min}}</math>;
- Подписью документа <math>D</math> является пара <math>(z,i_{min})</math>.
Проверка подписи
- Вычислить <math>s_1 = zH_{pub}^T</math>;
- Вычислить <math>s_2 = h(h(D)|i_{min})</math>;
- Сравнить <math>s_1</math> и <math>s_2</math>: если они совпадают — подпись верна.
Пример работы системы
Пусть для кодирования был выбран <math>(7,3)</math> код Рида-Соломона над полем Галуа <math>GF(2^3)</math>, построенным по модулю неприводимого многочлена <math>x^3+x+1</math>, с порождающим многочленом <math>g(x)=(x-1)(x-{\alpha})(x-{\alpha}^2)(x-{\alpha}^3)=(x-1)(x-2)(x-4)(x-3)=x^4+4x^3+7x^2+7x+5.</math>
Тогда, порождающая матрица кода: <math>G= \begin{pmatrix} 1 & 4 & 7 & 7 & 5 & 0 & 0 \\ 0 & 1 & 4 & 7 & 7 & 5 & 0 \\ 0 & 0 & 1 & 4 & 7 & 7 & 5 \end{pmatrix} </math>
Проверочная матрица кода: <math>H= \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 4 & 3 & 6 & 7 & 5 \\ 1 & 4 & 6 & 5 & 2 & 3 & 7 \\ 1 & 3 & 5 & 4 & 7 & 2 & 6 \end{pmatrix} </math>
Заметим, что расстояние данного кода <math>d=n-k+1=5</math>, то есть число исправляемых ошибок <math>t=(d-1)/2=2</math>.
Генерация ключей
Пусть выбрана матрица <math>S= \begin{pmatrix} 4 & 1 & 3 & 5 \\ 7 & 1 & 5 & 2 \\ 2 & 6 & 5 & 4 \\ 1 & 7 & 2 & 1 \end{pmatrix} </math> . Тогда обратная к ней матрица <math>S^{-1}= \begin{pmatrix} 1 & 5 & 2 & 7 \\ 7 & 5 & 0 & 7 \\ 4 & 4 & 1 & 5 \\ 1 & 0 & 0 & 4 \end{pmatrix} </math>
Пусть выбрана матрица перестановки <math>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} </math>
В этом случае открытым ключом системы будет матрица: <math>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} </math>
Шифрование
Пусть выбранное сообщение было представлено в виде вектора <math>m= \begin{pmatrix} 0 & 2 & 0 & 0 & 0 & 5 & 0 \end{pmatrix} </math> веса 2.
Зашифрованное сообщение: <math>M=mH_{pub}^T= \begin{pmatrix} 7 & 2 & 7 & 7 \end{pmatrix} </math>
Расшифровывание
Принятый вектор <math>M= \begin{pmatrix} 7 & 2 & 7 & 7 \end{pmatrix} </math>
Для него вычислим декодируемый синдром <math>s=M(S^{-1})^T= \begin{pmatrix} 0 & 1 & 3 & 6 \end{pmatrix} </math>
Используя алгоритм декодирования кода Рида-Соломона, декодируем <math>s</math>.
Получится вектор <math>\hat m= \begin{pmatrix} 2 & 0 & 0 & 0 & 0 & 0 & 5 \end{pmatrix} </math>
После чего вычислим исходный вектор <math>m=~\hat mP^{-1}= \begin{pmatrix} 0 & 2 & 0 & 0 & 0 & 5 & 0 \end{pmatrix} </math>
См. также
Примечания
Литература
