Реализация системы распространения ключей на основе алгоритма Диффи-Хеллмана (длиной 256 бит)

      

      Это позволяет значительно упростить  функции.

      Размещение  значений в массиве обратное, т.е. число “FF AB C4” в массиве будет представлено как: unsigned char a[3]={0xC4, 0xAB, 0xFF};

      Все функции в программе предназначены  для работы с 256-битными значениями.

      Алгоритмы арифметики целых чисел и полиномов  во многом похожи, поскольку представление  целого числа а в системе счисления  с основанием B в виде:

        
 где 0 < a_i < В, аналогично представлению полинома .

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

      2.1.1. Сложение и вычитание

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

      Пусть неотрицательные целые числа  а и b заданы в системе счисления с основанием В:

      

      

      где 0 <a_i ; b_i<B. Для удобства считаем, что оба числа имеют равную длину, при необходимости старшие разряды меньшего числа заполняем нулями.

      Сложение  выполняется «в столбик».

      Алгоритм 1. Сложение целых чисел, [Молдовян Н.А. и др., 2004].

      Вход. Целые числа , .

      Выход. Сумма .

      1. Положить

      2. Для i = 0, 1,...,п- 1 выполнить следующие действия.

      2.1. Вычислить

      2.2. Положить , .

      3. Положить с_п = s.

      4. Результат: .

      Переменная  s означает перенос в старший разряд и всегда принимает значение 0  
(при a_i+b_i+s < B) или 1 (при a_i+b_i+s ≥ B). На шаге 2.1 Может произойти не более одного переноса. Действительно:

      a_i+b_i+1 < (B-1)+(B-1)+1 < 2B-1<2B.

      Вычитание аналогично сложению изменение только в шаге 2.1.  .

      В этом случае если t отрицательное то у следующего элемента занимается 1.

      Сложность алгоритма сложения и вычитания  равна О(п).

      Код функции summa(сумма) : 

      for (i=0;i<=32;i++){

      s=a[i]+b[i]+buf; //Общее значение

      c[i]=s;//число  заносимое в ячейку

      buf=(s)>>8;//остаток

      }

      Код функции sub(разность) c = a-b : 

      for(i=0;i<=31;i++){

            s=a[i]-b[i]+buf;

            buf=s>>8;

            c[i]=s;

       }

      2.1.2. Умножение «в столбик».

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

      Пусть неотрицательные целые числа а и b заданы в системе счисления с основанием B.

      

      

      где 0 ≤ a_i < B, 0 ≤ b_i < B

      Самый очевидный способ умножения — умножение «в столбик».

      Алгоритм 2. Умножение целых чисел «в столбик», [Молдовян Н.А. и др., 2004].

      Вход. Целые числа , где 0 < b ≤ a.

      Выход. Произведение

      1. Для i = 0, 1,...,п- 1 положить c_i= 0

      2. Для i = 0, 1,...,п- 1 выполнить следующие действия.

      2.1. Для j = 0, 1,...,п- 1:

      2.1.1. Положить s= 0.

      2.1.2. Вычислить t = c_i+j+a_ib_j+s , c_i+j=t (mod B) , .

      2.2. Положить c_i+n =s.

      3. Результат:

      Во  внешнем цикле этого алгоритма  вычисляются частичные произведения , а во внутреннем — произведения , где j = 0, 1, ..., п- 1. Текущий разряд произведения равен t (mod В), а очередной перенос: . При этом на шаге 2.1.2 выполняется неравенство:

      

      Сложность умножения в «столбик» О(n²).

      Функция умножения реализована как умножение с вычислением модуля.

      Код функции mult_mod (умножение по модулю) c=a*b (mod mod):  

      void mult_mod(unsigned char a[33],unsigned char b[33],unsigned char c[33]){

      int i,j,k,s,t;

      unsigned char d[65]={0};

      for (k=0;k<=31;k++) c[k]=0; //очищение переменной

      for(i=0;i<=31;i++){

      s=0;

            for(j=0;j<=31;j++){

                  t=d[i+j]+a[i]*b[j]+s;

                  d[i+j]=t;

                  s=t>>8;

            }

            d[i+32]=s;

      }

      modul(d,mod,c); //вычисление модуля mod - глобальная переменная

      }

      2.1.3. Возведение целого числа в квадрат.

      Отдельно  реализована функция возведения в квадрат.

      Алгоритм 3. Возведение в квадрат, [Молдовян Н.А. и др., 2004].

      Вход. Целое положительное число .

      Выход. Значение

      1. Для i = 0, 1,...,п- 1 положить с_i= 0.

      2. Для i = 0, 1,...,п- 1 выполнить следующие действия.

      2.1. Положить , , .

      2.2. Для j = 0, 1,...,п- 1 вычислить t = c_i+j+a_ia_j+s , c_i+j=t (mod B) , .

      2.3.     Положить c_i+n =s.

      Результат: с .

      На  шаге 2.2 алгоритма выполняется неравенство:

      

      Это означает что t может занимать более двух разрядов в системе исчисления B.

      Сложность алгоритма возведение в квадрат  О( ).

      Код функции step2 (возведение в квадрат) b=a^2 (mod mod): 

      void step2(unsigned char a[33],unsigned char b[33]){

            unsigned char c[65]={0};

            int t,s,i,j;

            for(i=0;i<=32;i++){

                  t=c[2*i]+a[i]*a[i];

                  c[2*i]=t%256;

                  s=t>>8;

                  for(j=i+1;j<=32;j++){

                        t=c[i+j]+2*a[i]*a[j]+s;

                        c[i+j]=t%256;

                        s=t>>8;

                  }

                  c[i+33]=s;

            }

            modul(c,mod,b);//вычисление  модуля

      }

      2.1.4. Деление. Вычисление остатка.

      Для деления в общем случае используется алгоритм Д. Кнута . Будем делить «в столбик» число  на число . Найдем такое частное и остаток , что .

      При делении на каждом шаге находим частное  от деления некоторого (n+1)-разрядного числа на b, где О < R/b<В. Неравенство R/b <В эквивалентно неравенству R/B<b, откуда b:

      

      Полагая R = R - Qb, получаем 0 < R < b.

      Для определения числа Q будем использовать аппроксимацию

          [1]

      При      получаем  

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

      (1) сводится к проверке равенства .

      Теорема 1.

      Пусть ,   , если  то значение удовлетворяет неравенству , где q определяется из соотношения (1.1). 

      Алгоритм  деления с остатком. Чтобы старший  разряд делителя удовлетворял условию  теоремы 1.1, числа а и b нужно умножить на некоторое целое число d>0, такое что   где.

       ,

      Частное при этом не изменяется: . Число разрядов недолжно превышать число разрядов b, число разрядов в может быть на единицу больше, чем в а (если это не так, полагаем а_т+п = 0).Выбираем d равным степени двойки, так как умножение на d в этом случае выполняется сдвигом.

      Алгоритм  4. Деление «в столбик», [Молдовян Н.А. и др., 2004].

      Вход. Неотрицательные целые числа , ;

      Выход. Целые числа , , такие, что , .

      1. Определить такое целое число d>0, что , где

      2. Положить .

      3. Для i = m + n ,m + n - 1, ..., n выполнить следующие действия

      3.1. Если r_i=b_n-1, то положить ; в противном случае найти где .

      3.2. Пока полагать

      3.3. При положить .

      3.4. Вычислить и .

      4. Результат: ,

      Сложность алгоритма деления «в столбик» равна  О(mn).

      Реализованы две функции целочисленное деление  и вычисление остатка.

      Основной  код функций: 

      for(i=64;i>=0;i--){

                  ai=i+1;

                  if(a[i]!=0)break;