Выпускная работа по «Основам информационных технологий» - rita.netnado.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Выпускная работа по «Основам информационных технологий» 1 368.13kb.
Выпускная работа по «Основам информационных технологий» Магистрантка... 1 247.67kb.
Выпускная работа по «Основам информационных технологий» 6 316.68kb.
Выпускная работа по «Основам информационных технологий» 1 151.62kb.
Выпускная работа по «Основам информационных технологий» Магистранта... 1 169.61kb.
Выпускная работа по «Основам информационных технологий» 3 445.95kb.
Выпускная работа по «Основам информационных технологий» на тему «Применение... 2 254.7kb.
Выпускная работа по «Основам информационных технологий» 1 327.94kb.
Выпускная работа по «Основам информационных технологий» Магистранта... 1 324.29kb.
Выпускная работа по предмету «Основы информационных технологий» Магистрант... 1 295.47kb.
Реферат на тему: перспективы использования информационных технологий... 1 266.44kb.
Тема №4 Поляризация 1 25.58kb.
Публичный отчет о деятельности моу кассельская сош 2 737.71kb.
Выпускная работа по «Основам информационных технологий» - страница №1/1



БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Выпускная работа по
«Основам информационных технологий»


Магистрантка кафедры УМФ

Кайгородова Леся Иосифовна

Руководители:

профессор Соболевский Павел Иосифович,

ст. преподаватель Кожич Павел Павлович

Минск – 2007 г.

Оглавление


Оглавление 2

Список обозначений ко всей выпускной работе 3

Использование IT в криптографии 4

Введение 4

Глава 1. Обзор литературы 5

Глава 2. Методика исследования 7

Глава 3. Основные результаты 10

Глава 4 . Обсуждение результатов 13

Заключение 14

Список литературы к реферату 15

Предметный указатель к реферату 16

Интернет ресурсы в предметной области исследования 17

Действующий личный сайт в WWW 18

Граф научных интересов 19

Презентация магистерской диссертации 20

Список литературы к выпускной работе 21

Приложения 22

Приложение 1. Презентация магистерской диссертации 22

Приложение 2. Генерация параметров для алгоритма формирования ЭЦП в соответствии со стандартом СТБ 1176.2-99 в системе Mathematica 25



Список обозначений ко всей выпускной работе


SMP — симметричная мультипроцессорная система

PVP — параллельная векторная система

MPP — система массового параллелизма

NUMA — система с неоднородным доступом к памяти

ЭВМ — электронная вычислительная машина

RSA — Rivest, Shamir, Adleman, система шифрования

ЭЦП — электронная цифровая подпись

Использование IT в криптографии

Введение


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

В настоящее время криптографическая защита информации из тайнописи, доступной лишь посвященным, превращается в общенародное достояние. Вследствие развития информационных технологий и особенно в связи с широким распространением Интернета защита конфиденциальной информации стала одной из актуальнейших задач современности. До 60-70-х годов ХХ века криптография во всех странах находилась в ведении структур, отвечающих за безопасность связи и информации. Развитие средств связи, таких как телеграф, телефон, радио, обусловливало изменение характера криптографии, а с применением электронных средств передачи информации, задачи криптографии усложнились и расширились. Широкое распространение компьютерных технологий стало причиной того, что сфера действия криптографии видоизменилась и пополнилась разного рода задачами, не связанными непосредственно с засекречиванием информации, — это и разработка систем электронной цифровой подписи, протоколов выборов, подписания контрактов, и идентификация удаленных пользователей; и появление методов, позволяющих избежать получения ложных сообщений, и создание средств защиты систем электронных платежей. Следует выделить два основных направления, в которых развивается прикладная криптография – это применение программного обеспечения и применение аппаратного обеспечения при реализации криптографических алгоритмов.


Глава 1. Обзор литературы


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

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

В последние несколько лет появилось десятки статей, монографий и переводных изданий, касающихся основных аспектов криптографии. В основном, это работы теоретического плана, посвященные описанию, синтезу и анализу криптографических алгоритмов и протоколов. Понимание этих работ и использование их результатов в практическом плане достаточно затруднено. Исключений из этого правила довольно немного. Так, на мой взгляд, одной из лучших работ является монография А. Алферова, А. Зубова, С. Кузьмина и А. Черемушкина «Основы криптографии: учебное пособие» (М.: Гелиос АРВ, 2001).

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

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

Наиболее известная работа по прикладной криптографии – монография Bruce Shneier «Applied Cryptography Second Edition: protocols, algorithms, and source code in C» (John Wiley & Sons, Inc. New York, 1997). Однако содержание этой книги с современных научно-методических позиций представляется избыточным. Значительная часть монографии посвящена классической криптографии. О их практической реализации, насущно необходимой специалистам-прикладникам, рассказано только в третьей части монографии.

Следует выделить еще одну очень важную книгу для программистов – Щербакова Л. Ю., Домашева А. В, “Прикладная криптография. Использование и синтез криптографических интерфейсов”. Основное внимание в книге авторы уделяют прикладным вопросам – использованию уже существующих в операционных системах Microsoft криптографических модулей (криптопровайдеров) и созданию собственных криптопровайдеров при помощи специальных инструментариев. Книга содержит эксклюзивные материалы, не публиковавшиеся ранее. Здесь можно найти уже готовые реализации некоторых всемирно известных стандартов.

Что касается статей и книг, посвященных аппаратной реализации криптографических алгоритмов, то здесь дела обстоят намного сложнее. В основном, новшества и открытия публикуются, но доступ к ним ограничен из-за дороговизны. Но существует много литературы, посвященной теме параллельных вычислений – нового направления в развитии вычислительной математики. Этим аппаратом мы можем смело пользоваться для того, чтобы получить быструю реализацию нужных нам алгоритмов. Здесь можно выделить следующие источники: Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб:. БХВ-Петербург, 2002, – 608с. (2-е издание 2004), а также очень известный нтернет-ресурс http://www.parallel.ru. Что касается уже известных аппаратно реализуемых алгоритмов, то следует упомянуть такие статьи А. Тиунчика из НАН РБ, как «Мелкозернистая реализация алгоритма дискретного логарифмирования» и «Реализация алгоритма умножения по методу Монтгомери на FPGA».


Глава 2. Методика исследования


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

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

Рассмотрим теоретико-числовые проблемы этой области.

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



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

Задача вычисления дискретного логарифма в мультипликативной группе конечного поля. Практически сразу после опубликования работы У. Диффи и М. Хеллмана Дж. Поллард публикует вероятностные алгоритмы решения задачи дискретного логарифмирования, имеющие корневую оценку сложности и не требующие большого объема памяти. Этот метод называют r-методом Полларда (вариация метода метод Полларда, общая идея известна также под названием "baby step, giant step"). В дальнейшем основные идеи построения эффективных алгоритмов для решения задачи дискретного логарифмирования были связаны с, так называемым, методом решета. Долгое время асимптотически наиболее эффективным (асимптотическая оценка сложности – ). Метод был реализован и применен для логарифмирования в простых полях при p длиной до 67 десятичных знаков. Последним существенным достижением в этой области является метод решета числового поля Д. Гордона. Асимптотически метод более эффективен, чем все предыдущие: оценка его трудоемкости . Однако его практическая реализация сложнее: пока имеется сообщение, что этим методом удалось решить задачу дискретного логарифмирования в простом поле при p длиной 40 десятичных знаков. Для этого специалистам немецкого университета Universitat des Saarlandes в Саарбрюккене потребовались 21 час работы рабочей станции Sparc и 40 минут работы суперкомпьютера Cray.

Задача разложения целых чисел на множители. По сравнению с задачей дискретного логарифмирования задача факторизации чисел или разложения их на множители имеет более длительную историю, ведомую обычно с античных времен от Эратосфена (предположительно 284 - 202 гг. до н.э.), а в дальнейшем связанную с именами таких великих математиков, как Фибоначчи (предположительно 1180-1250 гг.), Ферма (1601-1665 гг.), Эйлер (1707-1783 гг.), Лежандр (1752-1833 гг.), Гаусс (1777-1855 гг.). В большинстве случаев удается разложить число на множители с помощью пробных делений на первые (маленькие) простые числа. Задача становится содержательной, когда требуется разложить число, равное произведению двух больших простых чисел (например, число Блюма). В 70-х годах был предложен (p-1)-метод Полларда, эффективный для случая, когда p-1 раскладывается на маленькие простые множители, где p — один из делителей факторизуемого числа. Вскоре, как развитие данного решения появился (p+1)-метод Полларда. Следующим шагом в этом направлении стала идея использования псевдослучайных отображений (r-метод Полларда). Этим методом было разложено на множители 8-ое число Ферма (– число длиной 77 десятичных знаков). На сегодняшний день, как и для задачи дискретного логарифмирования, основные продвижения в проблеме факторизации связаны с развитием методов решета, в которых выделяют следующие этапы развития: методы линейного решета, методы квадратичного решета и метод решета числового поля. Сегодня практически наиболее эффективным для факторизации чисел длиной до 130 десятичных знаков остается метод квадратичного решета. Его асимптотическая оценка трудоемкости – , где . Именно этим методом был решен предложенный Райвестом практический пример вскрытия системы RSA, для чего потребовалось разложить на множители число длиной 129 десятичных знаков. Методы решета числового поля асимптотически более эффективны (оценка трудоемкости: ), но применимы только для чисел вида n=re-s, где r и s сравнительно малы. На практике считается, что рассматриваемые методы следует применять для чисел из интервала 10130 Задача построения больших простых чисел с некоторыми дополнительными условиями. Для нужд практической криптографии актуальна проблема построения быстрых алгоритмов нахождения "случайных" простых чисел заданной длины. Скорость работы алгоритмов построения больших простых чисел важна для систем, использующих схему RSA, так как ключами в них собственно и являются большие простые числа. Обычно в этих алгоритмах реализуется какая-либо модификация "решета" с последующей проверкой чисел на простоту. При этом используется тот факт, что простые числа расположены достаточно "густо": результаты о плотности распределения простых чисел среди натуральных образуют отдельное направление в теории чисел. На сегодня известно достаточно много алгоритмов проверки чисел на простоту: как правило, ответ на этот вопрос дает уже малая теорема Ферма. Проблема заключается в доказательстве того, что проверяемое число действительно является простым. Несмотря на то, что большинство из таких алгоритмов имеет субэкспоненциальную оценку сложности, на практике они показывают вполне приемлемую скорость работы. Существуют вероятностные алгоритмы, имеющие полиномиальные оценки сложности. Важной особенностью известных методов дискретного логарифмирования является существенная зависимость их трудоемкости от мощности простого поля, в котором решается задача. Отсюда возникает необходимость разработки как алгоритма проверки простого числа на "слабость", так и алгоритма, позволяющего гарантированно избегать построения "слабых" чисел.



Задача вычисления мощности группы точек эллиптической кривой над конечным полем. Точные формулы для мощностей групп точек эллиптической кривой известны только для достаточно узкого класса кривых. На практике актуальна задача построения систем асимметричной криптографии, где сама кривая является "долговременным" ключом. Таким образом возникает проблема построения эффективных алгоритмов вычисления мощности группы точек эллиптической кривой произвольного вида. Здесь известен вероятностный алгоритм Шенкса, основанный на идее типа "baby step, giant step". Метод имеет оценку сложности , где q — мощность конечного поля. Из детерминированных алгоритмов известен метод Скуфа, основанный на использовании эндоморфизма Фробениуса и имеющий оценку сложности , где q — мощность конечного поля. Однако для практических вычислений метод, по-видимому, мало пригоден.

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


Глава 3. Основные результаты


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

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

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


  • общая память — все процессора работают в едином адресном пространстве с равноправным доступом к памяти

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

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

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





Рисунок 3.1. Средства параллельных вычислений

Выделяют следующие классы параллельных систем.

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

  • PVP — параллельная векторная система. Основным признаком PVP-систем является наличие специальных векторно-конвейерных процессоров. Как правило, несколько таких процессоров работают одновременно над общей памятью (аналогично SMP) в рамках многопроцессорных конфигураций.

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

  • NUMA — система с неоднородным доступом к памяти. NUMA представляет собой нечто среднее между SMP и MPP. В NUMA память физически распределена, но логически общедоступна. Масштабируемость NUMA-систем ограничивается объемом адресного пространства и возможностями операционной системы.

  • Кластеры — недорогой вариант MPP. Обычно это сеть из персональных компьютеров или рабочих станций общего назначения, которая объединяется в ''виртуальную многопроцессорную машину''. Для связи узлов используется одна из стандартных сетевых технологий (Ethernet, Myrinet).


Глава 4 . Обсуждение результатов


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

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

В случае полуавтоматической системы распараллеливания, в тексте последовательной программы выделяются блоки, которые могут выполняться параллельно. Обычно, в текст вставляются специального вида комментарии, которые игнорируются обычным (последовательным) компилятором. Примером такой полуавтоматической системы может служить Adaptor — одна из реализаций спецификации HPF: High Performance Fortran (http://www.crpc.rice.edu/HPFF).

Автоматические системы распараллеливания выполняют декомпозицию последовательного алгоритма самостоятельно. На вход подается последовательная программа, на выход выдается её параллельный аналог. Пример такой системы: BERT77 — средство автоматического распараллеливания Fortran-программ (http://www.plogic.com/bert.html). Системы из этого класса так же могут помочь пользователю выяснить, можно ли распараллелить данную задачу, оценить время ее выполнения, определить оптимальное число процессоров.

Заключение


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

Квантовая криптография еще не вышла на уровень практического использования, но приблизилась к нему. В мире существует несколько организаций, где ведутся активные исследования в области квантовой криптографии. Среди них IBM, GAP-Optique, Mitsubishi, Toshiba, Национальная лаборатория в Лос-Аламосе, Калифорнийский технологический институт (Caltech), а также молодая компания MagiQ и холдинг QinetiQ, поддерживаемый британским министерством обороны. Диапазон участников — от крупнейших мировых вендоров до небольших начинающих компаний — свидетельствует о начальном периоде в формировании рыночного сегмента, когда в нем на равных могут участвовать и те, и другие.

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


Список литературы к реферату


  1. W. Diffie, M.E Hellman. New directions in cryptography IEEE Transactions of Information Theory, v. IT-22, pp. 644–654, Nov 1976.

  2. Жиль Брассар. Современная криптология. — М., «ПОЛИМЕД», 1999.

  3. Bruce Schneier. Applied Cryptography, Second edition: Protocols, Algorithms, and Source Code in C. — John Wiley & Sons. Inc., 1996.

  4. Beresford N. Parlett. Some basic information of information-based complexity theory Bulletin of the AMS, v. 26, n. 1, pp. 3–27, January 1992.

  5. В.В.Воеводин, Вл.В.Воеводин. Параллельные вычисления. — Санкт-Петербург : БХВ-Петербург, 2002 — 608 стр.

  6. А.Е.Дорошенко. Математические модели и методы организации высокопроизводительных параллельных вычислений. — Киев: Наукова думка, 2000 — 176 стр.

  7. Ю.В. Капитонова, А.А. Летичевский. Математическая теория проектирования вычислительных систем. — Москва: Наука, 1988 — 295 стр.

Предметный указатель к реферату


MPP

NUMA


PVP

SMP


RSA

Кластеры

Интернет ресурсы в предметной области исследования


  1. http://www.ssl.stu.neva.ru/psw/crypto/. Перспективы развития и использования алгоритмов в криптографии.

  2. http://mechanoid.narod.ru/parallel/phd/index.html. Полуавтоматическая система декомпозиции последовательных программ для параллельных вычислителей с распределенной памятью.

  3. http://www.intuit.ru/department/calculate/paralltp. Теория и практика параллельных вычислений.

  4. http://www.icyb.kiev.ua.

  5. http://parallel.ru/research/apps.html. Информация о суперкомпьютерных приложениях.

  6. http://parallel.ru/computers/classes.html. Основные классы современных параллельных компьютеров.

  7. http://www.osp.ru/pcworld/2003/03/165312/. Hard или soft: что выбрать?

  8. http://parallel.ru/computers/classes.html. Основные классы современных параллельных компьютеров.

  9. http://www.parallel.ru/tech/tech_dev/ifaces.html. Коммуникационные библиотеки.

  10. http://parallel.ru/research/apps.html. Задачи для суперкомпьютеров.


Действующий личный сайт в WWW


www.lesia-kaigorodova.narod.ru

Граф научных интересов




Смежные специальности

01.01.07 – вычислительная математика

Теория и методы параллельных вычислений.

Численные методы и алгоритмы решения прикладных задач.



01.01.05 – теория вероятностей и математическая статистика

Статистические выводы и анализ данных.

Последовательный анализ.



Основная специальность


01.01.09 – дискретная математика и математическая кибернетика

Теория сложности вычислений.

Теоpия кодиpования и кpиптогpафия.

Дискpетная оптимизация.



Сопутствующие специальности

05.13.01 — системный анализ, управление и обработка информации

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

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



05.13.11 – математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

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




Презентация магистерской диссертации


Просмотреть презентацию

Список литературы к выпускной работе


  1. Bruce Schneier. Applied Cryptography, Second edition: Protocols, Algorithms, and Source Code in C. — John Wiley & Sons. Inc., 1996.

  2. Beresford N. Parlett. Some basic information of information-based complexity theory Bulletin of the AMS, v. 26, n. 1, pp. 3–27, January 1992.

  3. В.В.Воеводин, Вл.В.Воеводин. Параллельные вычисления. — Санкт-Петербург : БХВ-Петербург, 2002 — 608 стр.

  4. www.vak.org.by

Приложения

Приложение 1. Презентация магистерской диссертации

















Приложение 2. Генерация параметров для алгоритма формирования ЭЦП в соответствии со стандартом СТБ 1176.2-99 в системе Mathematica

Параметры r & l



Исходные случайные данные









Генератор последовательностей на основе случайных данных















Размерности случайных последовательностей









Алгоритм генерации параметров p & q































Генерация параметра a





Обратный элемент к