Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО профессионального образования

ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Институт математики, естественных наук

и информационных технологий

Кафедра программного обеспечения

РАЗРАБОТКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ДЛЯ ФОРМИРОВАНИЯ БАЗЫ ДАННЫХ ДЛЯ ГОСУДАРСТВЕННОЙ ИТОГОВОЙ АТТЕСТАЦИИ 9 КЛАССОВ

Выпускная квалификационная работа

Научный руководитель

старший преподаватель кафедры

программного обеспечения

Зайцева С.С.

Автор работы

Петренко А.А.

Тюмень - 2012г.



Введение

Государственный институт развития регионального образования Тюменской области (ТОГИРРО) - государственное образовательное учреждение дополнительного профессионального образования (повышения квалификации) специалистов. Учредитель - Департамент образования и науки Тюменской области.

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

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



Раздел I. Описание предметной области и постановка задачи

1.1 Общие сведения об организации

Государственный институт развития регионального образования Тюменской области (ТОГИРРО) - государственное образовательное учреждение дополнительного профессионального образования (повышения квалификации) специалистов. Учредитель - Департамент образования и науки Тюменской области.

Цель ТОГИРРО: определение стратегии развития образовательной системы области и ее научно-методическое обеспечение на основе мониторинговых исследований.

Основные задачи института:

• Информационно-аналитическая деятельность.

• Проектно-прогностическая деятельность, обеспечение стратегического развития отрасли.

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

• Организационно-педагогическая деятельность.

13 января 1945 года по просьбе Тюменского исполкома областного Совета депутатов трудящихся был открыт Институт усовершенствования учителей при Тюменском ОблОНО.

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

В начале 90-х годов в области насчитывалось 37 тыс. учителей, более 27 тыс. дошкольных работников. В сентябре 1991 года по решению исполкома Тюменского областного совета народных депутатов на базе областного института усовершенствования учителей открылся институт повышения квалификации педагогических кадров, получивший статус высшего учебного заведения.

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

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

В 2006 году произошло слияние ТОГИРРО и Государственного учреждения Тюменской области «Центр мониторинга качества образования Тюменской области» (ГУ ТО «ЦМКО ТО»), которое занималось проведением стандартизированных процедур оценки достижения учащихся и единого государственного экзамена (ЕГЭ). В связи с этим в структуре ТОГИРРО были созданы отделы организационного и технического обеспечения стандартизированных процедур оценки достижения учащихся (СПОДУ), которым были переданы функции «ЦМКО ТО».

1.2 Отдел технического обеспечения СПОДУ

Отдел технического обеспечения СПОДУ «ТОГИРРО» выполняет следующие функции:

• создание проектов на основе машиночитаемых форм;

• информационно-технологическое сопровождение проведения ЕГЭ;

• создание и ведение региональных баз данных образовательных учреждений;

• создание и ведение баз данных участников ЕГЭ;

• организация обработки данных с бланков ЕГЭ;

• создание и ведение баз данных результатов ЕГЭ по субъекту Федерации;

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

• ведение деловой переписки посредством электронной почты;

• обеспечение безопасности и комплексной защиты информации.

Одной из основных функций отдела является техническое сопровождение процедур проведения репетиционного тестирования в форме ЕГЭ, проведение срезовых контрольных работ (СКР) проводимых Департаментом образования и науки Тюменской области, проведение ЕГЭ.

Эти функции подразумевают выполнение следующих видов работ:

1. Проведение СКР и репетиционного тестирования:

• разработка бланков;

• создание машинопечатных форм для репетиционного тестирования и СКР;

• сканирование и верификация бланков репетиционного тестирования и СКР;

• формирование отчетов о результатах репетиционного тестирования и СКР;

• формирование статистической отчетности репетиционного тестирования и СКР;

2. Проведение ЕГЭ:

• формирование региональной базы участников ЕГЭ;

• распределение участников ЕГЭ по пунктам проведения экзамена;

• обработка бланков ЕГЭ (сканирование, верификация);

• отправка результатов обработки бланков в Федеральный Центр тестирования;

• получение и расшифровка результатов тестирования;

• подведение итогов экзамена и формирование статистической отчетности.

Информация, поступающая в технический отдел СПОДУ:

• Приказы, распоряжения и инструктивные материалы направляются из Департамента образования и Федерального центра тестирования в технический отдел СПОДУ;

• Списки учащихся, учителей, учебной литературы направляются из Муниципального образовательного учреждения (МОУ СОШ) в технический отдел СПОДУ;

• Схемы итоговой аттестации учащихся направляется из Муниципальных органов управления образования (МОУО) в технический отдел СПОДУ;

• Результаты Единого государственного экзамена и Централизованного тестирования из Федерального Центра тестирования направляются в технический отдел СПОДУ.

Информация, выходящая из технического отдела СПОДУ:

• Электронные версии бланков из технического отдела СПОДУ направляются по электронной почте в Федеральный Центр тестирования для последующей обработки и проверки;

• Результаты Единого государственного экзамена и Централизованного тестирования из технического отдела СПОДУ направляются в Муниципальные органы управления образованием и в Муниципальные образовательные учреждения;

• Статистическая отчетность по результатам итоговой аттестации из технического отдела СПОДУ направляется в Федеральное агентство по образованию, Департамент образования и науки Тюменской области и Муниципальные органы управления образования.

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

• Схемы итоговой аттестации учащихся направляются начальнику отдела и администраторам для формирования федеральной базы данных по проведению ЕГЭ (в части организации ППЭ);

• Перед проведением экзаменов административная группа по схеме проведения итоговой аттестации формирует списки учащихся, организаторов в ППЭ;

• После проведения экзамена электронные версии бланков шифруются и автоматически отсылаются в Федеральный Центр тестирования для последующей обработки и проверки;

• После получения результатов ЕГЭ, ЦТ из Федерального Центра тестирования административная группа подготавливает их для рассылки в МОУО и МОУ.

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

1.3 Постановка задачи

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

Программное обеспечение должно включать:

Приложение для РЦОИ - «Приложение Регион». Программа предназначена для создания и сопровождения региональной базы данных учащихся 9-ых классов. Также программа должна формировать файлы базы данных для последующей передачи на нижестоящие уровни (АТЕ, ОУ). Должны быть реализованы следующие функции:

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

· для работы с данными об участниках ГИА, просмотр и редактирование информации, а также для внесения данных о годовых оценках;

· для репликации данных при передаче между приложениями разных уровней: Регион и АТЕ; Регион и ОУ; АТЕ и ОУ;

· для передачи данных в зашифрованном виде;

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

· для просмотра и редактирования информации об административно-территориальной единице;

· формирование отчетных документов в формате xlsx о выбранных экзаменах участниками по АТЕ или ОУ;

· для экспортирования и импортирования данных об административно-территориальной единице в РЦОИ;

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

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

· формирование отчетных документов в формате xlsx о выбранных экзаменах участниками по ОУ;

· для экспортирования и импортирования данных об образовательном учреждении в РЦОИ.



Раздел II Математическое обеспечение

2.1 Правила разрешения конфликта версий. Общие положения.

Введем следующие обозначения состояний записей:

· nil -- с записью ничего не произошло;

· ins -- запись добавлена;

· upd -- запись модифицирована;

· del -- запись помечена на удаление.

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

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

t₁<t₂ & upd₁ & del₂,

где нижний индекс указывает индекс БД, в которой произошло относящееся к ней изменение состояние записи.

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

· nil - ничего не делать;

· ins - добавить запись;

· upd - обновить запись;

· del - пометить запись на удаление.

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

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

t₁<t₂ & upd₁ & del₂  del₁ & nil₂.

Запись следует читать следующим образом: «если изменение в DB₁ произошло раньше, чем в DB₂ и запись была изменена в DB₁ и удалена в DB₂, то необходимо ее пометить на удаление в DB₁ и ничего не предпринимать в DB₂». Левая часть этого выражения состоит из трех предикатов (соотношение моментов времени - это один предикат), объединенных оператором логической конъюнкции. Приведенное правило может сработать только в случае, если все три предиката в левой части выражения истинны.

В общем случае правила для разрешения конфликта версий для N баз данных записываются в виде:

t₁ i₁ t₂ i₂ … i_N-1 t_N & s₁ & s₂ & … & s_N  a₁ & a₂ & … & a_N,

где t_i, i = 1...N - момент времени, в который произошло изменение в БД i;

i_j = {<, >, =} или (), j=1…N-1 - соотношение моментов времени t_j и t_j+1;

s_i, i = 1...N - состояние записи в БД i;

a_i, i = 1...N - действие, которое следует предпринять для разрешения конфликта версий записей в БД i.

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

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

С точки зрения практики решение задачи видится несколько по-иному. Каково бы не было количество баз, количество вариантов этого предиката не превышает 3^N-1, если использовать три вида соотношения времен (<, >, =) и 2^N-1 - если использовать два вида соотношения (). Таким образом, можно закодировать все соотношения моментов времени изменения записи не более чем 3^N-1 значениями, для чего использовать соответствующую функцию. Типы изменения состояний также возможно закодировать, ведь каждая запись может находиться только в одном из состояний. После осуществления этих операций требуется найти такое правило, левая часть которого будет в точности совпадать с полученными кодами.

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

2.2 Схема «Звезда»

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

При рассмотрении схемы синхронизации БД типа «звезда» будем говорить об одновременной синхронизации двух и более баз данных. Например, на рис. 1 синхронизируется состояние трех БД за один сеанс репликации.



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

1. Запись может быть создана только в одной БД. Поэтому предикат ins может присутствовать в левых частях только в единственном экземпляре и сочетаться только с предикатами nil. Максимальное количество таких сочетаний равно количеству БД, состояние которых одновременно синхронизируются.

2. Остальные варианты правых частей формируются путем перебора всех вариантов сочетания предикатов nil, upd и del. Среди них будет ровно один вариант, такой что: nih₁ & nih₂ & ... & nil_N . Этот вариант следует отклонить, как не существующий.

3. Для каждого сгенерированной левой части подсчитаем количество предикатов, которые зависят от времени (upd, del). Если таких предикатов более одного, то такую левую часть следует повторить 3^K-1 раз, если использовать три вида соотношения времен (<, >, =) и 2^K-1 - если использовать два вида соотношения (), где К - количество предикатов, зависящих от времени, сочетая их с полученными вариантами состояний.

Количество левых частей растет пропорционально степенной функции. Если для двух БД количество левых частей импликаций равно 16, то для трех БД уже 114. Случай 2-х БД есть вырожденный случай звезды.

2.3 Схема «Сеть»

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



В этой структуре возможна ситуация, которая изображена на рис. 3. После того, как была выполнена синхронизация БД₁ и БД₃ (Р₁) в БД₁ добавляется новая запись (ins₁). При следующей репликации Р₂ эта запись переносится в БД₂ (ins₂). Затем, при синхронизации состояний БД₂ и БД₃ (Р₃) запись вносится в БД₃. После этого запись модифицируется в БД₁ (upd₁). При разрешении конфликта версий записей при репликации Р₄ получается ситуация, при которой для базы БД₁ запись имеет статус upd, а для БД₃ - ins. Таким образом, для успешного разрешения конфликтов версии в левых частях правил следует предусмотреть ситуацию, в которой символ ins сочетается не только с символом nil, но и с символами upd и del.

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



2.4 Практическая реализация

Пусть требуется обеспечить репликацию данных между двумя базами DB₁ и DB₂. Для построения правил разрешения конфликтов версий записей выберем схему «звезда». Пусть в базе данных DB₁ существует таблица, схематичная структура которой выглядит следующим образом:

RTable1(PK, Data, DBID, RID, ChType, TransTime)

где PK -- первичный ключ;

Data -- данные хранимые таблицей;

DBID -- идентификатор БД, в которой была создана запись;

RID -- идентификатор записи для репликации, который был присвоен при создании записи;

ChType -- код типа изменения, произошедшего с записью, целочисленный тип данных;

Для ChType примем следующую кодировку:

· 0 - с записью ничего не произошло

· 1 - запись внесена;

· 2 -- запись изменена;

· 3 -- запись помечена на удаление.

TransTime -- момент времени, в который произошло изменение записи. Также допустим, что база данных DB₂ также содержит таблицу RTable1 идентичной схематичной структуры с теми же наименованиями атрибутов. Несложно заметить, что этот вариант схематичного представления структуры таблицы эквивалентен Table1. При этом

RK = {DBID, RID}; Ver_Stamp = {ChType, TransTime}

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

Res_Table(time_relation,state1,state2,action1,action2),

где time_relation имеет целочисленный тип и следующую кодировку:

· 1 - t₁ > t₂;

· 2 - t₁ = t₂;

· 3 - t₁ < t₂,

где t₁ и t₂ - моменты изменения состояния записи соответственно в DB₁ и DB₂.

state1 и state2 - состояния, в которых находятся записи в соответствующих базах. Их кодировка совпадает с кодировкой ChType.

action1 и action2 - действия, которые следует предпринять для разрешения конфликта версий записей. Тип данных этих полей, а также их кодировка могут выбираться разработчиком по обстоятельствам. Заполним поля time_relation, state1 и state2 таблицы Res_Table в соответствии с правилами образования левых частей схемы «звезда», а поля action1 и action2 в соответствии с тем, как требуется разрешать конфликт версий записей в том или ином случае. Для распознавания соотношения моментов времени будем использовать следующую функцию:

CREATE FUNCTION time_moment_relation

(time1 datetime,

time2 datetime)

RETURNS int

AS

BEGIN

declare res as int

if time1>time2

begin

select res=1

end

else

begin

if time1=time2

begin

select res=2

end

else

begin

if time1<time2 select res=3

end

end

RETURN res

END

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

Используя указанное ограничение, запрос

Select

DBID,

RID,

ChType,

TransTime

From

DB1.RTable1

Where

(TransTime > SRT)

вернет значения RK и Ver_Stamp всех записей, которые были внесены в таблицу, либо были модифицированы, либо были помечены на удаление с момента SRT. Результат работы этого запроса обозначим через DB1_Change. Для DB2 выполним аналогичный запрос, заменяя DB1 на DB2. Результат работы этого запроса обозначим через DB2_Change.

Для того чтобы найти состояние записи во всех базах сразу следует исполнить запрос вида:

Select

time_moment_relation(DB1_Change.TransTime,DB2_Change.TransTime) as moment_relation

ISNULL(DB1_Change.ChType, 0) as St_DB1,

ISNULL(DB2_Change.ChType, 0) as St_DB2,

DB1_Change.DBID as DBID,

DB2_Change.RID as RID

From

DB1_Change full outer join DB2_Change

On ((DB1_Change.DBID = DB2_Change.DBID) and (DB1_Change.RID = DB2_Change.RID))

Результат этого запроса обозначим через General_State. Следующий запрос выдаст необходимые действия для разрешения конфликта записей:

Select

Res_Table.action1,

Res_Table.action2

General_State.DBID as DBID,

General_State.RID as RID

From

General_State inner join Res_Table on ((General_State.moment_relation = Res_Table.time_relation) and (General_State.St_DB1 = Res_Table.state1) and (General_State.St_DB2 = Res_Table.state2))

Основываясь на результатах этой выборки, следует предпринять конкретные действия по устранению конфликтов версий записей. Если разрешение конфликтов версий завершилось удачей, то вычисляется новое значение для последней успешной репликации SRT1. Далее следует выполнить запрос для DB1 вида:

Update

DB1.RTable1

Set

ChType = 0,

TransTime = SRT1

Where

(TransTime > SRT)



Для DB2 выполним аналогичный запрос, заменяя DB1 на DB2.

2.5 Стандарт AES

Стандарт AES(Advanced Encryption Standard) является стандартом шифрования США, принятым в 2000-ом году. Он специфицирует алгоритм Rijndael. Этот алгоритм представляет собой симметричный блочный шифр, который работает с блоками данных длиной 128 бит и использует ключи длиной 128, 192 и 256 бит (версии AES-128; AES-192 и AES-256). Сам алгоритм может работать и с другими длинами блоков данных и ключей, но эта возможность в стандарт не вошла. При использовании 128-битного ключа для взлома шифрования по заявлению правительства США потребуется 149 триллионов лет. Биты данных нумеруются с нуля, начиная со старших. В AES основным является полиномиальное представлением кодов. Так байт {01100011} следует представлять как: x⁶ + x⁵ + x + 1. Алгоритм AES производит операции над двумерными массивами байт, называемыми структурами (state). Структура состоит из 4 рядов по Nb байт. Nb равно длине блока, деленной на 32 (в данном стандарте Nb=4). Это позволяет обозначать структуру как sr,c или s[r,c], где 0?r<4 и 0?с<4.

Входной код (in), который является последовательностью 16 байт можно представить как:

s[r,c] = in[r +4c]

При реализации алгоритма AES используются операции сложения байт (по модулю 2 = XOR) и умножения. В алгоритме AES при умножении байтов используется неприводимый многочлен

m(x) = x⁸ + x⁴ + x³ + x + 1 [1]



Вычисление произведения М байтов {b1} на {b2} здесь выполняется согласно следующему алгоритму

M=[{b1}?{b2}] mod m(x). [2]

В этом случае обратная величина байта равна

{b}^-1 ={b} mod m(x) [3]

для умножения полубайтов (коды длиной 4 бита) используется неприводимый полином

m2(x) = x⁴ + 1

Вычисление произведения М полубайтов {a} на {b} здесь выполняется следующим образом

M=[{a}?{b}] mod m2(x). [2a]

M представляет собой полубайт d. Операцию умножения полубайтов {a} на {b} можно записать в матричном виде:

[4]

Как было сказано выше длины ключей Nk (длина, измеренная в 32 битных словах) могут принимать значения 4, 6 или 8 (для AES-128, -192 и -256, соответственно). Число итераций Nr (round), реализуемых в алгоритме AES, составляет соответственно 10, 12 и 14.

2.6 Шифрование AES

При запуске алгоритма шифрования входной блок данных копируется в массив state. После первоначального добавления к state ключа массив state преобразуется с помощью функции циклической обработки Nr раз (последний цикл несколько отличается от предыдущих). Результат преобразования заносится в выходной массив. Описание алгоритма в С-подобном представлении отображено на рис. 1. Преобразования SubByte(), ShiftRows(), MixColumns() и AddRoundKey() осуществляют обработку массива state. Массив w[i] описан ниже.

Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])

Begin

byte state[4,Nb]

state = in

AddRoundKey(state, w[0, Nb-1])

for round = 1 step 1 to Nr-1

SubBytes(state)

ShiftRows(state)

MixColumns(state)

AddRoundKey(state, w[round*Nb, (round+1)*Nb-1])

end for

SubBytes(state)

ShiftRows(state)

AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1])

out = state

end

Рис. 1. Псевдокод, реализующий процедуру шифрования



2.6.1 Преобразование SubByte()

Преобразование SubByte() является нелинейной подстановкой байтов, которое работает независимо для каждого байта State и использует таблицу подстановок S. Эта замена включает в себя две операции:

1. Каждый байт заменяется на обратный мультипликативный (см. формулу 3). Байт {00} преобразуется сам в себя.

2. Для каждого байта осуществляется аффинное преобразование в поле GF(2), задаваемое формулой

[1.1]

2.6.2 Преобразование ShiftRows()

В преобразованиях ShiftRows() байты в последних трех рядах State циклически сдвигаются на разное число байт. Первый ряд (r=0) не сдвигается. Преобразование ShiftRows() осуществляется следующим образом

для 0<r<4 и 0?c<Nb [1.3]

где величина сдвига shift(r,Nb) зависит от номера ряда r следующим образом:

shift(1,4)=1; shift(2,4)=2; shift(3,4)=3



2.6.3 Преобразование MixColumns()

Преобразование MixColumns() обрабатывает State колонка за колонкой, каждая из колонок представляет собой 4-битный код. Колонки рассматриваются как полиномы над полем GF(2⁸). Колонка умножается на фиксированный полином {a}={03}x³+{01}x²+{01}x+ {02} по модулю x⁴+1 (см. формулу 2а).

2.6.4 Преобразование AddRoundKey()

В преобразовании AddRoundKey() к State добавляется ключ итерации (Round Key; побитовая операция XOR). Операция производится для каждого байта State.

2.6.5 Процедура расширения ключа

Ключи итерации вычисляются на основе ключа шифрования с помощью процедуры преобразования ключа (Key expansion). Эта процедура формирует Nb(Nr+1) слов. Алгоритм требует Nb слов и каждая из Nr итераций требует Nb слов. В результате получается линейный массив 4-байтовых слов, который обозначается [wi], где i лежит в пределах 0?i<=Nk.

Функция SubWord() работает с входными байтами, преобразуя их с помощью S-таблиц. Операция выполняется для каждого из 4 входных байт.

Функция RotWord() использует в качестве входного слова [a0,a1,a2,a3] и возвращает слово [a1,a2,a3,a0].

KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)], Nk)

Begin

word temp

i = 0

while (i < Nk)

w[i] = word(key[4*i], key[4*i+1], key[4*i+2], key[4*i+3])

i = i+1

end while

i = Nk

while (i < Nb * (Nr+1)]

temp = w[i-1]

if (i mod Nk = 0)

temp = SubWord(RotWord(temp)) xor Rcon[i/Nk]

else if (Nk > 6 and i mod Nk = 4)

temp = SubWord(temp)

end if

w[i] = w[i-Nk] xor temp

i = i + 1

end while

end

end

Рис. 2. Псевдокод реализации процедуры преобразования ключа

2.7 Расшифрование AES

Все процедуры, описанные в предыдущем разделе, являются обратимыми. Целью дешифровки является обработка зашифрованного массива данных с целью получения исходного блока данных. Процедуры дешифровки включают в себя функции InvShiftRows(), InvSubBytes(), InvMixColumns() и AddRoundKey(). Псевдокод для процедуры дешифровки представлен на рис. 3.

InvCipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])

begin

byte state[4,Nb]

state = in

AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1])

for round = Nr-1 step -1 downto 1

InvShiftRows(state)

InvSubBytes(state)

AddRoundKey(state, w[round*Nb, (round+1)*Nb-1])

InvMixColumns(state)

end for

InvShiftRows(state)

InvSubBytes(state)

AddRoundKey(state, w[0, Nb-1])

out = state

end

Рис. 3. Псевдокод процедуры дешифровки

2.7.1 Преобразование InvShiftRows()

Процедура InvShiftRows() является обратной по отношению ShiftRows(). Байты в последних трех рядах State циклически сдвигаются на разное число байт. Первый ряд (r=0) не сдвигается.

2.7.2 Преобразование InvSubBytes()

Преобразование InvSubBytes() является обратной подстановкой байт, в которой S-таблица последовательно применяется для каждого из байтов State. Это достигается за счет обратного аффинного преобразования.

2.7.3 Преобразование InvMixColumns()

Процедура InvMixColumns() является обратной по отношению MixColumns(). Колонки рассматриваются как полиномы над полем GF(2⁸).

2.7.4 Обратное преобразование AddRoundKey()

Преобразование AddRoundKey(), описанное в разделе 1.4 является обратимым, так как содержит только операции XOR.

2.7.5 Эквивалентный код дешифровки

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

EqInvCipher(byte in[4*Nb], byte out[4*Nb], word dw[Nb*(Nr+1)])

Begin

byte state[4,Nb]

state = in

AddRoundKey(state, dw[Nr*Nb, (Nr+1)*Nb-1])

for round = Nr-1 step -1 downto 1

InvSubBytes(state)

InvShiftRows(state)

InvMixColumns(state)

AddRoundKey(state, dw[round*Nb, (round+1)*Nb-1])

end for

InvSubBytes(state)

InvShiftRows(state)

AddRoundKey(state, dw[0, Nb-1])

out = state

end

Для эквивалентной программы дешифровки в конец программы расширения ключа добавляется следующий псевдокод:

for i = 0 step 1 to (Nr+1)*Nb-1

dw[i] = w[i]

end for

for round = 1 step 1 to Nr-1

InvMixColumns(dw[round*Nb, (round+1)*Nb-1])

Рис. 4. Псевдокод для эквивалентного обратного преобразования

Существует новая версия AES-NI (New Instructions), которая позволяет оптимизировать работу алгоритма (понизить загрузку процессора на 50%). Эта версия может использоваться и совместно с SSL. Компания Intel разработала микросхему, реализующую этот алгоритм (серия X5600). Количество клиентов при работе с версией AES-NI может быть увеличено на 13%.

2.7.6 Криптостойкость алгоритма AES

Первичная оценка криптостойкости алгоритма Rijndael была приведена авторами алгоритма в его спецификации, представленной на конкурс AES. Согласно оценкам авторов, Rijndael не подвержен следующим видам криптоаналитических атак:

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

· К алгоритму не применим дифференциальный криптоанализ.

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

· Square-атака (специфичная атака на алгоритмы со структурой «квадрат», к которым относится и AES) также не применима к алгоритму Rijndael.

· Алгоритм не вскрывается методом интерполяции.

AES -- в настоящее время самый широко распространенный алгоритм шифрования. Более 10 лет является официальным стандартом США для шифрования данных и применяется в различных сферах деятельности по всему миру. Обладает большим запасом криптостойкости.

Преимущества алгоритма:

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

· Высокая криптостойкость. Алгоритм известен около 15 лет, в течение 10 из которых он является стандартом шифрования в США. За это время, AES был хорошо исследован криптоаналитиками всего мира, и работа по поиску уязвимостей не прекращается до сих пор. На настоящий момент, не найдено серьезных уязвимостей, которые представляют практической опасности для криптостойкости алгоритма.

Недостатки алгоритма:

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

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

база данные аттестация государственный



Раздел III Инструментальные средства и технологии

3.1 Задание на разработку

Необходимо реализовать программное обеспечение для формирования базы данных для государственной итоговой аттестации 9 классов. Создать механизм репликации данных при передаче между регионом и АТЕ; регионом и ОУ; АТЕ и ОУ. Отправлять в зашифрованном виде данные с помощью существующих алгоритмов шифрования (AES). Предоставить функции создания отчетов в формате xlsx о выбранных экзаменах участниками по АТЕ или ОУ.

3.2 Используемые технологии

3.2.1 СУБД Microsoft SQL Server и Firebird

Microsoft SQL Server -- система управления реляционными базами данных (СУБД), разработанная корпорацией Microsoft. Основной используемый язык запросов -- Transact-SQL, создан совместно Microsoft и Sybase. Transact-SQL является реализацией стандарта ANSI/ISO по структурированному языку запросов (SQL) с расширениями. Используется для работы с базами данных размером от персональных до крупных баз данных масштаба предприятия; конкурирует с другими СУБД в этом сегменте рынка.

Firebird (FirebirdSQL) -- компактная, кроссплатформенная, свободная система управления базами данных (СУБД), работающая на Linux, Microsoft Windows и разнообразных Unix платформах.

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

Firebird используется в различных промышленных системах (складские и хозяйственные, финансовый и государственный сектора) с 2001 г. Это коммерчески независимый проект C и C++ программистов, технических советников и разработчиков мультиплатформенных систем управления базами данных, основанный на исходном коде, выпущенном корпорацией Borland 25 июля 2000 года в виде свободной версии Interbase 6.0.

3.2.2 Среда разработки Qt Creator

Qt Creator (ранее известная под кодовым названием Greenhouse) -- кроссплатформенная свободная IDE для работы с фреймворком Qt, разработанная Trolltech (Nokia). Анонс проекта состоялся на Qt Developer Days в октябре 2008 года. Публичная бета-версия проекта была опубликована 30 октября 2008 года. Финальный релиз состоялся 3 марта 2009 года (вместе с выходом Qt 4.5), а исходный код доступен под лицензией LGPL.

Особенности:

· Сделана специально для разработки на Qt.

· Встроенный редактор форм (Qt Designer) и справочная система (Qt Assistant).

· Контекстно-зависимая система помощи.

· Расширяема плагинами.

· Имеется графический фронтенд для GDB.

· Поддержка отладки с помощью CDB.

· Для создания проектов используется qmake.

· Обобщённая подсветка синтаксиса, поддерживается большое количество языков программирования и разметки. Есть возможность создания своих стилей подсветки.

· Возможность редактировать этапы сборки проекта.

· Поддержка разработки на языках C/C++/QML.

· QML-дизайнер.

· Возможность разработки под Symbian и Maemo с отладкой в эмуляторе или на устройстве.

3.2.3 Qt Framework

Qt -- кросс-платформенный инструментарий разработки ПО на языке программирования C++. Есть также «привязки» ко многим другим языкам программирования

Python -- PyQt, PySide; Ruby -- QtRuby; Java -- Qt Jambi; PHP -- PHP-Qt и другие.

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

Существуют версии библиотеки для Microsoft Windows, систем класса UNIX с графической подсистемой X11, iOS, Android, Mac OS X, Microsoft Windows CE, QNX, встраиваемых Linux-систем и платформы S60. В данный момент рассматривается возможность внедрения поддержки Qt в Windows Phone.

До недавнего времени библиотека Qt также распространялась ещё в одной версии: Qt/Embedded. Теперь эта платформа переименована в Qtopia Core и распространяется как отдельный продукт. Qtopia Core обеспечивает базовую функциональность для всей линейки платформ, предназначенных для разработки приложений для встраиваемых и мобильных устройств (КПК, смартфонов и т. п.).

Начиная с версии 4.5 Qt распространяется по 3 лицензиям (независимо от лицензии, исходный код Qt один и тот же):

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

GNU GPL -- для разработки ПО с открытыми исходниками распространяемыми на условиях GNU GPL;

GNU LGPL -- для разработки ПО с собственнической лицензией, но без внесения изменений в Qt.

Со времени своего появления в 1996 году библиотека Qt легла в основу тысяч успешных проектов во всём мире. Кроме того, Qt является фундаментом популярной рабочей среды KDE, входящей в состав многих дистрибутивов Linux.

Отличительная особенность Qt от других библиотек -- использование Meta Object Compiler (MOC) -- предварительной системы обработки исходного кода. MOC позволяет во много раз увеличить мощь библиотек, вводя такие понятия, как слоты и сигналы. Кроме того, это позволяет сделать код более лаконичным.

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

Qt комплектуется визуальной средой разработки графического интерфейса «Qt Designer», позволяющей создавать диалоги и формы «мышью» (в режиме WYSIWYG). В поставке Qt есть «Qt Linguist» -- графическая утилита, позволяющая упростить локализацию и перевод программы на многие языки; и «Qt Assistant» -- справочная система Qt, упрощающая работу с документацией по библиотеке, а также позволяющая создавать кросс-платформенную справку для разрабатываемого на основе Qt ПО. Начиная с версии 4.5.0 в комплект Qt включена среда разработки «Qt Creator», которая включает в себя редактор кода, справку, графические средства «Qt Designer» и возможность отладки приложений. «Qt Creator» может использовать GCC или Microsoft VC++ в качестве компилятора и GDB в качестве отладчика. Для Windows версий библиотека комплектуется компилятором, заголовочными и объектными файлами MinGW.

3.2.4 Qt Cryptographic Architecture (QCA)

QCA призван обеспечить обычный и кросс-платформенный Crypto API, используя типы данных и соглашения Qt. QCA разделяет API от реализации, с помощью плагинов. Преимуществом данной модели является возможность приложения избегать явных ссылок на библиотеки шифрования. Это позволяет легко менять или модернизировать крипто реализации даже без необходимости перекомпилировать приложение. QCA реализован для Windows/Unix/MacOS.

3.2.5 Обзор методов репликации и синхронизации баз данных

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

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

Репликация (синхронизация) - процесс приведения данных электронных таблиц двух БД в идентичное состояние.

Репликацию можно классифицировать по-разному:

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

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

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

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

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

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

Table1(PK, Data, Ver_Stamp)

где PK -- первичный ключ таблицы, простой или составной. В некоторых базах данных можно использовать такой тип данных, как UNIQUEIDENTIFIER. Data -- данные, которые хранит таблица. Ver_Stamp - структура ее должна быть такова, чтобы были решены две проблемы: когда произошло событие с записью; какого рода событие произошло с записью.

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

Вторая проблема «Какого рода событие произошло с записью?» является значением некоторого перечислимого множества, и, следовательно, кодируется с помощью поля целочисленного типа, которое также обслуживает триггер. В дальнейшем обозначим его как ChType. Таким образом, можно сказать, что Ver_Stamp = {TransTime, ChType}, то есть штамп версии является объединением момента возникновения изменения и характеристики самого изменения.

Записи могут быть в следующих состояниях: с записью ничего не произошло; запись добавлена; запись модифицирована; запись помечена на удаление.

3.2.6 Стандарт AES. Шифрование данных

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

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

В конце 1996 г. Национальным институтом стандартов США (NIST) был объявлен конкурс на создание нового общенационального стандарта шифрования, который должен прийти на замену DES. Разрабатываемому стандарту было присвоено рабочее наименование AES (Advanced Encryption Standard).

2 октября 2000 г. в качестве предлагаемого стандарта был выбран алгоритм Rijndael ("Рейндал"), который разработан Винсентом Райманом (Vincent Rijman) и Йоан Дамен (Joan Daemen) и представляет собой алгоритм, не использующий сети Фейстеля.

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

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

3.2.7 Преимущества алгоритма шифрования Rijndael (AES)

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

Rijndael - это итерационный блочный симметричный шифр с архитектурой "Квадрат". Шифр имеет различную длину блоков и различные длины ключей. Длина ключа и длина блока могут быть равны: 128, 192 или 256 битам независимо друг от друга.

Преимущества алгоритма:

· Рассеивание (diffusion) - т.е. изменение любого знака открытого текста или ключа влияет на большое число знаков шифротекста, что скрывает статистические свойства открытого текста;

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

· Не подвержен многим видам криптоаналитических атак, таких как дифференциальный и линейный криптоанализ, Square-атака, метод интерполяции и др. Исследования, проведённые различными сторонами, показали высокое быстродействие Rijndael на различных платформах. Ценным свойством этого шифра является его байт-ориентированная структура, что обещает хорошие перспективы при его реализации в будущих процессорах и специальных схемах.