Размещено на http://www.allbest.ru/

Введение

finereader шифр редактор

Ещё совсем недавно бумага была единственным носителем информации. Однако в эпоху глобальной компьютеризации, которую мы все переживаем, всё больше информации предоставляется в удобной для человека цифровой форме, облегчающей хранение, передачу, обучение. И теперь огромные книжные стеллажи могут поместиться на одном CD, на флэш-брелоке. Но как быть, например, с тем огромным наследием истории в виде монографий, книг, энциклопедий учебников? Как быть, если нужно оперативно передать документы на большое расстояние, отредактировать их, а они в наличии лишь на бумаге? Не набирать же всё это вручную? Эта проблема решается специализированным программным обеспечением, производящим оптическое распознавание текста. Теперь достаточно отсканировать/сфотографировать ваши документы и с помощью этого программного обеспечения произвести распознавание полученных образов и преобразовать в удобный для дальнейшей работы формат.

ABBYY FineReader - омнифонтовая система оптического распознавания текстов. Это означает, что она позволяет распознавать тексты, набранные практически любыми шрифтами, без предварительного обучения. Особенностью программы ABBYY FineReader является высокая точность распознавания и малая чувствительность к дефектам печати, что достигается благодаря применению технологии «целостного целенаправленного адаптивного распознавания».

OCR-продукт (optical character recognition - оптическое распознавание текста) FineReader снискал большую популярность не в только сфере бизнеса, но и среди индивидуальных пользователей. И в октябре 2007 года на прилавках появилась новая версия программного продукта - ABBYY FineReader 9.0. Для курсовой работы мы возьмем именно эту версию Professional Edition, предназначенную для индивидуального использования.

Цель:

1. Научиться пользоваться данной программой

2. Распознать данный текст и отредактировать

3. Сделать отчет по проделанной работе

1. Теоретическая часть

1.1 Возможности ABBYY FineReader 9.0 Professional Edition

ABBYY FineReader - омнифонтовая система оптического распознавания текстов. Это означает, что она позволяет распознавать тексты, набранные практически любыми шрифтами, без предварительного обучения. Особенностью программы ABBYY FineReader является высокая точность распознавания и малая чувствительность к дефектам печати, что достигается благодаря применению технологии «целостного целенаправленного адаптивного распознавания».

Процесс ввода документа в компьютер можно подразделить на два этапа:

1. Сканирование. На первом этапе сканер играет роль «глаза» Вашего компьютера: «просматривает» изображение и передает его компьютеру. При этом полученное изображение является не чем иным, как набором черных, белых или цветных точек, картинкой, которую невозможно отредактировать ни в одном текстовом редакторе.

2. Распознавание. Обработка изображения OCR-системой.

Остановимся на втором шаге более подробно.

Обработка изображения системой ABBYY FineReader включает в себя анализ графического изображения, переданного сканером, и распознавание каждого символа. Распознавание изображения осуществляется на основе технологии «целостного целенаправленного адаптивного распознавания».

· Целостность - объект описывается как целое с помощью значимых элементов и отношений между ними.

· Целенаправленность - распознавание строится как процесс выдвижения и целенаправленной проверки гипотез.

· Адаптивность - способность CR-системы к самообучению.

Но первое что бросается в глаза при открытии ABBYY FineReader 9.0 это, конечно же, переработанный интерфейс. Нельзя сказать, что в предыдущих версиях программы интерфейс был непонятен или сложен. Наоборот, стоит отметить, что у ABBYY всегда всё было хорошо в отношении пользовательских интерфейсов во всех программных продуктах. Что касается интерфейса FineReader 9.0, то можно сказать, что он отличается, однако остался простым и интуитивно понятным. При запуске появляется уже стандартное для большинства современных приложений меню в стиле «сделай всё одним щелчком», где пользователю предлагается без лишних трудностей выбрать один из стандартных сценариев.

Эти сценарии доступны также прямо из меню «Пуск». При выборе какого-либо сценария сразу же запускается программа и выполняет его. Очень удобно.

Слева расположена функциональная боковая панель, которая скрывается влево за пределы экрана по нажатию на «Свернуть» в её верхнем правом углу. Для возврата панели обратно надо просто щёлкнуть по левой границе окна программы. На панели отображаются листы распознаваемого документа и ход распознавания.

В предыдущих версиях программы можно было воспользоваться Мастерами сканирования, распознавания и другими. Их пиктограммы находились под основным меню программы вдоль всего окна. Можно было выбрать дополнительные режимы. Здесь же окно полностью расчищено для увеличения рабочей области, а все действия могут быть легко выполнены с помощью боковой панели и настроек. По умолчанию все открываемые файлы сразу анализируются и распознаются.

Как можно видеть на скриншоте, на рабочих полях находятся пиктограммы для быстрого доступа к более глубоким настройкам и параметрам работы, которые, несомненно, оценят профессионалы. Работа с документами может затрудняться лишь малым разрешением вашего монитора - комфортная работа с полями программы возможна при разрешении более 1 280 х 800.

Кроме всего прочего, появился новый диалог для работы с изображениями. В нём собраны все необходимые инструменты.



В диалоге открытия документов теперь возможен предпросмотр.

Разработчики хорошо поработали над новой версией. В её основу легла новая технология распознавания - ADRT (Adaptive Document Recognition Technology), адаптивная технология распознавания текстов. В основе данной технологии лежит принцип цельного распознавания документа, то есть документ анализируется и распознаётся как единое целое, а не постранично.

Данная технология выделяет во всём документе логическую структуру. Анализируются и определяются сноски, ссылки, колонтитулы, номера страниц, стили, шрифты. В итоге полученный документ, по заверениям разработчиков, становится таким, будто его создал человек. Редактирование полученных результатов не сводится к работе с каждой страницей отдельно - вы продолжаете работать с документом целиком.

ADRT обеспечивает даже объединение таблиц и параграфов, разбитых границей страницы. То есть теперь распознанная таблица на двух отсканированных страницах представляет собой одно целое, а не две отдельные таблицы.

Я решили это проверить и распознали PDF файл, содержащий большую таблицу. Ниже представлен скриншот из FineReader 9.0, где видно, что мы распознавали. Далее следует скриншот документа, который сохранился в формате Microsoft Word после распознавания.



Как можно видеть, таблица сохранилась как единый объект, так как часть таблицы со второй страницы исходного PDF примкнула к нижней части таблицы итогового документа в Word.

В немалой степени благодаря именно этой технологии, в девятой версии программы были улучшены характеристики точности сохранения оформления документов по сравнению с предыдущей версией: в отношении договоров и юридических документов - на 19%, в отношении книг - на 22%, газет и журналов - на 32%. Конечно, это данные внутренних исследований ABBYY, и они не могут претендовать на абсолютную объективность. Однако, поработав с программой, мы можем сказать точно: качество распознавания действительно улучшилось.

В новой версии программы возможна работа не только с Microsoft Word, но и с Microsoft Exсel и Microsoft Outlook.

FineReader 9.0 позволяет сохранять документы в форматах DOCX и XLSX, внедрённых корпорацией Microsoft в Office 2007. Кроме этих форматов, была дополнительно внедрена поддержка формата PDF/A.

Кроме перечисленных выше нововведений, безусловно, основных, в новую версию были включены и другие дополнения. Так, например, программа теперь сама определяет язык распознавания. Раньше приходилось переходить к настройкам и задавать язык (или комбинацию языков), на котором написан документ. Теперь же всё это автоматизировано. Кстати, количество языков распознавания увеличилось до 179.

В FineReader 9.0 была улучшена работа с юридической документацией - используется специальная технология распознавания юридических текстов, позволяющая снять точную копию документа. Благодаря данной технологии не придётся тщательно просматривать документ и выделять все подписи как картинку - теперь во время анализа подписи помечаются автоматически и копируются в распознанный документ без изменений.

Ну и конечно, FineReader 9.0, как любое серьёзное приложение в наше время, написана с использованием многопоточных технологий и оптимизирована под многоядерные процессоры.

1.2 Ход работы с пакетом ABBYY FineReader 9.0 Prof. Edition

· Открыть изображение:

1. Нажмите стрелку справа от кнопки 1-Сканировать и в локальном меню выберите пункт Открыть изображение. Внешний вид значка изменится; подпись Сканировать поменяется на Открыть.

2. В меню Файл выберите пункт PDF/Открыть изображение.

3. В Windows Explorer: щелкните правой кнопкой мыши на файле с изображением и в локальном меню выберите пункт Открыть с помощью ABBYY FineReader. Если на вашем компьютере уже открыт ABBYY FineReader, изображение будет добавлено в текущий пакет, в противном случае перед добавлением изображения в пакет автоматически запустится ABBYY FineReader с пакетом, с которым вы работали в последний раз.

4. В Microsoft Outlook и/или Windows Explorer: Нажмите левой кнопкой мыши на файле с изображением, которое вы хотите открыть, и не отпуская кнопки, перетащите его на свернутое окно программы ABBYY FineReader. Изображение будет добавлено в текущий пакет и открыто в окне Изображение.

В диалоге Открыть изображение выберите одно или несколько изображений. Выбранные изображения появятся в окне Пакет, и последнее из выбранных изображений откроется в окне Изображение и в окне Крупный план ABBYY FineReader, при этом копия изображения помещается в папку пакета.

1.2.1 Особенности открытия PDF-файлов

Создатель PDF-файла может ограничить доступ к своему файлу, например, защитить его паролем, установить запрет на открытие файла или извлечение из него текста и графики. При открытии подобных файлов ABBYY FineReader будет запрашивать пароль, чтобы обеспечить защиту авторских прав создателя файла.

Анализ макета страницы

Прежде, чем приступить к распознаванию, программа должна знать, какие участки изображения надо распознавать. Для этого проводится анализ макета страницы, во время которого выделяются блоки с текстом, картинки, таблицы и штрих-коды.

В этой главе вы узнаете, когда может потребоваться ручной анализ макета страницы, какие типы блоков могут быть размечены на изображении, как отредактировать полученные в результате автоматического анализа блоки, а также, как упростить процесс анализа, используя шаблоны блоков.

1.2.2 Распознавание

Задача распознавания состоит в том, чтобы преобразовать отсканированное изображение в текст, сохранив при этом оформление страницы. Прежде чем приступить к распознаванию текста, необходимо установить язык распознавания. В этой главе описываются этот и другие параметры распознавания и приводятся описание ситуаций, в которых они используются.

Общая информация о распознавании

Внимание! Перед запуском распознавания проверьте установленные опции: язык распознавания, режим распознавания и тип печати распознаваемого текста.

Вы можете:

1. Распознать блок или несколько блоков, выделенных на изображении.

2. Распознать открытую страницу или все страницы, выделенные в окне Пакет.

3. Распознать все нераспознанные страницы пакета.

4. Распознать все страницы в фоновом режиме. В этом режиме возможно распознавание с одновременным редактированием уже распознанных страниц.

5. Распознать страницы в режиме распознавания с обучением. Данный режим применяется в основном для распознавания текстов, использующих декоративные шрифты, или для распознавания большого объема (более 100 страниц) документов низкого качества печати.

6. Распознать страницы одного пакета на нескольких компьютерах одновременно.

Чтобы запустить распознавание:

· Нажмите кнопку 2-Распознать на панели Scan&Read.

· В меню Процесс выберите нужный вам пункт:

Распознать - чтобы распознать открытую страницу или все страницы, выделенные в окне Пакет;

Распознать все - чтобы распознать все нераспознанные страницы пакета;

Распознать блок - чтобы распознать один или несколько блоков, выделенных на изображении;

Запустить фоновое распознавание - чтобы запустить распознавание в фоновом режиме.

Замечание. При распознавании уже распознанной страницы перераспознаются только отредактированные и добавленные блоки.

1.2.3 Сохранение во внешние редакторы и форматы

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

1.2.4 Общая информация по сохранению распознанного текста

Вы можете:

· Сохранить распознанный текст, используя Мастер сохранения результатов.

· Сохранить открытую или выделенные в окне Пакет страницы в файл или во внешнее приложение.

· Сохранить все страницы пакета в файл или во внешнее приложение.

· Сохранить изображение страницы.

Чтобы сохранить распознанный текст:

· Нажмите стрелку справа от кнопки 4-Сохранить и в локальном меню выберите необходимый пункт.

Замечание. При сохранении нескольких страниц сначала выделите их в окне Пакет.

После того как вы экспортировали распознанный текст в выбранное вами приложение, отправили его по электронной почте, передали в буфер или сохранили в файл, «информация» об этом действии отразится на значке кнопки 4-Сохранить. Поэтому для того, чтобы повторить ту же операцию для другого изображения, вам достаточно нажать на этот значок.

2. Практическая часть

Мы начинаем изложение основ криптографии с классической задачи передачи секретных сообщений от некоторого отправителя А к получателю В.

Отправитель сообщений и их получатель могут быть физическими лицами, организациями, какими-либо техническими системами. Иногда об А и В говорят как об абонентах некоторой сети, о пользователях некоторой компьютерной системы или, еще более формально, как об абстрактных "сторонах" (англоязычный термин "party") или "сущностях" (entity), участвующих в информационном взаимодействии. Но чаще бывает удобно отождествлять участников обмена с некоторыми людьми и заменить формальные обозначения А и В на Алиса и Боб.

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

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

Перед тем как передать сообщение по открытому каналу связи от А к В , А шифрует сообщение, а В, приняв зашифрованное сообщение, дешифрует его, восстанавливая исходный текст. Важно то, что в рассматриваемой нами в этой главе задаче Алиса и Боб могут договариваться об используемом ими шифре (или, скорее, о некоторых его параметрах) не по открытому каналу, а по специальному "закрытому" каналу, недоступному для прослушивания противником. Такой "закрытый канал" может быть организован при помощи курьеров, или же Алиса и Боб могут обмениваться шифрами во время личной встречи и т.п. При этом надо учитывать, что обычно организация такого закрытого канала и передача по нему сообщений слишком дороги по сравнению с открытым каналом и (или) закрытый канал не может быть использован в любое время. Например, курьерская почта намного дороже обычной, передача сообщений с ее помощью происходит намного медленнее, чем, скажем, по телеграфу, да и использовать ее можно не в любое время суток и не в любой ситуации.

Чтобы быть более конкретными, рассмотрим пример шифра. Так как проблема шифрования сообщений возникла еще в глубокой древности, некоторые шифры связаны с именами известных исторических личностей и в качестве первых примеров обычно используют именно такие шифры. Мы также будем придерживаться этой традиции. Начнем с известного шифра Гая Юлия Цезаря, адаптировав его к русскому языку. В этом шифре каждая буква сообщения заменяется на другую, номер которой в алфавите на три больше. Например, А заменяется на Г, Б на Д и т.д. Три последние буквы русского алфавита -- Э, Ю, Я -- шифруются буквами А, Б, В соответственно. Например, слово ПЕРЕМЕНА после применения к нему шифра Цезаря превращается в ТИУИПИРГ (если исключить букву Е).

Последующие римские цезари модифицировали шифр, используя смещение в алфавите на четыре, пять и более букв. Мы можем описать их шифр в общем виде, если пронумеруем (закодируем) буквы русского алфавита числами от 0 до 31 (исключив букву Е).

Тогда правило шифрования запишется следующим образом:

с = (т + к) mod 32, (1.1)

где тис -- номера букв соответственно сообщения и шифротекста, а к -- некоторое целое число, называемое ключом шифра (в рассмотренном выше шифре Цезаря к = 3). (Здесь и в дальнейшем a mod b обозначает остаток от деления целого числа а на целое число b, причем остаток берется из множества {0,1,-1} . Например, 13 mod 5 = 3.)

Чтобы дешифровать зашифрованный текст, нужно применить "обратный" алгоритм

m = (с - к) mod 32. (1.2)

Можно представить себе ситуацию, когда источник и получатель сообщений договорились использовать шифр (1.1), но для того, чтобы усложнить задачу противника, решили иногда менять ключ шифра. Для этого Алиса каким-либо образом генерирует число к, передает его Бобу по закрытому каналу связи, и после этого они обмениваются сообщениями, зашифрованными с помощью этого ключа к. Замену ключа можно проводить, например, перед каждым сеансом связи или после передачи фиксированного числа букв (скажем, каждую десятку символов шифровать со своим к) и т.п. В таком случае говорят, что ключ порождается источником ключа. Схема рассмотренной криптосистемы с секретным ключом приведена на рис. 1.1.



Обратимся теперь к анализу действий противника, пытающегося расшифровать сообщение и узнать секретный ключ, иными словами, вскрыть, или взломать шифр. Каждая попытка вскрытия шифра называется атакой на шифр (или на криптосистему). В криптографии принято считать, что противник может знать использованный алгоритм шифрования, характер передаваемых сообщений и перехваченный шифротекст, но не знает секретный ключ. Это называется "правилом Керкхоффса" в честь ученого, впервые сформулировавшего основные требования к шифрам (A. Kerckhoffs, 1883). Иногда это правило, кажется "перестраховкой", но такая "перестраховка" отнюдь не лишняя, если, скажем, передается распоряжение о переводе миллиона долларов с одного счета на другой.

В нашем примере Ева знает, что шифр был построен в соответствии с (1.1), что исходное сообщение было на русском языке и что был передан шифротекст ТИУИПИРГ, но ключ Еве не известен.

Наиболее очевидная попытка расшифровки -- последовательный перебор всех возможных ключей (это так называемый метод "грубой силы"). Итак, Ева перебирает последовательно все возможные ключи к = 1, 2, ..., подставляя их в алгоритм дешифрования и оценивая получающиеся результаты. Попробуем и мы использовать этот метод. Результаты дешифрования по (1.2) при разных ключах и шифротексте ТИУИПИРГ сведены в табл. 1.1. В большинстве случаев нам достаточно было расшифровать две-три буквы, чтобы отвергнуть соответствующий ключ (из-за отсутствия слова в русском языке, начинающегося с такого фрагмента).

Таблица 1.1: Расшифровка слова ТИУИПИРГ путем перебора ключей

к	т	к	т	к	771	к	т
1	СЗТ	9	ИЯ	17	БЧ	25	ЩП
2	РЖС	10	ИЮЙ	18	АЦБ	26	ШОЩ
3	ПЕРЕМЕНА	11	ЗЭИ	19	ЯХА	27	ЧН
4	ОДП	12	ЖЬ	20	ЮФ	28	ЦМ
5	НГ	13	ЕЫ	21	ЭУ	29	ХЛЦ
6	MB	14	ДЪ	22	Ь	30	ФК
7	ЛБМ	15	ГЩ	23	Ы	31	УЙ
8	КАЛАЗ	16	ВШГ	24	Ъ	32	ТИУИПИРГ

Из табл. 1.1 мы видим, что был использован ключ к = 3 и зашифровано сообщение ПЕРЕМЕНА. Причем для того, чтобы проверить остальные возможные значения ключа, нам не требовалось дешифровать все восемь букв, а в большинстве случаев после анализа двух-трех букв ключ отвергался (только при к = 8 надо было дешифровать пять букв, зато при к = 22,23,24 хватало и одной, так как в русском языке нет слов, начинающихся с Ь, Ъ, Ы).

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

В чем же причины нестойкости рассмотренного шифра и как можно было бы увеличить его стойкость? Рассмотрим еще один пример. Алиса спрятала, важные документы в ячейке камеры хранения, снабженной пятидекадным кодовым замком. Теперь она хотела бы сообщить Бобу комбинацию цифр, открывающую ячейку. Она решила использовать аналог шифра Цезаря, адаптированный к алфавиту, состоящему из десятичных цифр:

с= (т + к) mod 10. (1.3)

Допустим, она послала Бобу шифротекст 26047. Ева пытается расшифровать его, последовательно перебирая все возможные ключи. Результаты ее попыток сведены в табл. 1.2.

Таблица 1.2: Расшифровка сообщения 26047 путем перебора ключей

к	т	к	m
1	15936	6	60481
2	04825	7	59370
3	93714	8	48269
4	82603	9	37158
5	71592	0	26047

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

В первом примере сообщение -- текст на русском языке, поэтому оно подчиняется многочисленным правилам, различные буквы и их сочетания имеют различные вероятности и, в частности, многие наборы букв запрещены. (Это свойство называется избыточностью текста). Поэтому-то и удалось легко найти ключ и дешифровать сообщение, т.е. избыточность позволила "взломать" шифр. В противоположность этому, во втором примере все комбинации цифр допустимы. "Язык" кодового замка не содержит избыточности. Поэтому даже простой шифр, примененный к сообщениям этого языка, становится нескрываемым. В классической работе К. Шеннона [16] построена глубокая и изящная теория шифров с секретным ключом и, в частности, предложена "правильная" количественная мера избыточности. Мы кратко коснемся этих вопросов в главе 7, а в главе 8 будут описаны современные шифры с секретным ключом.

Описанная в приведенных примерах атака называется атакой по шифротексту. Но часто на шифр может быть проведена атака по известному тексту. Это происходит, если Ева получает в свое распоряжение какие-либо открытые тексты, соответствующие раннее переданным шифровкам. Сопоставляя пары "текст-шифротекст", Ева пытается узнать секретный ключ, чтобы с его помощью дешифровать все последующие сообщения от Алисы к Бобу.

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

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

Итак, мы познакомились с основными героями криптографии -- Алисой, Бобом и Евой и с важными понятиями этой науки -- шифром, ключом, атакой, открытым и защищенным каналом. Заметим, что с последним понятием связан один интригующий факт -- возможно построение надежных криптосистем без защищенного канала! В таких системах Алиса и Боб вычисляют секретный ключ так, что Ева не может этого сделать. Это открытие было сделано в основополагающих работах Диффи, Хеллмана и Меркля (см., например, [20]) в 1976 году и открыло новую эру в современной криптографии. Большая часть этой книги будет связана именно с такими системами, называемыми схемами с открытым, или несимметричным ключом.

2.1 Предыстория и основные идеи

Рассмотрим три задачи, решение которых поможет нам лучше понять идеи и методы криптографии с открытым ключом. Все эти задачи имеют важное практическое значение.

Первая задача -- хранение паролей в компьютере. Мы знаем, что каждый пользователь в сети имеет свой секретный пароль. При входе в сеть пользователь указывает свое имя (несекретное) и затем вводит пароль. Проблема состоит в следующем: если хранить пароль на диске компьютера, то Ева может прочитать его, а затем использовать для несанкционированного доступа (особенно легко это сделать, если Ева работает системным администратором этой сети). Поэтому необходимо организовать хранение паролей в компьютере так, чтобы такой "взлом" был невозможен.

Вторая задача возникла с появлением радиолокаторов и системы ПВО. При пересечении самолетом границы радиолокатор спрашивает пароль. Если пароль верный, то самолет "свой", в противном случае -- "чужой". Здесь возникает такая проблема: так как пароль должен передаваться по открытому каналу (воздушной среде), то противник может прослушивать все переговоры и узнавать правильный пароль. Затем "чужой" самолет в случае запроса повторит перехваченный ранее "правильный" пароль в качестве ответа локатору и будет пропущен.

Третья задача похожа на предыдущую и возникает в компьютерных сетях с удаленным доступом, например, при взаимодействии банка и клиента. Обычно в начале сеанса банк запрашивает у клиента имя, а затем секретный пароль, но Ева может узнать пароль, так как линия связи открытая.

Сегодня все эти проблемы решаются с использованием криптографических методов. Решение всех этих задач основано на важном понятии односторонней функции (one-way function).

Определение 2.1. Пусть дана функция

y = f(x), (2.1)

определенная на конечном множестве X (хX), для которой существует обратная функция

х = (у). (2.2)

Функция называется односторонней, если вычисление по (2.1) -- простая задача, требующая немного времени, а вычисление по (2.2) -- задача сложная, требующая привлечения массы вычислительных ресурсов, например, 106 - 1010 лет работы суперкомпьютера.

Данное определение, безусловно, неформально. Строгое определение односторонней функции может быть найдено в [24, 26], но для наших целей достаточно и вышеприведенного.

В качестве примера односторонней функции рассмотрим следующую:

y = ах mod p, (2.3)

где р -- простое число (т.е. такое, которое делится без остатка только на себя и на единицу), а х -- целое число из множества {1, 2,... ,р-- 1} . Обратная функция обозначается

x = loga у mod р (2.4)

и называется дискретным логарифмом.

Для того чтобы обеспечить трудность вычисления по (2.4) при использовании лучших современных компьютеров, в настоящее время используются числа размером более 512 бит. На практике часто применяются и другие односторонние функции, например, так называемые хеш-функции (они будут рассмотрены в главе 8), оперирующие с существенно более короткими числами порядка 60-120 бит.

Сначала мы покажем, что вычисление по (2.3) может быть выполнено достаточно быстро. Начнем с примера вычисления числа a16 mod p. Мы можем записать

a16mod p = ( ((a2)2)2 ) mod p,

т.е.значение данной функции вычисляется всего за 4 операции умножения вместо 15 при "наивном" варианте а· а· ...· а. На этом основан общий алгоритм.

Для описания алгоритма введем величину t = [log2x] -- целую часть log2 х (далее все логарифмы будут двоичные, поэтому в дальнейшем мы не будем писать индекс 2). Вычисляем числа ряда

a, а2, а4, а8, а2 mod р. (2.5)

В ряду (2.5) каждое число получается путем умножения предыдущего числа самого на себя по модулю р. Запишем показатель степени х в двоичной системе счисления:

x= (xtxt-1 ...x1x0)2 (2.6)

Тогда число у = ах mod p может быть вычислено как

(все вычисления проводятся по модулю р).

Пример2.1. Пусть требуется вычислить 3100 mod 7. Имеем t = [log 100] = 6 . Вычисляем числа ряда (2.5):

а а2 а4 а8 о16 а32 а64

3 2 4 2 4 2 4

Записываем показатель в двоичной системе счисления: 100=(1100100)2.

Проводим вычисления по формуле (2.6):

а64 а32 а4

4· 2· 1 · 1 · 4 · 1 · 1 = 4

Нам потребовалось всего 8 операций умножения.

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

Алгоритм 2.1 Возведение в степень (справа-налево)

ВХОД: Целые числа а, х = (xtxt-1 …x0)2, р.

ВЫХОД: Число у = ax mod р.

у <-- 1, s <-- а.

FOR г = 0,1,...,t DO

IF xi = 1 THEN y<--y· s mod p;

s <-- s· s mod p.

5. RETURN y.

Чтобы показать, что по представленному алгоритму действительно вычисляется у согласно (2.6), запишем степени переменных после каждой итерации цикла. Пусть х = 100 = (1100100)2, как в примере 2.1.

i:	0	1	2	3	4	5	6
Xi.	0	0	1	0	0	1	1
У:	1	1	a4	a4	a4	aye	am
s:	aa	a4	a8			a64

В некоторых ситуациях более эффективным оказывается следующий алгоритм, в котором биты показателя степени, просматриваются слева-направо, т.е. от старшего к младшему.

Алгоритм 2.2 Возведение в степень (слева-направо)

ВХОД: Целые числа а, х = (xtxt-1 …x0)2, р.

ВЫХОД: Число у = ах mod р.

у <-- 1

FOR i = t,t-1,...,0 DO

y<--y· y mod p;

IF xi = 1 THEN у <-- у· a mod p.

5. RETURN y.

Чтобы убедиться в том, что алгоритм 2.2 вычисляет то же самое, что и алгоритм 2.1, запишем степени переменной у после каждой итерации цикла для х -- 100 .

gi: 6	5	4	3	2	1	0
xi: 1	1	0	0	1	0	0
у: а	а3	a6	а12	a25	a50	a100

В общем случае справедливо следующее

Утверждение 2.1 (о сложности вычислений (2.3)). Количество операций умножения при вычислении по (2.3) не превосходит 2logх.

Доказательство. Для вычисления чисел ряда (2.5) требуется
t умножений, для вычисления у по (2.6) не более чем t умножений
(см. пример 2.1). Из условия t = [log x] , учитывая, что [log x] < log x, делаем вывод о справедливости доказываемого утверждения.

Замечание. Как будет показано в дальнейшем, при возведении в степень по модулю р имеет смысл использовать только показатели х < р. В этом случае мы можем сказать, что количество операций умножения при вычислении (2.3) не превосходит 2 log р.

Важно отметить, что столь же эффективные алгоритмы вычисления обратной функции (2.4) неизвестны. Один из методов вычисления (2.4), известный под названием "шаг младенца, шаг великана", будет подробно описан в разделе 3.2. Этот метод требует порядка операций.

Покажем, что при больших р функция (2.3) действительно односторонняя. Пусть, например, для вычисления обратной функции используется метод "шаг младенца, шаг великана". Получаем следующий результат (таблица 2.1).

Таблица 2.1: Количество умножений для вычисления прямой и обратной функции

Количество десятичных знаков в записи р	Вычисление (2.3)	Вычисление (2.4)
	(21og p умножений)	( умножений)
12	2 * 40 = 80	2 * 106
60	2 * 200 = 400	2 * 1030
90	2 * 300 = 600	2 * 1045

Мы видим, что если использовать модули, состоящие из 50-100 десятичных цифр, то "прямая" функция вычисляется быстро, а обратная практически не вычислима. Рассмотрим, например, суперкомпьютер, который умножает два 90-значных числа за 10-14 сек. (для современных компьютеров это пока не доступно). Для вычисления (2.3) такому компьютеру потребуется

а для вычисления (2.4) --

т.е. более 10 22 лет. Мы видим, что вычисление обратных функций практически невозможно при длине чисел порядка 100 десятичных цифр, и использование параллельных вычислений и компьютерных сетей существенно не меняет ситуацию. Таким образом, можно утверждать, что функция (2.3) действительно односторонняя, но с оговоркой. Никем не доказано, что обратная функция (2.4) не может быть вычислена столь же быстро, как и "прямая".

Используем функцию (2.3) для решения всех трех задач, описанных в начале данного раздела, не забывая, однако, что точно так же может быть использована и любая другая односторонняя функция.

Начнем с хранения паролей в памяти компьютера. Решение задачи основано на том, что пароли вообще не хранятся! Точнее, при регистрации в сети пользователь набирает свое имя и пароль; пусть, например, его имя -- "фрукт", а пароль -- "абрикос". Компьютер рассматривает слово "абрикос" как двоичную запись числа х и вычисляет (2.3), где а и р--два несекретные числа, возможно даже, всем известные. После этого в памяти компьютера заводится пара "имя, у ", где у вычислено по (2.3) при х = "пароль". При всех дальнейших входах этого пользователя после ввода пары ("фрукт", "абрикос"), компьютер вычисляет по (2.3) новое значение yнов с х = "абрикос" и сравнивает с хранящимся в памяти ранее вычисленным значением у Если унов совпадает с хранящимся в памяти у, соответствующим данному имени, то это законный пользователь. В противном случае это Ева.

Ева может попытаться найти х по у. Однако мы видели, что уже при 90-значных числах для этого потребуется более чем 1022 лет. Таким образом, представленная система хранения пароля весьма надежна и используется во многих реальных операционных системах.

Рассмотрим решение второй задачи (ПВО и самолет). Можно использовать следующий метод. Каждому "своему" самолету присваивается секретное имя, известное системе ПВО и летчику, точнее, бортовому компьютеру. Пусть, например, одному из самолетов присвоено секретное имя СОКОЛ, и этот самолет приближается к границе 10 сентября 2002 года в 12 час.45 мин. Тогда перед приближением к границе бортовой компьютер самолета формирует слово

СОКОЛ 02 09 10 12 45

(имя год месяц день часы минуты).

Другими словами, компьютер на самолете и станция ПВО прибавляют к секретному слову сведения о текущем времени и, рассматривая полученное слово как число х, вычисляют у = ax mod р, где аирне секретны. Затем самолет сообщает число у станции ПВО. Станция сравнивает вычисленное ею число у с полученным от самолета. Если вычисленное и полученное значения совпали, то самолет признается как "свой".

Противник не может взломать эту систему. Действительно, с одной стороны, он не знает секретного слова СОКОЛ и не может найти его по у, так как вычисление х по у занимает, скажем, 1022 лет. С другой стороны, он не может просто скопировать у и использовать его в качестве ответа в будущем, так как время пересечения границы никогда не повторяется и последующие значения у будут отличаться от первоначального.

Рассмотренный вариант решения "задачи ПВО" требует точной синхронизации часов в самолете и в локаторе. Эта проблема достаточно легко решается. Например, служба навигации постоянно передает метки времени в открытом виде (время не секретно), и все самолеты и локаторы используют эти метки для синхронизации своих часов. Но есть более тонкие проблемы. Метка времени добавляется в слово х для того, чтобы все вычисляемые значения у были различны и противник не мог их повторно использовать. Однако противник может попытаться мгновенно повторить у в пределах текущей минуты. Как предотвратить эту возможность? Это первый вопрос. Другое затруднение возникает в ситуации, когда самолет посылает число у в конце 45-й минуты, а локатор принимает его в начале 46-й. Мы предоставляем читателю возможность самостоятельно предложить вариант решения этих проблем.

Другой способ решения "задачи ПВО" возможен, если мы будем использовать дополнительный открытый канал передачи данных от локатора к самолету. Как и выше, каждый "свой" самолет и локатор знают секретное слово (типа СОКОЛ), которое не заменяется. Обнаружив цель, локатор посылает ей случайно сгенерированное число а ("вызов"). Самолет вычисляет у = ах mod р, где х -- секретное слово ("СОКОЛ"), и сообщает число у локатору. Локатор воспроизводит те же вычисления и сравнивает вычисленное у и принятое. В этой схеме не нужно синхронизировать часы, но, как и ранее, противник не может повторить число у, так как локатор всякий раз посылает разные вызовы (a). Интересно, что эта задача, по-видимому, была исторически первой, при решении которой использовались односторонние функции.

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

2.2 Первая система с открытым ключом -- система Диффи-Хеллмана

Данная криптосистема была открыта в середине 70-х годов Диффи (Whitfield Diffie) и Хеллманом (Martin Hellman) и привела к настоящей революции в криптографии и ее практических применениях. Это первая система, которая позволяла защищать информацию без использования секретных ключей, передаваемых по защищенным каналам. Для того чтобы продемонстрировать одну из схем применения таких систем, рассмотрим сеть связи с N пользователями, где N -- большое число. Пусть мы хотим организовать секретную связь для каждой пары из них. Если мы будем использовать обычную систему распределения секретных ключей, то каждая пара абонентов должна быть снабжена своим секретным ключом, т.е. всего потребуется

ключей.

Если абонентов 100, то требуется 5000 ключей, если же абонентов 104 , то ключей должно быть 5 * 107 . Мы видим, что при большом числе абонентов задача снабжения секретными ключами очень трудоемка.

Диффи и Хеллман решили эту задачу за счет открытого распространения и вычисления ключей. Перейдем к описанию предложенной ими системы.

Пусть строится система связи для абонентов А, В, С,... .У каждого абонента есть своя секретная и открытая информация. Для организации этой системы выбирается большое простое число р и некоторое число g, 1 < g < р--1, такое, что все числа, из множества {1,2,….,р--1} могут быть представлены как различные степени g mod р (известны различные подходы для нахождения таких чисел g, один из них будет представлен ниже). Числа р и g известны всем абонентам.

Абоненты выбирают большие числа Хa,Хb,Хc которые хранят в секрете (обычно такой выбор рекомендуется проводить случайно, используя датчики случайных чисел). Каждый абонент вычисляет соответствующее число Y , которое открыто, передается другим абонентам,

В результате получаем следующую таблицу.

Таблица 2.2: Ключи пользователей в системе Диффи-Хеллмана

Абонент	Секретный ключ	Открытый ключ
А	ХА	YA
В	ХB	YB
С	ХС	YC

Допустим, абонент А решил организовать сеанс связи с В при этом обоим абонентам доступна открытая информация из таблицы 2.2 Абонент А сообщает, что он хочет передать данные абоненту В . Абонент А вычисляет величину

(никто другой кроме А этого сделать не может, так как число ХА секретно). Абонент В вычисляет число

Утверждение 2.2. ZAB = ZBA .

(Здесь первое равенство следует из (2.8), второе и четвертая - из (2.7)
последнее -- из (2.9).)

Отметим главные свойства системы:

абоненты А и В получили одно и то же число Z = ZAB = ZBA , которое не передавалось по открытой линии связи;

Ева не знает секретных чисел ХA, ХB,…., поэтому не может вычислить число ZAB (вообще говоря, она могла бы попытаться найти секретное число ХA по YA (см. (2.7)), однако при больших р это практически невозможно (требуются миллионы лет)).

Теперь абоненты А и В могут использовать ZAB в качестве секретного ключа для шифрования и дешифрования данных. Таким же образом любая пара абонентов может вычислить секретный ключ, известный только им.

Выбор числа g при произвольно заданном р может оказаться трудной задачей, связанной с разложением на простые множители числа р -- 1 . Дело в том, что для обеспечения высокой стойкости рассмотренной системы число р -- 1 должно обязательно содержать большой простой множитель (в противном случае алгоритм Полига-Хеллмана, описанный, например, в [26], быстро вычисляет дискретный логарифм). Поэтому часто рекомендуют использовать следующий подход. Простое число р выбирается таким, чтобы выполнялось равенство

p = 2q+ 1,

где q -- также простое число. Тогда в качестве g можно взять любое число, для которого справедливы неравенства

1 < g < р -- 1 и gq mod р ? 1.

Пример 2.2. Пусть р = 23 = 2 · 11 + 1 (q = 11). Выберем параметр g. Попробуем взять g = 3 . Проверим: 311 mod 23 = 1 и значит, такое g не подходит. Возьмем g = 5. Проверим: 511 mod 23 = 22 ? 1. Итак, мы выбрали параметры для системы Диффи-Хеллмана: р = 23, д = 5 . Теперь каждый абонент выбирает секретное число и вычисляет соответствующее ему открытое число. Пусть ХA = 7, ХB = 13. Вычисляем YA = 57 mod 23 = 17, YB = 513 mod 23 = 21. Пусть А и В решили сформировать общий секретный ключ. Для этого А вычисляет ZAB = 217 mod 23 = 10, а В вычисляет ZBA = 1713 mod 23 = 10. Теперь они имеют общий ключ 10, который не передавался по каналу связи.

2.3 Элементы теории чисел

Многие криптографические алгоритмы основаны на результатах классической теории чисел. Мы рассмотрим необходимый минимум из этой теории. Классические теоремы Ферма, Эйлера и ряд других результатов из теории чисел будут даны без доказательств, которые могут быть найдены практически в любом учебнике по теории чисел (см., например, [3]). Читатели, знакомые с теорией чисел, могут непосредственно перейти к разделу 2.4.

Определение 2.2. Целое положительное число р называется простым, если оно не делится ни на какое другое число, кроме самого себя и единицы.

Пример 2.3. Числа 11, 23 -- простые; числа 27, 33 -- составные (27 делится на 3 и на 9, 33 делится на 3 и на 11).

Теорема 2.3 (основная теорема арифметики). Любое целое
положительное число может быть представлено в виде произведения
простых чисел, причем единственным образом.

Пример 2.4. 27 = 3 * 3 * 3, 33 = 3 * 11.

Определение 2.3. Два числа называются взаимно простыми, если они не имеют ни одного общего делителя кроме единицы.

Пример 2.5. Числа 27 и 28 взаимно просты (у них нет общих делителей кроме единицы), числа 27 и 33 -- нет (у них есть общий делитель 3).

Определение 2.4 (функция Эйлера). Пусть дано целое число N > 1. Значение функции Эйлера ц (N) равно количеству чисел в ряду 1,2,3,. ..,N-- 1, взаимно простых с N.

Утверждение 2.4. Если р простое число, то ц (р) = р - 1.

Доказательство. В ряду 1,2,3,...,р-1 все числа взаимно
просты с р, так как р -- простое число и по определению не делится
ни на какое другое число.

Утверждение 2.5. Пусть р и q -- два различных простых числа и p<q. Тогда ц (pq) = (р - 1) (q- 1).

Доказательство. Выпишем ряд

1,2,...,р-1,р,р + 1,…q,…,2р,…,2q,...,( q-1)р,…,(р-l)q,…,p(q- 1)

и вычеркнем в нем все не взаимно простые числа. Окажутся вычеркнутыми числа

р,2р,3р,…,(q- 1)р и q,2q,3q,… , (р -1)q.

Всего будет вычеркнуто (q - 1) + (р - 1) чисел, а останется pq-(p - 1)-
(q - 1) = pq - q - р + 1 = (р - 1) (q - 1) чисел.

Теорема 2.6 (Ферма). Пусть р -- простое число и 0 < а < р. Тогда

ap-1 mod р = 1.

При мер 2.7. р = 13,а = 2;

212 mod 13 = (22)2 * ((22)2)2 mod 13 = 3 · 9 mod 13 = 1,

1010 mod 11 = 102 * ((102)2)2 mod 11 = 1 * 1 = 1.

Теорема Ферма является частным случаем теоремы Эйлера, когда 6 -- простое число.

Пример 2.8.

ц(12) =4,

54 mod 12 = (52)2 mod 12 = (l2)2 mod 12 = 1.

ц (21) = 2 * 6 = 12,

212 mod 21 = 24 * (24)2 mod 21 = 16-4 mod 21 = 1.

Нам понадобится еще одна теорема, близкая к теореме Эйлера.

Теорема 2.8. Если р и q -- простые числа, р ? q и к -- произвольное целое число, то

Пример 2.9. Возьмем р = 5 , q = 7 . Тогда pq = 35 , а функция Эйлера -- ц (35) = 4 * 6 = 24. Рассмотрим случай к = 2, т.е. будем возводить числа в степень 2 * 24 + 1 = 49 . Получим

949 mod 35 = 9,. 2349 mod 35 = 23.

Это не удивительно, так как каждое из чисел 9 и 23 взаимно просто с модулем 35, и по теореме Эйлера 924 mod 35 = 1, 2324 mod 35 = 1. Однако теорема 2.8 остается верной и для следующих чисел:

1049 mod 35 = 10 , 2849 mod 35 = 28,

в то время как теорема Эйлера для них не применима (каждое из чисел 10 и 28 не взаимно просто с модулем 35, 1024 mod 35 = 15 , 2824 mod 35 = 21).

Определение 2.5. Пусть а и b -- два целых положительных числа. Наибольший общий делитель чисел a и b есть наибольшее число с, которое делит аи b:

c=qcd(a,b)

(Обозначение qcd для наибольшего общего делителя происходит от английских слов greatest common divisor и принято в современной литературе.)

Пример 2.10. qcd(10,15) = 5; qcd(8,28) = 4.

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

Алгоритм 2.3 Алгоритм Евклида

ВХОД: Положительные целые числа а, b, а?b.

ВЫХОД: Наибольший общий делитель gcd(a, b).

1. WHILE b ? 0 DO;

2. r<-- a mod b, а<-- b, b<-- r.

3. RETURN а.

Пример2.11. Покажем, как с помощью алгоритма Евклида вычисляется gcd(28,8):

a: 28 8 4

b: 8 4 0

r : 4 0

Здесь каждый столбец представляет очередную итерацию алгоритма. Процесс продолжается до тех пор, пока b не станет равным нулю. Тогда в значении переменной a содержится ответ (4).

Для многих криптографических систем, рассматриваемых в следующих разделах и главах, актуален так называемый обобщенный алгоритм Евклида, с которым связана следующая теорема.

Теорема 2.9. Пусть a и b -- два целых положительных числа. Тогда существуют целые (не обязательно положительные) числа х и у, такие, что

ах + by = gcd(a,b). (2.11)

Обобщенный алгоритм Евклида служит для отыскания gcd(a, b) и х,у, удовлетворяющих (2.11). Введем три строки U =(u1,u2,u3) , V =(v1,v2,v3) и Т =(t1,t2,t3). Тогда алгоритм записывается следующим образом.

Алгоритм 2.4 Обобщенный алгоритм Евклида

ВХОД: Положительные целые числа а ,b, а ? b.

ВЫХОД: gcd(a, b), х, у , удовлетворяющие (2.11).

1. U<--(a,1,0), V<--(b,0,1)

2. WHILE u1 ? 0 DO

q<--u1, div v1;

T<--( u1 mod v1, u2 - qv2, u3 - qv3);

U<--V,V<--T .

3. RETURN U = (gcd(a,b) x,y).

Результат содержится в строке U .

Операция div b алгоритме -- это целочисленное деление ( a div b = [a/b] ). Доказательство корректности этого алгоритма может быть найдено в [1, 9].

Пример 2.12. Пусть a =28, b =19. Найдем числа х и у, удовлетворяющие (2.11).

U				28	1	0
V	U			19	0	1
T	V	U		9	1	-1	q =	i
	T	V	U	1	-2	3	q =	2
		T	V	0	-17	-28	q =	9

Поясним представленную схему. Вначале в строку U записываются числа (28,1,0), а в строку V -- числа (19,0,1) (это первые две строки на схеме). Вычисляется строка Т (третья строка в схеме). После этого в качестве строки U берется вторая строка в схеме, а в качестве V -- третья, и опять вычисляется строка T (четвертая строка в схеме). Этот процесс продолжается до тех пор, пока первый элемент строки V не станет равным нулю. Тогда предпоследняя строка в схеме содержит ответ. В нашем случае gcd(28,19) = 1, х = -2, у = 3. Выполним проверку: 28 * (-2) + 19 * 3 = 1.

Рассмотрим одно важное применение обобщенного алгоритма Евклида. Во многих задачах криптографии для заданных чисел с, m требуется находить такое число d < m , что

cd mod m = 1. (2.12)

Отметим, что такое d существует тогда и только тогда, когда сит -- взаимно простые числа.

Определение 2.6. Число d, удовлетворяющее (2.12), называется инверсией с по модулю m и часто обозначается с-1 mod m.

Данное обозначение для инверсии довольно естественно, так как мы можем теперь переписать (2.12) в виде

cc-1 mod m = 1.

Умножение на с-1 соответствует делению на с при вычислениях по модулю m. По аналогии можно ввести произвольные отрицательные степени при вычислениях по модулю m:

c-1 -- (сe)-1 = (с-1)e mod m.

Пример 2.13. 3 * 4 mod 11 = 1, поэтому число 4 -- это инверсия числа 3 по модулю 11. Можно записать 3-1 mod 11=4. Число 5-2 mod 11 может быть найдено двумя способами:

5-2 mod 11 = (52 mod 11)-1 mod 11 = 3-1 mod 11 = 4,

5-1 mod 11 = (5-1 mod 11)2 mod 11 = 92 mod 11 = 4.

При вычислениях по второму способу мы использовали равенство 5-1 mod 11=9. Действительно, 5 * 9 mod 11 = 45 mod 11 = 1.

Покажем, как можно вычислить инверсию с помощью обобщенного алгоритма Евклида. Равенство (2.12) означает, что для некоторого целого к

cd-km = l. (2.13)

Учитывая, что с и m взаимно просты, перепишем (2.13) в виде

m(-k) + cd = gcd(m,c), (2.14)

что полностью соответствует (2.11), здесь только по-другому обозначены переменные. Поэтому, чтобы вычислить с-1 mod m , т.е. найти число d, нужно просто использовать обобщенный алгоритма Евклида для решения уравнения (2.14). Заметим, что значение переменной к нас не интересует, поэтому можно не вычислять вторые элементы строк U , V , T. Кроме того, если число d получается отрицательным, то нужно прибавить к нему m, так как по определению число a mod m берется из множества {0,1,..., m -- 1} .

Пример 2.14. Вычислим 7-1 mod 11. Используем такую же схему записи вычислений, как в примере 2.12:

Получаем d = -3 и dmod 11 = 11 - 3 = 8, т.е. 7-1 mod 11 = 8. Проверим результат: 7 * 8 mod 11 = 56 mod 11 = 1.

Наконец, сформулируем следующее известное свойство простых чисел.

Утверждение 2.10 (о простых числах). Количество простых чисел, меньших п, примерно равно п/ln п.

(Точная формулировка и доказательство могут быть найдены в [3].)

В заключение раздела отметим, что хотя алгоритмические вопросы теории чисел, связанные с проверкой чисел на простоту, с разложением на простые множители и т.п., не рассматриваются в этой книге, они широко исследуются во всем мире. Так недавно был найден метод проверки чисел на "простоту" полиномиальной трудоемкости, описанный в [17].