МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение

высшего профессионального образования

ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

КАФЕДРА ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ

ГЕНЕРАЦИЯ БОЛЬШИХ ПРОСТЫХ ЧИСЕЛ В КРИПТОСИСТЕМАХ С ОТКРЫТЫМ КЛЮЧОМ

для студентов специальностей

«Компьютерная безопасность» и «Комплексное обеспечение информационной безопасности автоматизированных систем»

Издательство

Тюменского государственного университета

2009

УДК 003.26:519(075.8)

ББК 3973.26-018.2я73+В13я73

Ниссенбаум О.В., Овсянко А.Г. Криптографические методы защиты информации. Генерация больших простых чисел в криптосистемах с открытым ключом: Учебно-методическое пособие для студентов IV курса ОДО специальностей «Компьютерная безопасность» и «Комплексное обеспечение информационной безопасности автоматизированных систем» Тюмень: Издательство Тюменского государственного университета, 2009, 41 стр.

Учебно-методическое пособие включает теоретический материал, задания к лабораторным занятиям, данные для самостоятельной проверки заданий, список основной и дополнительной литературы. Материал разбит на три раздела, соответствующие темам трех лабораторных работ по предмету «Криптографические методы защиты информации». Пособие также может быть использовано для организации самостоятельной работы студентов.

Рекомендовано к изданию кафедрой информационной безопасности. Утверждено проректором по учебной работе Тюменского государственного университета.

ОТВЕТСТВЕННЫЙ РЕДАКТОР: А.А. Захаров, зав.кафедрой

д.т.н., профессор

РЕЦЕНЗЕНТЫ: А.В. Широких, доцент каф. информац.

безопасности ГОУ ВПО ТюмГУ, к.т.н.

С.Д. Захаров, зав. каф. МиИ ГОУ ВПО

ТО ТГАМЭУП, к.ф.-м.н., доцент.

 ГОУ ВПО Тюменский государственный университет, 2009.

 О.В. Ниссенбаум, А.Г. Овсянко, 2009.

СОДЕРЖАНИЕ

РАЗДЕЛ 1. ОПЕРАЦИИ С БОЛЬШИМИ ЧИСЛАМИ

Простым числам в криптографии отведена одна из ведущих ролей. Большинство современных алгоритмов, такие как алгоритмы ГОСТ Р 34.11-94, ГОСТ Р 34.11-2001, DSA и EСDSA, используют простые числа. Криптографические стандарты накладывают условия на длину простого числа, например в ГОСТ Р 34.11-2001 значение простого числа должно быть больше 2²⁵⁵ , а по стандарту DSA – от 2⁵¹² до 2¹⁰²⁴.

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

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

1. 
   Сложение и вычитание целых положительных чисел по положительному модулю (x=(a+b) mod m, x=(a-b) mod m);
   
2. 
   Возведение целого положительного числа в квадрат по модулю (x=a² mod m);
   
3. 
   Возведение целого положительного числа в целую положительную степень по модулю (x=a^b mod m);
   
4. 
   Умножение двух целых положительных чисел по модулю (x=ab mod m);
   
5. 
   Вычисление обратного к целому положительному числу по целому положительному модулю (x=a^-1 mod m, где 0am).
   

1.1. Сложение

• 
  A и B – входные параметры процедуры сложения, принадлежащие классу больших чисел;
  
• 
  C – переменная этого же класса, в которую будет записан результат сложения;
  
• 
  булева переменная s, которая будет использована для хранения бита переноса (изначально следует присвоить ей нулевое значение s=0).
  

Поскольку для класса 64-битных чисел уже заданы операции сложения, умножения и т.п., целесообразно воспользоваться ими для задания операций над 128-битными числами.

Операцию сложения начинаем со сложения младших частей чисел. При сложении двух 64-битных чисел результат может составить до 65_бит. Стандартная операция сложения 64-битных чисел может привести к переполнению регистра. Поэтому будем выделять следующие случаи:

I) A₀(64) =0 и B₀(64)=0. Тогда переполнения регистра не произойдет, и мы можем сразу воспользоваться стандартной операцией сложения (C₀=A₀+B₀);

II) A₀(64)=1 и B₀(64)=1. Тогда результат наверняка займет 65 бит. В этом случае запоминаем значение старшего, 65-го бита: s=1, присваиваем старшим битам нулевые значения (A₀(64)=0, B₀(64)=0) и применяем стандартную операцию сложения (C₀=A₀+B₀);

III) (A₀(64)=1 и B₀(64)=0) либо (A₀(64)=0 и B₀(64)=1). Тогда:

1) значению старшего бита присваиваем нулевое значение (A₀(64)=0, B₀(64)=0), пользуемся стандартной операцией сложения (C₀=A₀+B₀);

2) проверяем старший бит результата:

а) если C₀(64)=0, то присваиваем C₀(64)=1,

б) если C₀(64)=1, то присваиваем C₀(64)=0 и запоминаем значение 65-го бита s=1.

Затем производится сложение старших частей – A₁ и B₁, идентичное сложению младших частей за исключением следующего нюанса: в качестве завершающего шага к старшей части следует прибавить бит переноса (С₁=С₁+s).

При сложении старших частей также может возникнуть бит переноса. Его желательно сохранить, чтобы не допускать переполнения ни при каких входных значениях A и B. Каждый раз после сложения чисел желательно выполнять процедуру вычисления остатка от деления, описанную в пункте 1.3.