New Data Seal

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
New Data Seal (NDS)
Создатель [IBM]
Создан 1975 год
Размер ключа 2048 бит
Размер блока 128 бит
Число раундов 16
Тип сеть Фейстеля

New Data Seal (NDS) — блочный шифр, основанный на алгоритме Люцифера, который позже стал стандартом DES. Шифр был разработан в компании IBM в 1975 году. Для шифрования NDS использует делит входные (незашифрованные) данные на блоки по 128 бит и использует очень длинный ключ размером 2048 бит. Структура шифра точно такая же, как и у DES: cеть Фейстеля с 16 раундами.

Принцип работы[править | править код]

Шифр NDS является достаточно простым в частности из-за того, что в каждом раунде сети Фейстеля в его основе используется один и тот же ключ.

  • Ключ представляет собой отображение: то есть размерность пространства таких ключей что более чем достаточно для предотвращения перебора ключей.
  • Система использует 2 заранее известных (не динамичных) S-блока: ключевое расписание состоит из одного ключа Блок открытого текста делится на 2 подблока размером 64 бита каждый. Для того, чтобы посчитать
    1. разбивается на восемь 8-битных частей. За обозначим байт, образованный первым битом каждого байта в
    2. каждая часть разбивается на два 4-битных ниббла
    3. к левому нибблу применяется к правому —
    4. в случае, если -ый бит равен 1, поменяются местами нибблы -ой части после преобразования
    5. к 64-битному результату (после объединения всех частей) применяется заранее известная перестановка. Она позволяет защитить шифр от взлома и анализа как системы более простых независимых подшифров.

Алгоритм взлома[править | править код]

Использование одного и того же ключа в каждом раунде является слабым местом данного шифра и используется в атаке на основе подобранного открытого текста. С ее помощью можно полностью восстановить ключ шифрования: обозначим за преобразование, соответствующее одному раунду NDS, то есть Далее, будет обозначать все 16 раундов. Заметим, что и коммутируют: В соответствии с принципом Керкгоффса мы знаем все об алгоритме шифрования, кроме ключа Тогда если мы будем знать для каждого возможного ключ будет считаться взломанным.

Процедура атаки следующая:

  1. Подобрать сообщение так, чтобы
  2. Взломщик получает зашифрованное сообщение соответствующее открытому тексту
  3. Пусть — один из возможных 8-битных ключей (всего комбинаций). И пусть есть результат после работы от 1 раунда с ключом .
  4. Если то и Следовательно левая половина согласована с правой половиной
  5. Взломщик получает зашифрованное сообщение соответствующее заранее выбранному тексту Если правая половина соответствует левой половине то можно считать допустимым значением для В худшем случае нужно будет перебрать комбинаций для нахождения нужного значения.
  6. Повторяем процедуру для каждого получая значение ключа с помощью заранее выбранных открытых текстов.

Атаки на шифр[править | править код]

В 1977 Эдна Гроссман и Брайант Такермен впервые продемонстрировали атаку на NDS с помощью сдвиговой атаки.[1][2] Этот метод использует не более 4096 подобранных открытых текстов. В их лучшем испытании они смогли восстановить ключ только с 556 подобранными открытыми текстами.

Примечания[править | править код]

  1. E. K. Grossman, Thomas J. Watson IBM Research Center Research Division, B. Tuckerman. Analysis of a Feistel-like Cipher Weakened by Having No Rotating Key. — IBM Thomas J. Watson Research Division, 1977. — 33 с.
  2. Henry Beker, Fred Piper. Cipher Systems: The Protection of Communications. — John Wiley & Sons, 1982. — С. 263–267. — ISBN 0-471-89192-4.