Воспользуйтесь поиском к примеру Реферат        Грубый поиск Точный поиск
Вхід в абонемент


Интернет реклама УБС






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

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

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

криптосистему с открытым ключом характеризуют три процедуры: образование

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

Теоретические основы

Пусть n - произвольное натуральное число, а х-целое число. Для целого числа х является Z

через х mod n обозначим остаток от деления числа х на число n. Запишем х? В (mod n), если х mod n? y mod n, и будем говорить, что х и у конгруэнтны (сравнительные) по модулю n. Например, 100 mod 11? L, -8 mod 10? 2. Множество (0, 1, ..., n-1) всех возможных неотъемлемых остатков по модулю п обозначим через Zn. Считаем, что х является обратным элементом к в по модулю п, если х? В (mod n). В этой ситуации запишем x = y-1 (mod n). Множество элементов из Zn, для которых существуют обращены в Zn, обозначим через Z * n и назовем эти элементы оборотными по модулю п. В множестве Zn можно выполнять две операции: х является суммой элементов в и z по модулю п, если в + z? x (mod n) х является произведением элементов y и z по модулю п, если yz? x (mod n). Если п является составным числом: n = pq, куплена pq равна нулю в Zn: pq? 0 (mod n). Обозначение а Р b означает, что а делит b. Для целых чисел а и b через НОД (a, b) обозначим их наибольший общий делитель - всего среди таких с, одно-временно с Ра и с Р b (хотя бы одно из чисел а и b считают отличным от нуля ). Наименьшее натуральное число, которое делится на каждое из неотрицательных целых чисел р1, р2, ..., pk, назы-вают их наименьшим общим кратным и обозначают

НСК (ри р2, ..., рк).

Утверждение 3.1. Такие условия эквивалентны:

1) х? y (mod n)

2) х - + kn, где k целое число

3) n (х-у).

конгруэнции имеет следующие свойства:

если x1? y1 (mod п) и х2? y2 (mod n), то x1 + х2? y1 + y2 (mod n)

если x1? y1 (mod n) i x2 = y2 (mod п), то х1 х2 = у1 y2 (mod n).

Пример 3.1. Доказать, что число 73524 делится на 11.

Очевидно, что 10?-l (mod II). На основании приведенных выше свойств Конгрив-Энке получаем 100? L (mod 11), 1000? -1 (Mod 11), 10000? L (mod 11). Отсюда 20? 2 (mod 11), 500? 5 (mod 11), 3000? 3 (mod 11), 70000? 7 (mod 11). Последовательное добавляют ния дает 73520? 7 (mod 11). Тогда 73520 + 4? 1 + 4? 0 (mod 11).

Рассмотрим алгоритм Евклида (III в. до н. есть.) получения наибольшего общего делителя натуральных чисел а и b.

Алгоритм опирается на выражения

НОД (а, b) = НОД (a, a mod b) для a> b, (3.1)

НОД (а, 0) = а. (3.2)

Пример 3. 2. Найти НОД (211, 79). Последовательно применим равенство (3.1), пока не получим (3.2):

Итак, НОД (211, 79) = НОД (79, 53) = НОД (53, 26) = НОД (26, 1) = НОД (1, 0) = 1. В общем случае выполнения алгоритма Евклида можно описать так.

Количество т шагов алгоритма Евклида определена неравенством т <2 log 2 b + 1. При выполнении алгоритма Евклида можно найти такие целые числа x, y, которые удовлетворяют диофантово уравнение ах - by = 1, где а и b взаимно просты: НОД (а, b) = 1, а> 0, b> 0 .

Пусть, где

Тогда (3.3)

Итак, числа х, у, определенные равенствами (3.3), является целочисленными решениями диофантовых уравнения.

Описанные вычисления удобно выполнять с помощью табл. З.1.

Пример 3.3. Определить такие целые числа x, у, 17х - тринадцатый = 1. Имеем

Заполнив табл. 3.1, получим

Отсюда k = 2; x = (-1) k-1 Qk-1 = Q1 = 3, y = (-l) k-1, Pk-1 =-P1 = -4. Легко перевиpиты, что 17 - (-3) -13 - (-4) = 1.

Пример 3.4. (Получение обратных элементов в Zn). Найти 8-1 mod 35, то есть решить сравнения 8x? L (mod 35).

Последнее сравнение равносильно диофантовых уравнению 8x + 35y = 1, связь которого находим, пользуясь алгоритмом Евклида. С этого алгоритма следует

3 = 2-1 + 1 q3 = 1

2 = 1-2 +0 q4 = 1

Заполнив табл. 3.1, получим

Имеем k = А; х? (-1) k-1; Qk-1 = Q3 = 13 (mod 35) = 22 (mod 35). Легко проверить, что 8.22 = 176 = 35.5 + 1 1 (mod 35).

Утверждение 3.2. Пусть Z * n - множество оборотных элементов по модулю п. Тогда

множество Z * n состоит из элементов х, взаимно простых с п и только из них: {х <п

НОД (x, n) = 1}.

Действительно, если НОД (х, n) = 1, то wx-wn = 1, где и, v - целые числа. Отсюда ux = l (mod


Страницы: 1 2 3 4 5 6 7 8 9