воскресенье, 28 февраля 2010 г.

Существующие решения систем управления данными в формате XML – Часть 2.

5. XML-ориентированные базы данных

XML-ориентированные базы данных в качестве модели данных использует модель данных, принятую в самом XML. Следует отличать XML-ориентированные базы данных (напрмер, Tamino или Cache) от реляционных, поддерживающих обмен данными на языке XML (Oracle, Microsoft SQL Server и др); в основе последних лежит реляционная модель.

Самые известнае и распространенные XML-ориентированные базы данных – Tamino (компания Software AG) и Cache (InterSystems).

clip_image002

Рисунок 3. XML-ориентированные базы данных

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

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

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

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

6. Данные и метаданные в XML-ориентированных базах данных

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

Класс описывается одним или несколькими XML-метадокументами, которые являются экземплярами соответствующих метаклассов. Сам метакласс имеет описание в виде таких же XML-метадокументов, являющихся тоже экземплярами этих же метаклассов. Таким образом, XML-база является описанной «на самой себе», что удобно по ряду причин, в частности, позволяет использовать одно и то же программное обеспечение как для работы с данными, так и для работы с метаданными.

Классы разделяются на две большие группы:

  • Исходные XML-документы, элементы которых «прошиты» взаимными связями (Id и Ref). Связи могут указывать как на узлы этого же документа, так и на узлы другого документа, находящегося как в этой же базы данных, так и какой-либо другой, расположенной на удаленном сервере. Если ставится задача полной поддержки исторической целостности, то кроме указателей связей в атрибуты тегов элементов записывается системная дата последнего изменения этого элемента.
  • Аналитические XML-документы, полученные из исходных XML-документов путем заполнения содержимого тегов (текста) значениями, получаемыми либо путем прямого перенесения, либо путем аналитической обработки значений из других XML-документов. Возникает ли подобный документ в момент его запроса (виртуальный документ) или рассчитывается заранее (хранимый документ), определяется практической целесообразностью.

Для описания классов используются экземпляры следующих метаклассов (не обязательно по одному):

  • Schema – описывает структурные свойства XML-элементов для исходных XML-документов – перечень имен дочерних элементов, обязательность и возможность множественности данного элемента и т. п., а также тип данных содержимого элемента и принадлежность домену. Осуществляет проверку поступившего на сервер или, чаще, заполняемого на клиенте документа.
  • XSLT-документы – описывают преобразования исходных XML-документов в аналитические XML-документы.
  • XSL-документы с таблицами CSS и набором скриптов Behaviors – определяют, соответственно, разметку и стиль оформления документов, а также поведение элементов для электронных документов.

clip_image004

Рисунок 4. Реляционные базы данных, поддерживающие обмен данными на XML

Помимо описанных выше классов и метаклассов XML-ориентированные базы данных включают в себя:

  • Набор сценариев для работы различных групп пользователей. У сервера, как у полноправного участника документооборота, также есть свой сценарий. Сценарий связывает события, порождаемые пользователем или порождаемые «внутри» XML-базы (триггеры), с соответствующими метадокументами (Schema, XSLT, XSL) и операциями манипулирования, совершаемыми на клиенте или на сервере. По сути, сценарий – это данные, описывающие логику работы приложения, препарированного на составные части с целью унификации.
  • Библиотеку готовых XSL-шаблонов, CSS-стилей, скриптов Behaviors для упрощения проектирования документов, возможности изменения на пользователе логико-геометрического представления и внешнего вида документа, а также для подготовки XSL-документов по умолчанию. Например, вид и поведение полей для ввода во входной форме могут быть определены по умолчанию на основании типа данных, записанного в Schema.
7. Tamino компании Software AG

Деловой мир развивается все стремительнее и время от времени требует реорганизации бизнес-процессов в короткие сроки для сохранения конкурентоспособности предприятия. Это обстоятельство приводит к необходимости создания такой инфраструктуры ИТ, в которой новые приложения смогут работать совместно с существующими компонентами и прикладными системами. Быстрое развитие электронного бизнеса и будущих рынков предполагает “перманентную революцию” в сфере ИТ, в то же время задача сохранения инвестиций (например, в оборудование или обслуживающий персонал клиента) требует принятия эволюционных мер. Таким образом ИТ должны быть способны реализовать радикальные изменения и быстро, и по возможности плавно. Вместе с тем электронный бизнес ставит новые проблемы, поскольку для его ведения необходимы:

  • быстрая адаптация технологии в соответствии с изменяющимися требованиями рынка;
  • адаптация систем к меняющимся (иногда на порядки) скоростям передачи данных;
  • соединение существующих “островов” ИТ без дублирования промышленных решений;
  • сокращение расходов на программирование в среде Интернет и администрирование серверов.

clip_image006

Рисунок 5. Архитектура Tamino

Для решения этих проблем компанией Software AG и был создан Tamino — информационный XML-сервер, основанный на открытых стандартах. Компоненты Tamino обеспечивают быстрый, но плавный процесс изменения ИТ, объединяя Интернет-технологии с современными достижениями в области разработки новых баз данных и средств доступа к уже существующим. Информационный сервер Tamino поддерживает спецификацию XML V.1.0, язык ссылок XLL, таблицы стилей XSL и подмножество XQL, а также концепцию пространства имен XML. Это интегрированное решение, объединяющее целый набор технологий.

8. Технология X-Machine

X-Machine представляет собой высокопроизводительный инструмент для хранения XML-данных в оригинальном виде и подключения написанных пользователем функциональных расширений сервера для выполнения различных операций преобразования документов.

clip_image008

Рисунок 6. Структура модуля X-Machine

Технология X-Machine позволяет не только хранить, но и отыскивать объекты, относящиеся к бизнес-процессам. X-Machine включает в себя:

  • XML-процессор. Объекты XML, запоминаемые в XML-хранилище, описываются соответствующей схемой данных, выраженной в правилах отображения. Данная информация хранится в базе данных Tamino. Внутренний XML-процессор выполняет проверку правильности синтаксиса описателей объекта и отвечает за синтаксическую корректность структуры объектов XML;
  • процессор объектов. Он используется при запоминании объектов в XML-хранилище. При этом структурированные данные (данные РСУБД) запоминаются в таблицах и колонках, соответствующих описанию схемы. Обмен с внешними источниками данных выполняется с помощью компонента X-Node;
  • интерпретатор запросов XML. Поддерживает язык запросов XQL и вместе с генератором объектов обрабатывает полученный запрос с целью поиска и формирования результата в виде XML-документа;
  • генератор объектов (Object Composer). Данный компонент применяется для поиска и чтения объектов. Используя уникальные идентификаторы объектов, сформированные X-Machine при их запоминании, генератор объектов конструирует информационные объекты и возвращает их как результат выполнения запроса в виде XML-документов. В простейшем случае информационные объекты будут объектами XML. В сложных запросах для конструирования XML-объекта из традиционных источников данных генератор объектов обращается к Tamino X-Node или Tamino SQL Engine;
  • программы обслуживания. Tamino предоставляет ряд программ обслуживания информационного сервера. В качестве главного примера может служить программа загрузки XML-объектов (аналог утилиты массовой загрузки данных в традиционных СУБД).
9. Tamino SQL Engine

За взаимодействие с SQL-приложениями в Tamino отвечает SQL-процессор. Опираясь на него, входящие в Tamino средства отображения данных формата XML могут автоматически представлять эти данные в виде объектов Интернета и, наоборот, информационные объекты Интернета могут стать доступными для стандартных приложений, ориентированных на SQL. SQL-процессор поддерживает операторы SQL версии 2 в части манипулирования определениями и управления данными (DML, DDL, DCL), а также выполнение ACID-транзакций.

clip_image010

Рисунок 7. Структура модуля Tamino SQL Engine

SQL-процессор получает SQL-запросы от Tamino несколькими способами:

  • посредством внутренних обращений Tamino X-Machine;
  • из SQL-приложений с помощью встроенного SQL либо через стандартные интерфейсы ODBC, JDBC, OLE DB;
  • через диспетчер Tamino.

Кроме того, SQL-процессор предоставляет препроцессоры для компиляторов со стандартных языков программирования.

10. Выводы

В ходе исследования существующих средств хранения данных в XML представлении и выявлении областей применимости каждого, были выявлены следующие существенные факторы:

1. Поддержка Native XML

Хранение XML документов без приведения к реляционному виду. Операции над документами хранилища выполняются по средствам XPath/XQuery запросов.

2. Поддержка реляционного представления

Хранение XML документов с приведением к реляционному виду. Операции над докуменртами в хранилище выполняются по средствам SQL-92 запросов.

3. Поддержка смешанного представления

Хранение XML документов возможно с приведением как к реляционному виду, так и в Native XML формате. Соответственно, операции над документами в хранилище выполняются по средствам SQL-92 и XPath/XQuery запросов.

4. Поддержка итеративного разбора ссылок XLink/XPointer

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

5. Поддержка мультидоступа

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

6. Атомарный элемент блокировки

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

7. Поддержка протоколов изменений и откатов.

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

8. Оценка области применения

На основании произведённого анализа приводится оценка области применения системы на базе рассматриваемого хранилища.

В анализе были рассмотрены

  • Файловая БД

XML файл храниться на диске. Работа ведётся по средствам Microsoft DOM 5.0 или SAX парсеров.

  • Реляционные БД
    • MS SQL Server 2005
    • DB2 Viper
    • My Sql 5.0
  • Native XML БД
    • Tamino
    • Sedna

Таблица 1.image

I. При работе с хранилищем такого типа возможна только обработка данных XML представления логики чтение только вперёд с монопольным доступом.

II. К мощности задач решаемых в I добавляется аппарат XPath запросов и построение в памяти модели данных с возможностью CRUD операций над элементами и атрибутами XML элементов.

III. Организация систем на базе XML типа данных реляционной БД обеспечивает поддержку многопользовательского доступа и позволяет использовать XPath/XQuery аппарат запросов. На базе таких хранилищ возможно построение системы распределенной обработки данных. Поддержка смешанного хранения XML позволяет максимизировать производительность при чтении данных, но при модификации требует актуализации данных в обоих представлениях.

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

V. Native XML обеспечивает самый богатый аппарат администрирования и использования XPath/XQuery. Но из-за сложности операций над XML спектр разрешимых задач ограничен вычислительной мощностью системы. В случае работы с XML, приводимом к реляционному виду, использование реляционного хранилища позволяет получить прирост производительности, исчисляемый порядками.

Advanced Encryption Standard (AES) – Часть 2.Описание AES

Блочные шифры

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

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

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

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

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

Блочный шифр состоит из двух взаимосвязанных алгоритмов: алгоритм шифрования E и алгоритм расшифрования E-1. Входными данными служат блок размером n бит и k-битный ключ. На выходе получается n-битный зашифрованный блок. Для любого фиксированного ключа функция расшифрования является обратной к функции шифрования clip_image001для любого блока M и ключа K.

Для любого ключа K, EK — перестановка набора входных блоков. Ключ выбирается из 2n! возможных перестановок.

Размер блока n — это фиксированный параметр блочного шифра, обычно равный 64 или 128 битам, хотя некоторые шифры допускают несколько различных значений. Длина 64 бита была приемлема до середины 90-х годов, затем использовалась длина 128 бит и более. Различные схемы шифрования позволяют зашифровывать открытый текст произвольной длины. Каждая имеет определенные характеристики: вероятность ошибки, простота доступа, уязвимость к атакам. Типичными размера ключа являются 40, 56, 64, 80, 128, 192 и 256 бит. В 2006 г. 80-битный ключ способен был предотвратить атаку грубой силой.


Описание AES
Алгоритм

С математической точки зрения, метод Rijndael основывается на теории полей Галуа, благодаря чему можно строго доказать некоторые его свойства, касающиеся секретности. Тем не менее, можно рассматривать его и с точки зрения кода программы на языке С, не вдаваясь в математические подробности. Как и в DES, в Rijndael применяются замены и перестановки. И там, и там используются несколько итераций, их число зависит от размера ключа и блока и равно 10 для 128-разрядного ключа и 128-битных блоков; для максимального размера ключа и блоков число итераций равно 14. Однако, в отличие от DES, все операции выполняются над целыми байтами, что позволяет создавать эффективные реализации как в аппаратном, так и в программном исполнении. Схематичный алгоритм метода Rijndael приведен ниже

clip_image003

У функции rijndael три аргумента: plaintext — массив размером 16 байт, содержащий входные данные, ciphertext — массив размером 16 байт, в который будет возвращен шифр, а также key — 16-разрядный ключ. В процессе вычислений текущее состояние данных сохраняется в байтовом массиве state, размер которого равен NROWS х NCOLS. Для 128-битных блоков данных размер этого массива равен 4x4 байта. В 16 байтах целиком уместится один блок. Массив state изначально содержит открытый текст и модифицируется на каждом этапе вычислений. На некоторых этапах выполняется побайтовая подстановка. На других этапах — перестановка байтов внутри массива. Могут выполняться и другие преобразования. В конечном итоге содержимое state представляет собой зашифрованный текст, который и возвращается в качестве результата функции. Алгоритм начинается с распространения ключа по 11 массивам одинакового размера, представляющим состояние (state). Эти массивы хранятся в гк — массиве структур, содержащих массивы состояний. Одна из этих структур будет использована в начале вычислений, а остальные 10 — во время 10 итераций (по одной на итерацию). Вычисление ключа для каждой итерации производится довольно сложным образом, и мы не будем рассматривать детали этого процесса. Достаточно сказать, что для этого осуществляются циклические повороты и суммирования по модулю 2 различных групп разрядов ключа. Следующий шаг состоит в копировании открытого текста в массив state для того, чтобы его можно было обрабатывать во время последующих итераций. Копируется текст в колонки по 4 байта: первые 4 байта попадают в колонку 0, вторые — в колонку 1 и т. д. И колонки, и строки нумеруются с нуля, а итерации — с единицы. Процесс создания 12 байтовых массивов размером 4x4 показан на рис.

clip_image005

Перед началом основного цикла вычислений производится еще одно действие: rk[0] поразрядно складывается по модулю 2 с массивом state. Другими словами, каждый из 16 байт в массиве state заменяется суммой по модулю 2 от него самого и соответствующего байта в rk[0]. ТОЛЬКО после этого начинается главное развлечение. В цикле проводятся 10 итераций, в каждой из которых массив state подвергается преобразованию. Каждый раунд (итерация) состоит из четырех шагов. На шаге 1 в state производится посимвольная подстановка. Каждый байт по очереди используется в качестве индекса для S-блока, заменяющего его значение на соответствующую запись S-блока. На этом шаге получается прямой моноалфавитный подстановочный шифр. В отличие от DES, где используются несколько S-блоков, в Rijndael S-блок всего один. На шаге 2 каждая из четырех строк поворачивается влево. Строка 0 поворачивается на 0 байт (то есть не изменяется), строка 1 — на 1 байт, строка 2 — на 2 байта, а строка 3 — на 3 байта. Смысл заключается в разбрасывании данных вокруг блока. Это аналогично перестановкам, показанным на рис. 8.5. На шаге 3 происходит независимое перемешивание всех колонок. Делается это с помощью операции матричного умножения, в результате которого каждая новая колонка оказывается равной произведению старой колонки на постоянную матрицу. При этом умножение выполняется с использованием конечного поля Галуа, GF(2S). Несмотря на то, что все это кажется довольно сложным, алгоритм устроен так, что каждый элемент матрицы вычисляется посредством всего лишь двух обращений к таблице и трех суммирований по модулю 2. Наконец, на шаге 4 ключ данной итерации складывается по модулю 2 с массивом state. Благодаря обратимости всех действий расшифровка может быть выполнена с помощью такого же алгоритма, но с обратным порядком следования всех шагов. Однако есть одна хитрость, которая позволяет заниматься расшифровкой, используя алгоритм шифрования с измененными таблицами. Данный алгоритм обладает не только очень высокой защищенностью, но и очень высокой скоростью. Хорошая программная реализация на машине с частотой 2 ГГц может шифровать данные со скоростью 700 Мбит/с. Такой скорости достаточно для шифрации видео в формате MPEG-2 в реальном масштабе времени. Аппаратные реализации работают еще быстрее.

Режим шифрования

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

Electronic Code Book (ECB)

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

Зашифрование может быть описано следующим образом : Ci = F(Pi) для любых i от 1 до N. Здесь Ci и Pi - блоки зашифрованного и открытого текстов соответственно, а F - функция блочного шифрования. Расшифровка по той же схеме. То есть Pi = F − 1(Ci).

clip_image007

Шифрование в режиме ECB

clip_image009

Дешифрование в режиме ECB

Недостатки:

  • идентичные блоки открытого текста шифруются в идентичные блоки зашифрованного текста при одном и том же ключе.
  • блоки могут пропадать или появляться. Злоумышлленник может перехватить блок и продублировать его. Со стороны приёмника он может быть воспринят, как "правильный". Таким образом, это не может скрыть образцы данных хорошо, поэтому этот метод не рекомендуется к использованию в криптографических протоколах.
Cipher Block Chaining (CBC)

Для сцепления используется механизм обратной связи, поскольку результат шифрации предыдущих блоков используется для шифрации текущего блока. Таким образом любой блок шифра зависит не только от исходного текста, но и от всех предыдущих блоков текста. В Cipher Block Chaining (CBC) текст XOR’ится с предыдущим шифр. блоком перед шифрацией. Дешифрация проводится аналогично. Математическая запись:

Ci = Ek (Pi XOR Ci-1)

Pi = Ci-1 XOR Dk(Ci)

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

clip_image011

Шифрование в режиме CBC

clip_image013

Дешифрование в режиме CBC

Большинство сообщений не делятся нацело на 64-битные блоки, обычно остается короткий блок в конце. Можно по-разному бороться с этим. Простейший метод – padding (дополнение до полного блока). Если надо потом убирать мусор, то достаточно просто последним байтом обозначить количество лишних байтов. Можно также обозначать последний байт текста символом конца файла. Это не всегда можно сделать (напр., если надо расшифровать блок и поставить его куда - нибудь в память). Тогда применяется следующая схема шифрования: предположим, в последнем блоке j бит. После зашифровки последнего целого блока, зашифруем шифрованный блок еще раз, выберем j начальных битов полученного текста и по XOR’им с исходным текстом. Это и есть шифр для неполного блока.

Cipher Feedback (CFB)

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

clip_image014

clip_image015

C0 = IV

где IV - вектор инициализации

Как режим CBC, изменения в открытом тексте распространяется повсюду в зашифрованном тексте, и в кодировании нельзя найти что-либо подобное. Также как и в CBC, в расшифровке можно найти что-либо подобное. Расшифровывая, однобитовое изменение в зашифрованном тексте затрагивает два блока открытого текста: однобитовое изменение в соответствующем блоке открытого текста, и полном искажении следующего блока открытого текста. Более поздние блоки открытого текста будут расшифрованы как обычно.

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

CFB совместно использует два преимущества перед режимом CBC с режимами OFB шифра потока и CTR: блочный шифр только когда-либо используется в направлении шифровки, и сообщение не должно быть дополнено к кратному числу размера блока шифра.

Output Feedback (OFB)

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

Из-за симметрии операции сложения, кодирование и расшифровка похожи:

clip_image016

clip_image017

Oi = Ek(Oi − 1)

O0 = IV

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

Уязвимость

Как и предполагали эксперты, после принятия алгоритма Rijndael в качестве стандарта AES попытки вскрытия данного алгоритма существенно усилились.

Можно сказать, что криптоанализ алгоритма AES стал развиваться, в основном, в следующих четырех направлениях:

Во-первых, попытки усиления «классических» атак или применения других известных атак к данному алгоритму. Например, была предложена атака методом бумеранга на 6-раундовую версию алгоритма со 128-битным ключом, для выполнения которой требуется 239 выбранных открытых текстов, 271 шифртекстов с адаптивным выбором и 271 операций шифрования.

Во-вторых, применение различных методов криптоанализа на связанных ключах, в частности были предложены следующие атаки:

  • Было предложено несколько вариантов атак на связанных ключах на 7- и 8-раундовый AES-192 с использованием невозможных дифференциалов.
  • Комбинация метода бумеранга и связанных ключей: 9-раундовый AES-192 атакуется при наличии 279 выбранных открытых текстов, каждый из которых шифруется на 256 связанных ключах, выполнением 2125 операций шифрования; для атаки на 10-раундовый AES-256 требуется 2114,9 выбранных открытых текстов (включая зашифрование на 256 связанных ключах) и 2171,8 операций. Данная атака использует слабость процедуры расширения ключа, состоящую в ее недостаточной нелинейности.
  • Предлагается атака на 10-раундовый алгоритм AES-192, для которой требуется 2125 выбранных открытых текстов (на 256 связанных ключах) и 2146,7 операций.

Несмотря на то, что предложенные атаки на связанных ключах являются весьма непрактичными, настораживает тот факт, что атаке подвержены уже 10 из 12 раундов алгоритма AES-192 (и это после всего 5 лет после принятия стандарта AES!) – возникает опасение, что эксперты (указывающие на недостаточность раундов в алгоритме Rijndael) были правы и полнораундовый алгоритм AES будет вскрыт существенно раньше, чем предполагали эксперты института NIST.

В-третьих, многие исследования посвящены алгебраической структуре алгоритма Rijndael, например:

  • Найдены линейные соотношения в таблице замен Rijndael (т.е. в единственном нелинейном элементе алгоритма). Однако, как и в других аналогичных работах, каких-либо практических возможностей использования данного свойства не предложено.
  • Зашифрование с помощью Rijndael можно выразить относительно (особенно по сравнению с другими «серьезными» алгоритмами шифрования) простой формулой. Авторы не нашли практического применения данной формулы, но предположили, что она будет использована в реальных атаках в течение ближайших примерно 20 лет.
  • Показано, что вскрытие алгоритма AES эквивалентно решению системы квадратичных уравнений в конечном поле GF(28).

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

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

Advanced Encryption Standard (AES) – Часть1.Процесс разработки AES

Введение

В конце прошлого века появилась необходимость заменить существующий стандарт шифрования. Необходимость в принятии нового стандарта была вызвана небольшой длиной ключа DES (56 бит), что позволяло применить метод грубой силы (полный перебор ключей) против этого алгоритма. Кроме того, архитектура DES была ориентирована на аппаратную реализацию, и программная реализация алгоритма на платформах с ограниченными ресурсами не давала достаточного быстродействия. Модификация 3-DES обладала достаточной длиной ключа, но при этом была ещё медленнее.

Формальное начало процессу разработки нового криптостандарта было положено 2 января 1997 года, когда НИСТ объявил о своем решении разрабатывать. Затем, 12 сентября того же года был опубликован официальный призыв ко всем заинтересованным кругам о выдвижении своих алгоритмов в качестве возможных кандидатов.

Требования к новому стандарту были следующими:

  • блочный шифр.
  • длина блока, равная 128 битам.
  • ключи длиной 128, 192 и 256 бит.

Подобные шифры были довольно редки во время объявления конкурса; возможно, лучшим был Square. Дополнительно кандидатам рекомендовалось:

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

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

Принятие нового стандарта
Первый раунд - 15 кандидатов

20 августа 1998 года прошла "Первая конференция кандидатов на AES" или AES1, где НИСТ объявил о приеме на конкурс 15 алгоритмов-кандидатов, в разработке которых принимали участие криптографы из 12 стран мира. (Еще 6 алгоритмов- кандидатов, в том числе и российский, не были допущены к конкурсу на основании, как пояснил НИСТ, "неполноты" представленной документации.) Вот список алгоритмов, вышедших в первый круг отбора:

страна

алгоритм

кто представил

Австралия

LOKI97

Lawrie Brown, Josef Pieprzyk, Jennifer Seberry

Бельгия

RIJNDAEL

Joan Daemen, Vincent Rijmen

Великобритания, Израиль, Норвегия

SERPENT

Ross Anderson, Eli Biham, Lars Knudsen

Германия

MAGENTA

Deutsche Telekom AG

Канада

CAST-256

Entrust Technologies, Inc.

DEAL

Outerbridge, Knudsen

Корея

CRYPTON

Future Systems, Inc.

Коста-Рика

FROG

TecApro Internacional S.A.

США

HPC

Rich Schroeppel

MARS

IBM

RC6

RSA Laboratories

SAFER+

Cylink Corporation

TWOFISH

Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, Niels Ferguson

Франция

DFC

Centre National pour la Recherche Scientifique

Япония

E2

Nippon Telegraph and Telephone Corporation (NTT)

Представив все 15 алгоритмов на конференции AES1, а затем и в соответствующем официальном документе, НИСТ призвал общественность принять активное участие в исследовании и обсуждении кандидатов.

Понемногу выявились явные аутсайдеры конкурса - те алгоритмы, для которых были продемонстрированы методы криптоанализа, так или иначе понижающие возможную (при имеющихся длинах блока и ключа) стойкость. Среди наименее удачливых в этом отношении претендентов оказались шифры LOKI97, FROG, MAGENTA, DEAL и SAFER +. Для алгоритмов CRYPTON и DFC было продемонстрировано наличие "слабых ключей", облегчающих вскрытие.

Для остальных криптоалгоритмов в ходе первого раунда не было получено сколь- нибудь существенных криптоаналитических результатов. (Хотя, к примеру, шифр HPC или "заварной пудинг" особо и не анализировали вследствие чрезвычайной экзотичности конструкции.) В этом же раунде были проведены и тестирования программных реализаций алгоритмов на производительность. Непосредственно в НИСТ шифры исследовались на эффективность в оптимизированных реализациях на языках Си и Java.

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

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

Второй раунд - пятерка лучших

9 августа 1999 г. НИСТ объявил победителей первого раунда. На основании проделанного анализа и с учетом принятых в процессе обсуждения поправок к алгоритмам, были отобраны пять алгоримтов-финалистов: MARS, RC6, Rijndael, Serpent и Twofish (не попавшие в финал алгоритмы E2 и CAST-256 можно считать "замыкающими список лучших".) В пятерке шифров-победителей за время исследований в первом раунде не было найдено никаких сколь-нибудь существенных уязвимостей и по своим характеристикам каждый из кандидатов потенциально был оценен как "превосходная технология".

Далее рассмотрим каждый из алгоритмов в алфавитном порядке:

MARS выполняет последовательность преобразований в следующем порядке: сложение с ключом в качестве pre-whitening, 8 раундов прямого перемешивания без использования ключа, 8 раундов прямого преобразования с использованием ключа, 8 раундов обратного преобразования с использованием ключа, 8 раундов обратного перемешивания без использования ключа и вычитание ключа в качестве post-whitening. 16 раундов с использованием ключа называются криптографическим ядром. Раунды без ключа используют два 8х16- битных S-boxes и операции сложения и XOR. В дополнение к этим элементам раунды с ключом используют 32-битное умножение ключа, зависимые от данных циклические сдвиги и добавление ключа. Как раунды перемешивания, так и раунды ядра являются раундами модифицированной сети Фейштеля, в которых четверть блока данных используется для изменения остальных трех четвертей блока данных. MARS предложен корпорацией IBM.

RC6 является параметризуемым семейством алгоритмов шифрования, основанных на сети Фейштеля; для AES было предложено использовать 20 раундов. Функция раунда в RC6 задействует переменные циклические сдвиги, которые определяются квадратичной функцией от данных. Каждый раунд также включает умножение по модулю 32, сложение, XOR и сложение с ключом. Сложение с ключом также используется для pre- и pos-whitening. RC6 был предложен лабораторией RSA.

Rijndael представляет собой алгоритм, использующий линейно-подстановочные преобразования и состоящий из 10, 12 или 14 раундов в зависимости от длины ключа. Блок данных, обрабатываемый с использованием Rijndael, делится на массивы байтов, и каждая операция шифрования является байт-ориентированной. Функция раунда Rijndael состоит из четырех слоев. В первом слое для каждого байта применяется S-box размерностью 8х8 бит. Второй и третий слои являются линейными перемешиваниями, в которых строки рассматриваются в качестве сдвигаемых массивов и столбцы перемешиваются. В четвертом слое выполняется операция XOR байтов подключа и каждого байта массива. В последнем раунде перемешивание столбцов опущено. Rijndael предложен Joan Daemen (Proton World International) и Vincent Rijmen (Katholieke Universiteit Leuven).

Serpent является алгоритмом, использующим линейно-подстановочные преобразования и состоящим из 32 раундов. Serpent также определяет некриптографические начальную и заключительную перестановки, которые облегчают альтернативный режим реализации, называемый bitslice. Функция раунда состоит из трех слоев: операция XOR с ключом, 32-х параллельное применение одного из восьми фиксированных S-boxes и линейное преобразование. В последнем раунде слой XOR с ключом заменен на линейное преобразование. Serpent предложен Ross Anderson (University of Cambridge), Eli Biham (Technion) и LarsKnudsen (University of California San Diego).

Twofish является сетью Фейштеля с 16 раундами. Сеть Фейштеля незначительно модифицирована с использованием однобитных ротаций. Функция раунда влияет на 32-битные слова, используя четыре зависящих от ключа S-boxes, за которыми следуют фиксированные максимально удаленные отдельные матрицы в GF(28), преобразование псевдо-Адамара и добавление ключа. Twofish был предложен Bruce Schneier, John Kelsey и Niels Ferguson (Counterpane Internet Security, Inc.), Doug Whiting (Hi/fn, Inc.), David Wagner (University of California Berkley) и Chris Hall (Princeton University).

Третья конференция AES

Третья конференция AES прошла в Нью-Йорке 13 и 14 апреля 2000 года, незадолго до завершения второго этапа. На ней присутствовало 250 участников, многие из которых приехали из-за рубежа. Двухдневная конференция была разделена на восемь сессий, по четыре в день, плюс к тому состоялась неформальная дополнительная сессия, подводившая итоги первого дня. На сессиях первого дня обсуждались вопросы, связанные с программируемыми матрицами (FPGA), проводилась оценка реализации алгоритмов на различных платформах, в том числе PA-RISC, IA-64, Alpha, высокоуровневых смарт-картах и сигнальных процессорах, сравнивалась производительность претендентов на стандарт, анализировалось число раундов в алгоритмах-кандидатах. На сессиях второго дня был проанализирован Rijndael с сокращённым числом раундов и показана его слабость в этом случае, обсуждался вопрос об интегрировании в окончательный стандарт всех пяти алгоритмов-претендентов, ещё раз тестировались все алгоритмы. В конце второго дня была проведена презентация, на которой претенденты рассказывали о своих алгоритмах, их достоинствах и недостатках. О Rijndael рассказал Винсент Риджмен, заявивший о надёжности защиты, высокой общей производительности и простоте архитектуры своего кандидата.

Выбор победителя

2 октября 2000 года было объявлено, что победителем конкурса стал алгоритм Rijndael, и началась процедура стандартизации. 28 февраля 2001 года был опубликован проект, а 26 ноября 2001 года AES был принят как Федеральный Стандарт Обработки Информации 197.

Ответы на базовые вопросы по С#

Типы данных.

  1. Чему равно значение переменой i до вызова функции ModifyInt? После вызова? Почему?
    • До вызова функции ModiffyInt: i=10

После вызова функции ModiffyInt: i=10

Значение переменной не изменилось, т.к. переменная i имеет тип int, а int – это тип характеризируемый значением(value type).Т.е. вызванной функции передаётся копия переменной.

  1. Чему равно значение переменной s до вызова функции ModfyString? После вызова? Почему?

§ До вызова функции ModiffyString s = "Hello, world"

После вызова функции ModiffyString s = "Hello, world"

Значение переменной не изменилось, т.к. переменная s является переменной типа string. Хотя string и является ссылочным типом(value-types), операции присваивания, копирования....предполагают работу со значениями строк. Строки в С# не изменяемы. Т.е. вызванной функции будет передана копия строки.

  1. Какие типы являются типами-значениями (value types)? Какие типы являются типами-ссылками (reference-types)?

Безымянный

  1. Какие различия между типами-значениями и типами-сылками?

Критерий различия

value-types

reference types

Размещение типа

В стеке

В управляемой динамической памяти

Представление переменной

В виде локальной копии

В виде ссылки на место в памяти, анятое соответствующим экземпляром

Базовый тип

Производный от System.ValueType

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

Возможность быть базовым для других типов

Всегда изолированы и не могут быть расширены

Если тип не изолирован, он может быть базовам для других типов

Поведение, принятое по умолчанию при передаче параметров

Переменные передаются по значению

Переменные передаются по ссылке

Возможность переопределить System.Object.Finalize

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

Возможно, неявно.

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

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

Безусловно, возможно.

Время прекращения существования переменных данного типа

Удаляются, когда оказываются вне контекста определения.

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

  1. В чем проявляется эта разница в примере types.cs?

§ Разница между типами value-types и reference types в примере types.cs не видна.

  1. Где размещаются переменные типов-значений (values-types)?

§ В стеке

  1. Где размещаются переменные типов-ссылок (reference-types)?

§ В управляемой динамической памяти

  1. Как создать новый тип-значение (values-type)?

§ Унаследовать свой класс от класса ValueType.

  1. Как создать новый тип-ссылку (reference-type)?

§ Нужно просто создать класс, при создании нового класса мы неявно наследуемся от класса System.Object.

  1. Какой тип у переменной i?

§ Переменная i имеет тип System.Int32.

  1. Какой тип у переменной j?

§ Переменная i имеет тип System.Int32.

  1. Объясните ваши наблюдения по поводу типов переменных i и j.

§ Int является сокращённым обозначением типа System.Int32. Поэтому переменная i имеет тип System.Int32. Вызванной функции передаётся копия переменной i, поэтому значение переменной не меняется после вызова функции. Переменная j также имеет тип System.Int32.

  1. Почему переменная типа-ссылки (reference type) o содержит старое значение?

§ Переменная типа-ссылки (reference type) o содержит старое значение, потому что когда значение преобразуется в объектный тип, среда CLR размещает новый объект в динамической памяти и копирует значение соответствующего типа в созданный экземпляр, а мы получаем ссылку на новый объект. Следовательно, при последующем изменении переменной I значение объекта o не меняется.

  1. Что такое boxing и unboxing?

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

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

  1. Вoxing выполняется неявно (implicit) или явно (explicit)? Пример.

§ Boxing выполняется автоматически и неявно.

  1. Unboxing выполняется неявно (implicit) или явно (explicit)? Пример.

§ Unboxing выполняется явно. Необходимо явно преобразовать объект к нужному типу.

  1. Приведите пример для обеих вариантов.

short s = 25;

object objShort = s;//boxing

short anothrShort = (short)objShort;//unboxing

  1. Почему класс String называется неизменяемым (immutable)? Что означает «неизменяемый» (immutable)?

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

  1. Объясните, почему в следующем примере будет выведена строка

§ Потому что метод s.Trim(); вернёт новый экземпляр класса, а объект s останется прежним.

Массивы. Коллекции. Структура приложения

  1. Может ли быть более одной точки входа в программу? Какие четыре варианта сигнатуры могут быть у точки входа?

§ Нет,точка входа должна быть только одна.

§ static void Main(string[] args)

{

}

§ static void Main()

{

}

§ static int Main(string[] args)

{

return 0;

}

§ static int Main()

{

return 0;

}

  1. Почему нижеприведенные примеры не компилируется и какая ошибка будет получена?

§ Потому что несколько точек входа в программу.

§ Пример будет скомпилирован, но с предупреждением(возможно не правильно задана функция Main). Функция Main не может принимать во входных параметрах int[], и компилятор не считает эту функцию точкой фхода.

  1. Используя написанный ниже метод Main, напишите новый метод ModifyString, который изменяет переменную s, присваивая ей значение “Hello, I’ve been modified,” так, чтобы строчка Console.WriteLine, которая вызывается в методе Main печатала “Hello, I’ve been modified,”.

static void Main()

{

string s = "Hello, world";

ModifyString(ref s);

Console.WriteLine(s);

}

static void ModifyString(ref string str)

{

str="Hello, I’ve been modified.";

}

  1. Напишите программу, отображающую все аргументы командной строки, с которыми она вызывается.

static void Main(string[] args)

{

for (int i = 0; i < args.Length; i++)

{

Console.WriteLine("Аргумент: {0}", args[i]);

}

}

  1. Аргументы какого типа можно передавать, ограничено ли их число?

§ Параметр один: массив строк(string[] args).

§ Количество аргументов в массиве строк не ограниченно.

  1. Для чего нужно значение, которое может возвращать метод Main?

§ По окончании работы программы возвращаемое значение предоставляется системе. При успешном завершении возвращается нуль.

  1. Напишите программу на C#, которая удлиняет этот массив до 10-ти элементов от 10 до 100.

int[] arr = new int[] { 10, 20, 30, 40, 50 };

//до 10

Array.Resize<int>(ref arr, 10);

for (int i = 5; i < arr.Length; i++)

{

arr[i] = (i + 1) * 10;

}

//от 10 до 100

Array.Resize<int>(ref arr, 100);

for (int i = 10; i < arr.Length; i++)

{

arr[i] = (i + 1) * 10;

}

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

§ Когда необходимо хранить данные однородных типов, к которым мы хотим иметь прямой доступ.

§ Когда известен точный размер массива данных.

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

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

§ Когда необходимо осуществлять поиск среди данных.

§ Когда необходимо хранить данные различных типов.

§ Когда неизвестен размер. Коллекция самостоятельно расширяться по мере добавления элементов.

Управляющие конструкции. Классы. Структуры

  1. напишите программу, которая разделить строку на элементы, отделенные запятыми (воспользуйтесь функцией String.Split) и помещает их в массив. Переберите элементы массива используя сначала оператор foreach, а потом еще раз, используя оператор for.

string s = "One, Two, Three, Four, Five";

string strSplit = ", ";

string[] strs = s.Split(strSplit.ToCharArray());

foreach (string s1 in strs)

{

Console.WriteLine(s1);

}

for (int i=0; i < strs.Length; i++)

{

Console.WriteLine(strs[i]);

}

  1. Изучите нижеприведенный пример и объясните, почему выбрасывается исключение когда вызывается метод CheckType с параметром string, но работает нормально, когда в качестве параметра этому методу передается значение типа int.

§ Exeption возникает при попытке преобразовать значение , содержащееся в объектной ссылке, в значение не соответствующего типа.

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

static void Main()

{

int i = 1;

string s = "Hello, world";

CheckType(i);

CheckType(s);

}

static void CheckType(object o)

{

int j;

string t;

if (o is int)

{

Console.WriteLine("o is an int");

}

else

{

Console.WriteLine("o is not an int");

}

try

{

j = (int)o;

}

catch (Exception e)

{

Console.WriteLine("Ошибка конвертации!");

}

}

  1. Почему в консоль выводятся два разных значения?

§ Т.к. byte это 8 бит. При перемножении чисел у нас получается число 31110. В двоичном виде это число будет выглядеть так 111100110000110. Это число выходит за разрядную сетку типа byte, поэтому первые 8 бит отбрасываются. Остаётся 10000110, что в десятичном виде 134.

§ А без явного приведения к типу byte произведение будет неявно приведено к типу большей разрядности, и будет выведено 31110.

  1. Какие варианты являются правильными циклами do/while?

do {i++;} while {i <= 10};//Синтаксически неверно.

do {i++;} while (i <= 10);//Верно.

do() {i++;} while() {i <= 10};//Синтаксически неверно.

do() {i++;} while (i <= 10); //Синтаксически неверно.

do (i++;) while (i <= 10);//Синтаксически неверно.

  1. Структура и класс – что из них является типом-значением (value-type), а что типом-ссылкой (reference-type)? Где создаются объекты каждого типа?

§ Структура является value-type, хранится в стеке.

§ Класс является reference-type, храниться в динамической памяти.

  1. Проанализируйте, скомпилируйте и запустите файл stuct.cs и объясните, как он работает, учитывая разницу между типами-значениями (value-types) и типами-ссылками (reference-types).

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

§ А при создании второго объекта класса, создаётся фактически не объект, а объектная ссылка, которая указывает на первый объект, размещённый в динамической памяти. Поэтому при изменении значений полей pc2, мы на самом деле изменяем объект ps1, т.к эти ссылки указывают на один и тот же объект.

  1. В чем ключевые отличия между классами и структурами, по отношению к типам-ссылкам (reference-types) и типам-значениям (value-types)?

§ См. ответ на вопрос №4.

  1. где размещаются переменные ps1 и ps2?

§ В стеке.

  1. где размещаются переменные pc1 и pc2?

§ Ссылки на объект хранятся в стеке, а сам объект в динамической памяти.

  1. В C# всё является объектами. Приведите короткий пример, демонстрирующий это утверждение.

static void Main()

{

Console.WriteLine(5.ToString());

}