Так. Стоять. Я не хочу: чтобы мы путались в терминах.
Пусть у вас есть функция F( X ) = Y
Обратной ей называется функция G(Y), такая что F(G(Y)) = Y
Обратная функция не обязана находить X. Обратная функция обязана находить значение из класса эквивалентности относительно исходной функции. (любое значение, которое даёт Y)
Именно это я называл поиском коллизий, и оно почти так используется в литературе. (С поправкой на рандомизируемость)
Теперь второе ваше утверждение:
>>Необратимость по определению хэш функции должна присутствовать.
Ни для одной хеш-функции не доказано, что она необратима именно алгоритмически. Более того, не доказано, что существует хотя бы одна необратимая функция в принципе. Более того, нахождение (доказательство) хотя бы одной трудно обратимой функции будет автоматические доказывать, что P!=NP.
То есть, интуитивно кажется, что восстановить по x=SHA512(4TbPornImage.iso) сам 4TbPornImage.iso должно быть сложно. Но нет никаких разумных доказательств того, что нельзя написать полиномиальную функцию BSHA(x), которая будет гарантированно выдавать какой-то бессмысленный набор байт z такой что SHA512(z)=x.
>>Гипотетически, можно иметь огромный словарь
Вам потребуется бесконечный словарь. То есть функция. Конечно, её сложность надо учитывать.
Отдельно
На самом деле, существование односторонних функций — вещь еще более сильная, чем P!=NP.
То есть, возможно, P!=NP, но при этом односторонних функций всё-таки не существует.
(Иными словами, P!=NP гарантирует только необратимость в худшем случае, а для существования односторонних функций нужна трудность в среднем)
Но если так-то дело дрянь, потому что и всей магии P=NP нету, и криптография тоже разваливается.
Мне действительно интересно… вот на Марсе вся атмосфера из углекислого газа.
Значит в некотором смысле, Марс — рай для растений.
Конечно, далеко не на 100%, потому что там еще холодно и маленькое давление.
Но бать может, что-нибудь живое на земле способно переносить такие условия? И если его туда просто принести в количестве, способном к поднятию марсоходом — то без конкурентов и в изобилии ресурсов этот вид там и рос бы безгранично, заодно обогащая атмосферу кислородом.
Это, конечно, не решает проблемы с давлением, но уж может повлиять на температуру.
>>И существование односторонних функций сильнее, чем P != NP в среднем.
Но из существования односторонних функций следует неравенство в среднем.
Я просто хотел показать, что пример с хешами сильнее, чем P!=NP. (как минимум уже потому что неравенство в среднем уже сильнее)
На самом деле, конечно, даже существования односторонних функций хватает не для всей криптографии.
В криптографическом определении именно «правые» функции.
Пруф:
То есть, не существует ни одного полиномиального «правого» обращения.
«левое» обращение слишком слабое.
В случае перемножения двух простых чисел ответ однозначен. В случае составных — нет.
А если докажут, что её нельзя посчитать за полиномиальное время, то окажется, что P!=NP.
Кандидатов-то в функции хватает: a*b, DLog, Rabin.
Хеши в некотором смысле — тоже кандидаты. Если окажется, что P=NP, то они все тоже вроде как, рухнут.
Пусть у вас есть функция F( X ) = Y
Обратной ей называется функция G(Y), такая что F(G(Y)) = Y
Обратная функция не обязана находить X. Обратная функция обязана находить значение из класса эквивалентности относительно исходной функции. (любое значение, которое даёт Y)
Именно это я называл поиском коллизий, и оно почти так используется в литературе. (С поправкой на рандомизируемость)
Теперь второе ваше утверждение:
>>Необратимость по определению хэш функции должна присутствовать.
Ни для одной хеш-функции не доказано, что она необратима именно алгоритмически. Более того, не доказано, что существует хотя бы одна необратимая функция в принципе. Более того, нахождение (доказательство) хотя бы одной трудно обратимой функции будет автоматические доказывать, что P!=NP.
То есть, интуитивно кажется, что восстановить по x=SHA512(4TbPornImage.iso) сам 4TbPornImage.iso должно быть сложно. Но нет никаких разумных доказательств того, что нельзя написать полиномиальную функцию BSHA(x), которая будет гарантированно выдавать какой-то бессмысленный набор байт z такой что SHA512(z)=x.
>>Гипотетически, можно иметь огромный словарь
Вам потребуется бесконечный словарь. То есть функция. Конечно, её сложность надо учитывать.
Отдельно
На самом деле, существование односторонних функций — вещь еще более сильная, чем P!=NP.
То есть, возможно, P!=NP, но при этом односторонних функций всё-таки не существует.
(Иными словами, P!=NP гарантирует только необратимость в худшем случае, а для существования односторонних функций нужна трудность в среднем)
Но если так-то дело дрянь, потому что и всей магии P=NP нету, и криптография тоже разваливается.
Значит, какие-то рецензенты там должны быть.
У меня, кстати, там знакомые публиковались — значит не совсем мурзилка издание.
Не доказано, что быстрых функций поиска коллизий не существует.
А то я тоже завис на таком извращении.
Двадцать тысяч?!?!
А я-то уже думал хвалебный коммент запостить.
Да Sailfish стоит дешевле. А он на самодельной ОСи.
Сам стараюсь писать похожим образом.
Впадины хороши тем, что там большое давление.
А у шапок давление маленькое. Подкрасим черным — будет возгонка изо льда сразу в пар.
Вода там во впадинах.
Бурить — опять же, не выход.
Но энивей, даже цианобактерии нуждаются в свете для фотосинтеза.
Я что-то вообще в принципе не вижу способов ее решить, потому что топить — явно не вариант.
Значит в некотором смысле, Марс — рай для растений.
Конечно, далеко не на 100%, потому что там еще холодно и маленькое давление.
Но бать может, что-нибудь живое на земле способно переносить такие условия? И если его туда просто принести в количестве, способном к поднятию марсоходом — то без конкурентов и в изобилии ресурсов этот вид там и рос бы безгранично, заодно обогащая атмосферу кислородом.
Это, конечно, не решает проблемы с давлением, но уж может повлиять на температуру.
Собственно, чуть ли не на Хабре было, что ПР договаривается о пресортировке почты за границей.
Вообще, с тех пор как у них главного выгнали, они начали шевелиться. У меня открытки в Москву из Эдинбурга за 2 недели дошли в Октябре.
www.itas2010.iitp.ru/pdf/1569329536.pdf
Алгоритм, кстати, отличный. У меня в софтине работал на ура.
Просто в 19 веке транслитерация была популярнее транскрипции.
Всем известный «Айвенго» изначально на русский переводился как «Ивангое» (Ivanhoe)
«Робинзон Крузо» — как «Робинзон Крузоэ»