Любая NP-полная задача. Задача об упаковке рюкзака, например. В общем виде (без ограничений на числа из набора). Если в наборе N чисел, то на классическом компьютере для отыскания решения необходимо выполнить (2^N)-1 опробований, а на квантовом при помощи алгоритма Гровера - около (2^{N/2})-1 опробований. Так что выигрыш не очень существенный. Но для некоторых задач строго доказано, что за счёт применения специализированного квантового алгоритма решения выигрыш может быть существенным. Таких задач известно две: задача дискретного логарифма и задача факторизации.
Фигня. Если речь идёт о консенсусе POW, например для биткойна, то максимум, что можно сделать - это повысить эффективность поиска решения за счёт квантового алгоритма Гровера. А он даёт выигрыш в корень квадратный раз из мощности пространства. Если используется SHA256, то это будет O(\sqrt{2^{256}}), что в общем-то ничего не даёт в практическом отношении и более того, легко «лечится» заменой SHA256 на SHA512, например. Так что владельцы квантовых компьютеров - легкого бабла вам не видать!
Задача дискретного логарифмирования, а также задача факторизации, которые лежат в основе атак на известные асимметричные криптосистемы, решаются с полиномиальной трудоёмкостью на квантовом компьютере. Это фундаментальный результат Шнорра. Это означает, что при наличии квантового компьютера с достаточным количеством кубит все эти криптосистемы находятся в группе риска. Именно по этой причине в нестоящее время интенсивно развивается такое направление как постквантовая криптография. В рамках постквантовой парадигмы предполагается конструирование криптосистем, атаки на которые сводятся к решению NP-полных задач, например. Надо только помнить, что силовая атака (исчерпывающий перебор) может быть относительно эффективно реализована при помощи квантового алгоритма Гровера. Иными словами, объём перебора можно сократить приблизительно в корень квадратный из мощности пространства возможных решений.
Дополнение относительно замечания под п.4. Наш вариант с применением итеративного хеширования в плане вычислительной трудоёмкости ничем не отличается от предложенного вами в п.4. Как Вы думаете почему?
Есть подгруппа G_3 простого порядка m, а точки с таким обозначением нет. Для обозначения точек используется иной шрифт.
Практических задач много. Нам они известны. А ещё больше тех, про которые мы сами пока ещё не догадываемся. А приведённый пример разве не иллюстрирует решение, которое позволяет управлять доступом к ресурсам? Или вам это кажется высосанным из пальца?
Это правильное замечание. Здесь можно много разных вариантов придумать. Прямого отношения к протоколу эти вещи не имеют.
Эти процедуры безусловно рассмотрены и проанализированы. Они описаны в нашем внутреннем документе. А также много чего ещё. Просто публикация на Хабр рассчитана не на специалистов в области криптографии, хотя в ней приводятся некоторые содержательно важные сведения.
Тут тоже правильное замечание. Включение/исключение приводит к замене группового общедоступного ключа, а также персональных секретов участников. При исключении необходимо отказаться от ранее использованного долговременного секрета β, тогда как при включении это не обязательно.
"Порядок простого поля" - это терминологический нонсенс. Бессмысленный набор слов. Из описания ясно, что рассматриваются только простые поля. Иными словами, характеристика поля - простое число. Поля вида GF(p^k), где к-некоторое натуральное число, возникают только в контексте билинейного отображения. Так что в общем виде характеристика поля - либо простое число, либо некоторая степень простого числа. И не несите всякую чушь про ЧСВ. На этом заканчиваем, поскольку вникать во что-либо у вас желания нет. Более того, я уже потратил достаточно времени, отвечая на ваши вопросы.
Зато все программисты считают себя криптографами. А как копнешь, так сразу ясно, что знают только слова, и то не все. В лучшем случае могут что-то складывать из готовых "кубиков". Причём часто делают это неправильно. Такова реальность.
Поле появляется только тогда, когда число простое. Сей удивительный факт был установлен великими: Лежандром, Галуа и многими другими. Они вначале также как вы недоумевали на этот счёт. Но это факт. Так что ничего тут не поделаешь.
Это именно потому, что вы в детали не хотите вникать. Дьявол-то в деталях, как говорится. Делом в том, что порядок мультипликативной группы простого поля GF(p) равен p-1. Поскольку р - простое число, то порядок всегда число составное. Для группы точек эллиптической кривой порядок находится в интервале Хассе. В принципе там могут быть простые числа. Но с некоторой вероятностью. Тут начинает работать большая теория и обсуждать это здесь не имеет смысла. Хоп!?
Ваши комментарии говорят о том, что вы не склонны к сотрудничеству. Мы тут действуем предельно цинично. Если пользы нет, то нет и взаимодействия. Поэтому вам придётся обойтись теми материалами, которые имеются. С уважением, ENCRY.
Нам нужно время для принятия решения. Поймите, у нас перед вами нет никаких специальных обязательств, а мы пока до конца не понимаем зачем вам это нужно.
У группы простого порядка подгруппы нет, конечно. Вы не поняли смысла. Находится группа такого составного порядка (отмечу, что это всегда натуральное число), что в его каноническом разложении имеется большое (соответствующее требованию криптостойкости) простое число. Это означает, что в группе имеется подгруппа этого самого простого порядка. Атака на основе принципа "разделяй и властвуй" для простого порядка не работает. Но для DLP известны и другие атаки субэкспоненциальной трудоёмкости. А вот для ECDLP такие атаки не известны. Но для ECDL есть так называемые атаки изоморфизма, которые включают спаривание в том числе. Но мы умеем с этим бороться. Надеюсь, что объяснил.
Вы о чём? Число атомов Вселенной 10^77(2^265). Число атомов галактики 10^67(2^223). Число атомов Солнца 10^57(2^190) и так далее. Когда это «ёмкость» закончится? Вы давайте не общими соображениями руководствуйтесь, а смотрите на конкретные числа. Это всегда полезно.
Вы не понимаете, что значит анонимность. Сейчас поясню. Вы, когда пользуетесь ЭЦП, то для её проверки применяете общедоступный ключ из сертификата, выданного на имя заверителя. В сертификате будет указано, кому именно этот ключ принадлежит. Иначе никакого смысла в ЭЦП нет. Следовательно, вы точно знаете кто именно подписал, когда выполняете проверку подписи. Именно по этой причине никакой анонимности быть не может.
Если сторонний наблюдатель начнёт коллекционировать данные, которыми обмениваются стороны в ходе различных сессий этого протокола, то он просто увидит наборы чисел из некоторого диапазона, про которые можно утверждать только то, что они распределены независимо и равномерно. Это та самая «рандомность», о которой так любят рассуждать неофиты. Больше никакой информации извлечь нельзя. Это доказано.
Любая NP-полная задача. Задача об упаковке рюкзака, например. В общем виде (без ограничений на числа из набора). Если в наборе N чисел, то на классическом компьютере для отыскания решения необходимо выполнить (2^N)-1 опробований, а на квантовом при помощи алгоритма Гровера - около (2^{N/2})-1 опробований. Так что выигрыш не очень существенный. Но для некоторых задач строго доказано, что за счёт применения специализированного квантового алгоритма решения выигрыш может быть существенным. Таких задач известно две: задача дискретного логарифма и задача факторизации.
Фигня. Если речь идёт о консенсусе POW, например для биткойна, то максимум, что можно сделать - это повысить эффективность поиска решения за счёт квантового алгоритма Гровера. А он даёт выигрыш в корень квадратный раз из мощности пространства. Если используется SHA256, то это будет O(\sqrt{2^{256}}), что в общем-то ничего не даёт в практическом отношении и более того, легко «лечится» заменой SHA256 на SHA512, например. Так что владельцы квантовых компьютеров - легкого бабла вам не видать!
Задача дискретного логарифмирования, а также задача факторизации, которые лежат в основе атак на известные асимметричные криптосистемы, решаются с полиномиальной трудоёмкостью на квантовом компьютере. Это фундаментальный результат Шнорра. Это означает, что при наличии квантового компьютера с достаточным количеством кубит все эти криптосистемы находятся в группе риска. Именно по этой причине в нестоящее время интенсивно развивается такое направление как постквантовая криптография. В рамках постквантовой парадигмы предполагается конструирование криптосистем, атаки на которые сводятся к решению NP-полных задач, например. Надо только помнить, что силовая атака (исчерпывающий перебор) может быть относительно эффективно реализована при помощи квантового алгоритма Гровера. Иными словами, объём перебора можно сократить приблизительно в корень квадратный из мощности пространства возможных решений.
Дополнение относительно замечания под п.4. Наш вариант с применением итеративного хеширования в плане вычислительной трудоёмкости ничем не отличается от предложенного вами в п.4. Как Вы думаете почему?
Подробности здесь https://patentimages.storage.googleapis.com/da/b1/68/78fea0959be102/WO2021080449A1.pdf
Именно так и есть.
Есть подгруппа G_3 простого порядка m, а точки с таким обозначением нет. Для обозначения точек используется иной шрифт.
Практических задач много. Нам они известны. А ещё больше тех, про которые мы сами пока ещё не догадываемся. А приведённый пример разве не иллюстрирует решение, которое позволяет управлять доступом к ресурсам? Или вам это кажется высосанным из пальца?
Это правильное замечание. Здесь можно много разных вариантов придумать. Прямого отношения к протоколу эти вещи не имеют.
Эти процедуры безусловно рассмотрены и проанализированы. Они описаны в нашем внутреннем документе. А также много чего ещё. Просто публикация на Хабр рассчитана не на специалистов в области криптографии, хотя в ней приводятся некоторые содержательно важные сведения.
Тут тоже правильное замечание. Включение/исключение приводит к замене группового общедоступного ключа, а также персональных секретов участников. При исключении необходимо отказаться от ранее использованного долговременного секрета β, тогда как при включении это не обязательно.
"Порядок простого поля" - это терминологический нонсенс. Бессмысленный набор слов. Из описания ясно, что рассматриваются только простые поля. Иными словами, характеристика поля - простое число. Поля вида GF(p^k), где к-некоторое натуральное число, возникают только в контексте билинейного отображения. Так что в общем виде характеристика поля - либо простое число, либо некоторая степень простого числа. И не несите всякую чушь про ЧСВ. На этом заканчиваем, поскольку вникать во что-либо у вас желания нет. Более того, я уже потратил достаточно времени, отвечая на ваши вопросы.
Я то всё ждал вопросов про термоядерный реактор и квантовый компьютер. Вот уж печалька.
Зато все программисты считают себя криптографами. А как копнешь, так сразу ясно, что знают только слова, и то не все. В лучшем случае могут что-то складывать из готовых "кубиков". Причём часто делают это неправильно. Такова реальность.
Поле появляется только тогда, когда число простое. Сей удивительный факт был установлен великими: Лежандром, Галуа и многими другими. Они вначале также как вы недоумевали на этот счёт. Но это факт. Так что ничего тут не поделаешь.
Это именно потому, что вы в детали не хотите вникать. Дьявол-то в деталях, как говорится. Делом в том, что порядок мультипликативной группы простого поля GF(p) равен p-1. Поскольку р - простое число, то порядок всегда число составное. Для группы точек эллиптической кривой порядок находится в интервале Хассе. В принципе там могут быть простые числа. Но с некоторой вероятностью. Тут начинает работать большая теория и обсуждать это здесь не имеет смысла. Хоп!?
Ваши комментарии говорят о том, что вы не склонны к сотрудничеству. Мы тут действуем предельно цинично. Если пользы нет, то нет и взаимодействия. Поэтому вам придётся обойтись теми материалами, которые имеются. С уважением, ENCRY.
Ок. Для начала почитайте вот эту заявку https://patents.google.com/patent/WO2020076178A1/fr?inventor=Chmora&oq=Chmora
Нам нужно время для принятия решения. Поймите, у нас перед вами нет никаких специальных обязательств, а мы пока до конца не понимаем зачем вам это нужно.
У группы простого порядка подгруппы нет, конечно. Вы не поняли смысла. Находится группа такого составного порядка (отмечу, что это всегда натуральное число), что в его каноническом разложении имеется большое (соответствующее требованию криптостойкости) простое число. Это означает, что в группе имеется подгруппа этого самого простого порядка. Атака на основе принципа "разделяй и властвуй" для простого порядка не работает. Но для DLP известны и другие атаки субэкспоненциальной трудоёмкости. А вот для ECDLP такие атаки не известны. Но для ECDL есть так называемые атаки изоморфизма, которые включают спаривание в том числе. Но мы умеем с этим бороться. Надеюсь, что объяснил.
Если сторонний наблюдатель начнёт коллекционировать данные, которыми обмениваются стороны в ходе различных сессий этого протокола, то он просто увидит наборы чисел из некоторого диапазона, про которые можно утверждать только то, что они распределены независимо и равномерно. Это та самая «рандомность», о которой так любят рассуждать неофиты. Больше никакой информации извлечь нельзя. Это доказано.