foundations_chap_2 (Лекции по информационной безопасности)

ГЛАВА 2КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫДанная глава посвящена изложению основных идей и методов криптографии. Под криптографией мы будем понимать область знаний, относящихся к средствам и методам преобразования сообщений в непонятную для посторонних форму, а также средствам и методам проверкиподлинности сообщений. Данная область является классическим примером соревнования средств защиты и нападения. Некоторые авторы под криптографией понимают только то, что относится к защите — в противоположность криптоанализу, который направлен на преодоление криптографической защиты. В этом случае дляобозначения совокупности криптографии и криптоанализа используется термин криптология.В первом параграфе на ряде простых примеров излагаются наиболее важные понятия криптографии с симметричным ключом.

Приведены примеры основных приемов криптоанализа, которые сводятсяк опробованию секретных ключей, а также применению вероятностностатистических и алгебраических методов.Во втором параграфе рассматриваются две системы блочного шифрования: Российский ГОСТ на шифрование данных и алгоритмDES, являвшийся до недавнего времени Федеральным стандартомСША.В третьем параграфе изложены идеи шифрования с открытымключом и цифровой подписи.В четвертом параграфе рассматривается получившая широкоераспространение криптосистема RSA.

Для полного понимания материала данной главы требуется определенная математическая подго-136КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫтовка. При отсутствии такой подготовки рекомендуется пропуститьвсе моменты, касающиеся доказательств тех или иных положений.Для более глубокого знакомства с проблемами криптографии рекомендуется обратиться к учебному пособию [2], вышедшему в моментзавершения работы над данной книгой. Там же можно найти и болееподробную библиографию.§ 2.1. Введение в проблемы классической криптографииЧтобы сделать материал данного параграфа более наглядным,начнем с рассмотрения небольшого примера.Пусть шифруемые сообщения состоят из символов алфавита A,включающего буквы русского языка (без буквы Ё) и знак пробела ( ),и имеется таблица 2.1, задающая соответствие между символами этого алфавита и числами от 0 до 32.Таблица 2.1А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч ШЩ Ъ Ы Ь Э Ю Я09 23 01 04 07 02 14 13 21 31 17 25 29 06 22 11 26 00 19 30 08 18 16 28 03 27 32 15 10 20 24 12 05Шифрование методом простой замены в данном случае заключается в подмене символов шифруемого сообщения соответствующимичислами из второй строки: «А» на «09», «Б» на «23» и т.

д. Такимобразом, текст:«ПРОСТАЯ ЗАМЕНА ОДИН ИЗ САМЫХ ДРЕВНИХ ШИФРОВ»в зашифрованном виде будет выглядеть следующим образом:«11 26 22 00 19 09 12 05 13 09 29 02 06 09 05 22 07 21 06 05 21 13 05 0009 29 15 18 05 07 26 02 01 06 21 18 05 03 21 08 26 22 01».Для того, чтобы расшифровать это сообщение, нужно произвести обратную замену, то есть найти в нижней строке таблицы 2.1каждое двузначное число криптограммы и заменить его стоящей надним буквой из верхней строки. Нижняя строка таблицы 2.1 выступаетв данном случае в качестве ключа, позволяющего как зашифровать,так и расшифровать сообщение.Если с помощью шифра простой замены зашифровано достаточно длинное сообщение, его можно прочесть и не имея ключа. Делов том, что частоты появления чисел в шифрованном тексте будутсовпадать с частотами появления соответствующих им символов висходном тексте.

Поэтому для дешифрования достаточно подсчитать§ 2.1.ВВЕДЕНИЕ В ПРОБЛЕМЫ КЛАССИЧЕСКОЙ КРИПТОГРАФИИ137относительные частоты встречаемости различных чисел в шифрованном сообщении и сравнить их с вероятностями встречаемости букв втекстах русского языка, приведенными в таблице 2.2.Таблица 2.2А0.069Л0.039Ц0.005Б0.013М0.027Ч0.012В0.038Н0.057Ш0.006Г0.014О0.094Щ0.004Д0.024П0.026Ъ0.001Е,Ё0.071Р0.042Ы0.015Ж0.007С0.046Ь0.013З0.016Т0.054Э0.002И0.064У0.023Ю0.005Й0.010Ф0.003Я0.017К0.029Х0.0080.146В таблице приведены оценки вероятностей появления букв русского языкаи пробела, полученные на основе анализа научно-технических и художественных текстов общим объемом более 1 000 000 символов.Для того, чтобы установить однозначное соответствие междусимволами нашего алфавита и двузначными числами зашифрованногосообщения, исходя только из анализа частоты появления последних,нужен очень большой текст. Поэтому задача дешифрования шифрапростой замены в случае небольших текстов не имеет простого алгоритма решения.

Это скорее творческий процесс, требующий большоготерпения и хорошего знания языка. При дешифровании простой замены может оказаться также полезной таблица 2.3 (см. стр. 138–139),содержащая частоты встречаемости различных пар, подряд идущихсимволов (биграмм).Проанализировав диагональные элементы этой таблицы, можнозаметить, что пара «НН» встречается гораздо чаще других пар, состоящих из одинаковых букв. Это позволяет на относительно небольшом тексте почти однозначно определить — какому числу соответствует буква «Н».

Можно подметить и другие полезные закономерности.Прежде чем дать формальное определение шифра, введем обозначения: X — множество возможных открытых текстов; S — множествошифрованных текстов (криптограмм); K — множество ключей.138КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫТаблица 2.3 (левая часть)А БВГ Д Е,Ё Ж ЗИЙ К Л МНОПА5 780 2445 80520791399 9693584 302 592397271843164 613630 1001Б 833815 1392165 103 5360 153 589 42 293 21410В 66898 136 14 19749780 344 32750 2471008 148 1159 5619 167Г 1730030 720 38311 6970 651147 26 318 66780Д 3999 68 744 17 354233 40 13 18750 254 719 143 1670 3383 184Е,Ё 337 748 1651247634151224 7001386 2272000243157254088 8090 389 953Ж 1099 240 10 830275070 9310 110 296 915430З 5543 141 953 241 788 483 64 15 6030 136 410 606 1224 13080И 288 541 2538 39112622510 2282740 15371657264048292871 3503 720 500Й0798 7600000 122 125 29 30760К 62212 40100 743 124 87 27740 17 9192 524 77390Л 5843 6218 176 484795 252 21 59060 291 323 39 552 532241М 3790 8554 540372900 26200 126 150 426 1261 3362 270Н 8380424 77 68978558 52 87750 46000 4097110340О163779 817746174680148719051618 6454035226662815330 4852 328 1879П 20711000229309 12090 64 7360 238 9102 166Р 8426 61 438 802 1886409 365 33 54890 376 182 891 823 867560С 1468 63 1356 19 2132466 27 13 2165035222634 652 1106 2910 1914Т 5467 18 26323 15261710 12 43740 759 175 136 15931220673У 149 898 524 9371462 402 940 25817 105 7851694 854 6013 826Ф 3750000 40600 68600 6511 8940Х 5261 142 420 9400 26209 117 41 336 16260Ц 47104900 96100 21540 12400 1940Ч 20720100376600 16220 387 193 904520Ш 77904600171800 16090 281 4005 327 18234Щ 3860000151700 152700005630Ъ00000 9660000000000Ы0 214 839 76 1381173 52 8521605 17414121231 1100 199Ь0 2929 53 76 5751 479470 7830 168 169548Э00332200317 73 107 101403Ю0 184126 18304700 26 20 442 400Я0 15 503 70 464 383 95 36019 34 147 581 344 49314133875350145573462569323481360456711158887402318552313103 972716937В таблице для всех возможных пар букв (с добавлением пробела) приведено количество их появлений в научно-технических и художественных текстах общим объемом в 1000 000 символов.

Первая буква определяет строку,а вторая буква — столбец, на пересечении которых указано число появленийсоответствующей пары в исследованном наборе текстов.§ 2.1.ВВЕДЕНИЕ В ПРОБЛЕМЫ КЛАССИЧЕСКОЙ КРИПТОГРАФИИ139Таблица 2.3 (правая часть)РСТУ Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я3814 4124 4812 144 252 9531316 988631741 000 10 807187015441 А1036 1603 9950 15034 62069912251 250 13 249 189 Б586 1701 301 6780 54 27 77690 12 52422 33900 337 7111 В1688615 441000 36 1 0 000000 415 Г952 595 15113530 87 150 55126 0 47 487 38817 360 1264 Д6184 4368 5292 133 94 548 3241046640471 0002 163 13515142Е,Ё3162 143000 25 0 0 00 15000 194 Ж32693 523002 47 2 0 15 471 10002 150 1525 З1534 3643 4337 86 4261521 8551902369233 0007 398237716600 И0 534 215020 59 124146 13 000004 8257 Й1847 254 19081757 202 2822 8 0 000000 3795 К0 1416 1401234 1040 96 10 1 0 64141361 8011945 5778 Л87 20221534305 19 8 2 01137 3230 501 7361 М28 454 12942830 6852 363 134 3123 04203 7210 1161317 2597 Н6353 6760 5998 131 228 386 3061499630194 000 117 298 56418322 О747487 229 700006 15 12 0 0 286 87 15 21 277 158 П118 215 7572374 21 190 47 137342 30 01322 4800 188 857 1368 Р417 1044111451196 46 181 58 278125 2 20 31125431 693572 3175 С2994 1418351839 439 14 266 4 4 7154944370 50 346 5763 Т1062 1182 14223 140 6157 799553333 000 111188 82 5346 У3061713 222 28000 0 0 0 23 1100051 Ф239518 1380100 17 0 500200 3888 Х2702 1170020 0 0 0 1430000 275 Ц510 2502 3610000 37 0 00 87000 419 Ч6076 2810000 0 0 00 24700071 Ш400 1250000 0 0 00 2700024 Щ00000000 0 0 00000 1240 Ъ195 549 626001611 11 209502 5 00000 20 4208 Ы0 630 182090 91 36286 7 0003 369 183 8032 Ь1214 20060 24 1700 0 0 00000013 Э36 131 51901 47 13 256 24828 0000 431 2453 Ю72 563 118685 188 37 125 19363 0000 283 10110197 Я421314568 736838521062 979 4334208871101 0002168 4613250140КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫО п р е д е л е н и е.