Квантовая криптография

Сообщение №32241 от epros 10 марта 2004 г. 14:07
Тема: Квантовая криптография

Здесь статья на CNews про субж.

Кто-нибудь знает, что это за зверь?


Отклики на это сообщение:

> Здесь статья на CNews про субж.

> Кто-нибудь знает, что это за зверь?

В сети много информации.Напр., неплохо ЗДЕСЬ


> Здесь статья на CNews про субж.

> Кто-нибудь знает, что это за зверь?

Это такая же лажа, как и квантовые компьютеры.
Средство получения грантов.


> В сети много информации.Напр., неплохо ЗДЕСЬ

Глубоко пока въехать не успел, но, кажется, речь идет всего лишь о способе безопасной передачи ключа. В связи с этим сразу возникает вопрос: "А как же алгоритмы с открытыми ключами?", на который тут же в первом абзаце видим странный ответ: "Степень надежности в данной методике выше, чем в случае применения алгоритмов с парными ключами (например, RSA)".

А какие-такие проблемы с надежностью у алгоритмов с парными ключами? Насколько я знаю, здесь надежность определяется только вычислительной сложностью крипто-аналитической задачи, т.е. сводится к чистой математике. Причем эту сложность легко можно сделать гораздо выше, чем требуется для раскрытия самогО передаваемого симметричного ключа. В то время как в этой "квантовой криптографии", похоже, надежность полностью определяется техникой.

Странно все это как-то.


> > В сети много информации.Напр., неплохо ЗДЕСЬ

> Глубоко пока въехать не успел, но, кажется, речь идет всего лишь о способе безопасной передачи ключа. В связи с этим сразу возникает вопрос: "А как же алгоритмы с открытыми ключами?", на который тут же в первом абзаце видим странный ответ: "Степень надежности в данной методике выше, чем в случае применения алгоритмов с парными ключами (например, RSA)".

> А какие-такие проблемы с надежностью у алгоритмов с парными ключами? Насколько я знаю, здесь надежность определяется только вычислительной сложностью крипто-аналитической задачи, т.е. сводится к чистой математике. Причем эту сложность легко можно сделать гораздо выше, чем требуется для раскрытия самогО передаваемого симметричного ключа. В то время как в этой "квантовой криптографии", похоже, надежность полностью определяется техникой.

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

> Странно все это как-то.


> Напр., с помощью квантовой криптографии в той же системе RSA можно периодически менять закрытый ключ, оставляя неизменным открытый.

Смена закрытого ключа без открытого невозможна, да и не нужна. Невозможна - потому что ключи в паре между собой жестко связаны. Не нужна - потому что если нам нужно сменить закрытый ключ, то нет проблемы вместе с ним сменить и открытый. Нужно просто сертифицировать новый открытый ключ в Certifacate Authority. Если сертификатор находится далеко, то запрос на сертификацию нового ключа может быть подписан с помощью старого.

Зачем тут изощряться на предмет какой-то дополнительной защиты при передаче ключей, я не очень понимаю.


> > Напр., с помощью квантовой криптографии в той же системе RSA можно периодически менять закрытый ключ, оставляя неизменным открытый.

> Смена закрытого ключа без открытого невозможна, да и не нужна. Невозможна - потому что ключи в паре между собой жестко связаны. Не нужна - потому что если нам нужно сменить закрытый ключ, то нет проблемы вместе с ним сменить и открытый. Нужно просто сертифицировать новый открытый ключ в Certifacate Authority. Если сертификатор находится далеко, то запрос на сертификацию нового ключа может быть подписан с помощью старого.

Да, так я хорошо выразился... Естественно, открытый ключ меняется, но изменять открытый ключ можно без всяких ухищрений. Т.е. открытый ключ остается открытым.

> Зачем тут изощряться на предмет какой-то дополнительной защиты при передаче ключей, я не очень понимаю.

Не знаю. Интересно было бы поговорить с профи.


> > Напр., с помощью квантовой криптографии в той же системе RSA можно периодически менять закрытый ключ, оставляя неизменным открытый.

> Смена закрытого ключа без открытого невозможна, да и не нужна. Невозможна - потому что ключи в паре между собой жестко связаны. Не нужна - потому что если нам нужно сменить закрытый ключ, то нет проблемы вместе с ним сменить и открытый. Нужно просто сертифицировать новый открытый ключ в Certifacate Authority. Если сертификатор находится далеко, то запрос на сертификацию нового ключа может быть подписан с помощью старого.

А кто является гарантом того, что нет алгоритма быстрого построения закрытого
ключа по открытому? Вы, Господь Бог или "такой алгоритм не известен, а значит
и невозможен"?

> Зачем тут изощряться на предмет какой-то дополнительной защиты при передаче ключей, я не очень понимаю.


> А кто является гарантом того, что нет алгоритма быстрого построения закрытого ключа по открытому? Вы, Господь Бог или "такой алгоритм не известен, а значит и невозможен"?

Все гарантии, которые есть, содержатся в науке криптографии (есть такой раздел математики). Она утверждает, что задача нахождения закрытого ключа по открытому имеет более чем полиномиальную сложность. Других гарантий, тем более "божественного" плана, конечно, нет. Если математики докажут сводимость задач неполиномиальной сложности к задачам полиномиальной сложности, то все криптоалгоритмы, несомненно, будут взломаны. Но такая возможность весьма сомнительна даже в очень отдаленной перспективе, а пока что на криптоалгоритмы можно положиться. По-моему, гораздо естественнее ожидать прорех в технике, обеспечивающей безопасность канала "квантовой криптографии".


> > А кто является гарантом того, что нет алгоритма быстрого построения закрытого ключа по открытому? Вы, Господь Бог или "такой алгоритм не известен, а значит и невозможен"?

> Все гарантии, которые есть, содержатся в науке криптографии (есть такой раздел математики). Она утверждает, что задача нахождения закрытого ключа по открытому имеет более чем полиномиальную сложность. Других гарантий, тем более "божественного" плана, конечно, нет. Если математики докажут сводимость задач неполиномиальной сложности к задачам полиномиальной сложности, то все криптоалгоритмы, несомненно, будут взломаны. Но такая возможность весьма сомнительна даже в очень отдаленной перспективе, а пока что на криптоалгоритмы можно положиться. По-моему, гораздо естественнее ожидать прорех в технике, обеспечивающей безопасность канала "квантовой криптографии".

Значит третий вариант. Тогда ответ такой - похоже не всех устраивают такие
гарантии и некоторым хочется гарантий по второму варианту. А получится или
нет - покажет время.


> > > А кто является гарантом того, что нет алгоритма быстрого построения закрытого ключа по открытому? Вы, Господь Бог или "такой алгоритм не известен, а значит и невозможен"?

> > Все гарантии, которые есть, содержатся в науке криптографии (есть такой раздел математики). Она утверждает, что задача нахождения закрытого ключа по открытому имеет более чем полиномиальную сложность. Других гарантий, тем более "божественного" плана, конечно, нет. Если математики докажут сводимость задач неполиномиальной сложности к задачам полиномиальной сложности, то все криптоалгоритмы, несомненно, будут взломаны. Но такая возможность весьма сомнительна даже в очень отдаленной перспективе, а пока что на криптоалгоритмы можно положиться. По-моему, гораздо естественнее ожидать прорех в технике, обеспечивающей безопасность канала "квантовой криптографии".

> Значит третий вариант. Тогда ответ такой - похоже не всех устраивают такие гарантии и некоторым хочется гарантий по второму варианту. А получится или нет - покажет время.

А в роли Господа Бога, стало быть, должна выступать квантовая механика? Забавно. Скажем, если я случайным образом загадываю число от одного до миллиона, то я полагаю, что для того, чтобы его угадать, злоумышленнику потребуются сотни тысяч попыток. Но чисто фантастически я могу допустить, что появится некий индивид, обладающий чудесными способностями угадывать числа с первой попытки. Как это в принципе возможно, я себе даже представить не могу. Но кто его знает, какие на свете возможны чудеса? Так вот, оказывается, этого чисто фантастического предположения достаточно для того, чтобы некто посчитал мой способ загадывания чисел "недостаточно надежным" и принялся искать "божественные гарантии" в квантовой механике или еще в каком-либо ЧЕЛОВЕЧЕСКОМ (а значит небесспорном) изобретении?


> > Значит третий вариант. Тогда ответ такой - похоже не всех устраивают такие гарантии и некоторым хочется гарантий по второму варианту. А получится или нет - покажет время.

> А в роли Господа Бога, стало быть, должна выступать квантовая механика? Забавно. Скажем, если я случайным образом загадываю число от одного до миллиона, то я полагаю, что для того, чтобы его угадать, злоумышленнику потребуются сотни тысяч попыток. Но чисто фантастически я могу допустить, что появится некий индивид, обладающий чудесными способностями угадывать числа с первой попытки. Как это в принципе возможно, я себе даже представить не могу. Но кто его знает, какие на свете возможны чудеса? Так вот, оказывается, этого чисто фантастического предположения достаточно для того, чтобы некто посчитал мой способ загадывания чисел "недостаточно надежным" и принялся искать "божественные гарантии" в квантовой механике или еще в каком-либо ЧЕЛОВЕЧЕСКОМ (а значит небесспорном) изобретении?

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


> Не понял. При расшифровке закрытым ключем текста, зашифрованного открытым ключем происходит угадывание чисел? Разве результат не однозначен?

Для расшифровки нужно знать закрытый ключ (который я в свое время загадал). Если знаете, то результат однозначен (я - знаю, поскольку я его и загадал). Если не знаете, то его нужно сначала угадать. Открытый ключ в этом не поможет.

> И, разве не возможна в принципе расшифровка с помощью открытого ключа? И тоже однозначная? Вы о чем?

Что значит "возможна в принципе"? В принципе возможно перепробовать подряд все возможные закрытые ключи и найти подходящий к данному открытому ключу или к данному зашфрованному сообщению (без разницы). Вопрос только в том, сколько ресурсов это потребует. Так что от знания открытого ключа никакой особой "помощи" не будет.

> А утверждение, что перехват сообщения в квантовой криптогграфии невозможен в принципе - это не означает, что перехват не возможен никогда и ни при каких затратах?

Что значит "никогда и ни при каких затратах"? Когда-нибудь при каких-нибудь затратах может быть удастся доработать квантовую механику таким образом, что перехват станет возможным. Где гарантии против этого? Вы, Господь Бог или что у Вас там третье?


> > Не понял. При расшифровке закрытым ключем текста, зашифрованного открытым ключем происходит угадывание чисел? Разве результат не однозначен?

> Для расшифровки нужно знать закрытый ключ (который я в свое время загадал). Если знаете, то результат однозначен (я - знаю, поскольку я его и загадал). Если не знаете, то его нужно сначала угадать. Открытый ключ в этом не поможет.

Разве? А вычислить закрытый ключ по открытому никак нельзя?

> > И, разве не возможна в принципе расшифровка с помощью открытого ключа? И тоже однозначная? Вы о чем?

> Что значит "возможна в принципе"? В принципе возможно перепробовать подряд все возможные закрытые ключи и найти подходящий к данному открытому ключу или к данному зашфрованному сообщению (без разницы). Вопрос только в том, сколько ресурсов это потребует. Так что от знания открытого ключа никакой особой "помощи" не будет.

Можно и перебором. А может есть алгоритм, который делает это за приемлимое время.


> > А утверждение, что перехват сообщения в квантовой криптогграфии невозможен в принципе - это не означает, что перехват не возможен никогда и ни при каких затратах?

> Что значит "никогда и ни при каких затратах"? Когда-нибудь при каких-нибудь затратах может быть удастся доработать квантовую механику таким образом, что перехват станет возможным. Где гарантии против этого? Вы, Господь Бог или что у Вас там третье?

Это как? На время отменяем иммитацию объективной реальности, подглядываем куда
надо, затем снова включаем иммитацию?
А с открытым/закрытым ключами такое же проделать нельзя?


> > Что значит "возможна в принципе"? В принципе возможно перепробовать подряд все возможные закрытые ключи и найти подходящий к данному открытому ключу или к данному зашфрованному сообщению (без разницы). Вопрос только в том, сколько ресурсов это потребует. Так что от знания открытого ключа никакой особой "помощи" не будет.

> Можно и перебором. А может есть алгоритм, который делает это за приемлимое время.

Пока для RSA-кодов такого алгоритма нет. Впрочем, лучше с этим вопросом на форум по математике выйти.


> Разве? А вычислить закрытый ключ по открытому никак нельзя?

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

> Можно и перебором. А может есть алгоритм, который делает это за приемлимое время.

А может есть способ угадывать случайные числа... Но вообще-то в математике пока не предвидится хоть какой-то прогресс в области уменьшения сложности такого рода задач.

> > Где гарантии против этого? Вы, Господь Бог или что у Вас там третье?

И все таки, какой из трех вариантов?

> Это как? На время отменяем иммитацию объективной реальности, подглядываем куда надо, затем снова включаем иммитацию?

Что за иммитация? Это Вы про квантовую механику? Так это всего лишь теория. Теории как разрабатываются, так и дорабатываются или опровергаются со временем.

> А с открытым/закрытым ключами такое же проделать нельзя?

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


> > Можно и перебором. А может есть алгоритм, который делает это за приемлимое время.

> Пока для RSA-кодов такого алгоритма нет. Впрочем, лучше с этим вопросом на форум по математике выйти.

Пока такой алгоритм неизвестен ( публично ). Но доказательства, что такой
алгоритм в принципе невозможен, нет.


> > Разве? А вычислить закрытый ключ по открытому никак нельзя?

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

По фрагменту? Не зная ничего об исходном тексте? А что тогда подбирать?
А вот по открытому ключу есть чего вычислять ( не обязательно перебором ).

> > Можно и перебором. А может есть алгоритм, который делает это за приемлимое время.

> А может есть способ угадывать случайные числа... Но вообще-то в математике пока не предвидится хоть какой-то прогресс в области уменьшения сложности такого рода задач.

Опять Вы про случайные числа. Разве кто спорит, что в области угадывания
"пока не предвидится хоть какой-то прогресс в области уменьшения сложности такого рода задач." Но при чем здесь угадывание?


> > Это как? На время отменяем иммитацию объективной реальности, подглядываем куда надо, затем снова включаем иммитацию?

> Что за иммитация? Это Вы про квантовую механику? Так это всего лишь теория. Теории как разрабатываются, так и дорабатываются или опровергаются со временем.

Не, я про отсутствие объективной реальности. Если она ( объективная реальность )
иммитируется сознанием, тогда все возможно при условии, что иммитацию можно
на время отменять. Иначе, увы, есть объективные законы.

> > А с открытым/закрытым ключами такое же проделать нельзя?

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

А кто спорит. Предмет обсуждения ведь пока в стадии разработки. И вопрос вроде
был - а надо ли вообще его разработкой заниматься.


> Не, я про отсутствие объективной реальности. Если она ( объективная реальность )
> иммитируется сознанием, тогда все возможно при условии, что иммитацию можно
> на время отменять. Иначе, увы, есть объективные законы.

Vallav, Вы серьёзно полагаете, что все (в частности математические) истины существуют где-то независимо от сознания? То ли в "мире идей" Платона, то ли в "Абсолютном духе" Гегеля... Вы, впрочем, предпочитаете называть это "объективной реальностью".
Такой способ мыслить кажется самоочевидным. Вероятно поэтому он очень давен (наверняка и до Платона существовал). Однако у него есть множество уязвимых мест. Подробно их расписывать здесь не буду, ибо оффтопик. Укажу на два главных: (а) бездоказательность (б) бесполезность.


> > Не, я про отсутствие объективной реальности. Если она ( объективная реальность )
> > иммитируется сознанием, тогда все возможно при условии, что иммитацию можно
> > на время отменять. Иначе, увы, есть объективные законы.

> Vallav, Вы серьёзно полагаете, что все (в частности математические) истины существуют где-то независимо от сознания?

Не, полагаю, что истины в сознании существуют только в сознании. Но моделируют
объективную реальность, а не ее иммитацию сознанием.

> То ли в "мире идей" Платона, то ли в "Абсолютном духе" Гегеля... Вы, впрочем, предпочитаете называть это "объективной реальностью".
> Такой способ мыслить кажется самоочевидным. Вероятно поэтому он очень давен (наверняка и до Платона существовал). Однако у него есть множество уязвимых мест. Подробно их расписывать здесь не буду, ибо оффтопик. Укажу на два главных: (а) бездоказательность (б) бесполезность.

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


> По фрагменту? Не зная ничего об исходном тексте? А что тогда подбирать?

Об исходном тексте всегда что-то известно. Хотя бы то, что это - текст, а не набор бессмысленных символов. Этой информации как правило бывает достаточно для подбора ключа. Недостаточно бывает вычислительных ресурсов.

> не обязательно перебором

Как факт из жизни - обязательно. Есть такие задачи, которые не упрощаются. Возьмите элементарную вещь - вычисление квадратного корня. Казалось бы, что проще - найти корень из 9. Все знают, что это 3. Но вот каков алгоритм нахождения в общем случае? Варианты:
1. Перебором всевозможных чисел, вычислением их квадрата и сравнением. Это очень просто, если известно, что число целое. А если нет и результат мы хотим знать с точностью до 10 знаков? Придется десятки миллиардов чисел проверять. Ладно, это плохой способ.
2. Разложением корня в какой-нибудь ряд Тейлора и расчетом его суммы вплоть до члена, обеспечивающего нужную точность. Иногда этот способ бывает довольно эффективным, но все же ему далеко по простоте до однократного умножения числа само на себя.
3. Последовательными приближениями: например, простой дихотомией. Довольно быстро достигаем нужной точности, но все же это на порядок сложнее, чем вычислить одно произведение.

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

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

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

> > А может есть способ угадывать случайные числа... Но вообще-то в математике пока не предвидится хоть какой-то прогресс в области уменьшения сложности такого рода задач.

> Опять Вы про случайные числа. Разве кто спорит, что в области угадывания "пока не предвидится хоть какой-то прогресс в области уменьшения сложности такого рода задач." Но при чем здесь угадывание?

Я про прогресс в области решения криптоаналитических задач. Все мыслимые способы упрощения задачи взлома данного криптографического алгоритма математики обычно находят в первый же год после его появления. А потом - полное отсутствие какого-либо продвижения и даже всяких надежд на него.

> Иначе, увы, есть объективные законы.

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

> Предмет обсуждения ведь пока в стадии разработки. И вопрос вроде был - а надо ли вообще его разработкой заниматься.

Вот я и хочу понять, зачем это нужно.



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

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

Измерение -это вмешательство в энергетическое состояние системы.
Быть может можно с помощью компенсации проводить измерения не изменяя энергетических состояний измеряемых параметров, но я про такое не слышал, а Вы?

С уважением Д.


> Да ненадо никаких вопросов задавать. Раньше на почте использовался штемпель для бандеролей. Не взломав штемпель и не повредив конверта не возможно было потрогать содержимое бандероли. Так же и с квантовой криптографией - открыть "бандероль" можно лишь один раз. Если кто то до Вас открыл бандероль, то Вы это можете проверить -вот и весь смысл криптоквантования- гарантия что Вы первый читаете посланную Вам информацию.

> Измерение -это вмешательство в энергетическое состояние системы.
> Быть может можно с помощью компенсации проводить измерения не изменяя энергетических состояний измеряемых параметров, но я про такое не слышал, а Вы?

> С уважением Д.

Причём тут "энергетическое состояние"? Разве бандероль со сломанным штемпелем отличается по энергии от целой?


> > > Не, я про отсутствие объективной реальности. Если она ( объективная реальность )
> > > иммитируется сознанием, тогда все возможно при условии, что иммитацию можно
> > > на время отменять. Иначе, увы, есть объективные законы.

> > Vallav, Вы серьёзно полагаете, что все (в частности математические) истины существуют где-то независимо от сознания?

> Не, полагаю, что истины в сознании существуют только в сознании. Но моделируют
> объективную реальность, а не ее иммитацию сознанием.

А что тогда входит в это понятие - "объективная реальность"? Поток ощущений? С этим я согласен.


> Vallav, Вы серьёзно полагаете, что все (в частности математические) истины существуют где-то независимо от сознания? То ли в "мире идей" Платона, то ли в "Абсолютном духе" Гегеля... Вы, впрочем, предпочитаете называть это "объективной реальностью".
> Подробно их расписывать здесь не буду, ибо оффтопик. Укажу на два главных: (а) бездоказательность (б) бесполезность.

А Вы всеръёз считаете, что такая математическая истина исчезнет, после того как умрёт последнее разумное существо нашей Вселенной?
И когда же тогда эта истина появляется?
Когда материя становиться разумной, т.е. сама себя постигающей?
С уважением Д.


> Как факт из жизни - обязательно. Есть такие задачи, которые не упрощаются. Возьмите элементарную вещь - вычисление квадратного корня. Казалось бы, что проще - найти корень из 9. Все знают, что это 3. Но вот каков алгоритм нахождения в общем случае? Варианты:
Ваш пример плох, именно для нахождения квадратного корня есть алгоритм. Если интерессно, то спрошу свою мать как это делается на бумажке, до потери пульса.
Никакого подбора, метод очень похож на деление одного числа на другое.

> Вот я и хочу понять, зачем это нужно.
С уважением Д.



> > Vallav, Вы серьёзно полагаете, что все (в частности математические) истины существуют где-то независимо от сознания? То ли в "мире идей" Платона, то ли в "Абсолютном духе" Гегеля... Вы, впрочем, предпочитаете называть это "объективной реальностью".
> > Подробно их расписывать здесь не буду, ибо оффтопик. Укажу на два главных: (а) бездоказательность (б) бесполезность.

> А Вы всеръёз считаете, что такая математическая истина исчезнет, после того как умрёт последнее разумное существо нашей Вселенной?

Да. Истинным может быть какое-либо высказывание. Кто будет высказываться в заданных Вами обстоятельствах?

> И когда же тогда эта истина появляется?

А как по-Вашему, если разумных существ не было, а истины были - когда они появились во Вселенной? Неужто в момент Большого взрыва :)



> Как факт из жизни - обязательно. Есть такие задачи, которые не упрощаются. Возьмите элементарную вещь - вычисление квадратного корня. Казалось бы, что проще - найти корень из 9. Все знают, что это 3. Но вот каков алгоритм нахождения в общем случае? Варианты:
> 1. Перебором всевозможных чисел, вычислением их квадрата и сравнением. Это очень просто, если известно, что число целое. А если нет и результат мы хотим знать с точностью до 10 знаков? Придется десятки миллиардов чисел проверять. Ладно, это плохой способ.
> 2. Разложением корня в какой-нибудь ряд Тейлора и расчетом его суммы вплоть до члена, обеспечивающего нужную точность. Иногда этот способ бывает довольно эффективным, но все же ему далеко по простоте до однократного умножения числа само на себя.
> 3. Последовательными приближениями: например, простой дихотомией. Довольно быстро достигаем нужной точности, но все же это на порядок сложнее, чем вычислить одно произведение.

Во, во. И я про это. Возможны варианты в решении обратной задачи.
Особенно наглядно это с делением. И, особенно если нужна очень большая точность
результата, положим N бит.
1. Перебор - безнадежно долго.
2. Поразрядный перебор ( деление столбиком ) - намного быстрее, но тоже долго.
3. Рекурсивный алгоритм - никакого перебора, требует 2*logN умножений.
При N=1000 всего 20 умножений.

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

Вопрос только в том, во сколько раз больше. Если в тысячу раз - то не проблема.

> Но с корнем разрыв в сложности прямой и обратной операций не настолько существенный, чтобы его можно было использовать в криптографии. А вот с произведением двух больших простых чисел ситуация другая: Разложение этого произведения на сомножители оказывается очень сложной в вычислительном плане задачей. Фактически ее решение сводится к перебору всевозможных простых сомножителей. И так же как с корнем, вряд ли когда-нибудь эта ситуация изменится.

Но ведь гарантий, что не изменится нет?

> Дело в том, что такие задачи лежат вне сферы применения аналитических методов, наработанных математикой. Если задача изначально сформулирована таким образом, чтобы соответствовать этим методам, то она, естественно, будет иметь аналитическое решение и, соответственно, - низкую вычислительную сложность. Другие задачи неизбежно сводятся к тупому перебору вариантов. Я не верю, например, что когда-нибудь будет придуман алгоритм, позволяющий находить триллионную цифру числа π за десяток процессорных операций.

А за триллион операций?


> Я про прогресс в области решения криптоаналитических задач. Все мыслимые способы упрощения задачи взлома данного криптографического алгоритма математики обычно находят в первый же год после его появления. А потом - полное отсутствие какого-либо продвижения и даже всяких надежд на него.

Но ведь гарантий нет?

> > Иначе, увы, есть объективные законы.

> О каких "объективных законах" речь? О законах квантовой механики? Так это законы теории, созданной людьми. СтоИт ли за ними нечто "объективное" - вопрос спорный. Во всяком случае, научный мир пережил уже столько пересмотров весьма фундаментальных представлений об устройстве Вселенной, что вряд ли стоит полагаться на незыблемость очередного представления.

Стоит. Куда денется. А все пересмотры имеют одно общее - старые законы уточня-
ются для новых условий а не отменяются напрочь.

> > Предмет обсуждения ведь пока в стадии разработки. И вопрос вроде был - а надо ли вообще его разработкой заниматься.

> Вот я и хочу понять, зачем это нужно.

Чтобы повысить надежность защиты сообщения от несанкционированного взлома.


> А что тогда входит в это понятие - "объективная реальность"? Поток ощущений? С этим я согласен.

Оффтопик.


> Причём тут "энергетическое состояние"? Разве бандероль со сломанным штемпелем отличается по энергии от целой?

Избыточное цитирование.


Оффтопик. Если у Вас нет дополнительной конкретной информации по обсуждаемомоу вопросу ("квантовая криптография"), то переходите на форум новых теорий.


> При N=1000 всего 20 умножений.

А прямая операция - всего 1 операция умножения. Не бог весть какая разница, но все же - слабо ее полностью преодолеть?

> > Я не верю, например, что когда-нибудь будет придуман алгоритм, позволяющий находить триллионную цифру числа π за десяток процессорных операций.

> А за триллион операций?

Тоже не верю. И потом, почему за триллион? Ведь цифра-то одна, а вариантов всего 10. Почему бы столбиком на бумажке не посчитать? Не верится? И мне тоже.

> Но ведь гарантий нет?

Абсолютных гарантий вообще ни в чем нет. Даже те гарантии, которые дают страховые компании, измеряются в конечных суммах.

> Стоит. Куда денется. А все пересмотры имеют одно общее - старые законы уточняются для новых условий а не отменяются напрочь.

Отменяются напрочь. Абсолютность времени, возможность одновременного знания импульса и координаты, непрерывность излучения, безусловная евклидовость пространства - все отменилось напрочь.

> > Вот я и хочу понять, зачем это нужно.

> Чтобы повысить надежность защиты сообщения от несанкционированного взлома.

Вот и понять бы, каким образом этот технический метод может дать повышение надежности по сравнению с чистой математикой.


> > При N=1000 всего 20 умножений.

> А прямая операция - всего 1 операция умножения. Не бог весть какая разница, но все же - слабо ее полностью преодолеть?

А зачем? Если закрытый ключ будет вычисляться по открытому в тысячу раз
медленнее, чем открытый по закрытому - Вы полагаете, это будет непреодолимым
препятствием?


> > Стоит. Куда денется. А все пересмотры имеют одно общее - старые законы уточняются для новых условий а не отменяются напрочь.

> Отменяются напрочь. Абсолютность времени, возможность одновременного знания импульса и координаты, непрерывность излучения, безусловная евклидовость пространства - все отменилось напрочь.

Не, именно уточняются.

> > > Вот я и хочу понять, зачем это нужно.

> > Чтобы повысить надежность защиты сообщения от несанкционированного взлома.

> Вот и понять бы, каким образом этот технический метод может дать повышение надежности по сравнению с чистой математикой.

Так пишут же - используя законы квантовой механики.


> > > Стоит. Куда денется. А все пересмотры имеют одно общее - старые законы уточняются для новых условий а не отменяются напрочь.

> > Отменяются напрочь. Абсолютность времени, возможность одновременного знания импульса и координаты, непрерывность излучения, безусловная евклидовость пространства - все отменилось напрочь.

> Не, именно уточняются.

Это результаты вычислений уточняются, а формулы - отменяются. Разницу чувствуете?


> > > > Стоит. Куда денется. А все пересмотры имеют одно общее - старые законы уточняются для новых условий а не отменяются напрочь.

> > > Отменяются напрочь. Абсолютность времени, возможность одновременного знания импульса и координаты, непрерывность излучения, безусловная евклидовость пространства - все отменилось напрочь.

> > Не, именно уточняются.

> Это результаты вычислений уточняются, а формулы - отменяются. Разницу чувствуете?

Отменяются - это когда новая формула при условиях применимости старой сводится
к старой формуле с поправками? Раньше такое ( добавление поправок ) называлось
уточнением.


> > > При N=1000 всего 20 умножений.

> > А прямая операция - всего 1 операция умножения. Не бог весть какая разница, но все же - слабо ее полностью преодолеть?

> А зачем? Если закрытый ключ будет вычисляться по открытому в тысячу раз медленнее, чем открытый по закрытому - Вы полагаете, это будет непреодолимым препятствием?

Криптоалгоритмы тем и отличаются от деления, что сложность обратной операции выше сложности прямой не в 20 и даже не в 1000 раз, а на нехилое количество порядков.

> > Отменяются напрочь. Абсолютность времени, возможность одновременного знания импульса и координаты, непрерывность излучения, безусловная евклидовость пространства - все отменилось напрочь.

> Не, именно уточняются.

Интересный способ "уточнить" представление об абсолютности времени - так, чтобы он превратился в принцип его относительности.

Может так и квантовомеханический принцип разрушения состояния при измерении - со временем "уточнится" так, что превратится в принцип неразрушающего измерения?

> > Вот и понять бы, каким образом этот технический метод может дать повышение надежности по сравнению с чистой математикой.

> Так пишут же - используя законы квантовой механики.

Что-то не больно надежно по сравнению с "использованием законов математики".


> > Это результаты вычислений уточняются, а формулы - отменяются. Разницу чувствуете?

> Отменяются - это когда новая формула при условиях применимости старой сводится
> к старой формуле с поправками? Раньше такое ( добавление поправок ) называлось
> уточнением.

То есть Вы переход от преобразований Галилея к преобразованиям Лоренца называете поправкой (уточнением) формулы? Ладно, учту на будущее :)



> > А зачем? Если закрытый ключ будет вычисляться по открытому в тысячу раз медленнее, чем открытый по закрытому - Вы полагаете, это будет непреодолимым препятствием?

> Криптоалгоритмы тем и отличаются от деления, что сложность обратной операции выше сложности прямой не в 20 и даже не в 1000 раз, а на нехилое количество порядков.

Вы о чем? О том, что в принципе не может быть алгоритма, который работает
быстрее, чем известный? На примере деления показано, что это не так.

> > > Отменяются напрочь. Абсолютность времени, возможность одновременного знания импульса и координаты, непрерывность излучения, безусловная евклидовость пространства - все отменилось напрочь.

> > Не, именно уточняются.

> Интересный способ "уточнить" представление об абсолютности времени - так, чтобы он превратился в принцип его относительности.

А в чем проблема? Читал про зеркала для детектора гравиволн - болванки в несколько
десятков килограмм. Но точность больно высока - приходится учитывать квантовые
эффекты.

> Может так и квантовомеханический принцип разрушения состояния при измерении - со временем "уточнится" так, что превратится в принцип неразрушающего измерения?

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

> > > Вот и понять бы, каким образом этот технический метод может дать повышение надежности по сравнению с чистой математикой.

> > Так пишут же - используя законы квантовой механики.

> Что-то не больно надежно по сравнению с "использованием законов математики".

Это не ко мне, это к тем, кто квантовой криптографией занимается. Объясняйте
им, что ерундой маются...



> То есть Вы переход от преобразований Галилея к преобразованиям Лоренца называете поправкой (уточнением) формулы? Ладно, учту на будущее :)

В области, где v много меньше c? А разве не так?



> Да. Истинным может быть какое-либо высказывание. Кто будет высказываться в заданных Вами обстоятельствах?
Отличаете ли Вы истину от физического закона?

> А как по-Вашему, если разумных существ не было, а истины были - когда они появились во Вселенной? Неужто в момент Большого взрыва :)
Я полагаю что физические з-ны(истина в последней инстанции)были всегда.

С уважением Д.



> Причём тут "энергетическое состояние"? Разве бандероль со сломанным штемпелем отличается по энергии от целой?

Да отличается! Ведь на разлом штемпеля была затраченна энергия.
Поверхность сломанного штемпеля изменилась, расстояние между разломом увеличилось итд итп.Не забывайте, что мы говорим про квантовые состояниях!
С уважением Д.


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100