Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 71
Ничего не выйдет, если доказательство будет неконструктивным. Представьте, что вы найдёте какое-нибудь отражение алгоритмов на топологию, а потом используя неразрывные потоки на многомерных сферах докажете эквивалентность P и NP.
Это никак не поможет строить P алгоритмы для NP задач.
Это никак не поможет строить P алгоритмы для NP задач.
В тексте насчет этого и сказано:
К сожалению, обладая одним лишь доказательством без соображений о том, как преобразовать его в рабочий алгоритм, захватить мир будет весьма проблематично.. Т.е. алгоритм преобразования должен быть, без него лишь за премией на миллион долларов, но тоже неплохо, на мой взгляд.
Полиномиально — не всегда быстро. Полином сотой, тысячной степени — уже сравнимо с экспонентой.
Какой милый и добрый захватчик мира! Взял денег и всех вылечил. А потом еще и секретом поделился! Хочу жить в мире, где такие злодеи…
А если серьезно — интереснее, что делать с криптографией после того, как такой гений обнаружится? Ведь, как я понимаю, большая часть шифровальных алгоритмов построена именно на вере в неупрощаемость вычислений, так? Не будет больше математической криптографии? Снова будем ценности и тайны в землю закапывать?
квантовая криптография; а пока строим квантовый компьютер — блокнотики, блокнотики…
Возможность слома квантовой криптографии уже обсуждают, причем отступать некуда.
шифроблокноты. Готовить сани летом, то есть запасаться гигабайтами случайных данных, обмениваться ими с другими важными вам людьми чтобы потом можно было на их основе шифровать реальные сообщения.
так вот для чего пригодится биткоин!
Появилась идея об организации devurandom-as-a-service.com.
Есть криптоалгоритмы, для которых пока что не придуманы соответствующие квантовые алгоритмы взлома, например NTRUEncrypt
logic.pdmi.ras.ru/~sergey/teaching/crypto10/12-quantum.pdf
Краткое введение в квантовую криптографию — tcode.tinro.ru/cryptography/src/38.pdf
logic.pdmi.ras.ru/~sergey/teaching/crypto10/12-quantum.pdf
В результате получается квантовое решение задачи дискретного логарифма. Эллиптические кривые не спасают — для любой коммутативной группы работает, нужно только умножать уметь.
Мы взломали всю коммутативную криптографию. Что делать?
* Один ответ — строить квантовую криптографию.
* Другой ответ — строить некоммутативную криптографию.
Краткое введение в квантовую криптографию — tcode.tinro.ru/cryptography/src/38.pdf
Зависит от того, в какой же мы реальности всё-таки живём.
Вполне может так оказаться, что NP=P, но есть вполне годные функции, такие что F(X) — квадратична по сложности, а F^{-1}(F(X)) — сотой степени.
Формально — бери, проверяй. Но сотая степень — это слишком много. Для любой практики этого нормально.
Но даже если =всё пропало=, и P=NP, то всё равно есть криптосистемы с одноразовым блокнотом. Ну, то есть, при походе в банк вам будут выдавать винчестер с «гарантированно случайными битами», и вы будете ими всё шифровать XORом, пока винт не закончится.
Но при этом, конечно, станет намного больше проблем с «физическим» доступом к машине.
Но умереть криптография не умрёт, конечно.
Вполне может так оказаться, что NP=P, но есть вполне годные функции, такие что F(X) — квадратична по сложности, а F^{-1}(F(X)) — сотой степени.
Формально — бери, проверяй. Но сотая степень — это слишком много. Для любой практики этого нормально.
Но даже если =всё пропало=, и P=NP, то всё равно есть криптосистемы с одноразовым блокнотом. Ну, то есть, при походе в банк вам будут выдавать винчестер с «гарантированно случайными битами», и вы будете ими всё шифровать XORом, пока винт не закончится.
Но при этом, конечно, станет намного больше проблем с «физическим» доступом к машине.
Но умереть криптография не умрёт, конечно.
Вот по этой ссылке перечислены некоторые криптографические примитивы, которые существуют без каких-либо предположений (существование односторонней ф-ции, P!=NP и.т.д.)
cstheory.stackexchange.com/a/20085
cstheory.stackexchange.com/a/20085
Доказательство равенства это далеко ещё не сам алгоритм решения NP задачи. Тогда о каком захвате мира может идти речь? В этом свете разумнее действительно просто взять миллион, а потом строить планы что с ним, собственно, делать.
Эммм… а что это делает на Хабре?
Я про Ваш комментарий то же самое могу спросить.
Мой комментарий тут справедливо негодует по поводу того что хабр превращается в мурзилку, где на одну техническую статью приходится пять статей в которых берут интервью с Вассерманом, обзирают очередной безликий смартфон, ну или фантазии чьи-то публикуют — типа этой. К чему это все на хабре? Больше не о чем написать? Ну давайте тогда я опубликую статью «Как бы изменился рынок железа если бы микросхемы можно было делать из говна попугайчиков?» — с экономическим анализом, техническими деталями, все как положено. Очень подходит для нынешнего хабра, нет?
Я бы почитал кстати про микросхемы из говна попугайчиков.
А по сути сказанного Вами, могу лишь заметить только то, что на Хабре предусмотрен механизм саморегуляции и именно он, а точнее результаты его работы могут привести Хабр к мурзилке. А могут и не привести.
Просто комментарий подобный вашему я, последнее время, замечаю в каждом третьем посте с положительной оценкой.
А по сути сказанного Вами, могу лишь заметить только то, что на Хабре предусмотрен механизм саморегуляции и именно он, а точнее результаты его работы могут привести Хабр к мурзилке. А могут и не привести.
Просто комментарий подобный вашему я, последнее время, замечаю в каждом третьем посте с положительной оценкой.
Я бы почитал кстати про микросхемы из говна попугайчиков.
Нет уж, увольте. Про говно попугайчиков — это я просто написал первый пришедший в голову бред. Писать статью я на эту тему точно не буду, и надеюсь никто не будет :)
А по сути сказанного Вами, могу лишь заметить только то, что на Хабре предусмотрен механизм саморегуляции и именно он, а точнее результаты его работы могут привести Хабр к мурзилке. А могут и не привести.
Отношение к статьям можно высказывать не только оценками, но и комментариями — они, кроме всего прочего, для этого тоже могут использоваться. И я пользуюсь этой замечательной возможностью, и плевать на минусы и карму. Если хваленая саморегуляция (не)сработает и Хабр таки превратится в мурзилку — зачем мне плюсы и карма на таком сайте?
Просто комментарий подобный вашему я, последнее время, замечаю в каждом третьем посте с положительной оценкой.
А вам не кажется что это не просто так? Комментарии «подобные моему» — это ведь тоже мнение людей, как и плюсы с минусами.
Отношение к статьям можно высказывать не только оценками, но и комментариями
Вот это ключевая фраза. Более развернутое мнение в первом комментарии возможно имело бы совсем другую оценку.
Так а что развертывать-то? Какой-то человек фантазирует на тему «А что если бы?..» Технической ценности в его фантазии ноль. Тогда что? Художественная ценность… не смешите, слог никакой (что в оригинале, что в переводе), сюжет как будто восьмиклассник придумывал :) Может какой-то социальный подтекст, проблема, анализ интересный? Тогда можно было бы считать этот текст например эссе. Но и тут зеро полное. Текст — пустышка. В нем нет ничего ни для ума, ни для сердца, ни для чего вообще. Но все-таки один человек эту пустышку сочинил, а другой не поленился перевести и запостить на хабр (якобы технический сайт, ага). Я не знаю, может это надо кому-то объяснять, но мне кажется что читателю (по идее технарю, хотя бы в какой-то степени… да просто взрослому человеку) пришедшему на (якобы технический, ага) хабр это очевидно.
Я понял Вас. Предлагаю в будущем писать «кг/ам» если статья плохая и «аффтар жжот пешы иcчо» если хорошая.
Поскольку не все знакомы с субкультурой падонкофф, предлагаю использовать более нейтральные варианты :) И если это очередной опус из серии «Как постоить гиперболоид и завоевать мир. Допустим гиперболодид построен. Теперь о завоевании мира. Нужно взять гиперболоид и каааак захерачить по гадам!..» — то предлагаю не распинаться (ибо опус этого не заслуживает), а писать кратко «Статья бессодержательна!», «Статья не для Хабра», «Прошу автора пояснить ценность этой статьи хоть с какой-нибудь точки зрения» и т.д. Может если такие комментарии будут чаще появляться под всяким бредом, люди задумаются о том что Хабр — это не их личный уютненький, а в первую очередь технический сайт где преобладать должны технические статьи. Хотя у меня как-то надежда на это все слабее и слабее если честно.
Слушайте, ну у вас фигня какая-то получается, а не презумпция невиновности — автор должен найти время, постараться, написать статью, выложить её, а потом ещё оправдываться что он не верблюд.
А ещё, судьи кто? Кто определяет какая статья для Хабра, а какая нет? По каким критериям?
А ещё, судьи кто? Кто определяет какая статья для Хабра, а какая нет? По каким критериям?
Слушайте, ну у вас фигня какая-то получается, а не презумпция невиновности — автор должен найти время, постараться, написать статью, выложить её, а потом ещё оправдываться что он не верблюд.
Презумпция невиновности есть только в уголовном праве, да и то не во всякой стране, хе-хе :) А в авторском ремесле ее нету и быть не может. Если вы думаете что любой авторский текст по умолчанию — это бесценный брЫльянт, то я вас огорчу. Что бы в этом убедится, достаточно посмотреть на тонны текстовых говен, ежедневно появляющихся в интернетах. А ведь кто-то же нашел время и все это написал, верно? :)
А ещё, судьи кто? Кто определяет какая статья для Хабра, а какая нет? По каким критериям?
Определяет сообщество, частью которого я являюсь. Свой вклад в Хабр я вношу написанием технических статей на относительно редкую техническую тематику. И не считаю их кстати каким-то бесценным материалом, не подверженным критике. Также, как один из тех людей которые все еще надеются сохранить Хабр как сайт технарей, считаю что таким статьям как эта тут не место. Кто судья спрашиваете? Я сужу статьи — вместе с вами, и со всеми комментирующими и голосующими конечно. И если я хочу высказаться кратко — я так и делаю. В этом есть что-то неправильное по-вашему?
Вы не нашли в статье для себя ничего нового и интересного? Не стоит делать из этого проблему.
Мне статья понравилась. Да, я «технарь хотя бы в какой-то степени», но с криптографией у меня мало общего. Было интересно почитать в такой форме. В другой вряд ли стал бы читать. Узнал много нового, особенно из комментариев.
Мне статья понравилась. Да, я «технарь хотя бы в какой-то степени», но с криптографией у меня мало общего. Было интересно почитать в такой форме. В другой вряд ли стал бы читать. Узнал много нового, особенно из комментариев.
Вы не нашли в статье для себя ничего нового и интересного? Не стоит делать из этого проблему.
Я и не делаю. Я просто написал что статья не для Хабра. Какая в этом проблема? Это уже потом развернулась бурная дискуссия, да, но инициатором ее был не я (посмотрите комментарии выше).
Мне статья понравилась. Да, я «технарь хотя бы в какой-то степени», но с криптографией у меня мало общего. Было интересно почитать в такой форме. В другой вряд ли стал бы читать. Узнал много нового, особенно из комментариев.
Рад за вас. Уверен что в таком случае вам еще больше понравятся соответствующие статьи из Википедии — информации по теме в них на порядок (т.е. в 10 раз) больше, а изложение хоть и не разбавлено неуклюжей сказкой про математика-хакера-миллионера, зато несложное и в общем более точное чем в этой статье. Да и ссылки в конце статей годные (даже в русской вики, что для статьи по математике — очень хорошо).
>Про говно попугайчиков — это я просто написал первый пришедший в голову бред. Писать статью я на эту тему точно не буду, и надеюсь никто не будет :)
Электричество из мочи уже было ;)
Электричество из мочи уже было ;)
Если бы микросхемы делали из говна попугайчиков в микроэлектронике быстро наступил бы кризис нехватки материалов
О чем речь? Пишите то, что вы хотите тут видеть! Хабр — не газета. Он формируется всеми нами и Вами лично, в том числе. Он, так сказать, зеркало интереса читателей и их устремлений. А любая статья, даже самая пустяковая, но способная развлечь аудиторию интересным и вполне наукоёмким образом, здесь приветствуется… Не нравится — смело ставьте минус, это ваше право.
А то получается: «что это за дрянь на моём Хабре?»
Но он — не ваш. Он — «государственный». Вы его только напрокат взяли. ;)
А то получается: «что это за дрянь на моём Хабре?»
Но он — не ваш. Он — «государственный». Вы его только напрокат взяли. ;)
Как захватить мир, найдя философский камень?
P = NP = крах современного мира. Но они не равны. Можно бесконечно приблизиться к P, построив автоматическую машину для печати ASICов. NP задачи великолепно параллелятся. Если напечатать 1024 устройства, то они ускорят перебор в 10 (двоичных) раз, но этого мало, нужно что бы машина печатала машину для печати. Тогда бутылочным горлом станет поставка ресурсов для печати (энергия, кремний, металлы. На пути к сингулярности.
Но они не равны.Пруф или равны.
P = NP = крах современного мира
из транзитивности получаем
P = крах современного мира
из транзитивности получаем
P = крах современного мира
NP задачи бесполезно параллелить. Количество исполнительных устройств растет так же экспоненциально, как и время.
Зачем деньги воровать то?
Вроде бы подобрать заголовок биткоин блока вполне себе NP задача, которую мы и умеем решать.
Сейчас за блок дают 25 биткоинов по 570 долларов. 14 тысяч долларов, неплохо и легально. Ну и другие монетки.
Кстати, миллион долларов можно собрать быстрее чем институт Клея признает доказательство.
Вроде бы подобрать заголовок биткоин блока вполне себе NP задача, которую мы и умеем решать.
Сейчас за блок дают 25 биткоинов по 570 долларов. 14 тысяч долларов, неплохо и легально. Ну и другие монетки.
Кстати, миллион долларов можно собрать быстрее чем институт Клея признает доказательство.
Если вы быстро нафармите себе кучу биткоинов и попробуете продать, то их курс тут же рухнет. А $14 тыс. на основание биоинженерной корпорации явно не хватает :)
Допустим, не 14 тысяч, а 6 миллионов, судя по графику глубины рынка… но да, и правда не хватит.
Вы неправильно понимаете «нафармить». Один блок должен появляться раз в 10 минут. Сейчас за него дают 25 монет, через 2 года будет 12,5 монет за блок (убавляется в 2 раза примерно раз в 4 года).
Этот процесс идёт и сейчас, каждые 10 минут появляются 25 монет. Чего вы думаете все посходили с ума с фармингом?
Эта инфляция биткоина плата за вычисление блоков, за средство проведения транзакций. Нет блоков — нет транзакций, деньги мертвы.
14 тысяч в 10 минут это 2 миллиона в сутки. На биоинженерную корпорацию не хватит, но за год можно на лабораторию заработать.
Этот процесс идёт и сейчас, каждые 10 минут появляются 25 монет. Чего вы думаете все посходили с ума с фармингом?
Эта инфляция биткоина плата за вычисление блоков, за средство проведения транзакций. Нет блоков — нет транзакций, деньги мертвы.
14 тысяч в 10 минут это 2 миллиона в сутки. На биоинженерную корпорацию не хватит, но за год можно на лабораторию заработать.
В плане P? NP можно вспомнить тест AKS (Агравала — Каяла — Саксены). Он был предложен в 2002 году, и позволил отнести проблему определения простоты числа к классу P. Однако, несмотря на полиномиальность, этот тест работает слишком медленно, за O(log^6 n) и на практике проблему продолжают успешно решать с помощью вероятностных алгоритмов.
teal.gmu.edu/courses/ECE746/project/F06_Project_resources/Salembier_Southerington_AKS.pdf
Так что говоря "Равенство P=NP может означать, что задачи, решение которых раньше считалось очень сложным, теперь решаются за полиномиальное время." важно понимать, что это полиномиальное время может оказаться невероятно большим. Например, сравнимым с временем активного существования звезд.
«AES… Он считается «золотым стандартом» шифрования. И вы доказали, что он бесполезен.» — здесь тоже есть проблема. Вне зависимости от равенства или неравенства классов P и NP, могут существовать или не существовать алгоритмы взлома AES более эффективные алгоритмы, чем полный перебор. Полиномиальные алгоритмы (если они есть) могут быть применимы для какого-либо AES-N, с огромной длиной ключа N (например, для ключей размером более 1 млрд бит). Такие алгоритмы будут совершенно неприменимы к AES-256.
www.schneier.com/blog/archives/2010/08/p_np_1.html
Также сам по себе алгоритм AES (и алгоритмы его взлома) не имеет смысла относить к NP либо к P, так как классы сложности традиционно определяют по асимптотике функции при росте размера входных данных. Стандарт AES фиксирует основные размеры (ключа, блока) и не определен для ключей и блоков произвольного размера.
crypto.stackexchange.com/questions/6313/is-aes-reducible-to-an-np-complete-problem
Как отмечено в wiki (P_versus_NP_problem) для слома криптографии требуется не произвольное полиномиальное, а эффективное решение для NP-полных задач.
teal.gmu.edu/courses/ECE746/project/F06_Project_resources/Salembier_Southerington_AKS.pdf
VIII.CONCLUSION The AKS algorithm in its current form is not suitable for general use due to the length of time required to verify primality.… Currently available probabilistic algorithms provide much faster response times within margins of error that are generally acceptable. Primality tests for numbers that might take hours or days using AKS could be performed in seconds or even less using probabilistic methods such as Miller-Rabin.
Так что говоря "Равенство P=NP может означать, что задачи, решение которых раньше считалось очень сложным, теперь решаются за полиномиальное время." важно понимать, что это полиномиальное время может оказаться невероятно большим. Например, сравнимым с временем активного существования звезд.
«AES… Он считается «золотым стандартом» шифрования. И вы доказали, что он бесполезен.» — здесь тоже есть проблема. Вне зависимости от равенства или неравенства классов P и NP, могут существовать или не существовать алгоритмы взлома AES более эффективные алгоритмы, чем полный перебор. Полиномиальные алгоритмы (если они есть) могут быть применимы для какого-либо AES-N, с огромной длиной ключа N (например, для ключей размером более 1 млрд бит). Такие алгоритмы будут совершенно неприменимы к AES-256.
www.schneier.com/blog/archives/2010/08/p_np_1.html
If P=NP, then there's a polytime algorithm for breaking AES-K, for keys of size K, that's polynomial in the limit as K goes to infinity.… So even if P=NP, it's still possible that AES-256 has no breaks other than brute force. It's even possible that AES-trillion has no breaks other than brute force. All P=NP would tell us is that we'll have something other than brute force for key lengths above SOME unknown threshold.
Также сам по себе алгоритм AES (и алгоритмы его взлома) не имеет смысла относить к NP либо к P, так как классы сложности традиционно определяют по асимптотике функции при росте размера входных данных. Стандарт AES фиксирует основные размеры (ключа, блока) и не определен для ключей и блоков произвольного размера.
crypto.stackexchange.com/questions/6313/is-aes-reducible-to-an-np-complete-problem
AES is a finite-domain function. It is invertible / distinguishable from a random permutation in (large but) constant time. The definitions of P, NP, etc., refer to asymptotic behavior — that is, as the input size grows to infinity. Because of the algebraic structure of AES, it is probably possible to define a «generalized AES» for infinitely many key lengths....
Как отмечено в wiki (P_versus_NP_problem) для слома криптографии требуется не произвольное полиномиальное, а эффективное решение для NP-полных задач.
Cryptography, for example, relies on certain problems being difficult. A constructive and efficient solution[Note: Exactly how efficient a solution must be to pose a threat to cryptography depends on the details. A solution of O(N^2) or better and a reasonable constant term would be catastrophic. On the other hand, a solution that is \Omega(N^4) or worse in almost all cases would not pose an immediate practical danger.] to an NP-complete problem such as 3-SAT would break most existing cryptosystems including:
Тест простоты (не путать с разложением на простые множители) — не NP-полная задача, это давно известно.
По поводу эффективного взлома — проблема в том, что то, что вчера было не по зубам суперкомпьютерам, завтра можно сделать на любом смартфоне. Поэтому так важна экспоненциальность: достаточно добавить один бит и время взлома увеличивается в два раза (условно говоря). А любой полином рано или поздно возьмут брутфорсом.
По поводу эффективного взлома — проблема в том, что то, что вчера было не по зубам суперкомпьютерам, завтра можно сделать на любом смартфоне. Поэтому так важна экспоненциальность: достаточно добавить один бит и время взлома увеличивается в два раза (условно говоря). А любой полином рано или поздно возьмут брутфорсом.
> вчера было не по зубам суперкомпьютерам, завтра можно сделать на любом смартфоне.
Оптимистичное «завтра»… По данным с графика s.top500.org/static/lists/2014/06/TOP500_201406_Poster.png можно увидеть, что примерно за десять лет первый суперкомпьютер списка становиться 500-ым. Еще через десять лет такой уровень производительности становится достижим для декстопов. Смартфоны отстают от десктопов еще условно на 5 лет.
> А любой полином рано или поздно возьмут брутфорсом.
С оценками в квадрилионы лет ( crypto.stackexchange.com/a/753 ) даже aes-128 скорее возьмут слишком поздно. Опять же, наличие полиномиального алгоритма — это еще не наличие более быстрого полиномиального алгоритма (для фиксированного размера ключа в 128 или 256 бит), чем полный перебор.
Оптимистичное «завтра»… По данным с графика s.top500.org/static/lists/2014/06/TOP500_201406_Poster.png можно увидеть, что примерно за десять лет первый суперкомпьютер списка становиться 500-ым. Еще через десять лет такой уровень производительности становится достижим для декстопов. Смартфоны отстают от десктопов еще условно на 5 лет.
> А любой полином рано или поздно возьмут брутфорсом.
С оценками в квадрилионы лет ( crypto.stackexchange.com/a/753 ) даже aes-128 скорее возьмут слишком поздно. Опять же, наличие полиномиального алгоритма — это еще не наличие более быстрого полиномиального алгоритма (для фиксированного размера ключа в 128 или 256 бит), чем полный перебор.
Статья предлагает совершать вещи, которые требуют много разных квалификаций и которые одному человеку не под силу. Начиная от безнаказанного воровства денег. Вас быстро вычислят спецслужбы. Чтобы от них скрыться, нужно обладать квалификацией и изобретательностью, сравнимой с целым коллективом сотрудников спецслужб. Даже знаменитых хакеров ловят. А ведь они жизнь посвятили информационной безопасности, как в плане нападения, так и в плане защиты.
Как водится, любой миллиардер может рассказать историю любого своего миллиона… кроме первого.
Как было отмечено выше, во-первых, доказательство P=NP должно быть конструктивным, во-вторых, полученные алгоритмы должны быть практически эффективными, вряд ли кого-то устроит полиноминальное время работы при степени полинома равной гуголу.
Тем не менее, имея лишь неэффективные полиноминальные алгоритмы, можно извлечь какой-то профит. Для этого можно сыграть на бирже на понижение отраслей, завязанных на криптографии, грубо говоря, попытаться создать панику. Разумеется, для этого нужно иметь значительный стартовый капитал и сделать много технической и социальной работы, так что придется привлекать много людей в команду и посвящать их в тайну доказательства. Ну и профит будет сильно ограниченным по сравнению с возможностью безнаказанно воровать деньги.
Тем не менее, имея лишь неэффективные полиноминальные алгоритмы, можно извлечь какой-то профит. Для этого можно сыграть на бирже на понижение отраслей, завязанных на криптографии, грубо говоря, попытаться создать панику. Разумеется, для этого нужно иметь значительный стартовый капитал и сделать много технической и социальной работы, так что придется привлекать много людей в команду и посвящать их в тайну доказательства. Ну и профит будет сильно ограниченным по сравнению с возможностью безнаказанно воровать деньги.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как захватить мир, доказав, что P=NP