Как стать автором
Обновить

Комментарии 83

К счастью для Гэтсби, его друг Альберт, математик по образованию и криптограф по призванию, посоветовал ему хитроумный способ.

А без математики ту же задачу никак не решить?
— У вас продается славянский шкаф?
— Проезжайте!

Так надо новый пароль на каждую вечеринку. А описываемый способ позволяет менять список гостей, не уведомляя посетителей.

Так в чем проблема? В лишней рассылке пароля (через приложение, в которое так и так лезть при изменении списка), или в том, что какое-то кисо обидится, не получив свежего пароля? Оно же еще больше обидится, если оно набриолинится, а его развернут уже у шлагбаума.

Мил человек, вот идешь сюда https://cacr.uwaterloo.ca/hac/ и читаешь главу 10. Книжка старенькая, но там прямо так и верно написано, почему простые решения не проканывают. Недостаток образования, как обычно.

Альберт так же объяснил Гетсби, почему он должен потратить миллион своих денег на инновации?

Есть множество весьма состоятельных людей, которые готовы инвестировать в науку и технологии. Например, https://ru.wikipedia.org/wiki/Зимин,_Дмитрий_Борисович Просто вы их не знаете, к несчастью для себя. Так что учитесь, господа, просто учитесь.

Придите к Зимину за инвестициями, а если начнет глупые вопросы задавать — пошлите книжки читать. Не дело это гениев распрашивать, подписал счет толстосум — и свободен.
Да вы не переживайте. Всё уже случилось.
Да Вы не выдавайте желаемое за действительное.
Вопросы по существу есть? Если нет, то…
На вопрос по существу Вы уже успешно отреагировали телемедициной заочной диагностикой, так и не ответив на него. Считайте, что к Вам вопросов нет.

Вот это да! У вас так хорошо задачи получается решать....

А термоядерный реактор не подскажете как достроить? А еще квантовый компьютер хотелось бы.

Или, просто....

Как же меня тянет блевать от такого типичного американского стиля повествования с тупыми метафорами, подобными колику с дверцей.

Понимаю. Вас бы устроил текст, написанный писателем-середнячком из группы «Стальное вымя», начинающийся словами: «Инда взопрели озимые. Рассупонилось солнышко, расталдыкнуло свои лучи по белу светушку. Понюхал старик Ромуальдыч свою портянку и аж заколдобился».

Из условия не очень понятно, чем для решения данной задачи не подошла схема с проверкой подписи? Имхо она проще zkp.

Анонимность-то где с проверкой подписи? Вы текст читайте внимательно. Там же написано, что анонимность гарантируется. Вообще не раскрывается никакой существенной информации с точки зрения идентификации.

так, а анонимность какого рода гарантируется? те что не раскроется в итоге. в общем-то если подписать что-то, и отдать пользователю, то тоже не раскрывается существенной информации. сгенерированный ключ не раскроется.

Вы не понимаете, что значит анонимность. Сейчас поясню. Вы, когда пользуетесь ЭЦП, то для её проверки применяете общедоступный ключ из сертификата, выданного на имя заверителя. В сертификате будет указано, кому именно этот ключ принадлежит. Иначе никакого смысла в ЭЦП нет. Следовательно, вы точно знаете кто именно подписал, когда выполняете проверку подписи. Именно по этой причине никакой анонимности быть не может.

Если сторонний наблюдатель начнёт коллекционировать данные, которыми обмениваются стороны в ходе различных сессий этого протокола, то он просто увидит наборы чисел из некоторого диапазона, про которые можно утверждать только то, что они распределены независимо и равномерно. Это та самая «рандомность», о которой так любят рассуждать неофиты. Больше никакой информации извлечь нельзя. Это доказано.

Может быть, пример из статьи не совсем информативный? Ведь если проход на вечеринку осуществляется один раз, то достаточно, чтобы у каждого был приглашённого был рандомный приватный ключ, публичная часть которого подписана организатором. Т. е. протокол был бы таким:

  • Подготовка:

    • 1. Организатор генерирует пару ключей, и сообщает привратнику публичную часть.

    • 2. Каждый приглашённый генерирует свою пару ключей, и сообщает организатору публичную часть.

    • 3. Организатор отправляет каждому приглашённому подпись публичного ключа этого приглашённого, сделанную с помощью приватного ключа организатора.

  • Пропуск на вечеринку:

    • 0. Организатор сообщает привратнику список отозванных публичных ключей (соответствующих людям, которых организатор передумал приглашать).

    • 1. При появлении гостя, привратник генерирует рандомный nonce и просит гостя подписать его.

    • 2. Гость отвечает двумя блобами: подписью nonce, сделанную его собственным приватным ключом, и подписью публичного ключа, полученную от организатора.

    • 3. Привратник проверяет эти две подписи и проверяет список отозванных ключей, после чего пускает или не пускает гостя.

По сути, это вариация на стандартную тему remote attestation protocol, который, например, используется в TPM-чипах (например, насколько я знаю, DRM-системы уже используют такое в продакшене, чтобы отличать "своих"/"чужих" клиентов, не зная при этом настоящего идентификатора каждого пользователя).

Какое требование из описанной в статье задаче делает этот протокол неподходящим?

  • 2. Каждый приглашённый генерирует свою пару ключей, и сообщает организатору публичную часть.

    Приглашённый должен получить сертификат на свой общедоступный ключ. В нём будет точно указано, кому он принадлежит. Иначе, кто угодно может выдать себя за приглашённого. Если организатор отправляет приглашённому его же общедоступный ключ, заверенный ЭЦП организатора, то информация о приглашённом раскрывается. Это всего лишь одно наблюдение. В предложенном протоколе есть и другие «дыры». Вообще, обсуждать разные криптоподелки особого смысла нет. Если делаешь что-то новое, то доказывай. Если информация не разглашается, то необходимо доказать либо ZKP-свойство, либо, как альтернатива, свойства WI и WH.

Про наш протокол не доказано, что он обладает свойством ZKP. Только WI и WH, что на практике важнее.

Но когда порядок группы — простое число, то решение на основе упомянутого принципа не работает. Значит, для сохранения экспоненциальной трудоёмкости решения DLP в случае силовой атаки порядок должен быть простым числом и группа должна содержать подгруппу большого простого порядка.

Разве у группы простого порядка есть собственные подгруппы?

У группы простого порядка подгруппы нет, конечно. Вы не поняли смысла. Находится группа такого составного порядка (отмечу, что это всегда натуральное число), что в его каноническом разложении имеется большое (соответствующее требованию криптостойкости) простое число. Это означает, что в группе имеется подгруппа этого самого простого порядка. Атака на основе принципа "разделяй и властвуй" для простого порядка не работает. Но для DLP известны и другие атаки субэкспоненциальной трудоёмкости. А вот для ECDLP такие атаки не известны. Но для ECDL есть так называемые атаки изоморфизма, которые включают спаривание в том числе. Но мы умеем с этим бороться. Надеюсь, что объяснил.

В детали вопросов об атаках на DLP/ECDLP я вникать особо и не хочу. Но почему вы рассматриваете группу именно составного порядка? Почему сразу не брать группу большого простого порядка?

Это именно потому, что вы в детали не хотите вникать. Дьявол-то в деталях, как говорится. Делом в том, что порядок мультипликативной группы простого поля GF(p) равен p-1. Поскольку р - простое число, то порядок всегда число составное. Для группы точек эллиптической кривой порядок находится в интервале Хассе. В принципе там могут быть простые числа. Но с некоторой вероятностью. Тут начинает работать большая теория и обсуждать это здесь не имеет смысла. Хоп!?

Насчет мультипликативной группы понятно, хотя я и не уловил (точнее не пытался) зачем нужно брать поле именно простого порядка. Остальное... На остальное нет времени, чтобы вникать. Да и лень:) Материал статьи не на среднего читателя. Не каждый знает что такое группа/подгруппа/кольцо/поле... Что уж говорить про детали. Хотя тема в целом и интересная.

Поле появляется только тогда, когда число простое. Сей удивительный факт был установлен великими: Лежандром, Галуа и многими другими. Они вначале также как вы недоумевали на этот счёт. Но это факт. Так что ничего тут не поделаешь.

Не понимаю к чему ирония…
Порядок конечного поля не обязательно простое число (хотя его степень), если конечно вы не рассматриваете только поля вычетов…
Почему вам необходимо рассматривать только поля простого порядка — это как раз то, во что я вникать и не хочу.
Расслабьте ваше ЧСВ: Вам самому до Галуа далековато. С другой стороны, нелепо ожидать, что все, кто вас читает непременно держат в голове детали всех теорий, которые вы применяли. Интеллектуальный шовинизм — это хорошо, но в меру.

"Порядок простого поля" - это терминологический нонсенс. Бессмысленный набор слов. Из описания ясно, что рассматриваются только простые поля. Иными словами, характеристика поля - простое число. Поля вида GF(p^k), где к-некоторое натуральное число, возникают только в контексте билинейного отображения. Так что в общем виде характеристика поля - либо простое число, либо некоторая степень простого числа. И не несите всякую чушь про ЧСВ. На этом заканчиваем, поскольку вникать во что-либо у вас желания нет. Более того, я уже потратил достаточно времени, отвечая на ваши вопросы.

Зато все программисты считают себя криптографами. А как копнешь, так сразу ясно, что знают только слова, и то не все. В лучшем случае могут что-то складывать из готовых "кубиков". Причём часто делают это неправильно. Такова реальность.

Я то всё ждал вопросов про термоядерный реактор и квантовый компьютер. Вот уж печалька.

Не в том месте ищете требуемый уровень дискуссии.
Так я на вас надеялся. Вы же заявили тематику. Ладно. Всего наилучшего.
  1. Интересный протокол. Получается, мы можем определить, что, например, аутентифицировался "свой", но кто именно из группы "своих" - неизвестно. Я прав?

  2. Среди исходных данных заявлено G_3, но точка нигде не используется. Где-то опечатка?

  3. Полагаю, что протокол родился в процессе решения какой-то практической задачи. Не покажите примеров применения протокола на практике? Очень интересно.

  4. Почему решили использовать именно многократное хеширование h^i(b)? Как по вашему, такой вариант: x_i=h(h(a_i)||b||i)?

  5. К сожалению, не рассмотрена процедура добавления/удаления участников. Тоже интересно:

А описываемый способ позволяет менять список гостей, не уведомляя посетителей.

Вот здесь хотелось бы подробнее. У меня получается пока путём полного перерасчета Г. А это ведет к необходимости рассылки новых ключей всем старым участникам.

  1. Именно так и есть.

  2. Есть подгруппа G_3 простого порядка m, а точки с таким обозначением нет. Для обозначения точек используется иной шрифт. 

  3. Практических задач много. Нам они известны. А ещё больше тех, про которые мы сами пока ещё не догадываемся. А приведённый пример разве не иллюстрирует решение, которое позволяет управлять доступом к ресурсам? Или вам это кажется высосанным из пальца?

  4. Это правильное замечание. Здесь можно много разных вариантов придумать. Прямого отношения к протоколу эти вещи не имеют.

  5. Эти процедуры безусловно рассмотрены и проанализированы. Они описаны в нашем внутреннем документе. А также много чего ещё. Просто публикация на Хабр рассчитана не на специалистов в области криптографии, хотя в ней приводятся некоторые содержательно важные сведения.

  6. Тут тоже правильное замечание. Включение/исключение приводит к замене группового общедоступного ключа, а также персональных секретов участников. При исключении необходимо отказаться от ранее использованного долговременного секрета β, тогда как при включении это не обязательно.

Андрей Львович, спасибо за ответы! Единственное, в качестве пожелания: сделайте пометку, что алгоритм защищен патентом. А то я уже порывался найти ему применение в своей идее беспарольной аутентификации на сайтах... неловко вышло.

2 Да. Я потом уже сам догадался, что не прав.

3 Если честно, то кажется) Вот если бы пример был в виде: пусть у нас есть группа роутеров, которым необходимо... Есть N участников документооборота, необходимо... - или любой другой подобный вариант. Это было бы, на мой взгляд, более близко к программистам - тем кто, в конечном итоге, будет реализовывать протокол. Но честно скажу, сам пока не могу придумать реальный кейс на использование. Т.е. придумать могу, но тут же приходит на ум, как использовать иные протоколы для реализации придуманной задачи. Вот я о чём.

Немного занудства

Статья начинается с уровня "Ничего не слышал про криптографию" и потом резко переходит на уровень "Эксперт по теории чисел". Это вызывает когнитивный диссонанс. Скромно предположу, что преамбула привлекает читателей из первой группы, но отталкивает из второй.

5 На Хабре есть специалисты и по криптографии и по теории чисел (я дилетант и к ним не отношусь). Подозреваю, что они просто не увидели статью в мощном потоке ежедневных статей. Или не обратили внимание из-за преамбулы)

делайте пометку, что алгоритм защищен патентом.

Компания ENCRY публикует на Хабр конкретные результаты. Именно по этой причине все эти результаты предварительно подаются в виде PCT-заявки, а затем по прошествии некоторого времени переводятся на национальную фазу и подаются в США и ЕС. Замечу, что такой подход – это редкость. В основном на Хабр публикуются переводы статей из англоязычных источников, обзоры или некоторая аналитика. Полагаю, что те кто располагает оригинальными результатами поступают также как мы. Или же предварительно публикуют соответствующие статьи в рецензируемых периодических изданиях.

Но честно скажу, сам пока не могу придумать реальный кейс на использование. Т.е. придумать могу, но тут же приходит на ум, как использовать иные протоколы для реализации придуманной задачи. 

Представьте, что когда Вы проходите через турникет в метро и подносите свой смартфон к NFC-считывателю, то запускается протокол идентификации, который не гарантирует анонимности. В итоге про ваши перемещения всё будет известно со всеми вытекающими последствиями. Вам бы это понравилось? Не сложно подключить фантазию и обобщить этот пример. А теперь придумайте как решить эту задачу, но только анонимно. Вы ведь утверждаете, что знаете как это сделать иным способом. Мне интересно.

Вы ведь утверждаете, что знаете

Не утверждаю. Не знаю. Полагать, что знаешь, и знать на самом деле - не одно и тоже.

как это сделать иным способом

Например, использовать один общий ключ и протокол SRP. У меня как раз на него взгляд упал при поисках альтернативных механизмов аутентификации в веб. Он не обеспечивает анонимность, наоборот. Но если у группы пользователей будет одинаковый ключ...

Вы проходите через турникет в метро

Вот. Отличный кейс!

Но если у группы пользователей будет одинаковый ключ...

Замечательно! Если секретный ключ какого-то одного пользователя будет раскрыт, то сразу автоматически пострадаю все остальные. Вы предложили решение, ущербность которого было осознано ещё несколько столетий тому назад. Я уж не говорю о проблемах с биллингом, которые возникают при таком подходе. Не надо заниматься вещами, в которых не разбираетесь. Программист не криптограф и уж точно не криптоаналитик. Это распространённое заблуждение.

Вы предложили решение, ущербность которого

Всё верно. Поэтому сразу же отбрасывал такое "решение" в корзину. Вы высказали интерес к моим соображениям по поводу "альтернативных" реализаций ("Мне интересно"). И я честно привел, сразу оговорившись, что нигде не утверждал, что знаю "как лучше", а писал: "...тут же приходит на ум...". При этом не утверждал категорически, что не существуют кейсы (о которых сам не знаю), где ваш протокол был бы хорош и не мог бы заменён на иные существующие.

Ну хорошо. Как поступать, согласно вашему протоколу, если ключ одного из участников (x_i, P_i) будет скомпрометирован?

Включение/исключение приводит к замене группового общедоступного ключа, а также персональных секретов участников. При исключении необходимо отказаться от ранее использованного долговременного секрета β...

Ну хорошо. Как поступать, согласно вашему протоколу, если ключ одного из участников (x_i, P_i) будет скомпрометирован

Ничего фатального не произойдёт. Раскрытие персонального секретного ключа i-го участника не приводит к раскрытию ключей всех остальных. Но если такое вдруг случится, то для корректной работы протокола надо будет выбрать новую бету, вычислить новые персональные секретные ключи участников, сформировать новый общедоступный ключ и затем выполнить рассылку персональных секретных ключей. Более того, если все участники объединят свои усилия и сами раскроют свои секретные ключи, то они не смогут вычислить собственный групповой общедоступный ключ по той причине, что не знаю секретную бету. Для раскрытия беты надо найти решение DLP в G_3. Про это всё подробно написано в патентной заявке. Так что читайте. Там есть ответы на все вопросы.

Уточнение, чтобы окончательно прояснить. Очевидно, что кто угодно может организовать свою собственную вечеринку, со свои списком приглашённых, уникальным набором персональных секретных ключей и групповым общедоступным ключом. Но вот «влезть» в чужую вечеринку просто так не получится. Отчасти это связано с тем обстоятельством, что на групповой общедоступный ключ выдаётся сертификат, в котором указано, кто является устроителем вечеринки. Сертификат очевидно содержит ЭЦП удостоверяющего центра (УЦ). Если злонамеренные участники солидарными усилиями (сговор) попытаются модифицировать существующий групповой общедоступный ключ, например с целью несанкционированного включения каких-то других участников, что в принципе возможно, то для достижения цели им потребуется подделать ЭЦП сертификата этого ключа. А для этого нужно либо знать секретный ключ УЦ, либо отыскать решение DLP/ECDLP. Иначе в ходе проверки сертификата такой фальсифицированный групповой общедоступный ключ будет определён как не валидный и отвергнут. Одним словом, сертификат – это не просто фитюлька, дань моде, как некоторые полагают, а существенная составляющая протокола.

Всё верно. Поэтому сразу же отбрасывал такое "решение" в корзину. Вы высказали интерес к моим соображениям по поводу "альтернативных" реализаций ("Мне интересно"). И я честно привел, сразу оговорившись, что нигде не утверждал, что знаю "как лучше", а писал: "...тут же приходит на ум...". При этом не утверждал категорически, что не существуют кейсы (о которых сам не знаю), где ваш протокол был бы хорош и не мог бы заменён на иные существующие.

Вот зачем писать всякие необдуманные вещи и потом так нудно оправдываться? Не понимаю…

Статья начинается с уровня "Ничего не слышал про криптографию" и потом резко переходит на уровень "Эксперт по теории чисел". Это вызывает когнитивный диссонанс. Скромно предположу, что преамбула привлекает читателей из первой группы, но отталкивает из второй.

Эксперт по теории чисел - это сильно сказано, конечно. Содержательную часть по-любому надо было как-то описать. Был избран классический путь. Безусловно, он рассчитан на уровень физ-мат образования из 80-х. Как с этим делом сейчас, мы не очень представляем. Скорее всего плохо, чем удовлетворительно. Но решение о публикации на Хабр было принято в том числе и для расширения круга читателей. Нам интересны различные мнения.

Это было бы, на мой взгляд, более близко к программистам - тем кто, в конечном итоге, будет реализовывать протокол.

Программисты не принимают решения о воплощении той или иной практической задачи. Их мнение относительно некоторых аспектов реализации может быть принято во внимание. Если программист в состоянии придумать что-то похожее на представленный протокол, например, или нечто более совершенное как в теоретическом, так и в практическом отношении, то он уже программист в некотором ином смысле, отличном от общепринятого. Может, конечно, так себя называть. Ничего страшного. Я знаю людей, которые публично объявляют себя математиками, по-сути не являющихся таковыми. Что касается реализации этого протокола, то особо и напрягаться не надо – есть специализированные библиотеки. С другой стороны, если программист возьмёт на себя труд реализовать алгоритм Миллера для спаривания, например, то уровень его математической квалификации должен быть достаточно высок. Для этого надо понимать теорию дивизоров и смежные дисциплины. Иными словами, навыки программирования в таких задачах не являются преобладающими.

3 Прошу прощения, ответ выше писал, ещё не ознакомившись с документом. Чукча не читатель...

Дополнение относительно замечания под п.4. Наш вариант с применением итеративного хеширования в плане вычислительной трудоёмкости ничем не отличается от предложенного вами в п.4. Как Вы думаете почему?

4.A Подозреваю, что причина кроется в том, что выход хеш-функции передается на её вход в качестве вектора инициализации:

h^i(b)=h(h^{i-1}(b),b)

где h^{i-1}(b) - это начальное значение вектора инициалиации хеш-функции h.

(Данный факт упрощает вычисления x_i во время единовременной генерации множества X).

4.B Хм.. п. 4 не относится к протоколу... Получается, в качестве x_i можно вообще брать случайные числа, сформированные криптостойким генератором? А приведенная формула получения x_i - это вариант такого генератора на базе хеш-функции. Я правильно понял?

4.C Меня немного смущает, что a_i - это множество всех последовательностей букв произвольной длины. Кто отвечает за генерацию? Участник или (назовем его) Арбитр, раздающий участникам x_i, P_i? Почему смущает? Ну хотя бы потому, что отдача на откуп генерации a_i открывает вектор атаки на вычисление h^i(b). Самый примитивный пример: a_i - пустая строка от Хакера. С другой стороны, ну вычислит этот b или h(b) легитимный Участник, что это ему даст? Он и так может "слить" свой идентификатор постороннему.

Подозреваю, что причина кроется в том, что выход хеш-функции передается на её вход в качестве вектора инициализации:

h^i(b)=h(h^{i-1}(b),b)

где h^{i-1}(b) - это начальное значение вектора инициалиации хеш-функции h

Если внимательно посмотреть на определение функции итеративного хеширования, то понятно, что для вычисления i-го значения достаточно знать предыдущее (i-1)-ое значение. А для этого его надо сначала вычислить, а затем сохранить в памяти. Это означает, что для вычисления произвольного значения по нашему методу достаточно два раза обратиться к хеш-функции. Ровно столько, сколько необходимо для вычисления по вашей схеме. Например, для SHA256 надо будет зарезервировать память для хранения 256 бит. Причём после формирования множества X память можно освободить.

Меня немного смущает, что a_i - это множество всех последовательностей букв произвольной длины. Кто отвечает за генерацию?

Отвечает некая сущность, с неизбежностью существования которой мы вынуждены мириться. Государство, например. Это входные данные. На них не накладывается никаких ограничений. Для простоты можете представить, что это персональные данные: данные из паспорта, ИНН, номер водительского удостоверения и так далее. Эти данные можно представить в виде некоторой структуры или просто сериализировать. Для функции итеративного хеширования это просто последовательность букв в некотором алфавите. Двоичном, например.

А приведенная формула получения x_i - это вариант такого генератора на базе хеш-функции. Я правильно понял?

Можно делать по-разному. Самое главное, и этот момент отмечен в публикации, чтобы все x_i всегда были различными. И понятно почему (это важно для корректной работы протокола). Даже, если вдруг a_i=a_j при i не равном j. Если знаете как сделать иным способом, но с принципиально меньшей вычислительной трудоёмкостью, то интересно было бы узнать.

А обязательно нужно, чтобы x_i зависел от a_i, тем более что мы преследуем анонимность? Если не обязательно, то подойдет любой криптостойкий генератор случайных чисел. Или генератор псевдослучайных чисел с огромным периодом, формирующий последовательность на базе начального b. Например, Вихрь Мерсена, скорость которого приближается к скорости линейных конгруэнтных алгоритмов.

А обязательно нужно, чтобы x_i зависел от a_i, тем более что мы преследуем анонимность? Если не обязательно, то подойдет любой криптостойкий генератор случайных чисел. Или генератор псевдослучайных чисел с огромным периодом, формирующий последовательность на базе начального b

Анонимность здесь ни при чём. Не надо валить всё в кучу. Задача чётко сформулирована – все x_i должны быть различны. Покажите, что вычислительная трудоёмкость выбранного вами генератора псевдослучайных чисел для формирования x_i принципиально ниже предложенного нами способа. Я уже писал об этом. Повторять больше не буду.

Покажите, что вычислительная трудоёмкость...

Это заявка на отдельную статью) Разрешите, я кратко?

После первичной инициализации генератора "Вихрь Мерсенна", получение следующих 624 чисел сводится к 6 сдвиговым и логическим операциям на число. Через каждые 624 числа (начиная с нулевого), идет "перемешивание", влекущее к необходимости выполнить 227 раундов по 6 логических и сдвиговых операций, и 397 раундов по 5 логических и сдвиговых операций. Итого: 3347 операций через каждые 624 числа. Это справедливо для "стандартных" (рекомендуемых) параметров алгоритма.

Теперь SHA-2 (256 бит). В основном цикле производится 64 раунда по 26 арифметико-логических и сдвиговых операций. Перед основным циклом производится 48 раундов по 13 арифметико-логических и сдвиговых операций. Итого: 2288 операций на каждый хеш.

Таким образом, при выдаче каждого n*624 (n = 0, 1, ...) числа, Вихрь Мерсенна будет примерно в 1,5 раза медленнее SHA-2 (256), а при выдаче остальных чисел - Вихрь будет примерно более чем в 300 раз быстрее.

Андрей Львович, а я не агитирую Вас немедленно всё бросить, и переписать ту часть протокола, которая к протоколу-то не сильно относится. Ага, особенно под влиянием изречений неизвестного сетевого анонимуса. Я не критикую, а интересуюсь: почему было выбрано именно такое решение. И дело не вычислительной трудоёмкости. Я ожидал услышать от Вас что-то в духе: "мы проанализировали различные схемы генерации ключевой информации, и пришли к выводу, что криптостойкость (иные требуемые параметры: скорость, предсказуемость) предложенной схемы, превышает криптостойкость классических схем генерации на базе ГПСЧ. Вот анализ здесь, и здесь...".

Что ж, Вы уже достаточно ответили по данному вопросу. Думаю, эту ветку можно закрыть.

Да не нужен тут никакой ГСПЧ. Не следует усложнять себе жизнь на пустом месте.

… будет примерно более чем в 300 раз быстрее.

В это не верю. Надо проверять. Тем более, что никакого разумного объяснения Вы не предлагаете. Здесь нужны аналитические оценки. Например, в случае SHA256 для последовательности из n бит на входе вычислительная трудоёмкость формирования выходного значения оценивается как O(n^2) двоичных операций. Если Вы понимаете, что означает O-большое или «символ Бахмана». Такая же оценка нужна и для вашего генератора. Тогда можно будет как-то сравнивать вычислительную трудоёмкость. Конкретные цифры не имеют особого смысла, так как привязаны к той или иной платформе, другим вещам, которые могут сильно варьироваться. Вообще-то пониманию этих вещей учат студентов в рамках университетского курса computer science.

h^i(b)=h(h^{i-1}(b),b)

Вы, когда пишете что-то, то будьте поаккуратнее. Вот что означает запятая? Ведь хеш-функция – это функция одного аргумента. Если Вы заметили, то в нашем тексте аргумент всегда один. Да, он может задаваться как конкатенация последовательностей, но всегда один. Для конкатенации используется специальное обозначение – две вертикальных палки. Обозначение стандартное. А что у вас имеется в виду?

А что у вас имеется в виду?

Начальное состояние хеш-функции, которое неявно фигурирует в выработке хеша. Да, Вы правы: хеш-функция - это функция одного аргумента. Но только формально. А по факту - там ещё один скрытый параметр - начальный вектор инициализации. Его я обозначил первым аргументом.

А если, например, взять семейство SHA-2 (из FIPS PUB 180-4) - то там фигурирует ещё и третий аргумент - постоянный (неявный) ключ шифрования. Например, у SHA-2 - это первые 32 бита дробных частей кубических корней первых 64 простых чисел.

Если длина b равна в точности блоку хеш-функции, то, например:

h^3(b)= h(h(h(b))) = h(b||b||b)=h(h^2(b)||b)=h(h^2(b),b)

где запятой я отделил значение начального вектора инициализации. Но у вас длина b - не равна блоку. Тогда:

h^3(b)=h(h(h(b)))=h(h^2(b),b)

это я имел в виду.

Если у вас алгоритм генерации x_i не входит в протокол - может стоит вынести его в приложение, как рекомендацию при реализации протокола?

А по факту - там ещё один скрытый параметр - начальный вектор инициализации. Его я обозначил первым аргументом. А если, например, взять семейство SHA-2 (из FIPS PUB 180-4) - то там фигурирует ещё и третий аргумент - постоянный (неявный) ключ шифрования. Например, у SHA-2 - это первые 32 бита дробных частейкубических корней первых 64 простых чисел.

Этот вектор инициализации или ключ шифрования, как Вы его называете, – внутренняя константа хеш-функции. Вы к нему не имеете ни малейшего отношения и не можете ничего с ним делать. Если всё-таки пытаетесь, то это уже не будет стандартная хеш-функция с заявленными свойствами, а нечто совсем иное. Вообще при реализации хеш-функций может применяться множество всяких констант. Вы не понимаете, почему они такие и зачем нужны. Вот и спрашивается, какого чёрта Вы эту константу вытаскиваете наружу и ей манипулируете?

Вот и спрашивается, какого чёрта

Чтобы поломать алгоритм. Не все играют по правилам. Особенно взломщики.

это уже не будет стандартная хеш-функция

Вот с этого и начинаются взломы. Попытка что-то применить не стандартным образом, неожиданно для его разработчика. Например, с этого и начинались исследования криптоаналитиков по поиску механизмов генераций коллизий для SHA-1. Сначала, для специально подобранных векторов инициализаций удавалось найти коллизии. Потом уже был вскрыт общий алгоритм целенаправленной выработки коллизий для стандартной SHA-1. По этим фактам есть соответствующие публикации.

Ниже уже ответил про Ваше заблуждение относительно невозможности вызвать функцию с числом аргументов, превышающих её определение.

Да при чём тут взломы? Какое это всё имеет отношение к делу? Думаете, что владеете сакральным знанием и хотите меня чему-то научить? «Есть многое на свете, друг Горацию…». В общем всё это выглядит достаточно нелепо. Вы частенько вместо конкретного ответа просто переходите на другую тему. Так дело не пойдёт. Я в таких «дискуссиях» не участвую.

Ниже уже ответил про Ваше заблуждение относительно невозможности вызвать функцию с числом аргументов, превышающих её определение

Прямо можно подумать, что это оправдывает запись вида h(\cdot)=h(\cdot, \cdot), гдеh(\cdot)– стандартная криптографическая хеш-функция.

Сразу предупреждаю, всякие риторические приёмы со мной не проканают.

Если длина b равна в точности блоку хеш-функции, то, например:

h^3(b)= h(h(h(b))) = h(b||b||b)=h(h^2(b)||b)=h(h^2(b),b)

где запятой я отделил значение начального вектора инициализации. Но у вас длина b - не равна блоку

Вы совсем не понимаете теорию хеш-функций. Это ладно, многие не понимают. Но Вы же программист. Ну, взяли бы и написали простейшую программку и проверили, что n^3(b)=h(h(h(b))) не равно h(h^2(b)||b) и не равно h(b||b||b) для произвольного b. Если бы это было так, и Вы смогли бы доказать этот факт (для начала можно продемонстрировать на примере для некоторого b), то снискали ли бы славу выдающегося специалиста по хеш-функциям. Мировое признание было бы обеспечено. Хочу заметить, что я вообще-то ликбезом не занимаюсь. Читайте книжки, можете мою прочитать.

h^3(b)=h(h(h(b)))\neq h(b\|b\|b)\neq h(h^2(b)\|b)

что n^3(b)=h(h(h(b))) не равно h(h^2(b)||b) и не равно h(b||b||b) для произвольного b.

Да. Прошу меня простить, ошибся. Как Вы сказали, был не аккуратен.

взяли бы и написали простейшую программку и проверили

Уже. Проверил. Увидел где ошибся.

И где ошибся?

Признание ошибок – путь к постижению истины.

можете мою прочитать

Если будете столь любезны и дадите ссылку (можно в личку), обязательно почитаю.

Например, здесь можно взять https://es1lib.org/book/3154417/2f0618?id=3154417&secret=2f0618

Издана 20 лет назад, а написана ещё раньше. Многие разделы до сих пор актуальны. Раздел про квантовую криптографию, например. Интересно, 20 лет назад сколько вам годков-то было?

Вы почему-то даже не понимаете, что запись вида h(\cdot)=h(\cdot, \cdot)– это какая-то дикость несуразная. Опять же Вы ведь программист. Ну, попробуйте сначала определить некоторую функцию с одним аргументом, а потом к ней обратиться, указав два или более аргументов. Вы думаете, что компилятор/интерпретатор или что там у вас, такое пропустит? И не надо полагать, что условная бумага всё стерпит.

 Ну, попробуйте сначала определить некоторую функцию с одним аргументом, а потом к ней обратиться, указав два или более аргументов.

На многих языках программирования это вполне нормальный трюк)

Но это уже оффтопик, не имеющий отношение к начальной теме)

На многих языках программирования это вполне нормальный трюк)

Который существенно усложняет анализ кода и является источником множества ошибок.

А где ссылка на eprint? Или хотя бы pdf на английском. Статья на хабре - это конечно хорошо, но по вашему "Witness hiding identification protocol" гугл выдаёт ссылки только на "Encyclopedia of Information Science and Technology, Third Edition"

Это правильное замечание. Статья со всеми доказательствами уже готова и мы собираемся её опубликовать. Сделать это ранее не могли по очевидным причинам – нам нужна была патентная заявка. Что касается свойств WI и WH, то в нашей публикации на Хабр есть ссылка на основную статью по этой тематике.

нам нужна была патентная заявка

С этого надо было начинать и этим же заканчивать ) А чего в посте об этом не указали? Минусов боитесь насобирать?

Для начала можете посмотреть Written opinion of international searching authority (separate sheet) https://mega.nz/file/sa5HESAS#X7UGNu6fKWofByYA9IVckSDwvH3XWQqv34e7wWqyXfw

Я не утверждаю, что это полноценная экспертиза, но лучше, чем ничего. У других и этого нет.

Спасибо, но это совсем несерьёзно. Задача патентного бюро - проверить заявку на новизну, а не разбираться в её смысле. Поэтому так много патентов на вечные двигатели, в частности

Вам что надо? Я всё уже объяснил.

В нашей публикации всё написано по-существу. Если есть какие-то внятные соображения, то изложите их. Если нет, то чего зря клаву мять. А про публикацию в рецензируемом периодическом издании мы и без вас понимаем. А то прямо как Капитан-очевидность…

А чего вы тявкаете на всех? То "тыжпрограммист" то зачем зря клаву мять... Где опубликовались - такие комментарии и получили.
Ваш К.О.

Понятно. Соображений нет.

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.