1.3.1 Построение дерева целей

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

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

В начале построим дерево целей нашего проекта, которое приведено на рис. 1.

Рис.1. Дерево целей

Таблица 1. Описание дерева целей

1.3.2 Требования по надежности

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

Можно выделить два основных аспекта надежности:

Наличие в готовом программном продукте ошибок

Готовность программного продукта к могущим возникнуть исключительным (нештатным) ситуациям

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

Ошибки возникающие на этапе проектирования ПП

Ошибки возникающие на этапе кодирования

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

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

Второй аспект подразделяется на:

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

недопустимых сочетаний исходных данных;

влияние операционного окружения.

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

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

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

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

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

Использование средств разработки с встроенным контролем качества написанного программного кода и средств отладки программного кода;

Использование эталонных тестовых вариантов;

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

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

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

1.3.3 Технические требования

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

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

· Производительность ЦП рабочей станции;

· Количество оперативной памяти установленной на рабочей станции.

программный шифрование криптография эллиптический

1.3.4 Требования по адаптивности

После построения дерева целей мы приходим к необходимости использовать для оценки качества проектных решений X один критерий. А именно: удобство. Поэтому при наличии вектора критериев U(x) = (U₁(x), U₂(x), U₃(x), U₄(x)) будем говорить не об оптимальности по какому-то отдельному критерию, а об оптимальности по вектору критериев. Для оценки предпочтения одного решения над другим построим интегральный критерий. Наличие интегрального критерия сводит процедуру выбора оптимального решения по многим критериям к однокритериальной задаче математического программирования.

Найти: x⁰ = arg max _x (min) Y[u(x)], при условии, что x Є P*, где P* - множество сравниваемых решений.

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

Y[u(x)]=r_kk [ u_k(x) ], r_k = 1 (1)

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

Приведем эту теорему:

Для того чтобы интегральный критерий имел аддитивный вид, необходимо и достаточно выполнение условия независимости по предпочтению для каждой пары критериев (u_i, u_j), i j, i,j = 1….K.

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

Y(u) = r₁₁(u₁) + r₂₂(u₂) + r₃₃(u₃) + r₄₄(u₄)

Где функция _k - зависимость веса критерия от его значения;

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

u_k - частный критерий эффективности

Для этого воспользуемся алгоритмом независимого шкалирования. Выберем один из значимых показателей -удобство ПП. Опишем частные критерии эффективности которые будут использоваться при построении аддитивного интегрального критерия:

· Наличие дружественно графического интерфейса пользователя - границы изменения от 1 до 10, цель оптимизации максимизация данного критерия.

· Время реакции системы не превышает 2 секунды - границы изменения от 1 до 10, цель оптимизации максимизация данного критерия.

· Достаточно полная справочная система - границы изменения от 1 до 10, цель оптимизации максимизация данного критерия.

· Выбор справочных значений из списка - границы изменения от 1 до 10, цель оптимизации максимизация данного критерия.

1. Наличие дружественно графического интерфейса пользователя. Используя понятие среднего по ценности значения критерия построим функцию ₁(u₁).Значения сведены в таблицу 7.

Таблица 7.

₁

U₁

Рис. 2. Функция ценности критерия.

2.

Время реакции системы не превышает 4 секунды. Используя понятие среднего по ценности значения критерия построим функцию ₂(u₂). Значения сведены в таблицу 8.

Таблица 1.

₂

U₂

Рис. 3. Функция ценности критерия

3. Достаточно полная справочная система. Используя понятие среднего по ценности значения критерия построим функцию ₃(u₃) Значения сведены в таблицу 9

Таблица 2.

₃

U₃

Рис. 4. Функция ценности критерия

4. выбор справочных значений из списка. Используя понятие среднего по ценности значения критерия, построим функцию ₄(u₄). Значения сведены в таблицу 10.

Таблица 3.

₄

U₄

Рис. 5. Функция ценности критерия

Теперь вычислим r_i для этого введем вектора:

U₁ = (U₁*, 1, 1, 1)

U₂ = (1,U₂*, 1, 1 )

U₃ = (1, 1, U₃*, 1)

U₄= (1, 1, 1, U₄*)

Выберем для U_k* такие значения,что бы эти вектора были приблизительно равны, тогда получим: U₁* = 6, U₂* = 8, U₃* = 7, U₄= 8. Из эквивалентности U₁ и U₂, U₁ и U_3, U₁ и U₄, и дополнив условием нормировки коэффициентов r_k получим систему из четырех уравнений:

r_{1 1}(6) = r_{2 2}(8)

r_{1 1}(6) = r_{3 3}(7)

r_{1 1}(6) = r_{4 4}(8)

r₁ + r₂ + r₃ + r₄ = 1

Подставляя значения _k из соответствующего графика где:

₁(6) = 0,625

₂(8) = 0,75

₃(7) = 0,68

₄(8) = 0,84

и выражая все через r₁ получаем следующие значения коэффициентов r_k

r₁ = 0,28

r₂ = 0,23

r₃ = 0,25

r₄ = 0,20

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

Отсюда аддитивный интегральный критерий будет иметь вид:

Y = 0,28 ₁(u₁) + 0,23 ₂(u₂) + 0,25 ₃(u₃) + 0,20 ₄(u₄) (2)

где функция _k - зависимость веса критерия от его значения;

u_k - частный критерий эффективности;

₁(u₁) - зависимость веса критерия (наличие развитого графического интерфейса) от его значения;

₂(u₂) - зависимость веса критерия (время реакции системы не превышает 4 секунды) от его значения;

₃(u₃) - зависимость веса критерия (достаточно полная справочная система) от его значения;

₄(u₄) - зависимость веса критерия (выбор справочных значений из списка) от его значения.

Используя значения из таблиц 7,8,9(пункт 1.3.6) находим коэффициенты для уравнений прямых, рисунки 2,3,4 (пункт 1.3.6), выбранных участков графиков, получаем следующие значения зависимости веса критерия от его значения:

1) ₁=0,083u₁+0,17, берем из таблицы 10 (пункт 1.3.5.) значение u1 и получаем ₁=0,083*7 + 0,17 = 0,75

2) ₂=0,125u₂-0,25, берем из таблицы 10 (пункт 1.3.5.) значение u2 и получаем ₁=0,125*10 - 0,25 = 1

3) ₃=0,0625u₃+0,25, берем из таблицы 10 (пункт 1.3.5.) значение u3 и получаем ₃=0,0625*5+0,25=0,56

4) ₄=0,083u₄+0,17, берем из таблицы 10 (пункт 1.3.5.) значение u₄ и получаем ₄= 0,083*6+0,17=0,67

Подставим ₁, ₂, ₃ и ₄ в уравнение аддитивного интегрального критерия 2 и рассчитаем оценку ПП.

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

На основании выполненного анализа сформулируем требования по критерию удобство ПП:

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

· Значение показателя - время реакции системы не превышает 2 секунды -должно быть не менее 10 баллов по выбранной шкале;

· Значение показателя - достаточно полная справочная система - должно быть не менее 5 баллов по выбранной шкале;

· Значение показателя - выбор справочных значений из списка - должно быть не менее 6 балла по выбранной шкале.

· Значение аддитивного интегрального критерия должно быть не менее 0,71.

2. Проектный раздел

Формулы для r_i могут быть переписаны следующим образом:

r₁ = a + b(- q₀)

r₂ = b ? r₁q₁ = a(? q₁) + b(1 + q₁q₀)

gcd(a,b) = r_n = as + bt

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

Связь с цепными дробями

Отношение a / b допускает представление в виде цепной дроби:

.

При этом цепная дробь без последнего члена равна отношению коэффициентов Безу t / s, взятому со знаком минус:

.

Ускоренные версии алгоритма

· Одним из методов ускорения целочисленного алгоритма Евклида является использование симметричного остатка:

·

где

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

ECЕS

· конечное поле GF(p);

· эллиптическая кривая E(GF(p));

· большой простой делитель количества точек кривой p;

· точка G, координаты которой имеют порядок, что и число p.

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

· выбирает случайное целое число Kc, 1 < Kc < p -1;

· вычисляет точку Kо = Kc P.

При этом секретным ключом пользователя является число Kc, открытым ключом - точка Kо. Кроме того, сообщение M разбивается на блоки длиной 2L - 16 бит, где L равно ближайшему большему целому от log2 p;

· выбирается случайное целое число k, 1 < k < n - 1;

· вычисляется точка (х1, у1) = kP;

· вычисляется точка (х2, у2) = k Kо.

Известно несколько подходов к зашифрованию - расшифрованию информации, предполагающих использование эллиптических кривых. Мы рассмотрим наиболее простой из этих подходов. Как было изложено выше, зашифрованное сообщение пересылается в виде значения (х, у) для точки Pm. Здесь точка Рm будет представлять зашифрованный текст и впоследствии будет расшифроваться. В качестве параметров данной криптосистемы рассматривается точка G и эллиптическая группа Еp (а, b).

Пользователи А и В выбирают секретные ключи KcА и KcB, а также генерируют открытые ключи KоA = KcА P и KоB = KcB P соответственно. Чтобы зашифровать сообщение Рm, пользователь А выбирает случайное положительное целое число k и вычисляет криптограмму Сm с помощью открытого ключа стороны В, - KоB, состоящую из двух точек

Cm = {(kG), (Pm + k KоB) }.

Чтобы расшифровать эту криптограмму, пользователь В умножает первую точку (kP) на cвой секретный ключ KcB и вычитает результат из второй точки:

(Рm + k KоB) - KcB (kP) = Рm + k(KcB P) - KcB (kP) = Рm.

Пользователь А замаскировал сообщение Рm с помощью добавления к нему маски k KоB.. Однако следует заметить, что никто не сможет убрать маску k KоB, кроме пользователя, который знает значение k и имеет личный ключ KcB. Противнику для восстановления сообщения придется вычислить k по данным P и kP, что является трудной задачей. В качестве примера возьмем

р = 751, ЕP = (-1, 188) и P = (0, 376).

Все расчеты в данном примере выполняются по модулю p.

Предположим, что пользователь А отправляет пользователю В сообщение, которое кодируется точкой Рm = (562, 201), и выбирает случайное число k = 386. Открытым ключом В является KоB = (201, 5). Мы имеем 386(0, 376) = (676, 558) и (562, 201) + 386(201, 5) = (385, 328).

Таким образом, пользователь А должен послать зашифрованный текст {(676, 558), (385, 328)}.

2.4 Выполнение алгоритмов

1. Выбираем случайным образом число р, с учетом вьшолнения условий: р>3;

2. Выбор коэффициениов эллиптической кривой а и b:

3. Проверяем выполнение условия

4. Выбираем случайным образом координату X точки эллиптической кривой;

5. Вычисляем значение координаты точки У,

;

6. Определяем поле Галуа GF(p), а также количество точек на эллиптической кривой p.

7. Выбираем точку Р, координаты которой имеют порядок, что и число p

8. Определяет порядок подгруппы группы точек эллиптической кривой q;

9. После чего отправитель пересылает получателю следующие данные:

· конечное поле GF(q);

· эллиптическую кривая E(GF(q));

· порядок подгруппы группы точек эллиптической кривой q;

· точку Р.

10. Выбираем случайное число КсA - секретный ключ отправителя,

1 < КсА < p-1;

11. Вычисляем точку КоА - открытый ключ отправителя КоА = КсAР;

12. Выбираем случайное число k (2-й секретный ключ отправителя),

1 < k < p-1;

13. Вычисляем точку кР (которая является первой точкой криптограммы);

Действия получателя:

14. Выбираем случайное число КсB - секретный ключ получателя, 1 < КсВ <p - 1;

15. Вычисляем точку КоВ - открытый ключ отправителя КсB = КсB Р;

16. Отправляем получателю свой открытый ключ КoB;

Действия отправителя:

17. Разбиваем исходное сообщение на блоки (символы ASCII (CP Win 1251));

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

;

19. Отправляем криптограмму C,

;

Действия получателя:

20. Получатель получив криптограмму, умножает ее первую часть (первую точку кР) на собственный секретный ключ КсВ и получает результат КсВ(кР);

21. Вычитает полученный результат КсВ(кР) из точек второй части криптограммы в результате чего получает исходное сообщение.

3. Специальный раздел

1. Устанавливаем начальные значения:

2. Вычисляем значения по формулам:

Последовательно выполняем вычисление шага 2. В ответ пойдет последний отличный от нуля остаток r:

Далее не считаем, так как процесс остановился - получен нулевой остаток. В ответ идут вычисленные на предыдущем шаге значения r5 = 1 - это НОД, u5 = -32 - это коэффициент перед 200, v5 - коэффициент пред 173.

3. Теперь, имея обратный элемент поля (равный 37), мы умножаем его на 151, и затем берем модуль от значения:

37 * 151 mod 200=187;

4. Данное значение и есть х, в уравнении x*173 = 151 mod 200 проверяем:

187*173 mod 200=32351 mod 200 = 151.

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

Результаты совпадают

Алгоритм формирования конечного поля Галуа GF(p) и подсчет количества точек эллиптической кривой n=#Ep

Возьмем р = 7, а = 2, b = 6.

Рассмотрим кривую:

Проверяем условие:

Итак, данная кривая несингулярна. Рассчитаем координату первой точки:

Координаты первой точки найдены G1[5,1]. Находим следующую точку поля, путем удваивания первой точки

Теперь чтобы найти значение преобразуем текущее значение к виду: 2*х = mod 7, после чего применяем алгоритм нахождения обратного элемента с помощью расширенного алгоритма Евклида. В результате получаем .

Находим третью точку поля:

Преобразуем, текущее значение к виду: 6*х = 5 mod 7, и также применим алгоритм нахождения обратного элемента Евклида. В результате получим .