- •Методические указания
- •Тула 2000 Содержание
- •Лабораторная работа № 1. Методы криптографии. Подстановки
- •1. Цель работы
- •Лабораторная работа № 2. Методы криптографии. Генерация псевдобесконечных ключей на основе датчиков псевдослучайных чисел
- •1. Цель работы
- •2. Теоретические положения
- •Лабораторная работа № 3. Методы двухключевой криптографии
- •1. Цель работы
- •2. Теоретические положения
- •Лабораторная работа № 4. Методы криптографии. Реализация процедур стандарта des
- •1. Цель работы
- •2. Теоретические положения
- •Лабораторная работа № 5. Методы криптографии. Реализация режимов стандарта des
- •1. Цель работы
- •2. Теоретические положения
- •Лабораторная работа № 6. Макросы документов ms word. Проектирование макросов. Проблемы информационной безопасности
- •1. Цель работы
- •2. Теоретические положения
- •Лабораторная работа № 7. Методы проектирования по информационной безопасности на основе технологии визуального программирования
- •1. Цель работы
- •2. Теоретические положения
- •Литература
Лабораторная работа № 3. Методы двухключевой криптографии
1. Цель работы
Знакомство с методами двухключевой криптографии и принципами формирования общих ключей Диффи и Хеллмана.
2. Теоретические положения
СТАНДАРТ RSA (криптография с асимметричным ключом)
Электронную (цифровую) подпись обычно реализуют на основе криптографического алгоритма с открытым ключом. Такие алгоритмы строятся на основе двух ключей (ключ шифратор (КШ), ключ дешифратор (КД)). Открытым может быть один из ключей, другой же обязательно секретным. На рис. 1 представлена система открытого распространения ключей Диффи и Хеллмана.
Рис. 1. Система открытого распространения
ключей Диффи и Хеллмана
При обмене информацией первый пользователь выбирает случайное число X1, из целых чисел 1,...,n-1. Это он держит в секрете, а другому пользователю посылает число
где m – положительное целое, меньшее n. Аналогично поступает и второй пользователь. В результате они могут вычислить z
.
Для того, чтобы вычислить z первый пользователь возводит y2 в степень X1, аналогичным способом поступает и второй пользователь. Не зная X1 и X2, злоумышленник не может вычислить z, имея только y1 и y2.
Эквивалентность этой проблемы проблеме вычисления дискретного логарифма есть главный вопрос криптографии с открытым ключом. До настоящего времени нет простого решения проблемы.
Например, если простое число длиной 1000 бит, то для вычисления y1 из X1 потребуется около 2000 умножений 1000 битовых чисел. С другой стороны, имеющимися алгоритмами вычисления логарифмов над полем GF(n) потребуется 2100 1030 операций. Подобрать же z злоумышленнику, не зная m, n, X1 или X2 за разумное время практически невозможно (см. табл. 1). В таблице 1 представлено сравнение рассмотренного ниже (в следующей лабораторной работе) одноключевого криптографического стандарта DES и двухключевого RSA.
Таблица 1
Характеристика |
DES |
RSA |
1 |
2 |
3 |
вид криптографического алгоритма |
Одноключевой |
Двухключевой |
Скорость работы |
Быстрая |
Медленная |
Наименее затратный криптоанализ |
Перебор по всему ключевому пространству |
Разложение модуля |
Стойкость |
Теоретическая |
Практическая |
Временные затраты на криптоанализ |
Столетия |
зависят от длины ключа |
Время генерации ключа |
Миллисекунды |
Десятки секунд |
Тип ключа |
Симметричный |
Асимметричный |
Длина ключа |
56 бит |
300 – 600 бит |
Проблема произведений произведение m-битных сомножителей
Основная проблема при формировании общих ключей Диффи и Хеллмана заключается в реализации произведений сомножителей большой разрядности (более 32-х бит). Рассмотрим метод формирования произведения сомножителей большой разрядности (m – разрядность сомножителей; L – количество 32-х битных слов каждом в сомножителе) на основе команд умножения 32-х битных сомножителей.
m = 64, L = 2
A = (a0 + a1 232);
B = (b0 + b1 232);
A B = (a0 + a1 232) (b0 + b1 232) = a0 b0 + 232 (a1 b0 + a0 b1) + 264 a1 b1.
Графическая интерпретация произведения 64-битных сомножителей
0 |
31 |
32 |
63 |
64 |
95 |
96 |
127 |
a0 b0 |
|
|
|
||||
|
a1 b0 + a0 b1 |
|
|
||||
|
|
a1 b1 |
|
m = 96, L = 3
A = (a0 + a1 232 + a2 264);
B = (b0 + b1 232 + b2 232);
A B = (a0 + a1 232 + a2 264) (b0 + b1 232 + b2 232) = a0 b0 + 232 (a1 b0 + a0 b1) + 264 (a0 b2 + a1 b1 + a2 b0) + 296 (a1 b2 + a2 b1) + 2128 a2 b2.
Графическая интерпретация произведения 96-битных сомножителей
0 |
31 |
32 |
63 |
64 |
95 |
96 |
127 |
128 |
159 |
160 |
191 |
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 |
1 |
15 |
2128 |
10 |
10 |
2 |
13 |
2256 |
8 |
9 |
3 |
13 |
2192 |
9 |
7 |
4 |
13 |
2512 |
11 |
7 |
5 |
11 |
2128 |
10 |
10 |
6 |
11 |
2256 |
8 |
9 |
7 |
11 |
2192 |
9 |
7 |
8 |
9 |
2192 |
9 |
7 |
9 |
13 |
2512 |
11 |
7 |
10 |
15 |
2128 |
10 |
10 |
11 |
9 |
2256 |
8 |
9 |
4. Оборудование
ПЭВМ с архитектурой IBM PC, операционная система – Windows 95, интегрированная среда – C++ Builder или Delphi версии не ниже 3.0
5. Порядок выполнения работы
Согласно полученному варианту задания разработать и отладить ПО для формирования общего ключа Диффи и Хеллмана.
Программно замерить время формирования одного общего ключа Диффи и Хеллмана.
Оформить отчет.
6. Оформление отчета
Отчет должен содержать:
задание на лабораторную работу;
листинг разработанного ПО для формирования общего ключа Диффи и Хеллмана;
результаты исследования времени формирования общего ключа Диффи и Хеллмана.
7. Контрольные вопросы
Какие ассемблерные команды предназначены для обработки 32-х разрядных операндов?
В каких случаях находят применение двухключевые криптографические методы?
Разработать функцию произведения L1 и L2 –словных сомножителей (L1 и L2 – количество 32-х битных слов в первом и втором сомножителе).
Каким образом программно измеряется время формирования общего ключа Диффи и Хеллмана?
Приведите основные характеристики стандарта RSA.
Какую минимальную разрядность общего ключа Диффи и Хеллмана целесообразно использовать?