Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Случайность и закономерность




Понятие последовательности даётся в элементарной математике. Однако в ней изучаются, детерминированны последовательности – они однозначно восстанавливаются по их нескольким элементам.

Так, арифметическая и геометрическая прогрессии восстанавливаются по любым двум своим подряд идущим членам.

Значения многочлена в целых точках также образуют детерминированную последовательность: она определяется любыми n+1 своими членами, где nстепень данного многочлена.

Но существуют последовательности, называемые случайные.

Для них, в отличие от детерминированных нельзя определить очередной член последовательности, зная предыдущие.

Опишем простейший способ получения двоичной случайной последовательности.

Пусть мы подбрасываем «правильную» монету. В зависимости от того, как она падает, полагаем очередной член последовательности равным 0 (орел) или 1 (решка). Как показывает опыт, обычно нельзя угадать, как монета упадет в очередной раз. Однако, если подбрасывать монету достаточно долго, примерно в половине случаев выпадет орел, а в половине – решка.

Говорят, что монета падает случайным образом, причем в каждом подбрасывании с одинаковой вероятностью1/2 выпадает орел (0) или решка (1).

Однако бывают ситуации («кривая монета»), когда орел и решка выпадают с разной вероятностью – ри qсоответственно (р≠q).Отметим, что р+q=1.

В случайной двоичной последовательности, полученной на основе подбрасывания «кривой монеты», рможно считать частотой появления нуля, а qчастотой появления единицы.

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

Изучение случайных и неслучайных двоичных последовательностей имеет важное значение для криптографии.

Например, выявление закономерностей в шифрованных сообщениях очень полезно при вскрытии шифра.

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

Другой Пример – это активно изучаемый в современной теоретической криптографии гипотетический объект – псевдослучайный генератор.

При изучении этого объекта используются многочисленные результаты теории сложности алгоритмов и исчислений.

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

Близким по духу, но более простым и хорошо известным, особенно для программистов, является такой объект, как датчик случайных чисел. Это – некоторое устройство или программа, которая вырабатывает псевдослучайные последовательности.



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

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

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

Опишем, простейший датчик, предложенный в 1949 году Д.Х. Лемером - линейного конгруэнтного метода.

Для заданного начального числа а0он вырабатывает бесконечную последовательность натуральных чисел{ak} по рекуррентному закону:

аk=d+ak-1 ∙ I (modN).

Здесь параметры датчика d,l,Nнекоторые целые числа.

Запись a=b(modN), означает, что (а–b)делится на число N; в данном случае в качестве аk берется остаток от деления( d+ak-1 ∙ I)на N.

Поскольку все члены последовательности {ak} – неотрицательные целые числа, не превосходящие (N–1), то среди них найдутся два одинаковых, скажем аi,- и аi+t.Тогда: аk=d+ak+t для k≥i, т.е. последовательностьпериодическаяс длиной периода t.

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

Следует отметить, что «хорошей во всех отношениях случайной последовательности» практически не существует.

Насколько «хорошей» является случайная последовательность, зависит от ее назначения.



Алгоритм и его сложность

Алгоритмэто одно из основных понятий в программировании и вычислительной математике.

Понятие Алгоритма очень долго оставалось интуитивным понятием. Только в 30-е годы XX века в работах выдающихся математиков А. Черча, Д.Гильберта, , С. Клини, Э. Поста и А. Тьюрингабыли предложены формальные определения алгоритма на основе понятия рекурсивной функции и на основе описания алгоритмического процесса.

Тем самым сформировалась теория алгоритмов – новое направление в математике, которое стало впоследствии теоретической основой развития вычислительной техники.

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

 

Под АЛГОРИТМОМ понимают:

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

В процессе выполнения алгоритма могут возникать новые данные:

- либо как результат преобразования исходных данных;

- либо как результат осуществления случайного выбора на каком-либо шаге алгоритма;

- либо как результат выполнения (вычислителем) измерений параметров окружения (внешних объектов).

АЛГОРИТМ выполняется некоторым субъектом- ВЫЧИСЛИТЕЛЕМ.

Пример АЛГОРИТМА:

- шифрование данных,

- вычисление односторонних функций.

На неформальном языке под Алгоритмом понимают четко описанную последовательность действий, приводящую к определенному результату.

Такой вид деятельности, как программирование – это постоянная работа с алгоритмами.

Очень важным понятием в математике является сложность алгоритма.

Если алгоритм проводит серии вычислений, сложностью алгоритма можно считать число совершаемых операций.

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

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

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

Индивидуальная задача характеризуется некоторым размером,т.е. объемом входных данных, требуемых для описания этой задачи.

Если размер индивидуальной задачи – некоторое натуральное число п, тогда сложность алгоритма решения массовой задачи становится функцией отn.

Приведем два примера.

1. Рассмотрим алгоритм простого перебора всех двоичных Ключей длины n.Ясно, что таких ключейn2, и поэтому в данном алгоритме n2 шагов, т.е. его сложность равна 2».

Это – простейший пример экспоненциальногоалгоритма (его сложность выражается через nэкспонентой). Большинство экспоненциальных алгоритмов – это просто варианты полного перебора.

2. Рассмотрим теперь алгоритм умножения столбиком двух n-значных чисел. Он состоит из n2умножений однозначных чисел, т.е. его сложность, измеренная количеством таких умножений, равна n2.

Это – простейший пример полиномиальногоалгоритма (его сложность выражается через nполиномом).

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

Можно сказать в новых терминах, что стойкость шифра – это сложность задачи его вскрытия.

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

Шифры замены и перестановки


В своей работе «Математическая теория секретной связи» Клод Шеннон обобщил накопленный до него опыт разработки шифров.

Оказалось, что даже в сложных шифрах в качестве типичных компонентов можно выделить шифры замены, шифры перестановкиили их сочетания.

Эти шифры можно считать как бы базовыми.

Шифр замены

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

При шифровании заменой (подстановкой) символы шифруемого текста заменяются символами того же или другого алфавита с заранее установленным правилом замены. В шифре простой замены каждый символ исходного текста заменяется символами того же алфавита одинаково на всем протяжении текста.

Шифр замены является простейшим, наиболее популярным шифром. Примерами являются: шифр Цезаря, «цифирная азбука» Петра Великого и «пляшущие человечки» А. Конан-Дойля.

Шифр замены осуществляет преобразование замены букв или других «частей» открытого текста на аналогичные «части» шифрованного текста.

Увеличив алфавиты, т.е. объявив «части» буквами, можно любой шифр замены свести к замене букв.

Дадим математическое описаниешифра замены.

Пусть: Xалфавит открытого текста, а Y - алфавит шифрованного текста, состоящие из одинакового числа символов.

Пусть также: g : X Y взаимнооднозначное отображение Xв Y. Каждой буквехалфавита Xсопоставляется однозначно определенная буква у алфавита Y , которую обозначаем символом g(х),причем разным буквам сопоставляются разные буквы.

Тогда шифр замены действует так: открытый текст x1x2...xn преобразуется в шифрованный текст g1)g(x2)...g(xn).

В криптографии рассматриваются 4 типа замены:

• моноалфавитная;

• гомофоническая;

• полиалфавитная;

• полиграммная.

Моноалфавитная замена

При данном методе каждой букве алфавита открытого каждому символу алфавита открытого текста ставится в соответствие один символ зашифрованного текста (из этого же алфавита).

Общая формула моноалфавитной замены выглядит следующим образом:

yi=(k1xi+k2)mod n,

Примером этого метода является шифр под названием Атбаш.

Правило шифрования состоит в замене i- ой буквы алфавита буквой с номером n= i + 1, где n — число букв в алфавите. Пример для латинского алфавита выглядит так:

Исходный текст: abcdefghijklmnopqrstuvwxyz

Зашифрованный текст: ZYXWVUTSRQPONMLKJIHGFEDCBA

Гомофоническая замена

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

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

Полиграммная замена

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

Полиалфавитные подстановки

Для повышения стойкости шифра используют так называемые полиалфавитные подстановки, которые для замены используют несколько алфавитов шифротекста.

Известно несколько разновидностей полиалфавитной подстановки, наиболее известными из которых являются:

· одноконтурная (обыкновенная и монофоническая)

· и многоконтурная.

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

Сам процесс шифрования осуществляется следующим образом:

1. Под каждой буквой шифруемого теста записываются буквы ключа. Ключ при этом повторяется необходимое число раз;

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

3. Полученный текст может разбиваться на группы по несколько знаков.

Частным случаем рассмотренной полиалфавитной замены является так называемая монофоническая замена.

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

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

Шифр перестановки

Шифр перестановки, осуществляет преобразование перестановки букв в открытом тексте.

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

Ключом шифра перестановки является перестановка номеров символов открытого текста.

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

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

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

Типичным и древнейшим примером шифра перестановки является шифр «Сциталь».

Алгоритм шифра: открытый текст разбивается на отрезки равной длины, и каждый отрезок шифруется (т.е. в нем переставляются буквы) независимо.

Математическое описание шифра перестановки

Пусть, длина отрезков равна n,

σвзаимнооднозначное отображение множества {1,2, ..., n} в себя.

Тогда шифр перестановки действует так:

- отрезок открытого текста x1...xn преобразуется в отрезок шифрованного текста xσ(1)...xσ(n).

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

Легко запоминать отображения «небольших» размеров, отображения, реализуемые каким-нибудь предметом (сциталь в шифре «Сциталь» и т.п.). Для отображения «большого» размера, процесс запоминания сильно усложняется.

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

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

Популярным способом запоминания отображения σ, т.е. шифра перестановки, является следующий:.

Пусть, например,n=20. Берем прямоугольную таблицу размера 4x5, вписываем в нее открытый текст «по строкам», а шифрованный текст считываем «по столбцам». Возможны и более хитрые способы вписывания и считывания.

Пример. Запишем фразу «это маршрутная перестановка» в прямоугольную таблицу размером 3×9, двигаясь по строкам, слева направо и пропуская пробелы (см. рис.2).

Пример маршрутной перестановки

Э т о м а р ш р у

Т н а я п е р е с

Т а н о в к а

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

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

Виды шифров перестановки

· Простая перестановка;

· Перестановка с усложнением по таблице;

· Перестановка с усложнением по маршруту.

Простая перестановка

Алгоритм шифрования:

1. Выбирается количество с неповторяющимися символами значений ключа;

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

3. Зашифрованный текст выписывается блоками (колонками) в той последовательности, в которой символы размещены в алфавите.

Усложненная перестановка по таблице

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

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

При шифровании текста в пустые клетки не заносятся символы текста и в зашифрованный текст из них не записываются никакие символы - они просто пропускаются.

При расшифровке символы зашифрованного текста также не заносятся в пустые клетки.
Для дальнейшего увеличения криптостойкости шифра можно в процессе шифрования менять:

· ключи,

· размеры таблицы перестановки,

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

Шифр перестановки с усложнением по маршрутам: понятие, примеры.

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

Струкрура трехмерного гиперкуба:

Номера вершин куба определяют последовательность его заполнения символами шифруемого текста при формировании блока. В общем случае n-мерный гиперкуб имеет n2 вершин.

Маршруты Гамильтона имеют вид:

Последовательность перестановок символов в шифруемом блоке для первой схемы 5-6-2-1-3-4-8-7, а для второй 5-1-3-4-2-6-8-7. Аналогично можно получить последовательность перестановок для других маршрутов: 5-7-3-1-2-6-8-4, 5-6-8-7-3-1-2-4, 5-1-2-4-3-7-8-6 и т.д.

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

Стойкость простой перестановки однозначно определяется размерами используемой матрицы перестановки. Например, при использовании матрицы 16*16 число возможных перестановок достигает 1.4E26. Такое число вариантов невозможно перебрать даже с использованием ЭВМ. Стойкость усложненных перестановок еще выше. Однако следует иметь в виду, что при шифровании перестановкой полностью сохраняются вероятностные характеристики исходного текста, что облегчает криптоанализ.

Абсолютно стойкий шифр

Единственным таким абсолютно стойким шифромявляется любая форма так называемой ленты однократного использования.

В ленте однократного использованияоткрытый текст «объединяется» с полностью случайным ключом такой же длины. Этот результат был доказан К. Шенноном с помощью разработанного им теоретико-информационного метода исследования шифров.

Оособенности строения абсолютно стойкого шифра и возможности его практического использования.

Типичным и наиболее простым примером реализации абсолютно стойкого шифра является шифр Вернама.

Шифр Вернама осуществляет побитовое сложение

n-битовогооткрытого текстаи nбитового ключа:

yi=x1⊕ki, i=1,...,n.

Здесь : x1...xnоткрытый текст, k1...knключ,

y1...ynшифрованный текст;

Символы складываются по таким правилам:

0⊕0=0, 0⊕1=1⊕0=1, 1⊕1=0.

Для абсолютной стойкости существенным является каждое из следующих требований к «ленте однократного использования»:

1) полная случайность (равновероятность) ключа (это, в маетности, означает, что ключ нельзя вырабатывать с помощью какого-либо детерминированного устройства;
2) равенство длины ключа и длины открытого текста;
3) однократность использования ключа.

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

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

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

А это сделать необычайно трудно и дорого.

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


Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!