ReSQL.ru
     
powered by simpleCommunicator - 2.0.60     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Шифрование Эль-Гамаля
8 сообщений из 8, страница 1 из 1
Шифрование Эль-Гамаля
    #33727569
curiousxp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
curiousxp
Участник
Всем привет.
Надо написать прогу которая шифрует данные по алгоритму эль-гамаля, с шифрованием проблем нет, вот алгоритм дешифрования что то туго доходит.
Кто нибудь может помочь, желтельно с конкретным примером.
...
Рейтинг: 0 / 0
15.05.2006, 15:19
| Ответить | Цитировать | Написать  
Шифрование Эль-Гамаля
    #33728674
curiousxp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
curiousxp
Участник
Никто не знает?
Вот алгоритм
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
СХЕМА ШИФРОВАНИЯ ЭЛЬ ГАМАЛЯ 
Схема Эль Гамаля [ 4 ], предложенная в  1985  г., может быть ис¬пользована как для шифрования, так и для цифровых подписей. Безопасность схемы Эль Гамаля обусловлена сложностью вычисления дискретных логарифмов в конеч-ном поле.
Для того чтобы генерировать пару ключей (открытый ключ-секретный ключ), сначала выбирают некоторое большое простое число P и большое целое число G, причем G<Р. Числа P и G могут быть распространены среди группы пользователей.
Затем выбирают случайное целое число X, причем Х<Р. Число X являет-ся секретным ключом и должно храниться в секрете. Далее вычисляют Y = G^X (mod P). Число Y является открытым ключом.
Для того чтобы зашифровать сообщение М, выбирают слу¬чайное целое число K,  1  < K < Р- 1 , такое, что числа K и (Р- 1 ) явля¬ются взаимно простыми.
Затем вычисляют числа
	a = G^K (mod P),
	b = Y^K (mod P).
Пара чисел (а, b) является шифртекстом. Заметим, что длина шифртекста вдвое больше длины исходного открытого текста M. Для того чтобы расшифро-вать шифртекст (а, b), вычисляют
	M = (b/a^X) (mod P)	( 6 . 1 )
Поскольку
	a^X = G^(KX) (mod P), 
	(b/a^X) =(Y^KM)/a^X  = (G^(KX) M)/G^(KX)  = M (mod P)
то соотношение ( 6 . 1 ) справедливо.

Никак не пойму раздел шифрования!
...
Рейтинг: 0 / 0
16.05.2006, 00:12
| Ответить | Цитировать | Написать  
Шифрование Эль-Гамаля
    #33728677
madgol
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
madgol
Участник
Определитесь, что именно не понятно дешифрование или шифрование
...
Рейтинг: 0 / 0
16.05.2006, 00:18
| Ответить | Цитировать | Написать  
Шифрование Эль-Гамаля
    #33728838
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Откуда описание-то ? Там где-то М потерялось. Судя по описанию расшифровки должно быть b = Y^KМ (mod P). Ну и конечно деление в 6.1 - не деление вовсе, а умножение на обратное по модулю.
...
Рейтинг: 0 / 0
16.05.2006, 08:08
| Ответить | Цитировать | Написать  
Шифрование Эль-Гамаля
    #33728869
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Ну и пример :)
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
void extended_euclid(__int64 a, __int64 b, __int64 *x, __int64 *y, __int64 *d)
/* calculates a * *x + b * *y = gcd(a, b) = *d */
{
  __int64 q, r, x1, x2, y1, y2;
  if (b ==  0 ) {
    *d = a, *x =  1 , *y =  0 ;
    return;
  }
  x2 =  1 , x1 =  0 , y2 =  0 , y1 =  1 ;
  while (b >  0 ) {
    q = a / b, r = a - q * b;
    *x = x2 - q * x1, *y = y2 - q * y1;
    a = b, b = r;
    x2 = x1, x1 = *x, y2 = y1, y1 = *y;
  }
  *d = a, *x = x2, *y = y2;
}

__int64 invmod(__int64 a, __int64 n)
/* computes the inverse of a modulo n */
{
  __int64 d, x, y;
  extended_euclid(a, n, &x, &y, &d);
  if (d ==  1 )
    if (x> 0 )
      return x;
    else
      return x+n;
  return  0 ;
}

__int64 powmod(__int64 a, __int64 k, __int64 n)
{
  __int64 b= 1 ;
  while (k) {
    if (k% 2 == 0 ) {
      k /=  2 ;
      a = (a*a)%n;
      }
    else {
      k--;
      b = (b*a)%n;
      }
  }
  return b;
}

main() {
__int64 P,G,X,Y,K,M,a,b;
P= 65537 ;
G= 32768 ;
X= 45621 ;
Y=powmod(G,X,P);
K= 37121 ;
M= 11111 ;
a=powmod(G,K,P);
b=powmod(Y,K,P)*M % P;
printf("%Ld\n",b*invmod(powmod(a,X,P),P) % P); // должно быть равно М
}
...
Рейтинг: 0 / 0
16.05.2006, 08:45
| Ответить | Цитировать | Написать  
Шифрование Эль-Гамаля
    #33729293
curiousxp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
curiousxp
Участник
BarloneОткуда описание-то ? Там где-то М потерялось. Судя по описанию расшифровки должно быть b = Y^KМ (mod P). Ну и конечно деление в 6.1 - не деление вовсе, а умножение на обратное по модулю.

Вот это место поточнее можно, никак не могу получить исходное число по формуле (6.1)
...
Рейтинг: 0 / 0
16.05.2006, 11:22
| Ответить | Цитировать | Написать  
Шифрование Эль-Гамаля
    #33729441
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
вот чо нашел
...
Рейтинг: 0 / 0
16.05.2006, 12:05
| Ответить | Цитировать | Написать  
Шифрование Эль-Гамаля
    #33737560
zloy den
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zloy den
Участник
Хм, на RSA похоже(сейчас алгоритм не вспомню). Или просто из одной группы?
...
Рейтинг: 0 / 0
19.05.2006, 09:50
| Ответить | Цитировать | Написать  
8 сообщений из 8, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Шифрование Эль-Гамаля
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]