Введение (несколько слов о криптографии)



страница1/4
Дата05.09.2014
Размер0.62 Mb.
ТипДокументы
  1   2   3   4
Г. И. Ивченко

Спецкурс “Случайные отображения”

(весна – 2009, гр. ЗИ-61)



§1.Введение (несколько слов о криптографии).

Криптография – это современная наука, являющаяся теоретической основой решения широкого круга актуальных практических проблем, объединяемых общим термином “защита информации”. О ее значении в современном мире говорит то, что она признается одним из трех критериев уровня научно-технического прогресса (два других – это ядерные и космические технологии).

Криптография – это синтетическая наука, объединяющая в себе алгебру, теорию чисел, теорию информации, комбинаторный и асимптотический анализ, теорию алгоритмов, теорию вероятностей и математическую статистику, теорию автоматов и другие математические и кибернетические направления.

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

С математической точки зрения, объектами изучения криптографии являются дискретные математические модели, т.е. такие, которые описывают реальные системы с конечным (но, как правило, очень большим – и в этом специфика криптографических моделей) числом возможных состояний.

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

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




§2.Отображения

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

Пусть X={x} и Y={y} – два произвольных множества. Отображением множества X в Y называется любое правило (обозначим его символом s), ставящее в соответствие каждому элементу x X некоторый элемент y Y. Это записывается так: Xgif" align=absmiddle hspace=8>Y или (более детально) y=s(x), x X (см. рис. 1). Элемент y Y, в который отображается x, называется образом x-а, а исходный элемент x – прообразом y-ка (при отображении s). спецкурс, рисунок 1.jpg

При этом мы будем предполагать выполненным свойство однозначности отображения: образ всегда только один. Что касается числа прообразов данного y Y, то в общем случае оно никак не ограничивается, в других же случаях на него накладываются те или иные ограничения, что связано уже с конкретным типом отображения.

В криптографических проблемах, как правило, рассматриваются конечные множества. Если объем =n, то говорят об n-множестве и записывают его так: = {1,2,…,n}. Часто множество Y совпадает с X, в этом случае говорят об отображении множества X в себя – именно этот случай мы будем рассматривать далее.

Любое отображение можно записать в виде следующей таблицы:


s = . (2.1)
где в верхней строке перечислены элементы множества , а в нижней – их соответствующие образы при отображении s: = s(k) , k = 1,2,…,n.

Наглядным представлением отображения s служит ориентированный граф , множество вершин которого составляет , а множество ребер (дуг) образовано n дугами (k,), направленными из k в , k = 1,…,n. Число дуг, входящих в вершину k в графе , равно числу прообразов элемента k при отображении s и называется кратностью вершины k.

Граф отображения s естественным образом разбивается на связные компоненты, при этом каждая связная компонента содержит ровно один контур (цикл) и, возможно, подходы к нему. Если какой-то элемент k отображается в себя же: =k (в этом случае говорят, что отображение s оставляет элемент k на месте), то в графе в вершине k имеется петля. Таким образом, петля это цикл длины 1. Вершины графа , лежащие на циклах, называются циклическими, их число для конкретного цикла называется длиной этого цикла.

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

Приведем два важных примера конкретных отображений.

Если на отображение s не накладывается никаких дополнительных ограничений (помимо однозначности), т.е. в нижней строке таблицы (2.1) на каждом месте может стоять любой элемент множества , то мы получаем класс всех однозначных отображений в себя, обозначаемый . Очевидно, число таких отображений =.

Если отображение s взаимно однозначное, т.е. для любого k имеется только один прообраз, то нижняя строка таблицы (2.1) содержит все элементы , как-то переставленные. Число всех перестановок из n элементов равно n!; таким образом, число различных взаимно однозначных отображений множества в себя равно n!. Такие отображения называются подстановками степени n или n-подстановками, множество всех n-подстановок обозначается . Для любой подстановки s ее граф состоит только из циклов, кратности всех вершин равны 1 и все вершины являются циклическими.

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

В теории отображений основной интерес представляют, так называемые, перечислительные задачи, связанные с подсчетом числа отображений заданного класса, обладающих изучаемым свойством. Например, сколько существует n-подстановок, имеющих заданное число циклов, или заданное число циклов определенной длины? Для решения подобных задач весьма эффективным оказался вероятностный подход, впервые примененный В. Л. Гончаровым в его фундаментальной работе “Из области комбинаторики” (Изв. АН СССР, сер. матем., 1944, т.8, №1, с.3-48). В этой работе с помощью вероятностного подхода проведено обстоятельное исследование структуры n-подстановок, включая их асимптотический анализ, когда степень подстановок n принимает большие значения (при n). В настоящее время вероятностный подход успешно применяется при исследовании структуры различных комбинаторных объектов, в том числе и различных типов отображений. Содержание данного спецкурса, в основном, связано с систематическим использованием вероятностного подхода для решения различных (не только перечислительных) задач для n-подстановок.

Опишем общую схему сведения перечислительных задач к вероятностным. Пусть ={s} – некоторый класс отображений множества в себя, и H есть некоторое свойство, которым каждое отображение s может обладать или нет. Подмножество отображений, обладающих свойством H, обозначим (H). Суть вероятностного подхода для определения объема состоит в следующем: на множестве задается равномерная вероятностная мера, приписывающая каждому s вероятность его наблюдения P(s)=. Тем самым получается конструкция случайного отображения. Далее, по классическому определению вероятности, можем записать соотношение



P(s )= . (2.2)
Если мы можем, используя вероятностные методы, вычислить (или хотя бы приближенно оценить) эту вероятность, то мы получаем ответ в виде:
=P(s )). (2.3)
Так перечислительная задача вычисления объема сводится к вероятностной задаче вычисления вероятности случайного события {s )}. Для решения же последней задачи можно использовать мощный аппарат современной теории вероятностей и в особенности ее предельные теоремы. Дело в том, что для криптографических применений особо актуальны ситуации, когда параметр n неограниченно возрастает (n). В этих случаях необходим асимптотический анализ, и предельные теоремы вероятностей как раз и являются эффективным инструментом проведения таких исследований.

§3. Подстановки и их цикловая структура.
Как говорилось выше, n-постановка — это взаимно однозначное отображение множества Xn={1,2,...,N} в себя, класс (множество) всех таких отображений обозначаентся Sn={s}, их число есть |Sn|=n!. Стандартная запись подстановки S имеет вид
, (3.1)
где нижняя строка (s1,s2,...,sn) представляет собой перестановку чисел (1,2,...,n). Отметим нетокорые важные свойства подстановок.

Для подстановок естественным образом определяется их произведение: если s и g — произвольные n-подстановки, то произведение sg есть n-подстановка, которая действует по правилу


, .
Таким образом, произведение sg — это последовательное применение этих отображений (сначала применяется s, затем g). Эта операция ассоциативна: , но, вообще говоря, не коммутативна.

Например, для X={1,2,3} и , имеем



Далее, в множестве Sn имеется единичная подстановка e, оставляющая все элементы Xn на месте: e(k)=e для всех ; для неё таблица (3.1) имеет вид
.
Наконец, каждой подстановке соответствует единственная подстановка такая, что . Например, если X={1,2,3} и , то .

Таким образом, чтобы получить s-1, надо в таблице (3.1) поменять местами нижнюю и верхнюю строки, а затем переставить столбцы так, чтобы верхняя (новая) строка имела обычный вид (1 2 … n).

Тем самым n-подстановки Sn образуют группу, которая называется симметрической группой степени n. Групповые свойства подстановок изучаются в алгебре, мы же будем акцентировать внимание на их комбинаторных свойствах, связанных с цикловой структурой подстановок.

Рассмотрим граф произвольной подстановки. Как уже отмечалось ранее, этот граф состоит из циклов вида


,
который записывается в виде строки (i, j, …, r), называемой циклом подстановки s; длина данного цикла равна числу входящих в него элементов (числу соответствующих вершин в цикле графа); при этом цикл длины 1 имеет вид (i) и соответствует петле в в вершине i. Таким образом, подстановки из Sn могут содержать любой циклы длины j, 1≤jn, и любую подстановкуможно записать в виде произведения её циклов:
(3.2)
Представление (3.2) означает, что подстановка s имеет α1 цикл длины 1 (в графев вершинах - петли), α2 циклов длины 2 и т.д. Например, разложение (3.2) для следующей подстановки степени 7 имеет вид

Говорят, что подстановкапринадлежит цикловому классу , если она содержит αj циклов длины j, 1≤jn. Набор называется цикловой структурой подстановки s. По своему определению, компоненты векторасуть целые неотрицательные числа, удовлетворяющие соотношению

. (3.3)

Подсчет числа подстановок в Sn с теми или иными характеристиками цикловой структуры и составляет круг комбинаторных (перечислительных) задач в теории подстановок, которыми мы и будем заниматься. При этом мы будем систематически использовать вероятностный подход, в соответствии с которым считается, что каждая подстановкаможет наблюдаться с одной и той же вероятностью . В этом случае мы будем говорить о равновероятных (или случайных) n-подстановках.



Для случайной подстановкиеё цикловая структурастановится случайным вектором, и его распределение является основой для вероятностного анализа свойств случайных подстановок. Мы начинаем анализ с вывода распределения векторадля равновероятной n-подстановки.

§4. Распределение цикловой структуры.
Обозначимчисло n-подстановок в цикловом классе, Тогда для случайной подстановки по классическому определению вероятности имеем
, (4.1)
следовательно, ключевую роль в нашей проблематике играют числа. Покажем, что
(4.3)
Рассмотрим разложение (3.2) некоторой подстановкииз циклового класса:

Путем всевозможныхперестановок элементов при сохранении скобок можно получить любую другую подстановку этого класса. При этом, если в цикле длины r сдвигать циклически его элементы, то цикл не изменится, - это можно сделать r способами, значит,вариантов таких перестановок ничего не меняют. Аналогично, перестановки, переводящие полностью элементы из одной скобки в скобки, содержащие такое же число элементов, не дают новых подстановок; для циклов длины r это даетперестановок. Таким образом, всего имеетсяперестановок, не меняющих исходную подстановку. Следовательно,

и мы получаем формулу (4.2).

Замечания.

      1. Представляет интерес вопрос, какой цикловой класс содержит наибольшее число подстановок и каков его объем. Ответ на эти вопросы таков (задача для слушателей):



2) Число очень быстро растет с увеличением n. Так, 10!=3 628 800, 100!≈10158; для вычисленияпри больших значениях n используется формула Стирлинга1

,

Возвращаясь к формуле (4.1), с учетом (4.2) можем записать, что



Если использовать индикатор: то последнее соотношение удобно записывать в более компактном виде:
. (4.3)
Представление (4.3), хотя и дает ответ, но из него трудно извлекать конкретную информацию о свойствах структуры. Для дальнейшего продвижения весьма эффективным является использование аппарата производящих функций.

Введем производящую функцию структуры


,
которая, с учетом (4.3), имеет вид
. (4.4)
Далее мы будем использовать следующее обозначение: если функция f(z) имеет представление в виде степенного ряда

с некоторым положительным радиусом сходимости |z|<R, то для её коэффициентов будем писать
.
Рассмотрим теперь экспоненту:
.
Тогда
. (4.5)
Сравнивая (4.4) и (4.5), можем записать, что
. (4.6)
Это и есть итоговое и удобное для дальнейшего анализа представление для производящей функции цикловой структуры случайной равновероятной n-подстановки.

Представление (4.6) можно записать и в несколько ином виде. Поскольку


,
то, вместо (4.6), для Fn(t1,…,tn) можно записать представление
. (4.7)
Сформулируем полученный результат в виде следующего утверждения.

Теорема 1. Для равновероятной n-подстановки производящая функция её цикловой структуры имеет вид (4.7):
.
Замечание.

как и должно быть!

Соотношение (4.7) является базовым в теории случайных подстановок: из него можно извлечь всю информацию об особенностях и свойствах цикловой структуры n-подстановок, что и будет продемонстрировано в дальнейшем. Но предварительно мы напомним некоторые факты из комбинаторики и теории вероятностей, которые будут необходимы нам в качестве технического аппарата.



Некоторые вспомогательные результаты.

1.Биномимиальные коэффициенты.

множества, называется биноминальным коэффициентом, так как эти числа фигурируют в знаменитой формуле бинома-Ньютона:

Для этих чисел можно использовать следующие представления:



= ==. (5.2)

Эти формулы можно обобщить на случай, когда показатель степени m есть произвольное действительное число. Для этого разложим функцию в окрестности точки =0 в ряд Тейлора:



Сравнивая коэффициенты в (5.3) с (5.2), можно записать, что



= , k=0,1,2,… (5.4)

Формула (5.4) и определяет биноминальные коэффициенты для произвольного действительного α через, так называемую, убывающую факториальную функцию



=t(t-1)…(t-n+1), n≥1, =1. (5.4)

Используя эти формулы, также можем записать разложение





где =t(t+1)…(t+k-1), k≥1, =1, есть, так называемая, возрастающая факториальная функция.

В (5.5) представлены различные записи биноминальных коэффициентов, которые мы в дальнейшем будем использовать.

2. Числа Стирлинга.

Если разложить убывающую факториальную функцию (5.4) по степеням аргумента t:



то коэффициенты этого разложения s(n,k) есть, так называемые, числа Стирлинга первого рода.

Через эти числа записывается также и разложение возрастающей факториальной функции, определённой в (5.5):

Подчеркнём, что s(n,k) =

3. Нам понадобятся также следующие асимптотические (при n→∞) формулы:

где С=0,5772… − постоянная Эйлера,





4. Производящие функции.

При исследовании целочисленных случайных величин (с.в.) удобно использовать аппарат производящих функций (пр.ф.). Напомним, что если с.в. η имеет распределение



P(η=k) = , k=0,1,2…,

то её пр.ф. определяется равенством



() E=.

Она определена по крайней мере для ≤1, а внутри единичного круга аналитична; при этом распределение ℒ(η) и пр.ф. () однозначно определяют друг друга, причём



=/k! , k=0,1,2,

Напомним также следующие важные свойства пр.ф.:




Леонард Эйлер (1707-1783) – математик, механик, физик астроном. Родился в Швейцарии, с 1727 по 1741 и с 1766 работал в Петербургской АН.

1)Если у с.в. η существует конечный момент r-го порядка, то её факториальные моменты =Eη(η-1)…( η-s+1) при sr могут быть вычислены по формулам


(1);

2) Если — независимые целочисленные с.в., то для пр.ф. их суммы = +…+ справедливо соотношение



3) Сходимость последовательности распределений {P( k=0,1,2,…} при n→∞ к распределению P( (т.е. для любого фиксированного k, что символически записывается в виде ℒ, эквивалентна сходимости





Пример. Пусть с.в. η имеет распределение Пуассона с параметром ,что записывается так: ℒ(=П(λ). Тогда

P(η=k)= ,k=0,1,2,…

все моменты существуют и



= , s=1,2…

Известно, что распределение Пуассона однозначно определяется своими моментами, при этом



Сходимость к распределению Пуассона может быть сформулирована и как сходимость соответствующих моментов: если при некотором λ для любого фиксированного s≥0, то ℒ(η(n)) → П(λ).

Аналогичные свойства имеют место и для пр.ф. многомерных с.в. =( c целочисленными неотрицательными компонентами: (=E; при этом независимы тогда и только тогда, когда

(=(().

5. Центральная предельная теорема (ЦТП).

В дальнейшем мы часто будем ссылаться на эту ключевую теорему теории вероятностей, потому мы напомним как её общую формулировку (в форме А.М. Ляпунова  , так и некоторое её важные частные случаи.


Теорема Ляпунова. Пусть дана последовательность серий { 1,2,…, взаимно независимых с.в., имеющих среднее = E, дисперсии =Dи абсолютные моменты =E, . Обозначим

Тогда, если выполнено условие



то при n→∞ нормированная с.в. асимптотически нормальна с параметрами (0,1), т.е.





Замечание. Условие (5.10) называется условием Линдеберга, а соотношение (5.11) кратко записывается так:

ℒ(. (5.12)

Для приложений полезно выделить некоторые следствия этой теоремы.

Следствие 1.Если с.в. ,, … , взаимно независимы и принимают лишь значения 0 и 1, при этом

где = P(, = P(, = 1,то при n→∞





Ляпунов Александр Михайлович (1857-1918) – русский математик и механик.

Следствие 2. Если взаимно независимые с.в. , , … , равномерно ограничены: C, 1, C>0 – некоторая постоянная, и = ∞, когда n ∞, то



  1   2   3   4

Похожие:

Введение (несколько слов о криптографии) iconРеферат состоит: из трех глав, введения и заключения. Введение в котором определяется постановка проблемы. В первой главе говорится о первых источниках посвященным сакским племенам, а во второй несколько слов о кургане и художественной

Введение (несколько слов о криптографии) iconЗанятие 5 Теоретико-числовые алгоритмы в криптографии
Цель. Изучение применяемых в криптографии базовых алгоритмов работы с большими числами
Введение (несколько слов о криптографии) icon1. Теоретические основы криптографии 9 Общие сведения по классической криптографии 9
Цель: дать методы обеспечения конфиденциальности и аутентичности информации, а также методы ее криптоанализа. Задача: подать информацию...
Введение (несколько слов о криптографии) iconНосов В. А. Краткий исторический очерк развития криптографии
Интернет. В данном очерке делается попытка проследить историю криптографии и присутствия в ней математиков. Основное внимание уделено...
Введение (несколько слов о криптографии) icon9. Использование криптографии для обеспечения безопасности передачи данных по сети
Самым распространенным средством для решения этой задачи является использование криптографии. В языке C# для этих целей предусмотрено...
Введение (несколько слов о криптографии) iconAtslēgas vārdi: Stratēģijas, kriptogrāfija, vēsturiskie dokumenti, noslēpums, slepenā informācija, šifrs, atslēga, kontroldarbs, noslēpumainība, anagrammas, alfabēts
Эта дипломная работа знакомит читателя с основными понятиями криптографии и методической разработкой уроков по курсу Введение в криптографию,...
Введение (несколько слов о криптографии) iconНесколько предварительных слов

Введение (несколько слов о криптографии) iconМногозначность слов. Прямое переносное значение слов
Цель: систематизировать знания детей о многозначности слов, прямом и переносном значении слов. Обогащать словарный запас, раскрывая...
Введение (несколько слов о криптографии) icon«Мой друг, мой враг, мой царь, мой раб родной язык»
Это ещё и особая «кладовая», где на различных полочках лежат части слов, готовые слова, глаголы, существительные… Можно взять несколько...
Введение (несколько слов о криптографии) iconНесколько слов о “горизонталях”, диспозитивности и ареалах обитания свободы выбора и суверенитета воли

Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org