Prof. Martin Hellman

 

Public-key cryptography pioneer and Stanford University Electrical Engineering Professor Emeritus  Martin Edward Hellman was born in 1945 and grew up in the Bronx borough of New York City. His father was a high school physics teacher, whose influence and collection of books helped to inspire Hellman’s early interest in science and mathematics. In his leisure time as a youth, Hellman would play stickball on the streets of his largely immigrant neighborhood, or later, practice as a ham radio operator, getting his ham license his senior year of high school—a hobby that furthered his passion for electronics and electrical engineering. [4, 5]

In 1962 Hellman graduated from Bronx High School of Science and earned a Bachelor’s degree in Electrical Engineering from New York University in 1966. After graduating, Hellman enrolled in graduate school at Stanford University’s Electrical Engineering Department, where he earned his Master’s degree in 1967 and his Ph.D. in 1969. He married during his first year of graduate school. His dissertation, written under advisor Thomas Cover, was entitled, “Learning with Finite Memory.”  

Hellman describes his Ph.D. research on Learning with Finite Memory.

Hellman’s interest in cryptography developed in the background during his early career. In late 1968, having completed his dissertation, he began work at IBM’s Thomas J. Watson Research Center in Yorktown Heights, New York, where IBM had recently launched a cryptographic research program. Headed by German-born cryptographer Horst Feistel (formerly with the Air Force Cambridge Laboratory, Lincoln Laboratory, and MITRE) it included Alan G. Konheim (a subsequent leader of this research team) and other notable cryptographic scientists. This group’s research would lead to development of the Lucifer encryption system.  Hellman, in the same department but working in other areas, ate lunch with Feistel who taught him about classical cryptographic systems and that “problems that sounded unsolvable could actually be solved very quickly.” [4]

Hellman learned more about cryptography during a talk by David Kahn, author of the The Codebreakers: The Story of Secret Writing (1967), at the 1969 IEEE International Symposium on Information Theory. Kahn’s book, a soon to be classic history of cryptography spanning ancient Egypt into the 1960s, had a significant impact on Hellman. [4, 7]

In September 1969 Hellman left IBM to teach in Electrical Engineering at MIT, joining a research group headed by noted information theorist Peter Elias. Elias passed along to Hellman a paper by Claude Shannon published in 1949 in the Bell Systems Technical Journal, alerting him to the fact that cryptography was “a branch of information theory.” [4] The paper was based on earlier, formerly classified, work Shannon did during the war, which Hellman points to as evidence of the influence of cryptography on Shannon's seminal 1948 paper on information theory.

Intrigued by California and Stanford in particular, Hellman left MIT in 1971 to join the faculty in Electrical Engineering at Stanford.  At Stanford, Hellman moved gradually into the cryptography field, writing a technical report in 1973. IBM’s investment in cryptography had encouraged Hellman to believe that the area must be of commercial importance. In Hellman’s mind this had helped counter discouraging responses from academics about cryptography. Hellman later reflected that he was “working in a vacuum with discouragement from all my colleagues.” [4] One critique was that academics could not hope to “discover anything new” as the most advanced work was kept secret. To this, Hellman would reply it does not matter what is known there (the classified world), “it is not available for commercial use... the person who gets credit is the first to publish, not the first to discover and keep things secret.”  Another argument was anything new that is “good” will be classified.  He was further discouraged when he gave a talk at IBM Thomas J. Watson Research Center which included Horst Feistel, Alan Konheim and others. They told Hellman that IBM’s management was discouraging further research on cryptography (whose problems it thought had largely had been solved by the IBM group’s development of Lucifer and the soon-to-be released DES). Instead IBM was trying to refocus energy on the challenge of secure operating systems.

In 1974, at the suggestion of Alan Konheim, Whitfield Diffie, who had a deep interest in cryptography and had just met with Konheim and others at IBM’s research lab, visited Hellman. Diffie had graduated from MIT in 1965 (B.S. in Mathematics), and then had worked at MITRE and been a resident guest at the MIT Artificial Intelligence (AI) Laboratory headed by Marvin Minsky.  He left MITRE and the MIT AI Lab in 1969 to move to California and join the Stanford University AI Lab run by former MIT faculty member John McCarthy. Leaving this laboratory to spend more time studying cryptography, Diffie spent time travelling and meeting others interested in cryptography, including IBM’s research group.  A planned half-hour early afternoon meeting in the fall of 1974 at Stanford between Diffie and Hellman evolved to an afternoon-long discussion followed by dinner and further exchange well into the evening.  In Hellman’s words, “…it was a mild epiphany, finding an intellectual soul mate.” [4]

Diffie and Hellman’s intellectual quest evolved into an effort to solve cryptography’s key distribution problem without the use of a cumbersome, inefficient, and less secure key distribution center or couriers. These two problems were so novel that previously they had never been posed in the open literature. Prior to the invention of public key cryptography, if two parties wanted secure communication, they were dependent on using a third party, typically a courier, to distribute or exchange the cryptographic key.  Key distribution created vulnerabilities, such as the trustworthiness of the messenger or potential interception, delays, and expenses. Many secure transactions required a courier with a locked hand-cuffed briefcase containing the key. [7]  Diffie and Hellman also sought to develop digital signatures to authenticate that messages have not been faked or tampered with.

Shortly after Hellman and Diffie’s initial 1974 meeting they began working together—Diffie secured a Stanford University job in support of his cryptography research.  In 1975 Hellman encouraged Diffie to enroll as a Stanford doctoral student under his direction, which Diffie did for the fall semester.  About eighteen months after their initial meeting, Diffie and Hellman became aware of similar, independent work being done by Ralph Merkle, then a Masters student in Computer Science at the University of California-Berkeley. With no one at Berkeley appreciating Merkle's work, Hellman encouraged him to enroll as graduate student in Electrical Engineering at Stanford University, which he did in 1976. Working under Hellman’s direction, Merkle completed his Ph.D in 1979. But, as Hellman recalls in his ACM Turing Award lecture: "Whit can be nobody’s student,” to which Diffie replies: "I’m not very good at it. I admire people who are good students. I think it’s a tremendously valuable skill. I just have never proved very good at it.” In consequence, Diffie never finished his degree at Stanford, but received the recognition he deserved in 1992 when the Swiss Federal Institute of Technology (ETH) awarded him an honorary doctorate. [4]

In 1974, Merkle independently developed the concept of public-key distribution, including an impractical proof of concept known as Merkle Puzzles. Soon afterward, and independently, Diffie and Hellman proposed a more elegant approach known as a public-key cryptosystem, which could provide both public-key distribution and digital signatures. They also developed a practical method of public-key distribution, now known as Diffie-Hellman Key Exchange. This led Hellman subsequently to argue that the name of that algorithm should include Merkle’s name.” [4, 7]

Hellman explains the basic concepts of public key cryptography.

The seminal paper for public-key, “New Directions in Cryptography,” was written by Diffie and Hellman, presented at an IEEE Information Theory Symposium in June 1976, and published as an invited paper in the November 1976 issue of IEEE Transactions on Information Theory.  The paper boldly began, “We stand today on the brink of a revolution in cryptography.”  Their inventive insights did in fact lead to a revolution in cryptography.  Diffie and Hellman’s article cites Merkle’s submitted “puzzles” paper, which was subsequently published in Communication of the ACM (April 1978).[1]

Hellman recalls the publication of “New Directions in Cryptography."

Public-key cryptography relies on "one-way" functions, so called because they are much easier to compute in one direction than to reverse. This makes it possible for a sender to encode a message using the recipient's openly distributed "public key," without needing (or being able to reverse engineer) the "private key" used by recipient to decode the message. This can facilitate secure communication between individuals who have not met (without a key distribution center) and authenticate the message sender (digital signatures). [1] *

Diffie and Hellman described the concept of a public-key cryptosystem in their 1976 paper, but did not have a practical implementation. That was done later by MIT scientists/mathematicians Ronald Rivest, Adi Shamir, and Leonard Adleman  with their RSA algorithm (first released in 1977), which formed the basis for the company they founded in 1982,  RSA Data Security. It relies on the factoring of large prime numbers as the basis of its one-way function.  RSA Data Security spun-off its certifications or digital signatures enterprise as Verisign, Inc., in 1995.  These three scientists jointly received the 2002 ACM Turing Award for the RSA algorithm and its impact on cryptography in practice. [8]

Great Britain’s signals intelligence center GCHQ later revealed that Australian-born James Ellis conceptualized secret communication over an unsecure channel, or public-key cryptography, between 1969 and 1970. Independently of Diffie-Hellman, and at around the same time, Malcolm J. Williamson then invented what is called Diffie-Hellman Key Exchange in the open literature. GCHQ also reported that mathematician Clifford Cocks developed the algorithm now known as RSA in 1973. Hellman feels that the evidence that GCHQ solved the key distribution problem is highly persuasive. But he also notes that this work did not address digital signatures, and that the first to publish a public paper is conventionally credited, because only openly disclosed discoveries can impact what is used in commercial and other open communities. [4]

Martin Hellman played a leading role in the late 1970s' and early 1980s' first “crypto war,” where he strongly advocated for cryptographic researchers' right to openly publish their work and the public’s right to strong encryption that can resist decryption efforts by domestic or foreign intelligence agencies including the National Security Agency (NSA). This included his early and continuing critique of the Data Encryption Standard (DES). NSA had worked with NBS (now NIST) and IBM to specify the DES, a modified version of Lucifer. While the general design of DES is stronger than that of Lucifer, its 56-bit key size was significantly weaker than Lucifer’s 128 bits. This is now known to have been a compromise that was thought to be strong enough for commercial use, but was widely believed to be vulnerable to decryption efforts by NSA through brute force with its massive computer processing resources. The National Bureau of Standards officially adopted DES on November 23, 1977. [2, 5]

Hellman describes and critiques the 1970s DES standard for encryption.

Hellman published more than 70 technical papers and was granted 12 patents (including the April 1980 public-key cryptography patent with Diffie and Merkle).  At Stanford, he played a role in helping students from diverse backgrounds to reach their potential within the university — work that was recognized by several awards from minority student organizations. Among many other honors, he was elected to the National Academy of Engineering (2002). In 1996 Hellman became Professor Emeritus.

Jeffrey R. Yost

*Diffie-Hellman Public-Key

As they explain in their landmark paper:

In a public-key cryptosystem enciphering and deciphering are governed by distinct keys, E and D, such that computing D from E is computationally infeasible (e.g. requiring 10¹⁰⁰ instructions).  The enciphering key E can be disclosed [in a directory] without compromising the deciphering key D. This enables any user of the system to send a message to any other user enciphered in such a way that only the intended recipient is able to decipher it….The problem of authentication is perhaps an even more serious barrier to the universal adoption of telecommunications for business transactions than the problems of key distribution…[it]…is at the heart of any system involving contracts and billing. Current electronic authentication systems cannot meet the need for a purely digital, unforgeable, message dependent signature. [1]

By convention, cryptography characters “Alice” and “Bob” (seeking secure communication) are used to explain public-key. Alice and Bob agree on large integers n and g with 1< g< n.   The selections impact the security of the system.  “The modulus n should be a prime; more importantly (n-1)/2 should also be a prime…and g should be a primitive root mod n…[and]...n should be…at least 512 bits long.” [6] The Diffie-Hellman protocol can be stated in basic form in 5 steps. [6]

(1)    Alice chooses x (a random large integer) and computes X=g^x mod n

(2)    Bob chooses y (a random large integer) and computes Y=g^y mod n

(3)    Alice sends X to Bob, while Bob sends Y to Alice (they keep x and y secret from each other)

(4)    Alice computes k = Y^x mod n

(5)    Bob computes k’ = X^y mod n