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

      if ( int(pole[r])==0) c[0]=1;

            else

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

                        c[i]=osn[i];

                  }

      for(k=r-1;k>=0;k--){

            step2(c,d);

            for(t=31;t>=0;t--) c[t]=d[t];

            if(int(pole[k])==1){

            mult_mod(c,osn,d);

            for(t=31;t>=0;t--) c[t]=d[t];

            }

      }

      }

      2.1.7. Генерация простого числа

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

      Алгоритм 7 Генерация простого числа, [Молдовян Н.А. и др., 2004].

      Вход. Разрядность к искомого числа р ; параметр t ≥ 1

      Выход. Число р, простое с вероятностью не менее

      1. Сгенерировать случайное k-битное число

      2. Положить b_k=1 , b₀=1

      3. Проверить, что р не делится на простые числа 3, 5, 7, ...,251 .

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

            4.1. Выбрать случайное число а, 2 < а <р - 2.

            4.2. Проверить число р тестом Миллера-Рабина для основания а. Если число р не прошло тест, то p = p+2 и вернуться на шаг 3.

      5. Результат: p.

      Равенство b_k=1 на шаге 2 гарантирует, что длина числа p в точности равна к бит, равенство b₀=1 обеспечивает нечетность числа p.

      Код функции random (генерация простого числа): 

      void random(unsigned char c[33]){

      unsigned int prost[54]={2,3,5,7,…, 241,251};

      unsigned char copy_mod[33]={0};

      int w,x,i,k,t,s,f,g=2,r,z,flag=0;

            srand(time(0));

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

                  mod[i]=rand();

            }//генерация простого числа

            mod[0]|=1;

            mod[31]|=128; //не четное и 256 бит

            st[0]=mod[0]-1;

            for(k=1;k<=31;k++){

                  st[k]=mod[k];

            }//st= простое-1

      for(w=0;;w++){

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

                  copy_mod[r]=mod[r];

                  mod2[r]=mod[r];

            }

            flag=0;

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

            r=0;

            for(k=31;k>=0;k--){

                  t=mod[k]+(r<<8);

                  r=t%prost[i];

            }//проверка на  делимость на маленькие простые  числа

            if(r==0){//число составное

                  flag=1;

                  break;

            }

      }

            if(flag==0){

            x=rabin();//проверка на  простоту

            if(x==1){

                  for(k=0;k<=6;k++){//еще  7 проверок на простоту

                        st[0]=mod[0]-1;

                        for(f=1;f<=31;f++){

                              st[f]=mod[f];

                        }

                        x=rabin();

                        if(x==0)break;//ели не  прошло тест

                  }

                  if(x!=0){

                              x=razlogenie();//если простое

                                          // нахождение первообр. корня

                              if(x==1)break;//если число  разложено 

                                          //на простые и найден первообр. корень

                  }

            }

                  for(r=0;r<=31;r++)mod[r]=copy_mod[r];

            }

                  s=0;

                  g=2;

                  for(k=0;k<=31;k++){//прибавить  к проверяемому 2

                        t=mod[k]+g+s;

                        g=0;

                        s=t>>8;

                        mod[k]=t;

                        if(s==0)break;

                  }

            mod[0]|=1;

            mod[31]|=128;

            for(k=0;k<=31;k++){st[k]=mod[k];}

            st[0]-=1;

            }

      }

      2.1.8. Разложение числа на простые множители.

      В ходе реализации понадобилось разложить  большое число на простые множители  один из которых является большим.

      Алгоритм 8 Разложение числа на простые множители, [Молдовян Н.А. и др., 2004].

      Вход. Раскладываемое число n.

      Выход. Число не раскладывается на простые множители (с большим простым множителем); число раскладывается на q₁ , q₂ ,…, q_k - различных простых делителя.

      1. Создание ряда простых чисел p₁=2 ,p₂= 3,…, p₈₄₄= 6491;

      2. Положить t = 0. 

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

            3.1. Если w=n/p_i целое, t = t + 1, q_t = p_i;

            3.1. Пока w=n/p_i целое, n=n/p_i .

      4. Проверить число n  тестом Миллера-Рабина.

      Код функции разложение razlogenie() 

      int razlogenie(){

      int i,r,k,t,x,w,fl=0,counter=0;;

      unsigned char p[33]={0};

      int mass[300]={0};

      unsigned char c[33]={0};

      unsigned int prost[6900]={2,3,5,7,…,69491,69493};

      for(k=0;k<=32;k++) p[k]=mod[k];

      p[0]-=1;

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

            r=0;

            for(k=31;k>=0;k--){

                  t=p[k]+(r<<8);

                  c[k]=t/prost[i];

                  r=t%prost[i];

            }

      for(k=0;k<=31;k++) p[k]=c[k];

            if(r==0){

                  for(k=0;k<=31;k++) mod[k]=p[k];

                  if(fl!=i){

                        fl=i;

                        mass[counter]=prost[i];

                        counter++;

                  }

                  i--;

            }

            if(r!=0){

                  for(k=0;k<=31;k++) p[k]=mod[k];

            }

      }

      x=rabin();

      if(x==1){

            pervoobr(mass);//вычисление первообразного корня

      }

      return x;

      }

      2.1.9. Нахождение первообразного корня.

      Утверждение

      Пусть q₁ , q₂ ,…, q_k - различные простые делители функции Эйлера от числа п. Для того чтобы число g, взаимно простое с п, было первообразным корнем по модулю п, необходимо и достаточно, чтобы это g не удовлетворяло ни одному из сравнений:

       , ,…, .

      Алгоритм 9 Нахождение первообразного корня, [Молдовян Н.А. и др., 2004].

      Вход. Простое число n, q₁ , q₂ ,…, q_k - различные простые делители функции Эйлера

      Выход. Первообразный корень g.

      1. Генерация числа 1 < g < n.

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

            2.1. Если перейти к шагу 1.

      3. Число g первообразный корень по модулю n.

      Код функции pervoobr (нахождение первообразного корня): 

      void pervoobr(int mass[300]){

      unsigned char g[33]={0};

      unsigned char c[33]={0};

      unsigned char b[33]={0};

      int i,k,t,x,flag;

      srand(time(0));

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

            g[i]=mod[i];

            mod[i]=mod2[i];

            osn[i]=0;

      }

      for(k=0;k<=1000;k++){

            flag=2;

            for(i=0;i<=28;i++) osn[i]=rand();

            del(mod,g,st);

            step(c);

            x=rav(c);

            if(x!=0){

                  flag=1;

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

                        c[i]=0;

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

                              if(mass[i]!=0){

                                    c[0]=mass[i];

                                    c[1]=(mass[i]>>8);

                                    del(mod,c,b);

                                    for(t=0;t<=31;t++)st[t]=b[t];

                                    step(b);