Ход и порядок работы с пакетом ABBYY FineReader 9.0 Professional Edition. Сохранение во внешние редакторы и форматы. Первая система с открытым ключом - система Диффи-Хеллмана. Одностороння функция с "лазейкой" и шифр RSA. Элементы теории чисел.
Аннотация к работе
Так как проблема шифрования сообщений возникла еще в глубокой древности, некоторые шифры связаны с именами известных исторических личностей и в качестве первых примеров обычно используют именно такие шифры. Для этого Алиса каким-либо образом генерирует число к, передает его Бобу по закрытому каналу связи, и после этого они обмениваются сообщениями, зашифрованными с помощью этого ключа к. Тогда число у = ах mod p может быть вычислено как (все вычисления проводятся по модулю р). Для организации этой системы выбирается большое простое число р и некоторое число g, 1 <g <р-1, такое, что все числа, из множества {1,2,….,р-1} могут быть представлены как различные степени g mod р (известны различные подходы для нахождения таких чисел g, один из них будет представлен ниже). Число 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.В программе продемонстрирован совершенно новый подход к распознаванию - технология ADRT, где распознавание основано на анализе документов в целом. Поддержка распространенных форматов, качественное распознавание, ряд профессиональных возможностей делают ABBYY FINEREADER 9.0 незаменимой в бизнесе и других областях, где требуется быстрое и качественное распознавание текстов.
Введение
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 Excel и 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) не превосходит 2logx.
Доказательство. Для вычисления чисел ряда (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) новое значение унов с х = "абрикос" и сравнивает с хранящимся в памяти ранее вычисленным значением у Если унов совпадает с хранящимся в памяти у, соответствующим данному имени, то это законный пользователь. В противном случае это Ева.
Ева может попытаться найти х по у. Однако мы видели, что уже при 90-значных числах для этого потребуется более чем 1022 лет. Таким образом, представленная система хранения пароля весьма надежна и используется во многих реальных операционных системах.
Рассмотрим решение второй задачи (ПВО и самолет). Можно использовать следующий метод. Каждому "своему" самолету присваивается секретное имя, известное системе ПВО и летчику, точнее, бортовому компьютеру. Пусть, например, одному из самолетов присвоено секретное имя СОКОЛ, и этот самолет приближается к границе 10 сентября 2002 года в 12 час.45 мин. Тогда перед приближением к границе бортовой компьютер самолета формирует слово
СОКОЛ 02 09 10 12 45
(имя год месяц день часы минуты).
Другими словами, компьютер на самолете и станция ПВО прибавляют к секретному слову сведения о текущем времени и, рассматривая полученное слово как число х, вычисляют у = ax mod р, где аирне секретны. Затем самолет сообщает число у станции ПВО. Станция сравнивает вычисленное ею число у с полученным от самолета. Если вычисленное и полученное значения совпали, то самолет признается как "свой".
Противник не может взломать эту систему. Действительно, с одной стороны, он не знает секретного слова СОКОЛ и не может найти его по у, так как вычисление х по у занимает, скажем, 1022 лет. С другой стороны, он не может просто скопировать у и использовать его в качестве ответа в будущем, так как время пересечения границы никогда не повторяется и последующие значения у будут отличаться от первоначального.
Рассмотренный вариант решения "задачи ПВО" требует точной синхронизации часов в самолете и в локаторе. Эта проблема достаточно легко решается. Например, служба навигации постоянно передает метки времени в от
Вывод
Разработчики FINEREADER 9.0 хорошо поработали. В программе продемонстрирован совершенно новый подход к распознаванию - технология ADRT, где распознавание основано на анализе документов в целом. И этот подход действенен - распознавание очень качественное. Отдельно надо отметить интерфейс - он прост для новичков, а профессионалы найдут все, что нужно. Стоит отдельно отметить, что продукт обладает сертификатом на совместимость с Windows Vista. Поддержка распространенных форматов, качественное распознавание, ряд профессиональных возможностей делают ABBYY FINEREADER 9.0 незаменимой в бизнесе и других областях, где требуется быстрое и качественное распознавание текстов.
ABBYY FINEREADER удобная программа для распознавания текстов, фотографий. Я научился пользоваться программой ABBYY FINEREADER, она помогла мне в поставленной мною целью распознать текст.
Список литературы
1. Баласанян В.Э. Электронный документооборот - основа эффективного управления современным предприятием / В.Э. Баласанян // Секретарское дело. - 2002.- №2. - С. 46-48.
2. Бобылева М.П. Эффективный документооборот: от традиционного к электронному / М.П. Бобылева. - М.: Издательство МЭИ, 2004-49 с.
3. Бобылева М.П. Выбор программного продукта для автоматизации документооборота / М.П. Бобылева // Делопроизводство. - 2002. - №2. - С.27-33.
4. Витин Ю.Г. От документооборота классического - к электронному! / Ю.Г. Витин// Справочник секретаря и офис-менеджера. - 2004. - № 4. - С. 50-55.
5. Гайдукова Л.М. Проблемы традиционных технологий документационного обеспечения / Л.М. Гайдукова// - Секретарское дело. - 2006. - №10 - С. 17-22.
6. Глик Д.И. Национальные стандарты в области электронного документооборота / Д.И. Глик// - Секретарское дело. - 2006. - № 9 - С. 45-75.
7. Кудряев В.А. Организация работы с документами / В.А. Кудряев. - М.: Инфа-М, 2001. - 356 с.
8. Максимович Г.Ю. Современные информационные технологии хранения информации и организация доступа к ней / Г.Ю Максимович, В.И. Берестова // Секретарское дело. - 2005. - №1 (53) - С. 34 (2005 в).
9. Московая П.М. На пути к электронному документообороту / П.М. Московая // Делопроизводство. - 2004. - №2. - С.36-41.