МИСЗКИ книга (1085503), страница 23
Текст из файла (страница 23)
Как производится расшифрование криппкраммы Сначала издо определить число длинных столбцов, то есть число букв в последней строке прямо)толъника. Для этого нужно разделить шсло букв в сообщении на длину числового ключа. Остаток от деления и будет искомым числом. Когда это число определено, икквы криптограммы можно водворить на их собственные мес- ~ з. и сообщение будет прочитано естественным образом. им е 38 = 7.5+ 3, поэтому в заполнеинои табнных и 4 коротких стол ца. лице имеется 3 длинных р бщ ся из второго п он — длинный (так как первые три — нные), поэтому первые шесть букв разуют в рой столбец.
Следующие пять букв юразуют — короткий). Итак далее. Элементы криптоанализа ш фро р Заметим, что буквы каждого столбца заполненною прямо- угольника выписываются в кр я столбцами таблиа раЖиваатся на отрезки, являющиеся стол тограмма раЖи дует попытаться соединить цы.
Поэтому пр и дешифровании следу б «риптотраммы так„чтобы последовательных букв «ритгготр х шие (читаемые), с точки зрения обычного они образовывали хорошие ии. Дчя этого естественно исполь льзовать наибо- текста, комбинации. Дчя орые можно соста- лее частые биграммы откр ытого текста, которые текста. Если для вить из букв расом тр ассма иваемого шифрованного тек е СТ (самая частая би- несколько букв, стоящих до и после данной буквы, и нескольдо и после двиной буквы, соед аются д 6 6 записанные рядом. ры, то есть получаются д аются два стол ца укв, Конечно, мы не знаем длины стол цов, ио не ить, используя положение кон ения на них можно получ б лжиы иметь одинаковые длины б .
Так, стол цы до или б иннее второго на одну букву, или первый столбец может ыть длин б — последняя буква сообщения: итогдаэта уква— ния СТ получается по одной парг Для выбранного сочетания по ов каждою конкретного выбора букв и из кр ообр отобрать ту пару, которая со аммы, и из них целесообразно рать гр держит наиболее частые игр б аммы.
го оцесса можи Заметим, что при автоматизации этого проц ой би е вес, рав , равный частоте ее появления к ы . б азно отобрать ту пару столб ытом тексте. Тогда целесообразно откры больший вес. Кстати, появление одно' цов, которая имеет наи льший в 138 биграммы с низкой частотой может указать на то, что длину столбца надо ограничить. Выбрав пару столбцов, мы аналогичным образом можем подобрать к ним третий (справа или слева) и т. д. Описанная процедура значительно упрощается при использовании вероятных слов, то есть слов, которые могут встреппъся в тексте с большой вероятностью.
Рассмотрим также метод, применимый к любым шифрам перестановки. Допустим„что к двум или более сообщениям (или отрезкам сообщений) одинаковой длины применяется один и тот же шифр перестановки. Тогда очевидно, что буквы, которые находились на одинаковых местах в открытых текстах, окажутся иа одинаковых местах и в шифрованных текстах. Выпишем зашифрованные сообщения одно под другим так, что первые буквы всех сообщений оказываются в первом столбце, вторые — во втором и т.
д. Если предположить, чю две конкретные буквы в одном из сообщений идут одна за другой в открытом тексте, то буквы, стоящие на тех же местах в каждом из остальных сообщений, соедиюпотся подобным же образом. Значит, они могут служить проверкой правильности первого предположения, подобно тому, как комбинации, которые диот лиа столбца в системе вертикальной перестановки, позволяют проверить, являются ли соседними две конкретные буквы из ~тих столбцов. К каждому из указанных двухбуквенных сочетаний можно добавить третью букву для образования триграммы и к д.
Если располагать не менее чем четырьмя сообщениями одинаковой длины, то можно с уверенностью гарантировать их искрьпие подобным образом. А лгоритмы шифрованы~ с использовачнем открытых ключей Алгоритмы шифрования с открытым ключом, также назыкасмые асимметричными алгоритмами шифрования, устроены ~ак, что ключ, используемый для шифрования сообщений, отлиьзстся от ключа, применяемого для их расшифрования. Более пи о, ключ распшфроваиия не может быть за обозримое время вычислен, исходя из ключа шифрования. Свое название алго- 139 ритмы с открытым ключом получили благодаря тому, что ключ шифрования не требуется держать в тайне.
Любой может им воспользоваться, чтобы зашифровать свое сообщение, но только обладатель соответствующего тайного ключа расшифрования будет в состоянии прочесть это пшфрованное сообщение. Ключ шифроваиия обычно называют открытым ключом, а ключ расшифрования — тайным ключом. Иногда тайный ключ называют также секретлым, однако чтобы избежать путаницы с симметричными алгоритмами, будем использовать термин пзайлый валия с открытым клочом Корреспондент В, желая послать конфиденциальное сообщешв М корреспонденту А, с помощью кл1оча я;„., вычисляет шифротексг С = Ех (М), который направляет по каналу связи корреспонденту А. Получив сообщение С, корреспондеит А применяет к нему преобраювание 1)кр, и вычисляет открытый текст М.
Открытый ключ не требуется сохранять в тайне. Необхо димо лишь обеспечить его аутентичность, что, как правило, сдс пать легче, чем обеспечить рассылку и сохранность тайных клю чей. Как упоминалось ранее, системы шифрования с открыты ми ключами осуществляют блочное шифрование, поэтому от крытый текст перед шифрованием разбивается иа блоки вы бранного размера, которые последовательно преобразуются тк ким же образом, как зто происходит при использовании блочнь го шифра в режиме простой замены. Асимметричные системы шифрования обеспечивают зкз чигельно меньшие скорости шифрования, нежели симметрв ~ иые, в силу чего они обычно используются ие столько для шиф роваиия сообщений, сколько для шифрования пересылаемы между корреспондентами ключей, которые затем используютг» в симметричных системах.
Рассмотрим в качестве примера систему шифрования с т крытым ключом КЕА (РША Ривест, Шимир, Адельман). 3ашифруем аббревиатуру КЕА иср е = 7. С помощью кагор а Е про тое с 'Р(л) ' иаир 7=41+3 4=31+1, 1 = 4 — 3.1 = 4-(7-4 1).1 — 4. И>2-7-137 Н = 2 — 71 = (480-768).2 7,1 У= 2, и= — 137.
П осколку -137 гя 343(пюй 480 Ы = 43 2401 1( д 480) 141 Система КЗА (по фа Адлеман — К' ~ авторов — Ривест, 1Еам и в ' ' и1ешап) была иастолцее время явля ыла предложена в 1978 г шифрования с откр ее известной системо является наиболее ытым ключом. Расом им й мотрим правило создания исп о фроваиия блока текста с фрования и расшиф П сть усть и =р 9 — целое число, е ~~~~, пр~дсшвимое виде произ из условия шнх простых чисел Р, д.
Выберем числа е и й е и' =- 1(лкм1 ср(л)), где ср(л) (Р-1) (9-1) — значение ерации ключей, ~алие, ибо их знания ", хранятся в строжайшей ключа — таиного. достаточно для в ычислеиия из открытого Пусть М вЂ” блок опуытого те гиий блок шиф опуытого текста и С вЂ” соответств ую- ф . Огда правила шифрования и = Ек (М) = М'(спой л), Ок (С) = С'(шос$ л). При этом выполняется правило О» (С) = М. 140 Теперь представим данное сообщение в виде последова- тельности чисел, содержащихся в интервале 0...52б. Для этого буквы К.,Б и А закоднруем пятимерными двоичными векторами, воспользовавшись двоичной записью их порядковых номеров в английском алфавите: К = 18 = (100 10), Б = 19 = (10011), А = 1 = (00001). Тогда КБА = (100101001100001).
Укладываясь в заданный интервал 0...52б, получаем следующее представление: КБА = (100101001)„(100001) = (М~ —— 297, Мз — — 33). Далее последовапльно шнфруем М~ и Мг. С, =Ек (М1) = М,'= 297' (пкм1 527) = 474. При этом мы воспользовались тем, что 297 ((297 )~ 297)(пкм1 527) = = ((200~(пюд 527) 297)(тод527), Сз = Ек~(Мз) = М2' — — 33' (шод 527) = 407.
В итоге получаем шифротекст: у~ — — 474, уз —— 407. КБА определяется именно сложностью разложения числа " на простые множители. В связи с этим нужно выбирать числа Р н Ч таким образом, чтобы задача разложения числа и была достаточно сложна в вычисшпельном плане. Для этого импользукпся следующие правила: 1)числа р и 9 должны быть досгаточно болыпими, не слишком сильно отличаться друг от друга и в то же время быть не слишком близкими друг другу; 2)числа р и д должны быть такими, чтобы наибольший общий делитель чисел р — 1 и 9 — 1 был неболыким; желательно. чтобы Нод(р — 1, я — 1) = 2; 3) р и у должны быть сильно простыми числамн (сильно простым называется такое простое число г, *по г + 1 имеет большой простой делитель, г — 1 имеет большой простой дели тель з, такой, что число з — 1 также обладает достаточно большим простым делителем).
При расшифровании нужно выполнить следующую последовательность действий. Во-первых, вычислить 1)к (С~) = (С1)~~(пкм1 527). Отметим, что при возведении в степень удобно воспользоваться тем, что 343 = 25б + б4 + 1б + 4 + 2 + 1. На основании этого представления получаем: 474 (пюд 527)=-174, 474'(пмм1 527) - =237, 474~(пюд 527) †= 307, 474'~(шод 527) — = 443, 474п(пюд 527) = 205, 474 (пюй 527) =- 392, 474'~(шод 527) =- 307, 474~~(хпод 527) = 443, в сил~ чего: 474~(пюд 527) - =(443.392.443237.174474)(пкм1 527) = 297. Аналогично: 407~~(пмм)527) = 33. Возвращаясь к буквенной записи, получаем после расшифрования КБА. Анализ криптостойкости системы КЯА. Атака на алгоритм КБА и заключается в разложении и на множители и сложность нахождения тайного ключа системы 142 В случае„когда не выполнено хотя бы одно из Указанных условий, имеются эффективные алгоритмы разложеник и на про етые множители.
В настоящее время самые большие простые числа Р и Ф которые удается разложить на множители известнымн метод~ мн, содержат в своей записи 140 десятичных знаков- ПоэгомУ согласно указанным рекомендациям, числа р и 9 в системе КБА должны содержать не менее 100 десятичных знаков. Следует подчеркнуть необходимость соблюдения осторожности в выборе модуля КБА (числа и) для каждого из кор респондентов сети. Известно, по, зная одну нз трех величин: Р д или <р(п), можно легко найти тайный ключ КБА. Также известно, что, зная тайную экспоненту расшифрования д. можно легко разложить модуль в на множители. В этом случае Удав~с~ посгронгь вероятностный алгоритм разложения п. Отсюда следует, что каждый корреспондент сети, в которой для шифрования ис пользуется система КБА, должен иметь свой уникальный мо" дуль.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
