//Возвращает остаток от деления num на comp
int mod ( int num, int comp )
{
return num%comp;
}
//возвращает (base^gauge)mod(comp)
int pow_mod ( int base, int gauge, int comp )
{
// 1 - если gague нечетно
int odd_factor;
//устанавливаем odd_factor
if ( gauge % 2 )
odd_factor = 1;
else
odd_factor = 0;
//если возведение закончено, раскручиваем стек
if ( gauge == 1 )
return base;
//Иначе, передаем результаты вниз по стеку
else
{ //если число ножителей нечетно,
if ( odd_factor )
//домножаем на base, и результат берем по модулю
return mod ( pow_mod ( mod ( base*base, comp ), gauge/2, comp ) * base, comp )
else//если четно, просто передае дальше
return pow_mod ( mod ( base*base, comp ), gauge/2, comp )
}
}
Проблемы с генерацией ключей RSA
Задача: реализовать алгоритм шифрования RSA. Шифрующая/дешифрующая функция была написана.
Когда для шифрования/дешифрования используются ключи, взятые из авторитетных источников (статей, методичек) все получается.
Но когда используется ключ, сгенерированный самостоятельно, при расшифровке исходное сообщение не получается. Очевидно, проблема в генерации ключей. Что я делаю не так?
Пример генерации ключей RSA
1) Пусть p = 57 q = 41
НОД ( 57, 41 ) = 1
2) m = p*q = 2337
3) fi(m) = (p-1)*(q-1) = 56*40 = 2240
4) Пусть e = 37
НОД (p-1, e) = НОД (q-1, e) = 1
5) Пусть d = 1453
e*d = 1 mod(fi(m)) т.к.
37 * 1453 = 1 + 2240*24
53761 = 53761
Итак, ключ сгенерирован!
Открытый ключ (m, e) = 2337, 37
Секретный ключ (m, d) = 2337, 1453
Пусть шифруеое сообщение x = 111
Зашифрованное сообщение y = pow_mod ( 111, 37, 2337 ) = 567
Расшифровывем сообщение x(новое) = pow_mod ( 567, 1453, 2337 ) = 480
480 != 111
Расшифровка не получилась. Почему?
На всякий случай приведу листинг pow_mod. Возможно, ошибка все-таки в ней.
Когда для шифрования/дешифрования используются ключи, взятые из авторитетных источников (статей, методичек) все получается.
Но когда используется ключ, сгенерированный самостоятельно, при расшифровке исходное сообщение не получается. Очевидно, проблема в генерации ключей. Что я делаю не так?
Пример генерации ключей RSA
1) Пусть p = 57 q = 41
НОД ( 57, 41 ) = 1
2) m = p*q = 2337
3) fi(m) = (p-1)*(q-1) = 56*40 = 2240
4) Пусть e = 37
НОД (p-1, e) = НОД (q-1, e) = 1
5) Пусть d = 1453
e*d = 1 mod(fi(m)) т.к.
37 * 1453 = 1 + 2240*24
53761 = 53761
Итак, ключ сгенерирован!
Открытый ключ (m, e) = 2337, 37
Секретный ключ (m, d) = 2337, 1453
Пусть шифруеое сообщение x = 111
Зашифрованное сообщение y = pow_mod ( 111, 37, 2337 ) = 567
Расшифровывем сообщение x(новое) = pow_mod ( 567, 1453, 2337 ) = 480
480 != 111
Расшифровка не получилась. Почему?
На всякий случай приведу листинг pow_mod. Возможно, ошибка все-таки в ней.
Код:
Знания не порождали бы страх, если нормально пользоваться поиском и медитировать на документации... ;)
здесь смотрел?
здесь смотрел?
А обязательно писать самому генератор ключей и нельзя восспользоваться уже существующими функциями генерации случайных простых больших значений? Из OpenSSL например.
Тут просто смутило, что операции идут с простыми типами как int, вместимости которого для RSA да и для любого несиметричного криптоалгоритма ужасно мало и непримелимо.
Тут просто смутило, что операции идут с простыми типами как int, вместимости которого для RSA да и для любого несиметричного криптоалгоритма ужасно мало и непримелимо.
Ошибка - в самом начале. Числа p и q должны быть не только взаимно простыми, они должны быть простыми.
Цитата:
А обязательно писать самому генератор ключей и нельзя восспользоваться уже существующими функциями генерации случайных простых больших значений?
Генерация ключей RSA, и генерация больших случайных значений - это разные вещи.
Цитата:
Тут просто смутило, что операции идут с простыми типами как int, вместимости которого для RSA да и для любого несиметричного криптоалгоритма ужасно мало и непримелимо.
Ты совершенно прав. Этот код носит демонстративный характер, и не может применяться для решения прикладных задач.
Спасибо всем, для меня тема закрыта.
Цитата: Overmind
Числа p и q должны быть не только взаимно простыми, они должны быть простыми.
Есстественно, в этом то и вся суть.
Цитата: Overmind
Генерация ключей RSA, и генерация больших случайных значений - это разные вещи.
Да я в курсе уж )) Но для генерации RSA ключей, сначало надо сгенерить парачку больших простых случайных чисел заданной разрядности. Для этого я и советовал обратиться к тому же OpenSSL и поглядеть там тип BIGNUM (Хотя довольно кривой на мой взгляд ))
Цитата:
Есстественно, в этом то и вся суть.
Сложно было сразу написать, что шифрование не получается из-за этого?