Постквантовая криптография и закат RSA — реальная угроза или мнимое будущее? / forpes.ru

Главная
Постквантовая криптография и закат RSA — реальная угроза или мнимое будущее?

Постквантовая криптография и закат RSA — реальная угроза или мнимое будущее? +35

17.07.2017 05:44

NWOcs 46 17200 Источник

RSA, эллиптические кривые, квантовый компьютер, изогении… На первый взгляд, эти слова напоминают какие-то заклинания, но все куда ~~проще~~ сложнее, чем кажется!

Необходимость перехода к криптографии, устойчивой к атаке на квантовом компьютере, уже официально анонсирована NIST и NSA, из чего вывод довольно-таки простой: пора вылезать из зоны комфорта!

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

Чтобы разобраться в тонкостях криптографии на эллиптических кривых, проследить новомодные веяния постквантовой криптографии и даже прикоснуться к ней с помощью библиотеки Microsoft SIDH, добро пожаловать под кат, %username%!

1. Начнём с основ: чуть-чуть о криптографии

Что такое криптография и для чего она вообще нужна? Скажем, Алиса и Боб хотят обменяться сообщением, да так, чтобы его содержание оставалось в секрете. Очевидно, что у каждой из сторон должен быть свой ключ. И на этом этапе можно выделить два подвида криптосистем.

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

Такая проблема изящно решается в асимметричных криптосистемах с помощью специальных алгоритмов. Однако тут мы сталкиваемся с трудоемкостью операций, что может быть неэффективно для большого объема данных. В таких криптосистемах нужно очень постараться, чтобы из одного ключа вычислить другой, и, пока чей-то компьютер не обладает огромной мощью ~~темной стороны~~, можно быть относительно спокойными за секретность защищаемых данных.

Интересная многоходовочка… Ну а как она реализуется, спросит пытливый %username%? Все дело в так называемых односторонних функциях. Пусть есть функция $inline$ . По известному аргументу $inline$ вычислить значение функции $inline$ проще, чем захватить Вестерос с тремя драконами и армией безупречных. Однако вычисление аргумента $inline$ по известному значению функции $inline$ является довольно-таки трудоемкой задачей.

Наиболее известными кандидатами в односторонние функции являются задача факторизации числа, которая состоит в разложении числа на простые множители, и задача дискретного логарифмирования, которая заключается в поиске неизвестного $inline$ по известным значениям $inline$ и $inline$ , которые удовлетворяют: $inline$ . Первая, например, применяется в широко известной криптосистеме RSA, а вторую можно встретить в схеме установления ключа Диффи-Хэллмана.

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

2. А теперь посложнее: эллиптические кривые

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

$display$

Однако на практике такую форму кривой можно встретить нечасто. Различают формы Лежандра, Монтгомери, Гессе и т.д. Использование той или иной формы может увеличить эффективность операций над точками эллиптической кривой. Например, в форме Монтгомери есть возможность выполнять умножение точки на число за фиксированное время благодаря алгоритму лестницы Монтгомери.

Наверняка многие сталкивались с формой Вейерштрасса, ее называют канонической для полей с характеристикой $char K \neq 2,3$ :

$display$

Важной характеристикой эллиптической кривой является ее дискриминант, который для формы Вейерштрасса вычисляется так:

$\Delta=4a^3+27b^2$ .

Дискриминант не должен быть равен нулю, иначе кривая уже не будет эллиптической, так как будут существовать точки перегиба, как на кривой $inline$ на рисунке справа.

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

$inline$ задана над полем рациональных чисел.

image alt
Однако, при использовании рациональных чисел возникает сложность с их округлением, и, как следствие, с неоднозначностью операций зашифрования и расшифрования. Поэтому в криптографии эллиптические кривые задаются над конечным полем, где координаты точек – это элементы поля. График кривой, конечно, потеряет свою былую привлекательность, плавные линии заменятся на точки, но мы же любим эллиптические кривые далеко не за это!

Нельзя не упомянуть еще одну характеристику эллиптических кривых, которая (СПОЙЛЕР!) еще одарит читателей своим присутствием в статье. Речь идет о $inline$ инварианте, постоянной величине. Его вычисление для эллиптической кривой в форме Вейерштрасса тоже не обладает устрашающим воздействием на организм: $j = 1728 \frac{4a^3}{4a^3+27b^2}$

Свойства группы

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

Замкнутость означает, что результат сложения элементов группы тоже является элементом группы. Переведем в термины эллиптической кривой: при сложении точек эллиптической кривой получается точка, принадлежащая этой же кривой.

Как видно из рисунков сверху, геометрический смысл сложения точек на эллиптической кривой состоит в следующем: необходимо провести секущую через складываемые точки и отразить точку пересечения этой прямой с эллиптической кривой относительно оси Ox.
Ассоциативность означает независимость результата сложения от изменения порядка действия.
В группе должен существовать нейтральный элемент. Результат сложения любого элемента группы $inline$ и нейтрального будет равен тому же элементу.В эллиптических кривых роль нейтрального элемента играет бесконечно удаленная точка: $P_\infty: P_\infty+P=P+P_\infty=P$
К каждому элементу должен существовать обратный к нему (относительно основной операции). При сложении элемента группы и обратного к нему получаем нейтральный элемент.
Свойство коммутативности нам знакомо еще из школьной математики: от перестановки слагаемых сумма не меняется. Именно данное свойство и делает группу абелевой.

Пара слов о стойкости

Теперь поговорим немного о стойкости криптосистем, основанных на задаче дискретного логарифмирования. Пусть $inline$ – конечная циклическая группа, то есть, каждый ее элемент представим в виде степени одного-единственного элемента — образующей $inline$ : $<g\ > = G=\{1, g^2, g^3, ...,g^{q-1}\}$ .

В зависимости от выбора группы $inline$ существуют различные методы решения задачи дискретного логарифмирования. Так, для решения задачи дискретного логарифмирования в конечном поле, на общее несчастье существуют не только универсальные алгоритмы (метод Полига-Хеллмана, $\rho$ -метод Полларда и др.), которые имеют экспоненциальную сложность, но и специальные, имеющие субэкспоненциальную сложность (метод базы разложения, метод решета числового поля).

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

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

Данные кривые уязвимы к MOV атаке, которая позволяет сводить вычисление задачи дискретного логарифмирования в группе точек эллиптической кривой над полем $\mathbb{F}_q$ к задаче дискретного логарифмирования в конечном поле $\mathbb{F_q^k}$ . Учитывая, что длина ключа в криптографии на эллиптических кривых меньше, и что для суперсингулярных кривых значение $inline$ не является большим, реализация данной атаки проходит крайне успешно для злоумышленника.

Ну так в чем же проблема? Используем подходящие эллиптические кривые и радуемся жизни! Но не тут-то было…

3. Квантовая угроза

В последнее время широкую популярность получают квантовые вычисления. Если в классическом компьютере наименьшая единица информации представляется битом, который может принимать значение либо 0, либо 1 в одно время, то в квантовом эту роль выполняют кубиты. Их особенность состоит в том, что кубит может находиться и в состоянии 0, и в состоянии 1 одновременно. Это и дает квантовым компьютерам их превосходящую вычислительную мощь. Например, если мы рассматриваем четыре бита информации, то из всевозможных 16 состояний мы можем выбрать лишь одно в один момент времени. 4 кубита же могут находиться в 16 состояниях одновременно, то есть в суперпозиции, и данная зависимость растет экспоненциально с каждым новым кубитом.

Если в классическом компьютере логические элементы получают на вход биты информации, а на выходе выдают однозначно определенный результат, то в квантовом компьютере в качестве логического элемента берется так называемый квантовый гейт (quantim gate), который манипулирует значением целой суперпозиции.

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

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

С одной стороны, появление квантового компьютера — это круто. Серьезно. Во многих сферах науки такая машина принесет немало пользы (например, при моделировании), однако для криптографии такой значимый прорыв будет критичен. А все потому, что в 1994 году Питер Шор предложил квантовый алгоритм, который позволяет разложить число не за стотыщмильонов лет, а за вполне обозримое время.

Об алгоритме Шора

Модификация данного алгоритма позволяет решить и задачу дискретного логарифмирования. Обобщенно метод Шора состоит в сведении сложновычислимой на классическом компьютере задачи к вычислению порядка некой функции. Если рассматривать разложение числа на множители, или задачу факторизации, то в качестве той самой функции берется $f(x)=a^x(mod\, N)$ , где $inline$ число, которое раскладывается, а $inline$ специально подобранное значение, взаимно простое с $inline$ .Далее по ходу алгоритма находится период функции $inline$ , который удовлетворяет соотношению: $inline$ и, как следствие, выполняется $a^w=1(mod\, N)$ . По найденном периоду вычислить собственный делитель числа $inline$ можно с помощью алгоритма Евклида: $gcd(a^\frac{w}{2}, N)$ .

Для того, чтобы решить задачу дискретного логарифмирования, то есть, найти такое $inline$ по данным $inline$ , необходимо вычислить порядок другой функции, а именно: $f(x_1, x_2)=g^{x_1}y^{x_2}$ , где $inline$ образующая группы c числом элементов, равным $inline$ . Период функции представляется парой чисел $inline$ : $inline$ . Тогда решение задачи дискретного логарифмирования будет иметь вид: $k=-\frac{w_1}{w_2}(mod\, q)$ .

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

Неудивительно, что существование подобных алгоритмов и тенденция к разработке квантовых компьютеров подтолкнули специальные организации к размышлениям. Агентством национальной безопасности США, например, еще в 2015 году был анонсирован план перехода к алгоритмам, устойчивым к атаке на квантовом компьютере. А в 2016 году NIST США официально объявил о о запуске конкурса заявок на разработку алгоритмов постквантовой криптографии.

Постквантовая криптография не ограничивается одним примитивом, на самом деле, на данный момент рассматриваются несколько кандидатов. В их число могут, например, входить быстрые криптографические протоколы на решетках, схемы на хэш-функциях (например, подпись Меркла) и криптосистемы, основанные на некоммутативной алгебре (например, на группе кос). Свой выбор мы остановили на альтернативе, тесно связанной с эллиптическими кривыми (ведь мы их так любим!), а именно, с изогениями.

4. Isogeny will save us!

Начнем с понятия: изогения – это рациональное отображение, переводящее точки одной эллиптической кривой в точки изогенной кривой, оставляя неподвижной бесконечно удаленную точку. Пусть имеем две изогенные эллиптические кривые $inline$ и $inline$ . Изогенными они называются, если они заданы над одним полем и имеют одинаковое число точек.

Так вот, изогения — это, по сути, небольшой ВЖУХ, который берет точку кривой $inline$ на вход, а на выходе выдает точку кривой $inline$ . Ядром изогении называется множество точек на кривой $inline$ , которые переходят в бесконечно удаленную точку кривой $inline$ .

Для каждой изогении существует единственная дуальная изогения, выполняющая обратное преобразование. То есть, если изогения имеет следующий вид: $\phi:E_1 \rightarrow E_2$ , то дуальная к ней: $\hat{\phi}:E_2 \rightarrow E_1$ .

Если перемножить изогению и дуальную к ней, получим точку кривой $inline$ , умноженную на целое число $inline$ , которую называют степенью изогении. Изогении простых степеней могут задавать перестановки на множестве $inline$ инвариантов изогенных кривых. А последовательное наложение графов изогенных эллиптических кривых позволяет получить просто космически красивую звезду изогенных кривых, как на рисунке ниже.

Возможность применения изогений для построения криптосистем была предложена сравнительно недавно. В 2003 году автором E. Teske была опубликована работа, где изогении использовались в схеме с возможностью депонирования ключей. В 2006 году А. Г. Ростовцевым и А. Столбуновым схема шифрования Эль-Гамаля была адаптирована под изогении эллиптических кривых. В том же 2006 году для построения хэш-функций было предложено использовать графы изогенных суперсингулярных кривых. Важным и, можно сказать, переломным моментом в исследовании изогений является работа, опубликованная в 2010 году, где предлагается квантовый алгоритм, решающий задачу нахождения изогений несуперсингулярных кривых за субэкспоненциальное время. С этого момента исследования стали больше ориентированы на суперсингулярные кривые. Так, в сети уже можно найти схемы шифрования с открытым ключом, доказательства с нулевым разглашением, схему неоспоримой подписи и подписи вслепую.

5. Microsoft SIDH: что за покемон?

Компания Microsoft тоже не осталась в стороне и в 2016 году выпустила библиотеку SIDH(Supersingular Isogeny Key Exchange) с открытым исходным кодом. Одним из преимуществ данной библиотеки является возможность использования эллиптических кривых в форме Монтгомери, которые защищают от атак по времени.

SIDH реализована на языке C и поддерживает использование Microsoft Visual Studio на OC Windows и LNU GCC и clang на OC Linux. В библиотеке представлена реализация базовых арифметических функций с возможностью поддержки различных платформ, включая x64, x86 и ARM. Большим плюсом к производительности является оптимизированная реализация операций на эллиптических кривых.
В библиотеке реализован протокол разделения ключа Диффи-Хеллмана на изогениях суперсингулярных кривых.

Эта схема была предложена авторами Jao и DeFeo. Упрощенно ее можно описать следующим образом. В качестве параметров криптосистемы используется общеизвестная суперсингулярная кривая $inline$ и зафиксированные на ней точки $inline$ . Для удобства за ходом протокола можно следить на рисунке ниже.

Пусть Алиса хочет разделить с Бобом не жизнь, а закрытый ключ. Для этого она генерирует случайные числа $inline$ и строит изогению $\phi_A:E_0 \rightarrow E_A$ , где ядро задается как $inline$ .
Боб выполняет те же действия, но только строит уже изогению $inline$ , где в качестве ядра выбирается $inline$ .

Изогении $\phi_A$ и $\phi_B$ являются секретными и кому попало не передаются. Однако, и Боб, и Алиса могут без каких-либо последствий разделить точки на своих изогенных кривых, к тому же, переданы могут быть и сами кривые. Так и происходит на самом деле. Данный этап обозначен на рисунке пунктирной линией. Алиса передает Бобу точки $\phi_A(P_B)$ и $\phi_A(Q_B)$ , и саму кривую $inline$ . Боб делает тоже самое: передает Алисе точки $\phi_B(P_A)$ и $\phi_B(Q_A$ и кривую $inline$ .

А это вообще законно?! Можешь быть спокоен, %username%, зная обе изогенные кривые, злоумышленник не сможет вычислить саму изогению.

Итак, Алиса и Боб обменялись данными, теперь подходим к завершающему и невероятно красивому этапу, а именно, к получению общего ключа. Зная образы точек $inline$ и $inline$ на кривой $inline$ и случайные числа $inline$ и $inline$ , Боб сможет легко построить изогению $\phi'_A$ , а Алиса, обладающая тем же объемом информации, сможет построить изогению $\phi'_B$ . Изящное решение заключается в том, что изогении $\phi'_A$ и $\phi'_B$ приведут наших собеседников к кривой $E_{AB}$ , и в качестве ключа может быть взят ее $inline$ инвариант.

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

CurveIsogeny = SIDH_curve_allocate(CurveIsogenyData);
    if (CurveIsogeny == NULL) {
        Status = CRYPTO_ERROR_NO_MEMORY;
        goto cleanup;
    }
    Status = SIDH_curve_initialize(CurveIsogeny, &random_bytes_test, CurveIsogenyData);
    if (Status != CRYPTO_SUCCESS) {
        goto cleanup;
    }

Сама структура:

typedef struct
{    
    CurveIsogeny_ID  CurveIsogeny;                             
    unsigned int     pwordbits;                               
    unsigned int     owordbits;                               
    unsigned int     pbits;                                   
    uint64_t         prime[MAXWORDS_FIELD];                   
    uint64_t         A[MAXWORDS_FIELD];                       
    uint64_t         C[MAXWORDS_FIELD];                       
    unsigned int     oAbits;                                   
    uint64_t         Aorder[MAXWORDS_ORDER];                  
    unsigned int     oBbits;                                  
    unsigned int     eB;                                      
    uint64_t         Border[MAXWORDS_ORDER];                   
    uint64_t         PA[2*MAXWORDS_FIELD];                    
    uint64_t         PB[2*MAXWORDS_FIELD];                    
    unsigned int     BigMont_A24;                             
    uint64_t         BigMont_order[BIGMONT_MAXWORDS_ORDER];   
    uint64_t         Montgomery_R2[MAXWORDS_FIELD];           
    uint64_t         Montgomery_pp[MAXWORDS_FIELD];           
    uint64_t         Montgomery_one[MAXWORDS_FIELD];          
} CurveIsogenyStaticData;

Чтобы Алисе и Бобу обменяться ключами, достаточно вызвать пару функций, которые не обязывают знать того, что же творится «под капотом». Генерация ключей происходит с помощью функций:

Status = KeyGeneration_A(PrivateKeyA,PublicKeyA, CurveIsogeny);

Status = KeyGeneration_B(PrivateKeyB,PublicKeyAB CurveIsogeny);

Алиса и Боб обмениваются вычисленными открытыми ключами и находят общий ключ:

Status = SecretAgreement_A(PrivateKeyA, PublicKeyB, SharedSecretA, false, CurveIsogeny);

Status = SecretAgreement_B(PrivateKeyB, PublicKeyA, SharedSecretB, false, CurveIsogeny);

Среди функций в библиотеке можно выделить и базовые арифметические, которые помогут в реализации своих протоколов. Это, например, j_inv, вычисляющая j-инвариант эллиптической кривой, inv_3_way, находящая значение мультипликативно обратного, удвоение точки и сложение точек – xDBLADD, утроение точки – xTPL и т.д. С полным описанием вы можете ознакомиться в публикации.

6. It's coding time!

Чтобы не быть голословными и прикоснуться к светлому будущему в лице постквантовой криптографии, мы решили проверить применимость данной библиотеки на примере устройства с относительно ограниченной мощностью – мобильного телефона. В итоге, на OC Android было реализовано приложение для голосования. Его фишкой является внедрение постквантовой криптографии для зашифрования отправляемого голоса на устройстве и его расшифрования на сервере.

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

Итак, имеем общеизвестную кривую $inline$ , те же четыре точки на ней $inline$ , двух квантовых параноиков и сильное желание пообщаться. Инициализируем структуру с параметрами криптосистемы:

CurveIsogeny = SIDH_curve_allocate(CurveIsogenyData);
Status = SIDH_curve_initialize(CurveIsogeny, &random_bytes_test, CurveIsogenyData);

Открытый ключ здесь представлен в виде кортежа значений: $E_A, \phi_A(P_B), \phi_A(Q_B)$ и случайного числа $inline$ . Закрытый ключ представляется числами $inline$ и $inline$ , с помощью которых строится изогения $\phi_A:E_0 \rightarrow E_A$ .

Keys.PrivateKey = (unsigned char*)calloc(1, obytes);         
Keys.PublicKey = (unsigned char*)calloc(1, 4 * 2 * pbytes);      
random_bytes_test(10, Keys.k);
Status = KeyGeneration_A(Keys.PrivateKey, Keys.PublicKey, CurveIsogeny);

На этапе зашифрования Боб генерирует случайные значения $inline$ , $inline$ и строит изогению $\phi_B:E_0 \rightarrow E_B$ . Используя переданные ему значения открытого ключа $E_A, \phi_A(P_B), \phi_A(Q_B)$ , Боб, строя изогению $\phi'_B:E_A \rightarrow E_{AB}$ , переходит в общую кривую.

Status = KeyGeneration_B(IsogenyB, imagesB, CurveIsogeny); 
Status = SecretAgreement_B(IsogenyB, PublicKey, j, false, CurveIsogeny);

Дальше можете выдохнуть. $inline$ инвариант общей кривой $E_{AB}$ конкатенируется со числом $inline$ , и от этой мешанины берется хэш. Полученное значение ксорится с секретными данными. В случае приложения – это хэш от названия доклада.

strncat(j, k, 10);
shaCompute(j, hash); 
for (i = 0; i < strlen(message); i++) 
         message[i] ^= hash[i];

Алиса принимает кортеж из значений $E_B, \phi_B(P_A), \phi_B(Q_A)$ и значение шифртекста. По полученным данным она строит изогению $\phi'_A$ , переходит в общую кривую $E_{AB}$ и, используя ее $inline$ инвариант, расшифровывает сообщение.

Status = SecretAgreement_A(PrivateKey, imagesB, j, false, CurveIsogeny); 
strncat(j, k, 10); 
shaCompute(j, hash); 
for (i = 0; i < strlen(cipher); i++) 
          cipher[i] ^= hash[i];

При запуске приложения на сервер отправляется запрос, в ответ на который приходит список докладов. При желании пользователя проголосовать (ну и при нажатии соответствующей кнопки), сервер отправляет открытые параметры, необходимые для зашифрования голоса. Клиент, не теряясь, использует эти параметры, думает около 5-8 секунд, и отправляет необходимые параметры для расшифрования и шифр текст. Сервер это дело расшифровывает за каких-то 0.11 секунд и выдает клиенту результаты голосования.

Для того, чтобы «подружить» Java и C, была использована технология JNI. SIDH компилируется в библиотеку и подключается в коде на java:

static {
        System.loadLibrary("native-lib");
    }

Разработанное приложение можно было скачать на «Очной ставке» NeoQUEST 29 июня 2017 года! Многие слушатели воспользовались возможностью прикоснуться к, вероятно, будущему направлению в области криптографии и проголосовали за понравившийся доклад. Причем каждый голос был защищен от атак на квантовом компьютере! Ну а еще — приложение красивое!

И в заключение...

Безусловно, пока сложно судить о необходимости постквантовой криптографии, когда мощного квантового компьютера, по сути, и нет… Однако суета в NSA и NIST не могут не наводить на подозрения. О реальных мотивах такой спешки нам остается только догадываться. В любом случае, никогда не помешает перестраховаться и начать изучение нового и интересного направления в криптографии, тем более, если это вполне осуществимо на практике.

Если вам интересна реализация приложения, а также если появится желание написать нечто новое, милости просим в исходники!

Совсем скоро мы выложим на нашем youtube-канале видео докладов с «Очной ставки» NeoQUEST-2017, где будет, в том числе, и запись доклада про эллиптические кривые и постквантовую криптографию!

Ну а фотографии с NeoQUEST-2017 мы уже выложили в группе NeoQUEST ВКонтакте. В ближайшем будущем ждите новых статей, в том числе, и с разборами заданий hackquest (скрытого от глаз гостей «Очной ставки»)!

Поделиться с друзьями

-->

Комментарии (46)

kay
17.07.2017 10:34
#10315182
+2
Т.е. RSA (факторизация) и ECC (эллиптические кривые) достаточно легко могут быть обсчитаны на квантовом компьютере, а вот изогенные эллиптические кривые нет? Значит ли это, что квантовый алгоритм еще не придуман или обратный алгоритм изогенных кривых имеет такую же сложность как на квантовых, так и на обычных компьютерах?
1. RealSaniok
  17.07.2017 16:26
  #10315856
  +1
  Пока не доказано, что P?NP (одна из «задач тысячелетия» всего лишь) — любая асимметричная криптография под угрозой по определению
1. CuPoTKa
  17.07.2017 16:26
  #10315858
  +1
  Значит ли это, что квантовый алгоритм еще не придуман или обратный алгоритм изогенных кривых имеет такую же сложность как на квантовых, так и на обычных компьютерах?
  
  Предпологается, что сложность на квантах того же порядка (хоть и не одинакова) как и на обычных.
1. NWOcs
  18.07.2017 21:56
  #10318032
  +1
  Алгоритм Шора позволяет решать задачи факторизации и дискретного логарифмирования (как в конечном поле, так и в группе точек эллиптической кривой) достаточно быстро на квантовом компьютере. Задача вычисления изогений обеспечивает, по крайней мере, субэкспоненциальную сложность для квантового компьютера, то есть для несуперсингулярных кривых в настоящее время существует квантовый алгоритм, позволяющий решить задачу вычисления изогений за субъэкспоненциальное время. Если же рассматривать рассматривать суперсингулярные кривые, то для них существует алгоритм, дающий лишь экспоненциальную сложность.

BiosUefi
17.07.2017 10:42
#10315198
-5
>кубит может находиться и в состоянии 0, и в состоянии 1 одновременно.
и какая у него «глубина», сколько знаков после запятой?
3?
5?
3555?
1. merlin-vrn
  17.07.2017 12:44
  #10315436
  Это вопрос некорректный. Нисколько. Как и формулировка из статьи.
  
  Правильно так: кубит может находиться в состоянии, являющемся произвольной суперпозицией |0> и |1>. Может это быть |0>, может |1>, может (|0>+|1>)/sqrt(2), может какая угодно другая комбинация.
  
  Понятия «знаков после запятой» тут нет, по-прежнему это один (ку)бит, одна ячейка памяти, один знак.
1. John_SC
  17.07.2017 16:26
  #10315862
  Он же бит, хоть и ку-бит. Т.е. он true&false.
  1. BiosUefi
    17.07.2017 16:32
    #10315884
    -2
    > он true&false.
    на обывательский взгляд он сколькото «true» и сколькото «false» т.е. в пропорции, а до какогото знака?
    
    ведь когда происходит загрузка значений они еще не «ку-бит» и имеют какуюто точность, вопрос какую?
    
    alexeykuzmin0
    17.07.2017 18:54
    #10316068
    +1
    Тот факт, что «он одновременно 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» лишен смысла. Если у нас блок, который в кубит записывает распределение достаточно точен, то до большого, если он работает плохо, то будут ошибки. Но обычно, как и при работе с логическими вентилями, мы считаем нашу аппаратуру абсолютно надежной.
    
    mikhanoid
    17.07.2017 21:00
    #10316204
    В кубиты ничего не записывается. Кубиты, в некотором смысле, «поворачиваются» в нужное положение при помощи унитарных преобразований. А эти преобразования абсолютно точные, потому что работают на уровне физических симметрий (можно вспомнить спектры). Проблема в другом, сложно поддерживать большое когерентное состояние.
    
    Paulus
    17.07.2017 22:25
    #10316304
    нельзя ли попросить развить тему. Вот, например, на что похож квантовый ассемблер? С Intel 8008 было как-то проще, а тут 16 кубитов уже есть, а что они делают-то? 2+2 на них вычислить уже можно или стрелка подключенного к ним осциллографа пока только дискретное распределение с максимумом где-то в районе 5 начертить может?
    А то эти кванты на АлиЭкспресс уже скоро будут, а как туда OpenGL портировать или как ключи Телеграма подбирать непонятно :)
    
    khim
    18.07.2017 00:34
    #10316392
    +1
    Вот, например, на что похож квантовый ассемблер?
    Над этим вопросом сейчас и ломают учёные умы, как бы.
    
    То есть для идеального квантового компьютера, где можно «запутать» N кубитов произвольно — уже есть какое-то понимание… но их нет в природе. А те которые есть — сильно ограничены.
    
    А то эти кванты на АлиЭкспресс уже скоро будут, а как туда OpenGL портировать или как ключи Телеграма подбирать непонятно :)
    До АлиЭкспресс им ещё… долго. Пока мы где-то на уровне ЭНИАКа, никакого ассеблера ещё нет, только машинные коды… причём свои у каждого экземпляра железяки…
    
    kogemrka
    18.07.2017 10:14
    #10316612
    +1
    нельзя ли попросить развить тему. Вот, например, на что похож квантовый ассемблер?
    
    Попробуйте думать не в терминах «ассемблера» а в терминах logic gate'ов.
    Там, где в классической вычислительной модели единички и нолики, здесь состояния кубитов.
    Там, где в классической вычислительной модели простые и понятные гейты и/или/не (и т.д.), здесь свои гейты, из которых можно брать и собирать схему.
    https://en.wikipedia.org/wiki/Quantum_gate
    
    Они сложные, сложнореализуемые сами по себе и не описывают полностью все возможные смены состояний, но, в общем-то, это совершенно естественно, что квантовые компьютеры «непонятные» по сравнению с традиционными.
    
    От квантовых компьютеров ждут, что они будут за полиномиальное время решать некоторые задачи, которые не решаемы в принципе за полиномиальное время на машинах тюринга / не решаемы на схемах из логических элементов полиномиального размера. (ну, насколько известно на данный момент, не решаемы. И при допущении P!=NP, конечно).
    
    Совсем-совсем утрируя: мы хотим за полином делать вещи, которые ни на одном компьютере, ни на одном ассемблере и ни на одном из существующих языков программирования невозможно решать за полином.
    Для этого предлагается использовать некоторую странную хрень. Если бы эту хрень можно было бы взять и очень просто описать традиционными языками программирования — затея была бы абсолютно бесполезной — мы же прямо в условии задачи заявили, что результат по определению своему недостижимым традицонными языками программирования и их вариациями.
    
    А то эти кванты на АлиЭкспресс уже скоро будут,
    
    Скоро не будут.
    
    а как туда OpenGL портировать или как ключи Телеграма подбирать непонятно :)
    
    В математике нет царских путей. Если любопытно, рекомендую книжку quantum computing since democritus (кроме quantum в ней очень много про сложность вычислений вообще относительно простым языком).
    
    merlin-vrn
    18.07.2017 20:44
    #10317960
    Пока никакой идеи нет, как сделать квантовый компьютер с хранимой программой. Проблема в том, что мы не можем просто так «стереть» кубит. Весь компьютер обязан быть обратимым вплоть до редукции, именно редукция необратима.
    
    Потому квантовые примитивные ячейки — 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>, поэтому понятие таблицы истинности для квантового примитива не совсем корректно. Оно заменяется на некий оператор (эти операторы можно довольно просто построить), который действует на это состояние, переводя его в другое состояние, так, чтобы для чистых состояний результат был эквивалентен классической таблице истинности.
    
    А типичная для классических процессоров операция «перезаписи» ячейки памяти по идее, запрещена, т.к. старое значение необратимо теряется. Значит, и регистр в обычном понимании сделать нельзя. Могла бы быть разрешена операция «обмена».
    
    Я не уверен, может быть, уже научились обходить все эти сложности и я устарел.
1. HerrJohan
  17.07.2017 16:26
  #10315864
  Не дискретируйте (или дискретизируйте — так правильно?)
1. sotnikdv
  18.07.2017 02:03
  #10316458
  Да не в кубите дело, точнее не в троичной логике, почему вы все на этом фокусируетесь — мне непонятно. Были уже триты. Квантовый компьютер — это не про количество значений единичного переключателя, это про квантовую запутанность.

BiosUefi
17.07.2017 12:54
#10315452
>может (|0>+|1>)/sqrt(2),
И сколько в том sqrt(2) знаков?
Или не имеет смысла даже интересоваться 1.41 или 1,414213562373? Потому как на результат/значение, не оно влияет?
1. merlin-vrn
  17.07.2017 13:09
  #10315490
  Это состояние так обозначается, "(|0>+|1>)/sqrt(2)". Никто этот корень квадратный не высчиляет. Этот корень — вообще просто нормировочный коэффициент. Могу другое «не-чистое» состояние предложить, в котором не будет корня, например, (|1>+3|0>)/2. В другом базисе эти же состояния могут выражаться вообще без корней и знаменателей. Это просто обозначения.
  
  Редуцируя («передавая в классический компьютер») эти состояния мы получаем их них «0» или «1» с какой-то вероятностью. Например, редуцируя первое состояние мы любой бит получим с одинаковой вероятностью, а редуцируя второе — шансы получить «0» в три раза выше, чем «1». Редукция чистых состояний (|0> и |1>) происходит точно.
  1. Vindicar
    17.07.2017 13:56
    #10315580
    То есть применительно к взлому ключей RSA мы будем получать результат вроде «первый бит ключа 1 с вероятностью 85%», и сможем производить оптимизированный перебор, перебирая в первую очередь наиболее вероятные ключи?
    
    hc4
    17.07.2017 17:26
    #10315972
    -1
    Скорее квантовый алгоритм с какой-то вероятностью вернёт правильный результат (в данном случае порядок функции).
    Если результат будет неправильным, то просто надо провести вычисление повторно. В итоге рано или поздно нам повезет и мы получим правильный ответ :)
    
    alexeykuzmin0
    17.07.2017 19:08
    #10316076
    +1
    Нет, получается не так. Квантовый компьютер может за одну операцию что-то проделать не с числом (как обычный), а с вероятностным распределением (как с математическим объектом: было одно распределение, а после операции стало другое). Например, если мы хотим получить решение какой-нибудь классической задачи (т.е. число), мы можем взять нулевое состояние (|0...0> — такое, которое при измерении с вероятностью 1 выдаст вектор из всех нулей), потом применять к нему какие-нибудь манипуляции, а в конце измерить. И если наши манипуляции таковы, что для одних входных данных мы придем к распределению, всегда выдающему 0, а при других — к всегда выдающему 1, то так мы сможем отличить одно от другого.
    Например, по этой схеме работает алгоритм Дойча. Почитайте вики, там очень хорошее объяснение с примером работы. Да, задача, которую он решает, не слишком применима в реальной жизни, но существуют похожие более сложные алгоритмы для решения реальных задач.
    
    merlin-vrn
    18.07.2017 20:51
    #10317966
    В конечном итоге, результат работы квантового алгоритма непредсказуем. Но это нисколько не похоже на «оптимизированный перебор». Никаких «более вероятных ключей» перебрать нельзя.
    
    Забудьте про перебор, конкретно RSA ломается факторизацией числа, которую алгоритм Шора делает эффективно. Не перебором каких-то там «наиболее вероятных комбинаций», он никак не оценивает вероятность комбинаций. А зная сомножители найти секретный ключ проще простого.
    Если квантовый этап алгоритма Шора не нашёл подходящего значения периода (если мне память не изменяет, вероятность успеха — 2/3), мы это узнаем при проверке, на классическом этапе, и будем перезапускать квантовый этап до тех пор, пока он на найдёт подходящее значение.

chpoklv
17.07.2017 16:26
#10315866
Сможет ли квантовый компьютер взломать биткоин?
1. mikhanoid
  17.07.2017 18:18
  #10316016
  +1
  Сможет, если построят достаточно большой КК (нужно 192 когерентных кубита, а пока IBM говорит, что у них есть 16; и не факт, что есть на самом деле). Но для этого могут быть существенные физические ограничения.
  1. barkalov
    17.07.2017 21:00
    #10316200
    +1
    А расскажите, почему именно 192?
    
    mikhanoid
    17.07.2017 21:14
    #10316226
    Ну, насколько я знаю, если нужно вычислить дискретный логарифм на эллиптической кривой над полем с 384-порядком, требуется проанализировать 2^192 вариантов. Которые, собственно, и надо все «упихать» в когерентное состояние.
    
    dreesh
    25.07.2017 15:01
    #10327204
    Это при наличии публичного ключа, а если мы знаем только номер нужно же будет еще 2 хеша обратить и сколько тогда нужно кубитов?

nikolay_karelin
17.07.2017 18:33
#10316038
Про квантовые алгоритмы говорят уже больше 20 лет, но воз пока и ныне там: слишком сложно работать с кубитами. Хотя апгрейд крипто на более стойкое — это в любом случае полезно.

Lsh
17.07.2017 20:35
#10316168
Что прочитать про квантовый компьютер и кубиты, чтобы придти к полному пониманию как оно работает?
Статьи на википедии не помогли. =) Хотя как работает обычный компьютер понимается прекрасно.
Кубиты физически (как ячейки памяти) что из себя представляют? Как они запутываются/связываются с «соседями»?
1. mikhanoid
  17.07.2017 20:49
  #10316184
  +1
  Китаев А., Шень А., Вялый М. «Классические и квантовые вычисления» — хорошее введение.

Amomum
18.07.2017 02:42
#10316474
-1
Компания Microsoft тоже не осталась в стороне и в 2016 году выпустила библиотеку SIDH(Supersingular Isogeny Key Exchange) с открытым исходным кодом. Одним из преимуществ данной библиотеки является возможность использования эллиптических кривых в форме Монтгомери, которые защищают от атак по времени.

Вау, подумал я. Круто!

SIDH реализована на языке C

Oh wait…

if (CurveIsogeny == NULL) {
Status = CRYPTO_ERROR_NO_MEMORY;
goto cleanup;
}

Ну блин, опять пошло-поехало…

Ivan_83
18.07.2017 14:29
#10317148
+2
Так вопрос как раз в том, что ECDSA падёт раньше нежели старенький RSA, ибо у квантовых компов плохо в кубитами, а у ECDSA разрядность маленькая.
Если взять какое то RSA 16384 то оно продержится на порядки дольше чем ECDSA 521 (хз почему вы там брали бинарные в табличку — они не так распространены как secp).

Статья выглядит как реклама SIDH от мс.
Между тем:
1. кодстайл там традиционный для венды но не для опенсорца
2. куча параметров взятых хз откуда
3. разделение на алису/боба — это маразм какой то: как в п2п определится?
4. кажется жёстко зашитая разрядность под параметры, те мат часть либы не универсальная, да и вообще не уверен что она там нужна была, особенно для патча в OpenSSL
5. В OpenSSL это не взяли

И надо бы посмотреть что говорят эксперты которые в теме, типа DJB и прочих.
А пока, кого беспокоят квантовые компы может нагенерить RSA 16384 и пусть подавятся %)
Правда при этом все криптооперации с такими ключами будут и на компе долго проходить.
Я как то такие ключи в SSH сделал, похоже после этого ботам подбирающим пароли поплохело, да и сам я ждал по несколько секунд, это вам не ECDSA/25519 и рейтом по 3-10к в секунду на ядро.

2 Amomum
А что надо на крестах или ГОмосятине какой писать?
goto тоже нормальная практика для err_out/cleanup потому что 100500 проверок и только одно место для очистки всего сразу.
1. Amomum
  20.07.2017 02:00
  #10320240
  А что надо на крестах или ГОмосятине какой писать?
  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, сдвиги отрицательных чисел влево и черт знает что еще.
  1. Ivan_83
    20.07.2017 10:49
    #10320668
    -2
    Никому кроме рустовцев не нужен код на раст.
    Никому кроме плюсовиков не нужен и не понятен код на крестах.
    …
    Всем понятен си.
    
    Ничего лучше goto не придумано чтобы прыгать на кусок с очисткой ресурсов в случае ошибки.
    Остальное либо увеличивает табуляцию либо копирование портянки с очисткой в каждое место куда можно написать goto, что увеличивает вероятность ошибки по экспоненте и роняет читабельность.
    
    Если ты такой идеалист оторванный от реальности, иди разгребай авгиевы конюшни в том же OpenSSH, потом будешь рассказывать про аккуратность, гото, мисра и прочие мастхэв идеалиста.
    
    Amomum
    20.07.2017 13:29
    #10320946
    +1
    Если ты такой идеалист оторванный от реальности, иди разгребай авгиевы конюшни в том же OpenSSH, потом будешь рассказывать про аккуратность, гото, мисра и прочие мастхэв идеалиста.
    
    А, ну правильно, в openssh конюшни и дальше будем такие же конюшни разводить, прально.
    Конечно, табуляция ведь гораздо важнее чем чистота кода!
    И супер-пупер защищенная от квантовых компьютеров криптография будет за границы массивов выходить. Ну ок, на здоровье.
    
    Ivan_83
    21.07.2017 11:17
    #10322406
    -2
    Твоё мнение никому не интересно, можешь сколько угодно распинаться о том как по твоему надо делать, о розовых пони и прочих галлюцинациях.
    Я же тебе предложил: иди и сделай, покажи как надо — тогда будет о чём подумать, пока ты очередной теоретег.
    
    Реальный код это всегда компромисс между: скоростью работы, потребляемыми ресурсами, временем разработки, безопасностью, читаемостью, соблюдением кодстайла, писаниной тестов и документации и тд.
    
    2 khim
    Не нужны твои плюсы никому, закапывай их.
    Все популярные либы написаны на си, как крипто, так и куча прочих.
    
    Крипта часто в закрытых либах не потому что там какие то лицензии а потому что в либах она сертифицирована, и требования к сертификации распространяются на весь продукт. Сертифицировать крипту самому долго, дорого и нудно.
    
    khim
    21.07.2017 12:41
    #10322580
    +1
    Не нужны твои плюсы никому, закапывай их.
    Серьёзно?
    
    Все популярные либы написаны на си, как крипто, так и куча прочих.
    А когда копилятор, линкер или даже любимый вами OpenSSL переписывают на C++ — эти люди сразу из категории «кто-то» попадают в категорию «никто»?
    
    Ну тогда нормально — скоро весь мир будет там, и «никто» в Ivan-спике будет обозначать «все».
    
    Только зачем это — ума не приложу. Очень хочется получить значок «тролль»? Ну там есть много других способов это сделать.
    
    Ivan_83
    22.07.2017 17:09
    #10323948
    -2
    Это дудль, они там какой только дурью не маятся.
    Конкретно боринг они начали пилить чтобы в хроме не было нашей крипты, потому как раньше они сидели на опенссл, а в него как раз гост втащили, и спустя короткий промежуток времени они под благовидным предлогом форкнули свой унылый боринг.
    Ну и не забывай, что пилят они его чисто для себя, остальным оно не надо.
    
    OpenCV — единственная известная мне либа на плюсах и практически без аналогов на сях.
    И то оно скорее историческое недразумение, ибо в начале её писали на си с классами, а потом было уже поздно.
    
    Если не понятно: клал я с прибором на карму.
    
    2 Amomum
    В каждой теме о крипте появляется нытик который думает точно так же: что крипту должны писать только особенные люди, которых никто никогда не видел, а остальным даже думать об этом низя ибо от этого рождаются фатальные баги.
    
    Имплементация криптоалгоритмов — это работа програмера. Лучше нескольких, которые интересуются темой и лучше чтобы их не сильно торопили и было время на подумать и тесты.
    Криптограф он математик и может вообще не знать ничего кроме своего матлаба/математики(вольфрам)/питона.
    Собственно я точно знаю что Берштейн и Ривест годно кодят на сях.
    
    Про сайтики ты вообще зря начал.
    Сайтик (да и любая прога сложнее обвязки на криптолибой) это стёк технологий, и даже если крипта имплементированна безупречно, то гденить на стыке любого из слоёв может случится факап:
    — дефолтные пароли
    — отсутствие запроса пароля на доступ/открытый сервис/порт голой жопой
    — возможность выполнения произвольного кода: как sql инъекции так и всякие eval() в пхп для входных данных или того хуже всякие переполнения буфера, useafterfree и пр.
    — не ограниченный физический доступ к системе где оно крутится
    
    Скажу больше.
    Даже если яростно говнокодить криптоалгоритмы (речь про имплементацию) то проблемы всё равно вылезут за пределами этого кода, при условии что код вообще правильно работает — тестовые векторы совпадают с результатами.
    Даже тайминг атаки они как бы снаружи, и требуют наличия доступа на исполнение там же или возможность с высоким рейтом неограниченно накидывать рассчётов.
    
    Взлом ECDSA вроед в соньках был связан с тем что они поленились прочитать инструкцию по использованию ECDSA и вместо рандома каждый раз совали константу на подпись.
    Атака на какой то RADIUS сервер была потому что оно после того как посчитало хэш сравнивало его с юзерским хэшем используюя memcmp() а у него скорость работы зависит от входных данных: оно возвращает результат при первом же несовпадении.
    Хеартбет в опенссл, когда там можно было читать память с закрытыми ключами — так оно опять не в крипте, оно в коде TLS который рядом.
    
    Amomum
    21.07.2017 13:01
    #10322636
    Твоё мнение никому не интересно, можешь сколько угодно распинаться о том как по твоему надо делать, о розовых пони и прочих галлюцинациях.
    Я же тебе предложил: иди и сделай, покажи как надо — тогда будет о чём подумать, пока ты очередной теоретег.
    
    Мне кажется, что вы грубите мне несколько необоснованно. И откуда вы знаете, кому мое мнение интересно, а кому нет? Поэтому говорите, пожалуйста, только за себя.
    
    Я не криптограф и не считаю себя достаточно квалифицированным специалистом, чтобы писать криптографические библиотеки. Однако это не мешает мне чувствовать code smell.
    
    Реальный код это всегда компромисс между: скоростью работы, потребляемыми ресурсами, временем разработки, безопасностью, читаемостью, соблюдением кодстайла, писаниной тестов и документации и тд.
    
    Это утверждение верно. Но в зависимости от области применения этого кода компромисс достигается в разных точках. Сайтик в интернете для 10 друзей можно делать как угодно, но от кода в медицинской или автомобильной технике зависят человеческие жизни! И там надежность играет (или, по крайней мере, должна играть) несколько большую роль, чем количество табуляций или скорость разработки. От криптографии зависят приватность и очень чувствительные данные людей, а иногда и жизнь/свобода.
    
    А вообще, толстовато, уважаемый, толстовато.
    
    khim
    20.07.2017 17:10
    #10321384
    +2
    Ничего лучше goto не придумано чтобы прыгать на кусок с очисткой ресурсов в случае ошибки.
    Не нужно никуда прыгать. Очистка ресурсов осуществляется в деструкторах в C++ — и все довольны.
    
    Если ты такой идеалист оторванный от реальности, иди разгребай авгиевы конюшни в том же OpenSSH
    Тот факт, что из-за юридических проблем криптография в большинстве программ выполняется через библиотеку состоящую почти полностью из антипаттернов не означает, что «так и надо». Просто изменить это тяжело — и, к сожалению, не по техническим причинам.

32seph
21.07.2017 00:31
#10321990
NWOcs,
Для того, чтобы решить задачу дискретного логарифмирования,… необходимо вычислить порядок другой функции, а именно: f(x1,x2)=g^x1*g^x2

А можно подробнее, про эту функцию и почему ее период поможет в нахождении k? x1 и x2 это любые числа или как-то связанные с k?
1. NWOcs
  21.07.2017 01:39
  #10322060
  Если функция f(x1,x2) имеет вид: f(x1,x2)=g^(x1)y^(x2), то, сведя все к одному основанию, получаем: f(x1, x2)=g^(x1+k*x2). Алгоритм Шора находит периоды w1 и w2 этой функции, для которых значения функции начинают повторяться: f(x1,x2)=g^(x1+k*x2)=f(x1+w1, x2+w2)=g^(x1+w1+k(x2+w2)).
  Это возможно, когда g^(w1+k*w2)=1 или w1+k*w2=0(mod q). Таким образом, зная значения периодов w1 и w2, можно найти k=-w1/w2.
  Числа x1 и x2, таким образом, не связаны с числом k.

NWOcs
21.07.2017 01:02
#10322034
Просим прощения, обнаружили опечатку, функция f(x1,x2) имеет вид: f(x1,x2)=g^(x1)y^(x2)

iioufo
21.07.2017 01:04
#10322038
-2
Если кот Шредингера одновременно и жив и мертв, а кубит одновременно 0 и 1, то и информация получается одновременно зашифрована и нет?
1. NWOcs
  21.07.2017 01:54
  #10322066
  +1
  Приведенный в статье алгоритм шифрования не использует какие-либо свойства квантовых объектов для реализации зашифрования, то есть все операции проводятся на обычном компьютере, а сама информация может находиться либо в зашифрованном состоянии, либо в незашифрованном.
  Алгоритм Шора, как уже было сказано, направлен на получение данных, позволяющих найти закрытый ключ, с помощью которого и можно однозначно произвести расшифрование информации на обычном компьютере.
  Однако уже существует и другое направление в криптографии под названием квантовая криптография. Ее отличие от постквантовой криптографии состоит в том, что здесь как раз для защиты информации используются принципы квантовой физики.
1. merlin-vrn
  21.07.2017 09:15
  #10322238
  +1
  Кубит не «одновременно 0 и 1». Кот Шредингера не «одновременно жив и мёртв». Это бред. Никакая система в нескольких состояниях одновременно находиться не может.
  
  Кубит в состоянии, которое в некотором роде является промежуточным межу 0 и 1. Он не находится одновременно в нескольких состоянии, состояние у него одно и вполне конкретное, однозначное и существующее. Оно является линейной комбинацией |0> и |1>. В реальной физической реализации кубита |0> и |1> можно придать гораздо менее абстрактный вид, типа состояний электрона в атоме, занимающих конкретные уровни энергии системы.
  
  Кот Шрёдингера тоже находится в совершенно однозначном, конкретном состоянии, являющимся линейной комбинацией «жив» и «мёртв».
  
  Вот это настоящее состояние, хоть и существует, определено в таком конфигурационном пространстве, которое непредставимо в реальном мире и не может возникнуть в качестве результата измерения. Измерения могут дать только вещественные положительные значения. Поэтому, при попытке узнать состояние объекта происходит изменение этого состояния, этот процесс называется редукцией. Старое состояние необратимо искажается, восстановить его нельзя (редукция — необратимый процесс). Оно переходит в одно из возможных измеримых состояний, которые были составляющими актуального состояния. Таким образом, для кубита мы получим 0 или 1, и вероятность получения одного из них зависит от того, в каком состоянии находился кубит. Если у нас был дву-кубит в состоянии (|11>+|00>)/sqrt(2) мы в результате редукции получим с одинаковой вероятности 00 или 11 и никогда 01 или 10, т.к. они не являлись составляющими исходного состояния. И кот именно при измерении переходит в жив или мёртв, и вероятность одного из исходов зависит от того, в каком состоянии он находился.
  
  Если для системы выполняется эргодическая гипотеза и мы имеем технологию, как исходное состояние готовить в точности одинаково неограниченное количество раз, мы можем попробовать создать статистику и получить матрицу распределения вероятностей исходного состояния, т.е. узнать про него чуть побольше. Это максимум информации, который в принципе возможно получить о состоянии квантовой системы.
  
  Именно свойство необратимости процесса редукции и используется для «квантовой криптографии».