Шифры взбивания и стандарт DES
Казалось бы, что предел возможностей сокрытия сообщения уже достигнут, ан нет. Результат можно ощутимо улучшить, если вместо перестановки использовать линейное преобразование:
s=L*t
где L - невырожденная матрица случайного линейного преобразования бит, или, что то же самое, детерминант L не равен нулю. И хотя расшифровывание в этом случае придется осуществлять решением систем линейных уравнений, но каждый бит шифровки начинает уже зависеть от каждого бита текста. Шифры на основе этого преобразования называют скрамблерами или взбивалками за то, что они взбивают текст сообщения, как повара омлет. К сожалению, доля невырожденных матриц с увеличением их размера стремительно убывает. Детерминант матрицы L, как и ее элементы, может быть равен либо 0, либо 1. Если det(L)=0, то матрица вырождена. Поскольку известно, что для матрицы, составленной из квадратных подматриц А, В, С и D, имеем:
¦А В¦
¦ ¦ =det(A)det(B)-det(C)-det(D)
¦C D¦
и, обозначив через Pn вероятность равенства единице детерминанта случайной матрицы размером 2**n, получаем следующее рекуррентное выражение:
P(n+1)=2*Pn*Рn*(1-Pn*Pn).
Так как P1=0.5, то увеличение n влечет быстрое убывание невырожденных матриц среди случайных.
Для того, чтобы матрица L была невырожденной, случайной и при расшифровании не нужно было производить много вычислений, американскими криптографами был предложен алгоритм, легший в основу стандартного криптографического преобразования DES. Суть его одного шага можно описать следующей схемой.
Входной блок данных делится пополам на левую L' и правую R' части. После этого формируется выходной массив так, что его левая часть L" представлена правой частью R' входного, а правая R" формируется как сумма L' и R' операцией XOR. Далее, выходной массив шифруется перестановкой с заменой. Можно убедиться, что все проведенные операции могут быть обращены и расшифровывание осуществляется за число операций, линейно зависящее от размера блока. В то же самое время, после нескольких таких взбиваний можно считать, что каждый бит выходного блока шифровки может зависеть от каждого бита сообщения.
Система шифрования DES была разработана IBM под именем Lucifer и предложена со своими корректировками Национальным Бюро Стандартов США в 1976 году как стандарт шифрования. В ней применен ключ из 56 бит. Следует отметить, что в стандарте DES применены перестановки лишь специального типа, что наводило критиков этого стандарта на мысль, что АНБ хорошо знало их теорию и могло для взлома воспользоваться заранее известными слабыми местами. Однако принцип этого шифрования прошел самую широкую апробацию и ему посвящено множество публикаций. Нарекания вызывали лишь выбранные короткими длины блока в 64 бита и ключа в 56 бит, что недостаточно для таких задач, как национальная безопасность. Свое развитие DES получил в ГОСТ 28147-89, который увеличил длину ключа до 256 бит и допустил произвольные перестановки. В заключение приведем программу, демонстрирующую эффект взбивания на блоке в 64 байта. С увеличением числа взбиваний порча единственного бита в шифровке делает нечитаемой половину текста, что обусловлено побайтовой перестановкой. Если бы перестановка была побитовая, то весь текст от ошибки в единственном бите перестал бы читаться.
'------программа шифрования взбиванием
DEFINT I-N: DEFSTR S
RANDOMIZE 231
CLS:LOCATE 1, 1
Lot = 5
s$ = ""
FOR i=1 TO 64:s$=s$+CHR$(65+25*RND):NEXT
PRINT s$; " - text": sav = s$
s$ = ""
FOR i=1 TO 192: s$=s$+CHR$(255*RND): NEXT
'---------------------шифрование
FOR i = 0 TO Lot
sc=MID$(ss,1+I*32,32)
l=2^i:sl="": r=""
FOR j = 1 TO 32
kg=ASC(MID$(sc, j, 1))
kl=ASC(MID$(s$, j, 1))
kr=ASC(MID$(s$, j+32,1))
sl = sl+ CHR$(kl XOR kr)
sr = sr+ CHR$(kr XOR kg)
NEXT
s$=sr+RIGHT$(sl,l)+LEFT$(sl,32-l)
NEXT
'----------------------порча бита
ss=CHR$(ASC(s$) XOR 4)+RIGHT$(s$,63)
'-----------------печать шифровки
FOR i =1 TO 64
k = ASC(MID$(s$, i, 1))
DEF SEG=47114: POKE 2*i-2, k: DEF SEG
NEXT
LOCATE 2, 65: PRINT " - code"
'---------------расшифровывание
FOR i = Lot TO 0 STEP -1
sc=MID$(s$, 1+i*32, 32): l=2^i
s$=RIGHT$ (s$ ,32-
l)+MID$ (s$, 33,l)+LEFT$ (s$, 32)
sl = "": sr = ""
FOR j = 1 TO 32
kg = ASC(MID$(sc, j, 1))
kl = ASC(MID$(ss, j, 1))
kr = ASC(MID$(ss, j+32, 1))
sl = sl+ CHR$(kl XOR kr XOR kg)
sr = sr+ CHR$(kr XOR kg)
NEXT
ss = sl+sr
NEXT
FOR i =1 TO 64
k = ASC(MID$(s$, i, 1))
DEF SEG=47124: POKE 2*i-2,k: DEF SEG
NEXT
LOCATE 3, 65: PRINT " - text"
n = 0
FOR i =1 TO 64
IF MID$ (s$, i, 1) =MID$(sav, i,1) THEN
LOCATE 4, i: PRINT "+";: n = n+I
ELSE
LOCATE 4, i: PRINT "-";
END IF
NEXT
LOCATE 6, 1: PRINT 64 - n; "errors"
END
Шифр DES принят федеральным стандартом США, и хорош в использовании для многих коммерческих приложений. Однако правительства сами никогда не используют шифры, предлагаемые коммерсантам, чтобы закрыть свои данные, так как они недостаточно стойки от атак аналитиков. Например, 16-кратный DES был взломан Шамиром, применявшим дифференциальный криптоанализ, и Матсуи, использовавшим линейный криптоанализ. Наиболее серьезную практическую атаку на DES осуществил Мишель Винер, который разработал и опробовал микросхему, проверяющую в секунду 50 миллионов ключей DES. ЭВМ, стоящая миллион долларов и содержащая несколько десятков тысяч таких микросхем, способна перебрать все ключи DES за 7 часов. АБН и ФАПСИ тратят на вычислительную технику такие деньги, что могут построить ЭВМ, взламывающую шифровку DES за секунду. Это означает, что DES нельзя пользоваться для серьезных приложений. Для того, чтобы испортить правительственным криптоаналитикам сон, коммерсанты применяют так называемый "тройной DES", шифруя сообщение трижды двумя разными ключами, что увеличивает реальную длину ключа до 112 бит. Однако такой метод медленнее обычного DES метода в три раза.
