Поздравляем участников олимпиады

Поздравляем участников IX Открытого Чемпионата Харькова по спортивному программированию студентов факультета информатики и вычислительной техники Запорожского национального технического университета II курса групп ИВТ-410, ИВТ-710 Тоцкого Владислава, Смирнова Алексея, Палия Александра, Ильина Владислава, Белки Родиона, Курсона Сергея и I курса групп ИВТ-411, ИВТ-421 (занявших почетное 4 место в юношеском туре) Задорожнего Евгения, Бессонова Андрея и Косаренко Викторию.

Лекция 1. Основы программирования

Для установки среды разработки Borland C++ 5.02 запустите файл Setup.exe, который находится в папке инсталляции программы. Укажите папку, в которой вы желаете хранить программу, например C:\BC5. Значения параметров в диалоговых окнах установки рекомендуется оставить без изменений, нажимая кнопку Next.

Открыть среду разработки С++ для работы можно с помощью команды меню:

Пуск | Все программы | Borland C++ 5.02 | Borland C++.

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

Чтобы создать новый документ, выберите пункт меню

File| Text edit.

Чтобы сохранить документ, выберите пункт меню

File | Save as…

Содержание отчета по лабораторной работе:

  1. Титульный лист.
  2. Цель работы.
  3. Условие задачи.
  4. Блок-схема алгоритма.
  5. Текст программы.
  6. Результат работы программы (скриншот).
  7. Ответы на контрольные вопросы, написанные от руки (необязательно).

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

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

IX Открытый Чемпионат Харькова по спортивному программированию

  11 декабря 2011 г. Молодёжное научное общество «Q-BIT» и кафедра Информационных систем Харьковского национального экономического университета проводят традиционный Открытый Чемпионат Харькова по спортивному программированию.

 Принять участие в Чемпионате могут:

  • команды высших и общеобразовательных учебных заведений г. Харькова
  • команды высших и общеобразовательных учебных заведений в режиме ONLINE.

Для участия в Чемпионате необходимо:

Logo_Open   До 05.12.2011 зарегистрироваться в системе проведения турниров на сайтеhttp://khcup.qbit.org.ua. Если ваша команда уже принимала участие в Чемпионатах Харькова, то можно использовать существующую учётную запись для входа в систему.
Внимательно заполнить информацию о команде в разделе „Профайл”
Выбрать дивизион (соревнование, в котором вы примите участие):
Первый дивизион рассчитан на участников с опытом олимпиадного программирования. Желательно иметь представление про алгоритмы на графах, динамическое программирование, быстрые алгоритмы сортировки и поиска, алгоритмы на строках, сложные структуры данных.
Второй дивизион для участников с уверенными знаниями базовых алгоритмических структур и типов данных (массивы, строки).
Третий дивизион для начинающих. Достаточно уметь читать числа из текстового файла, записывать в текстовый файл результат выполнения программы, применять базовые алгоритмические структуры (ветвление и цикли).
Выбрать способ участия в Чемпионате:

  • Онсайт для участников из г. Харькова
  • Онлайн, если вы участвуете в Чемпионате в реальном времени через интернет.

Регистрация на Чемпионат до 5 декабря 2011 г.

Подробнее о чемпионате на официальном сайте http://khcup.qbit.org.ua

Лекция 1. Общие понятия и определения

Несанкционированный доступ (НСД) – доступ, который нарушает правила использования информационных ресурсов компьютерной системы, установленые для ее использования.

НСД является реализацией преднамеренной угрозы и называется атакой или нападением на компьютерную систему.

Защита информации – это комплекс организационно-технических мер, направленных на предотвращение НСД к содержащемуся в ней смыслу.

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

Основные угрозы безопасности информации:

  1. Уничтожение.
  2. Копирование (ознакомление).
  3. Искажение.
  4. Нарушение работоспособности системы (Например, отказ в обслуживании).

Защита информации направлена на сохранение свойств информации:

 1. Конфиденциальность – это свойство информации быть известной только допущенным и прошедшим проверку (авторизованным) субъектам системы (пользователям, процессам, программам).

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

3. Доступность – свойство компонента или ресурса быть доступным для авторизованных законных субъектов системы.

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

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

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

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

Уровни защиты информации:

1. Правовой (законодательный). Закон Украины про информацию (10.02.1992). Закон Украины про защиту информации в автоматизированных системах (05.07.1994). Государственный стандарт Украины ДСТУ 3396.0-96 – «техническая защита информации, основные положения». ДСТУ 3396.1-96 – «защита информации, техническая защита информации». ДСТУ 3396.2-97 – «защита информации, техническая защита информации, сроки и определения».
2. Морально-этический.
3. Административный.
4. Физический.
5. Аппаратно-программный.

Распространенные угрозы:

1. Троянский конь – программа, которая наряду с действиями, описанными в ее документации, выполняет некоторые другие действия, ведущие к нарушению безопасности системы и деструктивным результатам. Часто такие программы маскируются под полезные утилиты. Опасность троянского коня заключается в дополнительном блоке команд, вставленных в исходную безвредную программу. Этот блок может сработать при наступлении какого-либо условия (даты, состояния системы), либо по команде извне. Радикальный способ защиты от этой  угрозы заключается в создании замкнутой среды исполнения программ, которые должны храниться и защищаться от НДС.

2. Компьютерный вирус – подобно живому организму рождается, размножается и умирает. Первое определение, данное Фрэдом Коэном из Университета Южной Калифорнии: «Компьютерный вирус – это программа, которая может заражать другие программы, модифицируя их посредствам включения в них своей, возможно измененной копии, причем последняя сохраняет  способность к дальнейшему размножению». Наиболее опасны загрузочные вирусы.

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

 Для защиты от указанных вредоносных программ необходимо принятие ряда мер:
1)      исключение НДС к исполняемым файлам;
2)      предварительное тестирование приобретаемых программных средств;
3)      контроль целостности исполняемых файлов и системных областей;
4)      создание замкнутой среды исполнения программ.

Алгоритм модульного возведения в степень

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

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

Стандартным алгоритмом выполнения последовательности операций является бинарный алгоритм. В нем используется бинарное представление множителя (показателя степени) [1]. Рассмотрим более подробно алгоритм модульного возведения  в степень.

Алгоритм. Бинарное модульное возведение в степень.
Исходные данные: показатель степени n¹0, основание a, модуль m.
Результат: y=an(mod m).
1. Если n =1, то y:=(mod m); закончить работу алгоритма.
2. k:=ln–2; y:=a (mod m), где ln – длина числа n в битах;
3. Для i, принимающего значения от k до 0, выполнить шаги 4-5.
4. y := y2 mod m.
5. Если i-й бит n  равен 1, то y := y*a mod m.
6. Закончить работу алгоритма.

Этот алгоритм называется также SX-алгоритмом[1]. Смысл такого названия состоит в следующем: считаем, что S(squaring) соответствует операции возведения в квадрат, а X – операции умножения на основание. К примеру, возведем основание a  в степень 23 по модулю  p. Запишем 23 в двоичной системе счисления как 10111. Далее, пропуская самый левый бит, который всегда равен 1 запишем под каждой цифрой 1 SX, а под каждой цифрой 0 – X.

1 0 1 1 1
S SX SX SX

Двигаясь слева направо, получим определяющую строку SSXSXSX. Помня, что S — это возведение в квадрат, а X – умножение на основание, получаем следующую последовательность операций:

(((((((((((a2mod p)2)mod p)*a) mod p)2 mod p)*a) mod p)2 mod p)*a) mod p)=a23 mod p,

что соответствует действительности.

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

1. Кнут Д. Искусство программирования для ЭВМ. Получисленные алгоритмы / Д.Кнут. – М.: Мир. – Том 2. – 1976. – 788 с.

2. Вельшенбах М. Криптография на Си и С++ в действии. Учебное пособие  / Вельшенбах М. – М.: Издательство Триумф. – 2004. – 464 с.

Как поймать сообщение WM_KEYDOWN в диалоговом окне

При создании диалогового приложения в MS Visual C++ с использованием библиотеки классов MFC наткнулась на одну проблему. Решалась задача передвижения фигуры на экране с помощью клавиш управления курсором (стрелки вверх, вниз, влево, вправо). Имя проекта Move. Не могла поймать сообщение о нажатии клавиш WM_KEYDOWN, чтобы определить направление движения. Определение функций

void CMoveDlg::OnKeyDown(UINT nChar, UINT nRepCnt, UINT nFlags)
void CMoveDlg::OnKeyUp(UINT nChar, UINT nRepCnt, UINT nFlags)

ничего не дало.

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

Оказывается, WM_KEYDOWN диспетчеризуется в IsDialogMessage по логике работы диалога. Потому надо ловить его до того.

Привожу пример рабочего кода:

BOOL CMoveDlg::PreTranslateMessage(MSG* pMsg)
{
if(pMsg->message == WM_KEYDOWN)
{
switch(pMsg->wParam)
{
case VK_RIGHT:
AfxMessageBox("VK_RIGHT",MB_OK,NULL);
break;
case VK_LEFT:
AfxMessageBox("VK_LEFT",MB_OK,NULL);
break;
case VK_UP:
AfxMessageBox("VK_UP",MB_OK,NULL);
break;
case VK_DOWN:
AfxMessageBox("VK_DOWN",MB_OK,NULL);
break;
}
}
else CDialog::PreTranslateMessage(pMsg);
return true;
}

А ларчик просто открывался :)

Основа алгоритмов цифровой подписи

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

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

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

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

Литература

  1. ГОСТ Р 34.10-2001. Государственный стандарт российской федерации. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки цифровой подписи. М.: Госстандарт России, 2001.
  2. ДСТУ 4145-2002. Державний стандарт України. Інформаційні технології. Криптографічний захист інформації. Цифровий підпис, що ґрунтується на еліптичних кривих. Формування та перевірка. Київ:-Держстандарт України, 2003.
  3. Don Johnson, Alfred Menezes, Scott Vanstone. The Elliptic Curve Digital Signature Algorithm (ECDSA)//Certicom Research,Canada, 2001.
  4. J.H. Silverman “The Arithmetic of Elliptic Curve”, GTM 106,Springer-Verlag,New York, 1986
  5. Koblitz N. Elliptic Curve Cryptosystems // Mathematics of Computation. 1987. Vol. 48, №  177.P.203-209.
  6. Штанько С.В. Эллиптические кривые в криптографии // Проблемы информационной безопасности. Компьютерные системы. № 2, 2003, С. 65-74.
  7. Ростовцев А.Г. Алгебраические основы криптографии.– СПб.: НПО «Мир и семья», ООО «Интерлайн», 2000.–354с.

 

Криптография и цифровая подпись

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

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

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

На сегодняшний день в Украине уже имеется возможность доказать юридическую значимость электронных документов, подписанных с помощью цифрового ключа. Этому, безусловно, способствовали Закон Украины «Про електронні документи та електронний документообіг»[1],  устанавливающий основные организационно-правовые положения электронного документооборота и использования электронных документов, и закон Украины «Про електронний цифровий підпис», определяющий правовой статус электронной цифровой подписи и регулирующий отношения, которые возникают при использовании электронной цифровой подписи. Читать далее →

Как работать с длинными числами

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

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

Формы главной функции main() в С++

Сегодня мы поговорим о главной функции main() и ее формах. Традиционно, первая программа на языке программирования С++ выводит на экран строку «Hello, world!». Попробуем выполнить это несложное действие (работаем в Microsoft Visual Studio). Назовем наш проект program1.

#include <iostream>
using namespace std;
int main()
{
cout<<«Hello, world!»<<endl;
cin.get();
return 0;
} Читать далее →