Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Лекция. 12 База данных




Н

К

R

1,2.

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

 

 

         
  1,2,...      
          к,
I    

R. =L0©f(R0,K,)


Исходный текст


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


L, =R,


R2=L,ef(R,,K2)


 


16 раз


Шифрование


Ключ


©«-


г «


к,


 


Конечная перестановка


- R



R15=L,4©f(R14,K15)


 


           
   
 
   


Шифртекст

Рис.3.1. Обобщенная схема шифрования в алгоритме DES


Rw=L15ef(R1J,Kw)






 


       
 
 
   

-1

Следует сразу отметить, что все приводимые таблицы яв­ляются стандартными и должны включаться в реализацию алго­ритма DES в неизменном виде.

Все перестановки и коды в таблицах подобраны разработ­чиками таким образом, чтобы максимально затруднить процесс расшифровки путем подбора ключа. При описании алгоритма DES (рис. 3.2) применены следующие обозначения:

L и R - последовательности битов (левая (left) и пра­вая (right));


1,2...


Конечная перестановка IP

Выходная последовательность битов (шифртекст)

Рис.3.2. Структура алгоритма DES




           
   
     
 
 
 


LR - конкатенация последовательностей L и R, т.е. такая последовательность битов, длина которой равна сумме длин L и R; в последовательности LR биты последовательности R следуют за битами последовательности L;

© - операция побитового сложения по модулю 2.

Пусть из файла исходного текста считан очередной 64-битовый (8-байтовый) блок Т. Этот блок Т преобразуется с помо­щью матрицы начальной перестановки IP (табл. 3.1).

Таблица 3.1 Матрица начальной перестановки IP

 

               
               
               
               
               
               
               
               

Биты входного блока Т (64 бита) переставляются в соот­ветствии с матрицей IP: бит 58 входного блока Т становится битом 1, бит 50 - битом 2 и т.д. Эту перестановку можно описать выра­жением То = IP(T). Полученная последовательность битов То разделяется на две последовательности: Lo - левые или старшие биты, Ro - правые или младшие биты, каждая из которых содер­жит 32 бита.

Затем выполняется итеративный процесс шифрования, состоящий из 16 шагов (циклов). Пусть Tj - результат i-й итерации:

Т: = Li R,,

где Li = U t2... t32 (первые 32 бита); Rs = t33134... t64 (последние 32 бита). Тогда результат i-й итерации описывается следующими формулами:

Lj = Ri_1, i = 1, 2 16;

Ri = Li_1©f(RM,Ki), i= 1,2 16.

Функция f называется функцией шифрования. Ее аргумен­тами являются последовательность Rm, получаемая на предыду­щем шаге итерации, и 48-битовый ключ Kj, который является ре­зультатом преобразования 64-битового ключа шифра К. (Подроб­нее функция шифрования f и алгоритм получения ключа К, описаны ниже.)

На последнем шаге итерации получают последовательно­сти R^ и L16 (без перестановки местами), которые конкатенируются в 64-битовую последовательность R16 L16.


По окончании шифрования осуществляется восстановле­ние позиций битов с помощью матрицы обратной перестановки IP"1 (табл.3.2).

Таблица 3.2 Матрица обратной перестановки IP"1

 

               
               
               
               
               
               
               
               

Пример того, как соотносятся элементы первой строки матрицы 1Р~1 с элементами матрицы IP приведен в табл. 3.3.

Таблица 3.3

 

Связь элементов матриц
Элемент матрицы IP"'   Элемент матрицы IP
     
     
     
     
     

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

Итеративный процесс расшифрования может быть описан следующими формулами:

Ri-i = Li, 1=1,2 16;

L+.1 = R,-Ф f (Ц K|), i = 1,2,..., 16.

Таким образом, для процесса расшифрования с перестав­ленным входным блоком R16L16 на первой итерации используется ключ «16, на второй итерации - К15 и т.д. На 16-й итерации ип-пользуется ключ Ki. На последнем шаге итерации будут получены последовательности Lo и ROl которые конкатенируются в 64-битовую последовательность LoRo. Затем в этой последователь­ности 64 бита переставляются в соответствии с матрицей IP. Ре-


 
 


LR - конкатенация последовательностей L и R, т.е. такая последовательность битов, длина которой равна сумме длин L и R; в последовательности LR биты последовательности R следуют за битами последовательности L;

©-операция побитового сложения по модулю 2.

Пусть из файла исходного текста считан очередной 64-битовый (8-байтовый) блок Т. Этот блок Т преобразуется с помо­щью матрицы начальной перестановки IP (табл. 3.1).

Таблица 3.1 Матрица начальной перестановки IP

 

               
               
               
               
               
               
               
               

Биты входного блока Т (64 бита) переставляются в соот­ветствии с матрицей!Р: бит 58 входного блока Т становится битом 1, бит 50 - битом 2 и т.д. Эту перестановку можно описать выра­жением То = IP(T). Полученная последовательность битов То разделяется на две последовательности: Lo - левые или старшие биты, Ro-правые или младшие биты, каждая из которых содер­жит 32 бита.

Затем выполняется итеративный процесс шифрования, состоящий из 16 шагов (циклов). Пусть Т,- результат i-й итерации:

Т, = Ц Ri(

где Lj = ti t2... t32 (первые 32 бита); R, = t33134... t64 (последние 32 бита). Тогда результат i-й итерации описывается следующими формулами:

Li = RM, i = 1.2 16;

Ri = LM©f(RM, Ki), i= 1,2 16.

Функция f называется функцией шифрования. Ее аргумен­тами являются последовательность Rw, получаемая на предыду­щем шаге итерации, и 48-битовый ключ Kj, который является ре­зультатом преобразования 64-битового ключа шифра К. (Подроб­нее функция шифрования f и алгоритм получения ключа К, описаны ниже.)

На последнем шаге итерации получают последовательно­сти Ri6 и 1_1б (без перестановки местами), которые конкатенируются в 64-битовую последовательность R16 Це.


 

-.-1

По окончании шифрования осуществляется восстановле­ние позиций битов с помощью матрицы обратной перестановки

IP"1 (табл. 3.2).

Таблица 3.2 Матрица обратной перестановки IP"1

 

               
               
               
               
               
               
               
               

Пример того, как соотносятся элементы первой строки матрицы IP"1 с элементами матрицы IP приведен в табл. 3.3.

Таблица 3.3

 

Связь элементов матриц
Элемент матрицы IP"'   Элемент матрицы IP
     
     
     
     
     

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

Итеративный процесс расшифрования может быть описан следующими формулами:

Ri-i = Li, 1 = 1,2 16;

LM = Ri©f(UK,). i = 1,2 16.

Таким образом, для процесса расшифрования с перестав­ленным входным блоком R16Li6 на первой итерации используется ключ «16, на второй итерации - К^ и т.д. На 16-й итерации ис­пользуется ключ Ki. На последнем шаге итерации будут получены последовательности Lo и Ro, которые конкатенируются в 64-битовую последовательность LoRo. Затем в этой последователь­ности 64 бита переставляются в соответствии с матрицей IP. Ре-


зультат такого преобразования - исходная последовательность битов (расшифрованное 64-битовое значение).

Теперь рассмотрим, что скрывается под преобразованием, обозначенным буквой f. Схема вычисления функции шифрования f (Ri_i,Kj) показана на рис. 3.3.

Ri_-i (32 бита)

 

 

 

 

 

    Расширитель Е    
48 бит -"^ г К, (48 бит)
Г
             
Si £ >2 S з £ 4 £ 5 £ к £ >7 £>8
             
      Г  
  Перестановка битов Р
               

I 32 бита

f(RM,Ki)

Рис.3.3. Схема вычисления функции шифрования f

Для вычисления значения функции f используются:

• функция Е (расширение 32 бит до 48);

• функция Sl S2,..., S8 (преобразование 6-битового числа в 4-
битовое);

• функция Р (перестановка битов в 32-битовой последователь­
ности).

Приведем определения этих функций.

Аргументами функции шифрования f являются RM (32 би­та) и К; (48 бит). Результат функции Е (Rm) есть 48-битовое чис­ло. Функция расширения Е, выполняющая расширение 32 бит до 48 (принимает блок из 32 бит и порождает блок из 48 бит), опре­деляется табл. 3.4.

В соответствии с табл. 3.4 первые три бита Е (Rj_i) - это биты 32, 1 и 2, а последние - 31, 32, 1. Полученный результат (обозначим его E(R,_1)) складывается по модулю 2 (операция XOR)


Таблица 3.4 Функция расширения Е

 

           
           
           
           
           
           
           
           

с текущим значением ключа К, и затем разбивается на восемь 6-битовых блоков Bi, В2,..., Be:

Е (Ri-i) Ф Kj = Bi В2... В8.

Далее каждый из этих блоков используется как номер эле­мента в функциях-матрицах S'l S2,..., S8, содержащих 4-битовые значения (табл. 3.5).

Следует отметить, что выбор элемента в матрице Sj осу­ществляется достаточно оригинальным образом. Пусть на вход матрицы Sj поступает 6-битовый блок Bj = b-i b2 b3 b4 Ьб b6, тогда двухбитовое число bi b6 указывает номер строки матрицы, а че­тырехбитовое число Ь2 Ь3 b4 b5 - номер столбца. Например, если на вход матрицы S! поступает 6-битовый блок Bi= bi b2 b3 b4 b5 b6 = = 100110, то 2-битовое число Ь, b6 = 10(2) = 2(10j указывает строку с номером 2 матрицы S^ а 4-битовое число b2 b3 b4 Ь5=0011(2)=3(10) указывает столбец с номером 3 матрицы S^ Это означает, что в матрице St блок Вт = 100110 выбирает элемент на пересечении строки с номером 2 и столбца с номером 3, т.е. элемент 8(10) = =1000(2). Совокупность 6-битовых блоков Bl B2,..., В8 обеспечивает выбор четырехбитового элемента в каждой из матриц Si, S2,..., S8.

В результате получаем S^BO S2(B2) S3(B3)... S8(B8), т.е. 32-битовый блок (поскольку матрицы Sj содержат 4-битовые элемен­ты). Этот 32-битовый блок преобразуется с помощью функции пе­рестановки битов Р (табл.3.6).

Таким образом, функция шифрования

f(Ri_1,Ki) = P(S1(B1)....... Se(B8)).

Как нетрудно заметить, на каждой итерации используется новое значение ключа К, (длиной 48 бит). Новое значение ключа Kj вычисляется из начального ключа К (рис.3.4). Ключ К представ­ляет собой 64-битовый блок с 8 битами контроля по четности, рас­положенными в позициях 8, 16, 24, 32, 40, 48, 56, 64. Для удаления контрольных битов и подготовки ключа к работе используется функция G первоначальной подготовки ключа (табл. 3.7).



зультат такого преобразования - исходная последовательность битов (расшифрованное 64-битовое значение).

Теперь рассмотрим, что скрывается под преобразованием, обозначенным буквой f. Схема вычисления функции шифрования f (Ri_i,Kj) показана на рис. 3.3.

RM (32 бита)

 

 

 

 

 

 

      Расширитель Е    
  48 бит -— \ Л r Kj (48 бит)
r
               
  Si S 2 S з £ A S 5 £ >6 £ >7 S8
               
    r  
Перестановка битов Р
                 
I

32 бита

Рис.3.3. Схема вычисления функции шифрования f

Для вычисления значения функции f используются:

• функция Е (расширение 32 бит до 48);

• функция Si, S2,..., S8 (преобразование 6-битового числа в 4-
битовое);

• функция Р (перестановка битов в 32-битовой последователь­
ности).

Приведем определения этих функций.

Аргументами функции шифрования f являются Rm (32 би­та) и К| (48 бит). Результат функции Е (RM) есть 48-битовое чис­ло. Функция расширения Е, выполняющая расширение 32 бит до 48 (принимает блок из 32 бит и порождает блок из 48 бит), опре­деляется табл. 3.4.

В соответствии с табл. 3.4 первые три бита Е (Rj_i) - это биты 32, 1 и 2, а последние - 31, 32, 1. Полученный результат (обозначим его E(R,_i)) складывается по модулю 2 (операция XOR)


Таблица 3.4 Функция расширения Е

 

           
           
           
           
           
           
           
           

с текущим значением ключа Kj и затем разбивается на восемь 6-
битовых блоков Bi, B2.......... В8:

Е (Rj_i) © Kj = Bi В2... Be.

Далее каждый из этих блоков используется как номер эле­мента в функциях-матрицах S'l S2,..., S8, содержащих 4-битовые значения (табл. 3.5).

Следует отметить, что выбор элемента в матрице Sj осу­ществляется достаточно оригинальным образом. Пусть на вход матрицы Sj поступает 6-битовый блок Bf = bi b2 b3 b4 b5 b6, тогда двухбитовое число bi b6 указывает номер строки матрицы, а че­тырехбитовое число Ь2 Ь3 b4 b5 - номер столбца. Например, если на вход матрицы Si поступает 6-битовый блок Bi= bi b2 b3 b4 b5 b6 = = 100110, то 2-битовое число b1 b6 = 10(2) = 2(10) указывает строку с номером 2 матрицы S1t а 4-битовое число b2 b3 b4 Ь5=0011(2)=3(10) указывает столбец с номером 3 матрицы S-|. Это означает, что в матрице Si блок В, = 100110 выбирает элемент на пересечении строки с номером 2 и столбца с номером 3, т.е. элемент 8(10) = =1000(2). Совокупность 6-битовых блоков Bi, B2,..., В8 обеспечивает выбор четырехбитового элемента в каждой из матриц Si, S2,..., S6.

В результате получаем S^B-,) S2(B2) S3(B3)... S8(B8), т.е. 32-битовый блок (поскольку матрицы Sj содержат 4-битовые элемен­ты). Этот 32-битовый блок преобразуется с помощью функции пе­рестановки битов Р (табл.3.6).

Таким образом, функция шифрования

f(Ri_1,Ki) = P(S1(B1)....... S8(B8)).

Как нетрудно заметить, на каждой итерации используется новое значение ключа Kj (длиной 48 бит). Новое значение ключа К, вычисляется из начального ключа К (рис.3.4). Ключ К представ­ляет собой 64-битовый блок с 8 битами контроля по четности, рас­положенными в позициях 8, 16, 24, 32, 40, 48, 56, 64. Для удаления контрольных битов и подготовки ключа к работе используется функция G первоначальной подготовки ключа (табл. 3.7).


I -i.


 
 

Таблица 3.6 Функция Р перестановки битов

Таблица 3.5

 

 

          Функци» i преобразования S,, S2... .s,          
              Номер столбца            
                                 
                                     
                                    Si
                                     
                                     
                                     
                                    S?
                                     
                                     
                                     
                                    s3
                                     
н                                    
                                     
м               .0 ' 3                 s4
е                                    
Р                                    
                                     
                                    s5
с                   1?                
т                                    
                                     
                                    sB
к                                    
и                       .1            
                                     
                                    s7
                ^7                    
                                     
                                     
                                    s8
                                     
                                     

Ключ К

Функция G

Co (28 бит)

Do (28 бит)

Сдвиг влево

Сдвиг влево

Функция Н

Сдвиг влево

Сдвиг влево

D2

Функция

Сдвиг влево

Сдвиг влево

■Мб

N16

Функция н

Рис.3.4. Схема алгоритма вычисления ключей К,

Табл. 3.7 разделена на две части. Результат преобразова­ния G(K) разбивается на две половины Со и Do по 28 бит каждая. Первые четыре строки матрицы G определяют, как выбирают-

Таблица 3.7

20 28 23 31 24 3 30
 
12 15 18 8 27 13 11
32 19 22

Функция G первоначальной подготовки ключа (переставленная выборка 1)

 

             
             
             
            36..........
~63~       ~3~1 ~    
      46.      
          37 -  
             

ся биты последовательности Со (первым битом Со будет бит 57 ключа шифра, затем бит 49 и т.д., а последними битами - биты 44 и 36 ключа).

Следующие четыре строки матрицы G определяют, как выбираются биты последовательности Do (т.е. последователь­ность Do будет состоять из битов 63, 55, 47,...,12, 4 ключа шифра).

Как видно из табл. 3.7, для генерации последовательно­стей Со и Do не используются биты 8, 16, 24, 32, 40, 48, 56 и 64 ключа шифра. Эти биты не влияют на шифрование и могут слу­жить для других целей (например, для контроля по четности). Та­ким образом, в действительности ключ шифра является 56-битовым.

После определения Со и Do рекурсивно определяются Q и Dit i = 1, 2,..., 16. Для этого применяются операции циклического сдвига влево на один или два бита в зависимости от номера шага итерации, как показано в табл. 3.8.

Операции сдвига выполняются для последовательностей BMCHMO. Например, последовательность С3 получается посредством циклического сдвига влево на две позиции последо­вательности С2, а последовательность D3 - посредством сдвига влево на две позиции последовательности D2, C16 и D16 получают­ся из С15 и D15 посредством сдвига влево на одну позицию.

Таблица 3.8

Таблица сдвигов s, для вычисления ключа

 

Номер итерации Количество s, сдвигов влево, бит Номер итерации Количество & сдвигов влево, бит
       
       
       
       
       
       
       
       

Ключ К|, определяемый на каждом шаге итерации, есть результат выбора конкретных битов из 56-битовой последователь­ности С, D| и их перестановки. Другими словами, ключ Kj=H(Cj Dj), где функция Н определяется матрицей, завершающей обработку.ключа (табл. 3.9).


Таблица 3.9

Функция Н завершающей обработки ключа (переставленная выборка 2)

 

           
           
           
           
           
           
           
           

ключа Ki будет 14-й

Как следует из табл.3.9, первым битом ivi.гили ,^^yM4, •-,-„ бит последовательности С, Dj, вторым - 17-й бит, 47-м битом клю­ча К, будет 29-й бит Cj Dj, а 48-м битом - 32-й бит Cj Dj.

3.2.0сновные режимы работы алгоритма DES

Алгоритм DES вполне подходит как для шифрования, так и для аутентификации данных. Он позволяет непосредственно пре­образовывать 64-битовый входной открытый текст в 64-битовый выходной шифрованный текст, однако данные редко ограничива­ются 64 разрядами.

Чтобы воспользоваться алгоритмом DES для решения разнообразных криптографических задач, разработаны четыре рабочих режима:

• электронная кодовая книга ЕСВ (Electronic Code Book);

• сцепление блоков шифра СВС (Cipher Block Chaining);

• обратная связь по шифртексту CFB (Cipher Feed Back);

• обратная связь по выходу OFB (Output Feed Back).

Режим "Электронная кодовая книга"

Длинный файл разбивают на 64-битовые отрезки (блоки) по 8 байтов. Каждый из этих блоков шифруют независимо с ис­пользованием одного и того же ключа шифрования (рис.3.5).

Основное достоинство - простота реализации. Недостаток - относительно слабая устойчивость против квалифицированных криптоаналитиков. Из-за фиксированного характера шифрования при ограниченной длине блока 64 бита возможно проведение криптоанализа "со словарем". Блок такого размера может повто­риться в сообщении вследствие большой избыточности в тексте

 




Поделиться с друзьями:


Дата добавления: 2014-12-16; Просмотров: 367; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.013 сек.