Разработка программного средства реализации шифрования с применением асимметричных криптосистем

Доказательство 

• представим в двоичной системе счисления:

, где

• положим и затем для вычислим

 

• найденное   и будет искомым значением

Т.к каждое вычисление на шаге 2 требует не более трёх умножений  по модулю и этот шаг выполняется раз, то сложность алгоритма может быть оценена величиной .

Чтобы проанализировать время выполнения операций с открытым и секретным ключами, предположим, что открытый ключ   и секретный ключ удовлетворяют соотношениям . Тогда в процессах их применения выполняется соответственно и умножений по модулю.

Таким образом время выполнения операций растёт с увеличением количества ненулевых битов в двоичном представлении открытой экспоненты e. Чтобы увеличить скорость шифрования, значение e часто выбирают равным 17, 257 или 65537 — простым числам, двоичное представление которых содержит лишь две единицы: 17 = 0x11, 257 = 0x101, 65537 = 0x10001 (простые числа Ферма).

По эвристическим оценкам  длина секретной экспоненты d, нетривиальным  образом зависящей от открытой экспоненты e и модуля n, с большой вероятностью близка к длине n. Поэтому расшифрование данных идёт медленнее чем шифрование, а проверка подписи быстрее чем подписание.

Алгоритм RSA намного медленнее  чем DES и другие алгоритмы блочного шифрования.

7. Криптоанализ RSA

Основная статья: Криптоанализ RSA

На 2009 год система шифрования на основе RSA считается надёжной, начиная с размера  в 1024 бита.

Группе учёных из Швейцарии, Японии, Франции, Нидерландов, Германии и США удалось успешно вычислить  данные, зашифрованные при помощи криптографического ключа стандарта RSA длиной 768 бит. По словам исследователей, после их работы в качестве надежной системы шифрования можно рассматривать только RSA-ключи длиной 1024 бита и более. Причём от шифрования ключом длиной в 1024 бит стоит отказаться в ближайшие три-четыре года.

Как следует из описания работы, вычисление значений ключа осуществлялось общим методом решета числового поля.

На первый шаг (выбор  пары полиномов степени 6 и 1) было потрачено  около полугода вычислений на 80 процессорах, что составило около 3 % времени, потраченного на главный этап алгоритма (просеивание), который выполнялся на сотнях компьютеров в течение почти двух лет. Если интерполировать это время на работу одного процессора AMD Opteron 2.2ГГц с 2Гб памяти, то получилось бы порядка 1500 лет. Обработка данных после просеивания для следующего ресурсоёмкого шага (линейной алгебры) потребовалось несколько недель на малом количестве процессоров. Заключительный шаг после нахождения нетривиальных решений ОСЛУ занял не более 12 часов.

Решение ОСЛУ проводилось  с помощью метода Видемана на нескольких раздельных кластерах и длилось чуть менее 4 месяцев. При этом размер разреженной матрицы составил 192 796 550х192 795 550 при наличии 27 795 115 920 ненулевых элементов (то есть в среднем 144 ненулевых элементов на строку). Для хранения матрицы на жёстком диске понадобилось около 105 гигабайт. В то же время понадобилось около 5 терабайт сжатых данных для построения данной матрицы.

В итоге группе удалось  вычислить 232-цифровой ключ, открывающий  доступ к зашифрованным данным.

Исследователи уверены, что с использованием их метода факторизации взломать 1024-битный RSA-ключ будет возможно в течение следующей декады.

Зная разложение модуля на произведение двух простых чисел, противник может легко найти секретную экспоненту и тем самым взломать RSA. Однако на сегодняшний день самый быстрый алгоритм факторизации — решето обобщённого числового поля (General Number Field Sieve), скорость которого для k-битного целого числа составляет

 для некоторого ,

не позволяет разложить  большое целое за приемлемое время. 

8. Применение RSA

Система RSA используется для защиты программного обеспечения  и в схемах цифровой подписи.

Также она используется в открытой системе шифрования PGP и иных системах шифрования (к примеру, DarkCryptTC и формат xdc) в сочетании с симметричными алгоритмами.

Из-за низкой скорости шифрования (около 30 кбит/с при 512 битном ключе  на процессоре 2 ГГц), сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайным  ключом (сеансовый ключ), а с помощью RSA шифруют лишь этот ключ, таким образом реализуется гибридная криптосистема. Такой механизм имеет потенциальные уязвимости ввиду необходимости использовать криптостойкий генератор случайных чисел для формирования случайного сеансового ключа симметричного шифрования и эффективно противостоящий атакам симметричный криптоалгоритм (в данное время широкое применение находят AES, IDEA, Serpent, Twofish).

14. Алгоритм Эль-Гамаля

1. Общие сведения

Схема Эль-Гамаля (Elgamal) —  криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе стандартов электронной цифровой подписи в США и России (ГОСТ Р 34.11-94).

Схема была предложена Тахером Эль-Гамалем (англ.) в 1984 году. Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличии от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана.

 

В 1985 году Т.Эль-Гамаль (США) предложил следующую схему на основе возведения в степень по модулю большого простого числа P. 
Задается большое простое число P и целое число A, 1 < A < P. Сообщения представляются целыми числами M из интервала 1 < M < P.

2.  Шифрование сообщений

Протокол передачи сообщения M выглядит следующим образом.

абоненты знают числа A и P;

абоненты генерируют независимо друг от друга случайные числа:

Ka, Kb

удовлетворяющих условию:

1 < K < P

получатель вычисляет  и передаёт отправителю число B, определяемое последовательностью:

В = A ^Kb mоd(P)

отправитель шифрует  сообщение M и отправляет полученную последовательность получателю

C = M * B ^Ka mоd(P)

получатель расшифровывает полученное сообщение

D = ( A ^Ka ) ^-Kb mоd(P)

M = C * D mоd(P)

В этой системе открытого шифрования та же степень защиты, что для алгоритма RSA с модулем N из 200 знаков, достигается уже при модуле P из 150 знаков. Это позволяет в 5-7 раз увеличить скорость обработки информации. Однако, в таком варианте открытого шифрования нет подтверждения подлинности сообщений.

Подтверждение подлинности отправителя

Для того, чтобы обеспечить при открытом шифровании по модулю простого числа P также и процедуру  подтверждения подлинности отправителя Т.ЭльГамаль предложил следующий протокол передачи подписанного сообщения M:

абоненты знают числа A и P;

отправитель генерирует случайное число и хранит его  в секрете:

Ka

удовлетворяющее условию:

1 < Ka < P

вычисляет и передаёт получателю число B, определяемое последователньостью:

В = A ^Ka mоd(P)

Для сообщения M (1 < M < P):

выбирает случайное  число L (1 < L < P), удовлетворяющее условию

( L , P - 1 ) = 1

вычисляет число

R = A ^L mоd(P)

решает относительно S

M = Ka * R + L * S mоd(P)

передаёт подписанное  сообщение

[ M, R, S ]

получатель проверяет  правильность подписи

A M = ( B ^R ) *  ( R ^S ) mоd(P)

 

В этой системе секретным  ключом для подписывания сообщений  является число X, а открытым ключом для проверки достоверности подписи  число B. Процедура проверки подписи  служит также и для проверки правильности расшифровывания, если сообщения шифруются.

Генерация ключей

1. Генерируется случайное простое число длины битов.
2. Выбирается произвольное целое число , являющееся первообразным корнем по модулю .
3. Выбирается случайное целое число такое, что .
4. Вычисляется .
5. Открытым ключом является тройка , закрытым ключом — число .

3. Работа в режиме шифрования

Шифрсистема Эль-Гамаля является фактически одним из способов выработки открытых ключей Диффи  — Хеллмана. Шифрование по схеме  Эль-Гамаля не следует путать с алгоритмом цифровой подписи по схеме Эль-Гамаля.

1. Шифрование

Сообщение шифруется следующим образом:

1. Выбирается сессионный ключ — случайное целое число такое, что .
2. Вычисляются числа   и .
3. Пара чисел является шифротекстом.

2. Расшифрование

Зная закрытый ключ , исходное сообщение можно вычислить из шифротекста по формуле:

При этом нетрудно проверить, что

и поэтому

Нетрудно видеть, что  длина шифротекста в схеме  Эль-Гамаля длиннее исходного сообщения M вдвое.

3. Схема шифрования

Глава II.

15. Практическая часть.

Генерация ключей:

Выбираются случайные  простые числа P и Q так, что Q<P, затем  выбирается случайное число X<P , которое  является секретным ключом

1. Вычисляется y = Q^x mod p.

Открытым ключом является тройка (p,q,y), закрытым ключом — число x.

Шифрование

В дальнейшем будем понимать под М — исходное сообщение.

1. Выбирается случайное  секретное число k, взаимно простое  с p − 1.

2. Вычисляется a = q^Kmod p, b = y^K*Mmod p, где M — исходное сообщение.

Пара чисел (a,b) является шифротекстом. При этом длина шифротекста  длиннее исходного сообщения M вдвое.

Дешифрование

Зная закрытый ключ x, исходное сообщение получается из шифротекста (a,b) по формуле: M = b / (a^X)mod p.

Нетрудно проверить, что a^X=Q^KX mod p

b/a^X=(y^KM)/a^X=(Q^KX*M)/Q^KX=M(mod p)

 

Порядок выполнения работы:

1. проверить 2 больших  чиcла на взаимную простоту;

2. вычислить степень  большого целого числа;

3. решить сравнение  a*x=b mod p

 

Код:

 

void __fastcall TMainForm::RunElGamaleExecute(TObject *Sender)

{

RunElGamale->Enabled=false;

 

  unsigned int G,P,X,Y,M,A,B, cnt=0,K;

ElGmlB:

ListBox4->Clear();

Application->ProcessMessages();

cnt=0;

  P=simple[random(R-3)+3];    

  G=random(P-2)+1;

  X=random(P-2)+1;

/* 

  P=11; G=2;

  X=8;

  */

  Y=XYmodP(G,X,P);

 

ListBox4->Items->Add("Публичные параметры:  P="+IntToStr(P)+",  G="+IntToStr(G));

ListBox4->Items->Add("B:  X="+IntToStr(X)+" секретный параметр");

ListBox4->Items->Add("B:  Y="+IntToStr(Y)+" публикуется");

 

  M=random(P-2)+1;

// M=5;

 

  ListBox4->Items->Add("A: Сообщение M="+IntToStr(M));

  do

  {

   K=simple[random(R)];

   cnt++;

   if (cnt> 0xffff) goto ElGmlB;

  }

  while(K%(P-1) == 0) ;

 

//  K=9;

 

  ListBox4->Items->Add("A: Для подписи  сообщения M выбирается случайное число K="+IntToStr(K));

 

  A=XYmodP(G,K,P);

  ListBox4->Items->Add("A->B:  a="+IntToStr(A)+" передается по сети"); 

/* B=0;

  do

  {

   B++;

   cnt++;

   if (cnt> 0xffff) goto ElGmlB;

  }

  while(M != ((X*A+K*B)%(P-1)));

  B=  (unsigned int)pow(Y,K) % P;*/

  B=Y_K_M_mod_P(Y,K,M,P);

  ListBox4->Items->Add("A->B:  b="+IntToStr(B)+" передается по сети");

  //(M*aX mod P)=(b mod P);

 

  M=0;

  do

  {

   M++;

   cnt++;

   if (cnt> 0xffff) goto ElGmlB;

  }

  while( M_A_X_mod_P(M,A,X,P)   != (B%P));

//  Y_K_M_mod_P

ListBox4->Items->Add("В:  M="+IntToStr(M)+"");

 RunElGamale->Enabled=true;

 

 

 

 

16. Заключение

Криптография сегодня - это важнейшая часть всех информационных систем: от электронной почты до сотовой связи, от доступа к сети Internet до электронной наличности. Криптография обеспечивает подотчетность, прозрачность, точность и конфиденциальность. Она предотвращает попытки мошенничества в электронной коммерции и обеспечивает юридическую силу финансовых транзакций. Криптография помогает установить вашу личность, но и обеспечивает вам анонимность. Она мешает хулиганам испортить сервер и не позволяет конкурентам залезть в ваши конфиденциальные документы. А в будущем, по мере того как коммерция и коммуникации будут все теснее связываться с компьютерными сетями, криптография станет жизненно важной.

Криптосистемы разделяются  на симметричные и с открытым ключом.

Алгоритмы криптосистемы  с открытым ключом можно использовать

• Как самостоятельные средства для защиты передаваемой и хранимой информации
• Как средства распределения ключей. Обычно с помощью алгоритмов криптосистем с открытым ключом распределяют ключи, малые по объёму. А саму передачу больших информационных потоков осуществляют с помощью других алгоритмов.
• Как средства аутентификации пользователей.