Adi Shamir

Adi Shamir is an internationally recognized cryptographer. He has a number of claims to fame including being a co-inventor of the RSA public-key cryptography algorithm for encoding and decoding messages, co-inventor of a zero-knowledge proof scheme that allows one individual to show they know certain information without actually divulging it, and a major contributor to what has become known as differential cryptanalysis as well as other significant contributions to computer science.

Shamir was born in Tel Aviv in 1952. After attending local schools he enrolled in Tel Aviv University, obtaining a BSc in mathematics in 1973 and then went to the Weizmann Institute where he studied computer science and received his MSc (1975) and PhD (1977). After completing his doctorate he spent a year at the University of Warwick in Coventry, England continuing with his research in a postdoctoral position. In 1978 he joined the research staff at the Massachusetts Institute of Technology (MIT).

At MIT he met Ronald Rivest, and Leonard M. Adleman who collaborated with Adi on their fundamental advance in cryptography. They were inspired by a 1976 paper [3] by cryptographers Whitfield Diffie and Martin Hellman discussing several new developments in cryptography. It described ways for the sender and receiver of private messages to avoid needing a shared secret key, but it did not provide any realistic way to implement these concepts. Rivest, Shamir, and Adleman presented practical implementations in their 1977 paper, “A method for obtaining digital signatures and public-key cryptosystems,” [1] which showed how a message could easily be encoded, sent to a recipient, and decoded with little chance of it being decoded by a third party who sees it.

The method, known as Public Key Cryptography, uses two different but mathematically linked keys: one public key used to encrypt the message, and a completely different private key used to decrypt it. The encrypting key is made public by individuals who wish to receive messages, but the secret decrypting key is known only them. The two keys are linked by some well-defined mathematical relationship, but determining the decryption key from its publically available counterpart is either impossible or so prohibitively expensive that it cannot be done in practice. The “RSA” method (from the first letters of the names of the three authors) relies on the fact that nobody has yet developed an efficient algorithm for factoring very large integers. There is no guarantee, however, that it will be difficult forever; should a large quantum computer ever be built, it might be able to break the system.

A detailed discussion of the theory and practice behind RSA can be found here. The computer code to implement it is quite simple, and as long as suitably large integer keys are used, no one knows how to break an encoded message.

RSA is used in almost all internet-based commercial transactions. Without it, commercial online activities would not be as widespread as they are today. It allows users to communicate sensitive information like credit card numbers over an unsecure internet without having to agree on a shared secret key ahead of time. Most people ordering items over the internet don’t know that the system is in use unless they notice the small padlock symbol in the corner of the screen. RSA is a prime example of an abstract elegant theory that has had great practical application.

After developing the basic method in 1977, the three Turing Award recipients founded RSA Data Security in 1983. The company was later acquired by Security Dynamics, which was in turn purchased by EMC in 2006. It has done cryptographic research, sponsored conferences, shown how earlier encryption systems could be compromised, and spun off other companies such as Verisign. When the 1983 patent on RSA [2] was about to expire, RSA Data Security published all the details of its implementation so that there would be no question that anyone could create products incorporating the method.

The three Turing Award recipients were not aware that a similar method had been developed years before by British mathematician Clifford Cocks, who extended the even earlier work of James H. Ellis. Cocks was doing his encryption work at the British Government Communications Headquarters (GCHQ), so it was classified as secret and not released until 1997, twenty years after Rivest, Adleman, and Shamir had published their independent discovery.

Another of Adi’s contributions is known as Shamir’s Secret Sharing. This is a scheme in which a number of pieces of the secret are shared between individuals, but it requires either some or all of them to collaborate in order to reveal the total secret. It is essentially a mathematical mechanism equivalent to having several individuals present with their physical and other keys before an ICBM can be launched. The scheme is flexible enough to accommodate the situation where, for example, a senior individual can unlock the secret alone but it requires three or more junior officials to unlock the answer. A simple example can be found here.

Shamir’s interest in cryptography has led him to investigate methods of attacking the decoding of a message. He and Eli Biham, Adi’s graduate student, are usually given credit for the invention of what has become known as differential cryptanalysis, although the mechanism was evidently known, and kept secret, by IBM and the American National Security Agency (NSA) prior to the 1993 public release of Shamir’s and Biham’s book [4] on the subject. It involves a series of tests to code variations on a plain text message and note the differences in the resulting coded output. This can be used to discover where the cipher shows non-random behavior which can then be used to ease the recovery of the secret key. The discovery came when they were investigating the security of the 1977 Data Encryption Standard (DES) and they noted that the algorithm for the encoding was created in such a way that even a small modification would have made breaking the code much easier. It turned out that IBM and NSA, already knowing something about the techniques, had deliberately designed it with that in mind.

Another of Adi’s advances is known as identity-based cryptography. In this mechanism the public key used in RSA is simply some easily obtained information about the potential recipient of a message. It could be something as simple as the recipient’s email address, domain name, or a physical IP address. The first implementation of identity-based signatures and an email-address based system was developed by Adi 1984 [5].  It allowed users to digitally “sign” documents using only publicly available information.

Shamir also proposed a very similar identity-based encryption scheme which was of interest because it did not require the user to obtain a public-key to be used in encrypting a message. While Shamir had the initial concept in 1984, the first actual implementation was done in 2001 by two different groups [6,7]. 

In 1994 Shamir collaborated with Moni Naor to produce yet another interesting scheme known as visual cryptography [8].  An image (which could be text) is broken up in such a way that the resulting pieces appear to be simply a random scattering of white and dark pixels. When all the pieces are overlaid the message appears. The beauty of this scheme is that if someone manages to gather all but one of the pieces the message is still unreadable. It is even more interesting than being “unreadable” in that it is possible to construct a missing piece that will reveal any message and thus the secret will remain hidden until the last true piece is put in place. While this sounds good, it also means that someone with all but one piece is capable of deception by constructing a final piece to show any message they like. A simple example is available here.