Инструменты пользователя

Инструменты сайта


examination:mszki:question26

Экзаменационный вопрос №26

Система открытого распределения ключей Диффи – Хеллмана как пример асимметричной алгоритма шифрования.

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

Алгоритм основан на трудности вычислений дискретных логарифмов. Попробуем разобраться, что это такое. В этом алгоритме, как и во многих других алгоритмах с открытым ключом, вычисления производятся по модулю некоторого большого простого числа Р. Вначале специальным образом подбирается некоторое натуральное число А, меньшее Р. Если мы хотим зашифровать значение X, то вычисляем Y = AX mod P.

Причем, имея Х, вычислить Y легко. Обратная задача вычисления X из Y является достаточно сложной. Экспонента X как раз и называется дискретным логарифмом Y. Таким образом, зная о сложности вычисления дискретного логарифма, число Y можно открыто передавать по любому каналу связи, так как при большом модуле P исходное значение Х подобрать будет практически невозможно. На этом математическом факте основан алгоритм Диффи-Хеллмана для формирования ключа.

Формирование общего ключа

Пусть два пользователя, которых условно назовем пользователь 1 и пользователь 2, желают сформировать общий ключ для алгоритма симметричного шифрования. Вначале они должны выбрать большое простое число Р и некоторое специальное число А, 1 < A < P-1, такое, что все числа из интервала [1, 2, …, Р-1] могут быть представлены как различные степени А mod Р. Эти числа должны быть известны всем абонентам системы и могут выбираться открыто. Это будут так называемые общие параметры.

Затем первый пользователь выбирает число Х1 (X1<P), которое желательно формировать с помощью датчика случайных чисел. Это будет закрытый ключ первого пользователя, и он должен держаться в секрете. На основе закрытого ключа пользователь 1 вычисляет число Y1=AX1 mod P, которое он посылает второму абоненту.

Аналогично поступает и второй пользователь, генерируя Х2 и вычисляя Y2=AX2 mod P Это значение пользователь 2 отправляет первому пользователю.

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

Общие параметры Открытый ключ Закрытый ключ
Пользователь 1 Р, А Y1 Х1
Пользователь 2 Y2 Х2

Из чисел Y1 и Y2, а также своих закрытых ключей каждый из абонентов может сформировать общий секретный ключ Z для сеанса симметричного шифрования. Вот как это должен сделать первый пользователь: Z=(Y2)X1 mod P.

Никто другой кроме пользователя 1 этого сделать не может, так как число Х1 секретно. Второй пользователь может получить то же самое число Z, используя свой закрытый ключ и открытый ключ абонента следующим образом: Z=(Y1)X2 mod P.

Если весь протокол формирования общего секретного ключа выполнен верно, значения Z у одного и второго абонента должны получиться одинаковыми. Причем, что самое важное, противник, не зная секретных чисел Х1 и Х2, не сможет вычислить число Z. Не зная Х1 и Х2, злоумышленник может попытаться вычислить Z, используя только передаваемые открыто Р, А, Y1 и Y2. Безопасность формирования общего ключа в алгоритме Диффи-Хеллмана вытекает из того факта, что, хотя относительно легко вычислить экспоненты по модулю простого числа, очень трудно вычислить дискретные логарифмы. Для больших простых чисел размером сотни и тысячи бит задача считается неразрешимой, так как требует колоссальных затрат вычислительных ресурсов. Пользователи 1 и 2 могут использовать значение Z в качестве секретного ключа для шифрования и расшифрования данных. Таким же образом любая пара абонентов может вычислить секретный ключ, известный только им.

Пример вычислений по алгоритму

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

Р = 11, А = 7.

Каждый абонент выбирает секретное число Х и вычисляет соответствующее ему открытое число Y. Пусть выбраны

Х1 = 3, Х2= 9.

Вычисляем

Y1 = 73 mod 11 = 2,

Y2= 79 mod 11 = 8.

Затем пользователи обмениваются открытыми ключами Y1 и Y2. После этого каждый из пользователей может вычислить общий секретный ключ:

пользователь 1: Z = 83 mod 11 = 6.

пользователь 2: Z = 29 mod 11 = 6.

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

Вопросы практического использования алгоритма Диффи-Хеллмана

Для того, чтобы алгоритм Диффи-Хеллмана работал правильно, то есть оба пользователя, участвующих в протоколе, получали одно и то же число Z, необходимо правильным образом выбрать число А, используемое в вычислениях. Число А должно обладать следующим свойством: все числа вида A mod P, A2 mod P, A3 mod P,… , AP-1 mod P должны быть различными и состоять из целых положительных значений в диапазоне от 1 до Р-1 с некоторыми перестановками. Только в этом случае для любого целого Y < Р и значения A можно найти единственную экспоненту Х, такую, что Y = AХmod P, где 0 ⇐ X ⇐ (P - 1)

При произвольно заданном Р задача выбора параметра А может оказаться трудной задачей, связанной с разложением на простые множители числа Р-1. На практике можно использовать следующий подход, рекомендуемый специалистами. Простое число Р выбирается таким, чтобы выполнялось равенство Р = 2q + l, где q — также простое число. Тогда в качестве А можно взять любое число, для которого справедливы неравенства

1<A<P-1 и Aq mod P ≠ 1

На подбор подходящих параметров А и Р необходимо некоторое время, однако это обычно не критично для системы связи и не замедляет ее работу. Эти параметры являются общими для целой группы пользователей. Они обычно выбираются один раз при создании сообщества пользователей, желающих использовать протокол Диффи-Хеллмана, и не меняются в процессе работы. А вот значения закрытых ключей рекомендуется каждый раз менять и выбирать их с помощью генераторов псевдослучайных чисел.

Следует заметить, что данный алгоритм, как и все алгоритмы асимметричного шифрования, уязвим для атак типа «man-in-the-middle» («человек в середине»). Если противник имеет возможность не только перехватывать сообщения, но и заменять их другими, он может перехватить открытые ключи участников, создать свою пару открытого и закрытого ключа и послать каждому из участников свой открытый ключ. После этого каждый участник вычислит ключ, который будет общим с противником, а не с другим участником.

examination/mszki/question26.txt · Последние изменения: 2014/01/15 12:20 (внешнее изменение)