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

2.4 Шифр Шамира

Этот шифр, предложенный Шамиром (Adi Shamir), был первым, позволяющим организовать обмен секретными сообщениями по открытой линии связи для лиц, которые не имеют никаких защищенных каналов и секретных ключей и, возможно, никогда не видели друг друга. (Напомним, что система Диффи-Хеллмана позволяет сформировать только секретное слово, а передача сообщения потребует использования некоторого шифра, где это слово будет использоваться как ключ.)

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

cada mod (р - 1) = 1 (2.15)

Эти числа А держит в секрете и передавать не будет. В тоже выбирает два числа сB и dB , такие, что

cBdB mod (р-1) = 1 (2.16)

и держит их в секрете.

После этого А передает свое сообщение т, используя трехступенчатый протокол. Если m < р (m рассматривается как число), то сообщение m передается сразу , если же m ? р, то сообщение представляется в виде m1, m2,.. .,mt , где все m < р , и затем передаются последовательно m1,m2,….,mt. При этом для кодирования каждого m, лучше выбирать случайно новые пары (cada) и (cBdB) -- в противном случае надежность системы понижается. В настоящее время такой шифр, как правило, используется для передачи чисел, например, секретных ключей, значения которых меньше р. Таким образом, мы будем рассматривать только случай m < р. Дадим описание протокола.

Шаг 1. А вычисляет число

x1 = mСa mod p. (2.17)

где m -- исходное сообщение, и пересылает х1 к В.

Шаг 2. В, получив x1, вычисляет число

х1 = х1Cb mod р (2.18)

и передает x2 к A.

Шаг 3. А вычисляет число

x3 = x2Da mod р (2.19)

и передает его В.

Шаг 4. В, получив х3 , вычисляет число

x4 = x3Db mod p. (2.20)

Утверждение 2.11 (свойства протокола Шамира).

1) х4 = m, т.е. в результате реализации протокола от А к В действительно передается исходное сообщение;

2) злоумышленник не может узнать, какое сообщение было передано.

Д о к а з а т е л ь с т в о. Вначале заметим, что любое целое число е ? 0 может быть представлено в виде e = k(p -- 1) + r, где r = е mod (р -- 1). Поэтому на основании теоремы Ферма

xe mod р = rк(р-1)+r mod р = (1к · xr) mod р = хе mod (p-l) mod р.

(2.21)

Справедливость первого пункта утверждения вытекает из следующей цепочки равенств:

(предпоследнее равенство следует из (2.21), а последнее выполняется в силу (2.15) и (2.16)).

Доказательство второго пункта утверждения основано на предположении, что для злоумышленника, пытающегося определить т, не существует стратегии более эффективной, чем следующая. Вначале он вычисляет сb из (2.18), затем находит db и, наконец, вычисляет x4 = m по (2.20). Но для осуществления этой стратегии злоумышленник должен решить задачу дискретного логарифмирования (2.18), что практически невозможно при больших р.

Опишем метод нахождения пар ca,da и сb,db , удовлетворяющих (2.15) и (2.16). Достаточно описать только действия для абонента А, так как действия для В совершенно аналогичны. Число ca выбираем случайно так, чтобы оно было взаимно простым с р-1 (лучше сразу брать нечетное число). Затем вычисляем da с помощью обобщенного алгоритма Евклида, как это было объяснено в разделе 2.3.

П р и м е р 2.15. Пусть А хочет передать В сообщение m = 10. А выбирает р = 23, сa = 7 (gcd(7,22) = 1 ) и вычисляет da = 19. Аналогично, В выбирает параметры сb = 5 (взаимно простое с 22) и db = 9 . Переходим к протоколу Шамира.

Шаг 1. x1 = 107 mod 23 = 14 .

Шаг 2. х2 = 145 mod 23 = 15 .

Шаг З. х3 = 1519 mod 23 = 19.

Шаг 4. х4 = 19° mod 23 = 10.

Таким образом, В получил передаваемое сообщение m-- 10.

2.5 Шифр Эль-Гамаля

Пусть имеются абоненты А , В , С , ..., которые хотят передавать друг другу зашифрованные сообщения, не имея никаких защищенных каналов связи. В этом разделе мы рассмотрим шифр, предложенный Эль-Гамалем (Taher ElGamal), который решает эту задачу, используя, в отличие от шифра Шамира, только одну пересылку сообщения. Фактически здесь используется схема Диффи-Хеллмана, чтобы сформировать общий секретный ключ для двух абонентов, передающих друг другу сообщение, и затем сообщение шифруется путем умножения его на этот ключ. Для каждого следующего сообщения секретный ключ вычисляется заново. Перейдем к точному описанию метода.

Для всей группы абонентов выбираются некоторое большое простое число р и число g, такие, что различные степени g суть различные числа по модулю р (см. раздел 2.2). Числа р и g передаются абонентам в открытом виде (они могут использоваться всеми абонентами сети).

Затем каждый абонент выбирает свое секретное число сi, 1 < сi < р -- 1, и вычисляет соответствующее ему открытое число di,

di=gCi mod p. (2.22)

В результате получаем таблиц 2.3.

Таблица 2.3: Ключи пользователей в системе Эль-Гамаля

Абонент	Открытый ключ	Секретный ключ
А	dA	СA
В	dB	СB
С	dC	CC

Покажем теперь, как А передает сообщение то абоненту В. Будем предполагать, как и при описании шифра Шамира, что сообщение представлено в виде числа m < р.

Шаг 1. А формирует случайное число к, 1 < k < р - 2 , вычисляет числа

r = gк mod р, (2.23)

е = m · dkB mod р (2.24)

и передает пару чисел (r, е) абоненту В.

Шаг 2. В, получив ( r , е), вычисляет

(2.25)

Утверждение 2.12 (свойства шифра Эль-Гаадаля).

1) Абонент В получил сообщение, т.е. m' = m;

2) противник, зная р, g, db, r и е, не может вычислить m.

Доказательство. Подставим в (2.25) значение е из (2.24):

m' = m * dkB * rp-1-Cb mod p.

Теперь вместо r подставим (2.23), а вместо db -- (2.22):

По теореме Ферма

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

Для доказательства второй части заметим, что противник не мо-
жет вычислить к в равенстве (2.23), так как это задача дискретного
логарифмирования. Следовательно, он не может вычислить m в ра-
венстве (2.24), так как m было умножено на неизвестное ему число.
Противник также не может воспроизвести действия законного получа-
теля сообщения (абонента В), так как ему не известно секретное число
св (вычисление св на основании (2.22) -- также задача дискретного
логарифмирования).

Пример2.16. Передадим сообщение m = 15 от А к В. Выберем параметры аналогично тому, как это было сделано в примере 2.2 стр. 23. Возьмем р = 23 , g = 5 . Пусть абонент В выбрал для себя секретное число сb = 13 и вычислил по (2.22)

dB =513 mod 23 = 21.

Абонент А выбирает случайно число к, например к = 7, и вычисляет по (2.23), (2.24):

r = 57 mod 23 = 17, е = 15 * 217 mod 23 = 15 * 10 mod 23 = 12.

Теперь А посылает к В зашифрованное сообщение в виде пары чисел
(17,12). В вычисляет по (2.25)

m' = 12 * 1723-1-13 mod 23 = 12 * 179 mod 23 = 12 * 7 mod 23 = 15.

Мы видим, что В смог расшифровать переданное сообщение.

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

2.6 Одностороння функция с "лазейкой" и шифр RSA

Названный в честь его разработчиков Риверса (Ron Rivers), Шамира (Adi Shamir) и Адлемана (Leonard Adleman), этот шифр до сих пор является одним из самых широко используемых.

Мы видели, что шифр Шамира полностью решает задачу обмена сообщениями, закрытыми для прочтения, в случае, когда абоненты могут пользоваться только открытыми линиями связи. Однако при этом сообщение пересылается три раза от одного абонента к другому, что является недостатком. Шифр Эль-Гамачя позволяет решить ту же задачу за одну пересылку данных, но объем передаваемого шифротекста в два раза превышает объем сообщения. Система RSA лишена подобных недостатков. Интересно то, что она базируется на другой односторонней функции, отличной от дискретного логарифма. Кроме того, здесь мы встретимся с еще одним изобретением современной криптографии - односторонней функцией с "лазейкой" (trapdoor function).

В этой системе используются следующие два факта из теории чисел.

1. Задача проверки числа на простоту является сравнительно легкой.

2. Задача разложения чисел вида n = pq (р и q -- простые числа) на множители является очень трудной, если мы знаем только п, а р и q -- большие числа (это так называемая задача факторизации).

Пусть в нашей системе есть абоненты А, В, С,…Каждый абонент выбирает случайно два больших простых числа Р и Q . Затем он вычисляет число

N = PQ. (2.26)

(Число N является открытой информацией, доступной другим абонентам.) После этого абонент вычисляет число ф -- (Р -- l)(Q -- 1) и выбирает некоторое число d < ф, взаимно простое с ф, и по обобщенному алгоритму Евклида находит число с, такое, что

cd mod ф = 1. (2.27)

Вся информация, связанная с абонентами, представлена в таблице 2.4.

Таблица 2.4: Параметры абонентов в системе RSA

Абонент	Открытая инф.	Секретная инф.
A	NA,dA	PA,QA,cA
В	NB,dB	PB,QB, cB
С	NC, dC	PC,QC,cC

Опишем протокол RSA. Пусть Алиса хочет передать сообщение т Бобу, причем сообщение т рассматривается как число, удовлетворяющее неравенству т < NB (далее индекс В указывает на то, что соответствующие параметры принадлежат Бобу).

Шаг 1. Алиса шифрует сообщение по формуле

(2.28)

используя открытые параметры Боба.

Шаг 2. Боб, получивший зашифрованное сообщение, вычисляет

(2.29)

Утверждение 2.13. Для описанного протокола т' = т, т.е. абонент В получает исходящее от А сообщение.

Доказательство. По построению протокола

Равенство (2.27) означает, что для некоторого к

cBdB = кфв + 1.

Согласно утверждению 2.5

где ц(·) -- функция Эйлера. Отсюда и из теоремы 2.8 следует

Утверждение 2.14 (свойства протокола RSA).

Протокол шифрует и дешифрует информацию корректно;

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

Доказательство. Первое свойство следует из утверждения
2.13. Для доказательства второго свойства заметим, что злоумышлен-
ник знает только открытые параметры Nиd. Для того чтобы найти
с, он должен знать значение ф = (Р -- 1)(Q -- 1), а для этого, в свою
очередь, ему требуется знать Р и Q . Вообще говоря, он может найти
Р и Q, разложив N на множители, однако это трудная задача (см.
факт 2). Отметим, что выбор больших случайных Р и Q возможен за
приемлемое время, так как справедлив факт 1.

Применяемая в системе RSA односторонняя функция у = xd mod N обладает так называемой "лазейкой", позволяющей легко вычислить обратную функцию х = mod N, если известно разложение N на простые множители. (Действительно, легко вычислить ф =(Р -- 1)(Q -- 1), а затем с = d-1 mod ф.) Если Р и Q неизвестны, то вычисление значения обратной функции практически невозможно, а найти Р и Q по N очень трудно (см. факт 2), т.е. знание Р и Q -- это "лазейка" или "потайной ход"). Такие односторонние функции с лазейкой находят применение и в других разделах криптографии.

Отметим, что для схемы RSA важно, чтобы каждый абонент выбирал собственную пару простых чисел Р и Q , т.е. все модули Na, Nb, Nc,…., должны быть различны (в противном случае один абонент мог бы читать зашифрованные сообщения, предназначенные для другого абонента). Однако этого не требуется от второго открытого параметра d. Параметр d может быть одинаковым у всех абонентов. Часто рекомендуется выбирать d = 3 (при соответствующем выборе Р и Q, см. [26]). Тогда шифрование выполняется максимально быстро, всего за два умножения.

П р и м е р 2.17. Допустим, Алиса хочет передать Бобу число m = 15 . Пусть Боб выбрал следующие параметры:

Рв = 3, QB = 11, NB = 33, dB = 3

(3 взаимно просто с ф(33) = 20). Найдем сB с помощью обобщенного алгоритма Евклида:

св = 7

(проверим: 3 * 7 mod 20 = 1) . Кодируем m по формуле (2.28):

е = 153 mod 33 = 152 * 15 mod 33 = 27 * 15 mod 33 = 9.

Число 9 Алиса передает Бобу по открытому каналу связи. Только Боб знает сB = 7, поэтому он декодирует принятое сообщение, используя (2.29):

m' = 97 mod 33 = (92)2 * 92 * 9 mod 33 = 152 * 15 * 9 mod 33 = 15.

Таким образом, Боб расшифровал сообщение Алисы.

Рассмотренная система невскрываема при больших Р и Q , но обладает следующим недостатком: А передает сообщение В, используя открытую информацию абонента В (числа NB и dB). Злоумышленник не может читать сообщения, предназначенные для В, однако он может передать сообщение к В от имени А. Избежать этого можно, используя более сложные протоколы, например, следующий.

А хочет передать В сообщение m. Сначала А вычисляет число е = тCa mod NA. Злоумышленник не может этого сделать, так как сА секретно. Затем А вычисляет число f = ede mod NB и передает f к В. В получает f, вычисляет числа u = fc" mod NB и w = udA mod NA .

В результате абонент В получает сообщение w = m. Как и в исходной схеме RSA, злоумышленник не может прочитать переданное сообщение, но здесь, в отличие от RSA, он не может также послать сообщение от имени А (поскольку не знает секретного сA).

Здесь мы встречаемся с новой ситуацией. В знает, что сообщение пришло от А, т.е. А как бы "подписал" его, зашифровав своим секретным сd. Это пример так называемой электронной подписи. Она -- одно из широко используемых на практике изобретений современной криптографии и будет систематически изучаться в главе 4.

Контрольные вопросы

1. В чем слабость шифра гаммирования с неравновероятной гаммой?

2. Является ли надежным шифрование литературного текста с помощью модульного гаммирования, использующего гамму, два знака которой имеют суммарную вероятность, совпадающую с суммарной вероятностью остальных знаков? Почему?

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

4. Почему недопустимо использовать дважды одну и ту же гамму (даже случайную и равновероятную!) для зашифрования разных открытых текстов?

5. Почему в качестве гаммы нецелесообразно использовать текст художественного произведения? Можете ли Вы предложить метод вскрытия такого шифра?

6. Можно ли по шифртексту получить приближения для вероятностей знаков гаммы?

7. В чем состоит тест Казиски?

8. Назовите основные этапы работы по вскрытию шифра Виженера.

9. Каким образом рассчитывается индекс совпадения для реального языка?

10. Из каких простых замен «состоит» шифр гаммирования (какмногоалфавитный шифр)?

Анализ результатов

Pраб = min (Pкон, Pпровер) = min (90,85, 88,57)

Pпровер = 100%*( ошибочные символы/все символы)

Pконтр = 100%*( реальные ошибки/все символы)

Страница	Кол-во символов	% ошибок	Pпровер, ~%	Реальные ошибки	Pконтр, ~%
1	80/1841	4	95,65	30	98,36
2	256/4759	5	94,62	113	97,63
3	492/6160	8	92,01	204	96,68
4	212/3742	6	94,33	152	95,93
5	200/3825	5	94,77	136	96,44
6	400/3501	11	88,57	330	90,85
7	312/4678	7	93,32	225	95,17
8	332/5611	6	94,08	260	95,36
9	350/3994	9	91,23	300	92,49
10	210/3079	7	93,18	174	94,35
11	200/3144	6	93,64	170	94,59
12	252/3827	7	93,41	163	95,73
13	192/3315	6	94,20	150	95,47
14	256/3740	7	93,15	173	95,37
15	238/4163	6	94,28	134	96,78
16	285/3913	7	92,71	223	94,30
17	154/3400	5	95,57	93	97,26
Все	4421/66692		93,45	3030	95,46

Посчитав процент правильного распознания можно сделать вывод, что текст распознан на Отлично по шкале интеллектуальных задач, так как 95,46 >95, хотя текст для распознания был плохого качества.

Заключение

Разработчики 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.

10. Саблин В.К. О внедрении электронного документооборота / В.К. Саблин // Аудит. - 2004. - №5. - С.6.

Размещено на Allbest.ru