М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 185
Текст из файла (страница 185)
Способ шифрования зависит от устройства конкретной криптографической системы. Принципиальный момент заключается в том, что для обеспечения защиты информации (невозможности «подслушивания») необходимо, чтобы расшифровку было трудно выполнить, даже используя открытый ключ. Это похоже на верхнюю дверцу в описанном выше почтовом ящике: если сообщение уже положено в ящик, его невозможно забрать, даже если у вас есть ключ от верхней дверцы.
Поскольку «подслушивающему» лицу доступны только открытый ключ и зашифрованное сообщение, оно не сможет восстановить исходное сообщение. У Алисы же имеется дополнительная информация — секретный ключ Я. Последний определяет второе преобразование, которое применяется к зашифрованному сообщению.
Такое преобразование называют деиьифроеанием — зто действие, обратное шифрованию. Оно позволяет Алисе восстановить исходное сообщение. Рис. Пб.1. Реалиэация идеи криптографии с открытым ключом По существу эта же схема реале»овеяв почтовыми службами во многих странах Мы описали принцип действия криптографии с открытым ключом в цдеальном случае. К сожалению, к моменту написания данной книги неизвестно, существуют ли подобные надежно защищенные схемы, позволяющие осуществлять шифрование с открытым ключом. Известно лишь несколько схем, которые считают достаточно надежными — их регулярно используют на практике, например, при продаже товаров через Интернет.
Однако зто не означает, что доказана высокая степень защиты таких схем. Считаются, что зти схемы обладают хорошей защитой от несанкционированного доступа потому, что были приложены (безрезультатно!) огромные усилия для их «взлома». Из крипто- 776 Приложение 5. Криптография с открытым ключом и система ВЯА графических систем с открытым ключом наиболее широкое распространение получила система ВЯА (ее название образовано от инициалов создателей — Рдвеста, Шамира и Адлемана). Предполагаемая конфиденциальность системы ВЯА опирается, как мы увидим, на очевидную сложность разложения числа на простые множители на классическом компьтотере.
Для понимания работы этой системы требуется знание основ теории чисел (см. резд. П4.1 и П4.2 Приложения 4). Чтобы создать открытый и секретный ключи для использования в ВЯА-криптосистеме, Алиса должна выполнить следующие действия. 3. Выбрать случайным образом небольшое нечетное целое число е, взаимно- простое с у(и) = (р — 1)(с7 — 1). 4. Вычислить число с(, являющееся мультипликативным обратным к е по модулю ср(и). 5. Открытым ЯЯА-ключом будет пара Р = (е, и), секретным ВЯА-ключом — пара Я = (с(, и).
Пусть теперь Боб хочет зашифровать сообщение М с использованием открытого ключа Р, чтобы отправить зашифрованное сообщение Алисе. Будем считать, что сообщение М содержит не более 11ойи) бит (более длинные сообщения можно разбить на блоки длиной (1ойи1 бит и отправлять по очереди). Шифрование сообщения состоит в вычислении величины Е(М) = Ме (шос( и) (П5.1) Е(М) и будет зашифрованным вариантом сообщения М, который Боб перешлет Алисе.
Алиса сможет быстро дешифровать сообщение, используя свой секретный ключ Я = (с(, и), для этого нужно просто возвести сообщение в с1-ю степень: Е(М) — ~ Х)(Е(М)) = Е(М)" (шоб и). (П5.2) Докажем, что при такой операции действительно получится исходное сообщение. В самом деле, ес( = 1 (пюс1 ср(и)), а следовательно, ес( = 1 + кср(и) с некоторым целым й. Рассмотрим два случая. В первом число М вЂ” взаимно простое с и. Как следует из теоремы Эйлера (П4.9), обобщающей малую теорему Ферма, Мь"1"> = 1 (шод и), поэтому 1.
Выбрать два больших простых числа р и с7. 2. Вычислить их произведение и = рд. Ю(Е(М)) = Е(М)" (шод и) = М (шос1 и) = М +""'1"1 (шос1 и) = М ° М "'1"1 (шос( и) = М (пюс1 и), (П5.3) (П5.4) (П5.5) (П5.6) (П5.7) Приложение 5. Криптография с открытым ключом и система НЯА 777 т. е. в этом случае Алиса действительно получает исходное сообщение.
Во втором случае число М не является взаимно простым с и, так что М делится хотя бы на одно из двух чисел р и Ф Для определенности будем считать, что М делится на р н не делится на о (остальные случаи рассматриваются аналогично). Поскольку р делит М, выполняется равенство М = О (щи р), а значит, М = О = М (щи р). Поскольку о не делит М, согласно малой теореме Ферма получим, что М«« = 1 (шоб д), а следовательно, М"'<") = 1 (шод д), поскольку у(п) = (р — 1)(д — 1).
Из равенства ед'= 1+ )«~р(п) следует, что М«« = М (шой о). Согласно китайской теореме об остатках, М« = М (шо«) и), поэтому во втором случае (когда числа М и и не являются взаимно простыми) в результате дешифрования также получается исходное сообщение. 'Упражнение П5.1. Выполните самостоятельно шифрование с использованием системы ВЯА. Закодируйте слово «КВАНТОВЫИ», взяв р = 3, д = 11 (если пронумеровать буквы от О до 31, исключив букву «е», то каждую букву можно записать пятью битами; для каждой буквы отдельно вычисляется ее зашифрованный «образ»; подходящие значения для е и И выберите самостоятельно).
Насколько эффективно может быть реализована система ВЯА? Существуют две проблемы. Первая — создание открытых и секретных ключей для криптографических систем. Если этот процесс не выполняется эффективно, НЯА плохо подходит для практического использования. Узким местом здесь является «генерирование» простых чисел р и д. На практике используется следующий метод: выбирается произвольное число требуемой длины, а затем проверяется, является число простым или составным.
Имеются быстрые способы проверки простых чисел, нвпример тест Миллера-Рабина, с помощью которого примерно за 0(Ь~) операций выясняется, является ли число простым (здесь 1 — длина ключа). Если выясняется, что число составное, процедура повторяется еще один или несколько рэз — пока не будет выбрано простое число.
Из оценки количества простых чисел (см. задачу П4.1) слевует, что вероятность для числа из Ь бит быть простым примерно равна 1/)ой(2ь) = 1/.5, поэтому с большой вероятностью за 0(Ь) попыток можно найти простое число. Таким образом, всего потребовалось 0(Ь«) операций.
Рассмотрим теперь эффективность шифрования и дешифрования при использовании системы ВЯА. Мы используем возведение в степень в арифметике остатков, которое, как известно, требует 0(Ьз) операций (см. вставку 5.2). Таким образом, все операции, необходимые для шифрования с помощью системы ВЯА, могут быть быстро выполнены на классическом компьютере, и при достаточно скромных вычислительных мощностях можно работать с ключами длиной в тысячи битов. Как можно взломать систему НЯА? Опишем ниже два метода, которые дают надежду на взлом системы НЯА: в первом используется нахождение порядка элемента, во втором — разложение числа на множители.
Пусть Ева прочитала зашифрованное сообщение М' (шоб п) и ей известен открытый ключ (е, и), использованный при шифровании сообщения. Предположим, она может находить порядок зашифрованного сообщения, т. е. такое наименьшее положитель- 778 Приложение 5. Криптография с открытым ключом и система ВЯА нос число г, что (М')" = 1 (шоб и). (Не ограничивая общности, можно считать, что такое число существует, т. е. что число М' — взаимно простое с и. В противном случае у чисел М' (тод и) и и имеется общий делитель, который можно найти с помощью алгоритма Евклида, после чего система ВЯА может быть взломана, как это описывается ниже для второго метода.) Согласно упр.
П4.16, т делит у(п). Поскольку е взаимно простое с ~р(п), оно должно также быть взаимно простым и с г, а следовательно, иметь мультипликативный обратный элемент по модулю г (обозначим его Н'). Это означает, что еУ = 1+ йг для некоторого целого в. Тогда Ева может восстановить исходное сообщение М, возведя зашифрованное сообщение в И'-ю степень: (М')~ (шод п) = М1+"" (шод п) (П5.8) = М ° М"" (шоб п) (П5.9) = М (шоб и). (П5.10) Следует отметить, что Ева никогда не узнает секретный ключ (Н, и) — ей известны только (а', п).
Конечно, числа Н' и д тесно связаны, поскольку Н' является обратным к е по модулю г, Н вЂ” обратным к е по модулю ~р(п), а г делит ~р(п). Тем не менее наше обьяснение показывает, что систему ВЯА можно взломать, не выясняя точного значения секретного ключа. Конечно, этот метод действует только в том случае, если Ева умеет эффективно находить порядок элемента, а к настоящему моменту такой алгоритм для классического компьютера неизвестен. Но с помощью квантового компьютера задача нахождения порядка может быть эффективно решена (это описано в равд. 5.3.1), поэтому система ВЯА может быть взломана. зпражнение П5.2. Покажите, что Ы также является обратным элементом к е по модулю т, т. е.
Н = У (шос1 т). Второй метод взлома системы ВЯА позволяет полностью определить секретный ключ. Пусть Ева умеет находить разложение числа и (вычислять р и д, произведение которых равно и). Следовательно, она может эффективно находитыр(п) = (р — 1)(9 — 1). После этого легко вычисляется И, являющееся обратным к е по модулю ~р(п). Таким образом, полностью определяется секретный ключ (Н, и). Видно, что если бы существовал быстрый способ разложения числа на простые множители, систему ВЯА было бы очень легко взломать. Предполагаемая защита системы ВЯА опирается на тот факт, что для ее взлома требуется отыскать решение одной из двух задач, которые, как считается, трудно разрешить с помощью классического компьютера (хотя это и не доказано).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
