7,129
个编辑
更改
→密码学
==潜在应用==
==潜在应用==
===密码学===
===密码学===
'''整数因式分解 Integer factorization'''是'''公钥密码系统Public key cryptographic systems'''安全性的基础，如果一个大整数是几个素数的乘积（例如，两个300位素数的乘积）<ref>{{cite journal |last=Lenstra |first=Arjen K. |url=http://sage.math.washington.edu/edu/124/misc/arjen_lenstra_factoring.pdf |title=Integer Factoring |journal=Designs, Codes and Cryptography |volume=19 |pages=101–128 |year=2000 |doi=10.1023/A:1008397921377 |issue=2/3 |url-status=dead |archiveurl=https://web.archive.org/web/20150410234239/http://sage.math.washington.edu/edu/124/misc/arjen_lenstra_factoring.pdf |archivedate=2015-04-10 }}</ref>，那么在普通计算机上计算是不可行的。相比之下，量子计算机可以有效地解决这个问题，使用'''肖尔Shor算法'''来寻找它的因子。这种能力将使量子计算机能够破解目前使用的许多密码系统，也就是说，可以用多项式时间（整数位数）算法'''来解决这个问题。特别是目前流行的公钥密码算法大多是基于大整数因式分解或离散对数问题的困难性，而这两个问题都可以用'''肖尔Shor算法'''来解决。尤其是'''RSA、Diffie-Hellman和椭圆曲线Diffie-Hellman算法'''可能会被破解，它们一般用于保护安全网页、加密电子邮件和许多其他类型的数据。破解这些算法将对电子隐私和安全产生重大影响。
'''整数因式分解 Integer factorization'''是'''公钥密码系统 Public key cryptographic systems'''安全性的基础，如果一个大整数是几个素数的乘积（例如，两个300位素数的乘积）<ref>{{cite journal |last=Lenstra |first=Arjen K. |url=http://sage.math.washington.edu/edu/124/misc/arjen_lenstra_factoring.pdf |title=Integer Factoring |journal=Designs, Codes and Cryptography |volume=19 |pages=101–128 |year=2000 |doi=10.1023/A:1008397921377 |issue=2/3 |url-status=dead |archiveurl=https://web.archive.org/web/20150410234239/http://sage.math.washington.edu/edu/124/misc/arjen_lenstra_factoring.pdf |archivedate=2015-04-10 }}</ref>，那么在普通计算机上计算是不可行的。相比之下，量子计算机可以有效地解决这个问题，使用'''肖尔Shor算法'''来寻找它的因子。这种能力将使量子计算机能够破解目前使用的许多密码系统，也就是说，可以用多项式时间（整数位数）算法来解决这个问题。特别是目前流行的公钥密码算法大多是基于大整数因式分解或离散对数问题的困难性，而这两个问题都可以用肖尔Shor算法来解决。尤其是'''RSA、Diffie-Hellman和椭圆曲线Diffie-Hellman算法'''可能会被破解，它们一般用于保护安全网页、加密电子邮件和许多其他类型的数据。破解这些算法将对电子隐私和安全产生重大影响。
然而，其他密码算法似乎并没有被那些算法破解。<ref name="pqcrypto_survey">{{cite book |doi=10.1007/978-3-540-88702-7_1 |chapter=Introduction to post-quantum cryptography |title=Post-Quantum Cryptography |year=2009 |last1=Bernstein |first1=Daniel J. |journal=Nature |volume=549 |issue=7671 |pages=1–14 |pmid=28905891 |isbn=978-3-540-88701-0 }}</ref><ref>See also [http://pqcrypto.org/ pqcrypto.org], a bibliography maintained by Daniel J. Bernstein and [[Tanja Lange]] on cryptography not known to be broken by quantum computing.</ref>有些公钥算法是基于除整数分解和离散对数问题以外的问题，'''肖尔Shor算法'''并不适用于这些问题，例如McEliece密码体制基于编码理论中的一个问题。<ref name="pqcrypto_survey" /><ref>{{cite journal |last1=McEliece |first1=R. J. |title=A Public-Key Cryptosystem Based On Algebraic Coding Theory |journal=DSNPR |date=January 1978 |volume=44 |pages=114–116 |url=http://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF |bibcode=1978DSNPR..44..114M }}</ref>基于格的密码体制也不能被量子计算机破解，寻找一个多项式时间算法来解决'''二面体隐子群问题Dihedral hidden subgroup problem'''，将打破许多基于'''格'''的密码体制，这是一个充分研究的开放性问题。<ref>{{cite journal |last1=Kobayashi |first1=H. |last2=Gall |first2=F.L. |title=Dihedral Hidden Subgroup Problem: A Survey |year=2006 |journal=Information and Media Technologies |volume=1 |issue=1 |pages=178–185 |doi=10.2197/ipsjdc.1.470 |doi-access=free }}</ref>已经证明，用'''Grover算法'''来暴力破解对称（密钥）算法所需的时间大约相当于基础加密算法的2<sup>n/2</sup>次调用，而在经典情况下大约需要2<sup>n</sup>，<ref name=bennett_1997>{{cite journal |last1=Bennett |first1=Charles H. |last2=Bernstein |first2=Ethan |last3=Brassard |first3=Gilles |last4=Vazirani |first4=Umesh |title=Strengths and Weaknesses of Quantum Computing |journal=SIAM Journal on Computing |date=October 1997 |volume=26 |issue=5 |pages=1510–1523 |doi=10.1137/s0097539796300933 |arxiv=quant-ph/9701001 |bibcode=1997quant.ph..1001B }}</ref>这意味着对称密钥长度将有效地减半：AES-256应对使用'''Grover算法'''的攻击的安全性与AES-128应对经典暴力搜索的安全性相同（参见密钥大小）。
然而，其他密码算法似乎并没有被那些算法破解。<ref name="pqcrypto_survey">{{cite book |doi=10.1007/978-3-540-88702-7_1 |chapter=Introduction to post-quantum cryptography |title=Post-Quantum Cryptography |year=2009 |last1=Bernstein |first1=Daniel J. |journal=Nature |volume=549 |issue=7671 |pages=1–14 |pmid=28905891 |isbn=978-3-540-88701-0 }}</ref><ref>See also [http://pqcrypto.org/ pqcrypto.org], a bibliography maintained by Daniel J. Bernstein and [[Tanja Lange]] on cryptography not known to be broken by quantum computing.</ref>有些公钥算法是基于除整数分解和离散对数问题以外的问题，肖尔Shor算法并不适用于这些问题，例如McEliece密码体制基于编码理论中的一个问题。<ref name="pqcrypto_survey" /><ref>{{cite journal |last1=McEliece |first1=R. J. |title=A Public-Key Cryptosystem Based On Algebraic Coding Theory |journal=DSNPR |date=January 1978 |volume=44 |pages=114–116 |url=http://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF |bibcode=1978DSNPR..44..114M }}</ref>基于格的密码体制也不能被量子计算机破解，寻找一个多项式时间算法来解决'''二面体隐子群问题 Dihedral hidden subgroup problem'''，将打破许多基于'''格'''的密码体制，这是一个充分研究的开放性问题。<ref>{{cite journal |last1=Kobayashi |first1=H. |last2=Gall |first2=F.L. |title=Dihedral Hidden Subgroup Problem: A Survey |year=2006 |journal=Information and Media Technologies |volume=1 |issue=1 |pages=178–185 |doi=10.2197/ipsjdc.1.470 |doi-access=free }}</ref>已经证明，用[[Grover算法]]来暴力破解对称（密钥）算法所需的时间大约相当于基础加密算法的2<sup>n/2</sup>次调用，而在经典情况下大约需要2<sup>n</sup>，<ref name=bennett_1997>{{cite journal |last1=Bennett |first1=Charles H. |last2=Bernstein |first2=Ethan |last3=Brassard |first3=Gilles |last4=Vazirani |first4=Umesh |title=Strengths and Weaknesses of Quantum Computing |journal=SIAM Journal on Computing |date=October 1997 |volume=26 |issue=5 |pages=1510–1523 |doi=10.1137/s0097539796300933 |arxiv=quant-ph/9701001 |bibcode=1997quant.ph..1001B }}</ref>这意味着对称密钥长度将有效地减半：AES-256应对使用[[Grover算法]]的攻击的安全性与AES-128应对经典暴力搜索的安全性相同（参见密钥大小）。
'''量子密码学 Quantum cryptography'''可以实现公开密钥加密的一些功能。因此，面对量子黑客攻击时，基于量子的加密系统可能比传统系统更安全。<ref>{{cite news |last1=Katwala |first1=Amit |title=Quantum computers will change the world (if they work) |url=https://www.wired.co.uk/article/quantum-computing-explained |work=Wired UK |date=5 March 2020 }}</ref>
'''量子密码学 Quantum cryptography'''可以实现公开密钥加密的一些功能。因此，面对量子黑客攻击时，基于量子的加密系统可能比传统系统更安全。<ref>{{cite news |last1=Katwala |first1=Amit |title=Quantum computers will change the world (if they work) |url=https://www.wired.co.uk/article/quantum-computing-explained |work=Wired UK |date=5 March 2020 }}</ref>
<br>
===量子搜索===
===量子搜索===