Задано: n N

Найти: р и N такие,что р – простое, , а g порождает группу Z .

Для решения этой задачи применяется полиномиальная вероятностная процедура порождения случайного числа х из промежутка от n до 2 n вместе с его разложением на простые множители. Далее производится тестирование числа х +1 на простоту. Если х +1 – число простое, то полагают р = х +1. Если тест не пройден, то выбирают другое х. Следовательно, при положительном решении такой задачи можно переходить к задаче построения первообразного корня по модулю р. Заметим, что в этом случае р есть случайное простое заданного размера.

3. Задача дискретного логарифмирования.

Рассмотрим задачу дискретного логарифмирования по простому модулю.

Задано: N, где р – простое нечетное, ; g – первообразный корень по

модулю р.

Найти: у такое, что .

Стандартное обозначение: .

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

Лучший на сегодняшний день (2005 г.) алгоритм имеет время работы

, где > 0 – константы.

4. Алгоритм «Шаг лилипута, шаг великана» дискретного логарифмирования.

Это один из первых алгоритмов (1973 г.), который показал, что задача вычисления дискретного логарифма может быть решена быстрее, чем методом перебора.

Вход: N, где р – простое нечетное, ; g – первообразный корень по

модулю р.

1. Выбрать два натуральных числа m и k такие, что . (8.1)

2. Вычислить два ряда чисел

(8.2)

3. Найти такие i и j, для которых выполняется равенство

.

4. Число подать на выход.

Покажем корректность алгоритма. Действительно,

.

Остается проверить, что указанные i и j существуют. Легко видеть, что числа в ряду (8.1) имеют вид , где , . Здесь считаем, что . Тогда представим величину в виде , где , . При этом , и можно выбрать , если , и , если . В любом случае получим один из показателей чисел ряда (8.2).

Поэтому найдется показатель по , который удовлетворяет условию .

Оценим сложность этого метода.

Теорема. Время работы алгоритма «Шаг лилипута, шаг великана» для достаточно больших p удовлетворяет неравенству

. (8.3)

Доказательство. Выберем ,

так что (8.1) выполняется. Тогда в (8.2) потребуется не более операций умножения. Известно, что для выполнения операций умножения и деления с остатком требуется элементарных операций, где есть длина операндов. Таким образом, получено время вычисления рядов (8.2). Но кроме этого требуется еще найти среди полученных чисел равные. Сначала перенумеруем числа в рядах (8.2) с добавлением одного бита принадлежности к данному ряду, преобразуем обе последовательности в список и отсортируем по величине. Длина общего ряда равна . Для лучших алгоритмов сортировки требуется операций сравнения, где s – длина списка. В нашем случае потребуется операций сравнения над словами длины бит. Таким образом, требуется операций. После сортировки объединенного ряда его надо просмотреть и найти два равных числа из разных рядов (8.2), используя битовый признак. В итоге получается оценка (8.3).

5. Алгоритм Силвера-Полига-Хеллмана дискретного логарифмирования.

Этот алгоритм предполагает, что число р –1 имеет «небольшие» простые делители, точнее любое простое ограничено некоторым общим для всех числом r, что позволяет произвести факторизацию р – 1. Его время работы ограничено полиномом от . Пусть – каноническое разложение числа р – 1. Для каждого найдем , после чего по Китайской теореме найдем искомое у. Представим

, где .

Требуется найти последовательность . Заметим, что

для . Отсюда имеем

,

что можно переписать в виде

. (8.4)

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

. (8.5)

С помощью бинарного метода возведения в степень вычислим последовательность чисел

для . (8.6)

Заметим, что все элементы последовательности попарно различны, ибо g – первообразный корень. Вычислим также степень , которая по (8.5) должна совпасть с одним из членов последовательности (8.6). Тогда коэффициент равен соответствующему показателю j.

Допустим, что уже найдены . Тогда можно вычислить левую часть сравнения (8.4) по модулю р, так как . Сравнивая результат с

членами последовательности (8.6), находим . Это завершает описание алгоритма.

6. Некоторые задачи.

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

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

Задача 3. Найти методом ШЛШВ.

Задача 4. Найти методом ШЛШВ.

Задача 5. Найти методом ШЛШВ.

Задача 6. Найти СПХ-методом.

Задача 7. Найти СПХ-методом.

Задача 8. Найти СПХ-методом.

Раздел девятый

1. Концепция криптосистем с открытым ключом.

В 1976 г. американцы W. Diffie и M. Hellmann предложили новую концепцию т. н. двухключевой криптографии, в которой процедура шифрования является общедоступной, а расшифрование может успешно провести лишь тот, кто владеет секретным ключом. Таким образом, система требует наличия двух ключей – открытого, находящегося в общем пользовании, и закрытого, секретного, которым владеет лишь адресат. Это добавляет к общей схеме закрытого информационного обмена специальный генератор ключей, который вырабатывает соответствующие пары.

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

2. Формальные составляющие асимметричных криптосистем.

Необходимыми составляющими любой асимметричной криптосистемы являются следующие:

1) алфавиты открытых и закрытых текстов;

2) пространство ключей (множество слов в некотором алфавите);

3) алгоритм генерирование ключей – вероятностный полиномиальный алгоритм, который получив на вход N, где k – параметр безопасности, дает на выходе случайную пару , принадлежащую ключевому пространству, и где называется открытым ключом и применяется для зашифрования, а – секретным и применяется для расшифрования;

4) полиномиальный детерминированный алгоритм зашифрования Е, который получив на вход открытое сообщение М и открытый ключ , дает на выходе шифртекст С, что записывается в виде ;

5) полиномиальный детерминированный алгоритм расшифрования D, который получив на вход шифртекст С и секретный ключ , дает на выход открытый текст М, что записывается в виде .

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

1) если пара получена генератором производства ключей, то для любого открытого текста М должно из следовать ;

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

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

3. Криптосистема RSA.

Криптосистема RSA предложена в 1977 г. Ее авторами являются R. Rivest, A. Shamir, L. Adleman. Это одна из самых известных асимметричных систем.

1 ) Генерирование ключей.

Выбираются два больших различных простых числа р и q, вычисляется их произведение и значение функции Эйлера . Затем выбирается случайное число Z и вычисляется d такое, что . После этого полагают открытым ключом числа n и e, а секретным ключом – число d.

2) Зашифрование.

RSA – система блочная. Открытый текст разбивается на блоки, каждый из которых рассматривается как элемент кольца Z . Таким образом, для двоичной записи блока длины m должно выполняться неравенство . Если М есть блок открытого текста, то результат его шифрования выглядит так:

.

3) Расшифрование.

Процедура расшифрования выглядит также просто:

.

Укажем на корректность процедуры, т.е. что действительно для любого открытого текста М выполняется условие M = D(E(M)). Пусть . Это сравнение можно свести к системе сравнений

,

.

Рассмотрим первое из них, привлекая малую теорему Ферма.

.

То же проделаем и со вторым сравнением. В итоге получим требуемое, так как р и q числа взаимно простые.

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

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

Задано: N, где и .

Найти: х такое, что .

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

Задано: N, где и .

Найти: d такое, что для всех х.

Из алгоритма генерирования ключей вытекает, что решение такой задачи сводится к вычислению значения функции Эйлера , что на сегодня является трудной задачей, если неизвестны множители р и q. Для того, чтобы лишить противников всякой надежды на возможность факторизации числа n, р и q выбирают величиной порядка более , так что число n имеет порядок более . Итак, задачу нахождения секретного ключа можно свести к факторизации числа n, а последняя является сложной. Все это говорит в пользу того факта, что криптосистему в настоящее время считают стойкой при надлежащем выборе параметров безопасности. Числа р и q выбирают сильными простыми (см. р.7). Добавим к сказанному, что при том, что р и q должны быть большими, они не должны сильно отличаться друг от друга, но и не должны быть слишком близки друг другу. Наконец, р и q должны быть таковы, чтобы наибольший общий делитель чисел р -1 и q -1 был небольшим, желательно, чтобы . Нарушение любого из этих условий позволяет применить к числу n один из эффективных алгоритмов факторизации или нахождения секретного ключа. Имеются и некоторые другие условия использования RSA.

Рассмотрим небольшой пример. Выберем простые p и q. Пусть р = 997, q = 977. Тогда n = 974069, a = (р – 1)(q – 1) = 972096. Положим е = 868121, и решая сравнение ed = 1 (mod ), получаем, что d = 586025. Итак, сформированы ключи криптосистемы. Пусть задан открытый текст

«BETTER LATE THAN NEVER».

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

«01041919041726110019042619070013261304210417».

Разобьем его на блоки длины 4:

«0104 1919 0417 2611 0019 0426 1907 0013 2613 0421 0417».

Возводя каждый блок в степень е = 868121 по mod 974069, получаем цифровой шифртекст:

“491794 547096 837824 773497 682113 110037 449993 489740 770973 767593 837824”

Если теперь каждый блок этого текста возвести в степень d = 586025 по mod 974069, то

получим исходный цифровой текст.

Легко видеть, что в системе RSA не шифруются некоторые сообщения, например, 0 или 1. Справедлива

Теорема. В условиях RSA сравнение выполняется для всех

тогда и только тогда, когда .

Доказательство. Действительно, из сравнения следует система

Рассмотрим первое из сравнений системы. Если , то сравнение выполнимо. Поэтому пусть . Тогда сокращая обе части сравнения на М, получаем:

.

Но по теореме Ферма , и так как среди М встречаются первообразные корни по mod p, то . Подобный вывод справедлив и для простого q, откуда и следует необходимость. С другой стороны, если , то, например, сравнение

заведомо выполняется, а потому выполняется и первое сравнение системы. То же можно утверждать и для второго сравнения системы, а окончательный результат следует из Китайской теоремы.

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

Теорема. В условиях RSA сравнение выполняется для всех

тогда и только тогда, когда .

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

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

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

,

решая которую по китайской теореме получает ответ

.

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

Чтобы воспрепятствовать такому течению дел, можно сообщение дополнить некоторым специфическим слагаемым. Например, так

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

Теорема. Пусть – приведенный многочлен, , а –

натуральное число. Если у многочлена по модулю есть корень ,

удовлетворяющий неравенству , то этот корень можно

найти за полиномиальное от и время при фиксированном

значении .

Будем считать, что имеется пользователей, получивших соответствующие сообщения

Рассмотрим многочлены

Известно, что существует такое , что Это и следует найти.

Будем считать, что меньше каждого из модулей . Положим . По китайской теореме об остатках найдутся такие , что многочлен

будет удовлетворять соотношению

.

Теперь, если имеется достаточно много шифртекстов, т.е. , то опираясь на теорему Копперсмита можно узнать за полиномиальное время. Действительно, – приведенный многочлен степени и

.

Рассмотрим еще одну из возможных атак на RSA – метод повторного шифрования. Итак, пусть , при этом и, значит, также . Строим последовательность :

Это значит, что

Поскольку , то существует натуральное число m такое, что Но тогда

откуда вытекает

Тогда будет решением рассматриваемого сравнения.

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

Сформулируем еще теорему М.Винера.

Теорема. Пусть задана RSA-криптосистема с параметрами

.

Тогда d эффективно вычислимо.

Доказательство. Для доказательства потребуется результат из теории рациональных приближений вещественных чисел. Именно:

Теорема. Пусть и – несократимая дробь, , такая, что

,

тогда – подходящая дробь числа .

Теперь вернемся к исходной теореме. Оценим величину .

.

Поэтому . так как , то .

Положим . И далее оценим сверху разность

.

Воспользуемся тем, что . Следовательно, . Примем во внимание, что . Тогда

.

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

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

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

Можно доказать и такой результат.

Теорема. Если в условиях RSA-криптосистемы известен секретный ключ , то

существует вероятностный полиномиальный алгоритм факторизации .

Доказательство. Пусть известны и такие, что . Тогда делится на . Следовательно, для любого верно

.

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

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

, .

Поэтому – собственный делитель . Таким образом, факторизовано.

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

Сравнение равносильно системе

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

.

После чего легко получаем, что

.

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

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

4. Криптосистема Рабина.

Система предложена в 1979 г. Rabin’ым.

1) Генерирование ключей.

Выбирают два больших различных простых числа р и q, вычисляют их произведение . Полагают открытым ключом число n, а секретным – р и q.

2) Зашифрование.

Шифрование производится поблочно в соответствии с формулой

.

3) Расшифрование.

Процедура расшифрования предполагает для получения блока М извлечь корень квадратный из С. Зная р и q это можно осуществить эффективно. Так как имеется четыре корня по модулю n, то при переходе к буквенному тексту берут тот, что обладает смысловым содержанием. Несложная модификация алгоритма делает шифрующее отображение инъективным. Можно, например, поступить так: к шифруемому блоку приписываются в конце некоторое фиксированное количество элементов, которыми блок оканчивается. При расшифровании среди четырех результатов извлечения корня квадратного по модулю с высокой вероятностью найдется лишь один, у которого в конце будет находиться повторный подблок, состоящий из элементов.

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

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

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

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

Рассмотрим пример. Пусть теперь р = 997, а q = 991. Тогда n = 988027. Предлагается зашифровать текст:

“ARGUMENTUM OMNI DENUDATUM ORNAMENTO”.

Запишем цифровой эквивалент этой фразы:

«001706201204131920122614121308260304132003001920122614171300120413191409»

Эту запись разобьем на блоки длины 6, для чего в конце дописана буква «J» с номе-

ром 09. Имеем:

«001706 201204 131920 122614 121308 260304 132003 001920 122614 171300 120413

191409»

Каждый из блоков возводим в квадрат по модулю 988027 и получаем:

«934382 619345 766849 374164 944753 268783 935864 722319 374164 276127 982371

376094»

Для расшифровки, например, первого блока поступаем так, как это описывалось выше. Число р, как легко проверяется, имеет вид р = 8m + 5, где m = 124. Поэтому

х = 934382 2 = 709 (mod 997).

Число q имеет вид q = 4m + 3, где m = 247. Отсюда получаем

х = 934382 = 276 (mod 991).

Дата добавления: 2014-11-16