The Risks of a Post Quantum World …
The Risks of a Post Quantum World …
I appreciate that, at the current time, it is difficult to look towards further than next week, but things will resume in some way, and we must plan like never before for the future. And like never before we do need to understand the core risks to our future, and make plans to mitigate them.
And so I’ve been reading up on the Utimaco offering [here]:
I love their marketing focus, and they go straight for it, without messing around:
Quantum computers will decimate the security infrastructure of the digital economy — the only question is when
But wait? What is being broken? Well the target is RSA and Elliptic Curve methods, and which are the core of most key exchange methods, and in proving identity and signatures. But it’s a long way off, isn’t it? Well, they have an answer for that, in that some industries have long product life cycles. This includes smart metering, critical infrastructures and IoT, and which are often the things that we leave and care little about. It is thus a ticking time bomb, that cause a major security flaw in the fabric of the Internet. An interesting graphic shows that NIST will not have a standard ready for PQC (Post Quantum Cryptography) by 2023, and where RSA-2028 (the basis of most digital certificate) could be broken by 2027:
So, we should perhaps be thinking about a migration path for those devices which have long lifetimes, and which cannot be easily updated.
NIST and PQC
In January 2019, NIST took 69 submissions for Post-Quantum Cryptography (PQC) standardization and created a shorter-list of 29. This process aims to address the major problem of quantum computers cracking discrete logarithms, elliptic curve cryptography (eg ECDH for key exchange and ECDSA for digital signatures) and the factorization of prime numbers (eg RSA).
Through the standardization of AES and SHA-3, NIST has shown a leadership in defining standards and which have been extensively peer reviewed and assessed. With PCQ they are searching for a standard for public key encryption, key exchange and digital signing, which will scale into the future, and be robust against both standard attacks and post-quantum attacks.
There are two core focus areas around public key encryption/key exchange and digital signatures, and the announcement is here:
My tips for the winner are Classic McEllice, New Hope and NTRU for public key encryption, and GeMSS, Rainbow and SPHINCS+for digital signatures.
The next round will focus on the performance of the methods, especially in how limited processing devices cope. A key focus is thus on IoT devices, and with devices that have limited sources of processing power, memory and energy sources. These methods are often known as light-weight cryptography.
The core methods mainly fall into four main areas:
- Lattice-based cryptography [Lattice] — This classification shows great potential and is leading to new cryptography methods, such as for fully homomorphic encryption, and code obfuscation.
- Code-based cryptography [McEliece] — This classification was created in 1978 with the McEliece cryptosystem but has barely been using in real applications. The McEliece method uses linear codes that are used in error correcting codes, and involves matrix-vector multiplication. An example of a linear code is Hamming code.
- Multivariate polynomial cryptography [UOV] — This classification involves the difficulty of solving systems of multivariate polynomials over finite fields. Unfortunately, many of the methods that have been proposed have already been broken.
- Hash-based signatures [GMSS] — This classification involves creating digital signatures using hashing methods. The drawback is that a signer needs to keep a track of all of the messages that have been signed, and that there is a limit to the number of signatures that can be produced. New methods, though, integrate into Merkle Trees, which allows for the signer to use the same keys to sign multiple entities.
NIST are planning to hold PQC Standardization Conference in August 2019, and the announcement of the next phase will happen after that.
Public key methods
Public key methods provide us with ways of both authenticating the sender, and the integrity of the method. Unfortunately most of the methods which are used to create these signatures, such as with prime number factorization (as with RSA) and in elliptic curve methods, will be cracked with quantum computers. This article outlines some of the hash-based signature methods which could be used as a basis for hash-based signatures.
Many of the problems we see on the Internet relate to the lack of trust within transactions. The emails you receive and the Web sites that you visit often have very little trust built into them. For trust we examine the email address of the sender, but anyone can fake that address. So increasingly we create digital signatures, and where we sign our messages with a private key. In this way, we can check for authentication, integrity and non-repudiation.
With this Alice creates a key-pair: a public key and a private key. She then takes a hash of the message, and encrypts this hash with her private key (this is her signature), and passes the message and the signature to Bob. Bob then reads the message and takes a hash of it. He then decrypts Alice’s signature with her public and checks the hashes. If they match, he knows that she signed it, and that it has not been changed along the way:
Currently, we often use RSA, DSA and ECDSA to sign our messages. These are based on the difficulty of finding out the factors of a number and on the processing of discrete logarithms. At the current time these methods are computationally hard problems, but with quantum computers, they become much easier. This was shown by Peter Shor who illustrated that it was possible to crack them in polynomial time.
Of all the methods that are being proposed, the hash-based methods look as if they have a good chance of success of creating quantum robust signatures. Lattice- and code-based methods are being researched, but the usage of hashing methods is already well defined and could provide the best alternative to the existing methods. Hashing methods, too, often bring other advantages, such as forward security, which means that a key which is cracked will not reveal all the previous keys.
New Hope
One of the favouriates in winning the race is New Hope. It is a quantum robust key-exchange method, and is based on the Ring-Learning-with-Errors (Ring-LWE) problem. For this, Alice generates a message, and passes it to Bob, and Bob also generates a message and passes to Alice. After they process the message, they will end up with the same shared key.
With quantum computers, many of the current public key encryption methods, such as RSA, are at threat, as quantum computers can factorize the prime numbers used, within a reasonable time limit. So the risk is that anything which is encrypted now, will be able to be decrypted within the next 20 years.
NewHope was defined by Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe in this [paper]. Google selected NewHope for an experiment to reduce the impact of quantum computers. With this they integrated into a special browser version (Canary) and is integrated into HTTPs communications. The method is named “Ring Learning With Errors” (Ring-LWE) and is a key exchange method which would be robust in the age of quantum computing. Ring-LWE has no known weaknesses within a quantum computing era.
Ring-LWE uses a mixture of current key exchange methods and quantum robust methods, and thus an intruder would have to defeat both methods in order to crack the encrypted communication. It is currently only being used in a few Google domains, and only when users are using Chrome Canary, where users can see a string of “CECPQ1” within the browser’s security panel (under Key-exchange heading):
The method is defined as [paper]:
Alice initially generates a 256-bit seed value (seed), and then uses the Shake_128 hashing method to create the polynomial coefficients (a).
Next Alice generates secret values (sA) and error values (eA).
Alice then creates b_A parameters using a, s_A and e_A:
b_A=a×s_A+e_A
This value is passed to Bob, along with the seed.
From the seed value, Bob can recreate a.
Bob goes through a similar process to Alice, and sends Alice back two values (u,r). After this they can create the same shared key. The key is generated from a SHA-256 hash of a value (v).
For NewHope we define q = 12,289 and with NewHope512 we set n = 512. For NewHope1024 we select n = 1024. NewHope512 has a brute force security level equivalent to 128-bit AES, and NewHope1024 has the strength of 256-bit AES.
A sample run is:
Alice's message is (showing first 100 characters) [7104L, 11469L, 12754L, 9818L, 6103L, 2336L, 4494L, 4581L, 8702L, 1033L, 1638L, 2617L, 1507L, 10512L, 1147L, 8945L, 5384L, 2211L, 11003L, 10251L, 5612L, 3475L, 10105L, 2162L, 5933L, 2558L, 2550L, 5477
Alice Seed: 678ce7042916695f2ff0cbfe38a06f58Bob's message is (showing first 100 characters) [3L, 3L, 3L, 2L, 3L, 2L, 3L, 2L, 3L, 2L, 2L, 3L, 2L, 1L, 0L, 2L, 2L, 3L, 3L, 1L, 2L, 3L, 3L, 2L, 1L, 1L, 0L, 3L, 1L, 3L, 2L, 2L, 2L, 3L, 1L, 0L, 1L, 3L, 2L, 0L, 2L, 3L, 1L, 2L, 2L, 1L, 0L, 3L, 0L, 1L,Alice's key is
[200L, 167L, 209L, 244L, 161L, 207L, 196L, 242L, 27L, 239L, 148L, 211L, 8L, 94L, 80L, 197L, 75L, 16L, 191L, 241L, 157L, 179L, 122L, 60L, 185L, 242L, 88L, 120L, 108L, 68L, 85L, 200L]Bob's key is
[200L, 167L, 209L, 244L, 161L, 207L, 196L, 242L, 27L, 239L, 148L, 211L, 8L, 94L, 80L, 197L, 75L, 16L, 191L, 241L, 157L, 179L, 122L, 60L, 185L, 242L, 88L, 120L, 108L, 68L, 85L, 200L]
Successful handshake! Keys match.
We have generated 32 byte integers (32x8 bits = 256 bits). An outline of Ring LWE is:
And a demonstration of Ring LWE is given here.
McEliece Method
Another serious contender dates back to 1978. In a lesson for any modern researcher, in just two pages, Robert McEliece outlined a public key encryption method based on Algebraic Coding — now known as the McEliece Cryptography method [paper]. It is an asymmetric encryption method (with a public key and a private key), and, at the time, looked to be a serious contender for a trapdoor method. Unfortunately, RSA became the King of the Hill, and the McEliece method was pushed to the end of the queue for designers.
It has basically drifted for nearly 40 years. But, as an era of quantum computers is dawning, it is now being reconsidered, as it is seen to be immune to attacks using Shor’s algorithm [here].
The McEliece method uses code-based cryptography. Its foundation is based on the difficulty in decoding a general linear code, and is generally faster than RSA for encryption and decryption. Within it we have a probabilistic key generation method, which is then used to produce the public and the private key. The keys are generated with the parameters of n, k and T.
The keys are generated with the parameters of n, k and t. With this we created an [n,k] matrix of codes, and which is able to correct t errors. In his paper, McEliece defines defines n=1024, k=524, t=50, and which gives a public key size of 524x(1024–524) = 262,000 bits. In example above we use k=1608, N=2048 and T=40, which gives a public key size of 1608x(2048–40) — 3,228,864 bits. For quantum robustness it is recommended that N is 6960, k is 5,412 and t is 119 (giving a large key size of 8,373,911 bits.
Here is a demo of the encryption [here] and provides a simple explanation of how the key is created for McEliece crypto. It uses a (7,4) Hamming code with one-bit error correction. The following is an outline [here]:
This is based on the example [here]. We illustrate the process with a (7,4) Hamming code which corrects one error. The generator matrix is then:
1 0 0 0 1 1 0
G = 0 1 0 0 1 0 1
0 0 1 0 0 1 1
0 0 0 1 1 1 1
Bob then selectes a scrambler matrix (S):
1 1 0 1
S = 1 0 0 1
0 1 1 1
1 1 0 0
And also a permutation matrix:
0 1 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 1
P = 1 0 0 0 0 0 0
0 0 1 0 0 0 0
0 0 0 0 0 1 0
0 0 0 0 1 0 0
Bob public key then becomes the dot product of these matrices
1 1 1 1 0 0 0
G' = SGP = 1 1 0 0 1 0 0
1 0 0 1 1 0 1
0 1 0 1 1 1 0
Bob will use G’ as a public key, but S, G and P are secret. Next, for Alice to send a ciphered message to Bob, she converts the message into binary vectors of length k.
For a message of m Alice will create randomly a binary n-vector of weight t, and randomly places t 1’s in a zero vector of length n).
This is then sent to Bob:
y = mG’ + e
Bob then decrypts with:
yP−1=(mG′+e)P−1=mSG+eP−1=mSG+e′
A sample run is:
Message: [ 1. 1. 0. 1.]
G:
[[1 0 0 0 1 1 0]
[0 1 0 0 1 0 1]
[0 0 1 0 0 1 1]
[0 0 0 1 1 1 1]]
S:
[[1 1 0 1]
[1 0 0 1]
[0 1 1 1]
[1 1 0 0]]
P:
[[0 1 0 0 0 0 0]
[0 0 0 1 0 0 0]
[0 0 0 0 0 0 1]
[1 0 0 0 0 0 0]
[0 0 1 0 0 0 0]
[0 0 0 0 0 1 0]
[0 0 0 0 1 0 0]]
Result:
[[1 1 1 1 0 0 0]
[1 1 0 0 1 0 0]
[1 0 0 1 1 0 1]
[0 1 0 1 1 1 0]]Cipher: [ 0. 1. 1. 0. 1. 1. 0.]P^{-1}:
[[ 0. 0. 0. 1. 0. 0. 0.]
[ 1. 0. 0. 0. 0. 0. 0.]
[ 0. 0. 0. 0. 1. 0. 0.]
[ 0. 1. 0. 0. 0. 0. 0.]
[ 0. 0. 0. 0. 0. 0. 1.]
[ 0. 0. 0. 0. 0. 1. 0.]
[ 0. 0. 1. 0. 0. 0. 0.]]y': [ 1. 0. 0. 0. 1. 1. 1.]S^{-1}:
[[ 1. 1. 0. 1.]
[ 1. 1. 0. 0.]
[-0. 1. 1. 1.]
[ 1. 0. 0. 1.]]Decipher: [ 1. 1. 0. 1.]
NTRU
The NTRU (Nth degree TRUncated polynomial ring) public key method is a lattice-based method which is quantum robust. It uses the shortest vector problem in a lattice, and has an underpinning related to the difficulty of factorizing certain polynomials. This article outlines the method used to generate the public key (h).
With Lattice encryption, Bob and Alice agree to share N, p and q, and then Bob generates two short polynomials (f and g), and generates his key pair from this. Alice receives this, and she generates a random polynomial, and encrypts some data for Bob. Bob then decrypts the message with his private key. We generate the public and private key from N, p and q:
==== Bob generates public key =====
Values used:
N= 11
p= 3
q= 32
========Bob picks two polynomials (g and f):
f(x)= [-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1]
g(x)= [-1, 0, 1, 1, 0, 1, 0, 0, -1, 0, -1]====Now we determine F_p and F_q ===
F_p: [1, 2, 0, 2, 2, 1, 0, 2, 1, 2, 0]
F_q: [5, 9, 6, 16, 4, 15, 16, 22, 20, 18, 30]====And finally h====
f_q x g: [-5, -9, -1, -2, 11, 12, 13, 3, 22, 15, 16, 29, 60, 19, -2, -7, -36, -40, -50, -18, -30]
H (Bob's Public Key): [24, 19, 18, 28, 4, 8, 5, 17, 4, 17, 16]====Let's encrypt====
Alice's Message: [1, 0, 1, 0, 1, 1, 1]
Random: [-1, -1, 1, 1]
Encrypted message: [8, 2, 10, 23, 16, 7, 26, 2, 8, 3, 28]====Let's decrypt====
Decrypted message: [1, 0, 1, 0, 1, 1, 1]
NTRU is a asymmetric encryption and has been benchmarked as twice as fast as RSA to encrypt, and three times faster to decrypt. NTRU was the public key method which is not based on factorization (RSA) or discrete logs (Elliptic Curve).
The following is taken from Wikipedia and shows the test case [here]:
I have created a demonstrator here. An outline of the code [here]:
SPHINCS
For digital signatures SPHINCS looks to be one of the favouriates. It is a stateless hash-based signature scheme, which is quantum robust. It was proposed by Bernstein et al. in 2015 [paper]. SPHINCS+ 256 has a public key size of 1kB, a private key size of 1kB, and a signature of 41 kB. It has been shown to operate at speeds of hundreds of hashes per second on a 4-core 3.5GHz processor.
It uses WOTS and HORST for hash-based trees. The code uses a number of parameters:
- n — length of hash in WOTS / HORST (in bits)
- m — length of message hash (in bits)
- h — height of the hyper-tree
- d — layers of the hyper-tree
- w — Winternitz parameter used for WOTS signature
- tau — layers in the HORST tree (2^tau is no. of secret-key elements)
- k — number of revealed secret-key elements per HORST signature
In the example we use: n=256, m=512, h=2, d=1, w=4, tau=8, k=64.
The hashing method used of some of the operations is BLAKE, and Cha-cha is used to generate a random number.
A demonstration of this method is given here.
Rainbow — Oil and Vinegar (UOV)
The Ranbow method uses the Unbalanced Oil and Vinegar (UOV) scheme for a quantum robust cryptography method with asymmetric encryption. To explain its method, let’s take a simple example:
“Okay”, your teacher says, solve “x² + 2 x = 8”, and you quickly say “I think that x is equal to 2”.
Now the teacher says, “Solve: 2x + y = 1 and 3x + y = 7”,
And you quickly do a calculation and put up your hand … “I think x is 2 and y is 1”. “Well done”, says the teacher, “And now solve…
5 x+ 4y + 10 w + 9 z = 99
6 x + 3 y + 2 w + 3 z =38
8 x + 2 y + 7 w + z = 51
x + 9 y + 4 w + 6 z =57"
[The answer is below]
Things now get a bit difficult for you, as this is an NP-hard mathematical problem, where we would require significant computing power to solve large equations with many variables.
If we just have one variable, we can use the least mean squares method to compute the values. For example if we have:
x² + 2 x — 8 = 0
Then we can write a small Python program to solve this (8 = x² + 2x):
import numpy as npcoeff = [1,2,-8]
z = np.roots(coeff)
print z
The answer is [-4,2]. So trying -4 and 2 into this equation will solve it.
The multivariate polynomial problem is now being applied in quantum robust cryptography, where we create a trap door to allow us to quickly solve the n variables with m equations (which are multivariate polynomials).
One scheme that can be used is the Unbalanced Oil and Vinegar scheme and was created by J. Patarin. A signature is created with a number of equations:
y1 = f(x1, x2 … xn)
y2 = f(x1,x2 … xn)
…
ym= f(x1,x2 … xn)
where y1, y2, … ym is the message that is to be signed, and where x1, x2 … xn is the signature for the message.
So a simple example:
5 x+ 4y + 10 w + 9 z = 99
6 x + 3 y + 2 w + 3 z =38
8 x + 2 y + 7 w + z = 51
x + 9 y + 4 w + 6 z =57
The message is 99, 38, 51 and 57, and the signature is then 5, 4, 10 … 6.
A demonstrator of Oil and Vinegar is given here. The following provides an outline of the code, where we sign “Hello” with the private key and verify with the public key:
package rain;import java.math.BigInteger;
import java.security.SecureRandom;import org.bouncycastle.crypto.AsymmetricCipherKeyPair;
import org.bouncycastle.crypto.digests.SHA224Digest;
import org.bouncycastle.crypto.params.ParametersWithRandom;
import org.bouncycastle.pqc.crypto.DigestingMessageSigner;
import org.bouncycastle.pqc.crypto.rainbow.RainbowKeyGenerationParameters;
import org.bouncycastle.pqc.crypto.rainbow.RainbowKeyPairGenerator;
import org.bouncycastle.pqc.crypto.rainbow.RainbowParameters;
import org.bouncycastle.pqc.crypto.rainbow.RainbowSigner;public class rain {
public static void main(String args[]){SecureRandom keyRandom = new SecureRandom();
RainbowParameters params = new RainbowParameters();RainbowKeyPairGenerator rainbowKeyGen = new RainbowKeyPairGenerator();
RainbowKeyGenerationParameters genParam = new RainbowKeyGenerationParameters(keyRandom, params);rainbowKeyGen.init(genParam);AsymmetricCipherKeyPair pair = rainbowKeyGen.generateKeyPair();
org.bouncycastle.pqc.crypto.rainbow.RainbowPrivateKeyParameters priv = (org.bouncycastle.pqc.crypto.rainbow.RainbowPrivateKeyParameters) pair.getPrivate();
org.bouncycastle.pqc.crypto.rainbow.RainbowPublicKeyParameters pub = (org.bouncycastle.pqc.crypto.rainbow.RainbowPublicKeyParameters) pair.getPublic();
System.out.println("Random:"+new BigInteger(130, keyRandom).toString(32));
System.out.println("\n----Private Key----");System.out.println("Doc length:"+priv.getDocLength());
System.out.println("B1:");
showints(priv.getB1());
System.out.println("B2:");
showints(priv.getB2());
System.out.println("InvA1:");
showints(priv.getInvA1());
System.out.println("InvA1:");
showints(priv.getInvA2());
System.out.println("Vi:");
showints(priv.getVi());
System.out.println("\n----Public Key----");
System.out.println("Doc length:"+pub.getDocLength());
System.out.println("Coeff Quadratic:");
showints(pub.getCoeffQuadratic());
System.out.println("Coeff Scalar:");
showints(pub.getCoeffScalar());
System.out.println("Coeff Singlar:");
showints(pub.getCoeffSingular());
ParametersWithRandom param = new ParametersWithRandom(pair.getPrivate(), keyRandom);DigestingMessageSigner rainbowSigner = new DigestingMessageSigner(new RainbowSigner() , new SHA224Digest());
rainbowSigner.init(true, param);System.out.println("\n----Message and signing----");
String ex="hello";
if (args.length>1) ex = args[0];
byte[] message = ex.getBytes();
System.out.println("Message:"+ex);rainbowSigner.update(message, 0, message.length);
byte[] sig = rainbowSigner.generateSignature();System.out.println("Signature:"+getHexString(sig));
rainbowSigner.init(false, pair.getPublic());
rainbowSigner.update(message, 0, message.length);
if (!rainbowSigner.verifySignature(sig))
{
System.out.println("Failure in signature");
}
else
System.out.println("Success in signature");
}
public static String getHexString(byte[] b) {
String result = "";
for (int i=0; i < b.length; i++) {
result +=
Integer.toString( ( b[i] & 0xff ) + 0x100, 16).substring( 1 );
}
return result;
}
public static void showints(short [][] grid)
{
System.out.println("Dimension: [" + grid.length+"]["+grid[0].length+"] (Only displaying first few)");
int count=0;
for(int r=0; r<grid.length; r++) {for(int c=0; c<grid[r].length; c++)
{
System.out.print(grid[r][c] + " ");
count++; if (count>15) return;
}
System.out.println();
}
}
public static void showints(short [] grid)
{
for(int r=0; r<grid.length; r++) {
System.out.print(grid[r] + " ");}
System.out.println();
}
public static void showints(int [] grid)
{
for(int r=0; r<grid.length; r++) {
System.out.print(grid[r] + " ");}
System.out.println();
}
}
The variables used include:
- Doc — Number of polynomials in Rainbow.
- Vi — Number of Vinegar-variables per layer ({6, 12, 17, 22, 33})
- B1 — Translation part of the private quadratic map L1.
- InvA1 — Inverse matrix of A1.
- B2 — Translation part of the private quadratic map L2.
- InvA2 — Inverse matrix of A2.
Oil and Vinegar is a method which is difficult to solve if we do not have the required secret information. Unfortunately the methods used in discrete logarithms and prime number factorization are a major target for quantum computers, so we perhaps need to look to problems which will still be hard when quantum computers go live.
Ans: x=2, y= 1, w= 4, z= 5
Merkle signatures scheme (MSS)
The roots of hash-based methods is Merkle trees, and which are a way of hashing used in many applications, including with Bitcoin, Ethereum, Git distribution systems, No SQL, and P2P file transfer. With a Merkle tree we take our data elements, and then hash them, and take pairs of these hashes to create a new hash, and so we build a hierarchical tree. At the top of the tree is the root element (in this case Hash1234):
In this way, we can use the tree to see if we have matching data on systems. On a P2P network, we can transfer a file by splitting it into data segments and then distributing these segments across the network. A trusted source will have the complete Merkle tree for rebuilding the file, and a client can thus rebuild from the Merkle tree and determine the parts of the file which are still missing (or are in error). Once transferred, the root hash (and all the other hashes) will then match. In its core method, the Merkle Signature Scheme (MSS) has serious performance and memory issues, but enhanced methods such as XMSS create the hash table with much less of a performance hit.
The methods present for W-OTS and Lamport only provide for a one-time signature. In order to sign many messages, we can use the Merkel signature scheme (MSS). With we take a hash of the keys and build these as the leaves of the tree. The root of the tree is then the public key — the verification key. We then just use the private key of the OTS method to create the signature. The sender also sends the authentication path, which is the neighbouring nodes within the path which leads to the root of the tree. At the receiver end, they can then rebuild the tree using the verification key (which can be received a digital certificate) and the authentication path. For we move onto another key pair and where the index of the key part is revealed.
In the following example we have our root as the public key, and then want to sign with Key3. We then show the authentication path which takes us to the root (as defined in the bold arrows):
In the following we have a message of “hello” and which has a SHA-256 hash of “2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824”.
We first produce four sets of key pairs (and which can only be used once each). For each set of key-pairs we have 32 256-bit random numbers, and the public key is 32 256-bit versions of the private key, and that have been hashed 256 times.
We then take the message and hash it with SHA-256. Next we take each 8-bit value in the hash (N), and then hash 256-N times using SHA-256. These values become the signature.
To verify the receiver takes the hash of the message, and takes the SHA-256 hash. Next they will take each 8-bit value of the received signature, and then hash it by the value of the byte in the hash of the message. The results should be the corresponding value in the public key.
The Merkle root defines the top level hash, and where the authentication of the hash for the corresponding key pair is also given.
Message: hello
Hash(message): 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824=== Calculate four signatures with 32 key pairs each ===
Private key [0][0]: 4db81f526b64d69b58a6a1cf9578dc9e04eac297414e9fe63a85df2ccef11a6a
Private key [0][1]: 673d627b7badf7461257d3e65bd557bda0da24e6485d97e86cf92d784bbbcdc6
....
Private key [0][31]: 5d4b71021c9d90ec95822037004d994e15bee4587fc08cf33d1877cc8c5fe153
....
Public key [0][0]: 336196ed0c22d4cff3218c9000e24c70a0bfec5e0ca318afe4899a16ccc755c6
Public key [0][1]: fa0a9ce753520bb142dc97c10fc313e09b6f5f83639d9bfb2beabd78785276e0
....
Public key [0][31]: a5912d99be04e9af0fdc6e2b2903788d7023c6ddae69a7b409e07e57465e246b=== Determine Merkle Root ====
Merkle root: 3fa78ced3b5dc205b3dbfc29a89a2352d11f16c2a751c15666f25e73c6a54fbf=== Create signature ====
Signature [0]: 9e82faf05429db2854001abf42ea38eec1cd6cbf1b76292cc1bc8ef82ca61216
....
Signature [31]: aaaf98ff8576a19ac758b765a5eb75d42286bf548188e5778a294f09f78aa42a=== Verify signature ====
Verified MSS: True
Merkle path: [('161b01f3c986543bda6a9a49bde5820f7ba5324cdfd5ea4535d897fed750309c', '47dfb8b70b1a7e8227dca2b226410d818104f4af45352f5334f4230436903c4c'), ('b344637c77e539df5d5396b354bbc2c3d202d6b2fd4ce8175338ae42035ec1a6', '61eddc1359167727065c94a0427b8d18811a791fae7db2b5103dc3b20b1a3cf5'), ['3fa78ced3b5dc205b3dbfc29a89a2352d11f16c2a751c15666f25e73c6a54fbf']]
Verify root True
A demonstration of this method is given here.
Conclusions
As I said, we must look not towards now, but think carefully about our future, and the risks we face.