Влияние квантовых вычислений на нынешнюю криптографию
От: kochetkov.vladimir Россия https://kochetkov.github.io
Дата: 19.04.17 21:03
Оценка: 8 (2)
Таблица, показывающая, на сколько энтропийных попугаев снизится уровень защищённости нынешних криптографических алгоритмов в случае появления квантовых компьютеров достаточной мощности:

... << RSDN@Home 1.0.0 alpha 5 rev. 0>>

[Интервью] .NET Security — это просто
Автор: kochetkov.vladimir
Дата: 07.11.17
Re: Влияние квантовых вычислений на нынешнюю криптографию
От: BurningInside Россия  
Дата: 19.04.17 21:32
Оценка:
Здравствуйте, kochetkov.vladimir, Вы писали:

KV>Таблица, показывающая, на сколько энтропийных попугаев снизится уровень защищённости нынешних криптографических алгоритмов в случае появления квантовых компьютеров достаточной мощности:


KV>[_url=https://pbs.twimg.com/media/C9y1hEnWAAAI3zj.jpg:large]Image: large[/url]


Что значит "Grover"?
Re[2]: Влияние квантовых вычислений на нынешнюю криптографию
От: · Великобритания  
Дата: 19.04.17 21:42
Оценка: +1
Здравствуйте, BurningInside, Вы писали:

BI> KV>Таблица, показывающая, на сколько энтропийных попугаев снизится уровень

BI> Что значит "Grover"?
https://en.wikipedia.org/wiki/Grover%27s_algorithm
Ну и
https://en.wikipedia.org/wiki/Shor%27s_algorithm
avalon/2.0.1
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re: Влияние квантовых вычислений на нынешнюю криптографию
От: SkyDance Земля  
Дата: 19.04.17 22:32
Оценка:
KV>Таблица, показывающая, на сколько энтропийных попугаев снизится уровень защищённости нынешних криптографических алгоритмов в случае появления квантовых компьютеров достаточной мощности:

То есть весь PKI, основанный на RSA et al, можно будет выкинуть. Удачно, что уж тут. Это ж как бы весь интернет...
Re[2]: Влияние квантовых вычислений на нынешнюю криптографию
От: kochetkov.vladimir Россия https://kochetkov.github.io
Дата: 19.04.17 22:42
Оценка: +1
Здравствуйте, SkyDance, Вы писали:

SD>То есть весь PKI, основанный на RSA et al, можно будет выкинуть. Удачно, что уж тут. Это ж как бы весь интернет...


Ну во-первых, предпосылок к тому, что квантовые компьютеры достаточной мощности появятся в обозримом будущем пока нет. Во-вторых -- длину ключей увеличат и всего делов-то. А за выигранное время перейдут на пост-квантовые алгоритмы (десятки их уже сейчас). В третьих, у меня лёгкое дежавю, что мы это уже где-то здесь обсуждали =/

[Интервью] .NET Security — это просто
Автор: kochetkov.vladimir
Дата: 07.11.17
Re[3]: Влияние квантовых вычислений на нынешнюю криптографию
От: SkyDance Земля  
Дата: 19.04.17 23:24
Оценка:
KV> В третьих, у меня лёгкое дежавю, что мы это уже где-то здесь обсуждали =/

Вот и у меня тоже... но никак не пойму, я на RSDN такие вещи обычно не обсуждаю. А дежавю тоже есть.
Re[3]: Влияние квантовых вычислений на нынешнюю криптографию
От: DOOM Россия  
Дата: 20.04.17 10:12
Оценка: 3 (1) +1
Здравствуйте, kochetkov.vladimir, Вы писали:

KV>Во-вторых -- длину ключей увеличат и всего делов-то.

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

А вот дискретный логарифм устоит — поэтому эллиптические кривые наше все.
Re[2]: Влияние квантовых вычислений на нынешнюю криптографию
От: jazzer Россия Skype: enerjazzer
Дата: 20.04.17 14:32
Оценка:
Здравствуйте, SkyDance, Вы писали:

KV>>Таблица, показывающая, на сколько энтропийных попугаев снизится уровень защищённости нынешних криптографических алгоритмов в случае появления квантовых компьютеров достаточной мощности:


SD>То есть весь PKI, основанный на RSA et al, можно будет выкинуть. Удачно, что уж тут. Это ж как бы весь интернет...


The Blight
jazzer (Skype: enerjazzer) Ночная тема для RSDN
Автор: jazzer
Дата: 26.11.09

You will always get what you always got
  If you always do  what you always did
Re: Влияние квантовых вычислений на нынешнюю криптографию
От: Voblin Россия http://maslyaew.narod.ru/
Дата: 20.04.17 16:37
Оценка: 3 (1)
Здравствуйте, kochetkov.vladimir, Вы писали:

KV>Таблица, показывающая, на сколько энтропийных попугаев снизится уровень защищённости нынешних криптографических алгоритмов в случае появления квантовых компьютеров достаточной мощности:

KV>[картинка]

Знающие люди говорят (ссылку не спрашивайте, я её не помню, за что купил, за то и продаю), что разложение 15 на 3 и 5 в 2001-м было и останется первым и последним успешным применением Шора. Говорят, что где-то там в мягком подбрюшье квантовой реальности есть какая-то затыка, которая не даёт родить что-нибудь поинтереснее.

Я бы лучше боялся не квантового компьютера, а какой-нибудь секретной теоремы. Впрочем, даже если таковая есть у Больших наших Братьев, то горя нам от того тоже не очень много. Ради поимки блогера, репостнувшего картинку, они сей факт светить не станут. Нужно творить нечто совсем инфернальное мирового масштаба, чтобы ББ рискнул целостностью своего самого сокровенного секрета.

Реальное западло — это если секретная теорема уйдёт в широкие массы или будет переоткрыта каким-нибудь балбесом. Тут уж, конечно, мало никому не покажется.
Re[2]: Влияние квантовых вычислений на нынешнюю криптографию
От: · Великобритания  
Дата: 20.04.17 21:16
Оценка:
Здравствуйте, Voblin, Вы писали:

V> KV>Таблица, показывающая, на сколько энтропийных попугаев снизится уровень защищённости нынешних криптографических алгоритмов в случае появления квантовых компьютеров достаточной мощности:

V> KV>[картинка]

V> Знающие люди говорят (ссылку не спрашивайте, я её не помню, за что купил, за то и продаю), что разложение 15 на 3 и 5 в 2001-м было и останется первым и последним успешным применением Шора. Говорят, что где-то там в мягком подбрюшье квантовой реальности есть какая-то затыка, которая не даёт родить что-нибудь поинтереснее.

Вики говорит, что Also in 2012, the factorization of 21 was achieved, setting the record for the largest number factored with Shor's algorithm.
И даже что In November 2014, it was discovered that this 2012 adiabatic quantum computation had also factored larger numbers, the largest being 56153.
Но я не очень понимаю чем именно адиабатические квантовые вычислители "хуже". Кто-нибудь может на пальцах объяснить?
avalon/2.0.1
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[4]: Влияние квантовых вычислений на нынешнюю криптографию
От: · Великобритания  
Дата: 20.04.17 21:19
Оценка:
Здравствуйте, DOOM, Вы писали:

DOO> KV>Во-вторых -- длину ключей увеличат и всего делов-то.

DOO> Не все так просто. RSA не спасет длина ключа, так как факторизация числа на квантовом компьютере решается за полиномиальное время, а не за экспоненту.
DOO> А вот дискретный логарифм устоит — поэтому эллиптические кривые наше все.
В табличке ECDH/ECDSA тоже есть — это разве не они?
avalon/2.0.1
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[2]: Влияние квантовых вычислений на нынешнюю криптографию
От: Cyberax Марс  
Дата: 20.04.17 21:23
Оценка: +1
Здравствуйте, Voblin, Вы писали:

V>Знающие люди говорят (ссылку не спрашивайте, я её не помню, за что купил, за то и продаю), что разложение 15 на 3 и 5 в 2001-м было и останется первым и последним успешным применением Шора. Говорят, что где-то там в мягком подбрюшье квантовой реальности есть какая-то затыка, которая не даёт родить что-нибудь поинтереснее.

Проблема чисто в том, что нет практических квантовых компьютеров. С теорией там всё просто.
Sapienti sat!
Re[4]: Влияние квантовых вычислений на нынешнюю криптографию
От: kochetkov.vladimir Россия https://kochetkov.github.io
Дата: 21.04.17 01:00
Оценка:
Здравствуйте, DOOM, Вы писали:

DOO>Не все так просто. RSA не спасет длина ключа, так как факторизация числа на квантовом компьютере решается за полиномиальное время, а не за экспоненту.

DOO>А вот дискретный логарифм устоит — поэтому эллиптические кривые наше все.

Что-то мне подсказывает, что к тому моменту, когда будут (если вообще будут) созданы подходящие квантовые компьютеры, минимальная длина ключей RSA будет настолько конской, что пользоваться ими уже никто не будет.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>

[Интервью] .NET Security — это просто
Автор: kochetkov.vladimir
Дата: 07.11.17
Re[5]: Влияние квантовых вычислений на нынешнюю криптографию
От: DOOM Россия  
Дата: 21.04.17 09:04
Оценка:
Здравствуйте, ·, Вы писали:

DOO>> А вот дискретный логарифм устоит — поэтому эллиптические кривые наше все.

·>В табличке ECDH/ECDSA тоже есть — это разве не они?
Тоже смутило. Может там какая-то реализация неполная? Мы в универе рассматривали честный вариант с дискретным логарифмом — там факторизация за полином никак не помогает.
Re[6]: Влияние квантовых вычислений на нынешнюю криптографию
От: · Великобритания  
Дата: 21.04.17 09:14
Оценка:
Здравствуйте, DOOM, Вы писали:

DOO>>> А вот дискретный логарифм устоит — поэтому эллиптические кривые наше все.

DOO>·>В табличке ECDH/ECDSA тоже есть — это разве не они?
DOO>Тоже смутило. Может там какая-то реализация неполная? Мы в универе рассматривали честный вариант с дискретным логарифмом — там факторизация за полином никак не помогает.
Ну просто немного другой алгоритм "взлома", квантовый компьютер же не только факторизацию уметь может. А тут вообще пишут, что EC вероято быстрее сломается квантовыми вычислениями, т.к. размер ключа меньше, а значит потребуется меньше кубит, а значит технически проще построить сам к-компьютер.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[2]: Влияние квантовых вычислений на нынешнюю криптографию
От: Ops Россия  
Дата: 21.04.17 09:49
Оценка:
Здравствуйте, Voblin, Вы писали:

V>Впрочем, даже если таковая есть у Больших наших Братьев, то горя нам от того тоже не очень много. Ради поимки блогера, репостнувшего картинку, они сей факт светить не станут.


А зачем что-то светить? Когда ключ подобран, этого уже достаточно, а как это сделали, с помощью теоремы, шпионского ПО, или паяльника, сообщать не обязательно.
Переубедить Вас, к сожалению, мне не удастся, поэтому сразу перейду к оскорблениям.
Re[5]: Влияние квантовых вычислений на нынешнюю криптографию
От: Sharov Россия  
Дата: 21.04.17 17:51
Оценка:
Здравствуйте, kochetkov.vladimir, Вы писали:

KV>Что-то мне подсказывает, что к тому моменту, когда будут (если вообще будут) созданы подходящие квантовые компьютеры, минимальная длина ключей RSA будет настолько конской, что пользоваться ими уже никто не будет.


В чем проблема с длиной ключа? Ну будут фигачить на asic'ах и GPU.
Кодом людям нужно помогать!
Re: Влияние квантовых вычислений на нынешнюю криптографию
От: Gattaka Россия  
Дата: 04.05.17 08:36
Оценка:
Здравствуйте, kochetkov.vladimir, Вы писали:

KV>Таблица, показывающая, на сколько энтропийных попугаев снизится уровень защищённости нынешних криптографических алгоритмов в случае появления квантовых компьютеров достаточной мощности:

KV>Image: large

А что насчет гостовых алгоритмов?
Re[2]: Влияние квантовых вычислений на нынешнюю криптографию
От: · Великобритания  
Дата: 04.05.17 10:48
Оценка:
Здравствуйте, Gattaka, Вы писали:

KV>>Таблица, показывающая, на сколько энтропийных попугаев снизится уровень защищённости нынешних криптографических алгоритмов в случае появления квантовых компьютеров достаточной мощности:

KV>>Image: large
G>А что насчет гостовых алгоритмов?
Гостовые алгоритмы — эллиптические, которые ломаются
Автор: ·
Дата: 21.04.17
даже чуть проще.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[3]: Влияние квантовых вычислений на нынешнюю криптографию
От: Gattaka Россия  
Дата: 04.05.17 11:17
Оценка:
Здравствуйте, ·, Вы писали:

·>Гостовые алгоритмы — эллиптические, которые ломаются
Автор: ·
Дата: 21.04.17
даже чуть проще.


Ну так гост он ведь не только асимметричный. Есть еще симметрия, интересно как там дело обстоит. И опять же старый и новый ГОСТ — есть ли в этом плане разница.
Re[6]: Влияние квантовых вычислений на нынешнюю криптографию
От: kochetkov.vladimir Россия https://kochetkov.github.io
Дата: 08.05.17 10:16
Оценка:
Здравствуйте, Sharov, Вы писали:
S>Здравствуйте, kochetkov.vladimir, Вы писали:

KV>>Что-то мне подсказывает, что к тому моменту, когда будут (если вообще будут) созданы подходящие квантовые компьютеры, минимальная длина ключей RSA будет настолько конской, что пользоваться ими уже никто не будет.

S>В чем проблема с длиной ключа? Ну будут фигачить на asic'ах и GPU.

А смысл продолжать фигачить алгоритмы, уже требующие GPU, если есть менее требовательные альтернативы?
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>

[Интервью] .NET Security — это просто
Автор: kochetkov.vladimir
Дата: 07.11.17
Re[4]: Влияние квантовых вычислений на нынешнюю криптографию
От: kochetkov.vladimir Россия https://kochetkov.github.io
Дата: 08.05.17 10:16
Оценка: 1 (1)
Здравствуйте, Gattaka, Вы писали:

G>Ну так гост он ведь не только асимметричный. Есть еще симметрия, интересно как там дело обстоит. И опять же старый и новый ГОСТ — есть ли в этом плане разница.


И в Кузнечике, и в Магме -- внутри сеть Фейстеля. Для неё вроде показали экспоненту эффективности атаки то-ли Саймоном, то-ли Шором. Правда сходу, соответствующей публикации не нашёл.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>

[Интервью] .NET Security — это просто
Автор: kochetkov.vladimir
Дата: 07.11.17
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.