Математические основы криптологии и криптографические методы и средс

примерно одинакового размера простых чисел. Конечно, необходимо понимать, что «не в состоянии» здесь означает за приемлемое время.

Другим примером является модульное возведение в степень или модульное экспоненцирование (с фиксированным основанием и мо­ дулем). Пусть а и п - числа, такие, что 1 < а < л, и пусть также Zn = {0, 1,2, ..., л-1}. Тогда модульным возведением в степень на­ зывается функция fa,n:Zn—>Zn, определяемая какfa,n(m) = am mod п. Такую функцию можно вычислить эффективно, когда длина каждого из трех параметров а,п и т составляет несколько сотен знаков.

Функция вычисления, обратная модульному возведению в сте­ пень, называется дискретным логарифмированием. Даны целые чис­ ла а,п и х, требуется найти такое целое т (если конечно оно сущест­ вует), что am mod п - х. В настоящее время вычисление больших мо­ дульных экспонент можно выполнить даже на ПК, но тем не менее на сегодняшний день неизвестно ни одного алгоритма вычисления дискретных логарифмов больших чисел за приемлемое время даже на самых мощных компьютерах. Хотя мы и не можем доказать, что эффективных таких алгоритмов вообще не существует, имеются вес­ кие основания предполагать, что модульное возведение в степень (с фиксированными основанием и модулем) действительно является однонаправленной функцией.

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

2.2.8. Односторонние (однонаправленные) функции с потайным ходом

Функция f: X—>Y называется однонаправленной функцией с по­ тайным ходом, если, во-первых, не только самаf но и функция / -1, обратная ей, может быть вычислена эффективно, а, во-вторых, даже

если такой эффективный алгоритм вычисления/ известен, то никакое, пусть самое полное, описание его работы не должно давать возмож­ ности построить эффективный алгоритм вычисления

Секрет, с помощью которого можно эффективно вычислить функциюf \ как раз и называется потайным ходом для функцииf

Рассмотрим такие односторонние функции.

Первая функция, которую мы считаем односторонней с потай­ ным ходом, - модульное возведение в степень, но с фиксированной экспонентой и модулем. Пусть т и п - целые числа, a Zn определено так же, как ранее. Тогда модульное возведение в степень (относи­ тельно экспоненты т и модуля п) есть функция

g m , n = а " ' modя-

Необходимо быть уверенным в понимании различия между

функциями/,.,, И

Опять по аналогии операция, обратная gm,n, известна как извле­ чение корня /и-й степени из х по модулю п: даны целые числа т,п и х, найти такое целое а (если оно существует), что

am mod п = х.

Например, 5 - это корень 4-й степени из 16 по модулю 21, пото­ му что 54 mod 21 = 16. Очевидно, что 2 также является корнем 4-й степени из 16 по модулю 21.

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

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

Если р и q - два различных больших простых числа примерно одинакового размера и, кроме того, и р, и q сравнимы с 3 по модулю 4, то мы будем говорить, что их произведение л = pq является целым числом Блюма. Определим Z,,* как множество целых чисел от 1 до п - \ , которые не делятся ни нар, ни на q. Наконец, определим QRn как подмножество множества Z„* состоящее из чисел, которые яв­ ляются совершенными квадратами по модулю п. Элементы QRn из­ вестны как квадратичные вычеты по модулю п. В качестве неболь­

шого примера положим р = 19, a q = 23, откуда имеем п = 19-23 = 437. Тогда 135 является элементом Z,,*, в то время как 133 - нет (посколь­

ку 133 = 19-7). Более того, 135 не является квадратичным вычетом по модулю 437, так как не существует целого числа а, такого, что а2= 135 (mod 437), тогда как 139 является таковым, поскольку

242 =576s=139(mod437).

Теперь сформулируем без доказательства несколько утвержде­ ний, необходимых для понимания всего дальнейшего изложения. Число элементов в Z,,* равно (р - \){q - 1), причем в точности чет­ вертую их часть составляют квадратичные вычеты. Каждый квадра­ тичный вычет допускает ровно четыре различных «квадратных кор­ ня» в Z„*, из которых лишь один единственный является квадратич­ ным вычетом. Этот особый корень мы назовем примитивным (перво­ образным) квадратным корнем. В нашем примере 24-это прими­ тивный квадратный корень из 139 по модулю 437, другими тремя корнями являются числа 185, 252 и 413. Имеющий криптографиче­ ское значение факт заключается в том, что способность определять примитивные квадратные корни по модулю такого числа п оказыва­ ется вычислительно эквивалентной умению раскладывать это п на множители. Иначе говоря, тот, кто знает разложение п на множители, может эффективно вычислять и примитивные квадратные корни по модулю п, тогда как такие вычисления трудны.

Теперь можно определить еще одного кандидата на однона­ правленную функцию с потайным ходом. Мы случайно выбираем р и q и вычисляем п = pq, которое открыто объявляется. После этого лю­

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

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

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

2.2.9. Вопросы и задачи для самоконтроля

1.Определите класс языков Р.

2.Определите понятие «полиномиальный алгоритм».

3.Дайте определение класса NP.

4.Что означает утверждение «язык L принадлежит классу АД*»?

5.Что можно утверждать, если предположить, что классы Р

иNP совпадают?

6.Дайте понятие JVP-полного языка.

7.Сформулируйте основное требование для существования од­ носторонних функций.

8.Укажите отличие между эффективно вычислимой и односто­ ронней функцией.

9.Приведите пример однонаправленной функции.

10.Определите однонаправленную функцию с потайным вхо­ дом. Существенно ли ее отличие от однонаправленной функции?

11.Определите первообразный квадратный корень.

12.Извлечь квадратный корень из чисел 537; 439; 246; 238 по модулю 897.

13.Извлечь кубический корень из чисел 24; 29; 34 по модулю 41.

14.Пусть известно разложение числар - 1, где р есть простое чис­ ло. Как проверить то, что число а является первообразным корнем?

2.3. СОВРЕМЕННЫЕ АССИМЕТРИЧЕСКИЕ АЛГОРИТМЫ ШИФРОВАНИЯ

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

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

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

В 1976 году Уитфрид Диффи и Мартин Хеллман заложили ос­ новы для преодоления этой трудности, предложив понятие крипто­ графии с открытым ключом. Сходное понятие было независимо от­ крыто Ральфом Мерклем. Вскоре последовала его первая практиче­ ская реализация, предложенная Рональдом Райвестом, Эди Шамиром и Леонардом Эдлеманом.

Основное наблюдение, которое, собственно, и привело к крип­ тографии с открытым ключом, заключалось в следующем - тот, кто шифрует сообщение, не обязательно должен быть способен его де­ шифровать. Преимущество асимметричных шифров перед симмет­ ричными шифрами состоит в отсутствии необходимости предвари­ тельной передачи секретного ключа по надежному каналу. Сторона, желающая принимать шифрованные тексты, в соответствии с ис­ пользуемым алгоритмом вырабатывает пару «открытый ключ - за­ крытый ключ». Значения ключей связаны между собой, однако вы­ числение закрытого ключа по открытому должно быть невозможным с практической точки зрения. Открытый ключ публикуется в откры­ тых справочниках и используется для шифрования информации контрагентом и проверки ЭЦП. Закрытый ключ держится в секрете и используется для дешифровывания сообщения, переданного вла­ дельцу пары ключей, и для создания ЭЦП. Для удостоверения аутен­ тичности самих публичных ключей, передаваемых по открытому ка­ налу или получаемых из справочника, обычно используют сертифи­ каты. Однако в чистом виде асимметрические криптосистемы тре­ буют существенно больших вычислительных ресурсов, потому на практике используются в сочетании с другими алгоритмами.

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

2.3.1. Криптосистемы с открытым ключом

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

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

Ек: Мк —> Ск и D k: Ск —» Л/Л таких, что Dk(Ek(m)) = т для любого

открытого текста т е М к. Так же, как и в криптосистемах с секретным ключом, эффективные алгоритмы для вычисления Ек

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

Криптографические системы с открытым ключом используются следующим образом. Каждый пользователь раз и навсегда выбирает некоторый случайный ключ к е К Он использует этот ключ для по­ лучения обоих естественных алгоритмов Ек и Dk. Затем он делает публично доступным свой алгоритм шифрования Ек, возможно, по­ средством использования при этом некоторого справочника, но хра­ нит в тайне свой алгоритм дешифрования Dk. Тогда если один из пользователей криптосистемы захочет послать ему некоторое сооб­ щение, то он найдет в справочнике его открытый алгоритм шифро­ вания и использует его для того, чтобы шифровать свое сообщение. В этом случае после его пересылки, используя собственный секрет­ ный ключ, только законный получатель сможет дешифровать полу­ ченный шифротекст. Стоит отметить, что в противоположность криптосистемам с секретным ключом, если пользователь А, шифро­ вав некоторое сообщение т для пользователя В, сохранит шифро­ текст с, но потеряет соответствующий ему открытый текст (или за­ будет все, что в нем содержалось), то он не будет иметь никаких преимуществ перед нарушителем в раскрытии т из с. Также в про­ тивоположность криптосхемам с секретным ключом, если наруши­ тель перехватывает шифротекст, зная, для кого он был шифрован, то он может использовать открытый алгоритм шифрования для провер­

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

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

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

Самой первой криптографической системой с открытым ключом из тех, что были предложены в открытой литературе, является крип­ тосистема Райвеста, Шамира и Эдлемана. Эта криптосистема осно­ вывается на вере в то, что модульное возведение в степень при фик­ сированных экспоненте и модуле является однонаправленной функ­ цией с потайным ходом. Безопасность алгоритма RSA основана на трудности задачи разложения на множители. Алгоритм использует два ключа - открытый (public) и секретный (private), вместе откры­ тый и соответствующий ему секретный ключи образуют пару клю­ чей (keypair). Открытый ключ не требуется сохранять в тайне, он ис­ пользуется для шифровывания данных. Если сообщение было шиф­ ровано открытым ключом, то дешифровать его можно только соот­ ветствующим секретным ключом.

1.Основные положения криптосистемы RSA

В1978 году Рональд Райвест, Ади Шамир и Леонард Адлемац

(R. Rivesty A. Shamir, L. Adlemari) предложили пример функции, обладающей рядом замечательных свойств. На ее основе была построена реально используемая система шифрования, получившая название по первым буквам фамилий авторов - система RSA. Рассмотрим ее основные положения на примере криптосистемы с открытым ключом.

Теоретические положения построения криптографических сис­ тем с открытым ключом в основном базируются на следующих поня­ тиях и утверждениях:

♦Кольцо целых чисел является факториальным. Но задача раз­ ложения больших чисел на простые множители за полиноми­ альное время не разрешима.

♦Задача вычисления логарифма за полиномиальное время не разрешима.

♦Теорема 10.

♦Функции Эйлера.

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

А: риРг, га = P IPI , ф(гА), НОД(а, ф(гА)) = 1, 0 < а < ф(гл),

В: quqi, rB = qiqi, ф(гв), НОД (А, ф (rB)) = 1, 0 < Ь < ф(гв).

Затем печатается телефонная книга, доступная всем желающим, которая имеет вид

А: га, а;

В: гв, Ь,

гА - произведение двух простых чисел, известных только А, а - От­ крытый ключ, доступный каждому, кто хочет передать секретное Со­ общение А, гв - произведение двух простых чисел, известных только