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