LINUX.ORG.RU
ФорумTalks

я не спец в шифровании но заинтересовала новость


0

0

http://www.linux.org.ru/view-message.jsp?msgid=1781498

вот возьму я 6-й сонет шекспира и им, по хитрому образу зашифрую свое сообщение. Как может в этом случае помочь квантовый компьютер в расшифровке? Ну или текст любой за основу ключа, который никогда не издавался и известен только двум людям. И ключик, будет иметь, например? 10^15 десятичных символов.

☆☆


--------8<-----------

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

Чем же квантовый компьютер лучше классического? Большая часть современных ЭВМ работают по такой же схеме: n бит памяти хранят состояние и каждый такт времени изменяются процессором. В квантовом случае, система из n кубитов находится в состоянии, являющимся суперпозицией всех базовых состояний, поэтому изменение системы касается всех 2n базовых состояний одновременно. Теоретически новая схема может работать намного (в экспоненциальное число раз) быстрее классической. Практически, (квантовый) алгоритм Гровера поиска в базе данных показывает квадратичный прирост мощности против классических алгоритмов. Пока в природе их не существует.

[править] Алгоритмы

* Алгоритм Гровера позволяет найти решение уравнения f(x)=1,\; 0\le x < N за время O(\sqrt{N}).
* Алгоритм Шора позволяет разложить натуральное число n на простые множители за полиномиальное от log(n) время (для обычного компьютера полиномиальный алгоритм неизвестен).
* Алгоритм Дойча &#8212; Джоза позволяет &#171;за одно вычисление&#187; определить, является ли функция двоичной переменной f(n) постоянной (f1(n) = 0, f2(n) = 1 независимо от n) или &#171;сбалансированной&#187; (f3(0) = 0, f3(1) = 1; f4(1) = 1, f4(0) = 0).

Было показано, что не для всякого алгоритма возможно &#171;квантовое ускорение&#187;.

------------8<------------

взято с википедии

Deleted
()
Ответ на: комментарий от Deleted

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

vilfred ☆☆
() автор топика
Ответ на: комментарий от vilfred

Никак.

Как доказал дядя Шеннон, шифр Вернама - единственный принципиально нераскрываемый шифр.

Квантовый компьютер может использоваться только для взлома шифров, которые принципиально раскрываемы, но требуют слишком большого времени. Например, вскрытие RSA сводится к задаче разложения числа на множители, это NP-сложная задача, но она может быть решена на квантовом компьютере за полиномиальное время. (Правда, с кучей оговорок.)

Sikon ★★★
()
Ответ на: комментарий от KRoN73

> Сегодня основной вид шифров - это шифры с открытым ключём.

Сегодня основной вид компьютеров - это компьютеры с монитором?

legk
()
Ответ на: комментарий от legk

>Сегодня основной вид компьютеров - это компьютеры с монитором?

не понял иронии - есть еще алгоритмы с закрытым ключом.

blaster999 ★★
()
Ответ на: комментарий от blaster999

смысл в том, что сегодня без алгоритмов с закрытым ключом, алгоритмы с открытым ключом мало применимы.

legk
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.