Почему RSA нельзя взломать подсчётом phi(n)? Я понимаю, что факторизация N это NP проблема, но ведь если я подсчитаю phi(n), проблема которая является P, я смогу получить ключ для шифрования.
Пацаны, объясните, пожалуйста, я тупой.

Бамп.
Ну помогите, пожалуйста(((

>>219752164 (OP)
Каво

>>219752396
Почему RSA является безопасным, когда я могу получить ебучий клюш для дешифровки за полиномиальное время, блять?

Тебя ебет?
Ну шифруют и шифруют, че бухтеть то?

Бамп

>>219752539
Спасибо, у меня уже глаз дёргается, блять.

>>219752164 (OP)
Окей, как ты будешь получать ключ, найдя phi(n) за полиномиальное время?

Ну пожалуйста, я знаю, что хоть кто-то из вас знает, да блять.

>>219752749
Ща распишу, дай время!

>>219752749
У меня есть n, он всегда публичный:
phi(n) = X. Икс я считаю за полиномиальное время.
e - публичный ключ для шифрования.
gcd(e, phi(n)) = 1, здесь у меня ебаное фи уже подсчитано.
de = 1 (mod phi(n)), вот здесь я знаю "фи" плюс я знаю "е", который публичный, так что тут я могу легко вычислить "d"
n, e - публичные
зашифрованное сообщение c это m^e (mod n)
расшифрованное сообщение этоc^d (mod n), "d" я уже подсчитал.

>>219752164 (OP)
Можно, просто долго. Если тебе каким-то раком приснится конкретное разложение конкретного числа, юзаемого в банках, ты сможешь эти банки ломануть без проблем и спиздить все деньги оттуда.

>>219753173
Тогда какого хуя все твердят, что RSA это NP? Это P проблема, который просто долгая?
Тогда почему все говорят, что RSA это NP и приводят в пример факторизацию, когда нахождение фи является полиномиальным?

Р-р-ребята?

Хорошо, я понял.
>>219752749
>>219753173
Мне кажется, что нахождение фи займёт "псевдополиномиальное" время, что само по себе нихуя полиномиальным не является. Мне просто казалось, что обычный перебор займёт не так много времени :D :D :D

Thanks for writing to Dr Math. The answer to your question is no,
there is no known way to get phi(n) in polynomial time for general
(large) n. In fact, if n is a product of two primes,

n = pq

then finding phi(n) is equivalent to factoring n, because if you can
find phi(n), then

p + q = n + 1 - phi(n)
p q = n,

so p and q are, respectively,

n + 1 - phi(n) + sqrt((n + 1 - phi(n))^2 - 4n)
----------------------------------------------
2

and

n + 1 - phi(n) - sqrt((n + 1 - phi(n))^2 - 4n)
----------------------------------------------.
2

And those two expressions are very easy to calculate. So if you could
compute phi(n) in polynomial time, then you could factor n in
polynomial time, and it is conjectured (but not yet proven) that it is
impossible to factor n in polynomial time.

>>219753085
>de = 1 (mod phi(n)), вот здесь я знаю "фи" плюс я знаю "е", который публичный, так что тут я могу легко вычислить "d"
По-моему, здесь-то и собака зарыта.

Ты можешь, но за то время, которое на это уйдет, информация будет неактуальной

/тхреад

Почему матматики такие душные лузеры?

>>219753274
Нет, это NP, потому и долго. То, что ты написал это ты ошибся где-то, мне лень разбираться.

>>219753724
Не-а, нахождение d или e, когда у тебя есть что-либо из первого и есть фи -- это относительно лёгкая проблема.

https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

In big O notation, this algorithm runs in time O(log(m)2), assuming |a| < m, and is considered to be very fast and generally more efficient than its alternative, exponentiation.

>>219753867
Дядя, я понимаю, что я где-то ОШИБСЯ, скорее всего, я не могу быть умнее величайших умов двадцатого века, лол. Я просто думал, что я могу подсчитать фи перебором, и это правда, и время это займёт полиномиальное, но так как нахождение фи это нумерическая проблема, то время у меня здесь не полиномиальное, а псевдополиномиальное.

https://en.wikipedia.org/wiki/Pseudo-polynomial_time

>In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the numeric value of the input (the largest integer present in the input) — but not necessarily in the length of the input (the number of bits required to represent it), which is the case for polynomial time algorithms.

>>219752164 (OP)
Чел как ты найдешь фи от n за полиномиальное время? Оно у тебя растет экспоненциально от количества цифр.

>>219754917
Спасибо, броу, я уже понял, что затупил.
Я забыл про псевдополиномиальность.
https://en.wikipedia.org/wiki/Pseudo-polynomial_time