www.chms.ru - вывоз мусора в Балашихе 

Динамо-машины  Сигналы и спектры 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 [ 301 ] 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358

Окончание табл. 14.7

Итерация i

Количество сдвигов влево

Таблица 14.8. Ключевая перестановка 2

14 17

3 28

23 19

16 7

41 52

30 40

44 49

46 42

DES может реализовываться подобно блочной системе шифрования (см. рис. 14.11), что иногда называют методом шифровальной книги. Основным недостатком этого метода является то, что (при использовании одного ключа) данный блок входного открытого текста будет всегда давать тот же выходной шифрованный блок. Еще один способ шифрования, называемый способом шифрования с обратной связью, приводит к шифрованию отдельных битов, а не символов, что дает поточное шифрование [3]. В системе шифрования с обратной связью (описанной ниже) шифрование сегмента открытого текста зависит не только от ключа и текущих данных, но и от некоторых предшествующих данных.

С конца 1970-х широко обсуждались два спорных момента, связанных с DES [10]. Первый касается длины ключа. Некоторые исследователи считали, что 56 бит не достаточно, чтобы исключить взлом путем перебора. Второй момент касается внутренней структуры 5-блоков, которые никогда не выпускались IBM. Агентство национальной безопасности США, которое было привлечено к тестированию алгоритма DES, потребовало, чтобы эта информация не обсуждалась публично. Критики опасаются, что АНБ участвовало в проектировании этих схем и теперь способно проникать в любое сообщение, шифрованное согласно DES [10]. В настоящее время стандарт DES больше не является приемлемым выбором, обеспечивающим надежное шифрование. Поиск 56-битового ключа с помощью недорогих компьютерных методов является делом нескольких дней [11]. (Некоторые альтернативные алгоритмы обсуждаются в разделе 14.6.)

14.4. Поточное шифрование

Ранее мы определили разовое заполнение как систему шифрования со случайным одноразовым ключом, который обеспечивает безусловную защищенность. Реализовать разовое поточное заполнение можно с использованием действительно случайного потока ключей (ключевая последовательность никогда не повторяется). Таким образом, совершенная секретность может достигаться для бесконечного числа сообщений, так как каждое сообщение шифруется с помощью разных частей случайного ключевого

1Д Д Ппхпииг raquo;о iiiMrbr\r\D iuia

Q.11



потока. Развитие схем поточного шифрования - это попытка имитации схем одномоментного заполнения. Большой упор делается на генерации ключевых потоков, которые должны выглядеть случайными. Реализовать такие последовательности можно с помошью соответствуюших алгоритмов. Названная технология поточного шифрования использует псевдослучайные последовательности; их название отражает тот факт, что они выглядят случайными для случайного наблюдателя. Статистические свойства двоичных псевдослучайных последовательностей подобны получаемым при случайном подбрасывании симметричной монеты. В то же время, разумеется, эти последовательности являются детерминистическими (см. раздел 12.2). Данные технологии популярны, поскольку алгоритмы шифрования и дешифрования воплощаются с использованием регистров сдвига с обратной связью. На первый взгляд может показаться, что поточный псевдослучайный ключ может обеспечивать ту же защищенность, что и метод одномоментного заполнения, поскольку период последовательности, порожденной линейным регистром сдвига, составляет 2 бит, где п - количество разрядов в регистре. Если псевдослучайная последовательность воплощается с помощью 50-разрадного регистра и дискретности в 1 МГц, последовательность будет повторяться каждые 2 deg; - 1 микросекунды, или каждые 35 лет. В эпоху больших интегральных схем совсем несложно реализовать схему с 100 разрядами. В этом случае последовательность будет повторяться каждые 4 х 10* лет. Следовательно, можно предположить, что поскольку псевдослучайная последовательность не повторяется в течение такого длительного периода, она может казаться действительно случайной и давать совершенную секретность. Но все же существует одно важное отличие псевдослучайной последовательности от действительно случайной последовательности, используемой в методе одномоментного заполнения. Псевдослучайная последовательность генерируется алгоритмом. Таким образом, если известен алгоритм, то известна и сама последовательность. В разделе 14.4.2 будет показано, что из-за этой особенности схема шифрования, которая использует линейный регистр сдвига с обратной связью, слишком уязвима к атаке известного открытого текста.

14.4.1. Пример генерирования ключа с использованием линейного регистра сдвига с обратной связью

В технологии поточного шифрования для генерации псевдослучайной ключевой последовательности обычно используются регистры сдвига. Регистр сдвига может быть превращен в генератор псевдослучайной последовательности путем введения контура обратной связи, который вычисляет новый элемент для первого разряда, основываясь на предьщущих п элементах. Говорят, что регистр является линейным, если линейна операция, производимая в контуре обратной связи. В разделе 12.2 мы уже рассматривали пример генератора псевдослучайной последовательности. На рис. 14.13 этот генератор приведен повторно. В данном случае разряды регистра удобно нумеровать так, как показано на рис. 14.13, где п =4, а выходы разрядов 1 и 2 суммируются по модулю 2 (линейная операция) и передаются обратно на разряд 4. Если начальное состояние разрадов (х4, хз, xj, Х[) - это 1000, то следующие состояния будут выглядеть как 1000, 0100, 0010, 1001, 1100 и т.д. Выходная последовательность составлена из битов, снимаемых с крайнего правого разряда регистра, т.е. 111101011001000, где крайний правый бит в последовательности является самым ранним, а крайний левый - наиболее поздним. При данном произвольном п-разрядном линейном регистре сдвига с обратной связью выходная последовательность в конечном счете периодична.



Обратная связь

Выход

copy;

Сумматор по модулю 2

Рис. 14.13. Пример линейного регистра сдвига с обратной связью

14.4.2. Слабые места линейных регистров сдвига с обратной связью

Схема шифрования, в которой для порождения ключевого потока применяются линейные регистры сдвига с обратной связью (linear feedback shift register - LFSR), является очень уязвимой по отношению к атакам. Чтобы определить отводы обратной связи, начальное состояние регистра и всю последовательность кода, криптоаналитику требуется всего 2п бит открытого текста и соответствующий им шифрованный текст. Как правило, 2п намного меньше периода 2 - 1. Проиллюстрируем эту уязвимость с помощью примера регистра, изображенного на рис. 14.13. Пусть криптоаналитику, который ничего не знает о внутренних связях регистра, удалось получить 2п = 8 бит шифрованного текста и их открытый эквивалент.

Открытый текст: 01010101 Шифрованный текст: 00001100

Здесь крайний правый бит получен первым, а крайний левый - последним.

Чтобы получить фрагмент ключевого потока 01011001 (рис. 14.14), криптоаналитик складывает обе последовательности по модулю 2. Ключевой поток показывает содержание регистров в различные моменты времени. Крайние правые четыре ключевых бита показывают содержание регистра сдвига в момент г,. Если последовательно сдвигать эту четверку на один символ влево, то получим содержимое регистра в моменты ti, h, t. Используя линейную структуру регистра сдвига, можно записать следующее:

5+4 + 5Л + g2X2 + glXl = Xs. (14.27)

Здесь Xs - цифра, которая через контур обратной связи подана обратно на вход, а gi (= 1 или 0) определяет i-e соединение обратной связи. Таким образом, изучая содержание регистра в четыре момента времени, изображенных на рис. 14.14, можно написать следующие четыре уравнения с четырьмя неизвестными.

4(l) + ft(0) + 0) + .gi(l)=l 54(1) + 5з(1) + 52(0) + 51(0) = 0

4(0)+ Ы1) +52(1)+ Si(0) = l 54(1) + 5з(0) + Ы1) + 51П) = 0

(14.28)

Решение уравнений (14.28), соответствующих регистру, изображенному на рис. 14.13, является gi = l, amp;=1, ft = 0, 4 = 0. Таким образом, криптоаналитик узнал связи регистра, а также его начальное состояние в момент ti. Спедовательно, он может узнать последовательность в любой момент времени [3]. Обобщив этот пример на любой регистр сдвига с п разрядами, можно переписать уравнение (14.27) следующим образом:

1 = 1

(14.29)

14.4. Поточное шиЛповяние



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 [ 301 ] 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358