Practical Cryptography for Developers
master-zh
master-zh
  • Welcome
  • 前言
  • 密码学——概述
  • 哈希函数
    • 加密哈希和碰撞
    • 哈希函数:应用场景
    • 安全哈希算法
    • 哈希函数——示例
    • 练习:计算哈希值
    • 工作量证明(Proof-of-Work)哈希函数
  • MAC 和密钥派生
    • HMAC 与密钥派生
    • HMAC 计算——示例
    • 练习:计算 HMAC
    • KDF: Deriving Key from Password
    • PBKDF2
    • Modern Key Derivation Functions
    • Scrypt
    • Bcrypt
    • Linux crypt()
    • Argon2
    • Secure Password Storage
    • Exercises: Password Encryption
  • Secure Random Generators
    • Pseudo-Random Numbers - Examples
    • Secure Random Generators (CSPRNG)
    • Exercises: Pseudo-Random Generator
  • Key Exchange and DHKE
    • Diffie–Hellman Key Exchange
    • DHKE - Examples
    • Exercises: DHKE Key Exchange
  • Encryption: Symmetric and Asymmetric
  • Symmetric Key Ciphers
    • Cipher Block Modes
    • Popular Symmetric Algorithms
    • The AES Cipher - Concepts
    • AES Encrypt / Decrypt - Examples
    • Ethereum Wallet Encryption
    • Exercises: AES Encrypt / Decrypt
    • ChaCha20-Poly1305
    • Exercises: ChaCha20-Poly1305
  • Asymmetric Key Ciphers
    • The RSA Cryptosystem - Concepts
    • RSA Encrypt / Decrypt - Examples
    • Exercises: RSA Encrypt / Decrypt
    • Elliptic Curve Cryptography (ECC)
    • ECDH Key Exchange
    • ECDH Key Exchange - Examples
    • Exercises: ECDH Key Exchange
    • ECC Encryption / Decryption
    • ECIES Hybrid Encryption Scheme
    • ECIES Encryption - Example
    • Exercises: ECIES Encrypt / Decrypt
  • Digital Signatures
    • RSA Signatures
    • RSA: Sign / Verify - Examples
    • Exercises: RSA Sign and Verify
    • ECDSA: Elliptic Curve Signatures
    • ECDSA: Sign / Verify - Examples
    • Exercises: ECDSA Sign and Verify
    • EdDSA and Ed25519
    • EdDSA: Sign / Verify - Examples
    • Exercises: EdDSA Sign and Verify
  • Quantum-Safe Cryptography
    • Quantum-Safe Signatures - Example
    • Quantum-Safe Key Exchange - Example
    • Quantum-Safe Asymmetric Encryption - Example
  • More Cryptographic Concepts
    • Digital Certificates - Example
    • TLS - Example
    • One-Time Passwords (OTP) - Example
  • Crypto Libraries for Developers
    • JavaScript Crypto Libraries
    • Python Crypto Libraries
    • C# Crypto Libraries
    • Java Crypto Libraries
  • Conclusion
Powered by GitBook
On this page
  • Quantum-Safe and Quantum-Broken Crypto Algorithms
  • ECC Cryptography and Most Digital Signatures are Quantum-Broken!
  • Hashes are Quantum Safe
  • Symmetric Ciphers are Quantum Safe
  • Post-Quantum Cryptography
  • Hash-Based Public-Key Cryptography
  • Code-Based Public-Key Cryptography
  • Lattice-Based Public-Key Cryptography
  • Zero-Knowledge Proof-Based
  • Multivariate-Quadratic-Equations Public-Key Cryptography
  • Quantum-Resistant Cryptography - Libraries
  • SPHINCS+ Signatures in Python
  • NewHope Key Exchange in Python

Was this helpful?

Quantum-Safe Cryptography

PreviousExercises: EdDSA Sign and VerifyNextQuantum-Safe Signatures - Example

Last updated 5 years ago

Was this helpful?

Quantum computers are ...

  • TODO

  • TODO

See this page:

  • TODO

Quantum computing is a model of computing based on the quantum physics, which works differently than classical computers and can do things that classical computers can’t, such as breaking RSA and ECC efficiently. Quantum computers are not "faster computers" and they are not all-powerful and cannot do any computing job faster. Quantum computers are very efficient for certain problems and quite weak for others.

It is well known in computer science that quantum computers will break some cryptographic algorithms, especially the public-key cryptosystems like RSA, ECC and ECDSA that rely on the IFP (integer factorization problem), the DLP (discrete logarithms problem) and the ECDLP (elliptic-curve discrete logarithm problem). Quantum algorithms will not be the end of cryptography, because:

  • Only some cryptosystems are quantum-unsafe (like RSA, DHKE, ECC, ECDSA and ECDH).

  • Some cryptosystems are quantum-safe and will be only slightly affected (like cryptographic hashes, MAC algorithms and symmetric key ciphers).

Let's discuss this in details.

Quantum-Safe and Quantum-Broken Crypto Algorithms

Most cryptographic hashes (like SHA2, SHA3, BLAKE2), MAC algorithms (like HMAC and CMAK), key-derivation functions (bcrypt, Scrypt, Argon2) are basically quantum-safe (only slightly affected by quantum computing).

  • Use 384-bits or more to be quantum-safe (256-bits should be enough for long time)

Symmetric ciphers (like AES-256, Twofish-256) are quantum-safe.

  • Use 256-bits or more as key length (don't use 128-bit AES)

Most popular public-key cryptosystems (like RSA, DSA, ECDSA, EdDSA, DHKE, ECDH, ElGamal) are quantum-broken!

  • Most digital signature algorithms (like RSA, ECDSA, EdDSA) are quantum-broken!

  • Quantum-safe signature algorithms and public-key cryptosystems are already developed (e.g. lattice-based or hash-based signatures), but are not massively used, because of longer keys and longer signatures than ECC.

...

Quantum-Resistant Crypto Algorithms

...

ECC Cryptography and Most Digital Signatures are Quantum-Broken!

...

A k-bit number can be factored in time of order O(k^3) using a quantum computer of 5k+1 qubits (using Shor's algorithm).

256-bit number (e.g. Bitcoin public key) can be factorized using 1281 qubits in 72*256^3 quantum operations.

  • ~ 1.2 billion operations == ~ less than 1 second using good machine

ECDSA, DSA, RSA, ElGamal, DHKE, ECDH cryptosystems are all quantum-broken

Conclusion: publishing the signed transactions (like Ethereum does) is not quantum safe -> avoid revealing the ECC public key

Hashes are Quantum Safe

Cryptographic hashes (like SHA2, SHA3, BLAKE2) are considered quantum-safe:

  • On theory it might take 2^85 quantum operations to find SHA256 / SHA3-256 collision, but in practice it may cost significantly more.

Conclusion: SHA256 / SHA3-256 are most probably quantum-safe

  • SHA384, SHA512 and SHA3-384, SHA3-512 are quantum-safe

...

Symmetric Ciphers are Quantum Safe

...

Most symmetric ciphers (like AES and ChaCha20) are quantum-safe:

  • [Grover's algorithm]([[[[[[https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm)](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm))](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm)](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm)))](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm)](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm))](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm)](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm))))](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm)](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm))](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm)](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm)))](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm)](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm))](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm)](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm)))))](https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29%29%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29%29%29%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29%29%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29%29%29%29%29)\) finds AES secret key using √𝑁 quantum operations

AES-256 in the post-quantum era is like AES-128 before

  • 128-bits or less symmetric ciphers are quantum-attackable

Conclusion: 256-bit symmetric ciphers are generally quantum safe

  • AES-256, ChaCha20-256, Twofish-256, Camellia-256 are considered quantum-safe

Post-Quantum Cryptography

...

Post-quantum signature scheme XMSS:

  • Post-quantum key agreement schemes McEliece and NewHope

Hash-Based Public-Key Cryptography

...

Code-Based Public-Key Cryptography

...

Lattice-Based Public-Key Cryptography

...

GLYPH signatures (lattice-based Ring-LWE Lattice, Ring-LWE, Ring Learning with Errors)

NewHope

XMSS

NTRU: NTRUEncrypt and NTRUSign

Zero-Knowledge Proof-Based

Multivariate-Quadratic-Equations Public-Key Cryptography

...

Quantum-Resistant Cryptography - Libraries

The quantum-safe cryptography is still emerging, not mature, and still not widely supported by the most crypto-libraries and tools like Web browsers, OpenSSL, OpenSSH, etc. This is a list of well developed quantum crypto algorithm libraries:

SPHINCS+ Signatures in Python

NewHope Key Exchange in Python

See

See

On traditional computer, finding a collision for 256-bit hash takes √2^256 steps (using the ) -> SHA256 has 2^128 crypto-strength

Quantum computers might find hash collisions in ∛2^256 operations (see ), but this is disputed (see [Bernstein 2009] -

Quantum era will double the key size of the symmetric ciphers, see

Quantum-Safe key agreement:

JS XMSS -

Post-quantum signatures and key agreements (XMSS, McEliece, NewHope):

QC-MDPC and libPQC are quantum-broken:

Implementation in Go:

BLISS -

Implementation in Go:

Go implementation:

Python implementation:

Python implementation:

Python implementation:

PICNIC -

Rainbow:

liboqs (Open Quantum Safe) -

Bouncy Castle PQC -

https://ianix.com/pqcrypto/pqcrypto-deployment.html
https://en.wikipedia.org/wiki/Post-quantum_cryptography
http://www.theory.caltech.edu/~preskill/pubs/preskill-1996-networks.pdf
birthday attack
the BHT algorithm
http://cr.yp.to/hash/collisioncost-20090823.pdf
http://cr.yp.to/codes/grovercode-20100303.pdf
https://en.wikipedia.org/wiki/CECPQ1
https://ianix.com/pqcrypto/pqcrypto-deployment.html
https://pqcrypto.org
https://tools.ietf.org/html/rfc8391
https://www.npmjs.com/package/xmss
https://github.com/randombit/botan
https://eprint.iacr.org/2016/858.pdf
https://github.com/AidosKuneen/glyph
http://bliss.di.ens.fr
https://github.com/HcashOrg/bliss/blob/master/demo_test.go
https://github.com/Yawning/newhope
https://github.com/scottwn/PyNewHope
https://github.com/anupsv/NewHope-Key-Exchange
https://github.com/theQRL/QRL/blob/master/src/qrl/crypto/xmss.py
https://en.wikipedia.org/wiki/NTRUEncrypt
https://github.com/Microsoft/Picnic
https://github.com/bcgit/bc-java/tree/master/core/src/main/java/org/bouncycastle/pqc/crypto/rainbow
https://github.com/open-quantum-safe/liboqs
https://github.com/bcgit/bc-java/tree/master/core/src/main/java/org/bouncycastle/pqc/crypto
https://github.com/sphincs/pyspx
https://pypi.org/project/PySPX
https://github.com/anupsv/NewHope-Key-Exchange
https://github.com/scottwn/PyNewHope