Уязвимость RSA, когда зашифрованное M не взаимно просто с N

Когда $(N,e)$ является действительным открытым ключом RSA, где $N$ является произведением двух различных секретных простых чисел $p$ и $q$, существует вероятность $1/p+1/q$, что случайное сообщение $M $ таков, что $M^e$ не взаимно прост с $N$. Поскольку и $p$, и $q$ должны быть большими (сотни десятичных цифр) для обеспечения безопасности RSA, при фактическом использовании RSA этой вероятностью можно пренебречь. Вопрос заключается в рассмотрении того, что в реальном использовании не произойдет для случайного или псевдослучайного $M$ или для $M\in[1,N)$, выбранного тем, кто не знает (и не может найти) факторизацию $N$. .

RSA - это перестановка с лазейкой. Вам это о чем-нибудь говорит?

Хорошо, я не подумал об этом.В этом случае это серьезная уязвимость в системе безопасности, поскольку, взяв НОД зашифрованного текста (C) и N, можно получить p или q?

Решит ли проблему использование OAEP на C, не взаимно простом с N?

@Chen: я не понимаю, что вы имеете в виду под «использованием OAEP на C»; но использование OAEP для создания входных данных $M$ для необработанного шифрования RSA $M\mapsto C=M^e\bmod N$ для безопасного в остальном $N$ практически наверняка «решит проблему», если она была. Теперь мы можем безопасно шифровать числа, кратные $p$ или $q$. Опять же, даже если не использовать OAEP, нет никакой практической проблемы, потому что выбор $M$ или $C$ в $[1,n)$ с $\gcd(C,N)\ne1$ невозможен для человека, не знающего ( ни в состоянии найти) факторизацию $N$.

Извините, я хотел использовать OAEP на M. Вы имеете в виду, что выбрать M, который дает $ gcd (C, N) - 1 $, невозможно, не зная p и q?

а почему это невозможно? Будет ли это по-прежнему возможно с вероятностью успеха 1/p + 1/q?

@Chen, это ничем не отличается от злоумышленника, который просто угадывает случайные множители $N$ :)

@Chen: для практических размеров $p, q$, то есть $2^{-1024}$ или меньше, $1/p + 1/q$ фактически «невозможно»

Этот вопрос на других языках: