Лабораторная работа № 4. Методы криптографии. Реализация процедур стандарта DES

Цель работы

Знакомство с методами двухключевой криптографии и принципами формирования общих ключей Диффи и Хеллмана.

2. Теоретические положения

СТАНДАРТ RSA (криптография с асимметричным ключом)

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

Рис. 1. Система открытого распространения

ключей Диффи и Хеллмана

При обмене информацией первый пользователь выбирает случайное число X₁, из целых чисел 1,...,n-1. Это он держит в секрете, а другому пользователю посылает число

где m – положительное целое, меньшее n. Аналогично поступает и второй пользователь. В результате они могут вычислить z

.

Для того, чтобы вычислить z первый пользователь возводит y₂ в степень X₁, аналогичным способом поступает и второй пользователь. Не зная X₁ и X₂, злоумышленник не может вычислить z, имея только y₁ и y₂.

Эквивалентность этой проблемы проблеме вычисления дискретного логарифма есть главный вопрос криптографии с открытым ключом. До настоящего времени нет простого решения проблемы.

Например, если простое число длиной 1000 бит, то для вычисления y₁ из X₁ потребуется около 2000 умножений 1000 битовых чисел. С другой стороны, имеющимися алгоритмами вычисления логарифмов над полем GF(n) потребуется 2¹⁰⁰ 10³⁰ операций. Подобрать же z злоумышленнику, не зная m, n, X₁ или X₂ за разумное время практически невозможно (см. табл. 1). В таблице 1 представлено сравнение рассмотренного ниже (в следующей лабораторной работе) одноключевого криптографического стандарта DES и двухключевого RSA.

Таблица 1

Характеристика	DES	RSA
вид криптографического алгоритма	Одноключевой	Двухключевой
Скорость работы	Быстрая	Медленная
Наименее затратный криптоанализ	Перебор по всему ключевому пространству	Разложение модуля
Стойкость	Теоретическая	Практическая
Временные затраты на криптоанализ	Столетия	зависят от длины ключа
Время генерации ключа	Миллисекунды	Десятки секунд
Тип ключа	Симметричный	Асимметричный
Длина ключа	56 бит	300 – 600 бит

Проблема произведений произведение m-битных
сомножителей

Основная проблема при формировании общих ключей Диффи и Хеллмана заключается в реализации произведений сомножителей большой разрядности (более 32-х бит). Рассмотрим метод формирования произведения сомножителей большой разрядности (m – разрядность сомножителей; L – количество 32-х битных слов каждом в сомножителе) на основе команд умножения 32-х битных сомножителей.

m = 64, L = 2

A = (a₀ + a₁ × 2³²);

B = (b₀ + b₁ × 2³²);

A × B = (a₀ + a₁ × 2³²) × (b₀ + b₁ × 2³²) = a₀ × b₀ + 2³² × (a₁ × b₀ + a₀ × b₁) + 2⁶⁴ × a₁ × b₁.

Графическая интерпретация произведения 64-битных сомножителей

a0 × b0
	a1 × b0 + a0 × b1
		a1 × b1

m = 96, L = 3

A = (a₀ + a₁ × 2³² + a₂ × 2⁶⁴);

B = (b₀ + b₁ × 2³² + b₂ × 2³²);

A × B = (a₀ + a₁ × 2³² + a₂ × 2⁶⁴) × (b₀ + b₁ × 2³² + b₂ × 2³²) = a₀ × b₀ + 2³² × (a₁ × b₀ + a₀ × b₁) + 2⁶⁴ × (a₀ × b₂ + a₁ × b₁ + a₂ × b₀) + 2⁹⁶ × (a₁ × b₂ + a₂ × b₁) + 2¹²⁸ × a₂ × b₂.

Графическая интерпретация произведения 96-битных сомножителей

a0 × b0
	a1 × b0 + a0 × b1
		a0 × b2 + a1 × b1 + a2 × b0
			a1 × b2 + a2 × b1
				a2 × b2

Алгоритм умножения L-словных сомножителей

Функция умножения L-словных сомножителей

// A – массив 32-х битных слов 1-го сомножителя;

// B – массив 32-х битных слов 2-го сомножителя;

// P – массив 32-х битных слов произведения;

// L – количество 32-х битных слов в каждом сомножителе.

void Mmul(unsigned long int* A, unsigned long int* B,

unsigned long int* P, int L){

int q, j, k;

unsigned long int Pm, Ps, r_A, r_B, r_P;

for(q = 0; q < (L + L); q++) P[q] = 0;

for(q = 0; q < (L + L - 1); q++){

Pm = 0;

Ps = 0;

r_P = 0;

for(j = 0; j < L; j++){

if(j > q) break;

for(k = 0; k < L; k++){

if((k + j) > q) break;

if((k + j) == q){

r_A = A[j];

r_B = B[k];

asm{

mov eAX, r_A

mov eBX, r_B

mul eBX

add Pm, eAX

adc Ps, eDX

adc r_P, 0

}

}

}

}

P[q] = P[q] + Pm;

P[q + 1] = P[q + 1] + Ps;

if(r_P!= 0) P[q + 2] = P[q + 2] + r_P;

}

}

3. Задание на работу

Получить вариант задания у преподавателя для формирования общего ключа Диффи и Хеллмана.

Вариант	m	n	X1	X2
		2^128
		2^256
		2^192
		2^512
		2^128
		2^256
		2^192
		2^192
		2^512
		2^128
		2^256

4. Оборудование

ПЭВМ с архитектурой IBM PC, операционная система – Windows 95, интегрированная среда – C++ Builder или Delphi версии не ниже 3.0

5. Порядок выполнения работы

1) Согласно полученному варианту задания разработать и отладить ПО для формирования общего ключа Диффи и Хеллмана.

2) Программно замерить время формирования одного общего ключа Диффи и Хеллмана.

3) Оформить отчет.

6. Оформление отчета

Отчет должен содержать:

− задание на лабораторную работу;

− листинг разработанного ПО для формирования общего ключа Диффи и Хеллмана;

− результаты исследования времени формирования общего ключа Диффи и Хеллмана.

7. Контрольные вопросы

1) Какие ассемблерные команды предназначены для обработки 32-х разрядных операндов?

2) В каких случаях находят применение двухключевые криптографические методы?

3) Разработать функцию произведения L₁ и L₂ –словных сомножителей (L₁ и L₂ – количество 32-х битных слов в первом и втором сомножителе).

4) Каким образом программно измеряется время формирования общего ключа Диффи и Хеллмана?

5) Приведите основные характеристики стандарта RSA.

6) Какую минимальную разрядность общего ключа Диффи и Хеллмана целесообразно использовать?

Дата добавления: 2015-05-07