2002 阿迪-沙米尔

shiyi18

Adi Shamir
BIRTH:
July 6, 1952, Tel Aviv, Israel

EDUCATION:
BSc (Mathematics, Tel Aviv University, 1973); MSc (Computer Science, Weizmann Institute, Israel, 1975); PhD (Computer Science, Weizmann Institute, Israel, 1977)

EXPERIENCE:
Post doctorate position, Warwick University, England (1976); Instructor, Department of Mathematics, MIT (1977-1978); Assistant Professor Department of Mathematics, MIT (1978-1980); Associate Professor at Department of Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel (1980-1984); Professor, Department of Applied Mathematics, The Weizmann Institute of Science, Rehovot, Israel(1984 onward) Invited Professor, École Normale Supérieure, Paris (2006 onward).

HONORS & AWARDS:
Israel Mathematical Society Erd?s Prize (1983); IEEE WRG Baker Award (1986); UAP Scientific Prize (1990); Vatican Pontifical Academy PIUS XI Gold Medal (1992); ACM Paris Kanellakis Theory and Practice Award, jointly with others for RSA (1996); Elected to the Israeli Academy of Science (1998); IEEE Koji Kobayashi Computers and Communications Award (2000); ACM Turing Award, jointly with R. Rivest and L. Adleman (2002); Fellow, International Association of Cryptographic Research (2004); Elected to the US National Academy of Sciences (2005); Israel Prize (2008). Honorary Doctorates from École Normale Supérieure (2003) and the University of Waterloo (2009).

ADI SHAMIR DL Author Profile link
Israel – 2002
CITATION
Together with Leonard M. Adleman and Ronald Rivest, for their ingenious contribution to making public-key cryptography useful in practice.

SHORT ANNOTATED
BIBLIOGRAPHY
ACM TURING AWARD
LECTURE VIDEO
RESEARCH
SUBJECTS
ADDITIONAL
MATERIALS
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.



阿迪-沙米尔
出生地：以色列特拉维夫
1952年7月6日，以色列特拉维夫

学历
理学士（数学，特拉维夫大学，1973年）；硕士（计算机科学，以色列魏茨曼研究所，1975年）；博士（计算机科学，以色列魏茨曼研究所，1977年）。

工作经验。
博士后职位，英国华威大学（1976）；麻省理工学院数学系讲师（1977-1978）；麻省理工学院数学系助理教授（1978-1980）；以色列雷霍沃特魏兹曼科学研究所应用数学系副教授（1980-1984）；以色列雷霍沃特魏兹曼科学研究所应用数学系教授（1984起）。 巴黎高等师范学院特邀教授（2006起）。

荣誉和奖项。
以色列数学协会埃尔德奖（1983年）；IEEE WRG贝克奖（1986年）；UAP科学奖（1990年）；梵蒂冈教皇学院PIUS XI金奖（1992年）；ACM巴黎Kanellakis理论与实践奖，与其他人共同颁发给RSA（1996年）；当选为以色列科学院院士（1998年）；IEEE Koji Kobayashi计算机和通信奖（2000年）；ACM图灵奖，与R. Rivest和L. Adleman（2002）；国际密码研究协会研究员（2004）；当选为美国国家科学院院士（2005）；以色列奖（2008）。获得法国高等师范学院（2003）和滑铁卢大学（2009）的荣誉博士学位。

ADI SHAMIR DL作者简介链接
以色列 - 2002年
文献资料
与Leonard M. Adleman和Ronald Rivest一起，为使公钥密码学在实践中发挥作用做出了巧妙的贡献。

简短注释
书目
亚马逊图灵奖
讲座视频
研究成果
主题
额外的
材料
阿迪-沙米尔是一位国际公认的密码学家。他有许多名声，包括编码和解码信息的RSA公钥密码算法的共同发明者，零知识证明方案的共同发明者，该方案允许一个人在不实际泄露信息的情况下表明他们知道某些信息，并且是被称为微分密码分析的主要贡献者，以及对计算机科学的其他重要贡献。

沙米尔1952年出生在特拉维夫。在当地学校就读后，他进入特拉维夫大学，于1973年获得数学学士学位，然后进入魏茨曼研究所学习计算机科学，并获得硕士学位（1975年）和博士学位（1977年）。完成博士学位后，他在英国考文垂的华威大学呆了一年，以博士后的身份继续他的研究。1978年，他加入了麻省理工学院（MIT）的研究人员。

在麻省理工学院，他遇到了罗纳德-里维斯特（Ronald Rivest）和伦纳德-阿德尔曼（Leonard M. Adleman），他们与阿迪合作完成了密码学的基本进展。他们的灵感来自于密码学家Whitfield Diffie和Martin Hellman在1976年的一篇论文[3]，讨论了密码学的几个新发展。它描述了私人信息的发送者和接收者避免需要共享秘钥的方法，但它没有提供任何现实的方法来实现这些概念。Rivest、Shamir和Adleman在他们1977年的论文 "一种获得数字签名和公钥密码系统的方法"[1]中提出了实际的实现方法，该论文展示了如何轻松地对信息进行编码、发送至收件人，并进行解码，而被第三方看到的机会很少。

这种方法被称为公钥加密法，使用两个不同但在数学上有联系的密钥：一个用于加密信息的公钥，以及一个用于解密的完全不同的私钥。加密密钥由希望接收信息的个人公开，但秘密的解密密钥只有他们知道。这两把钥匙通过某种明确的数学关系联系在一起，但从公开的对应钥匙中确定解密钥匙要么是不可能的，要么是太昂贵了，以至于在实践中无法做到这一点。RSA "方法（来自三位作者名字的第一个字母）依赖于这样一个事实，即还没有人开发出一种有效的算法来处理非常大的整数。然而，并不能保证它永远困难；如果有一天大型量子计算机建成，它可能会打破这个系统。

关于RSA背后的理论和实践的详细讨论可以在这里找到。实现它的计算机代码相当简单，只要使用适当大的整数密钥，没有人知道如何破解一个编码信息。

RSA几乎被用于所有基于互联网的商业交易中。没有它，商业在线活动就不会像今天这样广泛。它允许用户在不安全的互联网上交流敏感信息，如信用卡号码，而不需要提前商定一个共享的秘密密钥。大多数人在互联网上订购物品时，除非注意到屏幕角落里的小挂锁符号，否则不知道该系统正在使用。RSA是一个抽象而优雅的理论的最好例子，它有很大的实际应用。

在1977年开发出基本方法后，三位图灵奖得主于1983年成立了RSA数据安全公司。该公司后来被Security Dynamics收购，后者又在2006年被EMC收购。它做过加密研究，赞助过会议，展示了早期的加密系统是如何被破坏的，并衍生出其他公司，如Verisign。当1983年RSA[2]的专利即将到期时，RSA数据安全公司公布了其实施的所有细节，这样就不会有任何人可以创造包含该方法的产品。

这三位图灵奖获得者并不知道，英国数学家Clifford Cocks在几年前就已经开发了类似的方法，他扩展了James H. Ellis更早的工作。科克斯当时在英国政府通信总部（GCHQ）从事加密工作，所以它被列为机密，直到1997年才被公布，也就是在里维斯特、阿德尔曼和沙米尔发表他们的独立发现的20年后。

阿迪的另一个贡献被称为沙米尔的秘密共享。这是一个在个人之间共享秘密的若干部分的方案，但它要求部分或全部人合作以揭示全部的秘密。它本质上是一种数学机制，相当于在发射洲际弹道导弹之前让几个人带着他们的物理和其他钥匙在场。该计划非常灵活，可以适应这样的情况，例如，一个资深人士可以单独解开秘密，但需要三个或更多的初级官员来解开答案。这里可以找到一个简单的例子。

沙米尔对密码学的兴趣促使他研究攻击信息解码的方法。他和Adi的研究生Eli Biham通常被认为是发明了被称为差分密码分析的方法，尽管在1993年Shamir和Biham关于该主题的书[4]公开发行之前，该机制显然已经被IBM和美国国家安全局（NSA）知道，并保持秘密。它涉及一系列测试，对纯文本信息进行编码变体，并注意由此产生的编码输出的差异。这可以用来发现密码显示非随机行为的地方，然后可以用来缓解秘钥的恢复。这一发现是在他们调查1977年数据加密标准（DES）的安全性时发现的，他们注意到编码的算法是以这样一种方式创建的，即使是一个小的修改也会使破解代码变得更加容易。事实证明，IBM和NSA已经对这些技术有所了解，在设计时故意考虑到了这一点。

阿迪的另一项进展被称为基于身份的密码学。在这种机制下，RSA中使用的公钥只是一些容易获得的关于信息潜在接收者的信息。它可以是收件人的电子邮件地址、域名或物理IP地址这样简单的东西。第一个实现基于身份的签名和基于电子邮件地址的系统是由Adi 1984[5]开发的。 它允许用户仅使用公开的信息对文件进行数字 "签名"。

Shamir还提出了一个非常类似的基于身份的加密方案，该方案令人感兴趣，因为它不要求用户获得用于加密信息的公钥。虽然Shamir在1984年就有了最初的概念，但第一个实际实现是在2001年由两个不同的小组完成的[6,7]。

1994年，Shamir与Moni Naor合作，产生了另一个有趣的方案，即视觉密码学[8]。 一幅图像（可以是文本）被分割开来，产生的碎片看起来只是白色和深色像素的随机散布。当所有的碎片都叠加在一起时，信息就出现了。这个方案的美妙之处在于，如果有人设法收集所有的碎片，但只有一个碎片，信息仍然是不可读的。它比 "不可读 "更有趣的是，有可能构建一个缺失的碎片，它将揭示任何信息，因此秘密将保持隐藏，直到最后一个真正的碎片被放置到位。虽然这听起来不错，但它也意味着拥有除一块以外的所有棋子的人能够通过构建最后一块棋子来显示他们喜欢的任何信息而进行欺骗。这里有一个简单的例子。