VPF::Генерация закрытого ключа RSA - Форум программистов

CMD

Дата 22.8.2006, 01:54 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 30
Регистрация: 1.8.2006

Репутация: нет
Всего: 1

Не понимаю как делать сабж. В описаниях алгоритма RSA обычно пишут : "Закрытый ключ d вычисляется из условия ed mod (p-1) (q-1)=1" или ссылаются на расширеный алгоритм Эвклида.
Вот пример из книги Брюса Шнайера: p=47; q=71; n=3337; e=79;
Как у него с помощью расширенного алгоритма Эвклида получилось d=1019 - неврубаюсь.
Алгоритм Эвклида пытался понять, но не получается, помогите пожалуйста разобраться.

Kuvaldis

Дата 22.8.2006, 03:20 (ссылка)

(нет голосов)

Загрузка ...

механик-вредитель

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 1
Всего: 61

CMD,

Цитата

Алгоритм Эвклида пытался понять, но не получается, помогите пожалуйста разобраться.

Вот вариант лекции по алгебре славного БГУИР (проще я, често говоря, не видел)

Код


Если три целых числа n, m, k связаны соотношением
N=M*K,
то m,k – делители n, а n – кратное m и k.
Теорема о делении с остатком: Для любых целых чисел a и b существуют единственные числа q и r, такие, что a=bq+r,   0 r<|b|, q – неполное частное, r – остаток.
Лемма 1: Если в равенстве m1+m2+…+mn=n1+n2+…+nn все слагаемые – целые числа и все, кроме последнего, делятся на целое k, то и отмеченное слагаемое должно делиться на k.

Общий делитель чисел m1,m2,…mt – это такое число Д, на которое делятся все перечисленные числа. НОД – наибольшее из них.

Алгоритм Евклида
НОД чисел a и b совпадает с последним отличным от нуля остатком в следующей цепочке равенств:

a = bq+r
b = rq1+r1
r = r1q2+r2
….
rk-1=rkqk+1+rk+1   НОД
rk=rk+1qk+2

1) Любой общий делитель a и b является делителем rk+1
В самом деле, согласно лемме 1, r делится на Д. Тогда r1 делится на Д. И т.д.

2) rk+1 является общим делителем a и b. 
В самом деле, из последних двух соотношений видно, что rk-1 делится на rk+1
3) rk+1 – натуральное число, которое делится на все общие делители a     и b. Значит, это и есть НОД a и b.
Эта цепочка всегда оборвётся, т.к. 0 ri<ri-1

Если что, справшивай (ну, и гуглом пользуйся smile

)

--------------------

Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей

CMD

Дата 22.8.2006, 15:43 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 30
Регистрация: 1.8.2006

Репутация: нет
Всего: 1

А можно пару простых наглядных примеров с числами? smile

Kuvaldis

Дата 22.8.2006, 21:04 (ссылка)

(нет голосов)

Загрузка ...

механик-вредитель

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 1
Всего: 61

Здесь посмотри

--------------------

Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей

CMD

Дата 22.8.2006, 23:59 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 30
Регистрация: 1.8.2006

Репутация: нет
Всего: 1

Алгоритм Эвклида я понял, даже функцию сделал:

Код


int Euclid()
{
GetDlgItemTextA(FindWindow(0,"TEST"), IDC_EDIT1, A , 20);
GetDlgItemTextA(FindWindow(0,"TEST"), IDC_EDIT6, B , 20);
int a=atoi(A);
int b=atoi(B);
int r=1;
while (r!=0)
{
r=a%b;
a=b;

 if(r!=0)b=r;
}
itoa (b, NOD, 10);
SetDlgItemTextA(FindWindow(0,"TEST"), IDC_EDIT12, NOD);
 return 0;
}

но меня интересует именно расширеный алгоритм :

Код


Методом Евклида решается в целых числах (!) уравнение e*d+(p-1)(q-1)*y=1. 
Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит 
множество пар (d,y), каждая из которых является решением уравнения в целых числах.

P.S. Не надо на меня смотреть как на идиота, я ещё только 1 курс техникума закончил... smile

, хотя какая разница smile

Это сообщение отредактировал(а) CMD - 23.8.2006, 00:09

Kuvaldis

Дата 23.8.2006, 01:13 (ссылка)

(нет голосов)

Загрузка ...

механик-вредитель

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 1
Всего: 61

CMD,

Цитата

но меня интересует именно расширеный алгоритм :

Извини, начал с простого, думал, ты этого не понимаешь. Тогда усаживайся поудобней и слушай сагу smile

:

Из алгоритма Евклида можно вывести следующее свойство НОД (наибольший общий делитель) :
Если D = НОД(А, В) но D можно представить в виде

D = А * К + В * Т

где К, Т - целые числа

Отсюда критерий взаимной простоты 2-х чисел:

1 = А * К + В * Т     // D = 1

В общем случае коэффициенты К, Т находятся из алгоритма следующим образом (что и является конструктивным доказательством данного утверждения):

Пусть А = 1001. В = 390
Найдем их НОД
1001 = 390 * 2 + 221      (1)
390 = 221 * 1 + 169        (2)
221 = 169 * 1 + 52          (3)
169 = 3 * 52 + 13            (4)
52 = 13 * 4
Так как последний отличный от нуля остаток равен 13, то НОД = 13

А теперь, как рекурсивный подъем, делаем вуаля:
из (4):    НОД = 169 + 52 * (-3)
из (3):    52 = 221 + 169 * (-1)
             Отсюда: НОД = 169 + (221 + 169 * (-1)) * (-3) = 221 * (-3) + 169 * 4

из (2):   169 = В + 221 * (-1)
             Отсюда НОД = 221 * (-3) + (В + 221 * (-1)) * 4 = В * 4 + 221 * (-7)

из (1):   221 = А + В * (-2)
             Отсюда НОД = В * 4 + (А + В * (-2)) * (-7) = А * (-7) + В * 18

Т.е. К = -7,  Т = 18

Цитата

Методом Евклида решается в целых числах (!) уравнение e*d+(p-1)(q-1)*y=1.
Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит
множество пар (d,y), каждая из которых является решением уравнения в целых числах.

В твоем случае НОД = 1, А = е, В = (p-1)(q-1)
d = К, y = Т.

Дальше вроде понятно (см. выше) smile

--------------------

Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей

Kuvaldis

Дата 24.8.2006, 16:29 (ссылка)

(нет голосов)

Загрузка ...

механик-вредитель

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 1
Всего: 61

CMD,
Вот рекурсивный алгоритм решения

Код


//---------------------------------------------------------------------------
int NOD_a_b(int a, int b, int& t, int& k)
{
   int  m;       // целочисленный коэффициент при делении
   int  r;       // остаток при делении
   int  k0, t0;  // текущие коэффициенты при подъеме (на выходе ответ)
   int  NOD;

   m = - a / b;  // с минусом
   r = a % b;
   if (r)
   {
      NOD = NOD_a_b(b, r, t, k);     // рекурсивный вызов
      t0 = k;
      k0 = t + k * m;
      t = t0;
      k = k0;
   }
   else
   {
      NOD = b;
      t = 0;
      k = 1;
   }
   return NOD;
}
//--------------------------------------------------------------------

--------------------

Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей

CMD

Дата 29.8.2006, 23:00 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 30
Регистрация: 1.8.2006

Репутация: нет
Всего: 1

Спасибо Kuvaldis! Вопрос исчерпан.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »