Кодирование с полуоткрытым ключем

Для осуществления обратной связи можно воспользоваться блоком «блокнот». Учитель может подобрать проверочный материал или использовать готовые тесты, на которые ученик отвечает в режиме реального времени.

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

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

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

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

Экспериментальные образцы программы имеют неоспоримое преимущество перед существующими и могут быть использованы в учебном процессе.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Агеев В.Н. Электронные учебники и автоматизированные обучающие системы. М., 2001.

2. Вербицкий А.А. Активное обучение в высшей школе: контекстный подход: метод. пособие. М.: Высшая школа, 1991.

3. Методика применения дистанционных образовательных технологий (дистанционного обучения) в образовательных учреждениях высшего профессионального образования Российской Федерации Приказ Минобразования РФ № 4452 от 18.12.2002.

4. Письмо Минобразования России от 21.01.2003 № 43-52-06 / 12 Об электронных изданиях.

5. Приказ Минобразования РФ от 16.06.2000 № 1791 "О создании Объединенного проекта по разработке нормативно--правовых документов и отраслевых стандартов дистанционного обучения".

6. Приказ Минобрнауки № 63 от 1 марта 2005 года «Порядок разработки и использования образовательных технологий».

7. Современные технологии обучения / под ред. Г.В. Борисовой, Т.Ю. Аветовой, Л.И. Косовой. СПб.: 2002.

Н.В. Браташенко, В.И. Кодачигов, Л.К. Кодачигова КОДИРОВАНИЕ С ПОЛУОТКРЫТЫМ КЛЮЧЕМ

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

В качестве кодирующих графов предлагается использовать сильносвязные (плотные) графы, называемые в [2] сплющенными многогранниками.

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

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

7

октаэдр

додекаэдр

гексаэдр а)

икосаэдр

б)

тетраэдр

Рис. 1. Правильные многогранники и их сплющенные представления

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

Сплющиваем не только куб. Например, Радемахер и Теплиц [2] фактически показали что сплющиваемы и все остальные правильные выпуклые многогранники. Их сплющенные: представления в слегка модифицированном виде приведены на рис.1, б.

а)

б)

в)

п=3 п=4 п=5

Рис. 2. п-мерные кубы

Главное достоинство так строящихся моделей - небольшая стандартная длина связей между вершинами. Основной недостаток - большая связность вершин (см. рис. 2).

К-мерные правильные выпуклые многогранники были, по-видимому, впервые описаны Стинхэмом в 1880 году (перевод его работы опубликован в [3]. Он утверждал, что в 4-мерном пространстве таких многогранников 6.

1) 4-мерный куб - аналог тетраэдра ^=5, ^=^=10, dз=5 (5 тетраэдров в качестве 3-мерных граней);

2) 4-мерный куб: d0=16, d1=32, d2=24, d3=8 (8 кубов в качестве 3-мерных граней;

3) 4-мерный 16-гранник: d0=8, d1=24, d2=12, d3=16 (16 3-мерных тетраэдров);

4) 4-мерный 24-гранник: d0=24, dl=d2=96, d3=24 (24 3-мерных октаэдра);

5) 4-мерный 120-гранник: d0=600, d1=1200, d2=320, d3=120 (120 3-мерных додекаэдров);

6) 4-мерный 600-гранник: d0=12, d1=720, d2=1200, d3=600 (600 тетраэдров).

В n-мерном (п>5) пространстве существуют лишь три типа выпуклых многогранников -аналогов тетраэдра, октаэдра и куба.

Здесь d0 , d1 , d2 , d3 ,... - соответственно число вершин, ребер, плоских граней, 3-мерных граней и т.д.

Рис. 3. 4-мерные тетраэдр и октаэдр

Однако, если взять за основу оставшиеся 4 правильных 3 -мерных многогранника, то можно получить и их п-мерные аналоги [4]. В качестве примера на рис.3 представлены так построенные 4-мерные тетраэдр и октаэдр. Сравнивая последнюю фигуру с классификатором на рис.1, замечаем ее близость к икосаэдру. На рис.4 показан 4-мерный додекаэдр.

Рис. 4. 4-мерный додекаэдр

К-мерный куб известен относительно давно. Известны также и его модификации, например обобщенный гиперкуб (см. рис. 5).

Рис. 5. Обобщенный гиперкуб

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

В качестве примера обратимся к 4-мерному кубу. Для наглядности восприятия он еще раз воспроизведен на рис. 6, а. Он же, как было показано выше, может быть представлен как сплющенная фигура на рис. 6, б.

а) б)

Рис. 6. 4-мерный куб

Перенумеруем его вершины в каждом цикле (их, как видно, 4) естественном порядке начиная с верхней левой в каждом цикле.

1 цикл: 1, 2, 3, 4; 3 цикл: 9, 10, 11, 12;

2 цикл: 5, 6, 7, 4; 4 цикл: 13, 14, 15, 16;

Здесь п=16.

Разбиваем исходный текст на 16 одинаковых частей по строкам и столбцам и перемешиваем (тасуем) их в соответствии с выбранным порядком обхода вершин многогранника.

Таковых можно выбрать несколько, например:

1)1, 2, 3, 4, 8, 5, 6, 7, 11, 12, 9, 10, 14, 15, 16, 13;

2)1, 5, 9, 13, 14, 10, 6, 2, 3, 7, 11, 15, 16, 12, 8, 4;

3)13, 14, 10, 9, 5, 6, 2, 1, 4, 3, 7, 8,12, 11, 15, 16;

4)1,13,14, 10,11,15,16, 12, 9, 5,6, 2, 3, 7, 8, 4 и т.д.

Выберем, например, 4-ый.

Перемешиваем части, на которые разбит текст по строкам (их в рассматриваемом случае 16) и столбцам (их тоже 16) в соответствии с подстановкой 1 равной:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 13 14 10 11 15 16 12 9 5 6 2 3 7 8 4

Очевидно, размещение всех 16 частей в порядке, соответствующем нижней строке подстановки делает текст совершенно неузнаваемым.

Выше мы, описали много других кодирующих графов, причем количество вершин их легко увеличивается. Так и рассмотренный выше вариант- это лишь один из вариантов 4-мерного многогранника. На рис. 2, в, например, приведен 5-мерный куб. Число его вершин уже не 16, а 32. Да и порядок обхода его вершин может быть выбран большим числом способов, чем для 4-мерного куба. Выше были предложены и другие варианты кодирующих графов.

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

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

О кодировании перестановок (подстановок). Перестановка - это предписание, указание на то, как надо поменять порядок расстановки элементов некоторого заданного, известного априори упорядоченного множества (кортежа) А. Пусть, например, А таково: А=<2,7,4,8,6,5,1,7,9>; Здесь существенно важно, что 2-1-й элемент, 7-2-й, ..., 9-9-й элемент, то есть, с А естественным образом можно связать кортеж А'=<1,2,3,4,5,6,7,8,9> Подстановка - это разновидность перестановки. Так подстановка

2 7 4 8 6 5 1 7 8

л=

4 3 7 1 2 5 8 6 9

показывает, что А после выполнения подстановки преобразуется в А1=<4,3,7,1,2,5,8,6,9>, а подстановка

2 7 4 8 6 5 1 7 9

л1=

11 13 15 10 16 12 17 18 19 преобразует кортеж В= <2 7 4 8 6 5 1 7 9> в

В = <11 13 15 10 16 12 17 18 19>. Особенность: А и А1 собраны из элементов одного и того же множества (алфавита) А= {1, 2, 3, 4, 5, 6, 7, 8, 9}, аВиВ - из двух разных (ну, или из двух непересекающихся подмножеств одного множества).

Можно сказать, что подстановка л является одноалфавитной, а л1 - 2-х алфавитной. В принципе можно говорить о 3-х алфавитной, 4-х алфавитной и т.д. п- алфавитной (п>3) подстановках. Впрочем, их можно определить и так:

• 3-х алфавитная подстановка - это композиция двух 2-х алфавитных подстановок; .

• п- алфавитная подстановка - это композиция (п-1) 2-х алфавитных перестановок.

Мы ограничимся рассмотрением одноалфавитных подстановок.

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

Пример - перестановка автоморфизма преобразующая граф в автоморфный.

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

1. Алгоритм кодирования должен быть недоступен «злоумышленнику».

2. Алгоритм кодирования является неожиданным и потому непонятным ему.

Ниже предлагается простой алгоритм, основанный на второй посылке. Он выполняется в два этапа.

Д

Первый этап: нормализация и кодирование. Доступ к А закрыт. Вместо А оперируем с -.

Второй этап: декодирование.

Для описания сути первого этапа введем в рассмотрение понятие расстояние i -го элемента а; е А до соответствующего элемента множества ^ -:

^ 1 = 1, I 2=-1, I 3=1, I 4=4, I 5=1, I 6=-1, I 7=-6, ( 8=-1, ( 9=0

< =2, 4=1, 13 =4, 4=-3, ^ -3, 4=-1, =1, =-2, С9 =0 Например, для А1 = <4,3,7,1,2,5,8,6,9>

В результате на первом этапе вместо подстановки

А 2 7 4 8 6 5 1 3 9 a Aj ( 4 3 7 1 2 5 8 6 9 ) b Ar 1 2 3 4 5 6 7 8 9 c

строится новая:

1 -1 1 4 1 -1 -6 -1 0 x1=a-b (2 1 4 -3 -3 -1 1 -2 0) x2=c-b

-2 0 -3 7 4 0 -7 1 0 x3=a-c

Исключив очевидную строку 2 в (2), имеем собственно закодированную подстановку. Код перестановки это следующая запись: А=(1, *1,1,4,1,*1,*6,*1,0;2,1,4,*3,*3,*1,1*2,0). Здесь * - представление минуса.

На втором этапе выполняется декодирование. Предварительно заметим, что известными данными для этого этапа являются строка с в (1) и строки xb x2, x3 в (2). Требуется восстановить строку b, а при необходимости и a в (1).

Для этого достаточно поэтапно выполнить следующие действия:

bj = Cj-x2l

al = xil+bl , i= 1,2,...,n.

Очевидно, что сложность кодирования и декодирования имеет оценку О (n), где n - длина перестановки.

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

Сравнительный анализ основных характеристик разработанной системы с ГОСТом 28147-89. Описанный подход был реализован программно на языке Си на процессоре Pentium III-1000Мгц. Результаты его сравнения с ГОСТом 28147-89 таковы: ГОСТовский алгоритм, реализованный на процессоре Pentium Ш-1000Мщ показал быстродействие шифрования 19 Мбайт/с. Наша же программа при том же процессоре шифровала со скоростью 24 Мбайт/с.

Получение строгих доказуемых оценок криптостойкости для каждого конкретного шифра -проблема нерешенная. Единственным путём для злоумышленника остается подбор ключа (графа) методом перебора всех возможных комбинаций. Легко подсчитать, сколько времени потребуется на взлом получаемого шифра при условии, что злоумышленнику известен алгоритм. Предположим, что подбор графа будет производиться на компьютере с процессором Pentlum III - 1000 МГц: при самой лучшей реализации программы для взлома описанной выше системы возможно сгенерировать не более полумиллиарда потенциальных ключей за секунду. Даже не учитывая значительное время на подстановку ключа и проверку результатов, при использовании графа с тридцати двумя вершинами, нужно будет перебрать 32!=2.63*1035 ключей (правило перестановок без повторений), а это займет примерно 1.7*1019 лет. При использовании кодирующего графа с шестнадцатью вершинами число потенциальных ключей составит 16!=2*1013, на перебор потребуется около 12 часов. Сгенерировать все возможные графы с их обходами - только первый шаг, всё полученные ключи нужно опробовать, а это займет огромное время.

Выводы. Предлагаемый метод позволяет строить криптоалгоритмы, отличающиеся:

• высокой степенью защиты данных;

• высокой скоростью кодирования;

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

• высокой криптостойкостью алгоритмов шифрования.

БИБЛИОГРАФИЧЕСКИМ СПИСОК

1. Пойа Д. Математическое открытие. М.: Наука, 1976. 448 с.

2. Радемахер Г., Теплиц О. Числа и фигуры. М.: ОНТИ, 1936. 236 с.

3. Стинхэм Д. Правильные многомерные выпуклые многогранники // Успехи математических наук, 1944. № 10.

4. Кодачигов В.И. Умозрительные эксперименты со сплющенными и рассплющенными многогранниками // Перспектива, 1995.

О.А. Ефименко, В.В. Кириченко

КОМПЛЕКСНАЯ ИНФОРМАТИЗАЦИЯ КАК ОСНОВА И УСЛОВИЕ ЭФФЕКТИВНОГО ИСПОЛЬЗОВАНИЯ КОМПЬЮТЕРНЫХ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

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

Информатизация образования как одно из приоритетных направлений процесса информатизации современного общества предполагает реализацию возможностей современных информационных технологий, с целью внедрения в практику образования психолого-педагогических разработок, направленных на развитие личности ученика, интенсификацию и интеллектуализацию учебной деятельности, приобщение к современным методам обработки и передачи информации. Реализация идей информатизации образования обеспечивает переход от иллюстративно-объяснительных методов и механического усвоения фактологических знаний к овладению умением самостоятельно приобретать новое знание, пользуясь современными методами представления и извлечения знания, средствами информационного взаимодействия с объектами предметных сред, созданных на базе технологий мультимедиа, "виртуальная реальность", использования возможностей периферийного оборудования современных ЭВМ.

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

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

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

- улучшение качества обучения посредством более полного использования доступной информации;

- повышение эффективности учебного процесса на основе его индивидуализации и интенсификации;

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

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

- интеграцию различных видов деятельности (учебной, учебно-исследовательской, методической, научной, организационной) в рамках единой методологии, основанной на применении информационных технологий;

подготовку участников образовательного процесса к жизнедеятельности в условиях информационного общества;