Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Алгоритм шифрования DES

Автор: DiMoN_TD 4.1.2012, 12:35

Добрый день.
Решил помучать себя и разобраться в способах и алгоритамх шифрования.
Для начала взял алгоритм шифрования http://ru.wikipedia.org/wiki/DES
Погуглил, почитал на вики.
После прочтения начали возникать вопросы. Первый вопрос, на который я бы хотел получить ответ:
Что означает "перестановка" и каким образом она вычисляется?
В вики в данной статье указана лишь результирующая таблица после перестановки (начальная перестановка, конечная перестановка, перестановка, применяемая к 32-битовому блоку и т.д.), и в других статьях посвященные этому алгоритму, в принципе, все тоже самое - лишь конечная таблица.

Автор: spin2 4.1.2012, 14:25

DiMoN_TD, перестановка в s-блоках?

Автор: DiMoN_TD 4.1.2012, 15:18

spin2,
до S-блоков я еще не дошел.
В описании алгоритма есть вот такая строчка:

Цитата

Начальная перестановка

Исходный текст T (блок 64 бит) преобразуется c помощью начальной перестановки IP которая определяется таблицей 1:

В этой таблице описан результат начальной перестановки:

Цитата

58  50  42  34  26  18  10  2  60  52  44  36  28  20  12  4
62  54  46  38  30  22  14  6  64  56  48  40  32  24  16  8
57  49  41  33  25  17  9  1  59  51  43  35  27  19  11  3
61  53  45  37  29  21  13  5  63  55  47  39  31  23  15  7

Далее описывается:

Цитата

По таблице первые 3 бита результирующего блока IP(T) после начальной перестановки IP являются битами 58, 50, 42 входного блока Т, а его 3 последние бита являются битами 23, 15, 7 входного блока.

А как они это получили - для меня загадка. Или же это стандартная таблица? Или есть какая-то функция, которая определяет перестановку, как в начальной перестановке так и в S-блоках?

Автор: DiMoN_TD 4.1.2012, 18:21

Так, закономерность образования Таблицы начальной перестановки я понял, единственное что не понял, почему именно так.

Автор: redwhite90 8.1.2012, 13:38

это всегда так. входной параметр алгоритма

Автор: DiMoN_TD 9.1.2012, 10:14

Кто может объяснить, как формируется ключ?
Первым этапом, как я понял, необходимо преобразовать ключ в 64битный массив.
Из него каждый 8й бит надо исключить, и получим 56битный массив. Из него сделать перестановку по таблице, и разбить на два блока Co и Do по 28 бит.
А вот дальше я не понял, что за циклические сдвиги происходят и почему в конечном итоге получается 48 битный ключ?

Автор: DiMoN_TD 9.1.2012, 18:43

Нашел источник, где на "пальцах" показывается, как формируется ключ.
http://orlingrabbe.com/des.htm

Выкладываю, если кто-то вдруг по поиску наткнется на эту же тему.

Автор: DiMoN_TD 12.1.2012, 16:57

В конечном итоге разобрался как это все работает.
Источники, которыми пользовался это:

1. http://orlingrabbe.com/des.htm
2. http://ru.wikipedia.org/wiki/DES#.D0.93.D0.B5.D0.BD.D0.B5.D1.80.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.B8.D0.B5_.D0.BA.D0.BB.D1.8E.D1.87.D0.B5.D0.B9_ki

Сверялся с http://www.tools4noobs.com/online_tools/encrypt/

Чуть позже выложу исходники на PHP, надо привести в читабельный вид.

Автор: DiMoN_TD 14.1.2012, 23:24

Возник еще один вопрос. Теперь по поводу дешифровки. Не получается расшифровать данные.
Везде пишут, что алгоритм дешифровки - это обратный метод шифровки, где:
1. Шифрованный текст преобразуется в 64-битовый блок.
2. Применяется перестановка согласно Конечной перестановки из алгоритма шифрования (IP(-1))
3. Далее идет цикл из 16 шагов, где происходит "дешифровка":

Код


R(i-1) = L(i)
L(i-1) = R(i) xor f(L(i), K(i))

4. Полученные результаты L(0) и R(0) конкатинируются в 64-битный конечный блок.
5. Конечный 64-битный блок подвергается начальной перестановке из алгоритма шифрования (IP(1))

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

Заранее спасибо.

Автор: spin2 15.1.2012, 15:07

DiMoN_TD, Там просто в обратную сторону идешь и все. Раз у тебя уже прога есть, отсекай по одному элементу и смотри, совпадают ли результаты.

Автор: DiMoN_TD 15.1.2012, 15:14

Выкладываю класс, написанный на PHP:

http://pastebin.com/vNM9UVaR

Пример использования:

Код


$DEC_alg = new DEC_algorithm("plainText","theKey",true);
echo $encryptText = $DEC_alg->encrypt();
echo "<br>";
echo $decryptText = $DEC_alg->decrypt($encryptText);

Как я и говорил выше - проблема с дешифровкой. Использую обратный метод шифрования, но в итоге не получается исходного текста.
Глаз уже замылен, возможно кто-то из просматривающих эту тему посмотрит более свежим взглядом, и подскажет где я мог ошибиться.
Более конкретно в методе decrypt();

Автор: DiMoN_TD 15.1.2012, 16:13

Цитата(spin2 @ 15.1.2012, 13:07

)

DiMoN_TD, Там просто в обратную сторону идешь и все. Раз у тебя уже прога есть, отсекай по одному элементу и смотри, совпадают ли результаты.

Ну смотри. Алгоритм шифрования:

1. P = Plaintext 64bit block.
2. IP1 (P)
4. L(0) R(0).
3. 1...16 итераций, шифровка. На выходе L(16) R(16). Конкатинируем R(16) и L(16) = RL.
4. IP2 (RL)
5 C = Chipertext 64bit block

Теперь алгоритм расшифровки должен быть следующим методом:
1. C = Chipertext 64bit block
2. IP2 ( С )
3. 16...1 итераций, дешифровка. На выходе L(0) R(0). Конкатинируем L(0) и R(0) = LR.
4. IP1 (LR)
5. P = Plaintext 64bit block.

Но на практике совершенно не получается.

И еще, если отсекать по одному элементу, как ты утверждаешь, не мог бы ты указать, что с чем должно "совпадать" при шифровке и дешифровке?

Автор: DiMoN_TD 15.1.2012, 16:29

spin2, все, разобрался. Я, видимо, неправильно понял описанный метод дешифровки в этой статье:
http://protect.htmlweb.ru/des.htm
описано:

Цитата

Все действия должны быть выполнены в обратном порядке. Это означает, что расшифровываемые данные сначала переставляются в соответствии с матрицей IP-1

Ну я и начал применять таблицу конечной перестановки в начале дешифровки. А оказывается, что надо было применить таблицу начальной перестановки.
Спасибо за указание на пошаговое сравнение шифровки\дешифровки. Так бы еще долго ломал голову, в каком месте и ошибся.

Допилю код - выложу на конечное обозрение.

Автор: DiMoN_TD 18.1.2012, 13:12

Как и обещал.
Выкладываю класс на php для криптования и декриптования текста алгоритмом DES методом ECB (в инете так и не нашел ни одного исходника):

http://pastebin.com/ARYsde8g

Пример использования:

Код


$DEC_alg = new DEC_algorithm();
$DEC_alg->setParameters("plainText","theKey",true);
$encryptText = $DEC_alg->encrypt();
$decryptText = $DEC_alg->decrypt($encryptText);

echo "<b>Plaintext:</b> ".$DEC_alg->plainText." (len = ".strlen($DEC_alg->plainText).")<br>";
echo "<b>The key:</b> ".$DEC_alg->theKey."<br>";
echo "<b>Encrypted:</b> ".$encryptText."<br>";
echo "<b>Decrypted:</b> ".$decryptText."<br>";

Спасибо за помощь. Задача решена smile

Автор: DiMoN_TD 30.1.2012, 10:17

Данный скрипт реализовал и опубликовал Тупалов Дмитрий.

[Доказательство того, что этот аккаунт принадлежит Тупалову Дмитрию.]

smile