Автор работы: Пользователь скрыл имя, 24 Мая 2010 в 03:27, Не определен
ВВЕДЕНИЕ 3
Глава 1. Система открытого распределения ключей 4
1.1. История создания системы распределения ключей. 4
1.2. Система распределение ключей Диффи-Хеллмана 6
1.3. Описание средств разработки. 7
Глава 2. Программная реализация открытого распространения ключей Диффи-Хеллмана. 9
2.1. Математические основы алгоритмов используемых в работе. 9
2.1.1. Сложение и вычитание 9
2.1.2. Умножение «в столбик». 10
2.1.3. Возведение целого числа в квадрат. 12
2.1.4. Деление. Вычисление остатка. 13
2.1.5. Тест Рабина— Миллера 16
2.1.6. Модульное возведение в степень 18
2.1.7. Генерация простого числа 20
2.1.8. Разложение числа на простые множители. 23
2.1.9. Нахождение первообразного корня. 24
Глава 3. Оценка алгоритма. 27
3.1. Оценка стойкости алгоритма. 27
3.2. Оценка скорости работы алгоритма. 27
ЗАКЛЮЧЕНИЕ 29
Литература. 30
}
for(i=32;i>=0;i--)
n=i+1;
if(b[i]!=0)
}
m=ai-n;
//printf("b = %x ",b[n-1]);
d=1;
if(b[n-1]<128){
for(i=2;i<=
d*=2;
if((b[
}
}//оценить d шаг 1
mult(b,d,bt);//шаг 1 b~=b*d
for(i=0;i<=63;i++)
for(i=m+n;i>=n;i--
s=0;
for(k=i-n;k<
t=r[k]
rt[k]=
s=t>>
}// шаг 3.1 r~=r*d
if(rt[i]==
else qt=((rt[i]*256+rt[i-1])/bt[n-
while((bt[n-
qt-=1;
}// шаг 3.2
mult(b,qt,
for(k=i;k>=
if(r[
}
if(rt[
}// шаг 3.3
mult(b,qt,
s=0;
for(k=i-n;k<
t=r[k]
r[k]=
s=t>>
}
c[i-n]=qt;
m-=1;
}
В итоге: r - остаток от деления ,c – целое от деления.
На сегодняшний день для проверки чисел на простоту чаще всего используется тест Рабина-Миллера, основанный на следующем наблюдении. Пусть число п нечетное и , где 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>=
t=st[
st[k]=
r=t%2;
}
if(int(st[0]
}//находим n-1=(2^s)*q где n-простое
for(i=0;i<=6;i++){
osn[i]=rand(
}//генерируем
step(c);
x=comp_sp(c,
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;
}
При обычном рекурсивном способе: 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{
}bit;
}cod;
cod.pol=st[i];
pole[i*8+0]=cod.
pole[i*8+1]=cod.
pole[i*8+2]=cod.
pole[i*8+3]=cod.
pole[i*8+4]=cod.
pole[i*8+5]=cod.
pole[i*8+6]=cod.
pole[i*8+7]=cod.
}//Представление числа в битовом формате
for(k=255;k>=0;k--){
r=k;
if(int(pole[k])==
}