Алгоритм RSA, должны ли простые p и q быть различными?

Да должны, закреплено в стандартах. При P=Q функция Эйлера считается по другой формуле, отсюда и неправильный результат

> причём смущает, что во втором источнике оговаривается, что выбранные простые числа должны быть нечётными

/me попытался представить четное простое число

конечно разными, иначе факторизация сводится к извлечению корня!

>/me попытался представить четное простое число

2

хорошо, нетривиальное четное простое число

это вопрос?

Если при выборе двух случайных!!! 1024-битных простых чисел они совпадут - юзер полный неудачник. Правда, на это все=же ставят проверки (а мало ли).

В случае P=Q задача факторизации сводится к взятию корня в целых числах, которое выполняется за считанные наносекунды. Так что... фэйл.

причём смущает, что во втором источнике оговаривается, что выбранные простые числа должны быть нечётными

You made my day!!! Интересно, сколько четных простых чисел кроме двойки вы сможете найти?

> You made my day!!! Интересно, сколько четных простых чисел кроме двойки вы сможете найти?

Хм, неужели не очевидно, что я именно это и имел в виду? А то, что в том источнике специально оговаривается, что простые должны быть нечётными, заставило сомневаться в том, что алгоритм там изложен без ошибок.

> Хм, неужели не очевидно, что я именно это и имел в виду?

Нет, не очевидно. Ибо очевидно другое утверждение - произведение двух простых чисел четно тогда и только тогда, когда хотя бы одно из них - 2. При этом факторизация сводится к еще более тривиальному действию на 200 тактов процессора.

//Т.е. то, что P и Q - нечетные есть пометка капитана очевидность.

> > Хм, неужели не очевидно, что я именно это и имел в виду?

Нет, не очевидно.

Да я уже давно заметил, что на LOR лучше не использовать выражений, которые при желании можно понять неверно. Часто находится человек, который именно это и сделает.

Большое простое число очевидно больше 2, а значит заведомо нечётное. Найди во фразе «два различных больших нечетных простых числа» лишнее слово. Это «нечётных», правильно? Теперь подумай, какой вариант более вероятен:

а). что и автор статьи не заметил, что «нечётные» можно не писать, и что я не знаю об этом;

б). что автор статьи не заметил, что «нечётные» можно не писать, я обратил на это внимание, а ты не понял, что означает моя фраза об этом («причём смущает, что во втором источнике оговаривается, что выбранные простые числа должны быть нечётными»);

;-)

Вообще-то, по второй ссылке много чего забавного... например, «64 это '='» в описании системы исчисления base64. Пункт 4 генерации ключа также забавен - используют некую пляску с бубном вместо простого взятия обратного по модулю (P-1)(Q-1) расширенным Евклидом.

Если p и q - специальные простые (т.е. (p-1)/2 - тоже простое), то можно обойтись без евклида.

> Если p и q - специальные простые (т.е. (p-1)/2 - тоже простое)

Неоправданное уменьшение пространства ключей.

то можно обойтись без евклида

Во-первых, в дань уважения к великому человеку можно было бы разок «шифт» придавить. Во-вторых, избежать использования алгоритма Евклида можно только путем замены на возведение в степень (p-2) в поле вычетов по простому P, а эта операция в разы тяжелее.

> Неоправданное уменьшение пространства ключей.

а Шнайер считает, что это усиление стойкости ключа

дань уважения к великому человеку можно было бы разок «шифт» придавить

«евклид» - это не «Евклид - учёный, без которого можно обойтись», а жаргонизм для «алгоритма Евклида»

эта операция в разы тяжелее

всяко не тяжелее, чем использование готового ключа

> а Шнайер считает, что это усиление стойкости ключа

Устаревшая инфа. Раньше так считали из-за неприменимости какой-то атаки к ключам такого вида. Но недавно нашли способ распространить ее и на них.

а жаргонизм для «алгоритма Евклида»

В следующий раз приводите список используемых жаргонизмов перед их употреблением.

всяко не тяжелее, чем использование готового ключа

Ага, а по сравнению с поиском больших простых - так вообще понты. Я спрашивал, зачем заморачиваться с поиском обратного по частям, если можно сделать это сразу? К тому же, не совсем понятно, каким образом автор статьи предлагает искать обратное по модулям (P-1) и (Q-1)?

> Я спрашивал, зачем заморачиваться с поиском обратного по частям, если можно сделать это сразу?

э не, зачем же по частям. Дело в том, что в этом случае мы знаем значение функции Эйлера для произведения p * q, таким образом легко можем найти обратное к e.

вру, в таком случае мы знаем φ(φ(n)), чтобы найти обратное к e путём простого возведения в степень по модулю

> Часто находится человек, который именно это и сделает.
Вы недавно на ЛОРе?? Всегда находится человек.

А, при условии, что (P-1) и (Q-1) - произведения двух простых? Да. Итого получаем: ограничение пространства ключей и замену расширенного алгоритма Евклида на более тяжелую операцию - возведение в степень по модулю. Так все же, в чем профит?