Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | | | | | | | | |
получай.. 09.07.01 15:27 Число просмотров: 1634
Автор: zelych Статус: Member
|
что-то поздновато ты опомнился, и неожиданно как-то..
однако, если интересно, тогда вот..
как всё это должно выглядеть в железе я не знаю, существует море всевозможных идей по поводу физической реализации квантового компьютера, да и не силён я в физике, поэтому расскажу с математической точки зрения..
вообще, квантовое вчисление является вероятностным, т.е. после применения этой схемы к некоторому начальному состоянию есть "большая" вероятность получить значение некоторой функции от этого состояния.
вероятность эта получается то ли из принципа Гейзинберга, то ли из уравнения Шредингера, вообщем смысл в том, что невозможно точно определить состояние квантовой частицы, а используемые для измерения физические взаимодействия изменяют состояние частицы (кстати именно это и используется в квантовой криптографии).
квантовая схема оперирует некоторым количеством кубитов (частиц). каждый кубит имеет два базисных состояния 0 и 1, так же возможны любые линейные комбинации этих состояний с комплексными коэффициентами:
ф =a.000> +b.001> + ..+c.1111>,
причём вероятность обнаружить некоторое из базисных состояний равна квадрату коэффициента при этом состоянии ( для |..00> это |a|^2), соответственно
|a|^2 + |b|^2 + .. = 1,
это равенство должно быть справедливо и для состояния кубитов после преобразования, поэтому квантовая схема должна состоять из некоторого множества унитарных операторов, сохраняющих эту сумму.
теперь немного о том, как всё это делается..
некоторое количество кубитов находится в каком-либо определённом состоянии. из них берётся несколько и они преобразуются определённым квантовым гейтом, и ставятся на место, после того, как таким образом проделаны все необходимые преобразования, измеряется конечнге состояние кубитов.
вот и всё..
самое главное то, что любые измерения производятся только в самом конце, т.к. после измерения состояние изменяется, т.е. нельза сделать например так:
if( ф == 0) ф++;
а теперь самое главное: квантовый параллелизм..
пусть, например, требуется найти период последовательности
f(0), ..., f( 2^n - 1)
берём два набора кубитов ф1 и ф2: в первом 2^n кубитов, во втором немного побольше.
посредством некоторого квантового оператора преобразуем первый набор к состоянию, в котором все значения 0 .. 2^n-1 равновероятны, т.о. в ф1 получилась суперпозиция всех значений аргумента функции f.
затем f(x) представляется в виде квантовой схемы F(ф) и вычисляется
ф2 = F(ф1),
т.о. ф2 - суперпозиция всех значений f(x) при x = 0 .. 2^n
вот и весь параллелизм..
потом применяется квантовое преобразование Фурье к ф1 (как всё это выглядит не помню).
измеряются значения ф1 и ф2, на этом квантовая часть закончена..
теперь, если t - период и f(a+t) = f(a), то в суперпозиции всех значений аргумента конструктивная интерференция будет только при ф1/2^n кратном 1/t, соответственно вероятность получить это значение будет слегка больше остальных.
пример с периодом последовательности здесь неспроста, если надо разложить на множители большое число N, то можно взять число а взаимно простое с N и вычислить
f(x) = a^x mod N
последовательность {f(x)} периодическая, с периодом t
a^t = 1 mod N,
если он чётный, то последнее тождество можно переписать вот так:
( a^(t/2) - 1 ) ( a^(t/2) + 1) = 0 mod N,
откуда следует, что НОД одного из сомножителей с N является делителем N
вот так..
|
|
<theory>
|
Об ассимитричных алгоритмах 17.05.01 18:35
Автор: tgj Статус: Незарегистрированный пользователь
|
|
Привет... народ, никто не знает, где в и-нете можно посмотреть информацию по теме "Перспективы использования ассимитричных алгоритмов в криптографии"? ,)
|
|
Re: Об ассимЕтричных алгоритмах 23.05.01 18:53
Автор: БРОНЕТАЧКИН Статус: Незарегистрированный пользователь
Отредактировано 23.05.01 18:55 Количество правок: 1
|
> Привет... народ, никто не знает, где в и-нете можно
> посмотреть информацию по теме "Перспективы использования
> ассимитричных алгоритмов в криптографии"? ,)
Кстати, я что-то сегодня торможу... Так про что курсач то? АА только в рамках криптографии или вообще везде, где только можно? Может быть курсач лучше так назвать: "Перспективы использования ассиметричных алгоритмов" и типа точка? ;)))) Или так:"Перспективы использования ассиметричных алгоритмов в электронных платежных системах"... Или вот так: "Перспективы использования ассиметричных алгоритмов. Идентификация и аутентификация. ЭЦП. Управление криптографическими ключами" Или может быть даже так: "Перспективы использования ассиметричных алгоритмов. Новые алгоритмы: генерации новых больших простых чисел, проверки на простоту, возведения в степень многозначного числа. Криптосистемы на эллиптических кривых" :)))))
|
| |
Re: Об ассимЕтричных алгоритмах 23.05.01 22:50
Автор: zelych Статус: Member
|
..skip..
> многозначного числа. Криптосистемы на эллиптических кривых"
> :)))))
если можно поподробнее..
(а лучше, где об этом можно реально прочитать..)
|
| | |
Re: Об ассимЕтричных алгоритмах 24.05.01 02:47
Автор: БРОНЕТАЧКИН Статус: Незарегистрированный пользователь
|
> ..skip..
> > многозначного числа. Криптосистемы на эллиптических
> кривых"
> > :)))))
>
> если можно поподробнее..
> (а лучше, где об этом можно реально прочитать..)
Часто спрашивают в последнее время.Реально читать лучше всего в библиотеке ;) Кстати, для тех, кто боится английского языка: математический английский очень легкий (особенно когда очень надо)! ;)
Fulton W. Algebraic Curves 1969 с древних времен :)))
Lang S. Elliptic Curves: Diophantine Analysis 1978
SilvermanThe Arithmetic of Elliptic Curves 1986
Husemoller D. Elliptic Curves 1987
Вроде толково пишет Koblitz N (Нил Коблиц) можно наверное найти и переводы на русский язык. У него:
Elliptic curve cryptosystems 1987v48
Introdaction to Elliptic Curves and Modular Forms 1993
если мало... могу еще дописать :-)
Что же касается и-нета, как там в писании то "Ищите и обрящете..." или что-то в этом роде: Поиск по всемирным ресурсам http://dialup.mtu.ru/intel_sources/search.htm по ключевым Elliptic curve cryptosystems и тд и тп...
Удачи ;))
|
| | | |
ссылки про ECC 24.05.01 14:33
Автор: XR <eXtremal Research> Статус: The Elderman
|
> > ..skip..
> > > многозначного числа. Криптосистемы на
> эллиптических
> > кривых"
> > > :)))))
> >
> > если можно поподробнее..
> > (а лучше, где об этом можно реально прочитать..)
>
> Часто спрашивают в последнее время.Реально читать лучше
> всего в библиотеке ;) Кстати, для тех, кто боится
> английского языка: математический английский очень легкий
> (особенно когда очень надо)! ;)
>
> Fulton W. Algebraic Curves 1969 с древних времен :)))
> Lang S. Elliptic Curves: Diophantine Analysis 1978
> SilvermanThe Arithmetic of Elliptic Curves 1986
> Husemoller D. Elliptic Curves 1987
>
> Вроде толково пишет Koblitz N (Нил Коблиц) можно наверное
> найти и переводы на русский язык. У него:
> Elliptic curve cryptosystems 1987v48
> Introdaction to Elliptic Curves and Modular Forms 1993
>
> если мало... могу еще дописать :-)
Я допишу :)
http://www.certicom.com/research/online.html
http://www.pegwit.org
http://www.esat.kuleuven.ac.be/~rijmen/
и ниже ссылка на страничку П.Семьянова, на эту тему я у него
насчитал ссылок с полдюжины ...
>
> Что же касается и-нета, как там в писании то "Ищите и
> обрящете..." или что-то в этом роде: Поиск по всемирным
> ресурсам http://dialup.mtu.ru/intel_sources/search.htm по
> ключевым Elliptic curve cryptosystems и тд и тп...
>
Это точно ;)
> Удачи ;))
P. Semjanov
|
|
о них же.. 17.05.01 18:40
Автор: zelych Статус: Member
|
> Привет... народ, никто не знает, где в и-нете можно
> посмотреть информацию по теме "Перспективы использования
> ассимитричных алгоритмов в криптографии"? ,)
перспективы?? весьма радужные..
|
| |
о них же.. 18.05.01 14:11
Автор: XR <eXtremal Research> Статус: The Elderman
|
> > Привет... народ, никто не знает, где в и-нете можно
> > посмотреть информацию по теме "Перспективы
> использования
> > ассимитричных алгоритмов в криптографии"? ,)
>
> перспективы?? весьма радужные..
Звучит как "Перспективы применения компьютеров в Internet" :)))
|
| | |
о них же.. 18.05.01 16:24
Автор: tgj Статус: Незарегистрированный пользователь
|
> > > Привет... народ, никто не знает, где в и-нете
> можно
> > > посмотреть информацию по теме "Перспективы
> > использования
> > > ассимитричных алгоритмов в криптографии"? ,)
> >
> > перспективы?? весьма радужные..
>
> Звучит как "Перспективы применения компьютеров в Internet"
> :)))
;)))))) да это я понимаю ;) но курсовик-то надо написать ;)
|
| | | |
немного конкретнее.. 21.05.01 17:27
Автор: zelych Статус: Member
Отредактировано 21.05.01 17:31 Количество правок: 1
|
> ;)))))) да это я понимаю ;) но курсовик-то надо написать ;)
конечно с "радужными перспективами" это я поспешил..
наиболее распространенная схема RSA основывается на вычислительной сложности дискретного логарифмирования. однако, теоретически эта проблема уже разрешена. Шор году кажется в 95`ом предложил квантовый алгоритм, позволяющий за полиномиальное время раскладывать большие числа на множители.
фишка в том, что квантовые компьтеры существуют пока только на бумаге, хотя по моему мнению еще лет 10 - 20 и..
..а что случится можно только предполагать.. наверное все спецслужбы сразу же обзаведутся такими компами, а это - никакой конфиденциальности в инете, полная отслеживаемость операций с банковскими картами, да и все прочая фигня типа ЭЦП Эль-Гамаля и т.п. будет уже не актуальна..
другое дело если кто-то предложит еще какую-нибудь одностороннюю функцию.. я что-то слышал о схеме основанной на сложности задачи о коммивояжоре, однако ничего конкретного по этому поводу не знаю..
еще конечно будет квантовая криптография, это уже может заменить RSA в смысле распределения ключей, однако до рядовых юзеров это скорее всего не дойдет, т.к. для передачи ключей необходим квантовый канал, а вот всякие там госучреждения вполне могут заиметь себе такой (году опять таки примерно в 95`ом был проведен эксперимент, в рамках которого по квантовому каналу на основе оптоволокна передали что-то на 23 километра, так что квантовая криптография, можно сказать, уже рльность)..
подробнее про квантовые компы и все, что с ними связано rcd.ru/qc
еще одна проблема - юридическая. это только для личного пользования никаких законов не надо, а чтобы реально использовать все выгоды от использования криптосредств нужны законы, причем законы правильные, а с этим, особенно в нашей стране, как-то не очень. а всё потому, что сидят у нас там, наверху, всякие ламухи которые не фига не понимают в этих делах, а спросить у людей знающих стесняются, вот и появляются всякие закончики с дырочками как у мастдая (а через эти дырочки свои люди могут себе денег немножко накачать), да такие законы что внедрять и пользоваться выгодами получается как-то невыгодно..
извини, что в таком тоне,просто наболело..
если хочешь подробнее поищи на computerra.ru, там в номере за 15 мая статейка была про коррупцию, да и вообще спроси у них там например про
внедрение закона об ЭЦП, они тебе расскажут..
а если не считать всего что я тут понаписал, то перспективы действительно весьма радужные: цифровой документооборот, развитие торговли и соответственно процветание всего человечества..
|
| | | | |
немного конкретнее.. 23.05.01 09:53
Автор: caxap Статус: Незарегистрированный пользователь
|
> конечно с "радужными перспективами" это я поспешил..
> наиболее распространенная схема RSA основывается на
> вычислительной сложности дискретного логарифмирования.
Извиняй, канешна, но устойчивость RSA основывается не на сложности дискретного логарифмирования, это ты с Диффи-Хеллманом спутал
> однако, теоретически эта проблема уже разрешена. Шор году
> кажется в 95`ом предложил квантовый алгоритм, позволяющий
> за полиномиальное время раскладывать большие числа на
> множители.
А что есть квантовый АЛГОРИТМ?? Чем он отличается от вообще алгоритма?
Надо ли понимать так, что тем самым решена проблема P=NP?
|
| | | | | |
немного конкретнее.. 23.05.01 22:47
Автор: zelych Статус: Member
|
> Извиняй, канешна, но устойчивость RSA основывается не на
> сложности дискретного логарифмирования, это ты с
> Диффи-Хеллманом спутал
кажется, нет..
но, в любом случае, дискретное логарифмирование, квадратичные вычеты и т.д. все эти "сложные проблемы" по сложности эквивалентны разложению числа на простые множители
> А что есть квантовый АЛГОРИТМ?? Чем он отличается от вообще
> алгоритма?
если ты хочешь знать, что это такое, то лучше зайди на rcd.ru/qc
> Надо ли понимать так, что тем самым решена проблема P=NP?
проблема P=NP этм не решается, просто Шором было найдено полиномиальное решение всего одной из задач, которая считалась до этого вычислительно не разрешимой..
|
| | | | | | |
немного конкретнее.. 24.05.01 14:18
Автор: XR <eXtremal Research> Статус: The Elderman
|
> > Извиняй, канешна, но устойчивость RSA основывается не
> на
> > сложности дискретного логарифмирования, это ты с
> > Диффи-Хеллманом спутал
>
> кажется, нет..
DH основан на дискретной экспоненте а атака будет сводиться к задаче
логарифмирования на простом поле. (DLP)
атака же на RSA действительно сводится к задаче факторизации (FACT)
то есть разложения числа на множители
> но, в любом случае, дискретное логарифмирование,
> квадратичные вычеты и т.д. все эти "сложные проблемы" по
> сложности эквивалентны разложению числа на простые
поясни насчет "эквивалентны" ...
hint: В настоящее время проблема DLP наиболее эффективно решаема
либо Копперсмитом либо алгоритмом COS а проблема FACT
- полиномиальным решетом MPQS
- алгоритмом непрерывных дробей CFM
- алгоритмом эллиптических кривых ECM
> множители
>
> > А что есть квантовый АЛГОРИТМ?? Чем он отличается от
> вообще
> > алгоритма?
>
> если ты хочешь знать, что это такое, то лучше зайди на
> rcd.ru/qc
То есть в 2-х словах не объяснишь ? :)
> > Надо ли понимать так, что тем самым решена проблема
> P=NP?
>
> проблема P=NP этм не решается, просто Шором было найдено
> полиномиальное решение всего одной из задач, которая
> считалась до этого вычислительно не разрешимой..
Пахнет массовым параллелизмом :) я прав ?
|
| | | | | | | |
если интересно, продолжение будет.. 24.05.01 17:08
Автор: zelych Статус: Member
|
> DH основан на дискретной экспоненте а атака будет сводиться
> к задаче
> логарифмирования на простом поле. (DLP)
>
> атака же на RSA действительно сводится к задаче
> факторизации (FACT)
> то есть разложения числа на множители
>
> > но, в любом случае, дискретное логарифмирование,
> > квадратичные вычеты и т.д. все эти "сложные проблемы"
> по
> > сложности эквивалентны разложению числа на простые
>
> поясни насчет "эквивалентны" ...
я имею в виду, что для того чтобы найти дискретный логарифм, или квадратичный вычет достаточно знать разложение на простые множители в первом случае модуля, во втором - модуля-1
> hint: В настоящее время проблема DLP наиболее эффективно
> решаема
> либо Копперсмитом либо алгоритмом COS а проблема FACT
> - полиномиальным решетом MPQS
> - алгоритмом непрерывных дробей CFM
> - алгоритмом эллиптических кривых ECM
> > > А что есть квантовый АЛГОРИТМ?? Чем он отличается
> от
> > вообще
> > > алгоритма?
> То есть в 2-х словах не объяснишь ? :)
в двух словах сложно, прям так сразу не смогу, надо немного подумать..
> > проблема P=NP этм не решается, просто Шором было
> найдено
> > полиномиальное решение всего одной из задач, которая
> > считалась до этого вычислительно не разрешимой..
>
> Пахнет массовым параллелизмом :) я прав ?
в некотором смысле да, дело в том, что один квантовый бит может одновременно действовать на много других..
P.S. если всётаки интересно,что это такое, то можно и продолжить..
|
| | | | | | | | |
интересно, хочу продолжение :) 19.06.01 03:38
Автор: Бяша <Biasha> Статус: Member
|
> > > > А что есть квантовый АЛГОРИТМ?? Чем он отличается от
> > > > вообще алгоритма?
> в двух словах сложно, прям так сразу не смогу, надо немного
> подумать..
Ну и что это такое? (наиболее формальное определение)
> P.S. если всётаки интересно,что это такое, то можно и
> продолжить..
а зачем же эта доска ещё :)
|
| | | | | | | | | |
получай.. 09.07.01 15:27
Автор: zelych Статус: Member
|
что-то поздновато ты опомнился, и неожиданно как-то..
однако, если интересно, тогда вот..
как всё это должно выглядеть в железе я не знаю, существует море всевозможных идей по поводу физической реализации квантового компьютера, да и не силён я в физике, поэтому расскажу с математической точки зрения..
вообще, квантовое вчисление является вероятностным, т.е. после применения этой схемы к некоторому начальному состоянию есть "большая" вероятность получить значение некоторой функции от этого состояния.
вероятность эта получается то ли из принципа Гейзинберга, то ли из уравнения Шредингера, вообщем смысл в том, что невозможно точно определить состояние квантовой частицы, а используемые для измерения физические взаимодействия изменяют состояние частицы (кстати именно это и используется в квантовой криптографии).
квантовая схема оперирует некоторым количеством кубитов (частиц). каждый кубит имеет два базисных состояния 0 и 1, так же возможны любые линейные комбинации этих состояний с комплексными коэффициентами:
ф =a.000> +b.001> + ..+c.1111>,
причём вероятность обнаружить некоторое из базисных состояний равна квадрату коэффициента при этом состоянии ( для |..00> это |a|^2), соответственно
|a|^2 + |b|^2 + .. = 1,
это равенство должно быть справедливо и для состояния кубитов после преобразования, поэтому квантовая схема должна состоять из некоторого множества унитарных операторов, сохраняющих эту сумму.
теперь немного о том, как всё это делается..
некоторое количество кубитов находится в каком-либо определённом состоянии. из них берётся несколько и они преобразуются определённым квантовым гейтом, и ставятся на место, после того, как таким образом проделаны все необходимые преобразования, измеряется конечнге состояние кубитов.
вот и всё..
самое главное то, что любые измерения производятся только в самом конце, т.к. после измерения состояние изменяется, т.е. нельза сделать например так:
if( ф == 0) ф++;
а теперь самое главное: квантовый параллелизм..
пусть, например, требуется найти период последовательности
f(0), ..., f( 2^n - 1)
берём два набора кубитов ф1 и ф2: в первом 2^n кубитов, во втором немного побольше.
посредством некоторого квантового оператора преобразуем первый набор к состоянию, в котором все значения 0 .. 2^n-1 равновероятны, т.о. в ф1 получилась суперпозиция всех значений аргумента функции f.
затем f(x) представляется в виде квантовой схемы F(ф) и вычисляется
ф2 = F(ф1),
т.о. ф2 - суперпозиция всех значений f(x) при x = 0 .. 2^n
вот и весь параллелизм..
потом применяется квантовое преобразование Фурье к ф1 (как всё это выглядит не помню).
измеряются значения ф1 и ф2, на этом квантовая часть закончена..
теперь, если t - период и f(a+t) = f(a), то в суперпозиции всех значений аргумента конструктивная интерференция будет только при ф1/2^n кратном 1/t, соответственно вероятность получить это значение будет слегка больше остальных.
пример с периодом последовательности здесь неспроста, если надо разложить на множители большое число N, то можно взять число а взаимно простое с N и вычислить
f(x) = a^x mod N
последовательность {f(x)} периодическая, с периодом t
a^t = 1 mod N,
если он чётный, то последнее тождество можно переписать вот так:
( a^(t/2) - 1 ) ( a^(t/2) + 1) = 0 mod N,
откуда следует, что НОД одного из сомножителей с N является делителем N
вот так..
|
| | | | | | | | | | |
получай.. 10.07.01 03:49
Автор: Бяша <Biasha> Статус: Member
|
Короче ясно, что нужно читать.
Потому вопрос: где это можно почитать? Желательно на русском. Желательно с минимумом физики.
|
| | | | | | | | | | | |
вот.. 13.07.01 15:53
Автор: zelych Статус: Member
Отредактировано 13.07.01 15:58 Количество правок: 1
|
почитать можно на rcd.ru/qc
есть ещё замечательная книжка "Классические и квантовые вычисления" там три автора: Шень, Манин, кажется, и ещё кто-то..
вообщем там как раз физики не так уж много, однако книжка весьма серьёзная: я её уже два раза читал, однако думаю можно ещё много чего интересного от туда выцепить..
вот так..
|
|
|
подробно о проекте
Анализ криптографических сетевых...
