пришел звиздец RSA

несколько замечаний по поводу прочитанно и увиденного:
1) некоторое удивление/сомненения вызывает перечень заслуг ...http://www.dwavesys.com/index.php?page=executive-team,,ну это так.. к слову пришлось..
2) о снимке "кристалла" - одна из последних - 0.1-микронная технология таких картинок не даст и к тому же доступна далеко не каждой компании, даже если компания в состоянии оплатить чип в штучном исполнении. к том уже при якобы сильном увеличении ландшафт кристалла не будет а-ля "голая пустыня" + "дорожки".
Предположим, что дорожки - это 0.1-0.2 микрон - это означает наличие оптических эффектов при съемке.. на такой толщине (если склероз не подводит) должна быть дифракция min в порядок. а где?...
и еще одно: структура + дорожки - не регулярная (а-ля "память") => произвольный дотуп к "базовым" элементам под большим вопросом. Даже если и поверить в реальность структуры - я бы трассировал это безобразие иначе..
ps/ и где взяли прозрачный диэлектрик?!
pps/ только не говорите, что "розовое" - это кремний!

так что.. будем ждать новостей...

 

Наткнулся по теме
http://www.osp.ru/news/2007/0312/3999402/

 

RElf, Solo, Stiver, crypto

Ну ok-ok, брякнул немножко не то. Погорячился. Чего ж так сразу пинать?

1. Имеем NP-полную проблему - факторизацию
2. Имеем RSA - алгоритм на основе NP-полной проблемы (т.е., я, конечно, понимаю, что никто, пока, собсно и не доказал, что RSA - это, действительно, NP, а не, скажем, P; поэтому сойдемся на NP)
3. Имеем алгоритм товарища Шора, который может погупать это добро за полиномиальное время на квантовом компе.

Собсно, поэтому и назвал. Признаю, погорячился. Переименую в "пришел звиздец RSA"

 

Помнится лет 10 (?) назад тоже была утка, что кто то придумал энергонезависимую память с быстродействием больше чем у оперативки и чуть ли не террабитными объемами на обном кристалле + дешевле обычной. И вроде показали опытный образец. Но вроде ни чего такого досих пор не наблюдается.
Называлось это чудо по имени создателя на букву Ш, но точней уже не помню.

 

Нет только квантового компа с 1024 кубитами (меньшее число кубитов один фиг не поможет сломать нормальные ключеги). Да и широко разрекламированый в прессе 16 кубитовый компьютер скорее всего не существует.
Да и если решиться проблема факторизации, что с того? Звезды от этого не упадут на землю, на свете не один RSA существует. Я так понимаю, что скорее всего дискретный логарифм и эллиптику на квантовой машине тоже можно будет ломать, но зато останется HFE, а также разные вариации задачи укладки ранца (может наконец то криптографы всерьез займуться ранцевыми алгоритмами).

 

http://www.pcworld.com/article/id,129711-c,futuretechnology/article.html

 

Ну существует 16 кубитовый компьютер, и что это меняет? (хотя один фиг не верю. для меня что наса подтвердило, что бабка из соседнего подьезда..) Имхо это все много шуму из ничего. Ученые давно бьются над квантовыми вычислениями, и представили уже немало разных концептов, только они сидели тихо, а не кричали об этом на весь мир. А эти же товарищи собираются в скором времени сдавать машинное время своего убогого вычислителя... Ну допустим доведут они число кубитов до 32 (это кажется реальным), всеравно такая машина окажется медленее хорошей обычной. Ну а оещание представить к концу следующего года 1024 кубита, это вобще курам на смех.
Скорее всего вся эта клоунада затевается с целью поднять курс акций конторы, которые будут распроданы предприимчивыми организаторами пиара, ну а когда выясниться, что все обещания оказались фуфлом, то лопухи инвесторы останутся с дулей в кармане...

 

volodya
Если быть совсем строгим, то факторизация принадлежит к NP (это очевидно, так как решение может быть проверено за полиномиальное время), но не доказано, что она принадлежит к NP-complete. Цитата из википедии: "If it could be proved that it is in either NP-Complete or co-NP-Complete, that would imply NP = co-NP. That would be a very surprising result, and therefore integer factorization is widely suspected to be outside both of those classes. Many people have tried to find classical polynomial-time algorithms for it and failed, and therefore it is widely suspected to be outside P."
Но то, что RSA рано или поздно все-таки придет звиздец, это медицинский факт

 

немного хотелось бы добавить:
для реализации полномасштабного квантового компьютера ПРЕВОСХОДЯЩЕГО по ПРОИЗВОДИТЕЛЬНОСТИ любой классический компьютер, на каких бы ФИЗИЧЕСКИХ принципах он не работал, следует обеспечить всего 5 пунктов:

1.L>1000
2.возможность процесса инициализации входного регистра.
3.обеспечить подавление эффектов декогерентизации. Время декогерентизации должно превышать минимум в 10^4 раз превышать время выполнения основных квантовых операций.
4.Необходимо обеспечить за время такта выполнение требуемой совокупности квантовых логических операций, определяющей унитарное преобразование. Эта совокупность должна содержать определенный набор только двухкубитовых операций, типа контролируемый инвертор или контролируемое НЕ (аналог исключающего ИЛИ в классических компьютерах), осуществляющих операции поворота вектора состояния двух взаимодействующих кубитов в четырехмерном гильбертовом пространстве, и однокубитовых операций, осуществляющих поворот вектора состояния кубита в двухмерном гильбертовом пространстве, таких как операции НЕ, Адамара и некоторые другие.
5.Необходимо обеспечить с достаточно высокой надежностью измерение состояния квантовой системы на выходе. Проблема измерения конечного квантового состояния является одной из основных проблем квантовых вычислений.




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

 

Квантовый компьютер всего лишь открывает эру гонки квантовых компьютеров за очередным приращением длины RSA ключа. Не больше и не меньше.

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

В связи с этим актуальность при выборе длинны RSA ключа приобретает аналог закона Мура для квантовых компьютеров.

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

Но сдругой стороны, RSA рано списывать со счетов, ибо всегда можно создать ключ, невзламываемый на ближайшие 50 лет.

А кого сейчас волнуют военные секреты Наполеона? У любой секретной информации есть срок актуальности.

Так что не вижу особой проблеммы.

 

RSA пора списывать со счетов, так как если обещаный 1024 кубитный компьютер будет готов, то все начнут переходить на 4, потом восьми, потом 16 килобитные ключи... Это уже по производительности ни в какие ворота не лезет, так что хотябы из этого соображения стоит озабоиться переходом на ECC или HFE уже сейчас.

 

по идее хватит и 32 кубитного компьютера, но пока его сделают...

 

насколько я себе представляю, в класс НП-полных попадают только те задачи, для которых доказано, что они эквивалентны какой-либо НП-полной.
Не стоит путать НП и НП-полноту.

 

http://www.computerra.ru/310169/

 

и что ты этим хочушь сказать?

 

RSA - ломают перебором (можно таблично) (грубой силой)
64 - битную реализачию на P4 - не очень долго (пробовал)
(например все простые числа до 2^32 занимают 193 МБ (1 байт на число))
У спец служб всяко это реализована на процах где это реализовано на железе и агромный массив винтов

Наращивая длину ключа - практически не даст гарантии, что взлом услрожнится
только время шифравания возрастет

Для квантового компа перебор всех ключей плевое дело (длина не имеет значения), тк его вычисления и заключаеется
проити все стадии пока не уравновесятся веса (кубит - это не 0-1 а некоторое состояние которое можно представить очень большим числом (незря его представляют как онадлоговое устройство)) например косинус можно представить как + (1) или - (0) или бесконечно возможных состояний

 

SWR
1. Только не говори никому, что RSA ломают грубой силой, а также про то, что число до 2^32 можно записать в один байт (за умного сойдешь).
2. А можно ли эту 64 битную реализацию продемонстрировать, ну например на RSA-704?
3. Для квантового компьютера алгоритм не совсем плевое дело как у тебя написано (алгоритм Шора не уравновешивает веса).

Что касаемо применяемых методов факторизации - наиболее быстрый на сегодняшний день - GNFS.

 

жжошь. В 1 байт впихнуть числа до 2^32 - квантовые контуперы отдыхают....

 

SWR
Апстену, адназначна!

 

В 1 байте хранится не число, а разница деленная на 2 до следующего простого числа.
(на самом деле там табличная (есть растояния более 255 но их мало))

Учись читаит - не в 1 байт все числа, а в 193 МБ и не все ,а только простые.