Четвёртой части моего введения пришлось немного подождать, но вот настало время и для неё. Ранее я касался некоторых тем, которые непосредственно вели к появлению направления квантовой информации и квантовых вычислений. Это уже были квантовая физика, информатика и, конечно же, теория информации. Сегодня же давайте сменим тему, обратившись к старому искусству — криптографии.
Если говорить в целом, то криптография решает проблему осуществления связи или вычислений между несколькими сторонами, которые не могут доверять друг другу. Самая известная криптографическая проблема — секретная передача данных. Возьмём самый банальный пример, вы хотите передать продавцу номер своей кредитки в обмен на товары, при этом, чтобы данные не были перехвачены третьей стороной. Это всё делается при помощи криптографического протокола. В дальнейших статьях я разовью тему криптографических протоколов, а пока достаточно лишь понять различие между криптосистемами с секретным ключом (privat key) и криптосистемами с открытым ключом (public key).
Суть работы системы с секретным ключом заключается в том, что две стороны, Алиса и Боб, используют для связи секретный ключ, который известен только им. Точный формат ключа в данном случае не имеет значения, представьте себе, например, строку из нулей и единиц. Вся «соль» в том, что этот ключ используется Алисой для шифровки данных, передаваемых Бобу, который должен будет их расшифровать. Как именно Алиса зашифрует информацию зависит от ключа, потому Боб должен обязательно знать ключ, для дешифровки.
К сожалению, такие системы имеют недостатки во многом. Наиболее фундаментальная проблема — как распределять ключи? Во многом эта проблема аналогична по своей сложности проблеме секретной связи, ведь третья сторона может перехватить ключ, а затем использовать его для расшифровки сообщений.
И вот тут в дело вступает квантовая механика. Одним из первых открытий в области квантовых вычислений и квантовой информации стал тот факт, что квантовая механика позволяет обеспечить полную конфиденциальность при распределении. Соответствующая процедура известна как квантовая криптография или квантовое распределение ключей. Основано это на принципе, согласно которому, наблюдение в общем случае всегда ведет к возмущению системы. Таким образом, если злоумышленник вклинивается в канал связи, то его присутствие будет проявляться в виде возмущения канала, а это в свою очередь видят Алиса и Боб. В такой ситуации Алиса и Боб просто могут отбросить биты, использованные при вмешательстве, и начать всё заново, без их использования.
Принципы квантовой криптографии были предложены еще в конце 60-х гг. Стивеном Уиснером, но не были приняты в печать. В итоге, в 1984 году Чарльз Беннет и Джилльз Брассар, опираясь на более ранние работы Уиснера, предложили первый криптографический протокол, который сейчас известен во всем мире как ВВ84. С тех пор, в мире было разработано большое количество квантовых криптографических протоколов, и не меньшее количество их экспериментальных прототипов. На данный момент некоторые подобные системы могут быть полезны для реальных приложений ограниченных масштабов.
Вторым важным видом криптосистем являются криптосистемы с открытым ключом. Такие системы не опираются на предварительную передачу секретного ключа между Алисой и Бобом. Вместо этого Боб публикует свой «открытый ключ», делая его доступным абсолютно всем.Алиса вполне может воспользоваться этим ключом для шифрования пересылаемого сообщения. Однако, интересным фактом является то, что третья сторона не сможет произвести дешифровку, используя только открытый ключ. Точнее говоря, шифрующее преобразование выбирается настолько хитроумно и нетривиально, что его исключительно трудно, хотя в принципе и возможно, обратить, зная только этот ключ. Чтобы обращение было простым для Боба, у него есть свой секретный ключ, соответствующий открытому ключу. Вместе они с легкостью позволяют Бобу расшифровать полученные сообщения.Секретный ключ дает определенную степень уверенности, что никто кроме Боба не сможет прочитать сообщение. И как правильно, вряд ли у кого-то хватит вычислительных ресурсов, чтобы осуществить дешифровку, имея лишь открытый ключ. Таким образом, данные системы решают проблему распределения ключей, делая ненужной передачу секретного ключа перед установлением связи.
Удивительны является тот факт, что данное направление, произведшее революцию в криптографии, не получило широкого распространения до середины 70-х гг., когда она была независимо предложена Уитфилдом Диффи и Мартином Хэллманом, а также Ральфом Меркле. Немного позже Рональд Райвест, Ади Шамир и Леонард Эдельман разработали криптосистему RSA, которая является наиболее распространённой системой своего типа в мире.
Позже выяснилось, что криптография с открытым ключом, криптосистемы Диффи-Хеллмана и RSA — на самом деле были разработаны в конце 60-х и начале 70-х гг. исследователями из Британского разведывательного управления.
Безопасность систем с открытым ключом основана на том, что обращение стадии шифровки только при наличии открытого ключа безумно затруднительно. Всё этого потому, что, например, подобная задача для RSA тесно связана с задачей факторизации. Общепринято, что задача факторизации трудно решается на классическом компьютере. Однако, быстрый алгоритм факторизации, разработанный Шором для квантового компьютера, мог бы послужить для взлома RSA.
Именно это практического применение квантовых компьютеров — взлом криптографических кодов — стимулировало интерес к квантовым вычислениям и квантовой информации.
Вот мы и рассмотрели исторические корни квантовых вычислений и квантовой информации. Конечно, с ростом и развитием этой области из нее выделились многие самостоятельные подразделы исследований, и вот уже о них, а так же конкретно о квантовых вычислениях и квантовой теории информации, я бы и хотел поговорить далее.
Криптография.
Если говорить в целом, то криптография решает проблему осуществления связи или вычислений между несколькими сторонами, которые не могут доверять друг другу. Самая известная криптографическая проблема — секретная передача данных. Возьмём самый банальный пример, вы хотите передать продавцу номер своей кредитки в обмен на товары, при этом, чтобы данные не были перехвачены третьей стороной. Это всё делается при помощи криптографического протокола. В дальнейших статьях я разовью тему криптографических протоколов, а пока достаточно лишь понять различие между криптосистемами с секретным ключом (privat key) и криптосистемами с открытым ключом (public key).
Криптосистемы с секретным ключом.
Суть работы системы с секретным ключом заключается в том, что две стороны, Алиса и Боб, используют для связи секретный ключ, который известен только им. Точный формат ключа в данном случае не имеет значения, представьте себе, например, строку из нулей и единиц. Вся «соль» в том, что этот ключ используется Алисой для шифровки данных, передаваемых Бобу, который должен будет их расшифровать. Как именно Алиса зашифрует информацию зависит от ключа, потому Боб должен обязательно знать ключ, для дешифровки.
К сожалению, такие системы имеют недостатки во многом. Наиболее фундаментальная проблема — как распределять ключи? Во многом эта проблема аналогична по своей сложности проблеме секретной связи, ведь третья сторона может перехватить ключ, а затем использовать его для расшифровки сообщений.
И вот тут в дело вступает квантовая механика. Одним из первых открытий в области квантовых вычислений и квантовой информации стал тот факт, что квантовая механика позволяет обеспечить полную конфиденциальность при распределении. Соответствующая процедура известна как квантовая криптография или квантовое распределение ключей. Основано это на принципе, согласно которому, наблюдение в общем случае всегда ведет к возмущению системы. Таким образом, если злоумышленник вклинивается в канал связи, то его присутствие будет проявляться в виде возмущения канала, а это в свою очередь видят Алиса и Боб. В такой ситуации Алиса и Боб просто могут отбросить биты, использованные при вмешательстве, и начать всё заново, без их использования.
Принципы квантовой криптографии были предложены еще в конце 60-х гг. Стивеном Уиснером, но не были приняты в печать. В итоге, в 1984 году Чарльз Беннет и Джилльз Брассар, опираясь на более ранние работы Уиснера, предложили первый криптографический протокол, который сейчас известен во всем мире как ВВ84. С тех пор, в мире было разработано большое количество квантовых криптографических протоколов, и не меньшее количество их экспериментальных прототипов. На данный момент некоторые подобные системы могут быть полезны для реальных приложений ограниченных масштабов.
Криптосистемы с открытым ключом.
Вторым важным видом криптосистем являются криптосистемы с открытым ключом. Такие системы не опираются на предварительную передачу секретного ключа между Алисой и Бобом. Вместо этого Боб публикует свой «открытый ключ», делая его доступным абсолютно всем.Алиса вполне может воспользоваться этим ключом для шифрования пересылаемого сообщения. Однако, интересным фактом является то, что третья сторона не сможет произвести дешифровку, используя только открытый ключ. Точнее говоря, шифрующее преобразование выбирается настолько хитроумно и нетривиально, что его исключительно трудно, хотя в принципе и возможно, обратить, зная только этот ключ. Чтобы обращение было простым для Боба, у него есть свой секретный ключ, соответствующий открытому ключу. Вместе они с легкостью позволяют Бобу расшифровать полученные сообщения.Секретный ключ дает определенную степень уверенности, что никто кроме Боба не сможет прочитать сообщение. И как правильно, вряд ли у кого-то хватит вычислительных ресурсов, чтобы осуществить дешифровку, имея лишь открытый ключ. Таким образом, данные системы решают проблему распределения ключей, делая ненужной передачу секретного ключа перед установлением связи.
Удивительны является тот факт, что данное направление, произведшее революцию в криптографии, не получило широкого распространения до середины 70-х гг., когда она была независимо предложена Уитфилдом Диффи и Мартином Хэллманом, а также Ральфом Меркле. Немного позже Рональд Райвест, Ади Шамир и Леонард Эдельман разработали криптосистему RSA, которая является наиболее распространённой системой своего типа в мире.
Позже выяснилось, что криптография с открытым ключом, криптосистемы Диффи-Хеллмана и RSA — на самом деле были разработаны в конце 60-х и начале 70-х гг. исследователями из Британского разведывательного управления.
Безопасность систем с открытым ключом основана на том, что обращение стадии шифровки только при наличии открытого ключа безумно затруднительно. Всё этого потому, что, например, подобная задача для RSA тесно связана с задачей факторизации. Общепринято, что задача факторизации трудно решается на классическом компьютере. Однако, быстрый алгоритм факторизации, разработанный Шором для квантового компьютера, мог бы послужить для взлома RSA.
Именно это практического применение квантовых компьютеров — взлом криптографических кодов — стимулировало интерес к квантовым вычислениям и квантовой информации.
Заключение.
Вот мы и рассмотрели исторические корни квантовых вычислений и квантовой информации. Конечно, с ростом и развитием этой области из нее выделились многие самостоятельные подразделы исследований, и вот уже о них, а так же конкретно о квантовых вычислениях и квантовой теории информации, я бы и хотел поговорить далее.