AES Algorithm

A quantum-safe symmetric key encryption, and fast due to the block cipher techniques used. 

• Convert to State Array
• Transformations (and inverses)
• AddRoundKey
• SubBytes
• ShiltRows
• MixColumns
• Key Expansion

1. Convert to state array

2a. AddRoundKey

2b. SubBytes (S-box)

for index 55, the s-box value is fc

2c. ShiftRows

2d. MixColumns

3. Key Expansion (new round key)

#AES round key (128 bits)

current round key = w0, w1, w2, w3 (column, vertical)

w0=column 1, w1 = c.2, w2 = c.3, w3 = c.4

g(w3) calculation:

   1) shift left, 2) apply s-box,

   3) add round constant (01,00,00,00)

new roundkey: w4, w5, w6, w7

   w4 = w0 xor g(w3), w5 = w4 xor w1,

   w6 = w5 xor w2,    w7 = w6 xor w3 

 

Example

Calculation of round key (round 1)

w3 = 01 02 14 13, shift left = 02 14 13 01, after s-box 77 fa 7b 7c, after + 1000h = 76 fa 7b 7c.

so g(w3) = 76 fa 7b 7c, then w4 = wo xor g(w3) = 74, fb 6a 7c (column one of round 1 key)

 

Algorithm

10 round = 128-bit keys

12 round = 196-bit keys

14 round = 256-bit keys 

AES-256 is considered to be quantum resistant. 

References:

1. Rijndael-Inspector - Rijndael_Animation_v4-eng.exe|swf - A flash application

2. AES-example.pdf

3. Zhou-Xuan-fulltext.pdf (Univ. of Manchester)

PGP Encryption

Developed by Phil Zimmerman in 1991. It combines symmetric, asymmetric (public key) encryption, hash, and digital signature all together providing confidentiality, integrity, and authentication. Good for email. The algorithm:

At the sender (Alice) side: 

1. Alice: Message M is hashed
2. Sign (encrypt) the hash value with her private key (EP)
3. Compress (zip) the message + signed hash value
4. Use a session key Ks to encrypt zipped output (ES)
5. Use Bob's public key to encrypt session key (EP)
6. Send encrypted message and encrypted session key 

At the recipient (Bob) side:

1. Use Bob's private key to decrypt session key (DP)
2. Use session key Ks to decrypt the zipped message
3. unzip, got message and signed hash value
4. Use Alice's public key to decrypt the hash value 
5. Computing hash value for the message received
6. Compare with hash value Alice computed.

Below are the PGP diagram:

Mathematically:

Note:

Image copyright: Author of this post. Free to use but reference is required. 

The Rise and Fall of BlackBerry (phones)

Blackberry with its iconic on device full keyboard was a symbol of c-suite executives and other business professionals, the list also include the US Presidents. The reason for the wide adoption (some 10 years ago) was not only the beautiful design but also its security. 

Blackberry uses an end-to-end encryption called PGP. The servers are managed by a company (or a third party). When Alice sends a message, the message is firstly compressed. PGP then creates a (one time) random session key to encrypt the compressed message. The session key is then encrypted using Bob's public key and send to Bob. Bob uses his private key to decrypt the session key and uses it to decrypt the message. 

It is important to note that the encryption and decryption are done on Blackberry devices, we call end-to-end. Since PGP is strong encryption, men in the middle cannot decipher and read the message. Due to the strong security feature, Blackberry quickly gained the market popularity. 

Because PGP is too strong to break up, it prevents some countries or regimes to spy on their citizens. As a result, many countries banned to bring Blackberry to those countries. As a result, this beautiful device was quickly faded away. 

Some scientists believe the fall of Blackberry was not because its business malpractice. It was because the strong security and no back door. Technology may not always win. 

Final comments: 

1. The good news is PGP technology is still here and people can choose to use.  

2. Random number generation (RNG) is very important for the security of encryption key. Quantum RNG (QRNG) can guarantee the truly randomness. 

3. Compression is a form of encryption, usually symmetric, due to its fast speed. 

4. Learn more about PGP, visit Philip Zimmermann's website. 

Quantum Cryptography

Quantum cryptography is to address issues in crypto key distribution by using a principle guaranteed by the fundamental laws of physics. Once a recipient receives the temper-proof key, She can then use conventional crypto method to encrypt/decrypt the message. So quantum cryptography is the hybrid approach of modern cryptography but the keys are exchanged via the quantum channel commonly called quantum key distribution (QKD). 

Fig. Quantum Cryptography

According to physics, a quantum state is unobservant. If an eavesdropper observes a quantum sate, it changes so as to cause errors at the destination. So the sending and receiving parties know the communication was compromised. Only validated keys are secure and used for further encryption/decryption. 

Image copyright: Author of this post. Free to use but reference is required. 

Quantum-safe Cryptography

The current public key encryption is mostly based on prime numbers. With the advancement of computer especial quantum computers, the threat to the existing crypto algorithms is becoming imminent. 

The need to increase the key length keeps growing. A new type of post-quantum or quantum resistant algorithms is under-development. 

Why should people worry about the existing encryption algorithms?

In WWII, German mathematicians claimed that the Enigma machine, based on simple substitution method, would require 100 years to solve. Alan Turing used less than 6 months built a Bombe at Bletchley Park. Bombe was able to crack 3,000 German encrypted message a day initially and later amounted to 2.5 million encrypted messages. 

Fig. Alan Turing's Bombe 

Today, those messages can be deciphered in a fraction of microseconds running a small program using the statistical analysis method. (The author has programmed one in Python.)

In 1977, RSA issued a challenge in an article "A new kind of cipher that would take millions of years to break". The so-called 40 quadrillion years problem (428 bit key) was solved in 1994 after a 6 months of work. 

RSA algorithm with key length 1024 bit to 4096 bit is considered strong and "unbreakable" today. Peter Shor @MIT proposed an algorithm that can solve such "unsolvable" programs on quantum computers. 

Imagine people store the encrypted data now and wait 10 years or so to decrypt when the powerful quantum computers are ready. Should you worry?

Crypto Keys and Key Exchange

In Crypto, encryption and decryption keys need to be well guided. In classical cryptography, A secret key is used. Key distribution is difficult.

British GCHQ (now NCSC) introduced the public key cryptography concept. A third party (CA) is responsible for key creation and distribution. This makes key exchange convenient. 

Fig. Public Key Cryptography

RSA public key encryption is based on two large prime numbers. Factor the product of those numbers seems simple but requires tremendous amount of time, or in many cases important. 

Since public key algorithms such as RSA require complex computations, it is slow. As a result, people usually do not use it directly for encrypting message (a large amount of data). Instead, use it to exchange short session keys for secret key algorithms (aka symmetric algorithms) such as AES. 

Note:

Image copyright: Author of this post. Free to use but reference is required. 

Cryptography Basics

Cryptography is to hide information before sending and reveal it at recipient. Figure 1 is an illustration of encryption and decryption process.  

Fig. Crypto Basics

Alice uses an encryption key to encryption the plaintext. The encrypted text (ciphertext) is then sent to Bob. Bob decrypts the ciphertext with a key to reveal the plaintext Alice sent to him. 

Here the encryption key and decryption key (could be one) are important. They need to be strong and convenient. 

Common secret key (one key) encryption algorithm: DES (1976, 56 bits key length, vulnerabilities exist), AES (256-bit key length, current).

Common public key (two keys) encryption algorithm: RSA (current).

Ideally, keys should keep changing to make them impossible to guess or deduce. Random numbers are used to generate keys but only truly random number are considered ideal. 

Quantum Random Number Generators (RNG) use the randomness of photons, it is impossible for observing or predicting the outcome.   

Note:

Image copyright: Author of this post. Free to use but reference is required. 

NSF Award Notice for Award - Quantum Crypto and Algorithms - May 6, 2020

This project promotes the progress of science in quantum computing algorithms and cryptologic techniques in order to improve security of encrypted information, which will have national security and defense applications.

Currently, the commonly used encryption algorithms such as RSA are considered “unbreakable” by modern digital computers due to the complexity of computation that would be required. However, this may change in the next decade or so in light of advances in quantum science.  Quantum mechanics has led to the discovery that considerable numbers of states can be manipulated at the same time thus significantly reduce the amount of time in processing. New quantum computers have shown the baseline of “quantum supremacy” in solving problems that classical digital computers practically cannot.

Efficient quantum algorithms are key to enable computer scientists to take full advantage of the next generation of practical quantum computers to efficiently solve today’s unsolvable problems. Advances in quantum science in both breaking and securing the encryptions are paramount for national security and preventing adversaries from taking advantage of critical areas of national defense.

This project seeks to discover efficient quantum cryptologic methods (i.e. the art of revealing the secret) and secure quantum cryptographic techniques (i.e. the science of making the secret more secure). This project not only exhibits the excellence in scientific research, but also supports diversity and inclusion goals for the benefit of society.