Ensuring authorship of digital messages or how concerns for privacy led to digital signature (Exploring the digital frontier IV)

In my previous post I addressed the issue of how to ensure the integrity of content as ephemeral as that of a digital file, in terms of how it passes from the controlled safekeeping of the physical format in which the file is recorded to a purely “logical” system of file content identification resulting from hashing functions.

A different question is addressed here, namely, how to ensure, not the content, but the authorship or origin of the file. This is fundamental when using the electronic medium for communications with legal implications, for transmitting scientific statements, or when the content is legally attributable to specific persons.

How such an useful technical tool came to be devised is an interesting story not only in intellectual terms but also for its idiosyncratic beginnings.

Whitfield Diffie versus the National Security Agency’s secrecy and monopoly on cryptography

It was the early seventies and Whitfield Diffie, a long-haired hippy mathematician and MIT graduate, whose interests included breeding skunks and other exotic animals, was travelling around the USA with his girlfriend in a dilapidated old Datsun 510. Visiting libraries and trying to interview anyone with information about an issue on which few were forthcoming, that is, modern mathematical cryptography techniques. An unusual branch of knowledge that had proved crucial in bringing the Second World War to a successful conclusion and which, during the Cold War, had been completely shrouded in secrecy by the national intelligence services. In particular, the NSA state agency, an organization so cryptic that scarcely anyone knew of its existence let alone its activities.

Diffie was both an eccentric and a visionary and at that time he was obsessed with the threat to individuals’ privacy that, in his view, was posed by the development and growth of computer technology. His fears were based on the fact that some information in digital format is extremely vulnerable to intrusion and copying. In a context in which huge volumes of information on our lives were about to be digitalized, protecting privacy required a specific tool which, of course, was modern cryptography which made use of the computer’s calculating capacity. Citizens needed access to this type of cryptography in order to protect their privacy. It was also necessary in economic activities, and in particular trade in the new digital medium. However, everything about cryptography was a state secret.

All the information in this matter was classified, patents could not be registered, scientific works were supervised, NSA procured all the best brains who worked in a closed area and were subject to stringent confidentiality undertakings, and anyone with the temerity to investigate in an independent capacity would soon find a federal agent peering over their shoulder and putting all kinds of obstacles in their way.

As he roamed around the United States in his Datsun, Whit Diffie barely managed to pick up any information, but what he did manage to find was a kindred soul with whom he joined forces. Martin Hellman was an electrical engineer who taught at Stanford University and who shared an interest in cryptography and who had a similar anti-establishment stance towards the implacable nature of official secrecy.

Having approached the matter from various perspectives, Diffie concluded that he would have to develop a decentralized cryptography system, that is, one which did not have an administrator allocating keys to all users, and therefore knowing everyone’s password, as occurred when various people began to share working hours or the same computer equipment. Total security for the information generated and registered in the new digital medium would only be feasible if each user could encrypt their files with a password that only they knew. Furthermore, in order to encrypt information for both personal and private use, such as communications or messages between specific subjects, the only cryptography known to that point was always a “symmetric” type, which means that the same key used to codify or encrypt a text also had to be used to decipher it and make it legible.

As a result, within the scope of communications this cryptography can only operate between subjects who know and trust each other, because they need to share the secret of that unique key, and it is also exposed to the threat of a third party discovering or intercepting the key, because the parties need to  indicate the key that they will use beforehand, and this communication requirement is the weak point in the system, as the more people that know it the more insecure it becomes, because the system is only as trustworthy as the least reliable or careless persons who are part of the process.

The vision for an asymmetric cryptography system

One day in May 1976, Diffie came up with an idea that would revolutionize cryptography forever, by breaking down the key into two elements so that what is coded with one part can only be decoded with the other part, and in addition, knowing  one of those parts does not reveal the other key. If a pair of keys of this type were generated, one could be made known through an insecure medium, which could even be known to the general public  (complete heresy in the age-old history of cryptography), whereas the other would be kept secret by the user. This in turn provided two different functionalities that should not be confused.

– One it can serve to transmit messages confidentially and through an insecure medium (which was soon to become internet). The sender codifies or encrypts the message by precisely applying the addressee’s public code, which had been obtained previously through a medium that is not necessarily confidential, or which could also be known to the general public. In this way, only this specific address can read the message, because only that person can decrypt it by applying the private code (which is the key correlating to the key used to encrypt).

– And secondly, for something different and very important that is not related to confidentiality or secrecy but which concerns authorship, with the security of knowing the provenance and therefore allocation of a message: as a tool for electronic or digital signature. For this purpose, the sender encrypts the whole message or a brief summary of its content which is its hash (for an explanation of this concept I refer you to my previous post) with its private code, and sends it. Anyone receiving a totally or partially encrypted message in this way can check its origin simply by applying the public key of the person appearing as sender. If the message or its encrypted part is decrypted, then we can be sure that it was encrypted precisely by that specific person who, it is assumed, is the only one who knows and could apply the private correlative key. In this way, a dual key cryptography becomes an instrument that enables recipients of messages to unquestionably verify their origin. Which is the same as saying that this cryptography becomes a tool for generating an electronic signature: by applying my private key to any message I am signing insofar as I am applying a mark or signal of recognition which it can be assumed that only I can apply, in that it presupposes in turn that I am the only person in the world that knows that private key.

In addition, the two functions of asymmetric cryptography thus explained can be combined: the sender signs the message by applying their private key and then encrypts it by applying the addressee’s public key. In this way only that person can read it and also its provenance is guaranteed.

In search of a one way mathematical function

How can a pair of keys with these properties be achieved?

In June 1976 Diffie and Hellman published their first article entitled «Multiuser Cryptographic Techniques», in which they confined themselves to explaining their vision of a possible dual key cryptographic system, which would provide security (both confidentiality and authenticity) for communications between people who did not know each other. The mathematical tool for this purpose should have a “one-way function”- easy to compute in one sense but very difficult to reverse- which would be provided with a “back door” that would enable the person who knows a specific secret key (a crucial part of the information on how the original computation was made) to easily decipher the message. The problem was to find that mathematical rarity, a one-way function.

Following publication of this article, Ralph Merkle, a Berkeley University computer studies student, got in touch with the authors because at that time he was working by himself on something similar (his proposals are known as Merkle’s Puzzles and the backpack problem).

Having been influenced by Merkle’s ideas, Diffie and Hellman, in a refurbished version of their first article, published under the title «New Directions in Cryptography» in November 1976, proposed what would become known as Diffie-Hellman Algorithm, based on a one-way function consistent with the mathematical operation of the discrete or modular exponentiation and its difficult reverse operation which is the discrete logarithm. Discrete or modular exponentiation consists of calculating the remainder c resulting from raising a base b to a determined exponent e and dividing the result by a modulus m. It is an easy operation to carry out, even with very big numbers. The reverse operation, that is, calculation of the exponent e given b, m and c –the discrete logarithm – is, however, an extremely difficult operation.

Without entering into the technicalities of the mathematical formula, what we are interested in knowing is this: Bob and Alice each generate two numbers by chance, one is kept secret and the other is exchanged through an insecure source, subsequently, by applying the algorithm to the number received from the counterpart and their own secret number, each of them obtains a new number which they then exchange once more. On the basis of these two last different numbers, Bob and Alice carry out an operation which results in both cases in the same number, a number known only to them and which they can use as a key. In this model, the difference between the calculation that requires application of the back door available to Bob and Alice and the computational effort of brute force that a third party attack would require is exponential (it could require millions of years of computing time). Notwithstanding, this design has the disadvantage that it does not provide authenticity of origin, that is, it is not feasible for signing a message and permitting its secure allocation to a specific sender. Simply, it serves to generate securely a shared key, that is, symmetric, among unknown subjects or those who operate in an insecure communications medium.

The RSA algorithm

We owe the definitive step on the path to asymmetric cryptography to Ronald Rivest and his collaborators Adi Shamir and Leonard Adleman, all MIT mathematicians, who in 1977 published a collective work entitled «A method for obtaining digital signatures and public-key cryptosystems». The method in question used as a one-way function the product of two big prime numbers- of more than hundred digits- the reverse operation of which, factorization in order to find the two primes that have been multiplied, is an extremely costly computational task, which can only be resolved through brute force. On this basis, they devised an algorithm, known as RSA (by Rivest, Shamir and Adleman), consistent with a sequence of operations that did generate two mathematically interlinked keys, with the properties that I anticipated earlier, namely, what is encrypted with a single key can be encrypted with the other and vice versa, and knowledge of one of these will not permit the other key to be deduced. And this is why one of the keys can be made public, providing the dual functionality that Whitefield Diffie had envisaged.

The non-mathematical base of an asymmetric cryptography electronic signature system

However – and it is particularly important to understand this – for the private key/public key method to be used as a signature mechanism, these mathematical properties of the keys generated by the RSA algorithm are not sufficient, as there is also a need to introduce two elements that are completely removed from mathematical science.

• In the first place, someone has to link or associate that pair of keys, specifically the public key, which is the only one that will be made known to third parties, to a specific person. Let us suppose that my private key was xyzw and my public key was 1234. If anyone receives a message that is deciphered by applying the key 1234, it may be assumed that the message comes from me if it has the security that 1234 is the public key, which is precisely the one I use for my communications. If Alice and Bob know and trust each other, Alice can inform Bob of her public key beforehand so that he can safely make this link between that specific public key and Alice’s identity. We could say that Bob knows Alice’s signature (I am referring here to the public key, not the private one, which Alice cannot not reveal to anyone, even her good friend Bob) because Alice has made it known to him or he is familiar with it, which is the same as Bob knowing Alice’s handwritten signature.

But what happens if Alice and Bob do not know each other? How can Bob know with any certainty the public key that Alice uses and which allows her to be considered the author of specific messages? Because a third party that Bob trusts is involved and certifies Alice’s public key.

Regarding this third party, there are two systems, one is decentralized or peer-to-peer, in which some users confirm the signatures of others, creating a network of recognition. Then centralized system which is generally known by its initials PKI (Public Key Infrastructure), in which a particular subject professionally assumes the role of certifier of public keys. This subject or agent carries out two specific tasks, one of identification (what is usually known as “registration authority”) and certification (“certification authority”). The registration authority’s task is to identify – normally by making a personal appearance and verifying by means of an official identity document of some kind- the person wishing to create a pair of keys that will be used as an instrument for digital signature. In this way this third party will be responsible for linking a specific person and a particular public key. The activity of certification consists of maintaining an accessible online register of current certificates by means of which,  any interested party will be able to confirm the identity of the holder of a specific public key (just a like a telephone directory with a list of names and their corresponding telephone numbers). Thus, when anyone receives a message signed with this type of electronic signature, the signature verification program available to the recipient automatically carries out two operations: firstly, it checks that the message was effectively signed with the sender’s private key (three things are done in this regard, the public key of the potential sender is applied, which is indicated in the message, on the sender’s encrypted hash in order to obtain the unencrypted version of said hash; subsequently the hash of the message received is directly calculated by applying the corresponding hashing function; and finally, the hash obtained is compared with the decrypted hash to check that they coincide); and secondly, it checks that the public key applied in the previous operation is effectively allocated to the sender in a current certificate according to online registration maintained by the appropriate certification authority (for which purpose it will be necessary to access the certifier’s website).

In our positive law, the aforementioned registration and certification authorities are the main objective of most of the precepts in respect of the law on electronic signature which considers, in accordance with European community law, that the provision of electronic signature certification services is not a public function but a business activity, and part of the sphere of free competition, although subject to specific legal requirements in order to ensure that the signatures supported by their certificates are deemed to be “recognized electronic signatures” which are those that are accorded full legal status equal to handwritten signatures under law.

In any case, what is interesting in this matter is the fact that the link between a public key and a specific person does not result from application of the actual cryptographic technique or any mathematical function, but rather from attestation or certification of this trusted third party which is provided by the registration and certification authority.

• In addition to this confidence in the third party that certifies the link between a public key and a specific person, this electronic signature system is based on another element which is not mathematical but regulatory; presupposing that the person who generates a specific pair of keys for the purposes of signature, keeps their private key secret. Thus, attributing the meaning of “signature” of a message to the use of this dual key cryptography instrument ultimately rests on the idea that only the person who has revealed a specific public key as their own, is the only individual who knows the correlative private key, and is therefore able to apply it. And I have qualified this element as regulatory because it does not belong to the scope of facts, but to the scope of how things should be, in that it is assumed that when a pair of keys are created and registered as one’s own specific public key, the obligation is assumed, or at least the duty, to diligently safeguard and maintain the privacy of the correlative private key is assumed, even if, in fact, this is not the case. This is what serves as the basis for the cliché of “non-repudiation” of the message signed with an electronic signature of this type, although it is true that if you search the law on electronic signature for anything explicitly referring to this extremely important rule, you will not find it.

Regarding this question, the fundamental legal problem is raised of  whether there could be a contractual or commercial link for a person, given the existence of a message signed with an electronic signature device (that is, by applying the correlative private key to the public key registered ) in those cases where a third party made use of the device, having known the private key, albeit because its owner voluntarily revealed it , or because it was obtained surreptitiously or with violence (the case referred to by cryptographers as the rubber hose attack, a contingency to which ultimately any cryptographic system is exposed, however mathematically secure it may be).

(For anyone whose curiosity is piqued by the subject of cryptography I recommend the fascinating book “Crypto. How the Code Rebels Beat the Government Saving Privacy in the Digital Age ” by Stephen Levy, Penguin Books 2002).