Криптоанализ классических шифров (стр. 10 из 27)

74 9116 74 47 33 74 55 96 85 6666 85 29 85 85-55 11 3374 5516 11 91 11 33 85 96 58 28 11 91 23 74 55 26 74 31 58 66 1111 47 62 11 66 61 55 58 96 74 29 11 91 91 11 4331 74 96 74 68 11,91 852916 96 58 33 85 9635 79 85,31 11 66 85 28 7491 8555 11 28 11 4374 79 58 29 66 85 91 91 11 43.5835 55 23 28 11 66 11 47 6174 91 1116 96 43 33 85 26 74 91 61 28 742955 74 55 47 11 33 23 4968 74 96 74 31 74 28,68 31 8558 2653 85 47 55 85 96 28 1131 74 66 79 91 1150 23 66 1129 23 49 55 58 91 1133 85 47 55 91 74 68 7491 85 66 85 68 11 66 11.

21.

40 77 40,29 75 5875 28 75!15 61 75 23 40 52 672929 54 52 1115 75 65 58 5415 84 40 29 54 61 67 28 75 77 7558 84 11 18 77 75 61 67 28 54 35 40,77 52 1115 75 37 11 84 11 52 54 28 11,28 4028 11 29 49 37 75 35 75 13,35 29 40 52 84 40 58 28 75 1335 54 84 15 54 65 28 75 1315 75 37 58 40 13 11 28 58 1129 75 90 29 49 72 40 11 58 37 8015 18 72 35 4029 84 11 13 11 2815 11 84 29 75 4113 54 84 75 29 75 41,5415 75 5211 1137 58 29 75 61 75 1337 61 75 82 11 28 4015 54 84 40 13 54 52 35 4054 9029 75 29 37 1118 8237 58 40 84 54 28 28 49 4680 52 11 84,35 40 35 54 13 5415 40 61 54 61 5461 11 5890 4037 58 7552 7515 75 80 29 61 11 28 54 8028 4035 75 28 29 11 41 11 84 1158 40 35 54 4629 75 5858 84 11 46 52 20 41 13 75 29 75 35-37 20 84 84 11 40 61 54 37 58 54 65 11 37 35 75 1137 75 65 11 58 40 28 54 11,11 37 61 5429 52 18 13 40 58 67 37 80,28 7513 11 37 58 28 49 46,28 40 52 7515 75 61 40 77 40 58 67,29 15 75 61 28 1118 37 58 84 40 54 29 40 11 58.54 33 7528 40 77 61 80 52 28 7515 75 35 40 90 49 29 40 11 5852 75 33 61 11 37 58 67,15 84 75 80 29 61 11 28 28 18 2054 4652 11 84 82 40 29 75 412915 11 84 29 18 2013 54 84 75 29 18 20:28 1835 40 3582 11,75 28 4075 58 15 84 40 29 54 61 4028 4011 29 84 75 15 11 41 37 35 54 4192 84 75 28 5826 11 61 49 4137 58 84 11 61 35 75 29 49 4133 40 58 40 61 67 75 285458 75 84 82 11 37 58 29 11 28 28 7515 75 84 29 40 61 4075 58 28 75 72 11 28 54 803777 11 84 13 40 28 37 35 75 4154 13 15 11 84 54 11 41,4029 52 75 33 40 29 75 3575 52 182972 11 37 58 28 40 52 26 40 58 75 1333 11 84 11 77 75 29 49 1133 40 58 40 84 11 5475 52 28 75 77 7554 9029 75 11 28 28 49 4615 75 84 58 75 2926 11 61 49 4652 29 4065 40 37 4015 40 61 54 61 5415 7558 75 4158 75 65 35 111877 75 84 54 90 75 28 58 40,77 52 1135 40 35 75 13 18 -58 7533 52 54 58 11 61 67 28 75 13 1829 75 80 35 1115 75 65 18 52 54 61 37 8077 11 84 13 40 28 37 35 54 4135 84 11 41 37 11 84…75 33 19 11 35 58 54 29 28 75 37 58 5484 40 52 5437 58 75 54 5818 58 75 65 28 54 58 67,65 58 7529 7529 58 75 84 18 2013 54 84 75 29 18 2090 52 11 72 28 54 41,15 18 37 58 675428 11 29 11 61 54 35 54 4129 75 11 28 28 75-13 75 84 37 35 75 4192 61 75 5829 13 11 37 58 113737 75 20 90 28 54 35 40 13 5415 40 58 84 18 61 54 84 75 29 40 6115 84 54 61 11 77 40 20 23 54 1129 75 52 495415 40 84 1884 40 9029 84 75 52 1133 4952 40 82 1137 58 84 11 61 80 6115 7528 40 37 58 75 80 23 54 13,4028 1115 84 54 29 54 52 11 29 72 54 13 37 8015 75 52 29 75 52 28 49 1361 75 52 35 40 1335 84 54 77 37-13 40 84 54 28 11.

22.

56 9631 57 87 3756 7584 77 87 24 96 73 68 75,56 7550 37 16 42 68 77,7720 73 3737 49 56 77 39 77 87 37,39 73 3712 84 9616 91 64 56 91 87 37.75 56 84 73 16 91 68 94 75 7531 57 87 7544 16 37 84 73 577556 96 49 77 73 96 14 87 75 12 57:96 84 87 7556 7744 37 28 37 68 37 56 56 75 68 9656 96 7356 7550 37 16 42 68 77,56 7584 77 87 24 96 73 68 75,96 84 87 7573 77 2673 37 87 41 68 3784 77 87 24 96 73 68 7731 96 4950 37 16 42 68 7775 87 7550 37 16 42 37 6831 96 4984 77 87 24 96 73 68 75-56 9673 3739 73 3756 9612 64 37 28 75 73 41,56 3728 77 35 9656 9644 16 75 31 87 75 35 77 73 41 84 61.12 84 9644 16 96 35 56 75 9616 77 84 68 87 77 28 5787 96 73 61 736839 96 16 73 91,1235 75 49 56 4184 87 96 28 91 96 7356 96 26 96 28 87 96 56 56 3744 16 96 73 12 37 16 61 73 4149 77 44 77 84 56 37 1412 77 16 75 77 56 73.56 91 35 56 3768 77 6826 37 35 56 3731 57 84 73 16 96 9637 73 84 82 28 7784 26 77 73 57 12 77 73 41 84 61,91 31 75 16 77 73 41 84 616839 96 16 73 37 12 37 1426 77 73 96 16 7575 4950 37 16 37 28 68 77,12 84 73 91 44 77 96 731284 75 87 9149 77 44 77 84 56 37 1412 77 16 75 77 56 7337 73 64 37 28 77…

12 96 84 4137 68 16 91 35 77 82 22 75 1426 75 1612 56 96 49 77 44 56 3784 73 77 8756 9644 16 37 84 73 3739 91 35 75 26-12 16 77 35 28 96 31 56 57 26.44 37 28 37 49 16 96 12 77 73 4184 87 96 28 37 12 77 87 3712 84 96 647512 84 61.44 41 82 22 75 6444 75 12 3784 37 87 28 77 73 75 68 37 12-1273 37 26,39 73 3737 56 7556 9684 37 87 28 77 73 75 68 7512 37 12 84 96,7750 16 91 44 44 7749 77 64 12 77 73 7775 4912 37 96 56 56 37 1468 37 56 73 16 16 77 49 12 96 28 68 75,44 16 96 84 73 77 16 96 87 37 50 3750 37 84 73 75 56 75 39 56 37 50 3764 26 57 16 61-1273 37 26,39 73 3737 5612 37 12 84 9656 9644 37 16 73 41 9675 87 7512 87 77 28 96 87 96 94,75 87 7573 377528 16 91 50 37 961237 28 56 37 2687 75 94 96,7744 37 87 68 37 12 56 75 6849 28 96 42 56 96 1473 77 14 56 37 1444 37 87 75 94 75 75.12 84 9612 37 49 26 37 35 56 37,68 37 50 28 7791 84 87 37 12 87 96 56 56 37 50 3784 75 50 56 77 87 7756 96 7356 7791 84 87 37 12 87 96 56 56 37 2626 96 84 73 96.

23.

22 10 75 6247 1074 10 24 88 47 39 35 66 15 75 58 10 47 64 53 5385 66 35 10 69 62 28 10 24 5366 49 53 47 47 10 49 64 10 58 3928 22 88 17 10 79 47 88 1547 66 22 53.4447 10 85 17 10 28 53 24 75 443551 66 75 58 53 47 53 64 88.35 10 3572 62 28 10 24 6647 8817 10 69,4466 80 37 80 10 2469 49 88 75 3937 74 53 17 66 58 28 66 17 88 47 53 885385 66 35 66 15,22 37 28 75 58 28 10,35 66 58 66 17 62 8853 75 85 62 58 62 28 10 88 79 39,66 35 10 69 10 28 79 53 75 392849 10 28 47 6669 47 10 35 66 74 62 4274 88 75 58 10 42.79 53 17 66 35 53 8828 66 17 66 58 1072 62 24 5317 10 75 85 10 42 47 37 58 62,37 75 10 49 39 72 1037 58 66 47 37 24 102875 37 74 88 17 35 10 42.4428 66 79 88 242842 66 24 24,51 49 8858 37 74 10 47 47 62 8869 88 17 35 10 24 1069 62 72 35 6666 58 17 10 31 10 24 5364 28 88 58 625349 88 58 10 24 5353 47 58 88 17 39 88 17 10.37 49 53 28 53 58 88 24 39 47 66,47 6642 66 69 44 53 4747 8837 69 47 10 2474 88 47 44.66 4785 17 66 58 44 47 37 2417 88 51 53 75 58 17 10 64 53 66 47 47 37 9735 47 53 51 37.4428 69 44 2417 37 22 35 37,66 72 7 41 03 54 73 7 2485 88 17 662872 17 66 47 69 66 28 37 9722 88 17 47 53 24 39 47 53 64 3753,75 35 24 66 47 53 28 79 53 75 3947 10 49 17 10 75 35 17 62 58 62 74 5375 58 17 10 47 53 64 10 74 53,75 58 66 24 35 47 37 24 75 447585 88 17 28 66 1553 6974 47 66 31 88 75 58 28 1047 88 66 31 53 49 10 47 47 66 75 58 88 15,35 66 58 66 17 62 8885 66 49 75 58 88 17 88 51 10 24 5374 88 47 4425 58 66 1547 66 22 39 97.74 66 8853 74 44,42 66 17 42 8824 37 53 7572 66 17 42 88 75,72 62 24 6647 10 22 88 17 58 10 47 662835 47 53 51 88,5322 88 17 47 53 24 1088 80 8847 8837 75 85 88 24 5328 62 75 66 42 47 37 58 39.

24.

6152 16 36 26 14 5416 45 24 29 4595 1129 36 95 86 36 16 29 451452 49 75 36 4797 36 93 95 61 54 26 6197 3626 86 45 97 49 95 41 29 11 47.93 49 30 61 86 95 11 93 56 11 86 83 8995 36 47 49 1695 11 37 36 93 14 54 26 6195 1130 86 36 16 36 4721 86 11 33 49,2636 29 95 11 47 1495 1130 95 45 86 16 49 95 95 14 8993 30 36 16 14 29,33 11 54 29 14 891471 11 52 16 36 19 49 95 95 83 89,36 52 95 49 26 49 95 95 83 8952 11 54 98 26 86 16 11 93 36 89;75 93 49,29 11 2997 36 47 95 14 54 36 26 4147 95 49,26 86 36 61 54 1197 54 61 33 95 11 6126 29 11 47 49 89 29 11.21 86 3652 83 54 1126 11 47 11 6152 36 54 41 19 11 6129 36 47 95 11 86 1130 75 36 26 86 14 95 14 56 49.6186 36 54 29 95 45 5493 30 49 16 41,36 95 1197 36 93 93 11 54 11 26 41.97 36 93 97 36 86 36 54 29 36 4775 36 16 49 54 1154 98 26 86 16 11.3049 4952 49 71 33 11 54 36 26 86 95 36 4726 30 49 86 496145 71 95 11 5426 49 52 61.95 1145 71 29 36 8933 49 54 49 71 95 36 8929 16 36 30 11 86 1454 49 33 11 5461,97 36 26 86 11 16 49 30 19 14 891436 52 16 98 71 75 19 14 89,1416 11 71 75 54 61 93 83 30 11 5454 49 97 95 14 95 4595 1197 36 86 36 54 29 49.6145 26 54 83 19 11 5475 36 54 36 26.95 4926 36 30 26 49 4747 36 89-52 49 7136 52 49 16 86 36 95 36 30,95 49 97 16 14 61 86 95 83 89,97 36 37 36 33 14 8995 1147 11 75 95 14 86 36 78 36 95 95 45 9871 11 97 14 26 41.-45 93 14 30 14 86 49 54 41 95 36,-26 29 11 71 11 5436 95,-95 11 2693 30 36 491447 8336 93 95 36.30 97 16 36 24 49 47,30 3626 95 4995 14 24 86 3695 4926 97 36 26 36 52 95 3630 83 71 30 11 86 4145 93 14 30 54 49 95 14 49.6116 36 52 29 3626 97 16 36 26 14 54:-71 95 11 24 14 86,30 26 4921 86 3626 36 95?-97 16 14 24 49 4797 36 26 54 49 93 95 14 8926 36 95.-33 49 26 86 36 4736 9597 36 29 11 71 11 5495 1197 45 26 86 36 89 97 45 71 83 16 49 29,26 86 36 61 30 19 14 8995 1147 16 11 47 36 16 95 36 8929 16 83 19 29 4995 36 24 95 36 75 3626 86 36 54 14 29 11.-86 49 52 49 97 16 14 93 49 86 26 61,95 11 30 49 16 95 36 49,45 30 14 93 49 86 4147 95 36 33 49 26 86 30 3626 95 36 30,97 16 49 33 93 4924 49 4793 36 52 49 16 49 19 41 26 6193 3621 86 36 8995 36 24 14.29 11 29 36 4926 49 75 36 93 95 6124 14 26 54 3697 3686 30 36 49 47 4529 11 54 49 95 93 11 16 98?

25.

48 84 13 3394 13 48 42 33 46 82,84 13 82 4894 82 46 84 33 4213 88 82 84 16 46 1625 8250 17 481342 61 37 78 50 511682 42 13 82 84 16 46 1650 48 17 341376 82 25 82 1672 82 46 48 69 17 82 28 82,28 84 4851 75 4875 84 33 46 1646 33 84 33 17,75 33 37 82 13 17 341638 48 37 17 16 46 33.82 1713 58 94 25 33 69 58 13 33 4676 82 75 48 46 33 17 16 34,163476 82 25 33 69 58 13 33 4648 50 5113 94 48,38 42 8217 1648 94 42 781350 16 37 48.1376 37 16 28 82 37 64 17 4817 48 17 33 13 16 94 42 17 82 28 8272 58 46 8294 82 72 37 33 17 8213 94 48,38 42 8284 82 13 48 46 82 94 78 76 82 13 16 84 33 42 7851 75 4851 94 82 76 64 16 501638 42 8269 37 34 4217 58 17 4869 84 37 33 13 94 42 13 51 61 21 16 48:28 82 37 82 84 33,75 33 37 25 16 481688 82 46 82 84 17 58 4894 42 37 33 17 58,94 82 25 37 82 13 16 21 33,94 25 37 58 42 58 481369 48 50 17 58 8828 46 51 72 16 17 33 88,72 82 37 82 69 84 34 21 16 4850 82 37 3425 82 37 33 72 46 16,82 37 51 84 16 3413 82 91 17 58,16 17 94 42 37 51 50 48 17 42 5813 37 33 38 48 13 33 17 16 341650 51 69 58 25 16,76 46 48 17 16 42 48 46 78 17 58 8875 48 17 21 16 17,17 48 76 82 84 13 16 75 17 58 4869 13 48 69 84 581676 46 33 17 48 42 58,25 37 33 94 25 16,25 82 42 82 37 58 50 1676 82 46 78 69 51 61 42 94 3417 48 13 48 37 17 58 48,25 82 28 84 3376 16 64 51 4294 13 82 1650 48 37 69 25 16 4825 33 37 42 16 17 58,37 33 94 42 48 17 16 341650 16 17 48 37 334 65 894 8213 94 48 50 1616 8894 82 25 37 82 13 48 17 17 58 50 1669 33 50 48 38 33 42 48 46 78 17 58 50 1694 13 82 91 94 42 13 33 50 16,94 48 37 48 72 37 34 17 58 8833 17 28 48 46 82 13,38 48 9188 46 48 72-88 13 33 46 331676 37 48 13 82 69 17 48 94 48 17 16 4828 82 94 76 82 84 33,37 33 69 84 33 38 5117 33 28 37 33 841364 25 82 46 33 88,19 16 28 51 37 5876 42 16 981698 33 37 48 91,88 37 33 17 34 21 16 48 94 341394 33 50 82 5094 48 37 84 98 4876 16 37 33 50 16 84,42 48 17 7872 58 25 33,17 3325 82 42 82 37 82 5076 82 25 82 16 42 94 3469 48 50 46 34,1637 58 72 58,17 3325 82 42 82 37 82 9194 42 82 16 4272 58 25,76 51 94 42 58 17 1613 94 48 50 16 46 82 94 42 16 13 82 28 8272 82 28 33.82 1751 13 16 84 48 4613 48 21 1617 48 82 76 16 94 51 48 50 58 48,42 33 25 16 48,25 33 2551 46 16 98 58,82 94 13 48 21 48 17 17 58 4828 33 69 82 13 58 50 1637 82 75 25 33 50 16,1625 16 42 33,25 82 42 82 37 58 9151 50 16 37 33 48 4276 37 1669 13 51 25 33 8838 48 46 82 13 48 38 48 94 25 82 28 8228 82 46 82 94 33.

3.4 Шифр Виженера

Теория криптоанализа шифра Виженера

Рассмотрим шифр модульного гаммирования с уравнением b_i = (a_i+ y_i) mod n, для которого гамма является периодической последовательностью знаков алфавита. Такая гамма обычно получается периодическим повторением некоторого ключевого слова. Например, ключевое слово KEY дает гамму KEYKEYKEY... . Рассмотрим задачу вскрытия такого шифра по тексту одной криптограммы достаточной длины.

Пусть µ - длина ключевого слова. Обычно криптоанализ шифра Виженера проводится в два этапа. На первом этапе определяется число µ, на втором этапе — само ключевое слово.

Для определения числа µ применяется так называемый тест Казиски, названный в честь Ф. Казиски, применившего его в 1863 г. Тест основан на простом наблюдении о том, что два одинаковых отрезка открытого текста, отстоящих друг от друга на расстоянии, кратном µ, будут одинаково зашифрованы. В силу этого в шифр-тексте ищутся повторения длины, не меньшей трех, и расстояния между ними. Обратим внимание на то, что случайно такие одинаковые отрезки могут появиться в тексте с достаточно малой вероятностью.

Пусть d₁,d₂,... — найденные расстояния между повторениями и d — наибольший общий делитель этих чисел. Тогда µ должно делить d. Чем больше повторений имеет текст, тем более вероятно, что µ совпадает с d. Для уточнения значения µ, можно использовать так называемый индекс совпадения, введенный в практику У. Фридманом в 1920 г.

Для строки х = (x₁,...,_,x_m) длины т, составленной из букв алфавита А, индексом совпадения в х, обозначаемым I_c(х) будем называть вероятность того, что две случайно выбранные буквы из х совпадают.

Пусть A = { a_i,..., a_n }. Будем отождествлять буквы алфавита с числами, гак что

a₁ ≡ 0,..., a_n-1 ≡ n - 2, а_n = n -1.

Теорема. Индекс совпадения в х вычисляется по формуле

(1)

где f_i — число вхождений буквы a_i в х, i

Z_n.

Доказательство. Будем вычислять I_с(х) как отношение числа благоприятных исходов к общему числу исходов. Благоприятным является исход, при котором на выбранных двух позициях в х расположены одинаковые буквы. Общее число исходов равно, очевидно, С²_m . Число благоприятных исходов есть

, (2)

В самом деле, переупорядочим буквы в х таким образом, чтобы сначала шли f_a1 букв а₁ затем — f_a2букв а₂и т.д.(4):

, (3)

Теперь заметим, что при случайном выборе мест (i и j) в строке х благоприятными являются следующие исходы:

В случае (а₁) мы можем выбрать пару букв а, из набора (3)

способами, в случае (а₂) пару букв а₂из (3) — способами и т. д.

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

и, следовательно, формулой (1).

Пусть х — строка осмысленного текста (например, английского). Допустим, как и ранее, что буквы в х появляются на любом месте текста с соответствующими вероятностями р₀,...,р_n-1независимо друг от друга, где р_i — вероятность появления буквы i в осмысленном тексте, i

Z_n В такой модели открытого текста вероятность того, что две случайно выбранные буквы из х совпадают с i Z_n равна p²_i следовательно,