Комментарии 46
Т.е. RSA (факторизация) и ECC (эллиптические кривые) достаточно легко могут быть обсчитаны на квантовом компьютере, а вот изогенные эллиптические кривые нет? Значит ли это, что квантовый алгоритм еще не придуман или обратный алгоритм изогенных кривых имеет такую же сложность как на квантовых, так и на обычных компьютерах?
Значит ли это, что квантовый алгоритм еще не придуман или обратный алгоритм изогенных кривых имеет такую же сложность как на квантовых, так и на обычных компьютерах?
Предпологается, что сложность на квантах того же порядка (хоть и не одинакова) как и на обычных.
и какая у него «глубина», сколько знаков после запятой?
3?
5?
3555?
Правильно так: кубит может находиться в состоянии, являющемся произвольной суперпозицией |0> и |1>. Может это быть |0>, может |1>, может (|0>+|1>)/sqrt(2), может какая угодно другая комбинация.
Понятия «знаков после запятой» тут нет, по-прежнему это один (ку)бит, одна ячейка памяти, один знак.
Он же бит, хоть и ку-бит. Т.е. он true&false.
на обывательский взгляд он сколькото «true» и сколькото «false» т.е. в пропорции, а до какогото знака?
ведь когда происходит загрузка значений они еще не «ку-бит» и имеют какуюто точность, вопрос какую?
Если мы возьмем обычный бит данных и измерим его, мы всегда получим какое-то одно значение — или true, или false. При этом оно совпадет с тем, что туда записали.
С кубитами не так: в кубит можно записать случайную величину, которая принимает значение true с вероятностью x, и false с вероятностью 1 — х. Тогда при первом измерении такого кубита мы получим значение 0 с вероятностью 1 — x, и 1 с вероятностью х, но тем самым мы разрушим его состояние — в будущем он всегда будет принимать то же самое значение, которое мы намерили. То есть, если у нас кубит с состоянием (|0> + |1>) / sqrt(2), то там не «записано 0 и 1 поровну», а вероятности того, что он при измерении окажется 0 и 1, одинаковые.
Это что касалось одного кубита. С несколькими кубитами ситуация еще интереснее — мы можем записать в них какое-нибудь совместное распределение всех этих кубитов (если это распределение не факторизуется, то такие кубиты называются запутанными). Это приводит к забавным эффектам: например, если у нас были два кубита с состоянием (|00> + |11>) / sqrt(2), то есть, они равновероятно либо оба равны 0, либо оба равны 1, то после измерения одного из них мы можем с уверенностью сказать о том, какой результат мы получим при измерении второго.
Мы можем себе представить устройства, которые работают с этими кубитами (некоторые из них уже существуют) — например, измеряют значение, меняют местами вероятности 0 и 1, или делают еще что-нибудь интересное. На основе этих квантовых вентилей можно построить гипотетическое вычислительное устройство точно так же, как обычный компьютер строится на основе логических вентилей.
Ну, если на пальцах, то оно как-то так устроено.
И вопрос «до какого знака там true&false» лишен смысла. Если у нас блок, который в кубит записывает распределение достаточно точен, то до большого, если он работает плохо, то будут ошибки. Но обычно, как и при работе с логическими вентилями, мы считаем нашу аппаратуру абсолютно надежной.
А то эти кванты на АлиЭкспресс уже скоро будут, а как туда OpenGL портировать или как ключи Телеграма подбирать непонятно :)
Вот, например, на что похож квантовый ассемблер?Над этим вопросом сейчас и ломают учёные умы, как бы.
То есть для идеального квантового компьютера, где можно «запутать» N кубитов произвольно — уже есть какое-то понимание… но их нет в природе. А те которые есть — сильно ограничены.
А то эти кванты на АлиЭкспресс уже скоро будут, а как туда OpenGL портировать или как ключи Телеграма подбирать непонятно :)До АлиЭкспресс им ещё… долго. Пока мы где-то на уровне ЭНИАКа, никакого ассеблера ещё нет, только машинные коды… причём свои у каждого экземпляра железяки…
нельзя ли попросить развить тему. Вот, например, на что похож квантовый ассемблер?
Попробуйте думать не в терминах «ассемблера» а в терминах logic gate'ов.
Там, где в классической вычислительной модели единички и нолики, здесь состояния кубитов.
Там, где в классической вычислительной модели простые и понятные гейты и/или/не (и т.д.), здесь свои гейты, из которых можно брать и собирать схему.
https://en.wikipedia.org/wiki/Quantum_gate
Они сложные, сложнореализуемые сами по себе и не описывают полностью все возможные смены состояний, но, в общем-то, это совершенно естественно, что квантовые компьютеры «непонятные» по сравнению с традиционными.
От квантовых компьютеров ждут, что они будут за полиномиальное время решать некоторые задачи, которые не решаемы в принципе за полиномиальное время на машинах тюринга / не решаемы на схемах из логических элементов полиномиального размера. (ну, насколько известно на данный момент, не решаемы. И при допущении P!=NP, конечно).
Совсем-совсем утрируя: мы хотим за полином делать вещи, которые ни на одном компьютере, ни на одном ассемблере и ни на одном из существующих языков программирования невозможно решать за полином.
Для этого предлагается использовать некоторую странную хрень. Если бы эту хрень можно было бы взять и очень просто описать традиционными языками программирования — затея была бы абсолютно бесполезной — мы же прямо в условии задачи заявили, что результат по определению своему недостижимым традицонными языками программирования и их вариациями.
А то эти кванты на АлиЭкспресс уже скоро будут,
Скоро не будут.
а как туда OpenGL портировать или как ключи Телеграма подбирать непонятно :)
В математике нет царских путей. Если любопытно, рекомендую книжку quantum computing since democritus (кроме quantum в ней очень много про сложность вычислений вообще относительно простым языком).
Потому квантовые примитивные ячейки — NOT, CNOT, CCNOT. Операция должна быть обратима, в частности, число входов равно числу выходов. Не может быть AND или OR, т.к. они необратимо теряют информацию. NOT не теряет, поэтому он остался, CNOT имеет классическую таблицу истинности 0 0 => 0 0, 0 1 => 0 1, 1 0 => 1 1, 1 1 => 1 0, т.е. первый бит (Control) регулирует, производится ли операция NOT над вторым битом, и как можете видеть, CNOT обратима. CCNOT — то же самое, три бита, второй Control управляет функционированием первого.
На самом деле, там не 0 и 1, а некая линейная комбинация |0> и |1>, поэтому понятие таблицы истинности для квантового примитива не совсем корректно. Оно заменяется на некий оператор (эти операторы можно довольно просто построить), который действует на это состояние, переводя его в другое состояние, так, чтобы для чистых состояний результат был эквивалентен классической таблице истинности.
А типичная для классических процессоров операция «перезаписи» ячейки памяти по идее, запрещена, т.к. старое значение необратимо теряется. Значит, и регистр в обычном понимании сделать нельзя. Могла бы быть разрешена операция «обмена».
Я не уверен, может быть, уже научились обходить все эти сложности и я устарел.
И сколько в том sqrt(2) знаков?
Или не имеет смысла даже интересоваться 1.41 или 1,414213562373? Потому как на результат/значение, не оно влияет?
Редуцируя («передавая в классический компьютер») эти состояния мы получаем их них «0» или «1» с какой-то вероятностью. Например, редуцируя первое состояние мы любой бит получим с одинаковой вероятностью, а редуцируя второе — шансы получить «0» в три раза выше, чем «1». Редукция чистых состояний (|0> и |1>) происходит точно.
Если результат будет неправильным, то просто надо провести вычисление повторно. В итоге рано или поздно нам повезет и мы получим правильный ответ :)
Например, по этой схеме работает алгоритм Дойча. Почитайте вики, там очень хорошее объяснение с примером работы. Да, задача, которую он решает, не слишком применима в реальной жизни, но существуют похожие более сложные алгоритмы для решения реальных задач.
Забудьте про перебор, конкретно RSA ломается факторизацией числа, которую алгоритм Шора делает эффективно. Не перебором каких-то там «наиболее вероятных комбинаций», он никак не оценивает вероятность комбинаций. А зная сомножители найти секретный ключ проще простого.
Если квантовый этап алгоритма Шора не нашёл подходящего значения периода (если мне память не изменяет, вероятность успеха — 2/3), мы это узнаем при проверке, на классическом этапе, и будем перезапускать квантовый этап до тех пор, пока он на найдёт подходящее значение.
Сможет, если построят достаточно большой КК (нужно 192 когерентных кубита, а пока IBM говорит, что у них есть 16; и не факт, что есть на самом деле). Но для этого могут быть существенные физические ограничения.
Про квантовые алгоритмы говорят уже больше 20 лет, но воз пока и ныне там: слишком сложно работать с кубитами. Хотя апгрейд крипто на более стойкое — это в любом случае полезно.
Статьи на википедии не помогли. =) Хотя как работает обычный компьютер понимается прекрасно.
Кубиты физически (как ячейки памяти) что из себя представляют? Как они запутываются/связываются с «соседями»?
Компания Microsoft тоже не осталась в стороне и в 2016 году выпустила библиотеку SIDH(Supersingular Isogeny Key Exchange) с открытым исходным кодом. Одним из преимуществ данной библиотеки является возможность использования эллиптических кривых в форме Монтгомери, которые защищают от атак по времени.
Вау, подумал я. Круто!
SIDH реализована на языке C
Oh wait…
if (CurveIsogeny == NULL) {
Status = CRYPTO_ERROR_NO_MEMORY;
goto cleanup;
}
Ну блин, опять пошло-поехало…
А что надо на крестах или ГОмосятине какой писать?
goto тоже нормальная практика для err_out/cleanup потому что 100500 проверок и только одно место для очистки всего сразу.
Я не буду говорить про Rust, но можно и на крестах, вообще-то. По крайней мере, типизация построже будет, а публичное API все равно extern «C».
На мой взгляд, goto — это не нормальная практика, это признак слабости и крохоборства :) Всегда можно написать без goto. И это не микроконтроллер с килобайтом памяти, чтобы там так байты и такты экономить.
На мой взгляд, опять-таки, криптографию нужно писать очень, очень, очень аккуратно, вплоть до MISRA C. А MISRA учит нас, что
Rule 14.4 (required): The goto statement shall not be used
По своему опыту могу сказать, что если в коде есть goto, то дальше ожидать можно чего угодно — игнорирования strict aliasing, касты через union, сдвиги отрицательных чисел влево и черт знает что еще.
Если ты такой идеалист оторванный от реальности, иди разгребай авгиевы конюшни в том же OpenSSH, потом будешь рассказывать про аккуратность, гото, мисра и прочие мастхэв идеалиста.
А, ну правильно, в openssh конюшни и дальше будем такие же конюшни разводить, прально.
Конечно, табуляция ведь гораздо важнее чем чистота кода!
И супер-пупер защищенная от квантовых компьютеров криптография будет за границы массивов выходить. Ну ок, на здоровье.
Не нужны твои плюсы никому, закапывай их.Серьёзно?
Все популярные либы написаны на си, как крипто, так и куча прочих.А когда копилятор, линкер или даже любимый вами OpenSSL переписывают на C++ — эти люди сразу из категории «кто-то» попадают в категорию «никто»?
Ну тогда нормально — скоро весь мир будет там, и «никто» в Ivan-спике будет обозначать «все».
Только зачем это — ума не приложу. Очень хочется получить значок «тролль»? Ну там есть много других способов это сделать.
Твоё мнение никому не интересно, можешь сколько угодно распинаться о том как по твоему надо делать, о розовых пони и прочих галлюцинациях.
Я же тебе предложил: иди и сделай, покажи как надо — тогда будет о чём подумать, пока ты очередной теоретег.
Мне кажется, что вы грубите мне несколько необоснованно. И откуда вы знаете, кому мое мнение интересно, а кому нет? Поэтому говорите, пожалуйста, только за себя.
Я не криптограф и не считаю себя достаточно квалифицированным специалистом, чтобы писать криптографические библиотеки. Однако это не мешает мне чувствовать code smell.
Реальный код это всегда компромисс между: скоростью работы, потребляемыми ресурсами, временем разработки, безопасностью, читаемостью, соблюдением кодстайла, писаниной тестов и документации и тд.
Это утверждение верно. Но в зависимости от области применения этого кода компромисс достигается в разных точках. Сайтик в интернете для 10 друзей можно делать как угодно, но от кода в медицинской или автомобильной технике зависят человеческие жизни! И там надежность играет (или, по крайней мере, должна играть) несколько большую роль, чем количество табуляций или скорость разработки. От криптографии зависят приватность и очень чувствительные данные людей, а иногда и жизнь/свобода.
А вообще, толстовато, уважаемый, толстовато.
Ничего лучше goto не придумано чтобы прыгать на кусок с очисткой ресурсов в случае ошибки.Не нужно никуда прыгать. Очистка ресурсов осуществляется в деструкторах в C++ — и все довольны.
Если ты такой идеалист оторванный от реальности, иди разгребай авгиевы конюшни в том же OpenSSHТот факт, что из-за юридических проблем криптография в большинстве программ выполняется через библиотеку состоящую почти полностью из антипаттернов не означает, что «так и надо». Просто изменить это тяжело — и, к сожалению, не по техническим причинам.
Это возможно, когда g^(w1+k*w2)=1 или w1+k*w2=0(mod q). Таким образом, зная значения периодов w1 и w2, можно найти k=-w1/w2.
Числа x1 и x2, таким образом, не связаны с числом k.
Алгоритм Шора, как уже было сказано, направлен на получение данных, позволяющих найти закрытый ключ, с помощью которого и можно однозначно произвести расшифрование информации на обычном компьютере.
Однако уже существует и другое направление в криптографии под названием квантовая криптография. Ее отличие от постквантовой криптографии состоит в том, что здесь как раз для защиты информации используются принципы квантовой физики.
Кубит в состоянии, которое в некотором роде является промежуточным межу 0 и 1. Он не находится одновременно в нескольких состоянии, состояние у него одно и вполне конкретное, однозначное и существующее. Оно является линейной комбинацией |0> и |1>. В реальной физической реализации кубита |0> и |1> можно придать гораздо менее абстрактный вид, типа состояний электрона в атоме, занимающих конкретные уровни энергии системы.
Кот Шрёдингера тоже находится в совершенно однозначном, конкретном состоянии, являющимся линейной комбинацией «жив» и «мёртв».
Вот это настоящее состояние, хоть и существует, определено в таком конфигурационном пространстве, которое непредставимо в реальном мире и не может возникнуть в качестве результата измерения. Измерения могут дать только вещественные положительные значения. Поэтому, при попытке узнать состояние объекта происходит изменение этого состояния, этот процесс называется редукцией. Старое состояние необратимо искажается, восстановить его нельзя (редукция — необратимый процесс). Оно переходит в одно из возможных измеримых состояний, которые были составляющими актуального состояния. Таким образом, для кубита мы получим 0 или 1, и вероятность получения одного из них зависит от того, в каком состоянии находился кубит. Если у нас был дву-кубит в состоянии (|11>+|00>)/sqrt(2) мы в результате редукции получим с одинаковой вероятности 00 или 11 и никогда 01 или 10, т.к. они не являлись составляющими исходного состояния. И кот именно при измерении переходит в жив или мёртв, и вероятность одного из исходов зависит от того, в каком состоянии он находился.
Если для системы выполняется эргодическая гипотеза и мы имеем технологию, как исходное состояние готовить в точности одинаково неограниченное количество раз, мы можем попробовать создать статистику и получить матрицу распределения вероятностей исходного состояния, т.е. узнать про него чуть побольше. Это максимум информации, который в принципе возможно получить о состоянии квантовой системы.
Именно свойство необратимости процесса редукции и используется для «квантовой криптографии».
Постквантовая криптография и закат RSA — реальная угроза или мнимое будущее?