Bài giảng Mật mã ứng dụng: Lịch sử mật mã

M™t mã ˘ng dˆng L‡ch s˚ m™t mã

1 / 48

NÎi dung

1 Tr˜Óc n´m 76

2 Phát minh m™t mã khóa công khai và RSA

3 B˜Óc i ban ¶u

4 M™t mã trong th˜Ïng m§i

5 Chính sách m™t mã

6 Tßn công

7 Ti∏p theo là gì?

8 K∏t lu™n

Euclid — 300 B.C.

3 / 48

Có vô h§n sË nguyên tË: 2, 3, 5, 7, 11, 13, . . . ◊Óc chung lÓn nhßt cıa hai sË là dπ tính toán (Dùng thu™t toán Euclid): gcd(12, 30) = 6

M™t mã cıa ng˜Ìi Hy L§p — Que tròn

Greek Cryptography – The Scytale

4 / 48

Khóa bí m™t là chu vi cıa que tròn. Khóa này chia s¥ gi˙a ng˜Ìi g˚i An unknown period (the circumference of the scytale) và ng˜Ìi nh™n. is the secret key, shared by sender and receiver.

Pierre de Fermat (1601-1665) Leonhard Euler (1707–1783)

Fermat’s Little Theorem (1640): For any prime p and any a, 1

a < p:

1 = 1 (mod p)

vÓi 1 ap a < p ‡nh l˛ Fermat nh‰ (1640): VÓi mÂi sË nguyên tË p, ap = 1 (mod p), 

Euler’s Theorem (1736): If gcd(a, n) = 1, then

a(n) = 1 (mod n) ,

where (n) = # of x < n such that gcd(x, n) = 1. a(n) = 1 (mod n).

5 / 48

‡nh l˛ Euler (1736): N∏u gcd(a, n) = 1, thì

Carl Friedrich Gauss (1777-1855)

6 / 48

Published Disquisitiones Aritmeticae at age 21 “The problem of distinguishing prime numbers from com- “The problem of distinguishing prime numbers from posite numbers and of resolving the latter into their prime factors is known to be one of the most important and use- composite numbers and of resolving the latter into ful in arithmetic.... the dignity of the science itself seems to their prime factors is known to be one of the most require solution of a problem so elegant and so celebrated.” important and useful in arithmetic. . . . the dignity of the science itself seems to require solution of a problem so elegant and so celebrated.”

“What two numbers multiplied together will

produce 8616460799 ? I think it unlikely that

anyone but myself will ever know.”

Gave world’s ﬁrst factoring challenge:

Factored by Derrick Lehmer in 1903. (89681

96079)

William Stanley Jevons (1835–1882)

Published The Principles of Science (1874)

ã ˜a th˚ thách ¶u tiên phân tích th¯a sË:

“What two numbers multiplied together will produce 8616460799 ? I think it unlikely that anyone but myself will ever know.”

7 / 48

˜Òc phân tích bi Derrick Lehmer vào n´m 1903. (89681 96079) ⇤

World War I – Radio

A marvelous new communication technology—radio Chi∏n tranh th∏ giÓi th˘ I – Radio

(Marconi, 1895)—enabled instantaneous MÎt công nghª truy∑n thông mÓi – radio (Marconi, 1895) – communication with remote ships and forces, but also cho phép giao ti∏p t˘c thÌi vÓi t¶u và l¸c l˜Òng  xa, nh˜ng các gave all transmitted messages to the enemy. thông iªp cÙng g˚i cho c£ k¥ thù. Use of cryptography soars. Viªc s˚ dˆng m™t mã t´ng lên. •

Decipherment of Zimmermann Telegram by B£n gi£i mã cıa Zimmermann British made American Telegram bi Anh trong chi∏n tranh th∏ giÓi I involvement in World War I inevitable.

8 / 48

•

Alan Turing (1912–1954)

Developed foundations of theory of computability (1936).

9 / 48

Phát tri∫n cÏ s cıa l˛ thuy∏t tính toán (1936).

Work of Alan Turing and others at

Bletchley Park, and William

Friedman and others in the USA, on

breaking of Axis ciphers had great

success and immense impact.

Cryptanalytic effort involved

development and use of early

computers (Colossus).

World War II – Enigma, Purple, JN25, Naval Enigma

Chi∏n tranh th∏ giÓi II Enigma, Purple, JN25, Naval Enigma

Nh˙ng nÈ l¸c phá mã liên quan ∏n • viªc phát tri∫n và dùng máy tính thÌi ¶u tiên (Colossus).

M™t mã ˜Òc th¸c hiªn bi các máy Cryptography performed by • rotor. (typically, rotor) machines.

•

10 / 48

Công trình cıa Alan Turing và nh˙ng ng˜Ìi khác  Bletchley Park, và William Friedman và nh˙ng ng˜Ìi khác  Mˇ, trong viªc phá hª mã Axis ã có anh h˜ng vô cùng lÓn.

Work of Alan Turing and others at

Bletchley Park, and William

Friedman and others in the USA, on

breaking of Axis ciphers had great

success and immense impact.

Cryptanalytic effort involved

development and use of early

computers (Colossus).

World War II – Enigma, Purple, JN25, Naval Enigma

Chi∏n tranh th∏ giÓi II Enigma, Purple, JN25, Naval Enigma

M™t mã ˜Òc th¸c hiªn bi các máy Cryptography performed by • rotor. (typically, rotor) machines.

•

Công trình cıa Alan Turing và nh˙ng ng˜Ìi khác  Bletchley Park, và William Friedman và nh˙ng ng˜Ìi khác  Mˇ, trong viªc phá hª mã Axis ã có anh h˜ng vô cùng lÓn.

•

10 / 48

Nh˙ng nÈ l¸c phá mã liên quan ∏n viªc phát tri∫n và dùng máy tính thÌi ¶u tiên (Colossus).

Information-theoretic in character—proves

unbreakability of one-time pad. (Published 1949).

Claude Shannon (1916–2001)

“Communication Theory of Secrecy Systems” Sept

1945 (Bell Labs memo, classiﬁed).

• “Communication Theory of Secrecy Systems” Sept 1945 (Bell Labs memo, classified).

11 / 48

• L˛ thuy∏t thông tin – ch˘ng minh tính không phá mã ˜Òc cıa hª one-time-pad (Xußt b£n 1949).

David Kahn – The Codebreakers (1967)

Kahn – The Codebreakers

In 1967 David Kahn published

A monumental history of cryptography. NSA attempted to suppress its publication.

The Codebreakers—The Story of Secret Writing. ây là mÎt b£o tàng l‡ch s˚ cıa m™t mã. NSA ã cË g≠ng cßm xußt b£n nó.

12 / 48

The Codebreakers—The Story of Secret Writing.

DES – U.S. Data Encryption Standard (1976)

DES U.S. Data Encryption Standard (1976)

DES Designed at IBM; Horst Feistel supplied key DES ˜Òc thi∏t k∏ t§i IBM: Horst Feistel là ng˜Ìi thi∏t k∏ chính. NSA elements of design, such as ladder structure. NSA ã giúp thi∏t k∏, và gi˙ kích th˜Óc khóa 56 bit. (?) helped, in return for keeping key size at 56 bits.(?)

13 / 48

Î ph˘c t§p tính toán

Computational Complexity

Hartmanis

Stearns

Cook

Blum

Karp

Theory of Computational Complexity started in 1965 L˛ thuy∏t Î ph˘c t§p tính toán b≠t ¶u n´m 1965 bi by Hartmanis and Stearns; expanded on by Blum, Hartmanis và Stearns; phát tri∫n bi Blum, Cook, và Karp. Cook, and Karp.

•

Key notions: polynomial-time reductions;

NP-completeness.

14 / 48

Các khái niªm chính: quy d®n thÌi gian a th˘c; NP-¶y ı. •

NÎi dung

1 Tr˜Óc n´m 76

2 Phát minh m™t mã khóa công khai và RSA

3 B˜Óc i ban ¶u

4 M™t mã trong th˜Ïng m§i

5 Chính sách m™t mã

6 Tßn công

7 Ti∏p theo là gì?

8 K∏t lu™n

In November 1976, Difﬁe and Hellman published New

Directions in Cryptography, proclaiming

“We are at the brink of a revolution in

cryptography.”

Phát minh m™t mã khóa công khai

Invention of Public Key Cryptography

Ralph Merkle, and independently Marty Hellman and

•

16 / 48

• Ralph Merkle, và Îc l™p bi Marty Hellman và Whit Diffie, ã Whit Difﬁe, invented the notion of public-key phát minh ra khái niªm m™t mã khóa công khai. cryptography. Trong tháng 11 n´m 1976, Diffie và Hellman công bË bài báo “New Directions in Cryptography”, khØng ‡nh r¨ng “We are at the brink of a revolution in cryptography”.

M™t mã khóa công khai (theo Diffie/Hellman)

• MÈi bên A có mÎt khóa công khai P KA ∫ ng˜Ìi khác có th∫ dùng nó ∫ mã hóa thông iªp g˚i cho A:

C = P KA(M ).

• MÈi bên A cÙng có mÎt khóa bí m™t SKA dùng ∫ gi£i mã b£n mã C nh™n ˜Òc:

M = SKA(C).

•

17 / 48

Dπ dàng tính ˜Òc c∞p khóa công khai/bí m™t. Công khai P KA không gây lÎ SKA! Không th∫ tìm (v∑ m∞t tính toán) SKA t¯ P KA. V™y thì các khóa công khai có th∫ an toàn cßt  nÏi công cÎng cùng vÓi tên chı s h˙u.

Ch˙ k˛ iªn t˚ (theo Diffie/Hellman)

• ﬁ t˜ng: K˛ vÓi SKA; ki∫m tra ch˙ k˛ vÓi P KA. ˜a ra mÎt ch˙ k˛ cho thông iªp M •

= SKA(M )

• ˜a ra P KA, M , và , mÂi ng˜Ìi có th∫ ki∫m tra tính hÒp lª cıa ch˙ k˛ b¨ng cách ki∫m tra:

? = P KA().

18 / 48

MÎt ˛ t˜ng tuyªt vÌi! • Nh˜ng hÂ không bi∏t làm th∏ nào có th∫ cài ∞t nó. . . •

Security relies (in part) on inability to factor product n

of two large primes p, q.

PK = (n, e) where n = pq and gcd(e, (n)) = 1

SK = d where de = 1 mod (n)

Encryption/decryption (or signing/verify) are simple:

C = PK (M) = M e mod n

M = SK (C) = Cd mod n

RSA (Ron Rivest, Adi Shamir, Len Adleman, 1977)

19 / 48

Tính an toàn (mÎt ph¶n) d¸a trên tính khó phân tích ra th¯a sË nguyên tË cıa sË n là tích cıa hai sË nguyên tË lÓn. P K = (n, e) vÓi n = pq và gcd(e, (n)) = 1. SK = d vÓi de = 1 (mod n). Mã hóa/gi£i mã (ho∞c k˛/ki∫m tra ch˙ k˛) rßt Ïn gi£n: • • • C = P K(M ) = M e mod n; M = SK(C) = C d mod n

Offered copy of RSA technical memo.

Offered $100 to ﬁrst person to break challenge

ciphertext based on 129-digit product of primes.

(Our) estimated time to solution: 40 quadrillion years

Martin Gardner column and RSA-129 challenge Martin Gardner và th˚ thách RSA-129

Described public-key and RSA cryptosystem in his Mô t£ hª m™t mã khóa công khai và hª m™t RSA trong Scientiﬁc American column, Mathematical Games • Scientific American column, Mathematical Games.

Cung cßp b£n sao cıa b£n th£o kˇ thu™t cıa RSA. •

20 / 48

• T∞ng 100$ cho ng˜Ìi ¶u tiên gi£i b£n mã vÓi RSA-129 bit. (Tác gi£ RSA) d¸ ki∏n thÌi gian c¶n gi£i: 40 triªu t n´m.

Publication of RSA memo and paper

B£n th£o kˇ thu™t cıa RSA

I. Introduction

S.L. Graham, R.L. Rivest* Editors

The era of "electronic mail" [10] may soon be upon us; we must ensure that two important properties of the current "paper mail" system are preserved: (a) messages are private, and (b) messages can be signed. We demonstrate in this paper how to build these capabilities into an electronic mail system.

Programming Techniques A Method for Obtaining Digital Signatures and Public- Key Cryptosystems

R. L. Rivest, A. Shamir, and L. Adleman MIT Laboratory for Computer Science and Department of Mathematics

An encryption method is presented with the novel

At the heart of our proposal is a new encryption method. This method provides an implementation of a "public-key cryptosystem", an elegant concept in- vented by Diffie and Hellman [1]. Their article moti- vated our research, since they presented the concept but not any practical implementation of such a system. Readers familiar with [1] may wish to skip directly to Section V for a description of our method.

II. Public-Key Cryptosystems

In a "public-key cryptosystem" each user places in a public file an encryption procedure E. That is, the public file is a directory giving the encryption proce- dure of each user. The user keeps secret the details of his corresponding decryption procedure D. These pro- cedures have the following four properties:

(a) Deciphering the enciphered form of a message M

yields M. Formally,

D(E(M)) = M.

(I)

(b) Both E and D are easy to compute.

(c) By publicly revealing E the user does not reveal an easy way to compute D. This means that in practice only he can decrypt messages encrypted with E, or compute D efficiently.

(d) If a message M is first deciphered and then enci-

property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences: (1) Couriers or other secure means are not needed to transmit keys, since a message can be enciphered using an encryption key publicly revealed by the intended recipient. Only he can decipher the message, since only he knows the corresponding decryption key. (2) A message can be "signed" using a privately held decryption key. Anyone can verify this signature using the corresponding publicly revealed encryption key. Signatures cannot be forged, and a signer cannot later deny the validity of his signature. This has obvious applications in "electronic mail" and "electronic funds transfer" systems. A message is encrypted by representing it as a number M, raising M to a publicly specified power e, and then taking the remainder when the result is divided by the publicly specified product, n, of two large secret prime numbers p and q. Decryption is similar; only a different, secret, power d is used, where e * d ------ l(mod (p - 1) * (q - 1)). The security of the system rests in part on the difficulty of factoring the published divisor, n.

phered, M is the result. Formally,

Key Words and Phrases: digital signatures, public-

E(D(M)) = M.

(2)

key cryptosystems, privacy, authentication, security, factorization, prime number, electronic mail, message- passing, electronic funds transfer, cryptography. CR Categories: 2.12, 3.15, 3.50, 3.81, 5.25

An encryption (or decryption) procedure typically consists of a general method and an encryption key. The general method, under control of the key, enciphers a message M to obtain the enciphered form of the message, called the ciphertext C. Everyone can use the same general method; the security of a given procedure will rest on the security of the key. Revealing an encryption algorithm then means revealing the key.

General permission to make fair use in teaching or research of all or part of this material is granted to individual readers and to nonprofit libraries acting for them provided that A C M ' s copyright notice is given and that reference is m a d e to the publication, to its date of issue, and to the fact that reprinting privileges were granted by permission of the Association for C o m p u t i n g Machinery. To otherwise reprint a figure, table, other substantial excerpt, or the entire work requires specific permission as does republication, or systematic or multiple reproduction.

This research was supported by National Science Foundation grant MCS76-14294, and the Office of Naval Research grant n u m b e r N00014-67-A-0204-0063.

When the user reveals E he reveals a very inefficient method of computing D(C): testing all possible mes- sages M until one such that E(M) = C is found. If property (c) is satisfied the number of such messages to test will be so large that this approach is impractical.

* Note. This paper was submitted prior to the time that Rivest became editor of the d e p a r t m e n t , and editorial consideration was completed u n d e r the former editor, G. K. Manacher.

A u t h o r s ' Address: MIT Laboratory for C o m p u t e r Science, 545

A function E satisfying (a)-(c) is a "trap-door one- way function;" if it also satisfies (d) it is a "trap-door one-way permutation." Diffie and Hellman [1] intro- duced the concept of trap-door one-way functions but

1 2 0

C o m m u n i c a t i o n s of the A C M

February 1978 Volume 21 N u m b e r 2

LCS-82 Technical Memo (April 1977) LCS-82 Technical Memo (April 1977) và CACM article (Feb 1978) CACM article (Feb 1978)

21 / 48

Alice and Bob (1977, in RSA paper) Alice and Bob (1977, in RSA paper)

Alice và Bob (1977, trong bài báo RSA)

PKA PKA PKA(M) PKA(M)

Alice and Bob now have a life of their own—they Alice and Bob now have a life of their own—they appear in hundreds of crypto papers, in xkcd, and Alice và Bob ã có cuÎc sËng riêng–HÂ xußt hiªn trong hàng nghìn appear in hundreds of crypto papers, in xkcd, and bài báo m™t mã, trong xkcd, và th™m chí có c£ trang Wiki riêng. even have their own Wikipedia page: even have their own Wikipedia page:

22 / 48

Independent Invention of Public-Key Revealed

Phát minh Îc l™p v∑ m™t mã ˜Òc ti∏t lÎ

In 1999 GCHQ announced that James Ellis, Clifford N´m 1999 GCHQ thông báo r¨ng James Ellis, Clifford Cocks, và Cocks, and Malcolm Williamson had invented Malcolm Williamson ã phát minh ra m™t mã khóa công khai, thu™t public-key cryptography, the “RSA” algorithm, and toán “RSA”, và “trao Íi khóa Diffie-Hellman key exchange” trong “Difﬁe-Hellman key exchange” in the 1970’s, before nh˙ng n´m 1970. their invention outside.

23 / 48

NÎi dung

1 Tr˜Óc n´m 76

2 Phát minh m™t mã khóa công khai và RSA

3 B˜Óc i ban ¶u

4 M™t mã trong th˜Ïng m§i

5 Chính sách m™t mã

6 Tßn công

7 Ti∏p theo là gì?

8 K∏t lu™n

Loren Kohnfelder Phát minh ra Ch˘ng th˜ sË

Loren Kohnfelder – Invention of Digital Certiﬁcates

•

Towards a Practical Public-key Cryptosystem

by

Loren M Kohnfelder

Submitted in Partial Fulfillment

of the Requirements for the

Dr^ree of Bachelor QI Science

at the

Massachusetts Institute of Technology

May, 1978

Signature of Author

t oi El/ctrlcpl Engineering! May 10, 1978

Certified by

Thesis Supervisor

Accepted by

Chairman, Departmental Committee on

Theoretical Foundations of Security

CÏ s l˛ thuy∏t cıa tính an toàn

“Probabilistic Encryption” Shaﬁ Goldwasser, Silvio Micali (1982) (Encryption should be randomized!)

• “Probabilistic Encryption” Shafi Goldwasser, Silvio Micali (1982) (Mã hóa nên ng®u nhiên!)

•

27 / 48

“A Digital Signature Scheme Secure Against Adaptive Chosen Message Attacks” Goldwasser, Micali, Rivest (1988) (Dùng khái niªm trò chÏi ∫ ‡nh nghæa rõ mˆc tiêu an toàn).

Hª mã dòng RC4 (Rivest, 1987)

RC4 là hª mã dòng ˜Òc dùng rÎng rãi nhßt. •

•

i = ( i + 1) mod 256 j = ( j + S [ i ]) mod 256 swap S [ i ] and S [ j ] Output S [( S [ i ] + S [ j ]) mod 256]

Không ph£i hª mã khóa công khai; b£n mã ˜Òc tính b¨ng cách lßy tuy∫n lo§i mÎt dãy bit gi£ ng®u nhiên vÓi b£n rõ. Vô cùng Ïn gi£n và nhanh: Dùng m£ng S[0..255] ∫ gi˙ mÎt hoán v‡ cıa 0..255, ˜Òc khi t§o dùng khóa bí m™t, và dùng hai con tr‰ i, j trong S. ∫ ˜a ra mÎt byte gi£ ng®u nhiên:

28 / 48

• ˜Òc dùng trong: WEP, BitTorrent, SSL, Kerberos, PDF, Skype,. . .

Hàm b´m MD5 (Rivest, 1991) MD5 Cryptographic Hash Function (Rivest, 1991)

File

MD5

(128-bit)

hash

•

29 / 48

• MD5 ˜Òc ∑ xußt nh˜ hàm gi£ ng®u nhiên. Nó ánh x§ file MD5 proposed as pseudo-random function mapping thành “dßu vân tay” 128-bit. (là mÎt bi∏n th∫ cıa MD4). I ﬁles to 128-bit ﬁngerprints. (variant of earlier MD4) Collision-resistance was a design goal – it should be MD5 ˜Òc thi∏t k∏ vÓi mˆc ích kháng xung Ît–không th∫ tìm infeasible to ﬁnd two ﬁles with the same ﬁngerprint. ˜Òc hai file vÓi cùng dßu vân tay. Many, many uses (e.g. in digital signatures) – very ˜Òc s˚ dˆng rßt rÎng rãi, và là mÎt mô hình chu©n nhi∑u thi∏t widely used, and a model for many other later hash k∏ cıa các hàm b´m sau này. function designs.

NÎi dung

1 Tr˜Óc n´m 76

2 Phát minh m™t mã khóa công khai và RSA

3 B˜Óc i ban ¶u

4 M™t mã trong th˜Ïng m§i

5 Chính sách m™t mã

6 Tßn công

7 Ti∏p theo là gì?

8 K∏t lu™n

U.S. Patent 4,405,829

B¨ng sáng ch∏  Mˇ 4,405,829

Filed December 1977 (MIT TLO) NÎp hÁ sÏ tháng 12 n´m 1977 (MIT TLO) Issued September 1983 ˜Òc cßp tháng 9 n´m 1983

31 / 48

Lotus (1987), Motorola, Apple, Novell, Netscape,

Microsoft, ...

RSA Conference series (1991)

Verisign spun out in 1995

1.3 billion certiﬁcate status checks/day

65 billion DNS requests/day (DNSSEC coming)

RSA acquired by Security Dyamics in 1996,

now part of EMC.

Công ty RSA (1983)

RSA the company (1983)

Jim Bidzos joined in 1986 Jim Bidzos ã tham gia n´m 1986 Lotus(1987), Motorola, Apple, Novell, Netscape, Microsoft, ... ChuÈi hÎi ngh‡ RSA (1991) Verisign tách ra vào n´m 1995

• • • •

1.3 tø l¶n ki∫m tra tr§ng thái ch˘ng th¸c mÈi ngày 65 tø DNS g˚i mÈi ngày (DNSSEC s≠p ra)

32 / 48

• RSA b‡ mua bi Security Dyamics n´m 1996, bây giÌ thuÎc EMC.

World Wide Web (Sir Tim Berners-Lee, 1990)

World Wide Web Sir Tim Berners-Lee, 1990

Just as radio did, this new communication medium,

the World-Wide Web, drove demand for cryptography • to new heights.

Cemented transition of cryptography from primarily

Môi tr˜Ìng truy∑n thông mÓi World-Wide Web ã ˜a yêu c¶u v∑ m™t mã lên mÎt t¶m cao mÓi.

33 / 48

M™t mã, mÎt lænh v¸c ˜Òc dùng chı y∏u trong quân s¸, bây giÌ ˜Òc s˚ dˆng chı y∏u cho th˜Ïng m§i. • military to primarily commercial.

NÎi dung

1 Tr˜Óc n´m 76

2 Phát minh m™t mã khóa công khai và RSA

3 B˜Óc i ban ¶u

4 M™t mã trong th˜Ïng m§i

5 Chính sách m™t mã

6 Tßn công

7 Ti∏p theo là gì?

8 K∏t lu™n

cations. Some people probably believe

ton, where Alsabti was almost accepted

it. But the cases where somebody is hot it. But the cases where somebody is hot on their trail are the exceptions rather on their trail are the exceptions rather than the rule." than the rule."

into a residency program in neurosur- into a residency program in neurosur- gery-until a researcher who had worked gery-until a researcher who had worked with. Alsabti told an administrator at Bay- with. Alsabti told an administrator at Bay- lor the details of his academic rise. lor the details of his academic rise.

U.S. cryptography policy evolves

Phát tri∫n cıa chính sách m™t mã  Mˇ

don't have to pad." In marginal cases, don't have to pad." In marginal cases, however, Relman admits that the art of however, Relman admits that the art of creative bibliography reading is becom- creative bibliography reading is becom- ing more complex. "You have to know ing more complex. "You have to know the journals, and what impact they have the journals, and what impact they have on the fields. You have to know the on the fields. You have to know the institutions, the people, the meetings. institutions, the people, the meetings. You can quickly sort out the papers that You can quickly sort out the papers that are derivative and not original. With the are derivative and not original. With the original, you then have to decide which original, you then have to decide which people are the driving force behind the people are the driving force behind the research and which were the also-rans. research and which were the also-rans. It's a ticklish matter." It's a ticklish matter."

U.S. government initially tried to control and limit • public-sector research and use of cryptography

Ban ¶u, chính phı Mˇ cË g≠ng ki∫m soát và giÓi h§n cÎng Áng nghiên c˘u và s˚ dˆng m™t mã.

Rather than trying to cope with the Rather than trying to cope with the effects of paper inflation, some research- effects of paper inflation, some research- ers have recommended radical steps to ers have recommended radical steps to prevent the growth of padded bibliogra- prevent the growth of padded bibliogra- phies in the first place. Durack, writing phies in the first place. Durack, writing in the 6 April 1978 New England Joarnsl in the 6 April 1978 New England Joarnsl of Medicine, says, half-seriously, that of Medicine, says, half-seriously, that the National Institutes of Health should the National Institutes of Health should limit the number of papers by each au- limit the number of papers by each au- thor to five per year, with a stepwise thor to five per year, with a stepwise reduction in funding as an automatic reduction in funding as an automatic penalty for each paper published above penalty for each paper published above five. Other observers, instead of recom- five. Other observers, instead of recom- mending a reliance on bureaucratic sanc- mending a reliance on bureaucratic sanc- tions, have called for-rigorous self-re- tions, have called for-rigorous self-re- straint by researchers straint by researchers

Attempt to chill research via ITAR (1977) CË g≠ng h§n ch∏ nghiên c˘u thông qua ITAR (1977). MIT “Changing Nature of Information” Committee MIT “Changing Nature of Information” ıy ban gÁm • (1981; Dertouzos, Low, Rosenblith, Deutch,Rivest,...) (1981; Dertouzos, Low, Rosenblith, Deutch,Rivest,...)

•

Self-restraint is beside the point to Self-restraint is beside the point to some observers. They say there is a good some observers. They say there is a good side to paper inflation because it forces side to paper inflation because it forces - administrators and those who judge re- - administrators and those who judge re- search careers to dig beneath appear- search careers to dig beneath appear- ances on a bibliography and discover the ances on a bibliography and discover the truly worthwhile aspects of a research truly worthwhile aspects of a research record. But to many others, who are record. But to many others, who are faced with a growing horde of journals faced with a growing horde of journals filled with fragmented and redundant re- filled with fragmented and redundant re- search paper inflation represents a time- search paper inflation represents a time- consuming chore. It may even affect consuming chore. It may even affect Nobel laureates. At 7:40 one recent Nobel laureates. At 7:40 one recent morning, Science called Watson at Cold morning, Science called Watson at Cold Spring Harbor, where te is now the Spring Harbor, where te is now the director, and inquired if he would dis- director, and inquired if he would dis- cuss some of the issues involving paper cuss some of the issues involving paper inflation. "I have no time," he said at a inflation. "I have no time," he said at a brisk clip, and then added right before brisk clip, and then added right before he hung up, "My life is too busy." he hung up, "My life is too busy." Perhaps he was buried in a stack of Perhaps he was buried in a stack of journals struggling to keep up with the journals struggling to keep up with the literature. WILLIAM J. BROAD literature. WILLIAM J. BROAD

Since only a few administrators have Since only a few administrators have the time and sophistication to sift the time and sophistication to sift through a thick bibliography that at first through a thick bibliography that at first glance looks promisingS problems and glance looks promisingS problems and misjudgments are probably more com- misjudgments are probably more com- mon than is ever admitted. A recent mon than is ever admitted. A recent example is the case of Elias A. K. Al- example is the case of Elias A. K. Al- sabti, a 25-year-old researcher from Jor- sabti, a 25-year-old researcher from Jor- dan who listed 60 papers on his curricu- dan who listed 60 papers on his curricu- lum vitae (Science, 27 June 1980). Al- lum vitae (Science, 27 June 1980). Al- sabti had pirated at least seven of his sabti had pirated at least seven of his papers and published them in obscure papers and published them in obscure journals. This, however, was unknown to journals. This, however, was unknown to administrators at Baylor College in Hous- administrators at Baylor College in Hous-

Since an element of self-deception Since an element of self-deception probably plays a part in the whole pro- probably plays a part in the whole pro- cess, attempts at restraint may not have cess, attempts at restraint may not have much impact. Says one geneticist: "Pri- much impact. Says one geneticist: "Pri- ority is the rationale that is used for lots ority is the rationale that is used for lots of this publishing, for the brief communi- of this publishing, for the brief communi-

Cryptography Policy Cryptography Policy

Seeks Seeks

Committee Committee

MIT MIT

Questions of who should do research on cryptography and Questions of who should do research on cryptography and how results should be disseminated are the first order of business how results should be disseminated are the first order of business

quences for individuals and for society if quences for individuals and for society if computers continue to be connected, as computers continue to be connected, as they are now, according to local deci- they are now, according to local deci- sions by individual entrepreneurs. The sions by individual entrepreneurs. The security of computer data varies greatly security of computer data varies greatly and there is no general assurance that and there is no general assurance that data are safe. data are safe.

35 / 48

easy to send computer programs be- easy to send computer programs be- tween connected machines and to in- tween connected machines and to in- struct a program to search for select, struct a program to search for select, and copy data from anywhere in a net- and copy data from anywhere in a net- work. Then the program can be instruct- work. Then the program can be instruct- Science, 13 Mar 1981 ed to remove itself without leaving a ed to remove itself without leaving a trace. By analogy, he says, "Consider a trace. By analogy, he says, "Consider a network of filing cabinets, connected by network of filing cabinets, connected by subterranean tunnels. Now imagine that subterranean tunnels. Now imagine that agents can crawl through these tunnels, agents can crawl through these tunnels, copy anything they want from any of the copy anything they want from any of the files, and leave with no signs of their files, and leave with no signs of their presence. That is one of the situations presence. That is one of the situations we are faced with.' we are faced with.'

Other issues that will arise as comput-

Within the next 10 yearse networks Within the next 10 yearse networks consisting of tens of,thousands of com- consisting of tens of,thousands of com- puters will connect businessesS corpora- puters will connect businessesS corpora- tions, and banks in giant webs, predicts tions, and banks in giant webs, predicts Michael Dertouzos, director of the Lab- Michael Dertouzos, director of the Lab- oratory for Computer Science at the oratory for Computer Science at the Massachusetts Institute of Technology. Massachusetts Institute of Technology. But the interconnectedness of these But the interconnectedness of these computers, which is their very strength, computers, which is their very strength, is also their weakness he says. Unless is also their weakness he says. Unless steps are taken to assure the privacy of steps are taken to assure the privacy of computer data and to assure that com- computer data and to assure that com- puter messages can be i'signed,'S it be- puter messages can be i'signed,'S it be- comes extraordinarily easy to commit comes extraordinarily easy to commit crimes and hard to detect them. crimes and hard to detect them.

Last fall, MIT formed a committeeS Last fall, MIT formed a committeeS headed by Dertouzos and called Qn the headed by Dertouzos and called Qn the Changing Nature of Information, to look Changing Nature of Information, to look into questions of computer security and into questions of computer security and other matters arising from the prolifera- other matters arising from the prolifera- tion of computer networks. The commit- tion of computer networks. The commit- tee's members include Francis Low and tee's members include Francis Low and Walter Rosenblith, the current and past Walter Rosenblith, the current and past

er networks proliferate, the MIT com-

Although a number of computer

provosts of MIT and John Deutch, the

mittee predictsS are questions about

crimes have been reported, many more

under secretary of energy in the Carter

what types of data should be stored in

are not because banks and corporations

Administration. They also include a

computers and for how longe how pro-

do not wish to publicize the weaknesses

computer scientist and lawyer, and pro-

grams can be protected since they can

of their systems. And the crimes that are

fessors of political scienceS philosophy,

neither be patented nor effectively copy-

detected, many experts believe, are only

and management.

the tip- of the iceberg. The FBI, aware of

righted5 the extent to which information

As Dertouzos explains, even if a com-

this problem, has mounted a major effort

should be treated as property, and who is

puter is thought of simply as a filing

to detect computer crimes in the banking

liable if a mistake is made, for example in

cabinet, the problem of preventing crime

industry.

a medical diagnosis that is assisted by a

is considerable. The very power of the

Dertouzos and others at MIT are ex-

computer. Although the committee in-

computer can be used to break the de-

tremely concerned about the conse-

tends eventually to address these ques-

fenses of the installation. It is relatively

1 139

0036-8075/811613-1139$00.50/0 CQPYNght t 1981 AAAS

SCIENCE, VOL. 21l, 13 MARCH 198}

U.S. cryptography policy evolves

Phát tri∫n cıa chính sách m™t mã  Mˇ

U.S. government tried to mandate availability of all encryption keys via “key escrow” and/or “Clipper Chip” (1993)

• Chính phı Mˇ yêu c¶u khóa mã hóa qua “key escrow” và/ho∞c “Clipper Chip” (1993)

•

Today, US policy leans toward strong cybersecurity, including strong cryptography, for all information systems as a matter of national security.

36 / 48

Ngày nay, chính sách cıa Mˇ nghiêng v∑ an toàn m§ng, bao gÁm m™t mã m§nh, cho mÂi hª thËng thông tin nh˜ mÎt ph¶n cıa an ninh quËc gia.

NÎi dung

1 Tr˜Óc n´m 76

2 Phát minh m™t mã khóa công khai và RSA

3 B˜Óc i ban ¶u

4 M™t mã trong th˜Ïng m§i

5 Chính sách m™t mã

6 Tßn công

7 Ti∏p theo là gì?

8 K∏t lu™n

Phân tích cıa RSA-129 (Tháng 4 n´m 1994)

•

RSA-129 = 11438162575788886766923577997614661201021829 67212423625625618429357069352457338978305971 23563958705058989075147599290026879543541

•

Derek Atkins, Michael Graff, Arjen Lenstra, Paul Leyland: RSA-129 = 34905295108476509491478496199038981334177646 38493387843990820577 x 32769132993266709549961988190834461413177642 967992942539798288533

• 8 tháng làm viªc bi kho£ng 600 ng˜Ìi tình nguyªn t¯ hÏn 20 n˜Óc; 5000 MIPS-n´m.

38 / 48

Bí m™t: The Magic Words Are Squeamish Ossifrage •

39 / 48

Factoring Records

Digits

600

500

400

300

⇥

200

⇥

100

Year

2000

2010

2020

2030

2040

40 / 48

In 2001, researchers at IBM used this algorithm on a

(real) quantum computer to factor 15 = 3

Dark clouds on horizon for RSA?

Phân tích th¯a sË nguyên tË trên máy tính l˜Òng t˚

Factoring on a Quantum Computer?

•

In 1994, Peter Shor invented a fast factorization algorithm that runs on a (hypothetical) quantum N´m 1994, Peter Shor ã tìm ra mÎt thu™t toán phân tích th¯a computer and works by determining multiplicative sË ch§y trong thÌi gian a th˘c trên máy tính l˜Òng t˚. period of elements mod n. N´m 2001, các nhà khoa hÂc cıa IBM ã dùng thu™t toán này trên mÎt máy l˜Òng t˚ (th™t) ∫ phân tích 15 = 3

41 / 48

• 5. ⇥

NIST now running competition for new hash function

standard (SHA-3).

Tßn công hàm b´m

Hash Function Attacks

In 2004 Xiaoyun Wang and colleagues found a way to N´m 2004, Xiaoyun Wang và Áng nghiªp ã tìm ra cách ∫ t§o ra xung Ît cho hàm b´m MD5:

!!! !!!

MD5(ﬁle1) = MD5(ﬁle2) MD5(file1) = MD5(file2)

• produce collisions for MD5:

và cho c£ SHA-1 và nhi∑u hàm b´m khác.

Also for SHA-1 and many other hash functions. Major break!! •

42 / 48

NÎi dung

1 Tr˜Óc n´m 76

2 Phát minh m™t mã khóa công khai và RSA

3 B˜Óc i ban ¶u

4 M™t mã trong th˜Ïng m§i

5 Chính sách m™t mã

6 Tßn công

7 Ti∏p theo là gì?

8 K∏t lu™n

Các th˚ thách

Làm cho các k∏t qu£ m™t mã tr nên th¸c t∏. • Có ph£i bài toán phân tích sË là th¸c s¸ khó? •

44 / 48

• Ch˘ng minh P • 6 TËi thi∫u hóa các gi£ s˚ trong m™t mã. = N P. Liªu máy tính l˜Òng t˚ có th¸c t∏? • ˜a Alice và Bob lên iªn tho§i thông minh! • Xây d¸ng n∑n t£ng m™t mã cho các hª thËng dπ b‡ tßn công. •

NÎi dung

1 Tr˜Óc n´m 76

2 Phát minh m™t mã khóa công khai và RSA

3 B˜Óc i ban ¶u

4 M™t mã trong th˜Ïng m§i

5 Chính sách m™t mã

6 Tßn công

7 Ti∏p theo là gì?

8 K∏t lu™n

K∏t lu™n

•

M™t mã không ph£i là gi£i pháp cho mÂi vßn ∑ cıa an toàn không gian m§ng, nh˜ng nó là thành ph¶n cÏ s cıa mÂi lÌi gi£i.

•

Các nghiên c˘u trong m™t mã là s¸ k∏t hÒp tuyªt vÌi cıa toán hÂc, thËng kê, l˛ thuy∏t khoa hÂc máy tính, kˇ thu™t iªn và tâm l˛ hÂc.

• Dù ã có nhi∑u thành t¸u trong vài chˆc n´m v¯a qua, nh˜ng v®n còn rßt nhi∑u th˘ ph£i làm.

46 / 48

M™t mà là mÎt lænh v¸c rßt thú v‡! •

Tài liªu tham kh£o

Các slides này ˜Òc d‡ch t¯

The growth of cryptography

47 / 48

cıa Ronald L. Rivest.

48 / 48

M™t mã ˘ng dˆng Các thành ph¶n m™t mã cÏ b£n

1 / 7

MÎt ph¶n b˘c tranh m™t mã

2 / 7

Tính toàn vµn Tính bí m™t Mã khóa Ëi x˘ng Mã xác th¸c thông Ëi iªp (MAC) Mã khóa công khai Ch˙ k˛ iªn t˚ Khóa x˘ng Khóa công khai

M™t mã khóa Ëi x˘ng

Thu™t toán:

sinh khóa Î dài ) K C Gen(1 Enc(K, M ) mã hóa thông iªp M vÓi khóa K, k∏t qu£

là b£n mã C gi£i mã C dùng khóa K ∫ lßy ˜Òc M . M = Dec(K, C)

S˚ dˆng trong th¸c t∏.

• N∏u chø c¶n tính bí m™t: AES-128 vÓi CBC mode ho∞c CTR mode.

3 / 7

• N∑u c¶n c£ tính bí m™t và xác th¸c: EAX, CCM, ho∞c GCM mode

M™t mã khóa công khai

Hª m™t mã RSA • Hª m™t mã d¸a trên ˜Ìng cong Elliptic (ECC) •

Thu™t toán:

Gen(1 ) (SK, P K) C Enc(P K, M )

sinh c∞p khóa (bí m™t, công khai) Î dài mã hóa thông iªp M vÓi khóa công khai P K, k∏t qu£ là b£n mã C gi£i mã C dùng khóa bí m™t SK ∫ ˜Òc M . M = Dec(SK, C)

Ví dˆ.

4 / 7

Giao th˘c trao Íi khóa Diffie-Hellman (DH) •

M™t mã khóa công khai

Hª m™t mã d¸a trên ˜Ìng cong Elliptic (ECC) •

Thu™t toán:

Gen(1 ) (SK, P K) C Enc(P K, M )

sinh c∞p khóa (bí m™t, công khai) Î dài mã hóa thông iªp M vÓi khóa công khai P K, k∏t qu£ là b£n mã C gi£i mã C dùng khóa bí m™t SK ∫ ˜Òc M . M = Dec(SK, C)

Ví dˆ.

4 / 7

Giao th˘c trao Íi khóa Diffie-Hellman (DH) • Hª m™t mã RSA •

M™t mã khóa công khai

Thu™t toán:

Gen(1 ) (SK, P K) C Enc(P K, M )

sinh c∞p khóa (bí m™t, công khai) Î dài mã hóa thông iªp M vÓi khóa công khai P K, k∏t qu£ là b£n mã C gi£i mã C dùng khóa bí m™t SK ∫ ˜Òc M . M = Dec(SK, C)

Ví dˆ.

4 / 7

Giao th˘c trao Íi khóa Diffie-Hellman (DH) • Hª m™t mã RSA • Hª m™t mã d¸a trên ˜Ìng cong Elliptic (ECC) •

Kích th˜Óc khóa (theo bit) Khuy∏n ngh‡ cıa NIST

5 / 7

AES DH & RSA ECC 160 1024 80 224 2048 112 256 3072 128 384 7680 192 512 15360 256

Mã xác th¸c thông iªp

Thu™t toán:

) Gen(1 S(k, m) k t V (k, m, t) sinh khóa Î dài t§o ch˙ k˛ thông iªp m dùng khóa k “yes” ho∞c “no” cho bi∏t ch˙ k˛ t có ph£i là ch˙ k˛ hÒp lª cıa m hay không.

6 / 7

Ví dˆ. HMAC.

Ch˙ k˛ iªn t˚

Thu™t toán:

Gen(1 ) (sk, pk) t S(sk, m)

V (pk, m, t) sinh khóa bí m™t và công khai Î dài t§o ch˙ k˛ thông iªp m dùng khóa bí m™t sk “yes” ho∞c “no” cho bi∏t ch˙ k˛ t có ph£i là ch˙ k˛ hÒp lª cıa m hay không.

7 / 7

Ví dˆ. RSA, DSA, ECDSA