The Patents That Built The Security of The Internet: Sharmir-Fiat, Schnorr, Brachtl, GQ, and…

The Patents That Built The Security of The Internet: Shamir-Fiat, Schnorr, Brachtl, GQ, and Kravitz

As a researcher, it is not only important to know where we are and where we are going, but it is just as important to know where we have been, and how current practice has evolved. At any point in time, we may back-track to a method that we forgot about, and develop new areas of research. Also the flaws and weaknesses that stopped a method from being developed might be overcome by new knowledge. The skill of the researcher is to understand this complex history, and make sense of it.

So I love reading classic research papers on the past, and in trying to build a timeline of thought that supports the advancement in technology. And so in Cybersecurity, we see much of the foundation of the field defined in the 1980s and laid out in terms of classic patents. For this I’ve defined the six classic patents that provide the core of much of what we have today in terms of encryption:

Now let’s push into the late 1980s and onto the 1990s, and see how these classic patents developed into areas of identity and within digital signatures.

When Fiat met Shamir

While Stanford saw the rise of the mighty patents around RSA and key exchange, it was Adi Shamir’s work that really pushes on into the 1980s. His patent with Amos Fiat was filed in July 1986 and published in May 1988. Its focus was on proving the identity of a device, and where the proof level could be changed depending on various parameters [here]:

As a small aside it has an unfortunate typo:

MDC-2/MDC-4 hashing

A key function within security is the verification of data with a hash value. This uses a one-way function to convert data into a fixed-length bit value. The MDC-2 (Modification Detection Code-2)/MDC-4 hashing method showed how a strong one-way function could be created. It was submitted in August 1987, and assigned to IBM [here]:

It was Ron Rivest who then pushed forward MD2 and MD4 in 1989, and defined a new 128-bit hashing method, and which was not covered by a patent.

On-line/off-line signing

In Nov 1988, Micali, Goldreich and Even submitted a patent that allowed for a pre-computation element so that a message could be signed without the requirement to be on-line. It involved two main stages. The first was a precomputed value that was independent on the message (s1), and the second for a one-time public key (s2) [here]:

The Schnorr signature

In Feb 1989, Claus Schnorr submitted a patent which was assigned to no-one. It has 11 claims, and allowed digital signatures which could be merged for multiple signers [here]:

With the Schnorr signature, we create a signature (R,s) for a hash of the message (MM). We first generate a private key (x) and then derive the public key from a point on the elliptic curve (G) to get:

P=x⋅G

Next, we select a random value (k) to get a signature value of R:

R=k⋅G

The value of s is then:

s=k−Hash(M,R)⋅x

Our signature of M is (s,R) and the public key is P.

To check the signature we calculate

P⋅Hash(M,R)+s⋅G

This becomes x⋅G⋅Hash(M,R)+(k−Hash(M,R)⋅x)⋅G

which is:

x⋅G⋅Hash(M,R)+k⋅G−Hash(M,R)⋅x⋅G=k⋅G

The value of k⋅G is equal to R, and so if the result is the same as R, the signature checks out.

A sample run with the message of “Hello” is (and where “BN” is “Big Number”) [here]:

Message:Hello
Private Key: dce71358bf6d57dffaf8ac422ea972dca65badd2ce21b585803ea3075b7de388
Public key: Buffer 03 9d e0 bd 0a e1 b2 1c 64 c7 35 12 31 1c d5 fd 35 42 f1 0a f5 02 9c c7 eb 81 e5 fb cc c8 51 18 27

Signature [s]: BN: 18573f5212373b51022b00cbe12276b8099a351526b3384ccd1f02ad71761ff1

Signature [r]: BN: 3d96504afbe3beec97a753c38d614ec5fa68cf8219df36d7cce891319058d5db

Public key recover: Buffer 03 9d e0 bd 0a e1 b2 1c 64 c7 35 12 31 1c d5 fd 35 42 f1 0a f5 02 9c c7 eb 81 e5 fb cc c8 51 18 27

Signature verified: true

In this case, we have 256-bit private key (dce7 … 388), and produce a 512-bit public key (03 96e … 827) — the “03” part identifies that we are using a Bitcoin public key. Thus, if we know the message — and which will be stored on the blockchain in the case of Bitcoin — and the key, we can see that we can recover the public key from the signature.

One of the great advantages of the Schnorr signature is that we can sign more than one message. Let’s say we have a transaction, and Bob, Alice and Trent must authorise it. In a Bitcoin network, this is defined as a “multisig” setup. Bob, Alice and Trent must then go away and create their own new “aggregated” signature, which will be their new public key for transactions. This is not efficient, and also reveals the Bob, Alice and Trent are working together. In an improved setup, we can define an n-from-m setup, where we can merge Bob, Alice and Trent’s keys into one public key, and then use that. The public key will then not reveal that Bob, Alice and Trent are working together, but they will create a new public key which will validate the transaction.

If we wanted just any two of them to validate it, we could ask for a 2-from-3 multisig. So if Bob, Alice and Trent are directors in a company, they could define that any two of them could validate a transaction.

The Bitcoin network could have found a way to enable this type of signature merging of public keys, and it all points to the Schnorr method. In the illustration below, we can see that the current method involves Bob, Alice and Trent getting together and creating a new public key (and an associated private). With Schnorr’s key aggregation method, we can take Bob, Alice and Trent’s public keys and then merge into a new transaction key. It will then not be possible to see the parties who created the transaction key.

GQ identification (created by Guillou and Quisquater)

After Schnorr’s signatures, the next great crypto patent was created by Louis Guillou and Jean-Jacques Quisquater, and assigned to the Philips Corporation. It was submitted in October 1991 (but was actually a resubmission from two previous submissions). It became one of the first to show a practical example of zero-knowledge proofs and focused on smart card identification [here]:

The Guillou-Quisquater (GQ) identification scheme was originally defined in 1988 [1] and supports a zero-knowledge proof method. The prover (Peggy) has a proving public key of (N,e,X) where N is the modulus, e is the exponent, and X=x ᵉ(mod N). x is the secret value that the prover (Peggy) must prove (x∈ℤ∗N) [What is ℤ∗N? Find out here]. After Peggy generates his public proving key, she will then be challenged by Victor (the verifier) to produce the correct result.

With the GQ method, Peggy (the prover) has a proving public key of (N,e,X) and a proving secret key of (N,x). N is a prime number for the modulus operation. In this case x is the secret, and where:

X=xᵉ (mod N)

On the registration of the secret, Peggy generates a random value (y), and then computes Y:

Y←yᵉ (mod N)

This value is sent to Victor (who is the verifier). Victor then generates a random value (c ) and sends this to Peggy. This is a challenge to Peggy to produce the correct result. Peggy then computes:

z←yxᶜ (mod N)

She then sends this to Victor in order to prove that she knows x. Victor then computes two values:

val1=YXᶜ (mod N)

val2=Xᵉ (mod N)

If the values are the same (val1≡val2), Peggy has proven that she knows x. This works because:

YXᶜ=yᵉ(xᵉ)ᶜ=yᵉxᵉᶜ

zᵉ=(yxᶜ)ᵉ=yᵉxᵉᶜ

In a formal definition (taken from this paper) [2], the method is:

In the following we define a secret value (x), an exponent (e) and a modulus value (N) [here]:

Peggy (the Prover) generates these values:
x(secret)= 3
N=  101
X=  27
Peggy generates a random value (y):
y= 20
Peggy computes Y = y^e (mod N) and passes to Victor:
Y= 21
Victor generates a random value (c) and passes to Peggy:
c= 85
Peggy calculates z = y.x^c (mod N) and send to Victor (the Verifier):
Victor now computes val=z^e (mod N) and (y x^c (mod N)) and determines if they are the same
val1= 48  val2= 48
Peggy has proven that he knows x

A demo is here:

And the core papers here:

[1] L. Guillou and J. J. Quisquater. A “paradoxical” identity-based signature scheme resulting from zero-knowledge. Advances in Cryptology — CRYPTO ’88, Lecture Notes in Computer Science Vol. 403, S. Goldwasser ed., Springer-Verlag, 1988. [paper]

[2] Bellare, M., & Palacio, A. (2002, August). GQ and Schnorr identification schemes: Proofs of security against impersonation under active and concurrent attacks. In Annual International Cryptology Conference (pp. 162–177). Springer, Berlin, Heidelberg. [paper]

The DSA signature (created by Kravitz)

The Digital Signature Algorithm (DSA) had such a generic name, but it has since become a de facto standard in many applications. It was submitted in July 1992 and grandly assigned to the US. In itself it touched base with the classic patents that had previously followed, and defined that it built on the Schnorr method but was compatible with the ElGamal technique [here]:

The ECDSA signature method is the elliptic curve equivalent of the DSA method and is used extensively with Bitcoin methods. With this, we create a private key (priv) and then generate a public key, which is:

and where G is the base point on the elliptic curve, and where we add this point priv times (G+G+G … +G) to produce the public key. For the

Next, we create a random number (k) and produce the signature of:

The signature is then (r,s) and H(M) is the SHA-256 hash of the message (M), and converted into an integer value. The power of -1 is the inverse mod function. Here is a demo:

Conclusions

And there you go. Basically, much of what we have now in terms of securing data was published and patented in the 1980s and 1990s. For some methods, such as for the Schnorr signature, the advancement has been suppressed because of the patent, but others have thrived.