Да при чём тут взломы? Какое это всё имеет отношение к делу? Думаете, что владеете сакральным знанием и хотите меня чему-то научить? «Есть многое на свете, друг Горацию…». В общем всё это выглядит достаточно нелепо. Вы частенько вместо конкретного ответа просто переходите на другую тему. Так дело не пойдёт. Я в таких «дискуссиях» не участвую.
Вы почему-то даже не понимаете, что запись вида – это какая-то дикость несуразная. Опять же Вы ведь программист. Ну, попробуйте сначала определить некоторую функцию с одним аргументом, а потом к ней обратиться, указав два или более аргументов. Вы думаете, что компилятор/интерпретатор или что там у вас, такое пропустит? И не надо полагать, что условная бумага всё стерпит.
Но если у группы пользователей будет одинаковый ключ...
Замечательно! Если секретный ключ какого-то одного пользователя будет раскрыт, то сразу автоматически пострадаю все остальные. Вы предложили решение, ущербность которого было осознано ещё несколько столетий тому назад. Я уж не говорю о проблемах с биллингом, которые возникают при таком подходе. Не надо заниматься вещами, в которых не разбираетесь. Программист не криптограф и уж точно не криптоаналитик. Это распространённое заблуждение.
Если длина b равна в точности блоку хеш-функции, то, например:
где запятой я отделил значение начального вектора инициализации. Но у вас длина b - не равна блоку
Вы совсем не понимаете теорию хеш-функций. Это ладно, многие не понимают. Но Вы же программист. Ну, взяли бы и написали простейшую программку и проверили, что n^3(b)=h(h(h(b))) не равно h(h^2(b)||b) и не равно h(b||b||b) для произвольного b. Если бы это было так, и Вы смогли бы доказать этот факт (для начала можно продемонстрировать на примере для некоторого b), то снискали ли бы славу выдающегося специалиста по хеш-функциям. Мировое признание было бы обеспечено. Хочу заметить, что я вообще-то ликбезом не занимаюсь. Читайте книжки, можете мою прочитать.
А по факту - там ещё один скрытый параметр - начальный вектор инициализации. Его я обозначил первым аргументом. А если, например, взять семейство SHA-2 (из FIPS PUB 180-4) - то там фигурирует ещё и третий аргумент - постоянный (неявный) ключ шифрования. Например, у SHA-2 - это первые 32 бита дробных частейкубических корней первых 64 простых чисел.
Этот вектор инициализации или ключ шифрования, как Вы его называете, – внутренняя константа хеш-функции. Вы к нему не имеете ни малейшего отношения и не можете ничего с ним делать. Если всё-таки пытаетесь, то это уже не будет стандартная хеш-функция с заявленными свойствами, а нечто совсем иное. Вообще при реализации хеш-функций может применяться множество всяких констант. Вы не понимаете, почему они такие и зачем нужны. Вот и спрашивается, какого чёрта Вы эту константу вытаскиваете наружу и ей манипулируете?
А обязательно нужно, чтобы x_i зависел от a_i, тем более что мы преследуем анонимность? Если не обязательно, то подойдет любой криптостойкий генератор случайных чисел. Или генератор псевдослучайных чисел с огромным периодом, формирующий последовательность на базе начального b
Анонимность здесь ни при чём. Не надо валить всё в кучу. Задача чётко сформулирована – все x_i должны быть различны. Покажите, что вычислительная трудоёмкость выбранного вами генератора псевдослучайных чисел для формирования x_i принципиально ниже предложенного нами способа. Я уже писал об этом. Повторять больше не буду.
Вы, когда пишете что-то, то будьте поаккуратнее. Вот что означает запятая? Ведь хеш-функция – это функция одного аргумента. Если Вы заметили, то в нашем тексте аргумент всегда один. Да, он может задаваться как конкатенация последовательностей, но всегда один. Для конкатенации используется специальное обозначение – две вертикальных палки. Обозначение стандартное. А что у вас имеется в виду?
Это было бы, на мой взгляд, более близко к программистам - тем кто, в конечном итоге, будет реализовывать протокол.
Программисты не принимают решения о воплощении той или иной практической задачи. Их мнение относительно некоторых аспектов реализации может быть принято во внимание. Если программист в состоянии придумать что-то похожее на представленный протокол, например, или нечто более совершенное как в теоретическом, так и в практическом отношении, то он уже программист в некотором ином смысле, отличном от общепринятого. Может, конечно, так себя называть. Ничего страшного. Я знаю людей, которые публично объявляют себя математиками, по-сути не являющихся таковыми. Что касается реализации этого протокола, то особо и напрягаться не надо – есть специализированные библиотеки. С другой стороны, если программист возьмёт на себя труд реализовать алгоритм Миллера для спаривания, например, то уровень его математической квалификации должен быть достаточно высок. Для этого надо понимать теорию дивизоров и смежные дисциплины. Иными словами, навыки программирования в таких задачах не являются преобладающими.
Статья начинается с уровня "Ничего не слышал про криптографию" и потом резко переходит на уровень "Эксперт по теории чисел". Это вызывает когнитивный диссонанс. Скромно предположу, что преамбула привлекает читателей из первой группы, но отталкивает из второй.
Эксперт по теории чисел - это сильно сказано, конечно. Содержательную часть по-любому надо было как-то описать. Был избран классический путь. Безусловно, он рассчитан на уровень физ-мат образования из 80-х. Как с этим делом сейчас, мы не очень представляем. Скорее всего плохо, чем удовлетворительно. Но решение о публикации на Хабр было принято в том числе и для расширения круга читателей. Нам интересны различные мнения.
А приведенная формула получения x_i - это вариант такого генератора на базе хеш-функции. Я правильно понял?
Можно делать по-разному. Самое главное, и этот момент отмечен в публикации, чтобы все x_i всегда были различными. И понятно почему (это важно для корректной работы протокола). Даже, если вдруг a_i=a_j при i не равном j. Если знаете как сделать иным способом, но с принципиально меньшей вычислительной трудоёмкостью, то интересно было бы узнать.
Меня немного смущает, что a_i - это множество всех последовательностей букв произвольной длины. Кто отвечает за генерацию?
Отвечает некая сущность, с неизбежностью существования которой мы вынуждены мириться. Государство, например. Это входные данные. На них не накладывается никаких ограничений. Для простоты можете представить, что это персональные данные: данные из паспорта, ИНН, номер водительского удостоверения и так далее. Эти данные можно представить в виде некоторой структуры или просто сериализировать. Для функции итеративного хеширования это просто последовательность букв в некотором алфавите. Двоичном, например.
Подозреваю, что причина кроется в том, что выход хеш-функции передается на её вход в качестве вектора инициализации:
где h^{i-1}(b) - это начальное значение вектора инициалиации хеш-функции h
Если внимательно посмотреть на определение функции итеративного хеширования, то понятно, что для вычисления i-го значения достаточно знать предыдущее (i-1)-ое значение. А для этого его надо сначала вычислить, а затем сохранить в памяти. Это означает, что для вычисления произвольного значения по нашему методу достаточно два раза обратиться к хеш-функции. Ровно столько, сколько необходимо для вычисления по вашей схеме. Например, для SHA256 надо будет зарезервировать память для хранения 256 бит. Причём после формирования множества X память можно освободить.
Но честно скажу, сам пока не могу придумать реальный кейс на использование. Т.е. придумать могу, но тут же приходит на ум, как использовать иные протоколы для реализации придуманной задачи.
Представьте, что когда Вы проходите через турникет в метро и подносите свой смартфон к NFC-считывателю, то запускается протокол идентификации, который не гарантирует анонимности. В итоге про ваши перемещения всё будет известно со всеми вытекающими последствиями. Вам бы это понравилось? Не сложно подключить фантазию и обобщить этот пример. А теперь придумайте как решить эту задачу, но только анонимно. Вы ведь утверждаете, что знаете как это сделать иным способом. Мне интересно.
Компания ENCRY публикует на Хабр конкретные результаты. Именно по этой причине все эти результаты предварительно подаются в виде PCT-заявки, а затем по прошествии некоторого времени переводятся на национальную фазу и подаются в США и ЕС. Замечу, что такой подход – это редкость. В основном на Хабр публикуются переводы статей из англоязычных источников, обзоры или некоторая аналитика. Полагаю, что те кто располагает оригинальными результатами поступают также как мы. Или же предварительно публикуют соответствующие статьи в рецензируемых периодических изданиях.
В качестве фантазии. Не исключаю, что возможна гибридная реализация, где некоторая часть будет имеет классическую архитектуру фон Неймана, а другая часть, для которой существенна суперпозиция состояний в контексте достижения эффекта квантового параллелилизма, будет уже воплощена на основе квантового процессора. Это такой разумный подход. Не понятно пока насколько он себя оправдывает.
Да не нужен тут никакой ГСПЧ. Не следует усложнять себе жизнь на пустом месте.
И где ошибся?
Да при чём тут взломы? Какое это всё имеет отношение к делу? Думаете, что владеете сакральным знанием и хотите меня чему-то научить? «Есть многое на свете, друг Горацию…». В общем всё это выглядит достаточно нелепо. Вы частенько вместо конкретного ответа просто переходите на другую тему. Так дело не пойдёт. Я в таких «дискуссиях» не участвую.
Вы почему-то даже не понимаете, что запись вида
– это какая-то дикость несуразная. Опять же Вы ведь программист. Ну, попробуйте сначала определить некоторую функцию с одним аргументом, а потом к ней обратиться, указав два или более аргументов. Вы думаете, что компилятор/интерпретатор или что там у вас, такое пропустит? И не надо полагать, что условная бумага всё стерпит.
Замечательно! Если секретный ключ какого-то одного пользователя будет раскрыт, то сразу автоматически пострадаю все остальные. Вы предложили решение, ущербность которого было осознано ещё несколько столетий тому назад. Я уж не говорю о проблемах с биллингом, которые возникают при таком подходе. Не надо заниматься вещами, в которых не разбираетесь. Программист не криптограф и уж точно не криптоаналитик. Это распространённое заблуждение.
где запятой я отделил значение начального вектора инициализации. Но у вас длина b - не равна блоку
Вы совсем не понимаете теорию хеш-функций. Это ладно, многие не понимают. Но Вы же программист. Ну, взяли бы и написали простейшую программку и проверили, что n^3(b)=h(h(h(b))) не равно h(h^2(b)||b) и не равно h(b||b||b) для произвольного b. Если бы это было так, и Вы смогли бы доказать этот факт (для начала можно продемонстрировать на примере для некоторого b), то снискали ли бы славу выдающегося специалиста по хеш-функциям. Мировое признание было бы обеспечено. Хочу заметить, что я вообще-то ликбезом не занимаюсь. Читайте книжки, можете мою прочитать.
Этот вектор инициализации или ключ шифрования, как Вы его называете, – внутренняя константа хеш-функции. Вы к нему не имеете ни малейшего отношения и не можете ничего с ним делать. Если всё-таки пытаетесь, то это уже не будет стандартная хеш-функция с заявленными свойствами, а нечто совсем иное. Вообще при реализации хеш-функций может применяться множество всяких констант. Вы не понимаете, почему они такие и зачем нужны. Вот и спрашивается, какого чёрта Вы эту константу вытаскиваете наружу и ей манипулируете?
Анонимность здесь ни при чём. Не надо валить всё в кучу. Задача чётко сформулирована – все x_i должны быть различны. Покажите, что вычислительная трудоёмкость выбранного вами генератора псевдослучайных чисел для формирования x_i принципиально ниже предложенного нами способа. Я уже писал об этом. Повторять больше не буду.
Вы, когда пишете что-то, то будьте поаккуратнее. Вот что означает запятая? Ведь хеш-функция – это функция одного аргумента. Если Вы заметили, то в нашем тексте аргумент всегда один. Да, он может задаваться как конкатенация последовательностей, но всегда один. Для конкатенации используется специальное обозначение – две вертикальных палки. Обозначение стандартное. А что у вас имеется в виду?
Программисты не принимают решения о воплощении той или иной практической задачи. Их мнение относительно некоторых аспектов реализации может быть принято во внимание. Если программист в состоянии придумать что-то похожее на представленный протокол, например, или нечто более совершенное как в теоретическом, так и в практическом отношении, то он уже программист в некотором ином смысле, отличном от общепринятого. Может, конечно, так себя называть. Ничего страшного. Я знаю людей, которые публично объявляют себя математиками, по-сути не являющихся таковыми. Что касается реализации этого протокола, то особо и напрягаться не надо – есть специализированные библиотеки. С другой стороны, если программист возьмёт на себя труд реализовать алгоритм Миллера для спаривания, например, то уровень его математической квалификации должен быть достаточно высок. Для этого надо понимать теорию дивизоров и смежные дисциплины. Иными словами, навыки программирования в таких задачах не являются преобладающими.
Эксперт по теории чисел - это сильно сказано, конечно. Содержательную часть по-любому надо было как-то описать. Был избран классический путь. Безусловно, он рассчитан на уровень физ-мат образования из 80-х. Как с этим делом сейчас, мы не очень представляем. Скорее всего плохо, чем удовлетворительно. Но решение о публикации на Хабр было принято в том числе и для расширения круга читателей. Нам интересны различные мнения.
Можно делать по-разному. Самое главное, и этот момент отмечен в публикации, чтобы все x_i всегда были различными. И понятно почему (это важно для корректной работы протокола). Даже, если вдруг a_i=a_j при i не равном j. Если знаете как сделать иным способом, но с принципиально меньшей вычислительной трудоёмкостью, то интересно было бы узнать.
Отвечает некая сущность, с неизбежностью существования которой мы вынуждены мириться. Государство, например. Это входные данные. На них не накладывается никаких ограничений. Для простоты можете представить, что это персональные данные: данные из паспорта, ИНН, номер водительского удостоверения и так далее. Эти данные можно представить в виде некоторой структуры или просто сериализировать. Для функции итеративного хеширования это просто последовательность букв в некотором алфавите. Двоичном, например.
где h^{i-1}(b) - это начальное значение вектора инициалиации хеш-функции h
Если внимательно посмотреть на определение функции итеративного хеширования, то понятно, что для вычисления i-го значения достаточно знать предыдущее (i-1)-ое значение. А для этого его надо сначала вычислить, а затем сохранить в памяти. Это означает, что для вычисления произвольного значения по нашему методу достаточно два раза обратиться к хеш-функции. Ровно столько, сколько необходимо для вычисления по вашей схеме. Например, для SHA256 надо будет зарезервировать память для хранения 256 бит. Причём после формирования множества X память можно освободить.
Представьте, что когда Вы проходите через турникет в метро и подносите свой смартфон к NFC-считывателю, то запускается протокол идентификации, который не гарантирует анонимности. В итоге про ваши перемещения всё будет известно со всеми вытекающими последствиями. Вам бы это понравилось? Не сложно подключить фантазию и обобщить этот пример. А теперь придумайте как решить эту задачу, но только анонимно. Вы ведь утверждаете, что знаете как это сделать иным способом. Мне интересно.
Компания ENCRY публикует на Хабр конкретные результаты. Именно по этой причине все эти результаты предварительно подаются в виде PCT-заявки, а затем по прошествии некоторого времени переводятся на национальную фазу и подаются в США и ЕС. Замечу, что такой подход – это редкость. В основном на Хабр публикуются переводы статей из англоязычных источников, обзоры или некоторая аналитика. Полагаю, что те кто располагает оригинальными результатами поступают также как мы. Или же предварительно публикуют соответствующие статьи в рецензируемых периодических изданиях.
Вообще очень рекомендую вот эту книжку https://biblio.mccme.ru/node/1547
В качестве фантазии. Не исключаю, что возможна гибридная реализация, где некоторая часть будет имеет классическую архитектуру фон Неймана, а другая часть, для которой существенна суперпозиция состояний в контексте достижения эффекта квантового параллелилизма, будет уже воплощена на основе квантового процессора. Это такой разумный подход. Не понятно пока насколько он себя оправдывает.
Описался. Результат Питера Шора. https://ru.m.wikipedia.org/wiki/Шор,_Питер