Бамп.
Ну помогите, пожалуйста(((
Ну помогите, пожалуйста(((
Каво
Почему RSA является безопасным, когда я могу получить ебучий клюш для дешифровки за полиномиальное время, блять?
Тебя ебет?
Ну шифруют и шифруют, че бухтеть то?
Ну шифруют и шифруют, че бухтеть то?
Бамп
Спасибо, у меня уже глаз дёргается, блять.
Окей, как ты будешь получать ключ, найдя phi(n) за полиномиальное время?
Ну пожалуйста, я знаю, что хоть кто-то из вас знает, да блять.
Ща распишу, дай время!
У меня есть 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" я уже подсчитал.
Можно, просто долго. Если тебе каким-то раком приснится конкретное разложение конкретного числа, юзаемого в банках, ты сможешь эти банки ломануть без проблем и спиздить все деньги оттуда.
Тогда какого хуя все твердят, что RSA это NP? Это P проблема, который просто долгая?
Тогда почему все говорят, что RSA это NP и приводят в пример факторизацию, когда нахождение фи является полиномиальным?
Р-р-ребята?
Хорошо, я понял.
Мне кажется, что нахождение фи займёт "псевдополиномиальное" время, что само по себе нихуя полиномиальным не является. Мне просто казалось, что обычный перебор займёт не так много времени :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.
Мне кажется, что нахождение фи займёт "псевдополиномиальное" время, что само по себе нихуя полиномиальным не является. Мне просто казалось, что обычный перебор займёт не так много времени :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.
>de = 1 (mod phi(n)), вот здесь я знаю "фи" плюс я знаю "е", который публичный, так что тут я могу легко вычислить "d"
По-моему, здесь-то и собака зарыта.
Ты можешь, но за то время, которое на это уйдет, информация будет неактуальной
/тхреад
/тхреад
Почему матматики такие душные лузеры?
Нет, это NP, потому и долго. То, что ты написал это ты ошибся где-то, мне лень разбираться.
Не-а, нахождение 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.
Дядя, я понимаю, что я где-то ОШИБСЯ, скорее всего, я не могу быть умнее величайших умов двадцатого века, лол. Я просто думал, что я могу подсчитать фи перебором, и это правда, и время это займёт полиномиальное, но так как нахождение фи это нумерическая проблема, то время у меня здесь не полиномиальное, а псевдополиномиальное.
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.
Чел как ты найдешь фи от n за полиномиальное время? Оно у тебя растет экспоненциально от количества цифр.
Спасибо, броу, я уже понял, что затупил.
Я забыл про псевдополиномиальность.
https://en.wikipedia.org/wiki/Pseudo-polynomial_time
Пацаны, объясните, пожалуйста, я тупой.