РОССИЙСКАЯ ФЕДЕРАЦИЯ
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Государственное образовательное учреждение
высшего профессионального образования
ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ИНСТИТУТ МАТЕМАТИКИ И КОМПЬЮТЕРНЫХ НАУК
КАФЕДРА ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ
,
КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫ ИНФОРМАЦИИ.
ГЕНЕРАЦИЯ БОЛЬШИХ ПРОСТЫХ ЧИСЕЛ В КРИПТОСИСТЕМАХ С ОТКРЫТЫМ КЛЮЧОМ
Учебно-методическое пособие
для студентов специальностей
«Компьютерная безопасность» и «Комплексное обеспечение информационной безопасности автоматизированных систем»
Издательство
Тюменского государственного университета
2009
УДК 003.26:519(075.8)
ББК 3973.26-018.2я73+В13я73
АЗ Н691
, Овсянко методы защиты информации. Генерация больших простых чисел в криптосистемах с открытым ключом: Учебно-методическое пособие для студентов IV курса ОДО специальностей «Компьютерная безопасность» и «Комплексное обеспечение информационной безопасности автоматизированных систем» Тюмень: Издательство Тюменского государственного университета, 2009, 41 стр.
Учебно-методическое пособие включает теоретический материал, задания к лабораторным занятиям, данные для самостоятельной проверки заданий, список основной и дополнительной литературы. Материал разбит на три раздела, соответствующие темам трех лабораторных работ по предмету «Криптографические методы защиты информации». Пособие также может быть использовано для организации самостоятельной работы студентов.
Рекомендовано к изданию кафедрой информационной безопасности. Утверждено проректором по учебной работе Тюменского государственного университета.
ОТВЕТСТВЕННЫЙ РЕДАКТОР: , зав. кафедрой
информационной безопасности,
д. т.н., профессор
РЕЦЕНЗЕНТЫ: , доцент каф. информац.
безопасности ГОУ ВПО ТюмГУ, к. т.н.
, зав. каф. МиИ ГОУ ВПО
ТО ТГАМЭУП, к. ф.-м. н., доцент.
Ó ГОУ ВПО Тюменский государственный университет, 2009.
Ó , , 2009.
СОДЕРЖАНИЕ
РАЗДЕЛ 1. ОПЕРАЦИИ С БОЛЬШИМИ ЧИСЛАМИ.. 4
1.1. Сложение. 5
1.2. Вычитание (меньшего числа из большего) 7
1.3. Вычисление остатка от деления (r = x mod m) 8
1.4. Умножение двух чисел по модулю (u×v mod m) 10
1.5. Возведение в квадрат. 14
1.6. Возведение в степень (дихотомический алгоритм) 15
Задания к разделу 1. 16
Тесты для самопроверки к разделу 1. 17
РАЗДЕЛ 2. ВЕРОЯТНОСТНЫЕ ТЕСТЫ НА ПРОСТОТУ. 19
2.1. Случайный поиск числа в заданном диапазоне. 19
2.2. Вероятностные тесты на простоту. 21
2.2.1. Тест Ферма на простоту. 21
2.2.2. Тест Соловея-Штрассена. 22
2.2.3 Тест на простоту Миллера-Рабина. 24
Задания к разделу 2. 26
Данные для самопроверки к разделу 2. 26
РАЗДЕЛ 3. ДОКАЗУЕМО ПРОСТЫЕ ЧИСЛА.. 28
3.1. Тест Миллера на простоту. 28
3.2. Тест Поклингтона. 30
3.3. Процедура генерации простых чисел ГОСТ Р 34.10-94. 32
Задания к разделу 3. 34
Данные для самопроверки к разделу 3. 35
ОБОЗНАЧЕНИЯ.. 39
СПИСОК ЛИТЕРАТУРЫ.. 40
РАЗДЕЛ 1. ОПЕРАЦИИ С БОЛЬШИМИ ЧИСЛАМИ
Простым числам в криптографии отведена одна из ведущих ролей. Большинство современных алгоритмов, такие как алгоритмы ГОСТ Р 34.11-94, ГОСТ Р 34.11-2001, DSA и EСDSA, используют простые числа. Криптографические стандарты накладывают условия на длину простого числа, например в ГОСТ Р 34.11-2001 значение простого числа должно быть больше 2255 , а по стандарту DSA – от 2512 до 21024.
Ключи и блоки данных такой длины не могут быть обработаны за один такт процессора, так как размер регистра процессора ограничен 64 битами. Одним из способов решения данной проблемы является создание классов больших чисел на основе существующих классов 64-битных чисел. Большое число создается на основе упорядоченного массива 64-битных чисел путем задания операций сложения, вычитания, умножения, и т. п.
В основном над классами больших чисел реализуют следующие операции:
1) Сложение и вычитание целых положительных чисел по положительному модулю (x=(a+b) mod m, x=(a-b) mod m);
2) Возведение целого положительного числа в квадрат по модулю (x=a2 mod m);
3) Возведение целого положительного числа в целую положительную степень по модулю (x=ab mod m);
4) Умножение двух целых положительных чисел по модулю (x=ab mod m);
5) Вычисление обратного к целому положительному числу по целому положительному модулю (x=a-1 mod m, где 0<a<m).
Рассмотрим методы, с помощью которых реализуются вышеперечисленные операции.
1.1. Сложение
Реализацию операции сложения рассмотрим на примере сложения чисел A и B длины 128 бит. Каждый операнд представлен в виде массива, состоящего из 2-х чисел, каждое из которых имеет длину 64_бита. Результатом данной операции будет являться число С, также представленное в виде массива из 2-х чисел длиной 64 бита каждое.
Для реализации операции сложения вам понадобится объявить класс больших чисел, объектами которого являются массивы, состоящие из двух беззнаковых целых чисел по 64 бита каждое.
· A и B – входные параметры процедуры сложения, принадлежащие классу больших чисел;
· C – переменная этого же класса, в которую будет записан результат сложения;
· булева переменная s, которая будет использована для хранения бита переноса (изначально следует присвоить ей нулевое значение s=0).
Младшая часть числа A обозначена как A0, старшая часть – как A1. Аналогичные обозначения вводятся для чисел B и C. Запись A0(i) означает «i-й бит младшей части числа A». Нумерация бит производится справа налево.
Поскольку для класса 64-битных чисел уже заданы операции сложения, умножения и т. п., целесообразно воспользоваться ими для задания операций над 128-битными числами.
Операцию сложения начинаем со сложения младших частей чисел. При сложении двух 64-битных чисел результат может составить до 65_бит. Стандартная операция сложения 64-битных чисел может привести к переполнению регистра. Поэтому будем выделять следующие случаи:
I) A0(64) =0 и B0(64)=0. Тогда переполнения регистра не произойдет, и мы можем сразу воспользоваться стандартной операцией сложения (C0=A0+B0);
II) A0(64)=1 и B0(64)=1. Тогда результат наверняка займет 65 бит. В этом случае запоминаем значение старшего, 65-го бита: s=1, присваиваем старшим битам нулевые значения (A0(64)=0, B0(64)=0) и применяем стандартную операцию сложения (C0=A0+B0);
III) (A0(64)=1 и B0(64)=0) либо (A0(64)=0 и B0(64)=1). Тогда:
1) значению старшего бита присваиваем нулевое значение (A0(64)=0, B0(64)=0), пользуемся стандартной операцией сложения (C0=A0+B0);
2) проверяем старший бит результата:
а) если C0(64)=0, то присваиваем C0(64)=1,
б) если C0(64)=1, то присваиваем C0(64)=0 и запоминаем значение 65-го бита s=1.
Затем производится сложение старших частей – A1 и B1, идентичное сложению младших частей за исключением следующего нюанса: в качестве завершающего шага к старшей части следует прибавить бит переноса (С1=С1+s).
При сложении старших частей также может возникнуть бит переноса. Его желательно сохранить, чтобы не допускать переполнения ни при каких входных значениях A и B. Каждый раз после сложения чисел желательно выполнять процедуру вычисления остатка от деления, описанную в пункте 1.3.
1.2. Вычитание (меньшего числа из большего)
Реализуем операцию вычитания A-B, где A³B. Поскольку в теории чисел и криптографии практически не используются отрицательные числа (точнее, в асмметричной криптографии все вычисления, как правило, производятся в системе наименьших неотрицательных вычетов, и типы переменных используются только беззнаковые), а все операци производятся по положительному модулю, то в случае, когда A<B (A<m, B<m), и требуется произвести операцию (A-B) mod m, ее программируют как (m-B+A) mod m.
Итак, для реализации операции вычитания вам понадобится тот же самый класс больших чисел, что и для сложения.
· A и B (A³B) – входные параметры процедуры вычитания, принадлежащие классу больших чисел;
· C – переменная этого же класса, в которую будет записан результат вычитания.
Опишем процедуру вычитания. Обозначения, описанные в предыдущем пункте, сохраняются. Заметим, что, поскольку A³B, то и A1³B1. Поэтому первым шагом алгоритма будет:
1. C1:=A1-B1;
Для младших же частей возможны различные случаи:
2. Если A0³B0, то С0:=A0-B0, иначе
следует перенести единицу из старшей части:
2.1. C1:=C1-1;
и учесть ее в младшей части результата:
2.2. C0:=not(B0-A0)+1.
При этом опреация not(B0-A0)+1 есть ни что иное как 264+A0-B0. Почему мы не можем запрограммировать С0:=264+A0-B0? Потому что тогда произойдет переполнение, ведь в переменную С0 нельзя записать число, большее (264-1).
1.3. Вычисление остатка от деления (r = x mod m)
Для вычисления остатка от деления можно применить следующий подход: проверить размеры чисел x и m (в битах). Если |x|>2|m| то использовать двоичное «деление столбиком», до тех пор, пока не будет достигнуто |x|£2|m|, а затем применяют метод Баррета.
Двоичное «деление столбиком»:
Вход: x, m, |x|>2|m|.
1. g:=m; k:=x;
2. g:=m<<(|k|–|m|);
3. если g>k, то g:=g>>1;
4. k:=k-g;
5. если |k|>2|m|, то Шаг 2, иначе Выход;
Выход: k.
Замечание. Если для вычисления остатка не предполагается в дальнейшем использовать метод Баррета или другой аналогичный метод (Монтгомери и т. п.), то условие проверки на Шаге 5 должно быть заменено на «если k>=m, то…».
Пример:
Вход: x=79=(1 , m=3=(11)2, |x|=7, |m|=2.
1. g:=3, k:=79;
2. g:=3<<(7-2)=(11)2<<5=(1 =96;
3. 96>59Þg:=96>>1=(1 >>1=(=48;
4. k:=79-48=31;
5. |k|=5>2|m|, возвращаемся на Шаг 2;
2. g:=3<<(5-2)=(11)2<<3==24;
3. 24<31;
4. k:=31-24=7;
5. |k|=3<2|m|, идем на Выход;
Выход: k=7.
Действительно, 79º7(mod 3).
Метод Баррета:
Вход: x, m, |x|£2|m|, k=|m|.
Предвычисления (если на протяжении всего криптоалгоритма используется один и тот же модуль, целесообразно z и d вычислить заранее единожды):
a) 
, (здесь 22k вычисляется при помощи быстрой операции битового сдвига 1<<(2k)).
b) d:=1<<(k+1) (то есть d=2k+1).
Алгоритм:
1. 
;
2. r1:=x mod d; r2:=(q m) mod d; r:=(r1-r2) mod d;
3. Пока r ≥ m, делаем r: = r – m (не более 2-х раз);
4. Выход: r.
Замечания. На шаге 1 операция вида b:=
может быть реализована как: s:=0 if (x and (1<<(k-1)))=0 else s:=1; b:=(x>>(k-1))+s; операция a:=
, поскольку d=(10…0)2, может быть реализована как a:=y>>(k+1). На шаге 2, поскольку d=(10…0)2, операции вида a:=y mod d реализуются как быстрые операции a:=y and (d-1).
Пример.
Вход: x=19; m=3; k=|m|=2; 
; d=1<<3=8.
1. 
;
2. r1 = 19 mod 8 = 3; r2 = 6 ∙ 3 mod 8 = 2; r = 3-2 mod 16 = 1;
3. r<m
Выход: 19 mod 3 =r=1
Замечание. В описанных выше алгоритмах встречаются операции (нециклического) битового сдвига: >> (вправо) и << (влево). Следует помнить, что операции эти осуществляются над числами созданного нами класса, поэтому эти операции тоже необходимо описать. Например, операция сдвига вправо A:=B>>k для 128-битовых чисел схематично может быть описана как
1. A0:=(B0>>k) or (B1<<(64-k));
2. A1:=B1>>k.
Здесь обозначения A1, B1, A0, B0 аналогичны пункту 1.1, а операции >> и << суть обычные правый и левый (нециклические) сдвиги 64-битовых чисел. Если же число имеет более 2-х разрядов (например, не 128-, а 192- или 256-битное), то операция сдвига будет описана подобным образом с поправкой на количество разрядов.
1.4. Умножение двух чисел по модулю (u×v mod m)
Заметим, что произведение двух 128-битных чисел есть число размером до 256 бит. Для того чтобы избежать удвоения размера результата, целесообразно определять не произведение, а произведение по модулю (операции в асимметричных криптосистемах выполняются в системе наименьших неотрицательных вычетов).
Прежде, чем определять процедуру умножения двух больших чисел (в нашем случае, 128-битных чисел, составленных из 64-битных), необходимо определить произведение двух 64-битных чисел (назовем его умножением цифр). Далее в псевдокодах будем обозначать такое умножение как MultiplySmall(X, Y, Z), где X и Y – 64-битные множители, Z – 128-битная переменная, произведение.
В целом, операция умножения цифр реализуется так же, как и операция умножения 128-битных чисел, только вместо старшей и младшей 64-битных частей числа используются 32-битные, а результат умножения занимает 128 бит. Для сложения, умножения 32-битных половин используются стандартные операции.
Пусть необходимо умножить два больших числа – u и v. Каждое из них, как и ранее, представляет собой массив из двух беззнаковых целых чисел по 64 бита каждое. В системе счисления по основанию b=264 эти числа можно представить в виде:
u = (u1, u0)b =u1b+u0; v = (v1 ,v0)b =v1b+v0.
Тогда их произведение имеет следующий вид:
u∙v mod m = (u1v1b2 + (u1v0 + u0v1)b + u0v0) mod m.
Таким образом, для вычисления произведения u∙v mod m на компьютере, вычисляются произведения:
A=u1v1 mod m; B=u0v0 mod m; C=(u1v0 + u0v1) mod m.
При этом C удобно вычислять как C=(u1v0 mod m) + (u0v1 mod m) mod m.
Заметим, что размер чисел A, B и C – 128 бит. Произведение y=uv займет до 256 бит. Поэтому для представления промежуточного результата y потребуется массив, состоящий из 4-x 64-битовых чисел: y={y3, y2, y1, y0}.
Число A записывается в 2 старших разряда результата, а число B – в два младших. Затем к полученному числу прибавляется C, сдвинутое влево на b разрядов (см. рисунок):
+
В виде псевдокода это можно представить, например, как
1. Y0:=A0; D0:=A1; D1:=B0;
2. Addition(D, C,D, s);
3. y1:=D0; y2:=D1; y3:=B1+s.
В приведенном выше псевдокоде D – переменная заданного нами типа 128-битных больших чисел, Addition(D, C,D, s) – процедура сложения двух больших чисел D и C, причем младшие 128 бит результата записывается в переменную D, а 129-й бит – в переменную s.
После указанных действий следует вычислить остаток от деления результата y mod m. Поскольку y не является переменной заданного нами типа больших чисел, придется написать для нее отдельную процедуру приведения по модулю, используя тот же подход, что и для 128-битовых значений. При этом следует помнить, что |y|=256 бит, |m|=128 бит.
Традиционный подход требует 4-х умножений 64-битовых чисел. Операция умножения является вычислительно трудоемкой. Существует более быстрый метод Карацубы, приведенный ниже, который использует всего 3 умножения 64-битовых чисел, поэтому дает выигрыш во времени порядка ¾.
Метод Карацубы:
Рассмотрим произведение K:
K:= (u0 + u1)(v0 +v1) = u1v1 + (u1v0 + u0v1) + u0v0.
Вычислив произведения A и B как в традиционном подходе и произведение K, можем вычислить C как
C = K–A–B.
Таким образом, применив традиционный подход, и заменив лишь способ вычисления C, сократим количество умножений цифр до 3-х.
Замечание. Следует отметить, что умножение для K несколько дольше простого умножения, так как при суммировании u0 и u1, v0 и v1, может возникнуть бит переноса (если u0+u1>b и/или v0 + v1>b). Вычисление K тогда может выглядеть, например, так:
1. Addition(u0,u1,Cu, s1); Addition(v0, v1,Cv, s2);
2. MultiplySmall(Cu, Cv, D);
3. K0:=D0; K1:=D1; K2:=0;
4. D0:=K1; D1:=K2;
5. if s2 then Addition(Cu, D, D);
6. if s1 then Addition(Cv, D, D);
7. if s1 and s2 then D1:=D1+1;
8. K1:=D0; K2:=D1;
То есть если при сложении u0 и u1 возникает бит переноса s1=1, то к произведению Cu×Cv необходимо прибавить Cv, сдвинув 64 бита влево; если бит переноса возникает при сложении v0 и v1, то необходимо прибавить Cu, сдвинув на 64 бита влево; если бит переноса возникает при сложении как v0 и v1,так и u0 и u1, то необходимо прибавить единицу, сдвинув на 128 бит влево.
Заметим, что K – трехразрядное число, при вычитании для вычисления C это необходимо будет учесть.
1.5. Возведение в квадрат
Пусть необходимо возвести в квадрат большое число – x, число создаваемого нами класса. В системе счисления по основанию b=264 это число можно представить в виде:
x = (x1, x0)b =x1b+x0.
Если для возведения в квадрат использовать процедуру умножения, описанную в пункте 1.4, то потребуется 4 умножения цифр (при использовании метода Карацубы – 3 умножения цифр). Если же использовать специальную процедуру возведения в квадрат, можно уменьшить число трудоемких операций умножения. Действительно,
x2=x12b2+x0x1×2b+x02 .
Вычисляем A=x12, B=x02, C=x0x1. Числа A, B и C являются 128-битными. Число A записывается в 2 старших разряда результата, а число B – в два младших. Затем к полученному числу прибавляется C, сдвинутое влево на 64+1=65 бит (см. рисунок).
Замечание. Для вычисления A и B используются процедуры возведения в квадрат (такую процедуру для 64-битных чисел следует создать отдельно, так чтобы результат помещался в число размером 128 бит), более быстрые, чем процедура умножения.
|
Такая процедура возведения в квадрат требует одного умножения и 2-х возведений в квадрат 64-битовых чисел.
1.6. Возведение в степень (дихотомический алгоритм)
Этот алгоритм использует процедуры возведения в квадрат и умножения, описанные в пунктах 1.4 и 1.5. Пусть требуется возвести число x в степень y. Представим y в двоичном виде:
.
Тогда 
.
Существуют две основных разновидности дихотомического алгоритма.
1. Алгоритм «справа налево»:
Вход: x, y=(yn-1,…,y0)2, z=0, q=1.
1. Если y0=1, то z:=1, q:=x.
2. В цикле: 
выполняем:
a) q:=q2; б) если yi=1, то z:=z×q.
Выход: z.
y | 1 | 0 | 0 | 1 | 1 |
q | x16 | x8 | x4 | x2 | x |
z | x19 | x3 | x3 | x3 | x |
Пример. y=19=(10011)2;
Всего в таком алгоритме n+ω(y) умножений. Сложность данного алгоритма составляет в среднем 3/2 log y.
2. Алгоритм «слева направо»:
Вход: x, y=(yn-1,…,y0)2, z=x.
1. В цикле: 
выполняем:
a) z:=z2; б) если yi=1, то z:=z×x.
Выход: z.
y | 1 | 0 | 0 | 1 | 1 |
z | x | x2 | x4 | x9 | x19 |
Пример. y=19=(10011)2.
Задания к разделу 1
Разработать класс 128-битных чисел. Реализовать операции над объектами класса:
· сложение чисел a и b по заданному модулю m. При этом числа a, b и m – 128–битные; следует использовать вспомогательную переменную d, состоящую из трех 64-битных частей (старшая часть используется для хранения бита переноса); сначала вычисляется сумма d=a+b (см. пункт 1.1), а затем эта сумма берется по модулю: d mod m (см. пункт 1.3);
· вычитание числа b из a по заданному модулю m; при этом возможны варианты b£a и b>a; a, b, m – 128-битные числа (см. п. 1.2 и 1.3);
· умножение чисел a и b по заданному модулю m; при этом числа a, b и m – 128–битные. Следует использовать вспомогательную переменную y, состоящую из четырех 64-битных частей. Сначала вычисляется произведение y=ab (см. пункт 1.4), а затем результат берется по модулю: y mod m (см. пункт 1.3).
· вычисление остатка от деления (см. пункт 1.3).
· возведение в квадрат по заданному мод.3).
· возведение в степень по заданному мод.3).
Тесты для самопроверки к разделу 1
Данными тестами самопроверки следует пользоваться следующим образом. Тест следует проводить в два этапа:
1) проверить арифметические операции на таблице малых чисел.
2) проверить арифметические операции на таблице больших чисел.
Арифметические операции следует проверять в следующем порядке: сложение, вычисление остатка от деления, умножение, возведение в квадрат, возведение в степень.
128-битные числа a и b подаются в программу на вход, а данные в колонках «a+b», «ab mod m», «a mod b», «a2», «ab» - это результаты которые должна вернуть программа при данных операциях (т. е. на основе этих данных следует делать вывод о корректности, реализованной операции). Следует отметить, что в таблице числа записаны в виде пары целых чисел, разделенных знаком «;», например запись «0 ; 210» значит, что 0 – это старшая, а 210 – это младшая часть числа.
Таблица малых чисел:
a | b | m | a+b | ab | a mod b | a2 | ab |
0 ; 51 | 0 ; 7 | 1 ; 0 | 0 ; 58 | 0 ; 357 | 0 ; 2 | 0 ; 2601 | 0 ; |
0 ; 78 | 0 ; 5 | 1 ; 0 | 0 ; 83 | 0 ; 390 | 0 ; 3 | 0 ; 6084 | 0 ; |
0 ; 36 | 0 ; 4 | 1 ; 0 | 0 ; 40 | 0 ; 144 | 0 ; 0 | 0 ; 1296 | 0 ; 1679616 |
0 ; 12 | 0 ; 8 | 1 ; 0 | 0 ; 20 | 0 ; 96 | 0 ; 4 | 0 ; 144 | 0 ; |
0 ; 55 | 0 ; 3 | 1 ; 0 | 0 ; 58 | 0 ; 165 | 0 ; 1 | 0 ; 3025 | 0 ; 166375 |
0 ; 10 | 0 ; 11 | 1 ; 0 | 0 ; 21 | 0 ; 110 | 0 ; 10 | 0 ; 100 | 0 ; |
0 ; 21 | 0 ; 10 | 1 ; 0 | 0 ; 31 | 0 ; 210 | 0 ; 1 | 0 ; 441 | 0 ; |
0 ; 5 | 0 ; 12 | 1 ; 0 | 0 ; 18 | 0 ; 60 | 0 ; 5 | 0 ; 25 | 0 ; |
0 ; 71 | 0 ; 2 | 1 ; 0 | 0 ; 73 | 0 ; 142 | 0 ; 1 | 0 ; 5041 | 0 ; 5041 |
Таблица больших чисел:
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 |
