Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 151
Текст из файла (страница 151)
т;~ Читателю остается доказать, что если С' — любое другое положительное целое число такое, что ~ ~ ~ = (г — 1) (пюг! п) для всех г, 1 < г < п, то С' > С. ° 842 ГЛАВА 22. Приложения теории чисел Например, чтобы найти Ьз, решаем сравнение 5055192724. Ьз = 4 (шог! 5044), что эквивалентно решению сравнения 1263798181 Ьз = 1 (пюг! 1261) или решению сравнения 22. Ьз = 1 (пюг! 1261). Следовательно, требуется найти Ьз и у такие, что 22Ьз + 1261у = 1. Используя алгоритм Евклида и обратную подстановку, приходим к результату 22 172+ ( — 3) 1261 = 1. Таким образом, М.Ь, Аг г=1 с= [[ = ]]6798505399334924]]„ 183904723300.
Далее используем С, 7' и 6 для хеширования йз = 7 6(йз) = 6(7) = ! 3183904723300 ! 1261 = ][25249046)8]] Обратные функции хеширования, введенные Яэшке, порождают большие целые числа. Вычислительные затраты, необходимые для реализации этого, должны быть соизмеримы с ресурсами, необходимыми для использования неминимальной и несовершенной функции хеширования: (1) максимально возможные затраты памяти, (2) возможность разрешения коллизий и (3) использование алгоритмов поиска для нахождения элементов данных в таблице. Объединяя последние несколько результатов, получаем следующую теорему.
ТЕОРЕМА 22.13. Пусть К = (йы)сг,...,6„) — множество, содержащее и различных положительных целых чисел; пусть 17 и Š— целые числа и пусть!'(х) = Хзх+ Š— функция, описанная в теоремах 22.8 22.10. Предположим также, что число С задано согласно части 2 теоремы 22.12, где т; = 7"(Ц). Тогда " =Е'"]]]. является минимальной совершенной функцией хеширования. ДОКАЗАТЕЛЬСТВО. Если т; = 7" (Ц), то из теоремы 22.12 следует, что 6(Й) = — =(! — 1) для 1 < г< п.
Следовательно, 6 является биекцией на (О, 1,..., (п — 1)). ПРИМЕР 22.14. Вернемся к примеру 22.!1, в котором К = (йыйг,бз,64) (3,6,7,12) и 7(х) = 180х+ 1. Было показано, что (1(йг),1(йг),)(йз) У("4)) = (541,1081,1261,2161). Пусть т, = )'(13). Числа т, являются попарно взаимно простыми и т, > и = 4. Используя теорему 22.!2, получаем следующую таблицу рдздЕП 22.3. Приложение: криптография 843 ° УПРАЖНЕНИЯ 1. Докажите, что если а и Ь вЂ” целые числа, для которых определены НОД(а, Ь) и НОД(а — Ь,а), то НОД(а, Ь) = НОД(а — Ь,а).
2. Для каждого из приведенных ниже множеств найдите многочлен 1(х) = Рх+1, который биективно отображает это множество на множество попарно взаимно простых чисел: а) (12,15,18,24); б) (5, 15, 20, 25) . 3. Пусть а,,аз,..., а„являются п различными положительными целыми числами. Докажите или опровергните утверждение: НОД(ам аз,..., а„) = 1 тогда и только тогда, когда НОД(а„а,) = 1 для всех г ~ У. 4.
В доказательстве теоремы 22.12 покажите, что а, = Х,п является наименьшим числом, кратным числу и, так что (1 — 1) гп, ( а, < 1 гп,. 5. Проверьте числа в таблице примера 22.14. 6. Для а) К = (12,15,18,24) из упражнения 2(а); б) К = (5,15,20,25) из упражнения 2(б). вычислите, используя теорему 22.12, целое число С и, соответственно, минимальную совершенную обратную функцию хеширования из теоремы 22.13. Проверьте тот факт, что 6(к,) = г — 1 при любом 1.
22.3. ПРИЛОЖЕНИЕ: КРИПТОГРАФИЯ Во всем мире правительства, компании и обычные люди хотят отправлять сообщения таким образом, чтобы прочитать их мог только адресат. Военные посылают приказы, банки передают информацию о движении капиталов, люди делают покупки, используя кредитные карточки. Сообщения, посланные по телефонным линиям, по радио, через спутник или через компьютерные сети могут быть перехвачены посторонними, возможно, враждебными лицами. Чтобы не допустить возможности получения информации или ее изменения посторонними лицами, сообщения изменены таким образом, что оригинал скрыт. Процесс засекречивания информации называется шифрованием или кодированием, а процесс рассекречивания — дешифровкой или декодированием.
Исходное сообщение называется открытым или незашифрованным текстом, а засекреченное сообщение — зашифрованным текстом (см. рис. 22.1). Конечно, и отправитель, и получатель сообщения должны согласовать процедуру шифрования и дешифровки. Эта процедура обычно состоит из общего метода и "ключа'*. Ключ обеспечивает специфическую информацию, что вместе с общим методом позволяет отправителю легко зашифровать, а получателю— легко дешифровать сообщение. Однако, в отсутствие ключа любой, перехвативший сообщение, не может за приемлемое время, используя самые мощные вычислительные ресурсы, получить исходный текст сообщения, даже зная общий метод шифрования. Например, восстановление сообщения при использовании самого быстродействующего компьютера потребовало бы, скажем, миллион лет или 844 ГЛАйд 22.
Приложения теории чисел Шифрование с С = К1М1 Зашифрованный текст Канал передачи М Исходное сообщение, или открытый текст Пер Дешифровка м = п(с) Криптоанализ М" Несанкционированное восстановление сообщения М Восстановление сообщения Рис. 22.1 М О Аг Е У 01001101г = 771о, 01001111г = 79~о, 01001110г = 78зо, 01001010г = 69го, 01011001г = 89го. Тогда М, могло бы соответствовать группам из двух букв, что дает "ЛХО" — Мг = 01001101 01001111г = 19791 ш, так что 0 < М, < п = 2гб = 65536. Конечно, полное сообщение можно было бы рассматривать как единую строку двоичных цифр, которые затем можно группировать в последовательность блоков любого удобного размера. Р.
Л. Райвест, А. Шамир и Л. Адлеман в работе Мегйог1 1ог ОЫа1п1пу 01р1а1 51упагигез алг1 Ри511с Кеу Сгур1озузгетз [98) представили общий метод исследования всех возможных сообщений на основе полного перебора, используя метод проб и ошибок. Попытка расшифровать открытый текст по зашифрованному тексту без использования общего метода или ключа называется криптоанализом. Рис.
22.1, на котором Š— функция шифрования, а  — функция дешифровки, иллюстрирует механизм поиска. Таким образом,Р(Е(М)) = М. Криптография— это наука, которая изучает методы шифрования и криптоанализа этих методов. Шифрование и дешифровка обычно выполняются компьютерами, поэтому сообщение М сначала преобразуется в целое число или в последовательность целых чисел с тем, чтобы появилась возможность преобразовывать эти числа, используя компьютерную арифметику. Таким образом, будем считать, что М вЂ” целое число. Сообщение в виде целого числа М обычно делят на блоки МММг, Мз,...,Мы так что каждый блок представляет собой целое число М„где 0 < М, < п, и число п выбрано заранее.
В таком случае шифрование выполняется блок за блоком как Е(Лг;) = С,, и дешифровка проводится аналогично относительно ах(Се) = М,. Например, можно следующим образом использовать 8-битовые компьютерные коды АВСП для каждого символа алфавита: РАЗДЕЛ 22.3. Приложение: криптография 845 шифрования, известный по фамилиям авторов как ЛБА-метод. Метод обладает многими хорошими характеристиками.
Пусть р и су — два достаточно больших числа, каждое из которых имеет, например, 100 разрядов, и пусть и = р. су. Для шифрования и дешифровки будут использованы два целых числа е и с1, которые связаны с числами р, су и и. Оба числа е и с1 будут определены ниже. Для шифровки сообщения М = М, вычислим с =е(м) = [[м ]]„, а для дешифровки вычислим м=Р(с) = [[с'Ц . Поскольку произведения М' и С~ приведены по модулю п, то зашифрованный текст и блоки исходного текста — это целые числа в диапазоне от 0 до (п — 1). Ключ для шифрования — пара целых чисел (п,е), и ключ для дешифровки— пара целых чисел (и, с)).
Сначала выберем в качестве с1 "большое" целое число, взаимно простое с произведением (р — 1) . (с1 — 1). Затем определим целое число е, 0 < е < и, т.е. единственное решение (теорема 3.65) сравнения с1 х = 1 (шос1 (р — 1)(су — 1)). Следовательно, учитывая соотношение ф(и) = ф(р)ф(су) = (р — 1)(су — 1), имеем д е = 1 (шос) ф(п)). ТЕОРЕМА 22.16. Если а) п = р су, где р и су — различные простые числа; б) ИОД(с!,ф(п)) = 1; в) с) е = 1 (шос) ф(и)); г) для 0 < У < п, определим функции Е(У) = [[У']]„и Р(,У) = ИУ'Ц тогда для 0 < .У < и Р(Е(,У)) = У и Е(Р(,У)) = Х ДОКАЗАТЕЛЬСТВО. Пусть 0 <,У < и. Из соотношения А вв В (гпос1 п) следует, что [[А]]„= [[В]]„.
Поэтому потому что по теореме 10.31 соотношения с1 е = 1 (шос1 ф(п)) и г = з (шос1 ф(п)) имеют место тогда и только тогда, когда х' = х' (шос) п). Результат Е(Р(,У)) = У может быть доказан аналогично. 846 ГЛЯВА 22. Приложения теории чисел ПРИМЕР 22.16. Предположим, что мы решили использовать 8-битовый код АЬСП для символов алфавита с размером блока, равным одному символу или букве. Нам потребуется и > 2а = 256.
Пусть р = 41 и 9 = 73, так что п = р д = 2993, ф(п) = 40 72 = 2880 = 2е Зз 5. Пусть 4 = 217 = 31.7, так что НОД(217, 2880) = 1. Используя алгоритм Евклида, в качестве решения сравнения 217х = 1 (щи 2880) получаем е = 1513. В таком случае, слово "МОГ7ЕУ", зашифрованное с использованием ЙЯА-метода с ключом (п,е) = (2993,1513), имеет вид, приведенный в следующей таблице Для эффективного вычисления М,' по модулю п был использован алгоритм из раздела 3.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
