Реализация системы распространения ключей на основе алгоритма Диффи-Хеллмана длиной 256 бит (стр. 4 из 5)
4.3. При
результат: «Число п составное».5. Результат: «Число п, вероятно, простое».
В результате выполнения теста для простого числа п в последовательности a (mod n), a2r(mod n), ...,
(mod n) обязательно перед 1 должна появиться -1 (или, что то же самое, п - 1 (mod n)). Это означает, что для простого числа п единственными решениями сравнения y2 = 1 (mod n) являются у = ±1 (mod n). Если число n составное и имеет k> 1 различных простых делителей (то есть не является степенью простого числа), то по китайской теореме об остатках существует 2kрешений сравнения у2 = 1 (mod n). Действительно, для любого простого делителя piчисла п существует два решения указанного сравнения: у = ±1 (mod рi). Поэтому k таких сравнений дают 2kнаборов решений по модулям pi, содержащих элементы ± 1.Сложность алгоритма равна
Код функции rabin (поверка на простоту):
/*mod – проверяемое значение,
st – степень числа при передаче в функцию sstep();
osn – основание при вычислении
Пр: osnst (mod mod)
*/
int rabin(){
unsigned char c[33]={0};
int i,k,g,t,q,r,x,j,fl,w;
unsigned char d[33]={0};//для р.м. р-1
srand(time(0));
for(i=0;i<=31;i++) st[i]=mod[i];
st[0]-=1;
for(i=0;i<=31;i++){
d[i]=st[i];
}
for(i=0;;i++){
q=i+1;
r=0;
for(k=31;k>=0;k--){
t=st[k]+(r<<8);
st[k]=(t>>1);
r=t%2;
}
if(int(st[0])%2==1) break;
}//находим n-1=(2^s)*q где n-простое
for(i=0;i<=6;i++){
osn[i]=rand();
}//генерируем основание
step(c);
x=comp_sp(c,d);
if(x==2){
return 1;
}
x=rav(c);
if(x==0) return 1;
j=1;
while(j<=q-1){
step2(c,c);
x=rav(c);
if(x==0) return 0;
j++;
}
x=comp_sp(c,d);
if(x!=2){
return 0;
}
return 1;
}
2.1.6. Модульное возведение в степень
При обычном рекурсивном способе: a0=1, a n=(a n-1)a (mod n). Требуется n-1 операций возведения в степень по модулю т, то есть O(m2) операций модульного умножения. Если же предварительно представить показатель п в двоичном виде
где к = [log2 n], и, 
, то 
где 
. При таком способе вычисления потребуется k модульных возведений в квадрат и 
модульных умножений. Учитывая, что каждый разряд принимает значение 0 или 1 равновероятно, можно считать, в среднем требуется 1,5 log m модульных умножений.Алгоритм 6 Модульное возведение в степень, [Молдовян Н.А. и др., 2004].
Вход. Целое число а, 1 ≤ а < т; показатель степени п ≥ 2,
Выход. с = ап(mod т).
1. Положить 
.
2. Для i =k-1 , k-2 , … , 0 выполнить следующие действия.
2.1. Вычислить
2.2. При ni = 1 вычислить
.3. Результат: с.
Код функции step (степень):
osn, st, mod – глобальные переменные основание, степень, модуль соответственно.
с = osnst (mod mod)
void step(unsigned char c[33]){
int i,k,t,r;
int pole[256]={0};
unsigned char d[33]={0};
for(i=0;i<=31;i++){
union{unsigned char pol;
struct{unsigned b0:1;
unsigned b1:1;
unsigned b2:1;
unsigned b3:1;
unsigned b4:1;
unsigned b5:1;
unsigned b6:1;
unsigned b7:1;
}bit;
}cod;
cod.pol=st[i];
pole[i*8+0]=cod.bit.b0;
pole[i*8+1]=cod.bit.b1;
pole[i*8+2]=cod.bit.b2;
pole[i*8+3]=cod.bit.b3;
pole[i*8+4]=cod.bit.b4;
pole[i*8+5]=cod.bit.b5;
pole[i*8+6]=cod.bit.b6;
pole[i*8+7]=cod.bit.b7;
}//Представление числа в битовом формате
for(k=255;k>=0;k--){
r=k;
if(int(pole[k])==1)break;
}
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. Положить bk=1 , b0=1
3. Проверить, что р не делится на простые числа 3, 5, 7, ...,251 .
4. Для i = 1,2, ..., t выполнить следующие действия.
4.1. Выбрать случайное число а, 2 < а <р - 2.
4.2. Проверить число р тестом Миллера-Рабина для основания а. Если число р не прошло тест, то p = p+2 и вернуться на шаг 3.
5. Результат: p.
Равенство bk=1 на шаге 2 гарантирует, что длина числа p в точности равна к бит, равенство b0=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.
Выход. Число не раскладывается на простые множители (с большим простым множителем); число раскладывается на q1 , q2 ,…, qk - различных простых делителя.
1. Создание ряда простых чисел p1=2 ,p2= 3,…, p844= 6491;
2. Положить t = 0.
3. Для i = 1,2, ...,844 выполнить следующие действия.
3.1. Если w=n/pi целое, t = t + 1, qt = pi;
3.1. Пока w=n/pi целое, n=n/pi .
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. Нахождение первообразного корня.
Утверждение
Пусть q1 , q2 ,…, qk - различные простые делители функции Эйлера
от числа п. Для того чтобы число g, взаимно простое с п, было первообразным корнем по модулю п, необходимо и достаточно, чтобы это g не удовлетворяло ни одному из сравнений: 
, 
,…, 
.Алгоритм 9 Нахождение первообразного корня, [Молдовян Н.А. и др., 2004].
Вход. Простое число n, q1 , q2 ,…, qk - различные простые делители функции Эйлера
Выход. Первообразный корень g.
1. Генерация числа 1 < g < n.
2. Для i = 1,2, ...,k выполнить следующие действия.
2.1. Если
перейти к шагу 1.3. Число g первообразный корень по модулю n.
Код функции pervoobr (нахождение первообразного корня):
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);