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

РО = = 2 1 ~~ осмысленное (14.12)

Р(М2) = 0 Л/2 - бессмысленное (14.13)

Предположим, что существует 2 * возможных ключа (размер алфавита ключей), где ЩК) - энтропия ключа (количество бит в ключе). Предположим, что все ключи равновероятны.

Р()=-щ- = ~ (14.14)

Определение расстояния единственности основано на модели случайного шифра, которая утверждает, что ддя каждого ключа К и шифрованного текста С операция дешифрования Dk(Q дает независимую случайную переменную, распределенную по всем юзможным 2 сообщениям (как осмысленным, так и бессмысленным). Следовательно, для данных Ки С операция gt;к(С) может с равной вероятностью давать любое из открытых сообщений.

При данном шифровании, описываемом как С,=Ек{М,), неверное решение F

возникает всегда, когда шифрование с помощью другого ключа Kj может давать С, из того же сообщения М, или из некоторого другого сообщения М,.

C,=E {M,) = E{M,) = E{Mj) (14.15)

Криптоаналитик, перехвативший С не сможет выбрать верный ключ и, следовательно, не сможет взломать систему шифрования. Мы не рассматриваем операции дешифрования, которые дают бессмысленные сообщения, так как они могут легко отбрасываться.

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

P(F) = - = 2-=2- deg; (14.16)

Здесь D = /-r - избыточность языка. Тогда ожидаемое число неверных решений F равно следующему:

F=[2 lt; -1]P(F) = [2 ( -ф- =2 -ш

Поскольку F быстро убывает с увеличением N, то

log2F = H(K)-DN=0 (14.18)

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

N=-. (14.19)



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

Стоит отметить, что доминирование бессмысленных дешифровок позволяет взламывать криптограммы. Уравнение (14.19) показывает значение использования методов сжатия данных до шифрования. Сжатие данных устраняет избыточность языка, таким образом увеличивая расстояние единственности. Совершенное сжатие данных даст Z? = О и = оо для любого размера ключа.

Пример 14.4. Расстояние единствешюсти

Вычислите расстояние единственности для системы шифрования, использующей письменный английский язык, ключ которой задается последовательностью к\, где каждое к, -

случайное целое из интервала (1, 25), которое определяет номер сдвига (рис. 14.3) для /-го символа. Предположим, что все возможные ключевые последовательности равновероятны.

Решение

Существует (25) возможных равновероятных ключевых последовательностей. Следовательно, используя равенства (14.5), (14.8) и (14.19), получаем следующее:

энтропия ключа: Н(К) = logi (25) = 135 бит,

абсолютная интенсивность английского языка: / = log2 26 = 4,7 бит/символ,

предполагаемая истинная интенсивность английского языка: г = 1,5 бит/символ,

избыточность: D = / - г = 3,2 бит/символ,

, Н(К) 135

N =-=-= 43 символа.

D 3,2

В примере 14.2 совершенная секретность сообщения из 29 символов иллюстрировалась с использованием того же типа ключевой последовательности, что и в данном примере, где показано, что если имеющийся шифрованный текст состоит из 43 символов (откуда следует, что некоторая часть ключевой последовательности должна использоваться дважды), то возможно единственное решение. В то же время не определена вычислительная сложность отыскания рещения. Даже если оценить теоретическое количество шифрованного текста, необходимое для взлома шифра, практически это может оказаться невозможным.

14.3. Практическая защищенность

Для последовательностей шифрованного текста, размер которых больше расстояния единственности, любая система уравнений (определяющая ключ) может быть решена путем простого перебора всех возможных ключей, пока не будет получено единственное решение. Однако это соверщенно непрактично, за исключением применения очень короткого ключа. Например, для ключа, полученного путем перестановки английского алфавита, существует 26! = 4 х 10* возможных пере-



становок (в криптографическом смысле это считается малым). Будем считать, что в результате изнурительных поисков мы нашли правильный ключ, перебрав приблизительно половину возможных комбинаций. Если допустить, что каждая проверка потребует для вычисления 1 мкс, то полное время поиска превысит 10 лет. Следовательно, если криптоаналитик хочет иметь некоторую надежду на успех, то о лобовых методах перебора следует забыть и применять какую-ту иную технологию (например, статистический анализ).

14.3.1. Смешение и диффузия

При расшифровке многих систем шифрования может применяться статистический анализ, использующий частоту появления отдельных символов и их комбинаций. Шеннон [5] предложил две концепции шифрования, усложняющие задачу криптоаналитика. Он назвал эти преобразования смешение (confusion) и диффузия (diffusion). Смешение - это подстановки, которые делают взаимосвязь между ключом и шифрованным текстом как можно более сложной. Это усложняет применение статистического анализа, сужающего поиск практического подмножества области ключей. В результате смешения дешифрование даже очень короткой последовательности шифрованного текста требует большого числа ключей. Диффузия - это преобразования, сглаживающие статистические различия между символами и их комбинациями. Примером диффузии 26-буквенного алфавита является преобразование последовательности сообщений М = Л/о, Л/ь ... в новую последовательность сообщений 1= Уо, Yi, - с помощью следующего соотношения:

У = Af +, по модулю 26. (14.20)

1 = 0

Здесь каждый символ в последовательности рассматривается как число по модулю 26, S - некоторое выбранное целое число и л = 1, 2, ... . Новое сообщение У будет иметь ту же избыточность, что и исходное сообщение М, но частота появления всех букв в У будет более равномерной, чем в Л/. В результате, чтобы статистический анализ принес криптоаналитику какую-либо пользу, ему необходимо перехватить большую последовательность шифрованного текста.

14.3.2. Подстановка

Технология шифрования с помощью подстановки, например использование шифра Цезаря и прогрессивного ключа шифрования Тритемиуса, широко используется в головоломках. Такие простые подстановочные шифры дают малую защищенность. Чтобы к подстановочной технологии можно было применить концепцию смешения, требуется более сложное соотношение. На рис. 14.6 изображен пример создания большей подстановочной сложности с помощью использования нелинейного преобразования. В общем случае п входных битов сначала представляются как один из 2 различных символов (на приведенном рисунке п = 2). Затем множество из 2 символов перемешивается так, чтобы каждый символ заменялся другим символом множества. После этого символ снова превращается в п-битовый.



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