В моей криптосистеме RSA я пытаюсь выбрать ключ шифрования e, который относительно прост с phi(n).
phi(n) — это произведение двух чисел, p-1 и q-1, где p и q — простые числа. Эти простые числа генерируются с использованием наивного теста на простоту (да, я знаю, что это неэффективно).
Когда я запускаю свою программу, я получаю следующий вывод:
***** p *****
878222789
***** q *****
851559637
***** n = p x q *****
3523942633
***** phi(n) = (p-1)x(q-1) *****
1794160208
***** e *****
99
***** d *****
47835
Проблема в том, что каждый раз, когда я запускаю эту программу, e всегда оказывается равным 99 или 97. Это единственная константа в этом выводе. Я почти уверен, что мой алгоритм GCD верен. Но это единственная подпрограмма в select_e().
Соответствующие функции:
void select_e(uint &e, const uint phi_n)
{ // e = encryption key
for(int i=3;i<100;i++) {
if(gcd(phi_n,i) == 1) {
e = i;
break;
}
}
printf("\n***** e *****\n%u\n",e);
}
uint gcd(uint a, uint b) {
uint temp;
while (b!=0) {
temp = b;
b = a%b;
a = temp;
}
return a;
}
РЕДАКТИРОВАТЬ**************< /em>*********
Итак, я добавил оператор break в select_e(), из-за которого программа выводит обычно значение 3 или 5 для e. Теперь, насколько я понимаю, неудачное расшифрование является результатом целочисленного переполнения из-за умножения двух 32-битных целых чисел и сохранения значения в другом 32-битном целом числе. Поэтому я изменил свою программу, чтобы генерировать меньшие p и q по модулю. Вот эта функция:
void generate_pq(uint &p, uint &q)
{
srand(time(NULL));
bool repeat = false;
printf("\nGenerating keys...\n");
while(!repeat) {
p = rand()%100;
repeat = isPrime(p);
}
repeat = false;
while(!repeat) {
q = rand()%100;
repeat = isPrime(q);
}
printf("\n***** p *****\n%u\n\n***** q *****\n%u\n",p,q);
}
Теперь проблема в том, что иногда мне везет, и сообщение успешно расшифровывается. В другое время это не работает. Вот пример неудачной расшифровки:
Generating keys...
***** p *****
79
***** q *****
49
***** n = p x q *****
3871
***** phi(n) = (p-1)x(q-1) *****
3744
***** e *****
5
***** d *****
749
Message: fdsa
Cipher: �/�J
Decrypted Message: �a
Я знаю, что функции расшифровки и шифрования работают. Я протестировал их по отдельности и изучил алгоритмы. Они не являются источником проблемы. Я предоставлю их для потомков, если потребуется.
breakвнутриif (gcd...)- person erikkallen schedule 02.12.2013