WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 27 |

Большинство известных алгоритмов электронной цифровой подписи (например, [10,70]) в качестве основной алгоритмической операции используют дискретное возведение в степень. Стойкость соответствующих криптографических схем основывается (как правило, гипотетически) или на сложности извлечения корней в поле GF(n), n - произведение двух больших простых чисел, или на трудности вычисления дискретных логарифмов в поле GF(p), p - большое простое число. Чтобы противостоять известным на данный момент методам решения этих задач операнды должны иметь длину порядка 512 или 1024 битов. Понятно, что выполнение вычислений над операндами повышенной разрядности (еще будет употребляться термин «операнды многократной точности» по аналогии с операндами однократной и двукратной точности [36]) требует высокого быстродействия рабочих алгоритмов криптографических схем.

Представление чисел Пусть A, N, e - три целых положительных числа многократной точности, причем A

Алгоритм использует вычислительную систему с фиксированной длиной слова, то есть A, B, N, P и S будут также рассматриваться как векторы A[1,m], B[1,m], N[1,m], P[1,m'] и S[1,m'], где каждый элемент вектора (элемент одномерного массива) есть цифра r-ичной системы счисления, m'=m+h, величина h будет изменяться в зависимости от вида алгоритма.

Основание r такой системы будет ограничено длиной машинного слова и цифры такой системы имеют вид 0,1,...,r-1 (r выбирается как целое положительное основание с неотрицательной базой). При этом n и m связаны соотношением n=s*m, где s=log2r (в дальнейших рассуждениях log - логарифм по основанию 2). Наиболее целесообразно выбрать основание r=как наиболее экономное представление чисел в машине, ибо при r<2 на представление чисел уходит больше памяти. Например, широко принятое на практике представление десятичных чисел в двоично-десятичном коде требует на 20 % большего объема памяти, чем двоичное представление тех же чисел.

Тем не менее, иногда полезно представлять ситуацию, когда r=[36, стр.283] или r=10k, например, при отладке программ.

Следует также обратить внимание на тот факт, что при выполнении арифметических операций над числами многократной точности, например, по классическим алгоритмам Кнута [36, стр.282-302], основание r следует уменьшать, чтобы не возникло переполнение разрядной сетки. Так, для операции сложения уменьшение выполняется до r=2-1, для умножения - до r=2/2. Однако если архитектурой вычислительной системы предусмотрен флаг переноса или хранение промежуточного результата с двойной точностью, то можно возвращаться к основанию r=2.

Алгоритм A*B modulo N - алгоритм выполнения операции модулярного умножения Операнды многократной точности для данного алгоритма представляются в виде одномерного массива целых чисел. Для знака можно зарезервировать элемент с нулевым индексом. Особенности представления чисел при организации взаимодействия алгоритма с другими рабочими программами, при организации ввода-вывода и т.д. рассматриваются, например, в работе [66]. В алгоритме использован известный вычислительный метод «разделяй и властвуй» и реализован способ вычисления «цифра-зацифрой». Прямое умножение не следует делать по нескольким причинам:

во-первых, произведение A*B требует в два раза больше памяти, чем при методе «цифра-за-цифрой»; во-вторых, умножение двух многоразрядных чисел труднее организовать, чем умножение числа многократной точности на число однократной точности. Так, в работе [64] приводятся расчеты на супер-ЭВМ «CRAY-2» для 100-разрядных десятичных чисел: модулярное умножение методом «цифра-за-цифрой» выполняется примерно на 10% быстрее, чем прямое умножение и следующая за ним модульная редукция.

Алгоритм модулярного умножения (алгоритм P) приведен на рис.2.1, а на рис.2.2 представлен псевдокод процедуры ADDK.

Так как B[i][0,...,2/2-1], то проверку «if B[i]<>0» в алгоритме P можно не вводить потому, что вероятность того, что B[i] будет равняться пренебрежимо мала, если значение не достаточно малым. Ошибка затем все равно будет алгоритмом обнаружена. Проверка «if p_short-k*n_short>n_short DIV 2» позволяет представлять k числом однократной точности и работать с наименьшими абсолютными остатками в каждой итерации. Значение операнда Pi на каждом шаге итерации должно быть ограничено величиной N.

Теорема 2.1. Пусть Pi - частичное произведение P в конце i-той итерации (т.е. в конце i-того цикла FOR алгоритма P). Тогда для любого i (i=[1,...,n]) abs(Pi)

Доказательство теоремы 2.1. Доказательство теоремы проведем методом индукции.

Если k=abs(p_short) DIV n_short, где DIV - целочисленное деление, то p_short=(k+)*n_short, (2.1.6) где k - целое, 0k

Проверка «if p_short-k*n_short>n_short DIV 2» есть ни что иное, как проверка >0.5 (2.1.7) На i-том шаге алгоритм вычисляет:

P'=Pi-1*r+A*B[i] (2.1.8) Возможны два варианта:

Вариант 1. Если k=0, т.е. n_short>abs(p_short) (см. алгоритм), то суммирование при помощи процедуры ADDK не производится и утверждение теоремы выполняется, т.е. abs(Pi)



Вариант 2. Если k>0, т.е.

n_short

Вариант A:

p_short<0 (2.1.10) Из (2.1.9) и (2.1.10) следует P'<-N и так как Pi=-P'+k*N (см. алгоритм), то согласно (2.1.7) Pi=*N, если 0.5 (2.1.11) и так как Pi=-P'+(k+1)*N, то Pi=-(1-)*N, если >0.5 (2.1.12) Алгоритм P m_shifts:=0;

while n[m_shifts]=0 do begin shift_left(N and A);

m_shifts:=m_shifts+1;

end;

m:=m_shifts;

reset(P);

n_short:=N[m];

for i:=n downto 1 do begin shift_left(P); {сдвиг на 1 элемент влево или умножение P*r} if b<>0 then addk(A*B[i],{to}P);

let p_short represent the 2 high assimilated digits of P;

k:=abs(p_short) div n_short;

if p_short-k*n_short>n_short div 2 then k:=k+1;

if k>0 then begin if p_short<0 then addk(k*N,{to} P) else addk(-k*N,{to} P);

end;

end;{for} right shift P, N by m_shifts;

if P<0 then P:=P+N;

write(P); {P - результат} Рис. 2.1. Псевдокод алгоритма модулярного умножения A*B modulo N Алгоритм ADDK carry:=0;

for i:=1 to m do begin t:=P[i]+k*N[i]+carry;

P[i]:=t mod r;

carry:=t div r;

end;

P[m+1]:=carry;

write(P); {P - результат} Рис.2.2. Псевдокод алгоритма вычисления P+k*N (процедура ADDK) Вариант B:

p_short>0 (2.1.13) Из (2.1.9) и (2.1.13) следует P'>N и так как Pi=P'-k*N, то согласно (2.1.7) Pi=-*N, если 0.5 (2.1.14) и так как Pi=P'-(k+1)*N, то Pi=(1-)*N, если >0.5 (2.1.15) Во всех случаях (2.1.11), (2.1.12), (2.1.14) и (2.1.15), так как 0<1, то abs(Pi)

Теорема доказана.

Примечание. Для чего нужна проверка (2.1.7) «if p_short-k*n_short>n_short DIV 2» Пусть в конце каждой итерации P принимает максимально возможное значение Pi-1=N-1, а N, A и B[i] заведомо тоже велики: N=rn+1-1, A=rn+1-2, B[i]=r-1. Тогда на i-том шаге согласно (2.1.8):

Pi'=(rn+1-2)*r+(rn+1-2)*(r-1)=2*rn+2-rn+1-4*r+2 (2.1.16) n+2 n+2r - r - 4r + 2 2r += 2r -1- (2.1.17) n+1 n+r -1 r -При достаточно большом m, если не введена проверка (2.1.6), то k<2*r-1, по условию же 0

Pi-1=(N-1)/2 и с учетом того, что если неравенство (2.1.7) выполняется, то Pi меняет знак на противоположный (сравн. (2.1.11), (2.1.12), (2.1.14) и (2.1.15)), из (2.1.6) и (2.1.7) получим, что 0k<(1/2)*r-1, что удовлетворяет наложенному на k условию, и для представление P достаточно m+1 разряда.

В алгоритме P используется также известный метод, когда для получения частного от деления двух многоразрядных чисел, используются только старшие цифры этих чисел (см., например, алгоритм D в работе [36, стр.291-295]). Чем больше основание системы счисления r, тем ниже вероятность того, что пробное частное k от деления первых цифр больших чисел не будет соответствовать действительному частному.

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

2.2. МЕТОДЫ И СРЕДСТВА АНАЛИЗА БЕЗОПАСНОСТИ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ Широко известны различные средства программного обеспечения обнаружения элементов РПС - от простейших антивирусных программсканеров до сложных отладчиков и дизассемблеров - анализаторов и именно на базе этих средств и выработался набор методов, которыми осуществляется анализ безопасности ПО.

Авторы работ [17,45] предлагают разделить методы, используемые для анализа и оценки безопасности ПО, на две категории: контрольноиспытательные и логико-аналитические (см. рис.2.3). В основу данного разделения положены принципиальные различия в точке зрения на исследуемый объект (программу). Контрольно-испытательные методы анализа рассматривают РПС через призму фиксации факта нарушения безопасного состояния системы, а логико-аналитические - через призму доказательства наличия отношения эквивалентности между моделью исследуемой программы и моделью РПС.

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

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

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





Методы и модели анализа безопасности программ Логико-аналитические Контрольно-испытательные Методы контроля выполнения Модель программы программы и РПС Формальный аппарат Средства контроля за доказательства безопасновыполнением программ сти программы Средства анализа и Самоконтролирующиеся преобразования программ среды Средства порождения моделей РПС Методы контроля состояния среды Средства преобразования моделей и определения отношений между ними Средства анализа безопасности программ Рис. 2.3. Методы и средства анализа безопасности ПО Контрольно-испытательные методы делятся на те, в которых контролируется процесс выполнения программы и те, в которых отслеживаются изменения в операционной среде, к которым приводит запуск программы.

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

Пусть задано множество ограничений на функционирование программы, определяющих ее соответствие требованиям по безопасности в системе предполагаемой эксплуатации. Эти ограничения задаются в виде множества предикатов С={ci(a1,a2,...am)|i=1,...,N} зависящих от множества аргументов A={ai|i=1,...,M}.

Это множество состоит из двух подмножеств:

• подмножества ограничений на использование ресурсов аппаратуры и операционной системы, например оперативной памяти, процессорного времени, ресурсов ОС, возможностей интерфейса и других ресурсов;

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

Для доказательства того, что исследуемая программа удовлетворяет требованиям по безопасности, предъявляемым на предполагаемом объекте эксплуатации, необходимо доказать, что программа не нарушает ни одного из условий, входящих в С. Для этого необходимо определить множество параметров P={pi|i=1,...,K}, контролируемых при тестовых запусках программы. Параметры, входящие в это множество определяются используемыми системами тестирования. Множество контролируемых параметров должно быть выбрано таким образом, что по множеству измеренных значений параметров Р можно было получить множество значений аргументов А.

После проведения Т испытаний по вектору полученных значений параметров Pi,i=1,...,T можно построить вектор значений аргументов Ai, i=1,...,T.

Тогда задача анализа безопасности формализуется следующим образом.

Программа не содержит РПС, если для любого ее испытания i=1,...,T множество предикатов C={cj(a1i,a2i...aMi)|j=1,...,N} истинно.

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

Рассмотрим схему анализа безопасности программы контрольноиспытательным методом (рис.2.4).

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

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

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

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

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

Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 27 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.