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

2. Делимость шифра. Если дан шифрованный текст (у ^ ), то можно получить другой шифрованный текст, изменив только вторую часть сообщения. Действительно, умножив у2 на g“ (и Ф0), мы полу­ чим шифротекст для другого сообщения /я, = mg’".

Для защиты от подобных атак Шнорром и Якобсоном было предложено объединить схему шифрования Эль-Гамаля с цифровой подписью Шнорра. Это позволяет не только шифровать сообщение, но и аутентифицировать его.

В заключение заметим, что алгоритм цифровой подписи DSA, разработанный NIST (National Institute of Standard and Technology)

и являющийся частью стандарта DSS, опирается на рассмотренный метод.

2.3.5. Вероятностное шифрование

Криптография с открытым ключом в значительной степени ре­ шает задачу распространения ключей, которая является довольно серьезной проблемой для криптографии с секретным ключом. Но с другой стороны, при перехвате шифротекста с = Ек{т) в любом случае становится известной некоторая информация об открытом тексте от, поскольку злоумышленник может вычислить без посто­ ронней помощи открытую функцию шифрования Ек для любого от­ вечающего ему открытого текста. Задавая произвольно от' по своему выбору, он может легко выяснить, верно ли, что от = от', так как это справедливо только если Ек(т') = с. Даже если определение от из с и в самом деле было бы трудно осуществить при знании только естест­ венного алгоритма шифрования, что мы еще не доказали, ничего нельзя сказать о том, сколь велика и в чем состоит возможная час­ тичная утечка информации об от. Если использовать метафору Шафи Гольдвассер, то применение криптографии с открытым ключом по­ добно попытке прятать верблюда под одеялом: можно утаить, какой из верблюдов спрятан, но не число его горбов.

Целью вероятностного шифрования - понятия, введенного Гольдвассер и Микэли, - является такое криптографическое преобра­

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

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

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

т е Мк и случайного числа reR k . С помощью любого к е К долж­ ны легко получаться эффективные естественные алгоритмы для вы­ числения как Ек, так и Dk, но построение какого-либо эффективно­ го алгоритма вычисления Dk на основе только естественных алго­ ритмов вычисления Ек должно быть практически невозможно.

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

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

Тем не менее вероятностное шифрование достигло такого со­ стояния, что уже существует криптосистема даже более эффективная, нежели RSA. Для обеспечения конфиденциальности (но не аутенти­ фикации) механизмы работы системы Блюма - Гольдвассер, которая описывается далее, являются наилучшими из того, что наука может предложить в настоящее время. Система основана на вере в то, что возведение в квадрат по модулю целого числа Блюма (п называется целым числом Блюма, если оно является произведением двух раз­ личных простых р и 9 , оба из которых сравнимы с числом 3 по моду­ лю 4) - однонаправленная функция с потайным ходом, и на том, что псевдослучайный битовый генератор является криптографически сильным. В качестве такого генератора для получения псевдослучай­ ного одноразового шифра необходимой длины из его собственного

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

Более формально, пусть р и q —два случайно выбранных раз­ личных простых числа, сравнимых с 3 по модулю 4, которые вместе образуют секретный ключ. Их произведение n =p q является от­ крытым ключом. Пространство сообщений открытого текста-это множество всех конечных двоичных строк произвольной длины. Любое сообщение может в этом случае шифроваться непосредствен­ но без разбиения на части точно так же, как это было в случае с RSA. Однако это только чисто теоретически, поскольку на самом деле длина битовой строки, представляющей открытый текст, не должна быть больше периода псевдослучайной последовательности, выраба­ тываемой BBS-генератором, хотя на практике этот, период в столь большое число раз превышает размер модуля «, что позволяет фак­ тически не ограничивать длину открытого текста. Вероятностным пространством служит множество QRn, т.е. множество квадратич­ ных вычетов по модулю п. Пространством сообщений шифрованного текста является множество пар, образованных квадратичными выче­ тами по модулю п и конечными двоичными строками.

Пусть т -некоторое /-разрядное сообщение. И пусть также х0 - это случайный квадратичный вычет по модулю п. Далее пред­

положим, что BBS(1,(x0) и x t определяются следующим образом. Пусть п - целое число Блюма с неизвестным разложением на множи­ тели. Выберем в качестве исходного числа случайным образом вы­ бранный квадратичный вычет х0 (для того чтобы это сделать, выбе­

рем наугад целое х, взаимно простое с л, и вычислим х0 = х 2mod«). Для /> 0 определим xi рекурсивно по формуле xM =x?modn и

обозначим через Ц первый значащий бит х,-. Для любого целого t

первые t битов, которые будут таким образом сгенерированы из х0 ,

ходный вектор х0 и открытый ключ п, задается в виде пары чисел

(х,,тФ BBS„ ,(JC0)} , где ® означает поразрядное сложение по моду­ лю 2. Здесь BBS„ ,(х0) используется в качестве одноразового шифра к открытому тексту т. Значение х ( включается в шифротекст толь­ ко для того, чтобы обеспечить законному получателю эффективное дешифрование, но тем самым никак не помогая нарушителю. Следу­ ет помнить, что необходимым и достаточным условием для эффек­ тивного вычисления примитивных квадратных корней является зна­ ние сомножителей числа п. Простейший алгоритм дешифрования заключается в вычислении всей псевдослучайной последовательно­ сти, начиная с х п в обратном порядке, и используя для этого ре­ куррентное уравнение х( = ^/x,+l mod п. В результате такого вычис­ ления сначала однозначно восстанавливается значение BBS,, ,(х0),

а затем из известного шифротекста легко получается открытый текст. Обозначим через I число разрядов модуля п. Эффективность только что описанного алгоритма шифрования полностью сопоста­ вима с эффективностью криптосхемы RSA, так как в нем для каждо­ го бита открытого текста используется одна операция модульного возведения в квадрат, в то время как в RSA для каждого (М)-блока открытого текста требуется одно модульное возведение в степень, и при этом каждое возведение в степень требует / возведений в квад­ рат и, кроме того, / умножений. Простейший алгоритм дешифрова­ ния, предложенный выше, не очень хорош: для каждого бита откры­ того текста он требует вычисления одного примитивного квадратно­ го корня, а на каждое такое вычисление расходуется примерно столько же времени, сколько на одно модульное возведение в сте­

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

Далее рассмотрим этот эффективный алгоритм вычисления х0

из x t при известном разложении п =p q . В качестве предваритель­ ного шага в нем сначала с помощью обобщенного алгоритма Евкли­ да раз и навсегда вычисляются целые числа а и b такие, что ар+bq =1. Затем выполняются следующие операции:

а<—exp mod

и<—expmod((x, mod р),а,р) v <- expmod((x, mod^),p,^) return (bqu + apv) mod n.

Схема вероятностного шифрования Блюма - Гольдвассер может быть сделана даже быстрее. Более тщательный анализ псевдослучай­ ного генератора BBS показывает, что в нем после каждой операции модульного возведения в квадрат можно использовать более одного значащего бита очередного квадратичного вычета х,.. А именно окончательная псевдослучайная последовательность не ослабится, если в нее для каждого индекса i будут выбираться (приблизительно) 1оёг(0 первых значащих битов х,- Благодаря Такому улучшению вероятностное шифрование будет осуществляться быстрее, нем шифрование RSA, примерно в log2(/) раз, причем то же самое спра­

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

2.3.6. Криптография на эллиптических кривых

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

или GF(T).

Особый интерес к эллиптической криптографии обусловлен те­ ми преимуществами, которые дает ее применение в беспроводных коммуникациях - высокое быстродействие и небольшая длина ключа. Например, в построенных на основе эллиптических кривых крипто­ системах бинарной размерности от 150 до 350 обеспечивается уро­ вень криптографической стойкости, который требует в известных криптографических системах элементов бинарной размерности от 600 до 1400 и более.

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

1. Полиномиальные функции. Криптосистемы на базе по­

линомиальных функций

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

Пусть р > 3 простое число, a,b е GF(p), такие, что 4а2 + lib 2 ф 0.

Эллиптической кривой Е над полем GF(p) называется множе­

над полем GF(p) вместе с дополнительной точкой со, называемой точкой в бесконечности.

Представление ЭК в виде уравнения (14) носит название эл­ липтической кривой в форме Вейерштрасса.

Если обозначить количество точек на кривой Е через NE. Тогда согласно теореме Хассе NE =p + l - t, где |Г| < 2(р)0,5.

NE называется порядком кривой Е, а t-следом кривой Е. Для точек на кривой вводится бинарная операция сложения, которая иг­ рает ту же роль, что и операция умножения в криптосистемах RSA

иЭль-Гамаля:

1.оо + оо = оо.

2.Для любых (дс,у)&Е, (ду>) + со = (х,у).

3.Для любых (х,у)^Е, (ду>) + (х, - у ) = со.

4. Для любых (XI,J >I) е Е и (хьу2) &Е х х Ф х2, (Х|,у,) + (хьу2)=

=(^з),

где х3 = X2 - х х- х 2,у 3 = Х(х, - х3) - у хД = (у2-yi)/(x2-*,). 5. Для любых (хцуО £ Е и у хФ0, (дс^О + (Х|,у0 = (дадъ),

где х3 = Х2- 2Хиу3= Ц хх- х 3) - у и Х = (3 х 2 + а)Пух.

Множество точек на кривой Е, с заданным таким образом би­ нарной операцией, образует абелеву группу.

Если NE =р+ 1, то Е называется суперсингулярной.

Пользуясь операцией сложения точек на кривой, можно естест­ венным образом ввести операцию умножения точки РЕ на произ­ вольное целое число k: кР = Р + Р +...+ Р.

Где операция выполняется к раз.

Построим теперь одностороннюю функцию, на базе которой бу­ дем строить криптосистему.

Пусть Е - ЭК, точка Р ^Е . Возьмем Ae Z, причем к < NE. В ка­ честве прямой функции выберем произведение кР. Для его вычисле­ ния по оптимальному алгоритму требуется не более 21og2A операций

сложения. Обратную задачу определим так: по заданным ЭК, т^чке Р ^ Е и произведении кР найти к. В настоящее время такая задала за полиномиальное время неразрешима.

Теперь рассмотрим криптографический протокол, аналогичный протоколу Диффи - Хеллмана.

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

Пример 55. Пусть абоненты А и В решили провести передачу сообщений, используя криптосистему на базе ЭК. Для этого они вы­ брали ЭК Е : у2=.х3 + 157л: + 223mod(743) и точку Р(117,692) на ней. Затем А генерирует секретное число а = 735. Пользователь В генери­

и пересылает его А. Далее пользователь А умножает присланное зна­ чение рР на а, получив после этого офР = (332,590). Пользователь В умножает присланное значение aР на Р, получая такой же резуль­ тат - арр = (332,590). Таким образом, оба пользователя получили общее секретное значение (координаты точки офР на ЭК), которое они будут использовать в качестве общего секретного ключа.