При создании программы возник вопрос: каким образом представлять большие числа? Решение было принято о том что число можно занести в массив типа unsigned char в который помещается два шестнадцатеричных числа, которые обрабатываются как 256-разрядные:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Положить

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

2.1. Вычислить

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

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

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

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

ai+bi+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 ? ai < B, 0 ? bi < B

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Код функции 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 = ci+j+aiaj+s , ci+j=t (mod B) , .

2.3. Положить ci+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.

Пусть , , если то значение удовлетворяет неравенству , где 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. Если ri=bn-1, то положить; в противном случае найти где .

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

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

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

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

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

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

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

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

ai=i+1;

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

}

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

n=i+1;

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

}

m=ai-n;

//printf("b = %x ",b[n-1]);

d=1;

if(b[n-1]<128){

for(i=2;i<=7;i++){

d*=2;

if((b[n-1]*d)>=128) break;

}

}//оценить d шаг 1

mult(b,d,bt);//шаг 1 b~=b*d

for(i=0;i<=63;i++){r[i]=a[i];}//шаг 2

for(i=m+n;i>=n;i--){//шаг 3

s=0;

for(k=i-n;k<=i;k++){

t=r[k]*d+s;

rt[k]=t;

s=t>>8;

}// шаг 3.1 r~=r*d

if(rt[i]==bt[n-1]) qt=255;

else qt=((rt[i]*256+rt[i-1])/bt[n-1]);// шаг 3.1 r~=r*d

while((bt[n-2]*qt)>((rt[i]*256+rt[i-1]-qt*bt[n-1])*256+rt[i-2])){

qt-=1;

}// шаг 3.2

mult(b,qt,bqt);

for(k=i;k>=i-n;k--){

if(r[k]<bqt[k-m]){

qt-=1;

break;

}

if(rt[k]>bqt[k-m])break;

}// шаг 3.3

mult(b,qt,bqt);

s=0;

for(k=i-n;k<=i;k++){

t=r[k]-bqt[k-m]+s;

r[k]=t;

s=t>>8;

}

c[i-n]=qt;

m-=1;

}

В итоге: r - остаток от деления ,c - целое от деления.

2.1.5 Тест Рабина--Миллера

На сегодняшний день для проверки чисел на простоту чаще всего используется тест Рабина-Миллера, основанный на следующем наблюдении. Пусть число п нечетное и , где r -- нечетное. Если п простое, то для любого а ? 2, взаимно простого с п, выполняется условие теоремы Ферма (аr = 1 (mod n)). Разложим число на множители:

Тогда в последнем произведении хотя бы одна из скобок делится на п, то есть либо аr=1(mod п), либо среди чисел а , аr, ..., найдется сравнимое с -1 по модулю п.

Обращение этого свойства лежит в основе теста Рабина-Миллера.

Алгоритм 5. Тест Рабина-Миллера, [Молдовян Н.А. и др., 2004].

Вход. Нечетное целое число п ? 5.

Выход. «Число п, вероятно, простое» шли «Число п составное».

1. Представить п - 1 в виде , где число r нечетное.

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

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

4. При и выполнить следующие действия.

4.1. Положить j = 1.

4.2. Если j ? s - 1 и .

4.2.1. Положить y=y2 (mod n)

4.2.2. При у = 1 результат: «Числю п составное».

4.2.3. Положить j=j+1.

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 (нахождение первообразного корня):

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);

x=rav(b);

if(x==0) flag=0;

}

}

}

}

if(flag==1){

break;

}

}

}

корень алгоритм множитель число

Глава 3. Оценка алгоритма

3.. Оценка криптостойкости алгоритма