WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |
Министерство образования Российской Федерации Санкт-Петербургский государственный институт точной механики и оптики (технический университет) А. Г. Коробейников Математические основы криптографии Учебное пособие Санкт-Петербург 2002 2 2 УДК 511 Коробейников А. Г. Математические основы криптографии. Учебное пособие. СПб: СПб ГИТМО (ТУ), 2002. 41 с В учебном пособии представлен материал, необходимый для начального введения в теорию криптографичесих алгоритмов. Это в первую очередь теория групп, теория колец, теория полей и прикладная теория чисел. В каждом разделе рассмотрены примеры на соответствующие темы.

Предназначено для студентов, обучающихся по специальности 0754 "Комплексная защита объектов информатизации".

Илл. – 3, список литературы – 9 наим.

© Cанкт-Петербургский государственный институт точной механики и оптики (технический университет), 2002 © А.Г. Коробейников 2002 3 3 ВВЕДЕНИЕ Математические методы, используемые в криптографии, невозможно успешно освоить без знания таких алгебраических структур, как группы, кольца и поля. Поэтому знание и умение работать с этими объектами является необходимым условием для подготовки специалистов в области защиты информации.

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

В первой части введены базовые определения и понятия теории множеств, рассмотрено понятие "отображение" и определены бинарные отношения.

Во второй части изучаются основные свойства, присущие целым числам.

В третьей части рассмотрены различные множества с последующим определением на них бинарных операций. Определены понятия полугрупп и моноидов.

В четвертой части определены и рассмотрены основные положения теории групп. Кратко изучены симметрическая и знакопеременная группа.

В пятой части рассмотрены основные правила взаимодействия между группами.

В шестой части определено понятие математического кольца, рассмотрены общие свойства колец. Построено кольцо классов вычетов. Определены правила отображений из одного кольца в другое. Рассмотрены различные типы колец.

В седьмой части определено понятие математического поля, рассмотрены его общие свойства. Кратко изучены поля Галуа.

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

Каждая часть сопровождается соответствующими примерами.

1. МНОЖЕСТВА И ОТОБРАЖЕНИЯ 1.1. МНОЖЕСТВА Математическое понятие множество является одним из центральных во всей математике. Оно определяется в зависимости от задач.

Примером может служить группа аксиом, известная как система NGB (по имени авторов – Джона фон Нейман, Поля Бернайса, Курта Геделя). Главная идея, положенная в основу NGB, заключается в различении понятий множества и класса. Все объекты NGB являются классами. Класс соответствует нашему интуитивному пониманию совокупности. Множеством являются те классы, которые являются элементами других классов. Классы, не являющиеся множествами, называются собственными классами.

Существует другая группа аксиом – система ZF (по имени авторов – Эрнста Цермело и Абрахама Френкеля). Это теория построимых множеств, т.е. множество строится из некоторых простых, с помощью таких операций, как пересечение, объединение, дополнение и т.д.

Мы будем понимать под множеством любую совокупность объектов, называемых элементами множества. Множества с конечным числом различных элементов могут быть описаны путем явного перечисления всех элементов. Обычно эти элементы заключаются в фигурные скобки.

Например, {16,32,64} – множество степеней двойки, заключенных между 10 и 100. Множество обозначается прописной буквой какого-либо алфавита, а его элементы – строчными буквами того же или другого алфавита.

Для некоторых особо важных множеств приняты стандарные обозначения, которых следует придерживаться. Так, буквами N, Z, Q, R обозначают соответственно множество натуральных чисел, множество целых чисел, множество рациональных чисел и множество вещественных чисел.

При заданном множестве S включение aS указывает на то, что a – элемент множества. В противном случае записывают aS. Говорят, что S – подмножество T или ST (S содержится в T), когда имеет место импликация:

xS, x xT.

Два множества совпадают (или равны), если у них одни и те же элементы. Символически это записывается в виде:

S=T ST и TS.

Пустое множество, т.е. множество, не содержащее ни одного элемента, по определению входит в число подмножеств любого множества.

Под пересечением двух множеств S и T понимают множество ST={x| xS и xT}, а под их объединением – множество ST={x| xS или xT}.

Пусть X и Y – произвольные множества. Пару (x,y) элементов xX, yY, взятых в данном порядке, называют упорядоченной парой, считая при этом, что (x1,y1)=(x2,y2) тогда и только тогда, когда x1=x2, y1=y2.

Декартовым произведением двух множеств X и Y называется множество всех упорядоченных пар (x,y):

XY={(x,y)|xX, yY}.

Пример 1. Пусть, R – множество всех вещественных чисел. Тогда декартов квадрат R2=RR есть просто множество всех декартовых координат на плоскости относительно заданных координатных осей.

Аналогично можно ввести декартово произведение X1X2X3 трех, четырех и т.д. множеств. При X1=X2=X3=…=Xk=X cокращенно пишут Xk=X1X2X3…Xk и говорят о k-й декартовой степени множества X.



Элементами Xk являются последовательности, или строки (x1,x2,…xk) длины k.

1.2. ОТОБРАЖЕНИЯ Понятие отображения или функции также является одним из центральных в математике. При заданных X и Y отображение f с областью определения X и областью значений Y сопоставляет каждому элементу xX элемент f(x)Y. Символически отображение записывается в виде f:XY. Образом при отображении f называется множество всех элементов вида f(x):

Im f = {f(x)|xX}=f(X)Y.

Множество f-1(y) = {xX|f(x)=y} называется прообразом элемента yY.

Отображение f:XY называется сюръективным, или отображением на, когда Im f=Y.

Отображение f:XY называется инъективным, когда из xx' следует f(x)f(x').

Отображение f:XY называется биективным, или взаимно однозначным, если оно одновременно сюръективно и инъективно.

Равенство f=g двух отображений означает по определению, что их соответствующие области совпадают.

Пример 2. Пусть R+ – множество положительных вещественных чисел. Тогда отображения f:RR, g:RR+, h:R+R+, определенные одним и тем же правилом xx2, все различны: f – ни сюръективно, ни инъективно, g – сюръективно, но не инъективно, а отображение h – биективно. Таким образом, задание области определения и области значений – важная часть определения отображения.

Единичным или тождественным отображением eX:XX называется отображение, переводящее каждый элемент xX в себя.

Отображение f-1 является обратным к f, если f(x)=y f-1(y)=x.

1.3. БИНАРНЫЕ ОТНОШЕНИЯ Для любых двух множеств X и Y всякое подмножество OXY называется бинарным отношением между X и Y (или просто на X, если X=Y).

Бинарное отношение ~ на X называется отношением эквивалентности, если для всех x, x1, x2X выполнены условия:

i. x~x (рефлексивность);

ii. x~x1 x1~x (симметричность);

iii. x~x1, x1~x2 x2~x (транзитивность).

Подмножество H={x'X|x'~x}X всех элементов, эквивалентных данному x, называется классом эквивалентности, содержащим x.

Так как x~x (i), то x'H. Любой элемент x'H называется представителем класса H.

Справедливо следующая теорема.

Теорема 1. Множество классов эквивалентности по отношению ~ является разбиением множества X в том смысле, что X является объединением непересекающихся подмножеств.

Доказательство. В самом деле, так как xH, то X=Hi. Далее, класс H однозначно определяется любым своим представителем, т.е.

Hi=Hj xi~xj. В одну сторону: xi~xj и xHi x~xix~xjxHjHiHj.

Но xi~xjxj~xi (ii). Поэтому выполнено и обратное включение HjHi.

Значит Hj=Hi. В другую сторону: так как xH, то Hi=H xHix~xi.

Если теперь HjHi и xHjHi, то x~xi и x~xj, откуда в силу транзитивности (iii) имеем xi~xj и Hj=Hi. Значит, различные классы не пересекаются. Теорема доказана.

Пример 3. Пусть V=R2 – вещественная плоскость с прямоугольной системой координат. Тогда, взяв за свойство ~ принадлежность точек P, P'V одной горизонтальной прямой, получим отношение эквивалентности с классами – горизонтальными прямыми (рис. 1).

Гиперболы Гp (рис. 2) вида xy=p>0 определяют отношение эквивалентности в области V+V точек P(x,y) c координатами x>0, y>0.

y y P' P Гp x l x Рис. 1. Рис. 2.

2. ОСНОВНЫЕ СВОЙСТВА ЦЕЛЫХ ЧИСЕЛ Задачей этой части является краткое описание тех простейших свойств делимости целых чисел, на которые по разным поводам будем ссылаться в дальнейшем.

2.1. ОСНОВНАЯ ТЕОРЕМА АРИФМЕТИКИ Целое число s называется делителем (или множителем) целого числа n, если n=st для некоторого tZ. В свою очередь n называется кратным s. Делимость n на s обозначается символом |. Делимость – транзитивное свойство на Z. Целое число p, делители которого исчерпываются числами ±p, ±1 (несобственные делители), называется простым.

Обычно в качестве простых берутся положительные простые числа > 1.

Фундаментальную роль простых чисел вскрывает так называемая основная теорема арифметики.

Теорема 2. Каждое положительное целое число n1 может быть записано в виде произведения простых чисел: n=p1p2p3…pS. Эта запись единственна с точностью до порядка сомножителей.(Без доказательства) Собрав вместе одинаковые простые множители и изменив обозначения, получим запись n в виде: n=p11p22p33…pSS.

Теорема 3 (Евклида) гласит, что множество P={2,3,5,11,13,…} всех простых чисел бесконечно. Действительно, если бы существовало бы лишь конечное число простых чисел, например p1p2…pk, то по основной теореме число c=p1p2…pk+1 делилось бы по крайней мере на одно из pi.

Без ограничения общности считаем c=pic'. Тогда p1(c'-p2…pk)=1, а это невозможно, поскольку делителями единицы в Z являются лишь ±1, что и требовалось доказать.

2.2. АЛГОРИТМ ДЕЛЕНИЯ В Z При заданных a,bZ, b>0, всегда найдутся q,rZ такие, что a=bq+r, 0 r < b (если считать лишь b0, то будет выполнено неравенство 0 r <|b|).

В самом деле, множество S={a-bs|sZ,a-bs0}, очевидно, не пусто (например, a-b(-a2)0). Стало быть, S содержит наименьший элемент.

Обозначим его r=a-bq. По условию r0. Предположив rb, мы получили бы элемент r-b=a-b(q+1)S, меньший, чем r. Это противоречие устраняется лишь при r

Проведенное несложное рассуждение дает алгоритм для нахождения частного b и остатка r за конечное число шагов.

Алгоритм деления в Z можно также использовать для определения наибольшего общего делителя (НОД), известного из школьного курса математики. Именно, при заданных целых числах n, m, одновременно не равных нулю, положим J={nu+mv|u,vZ}.





Выберем в J наименьший положительный элемент d=nu0+mv0. Используя алгоритм деления, запишем n=dq+r, 0r

Пусть теперь d' – любой делитель чисел n и m. Тогда d'|n, d'|m d'|nu0, d'|mv0 d'|(nu0+mv0) d'|d.

Итак, d обладает всеми свойствами НОД, и поэтому d=НОД(|n,m).

Мы пришли к следующему утверждению.

Наибольший общий делитель двух целых чисел n,m, не равных одновременно нулю, всегда записывается в виде НОД(n,m)=nu+mv; u,vZ.

В частности, целые числа n,m взаимно просты тогда и только тогда, когда nu+mv=1 при некоторых u,vZ.

Для доказательства этого утверждения нужно взять любой положительный элемент из множества J, а затем уменьшать его при помощи алгоритма деления до тех пор, пока не получится наименьший элемент, который и будет наибольшим общим делителем.

В дальнейшем нам понадобится так называемая функция Эйлера (:NN). Она определяется следующим образом. Если натуральное число n делится в точности на k различных простых чисел p1,p2,…pk, то количество чисел, меньших n и взаимно простых с n, равно (n)=n(1-1/p1)(1-1/p2)…(1-1/pk).

Пример 4. n =1155; p1=3; p2=5; p3 =7; p4 =11.

(n)=1155(1-1/3)(1-1/5)(1-1/7)(1-1/11)=480.

3. МНОЖЕСТВА С АЛГЕБРАИЧЕСКИМИ ОПЕРАЦИЯМИ 3.1. БИНАРНЫЕ ОПЕРАЦИИ Пусть X – произвольное множество. Бинарной алгебраической операцией (или законом композиции) на X называется произвольное (но фиксированное) отображение :XXX декартова квадрата X2=XX в X.

Таким образом, любой упорядоченной паре (a,b) элементов a,bX ставится в соответствие определенный элемент (a,b) того же множества X.

Иногда вместо (a,b) пишут ab, а еще чаще бинарную операцию на X обозначают каким-нибудь специальным символом: *, °, или +.

На X может быть задано, вообще говоря, много различных операций. Желая выделить одну из них, используют скобки (X,*) и говорят, что операция * определяет на X алгебраическую структуру или что (X,*) – алгебраическая система.

Пример 5. В множестве Z целых чисел, помимо естественных операций +, (сложения и умножения), легко указать получающиеся при помощи + (или -) и "производные" операции: n°m=n+m-nm, n*m=-n-m и т.д. Мы приходим к различным алгебраическим структурам (Z,+),(Z,-), (Z,°) и (Z,*).

Наряду с бинарными алгебраическими операциями не лишены интереса гораздно более общие n-арные операции (унарные при n=1, тернарные при n=3 и т.д.), равно как и их комбинации. Связанные с ними алгебраические структуры составляют специальную теорию универсальных алгебр.

В направлении конструирования разных бинарных операций на множестве X также, очевидно, открывается неограниченный простор фантазии. Но задача изучения произвольных алгебраических структур слишком обща, чтобы она представляла реальную ценность. По этой причине ее рассматривают при различных естественных ограничениях.

3.2. ПОЛУГРУППЫ И МОНОИДЫ Бинарная операция * на множестве X называется ассоциативной, если (a*b)*c=a*(b*c) всех a,b,cX. Она также называется коммутативной, если a*b=b*a. Те же названия присваиваются и соответствующей алгебраической структуре (X,*). Требования ассоциативности и коммутативности независимы. В самом деле, операция * на Z, заданная правилом n*m=-n-m, очевидно, коммутативна. Но (1*2)*3=(-1-2)*3=-(1-2)-1=1*(1*3). Так что условие ассоциативности не выполняется.

Элемент eX называется единичным (или нейтральным) относительно рассматриваемой бинарной операции *, если e*x=x*e для всех xX. Если e' – еще один единичный элемент, то, как следует из определения, e'=e'*e=e. Следовательно, в алгебраической структуре (X,*) может существовать не более одного единичного элемента.

Множество X с заданной на нем бинарной ассоциативной операций называется полугруппой. Полугруппу с единичным (нейтральным) элементом принято называть моноидом.

Элемент a моноида (M,,e) называется обратимым, если найдется элемент bM, для которого ab=ba=e (понятно, что элемент b тоже обратим). Если еще и ab'=e=b'a, то b'=eb'=(ba)b'=b(ab')=be=b. Это дает основание говорить просто об обратном элементе a-1 к (обратимому) элементу aM:aa-1=e=a-1a. Разумеется, (a-1)-1=a.

Пример 6. Пусть – произвольное множество, M() – множество всех отображений в себя. Тогда (M(),•,e) – моноид, где • – естественная композиция отображений, а e – тождественное отображение.

Пример 7. Пусть Mn(R) – множество квадратных матриц nn с вещественными коэффициентами. Тогда (Mn(R),,E) – моноид, где – операция умножения матриц, E – единичная матрица nn.

Пример 8. Пусть nZ={nm|mZ} – множество целых чисел, делящихся на n. Тогда (nZ,+,0) – коммутативный моноид, а (nZ,) – коммутативная полугруппа без единицы (n > 1).

4. ГРУППЫ 4.1. ПОНЯТИЕ ГРУППЫ Моноид G, все элементы которого обратимы, называется группой.

Другими словами, предполагается выполнение следующих аксиом:

(G1) на множестве G определена бинарная операция (x,y)xy;

(G2) операция ассоциативна: (xy)z=x(yz) для всех x,y,zG;

(G3) G обладает нейтральным (единичным) элементом e: e*x=x*e для всех xG;

(G4) для каждого элемента xG существует обратный x-1:x-1*x = x*x-1=e.

Для обозначения числа элементов в группе G (точнее, мощности группы) используются равноправные символы CardG, |G| и (G:e).

Пример 9. GL(n,R) – множество квадратных матриц nn с вещественными коэффициентами с ненулевым определителем. Тогда GL(n,R) – полная линейная группа по операции умножения матриц.

Pages:     || 2 | 3 | 4 | 5 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.