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.
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 3 / 48
M™t mã cıa ng˜Ìi Hy L§p — Que tròn
Greek Cryptography – The Scytale Khóa An bí unkno m™t là wn chu per vi ciod ıa (the que circumf tròn. erence Khóa này of the chia s¥ scytale) gi˙a ng˜Ìi g˚i is the secret key, shared và ng b ˜Ìi y sender nh™n. and receiver. 4 / 48 Pierre de Fermat (1601-1665) Pierre de Fermat Leonhard
(1601-1665) Euler (1707–1783) Leonhard Euler (1707–1783)
Fermat’s Little Theorem (1640): ‡nh l˛ F For an ermat y nhpr ‰ ime p and (1640): an VÓyi a, m 1 Âi s a < Ë p: nguyên tË p, ap 1 = 1 (mod p) Euler’s ap 1 Theorem = 1 (1736): (mod p), vÓi 1  a < p If gcd(a, n) = 1, then
‡nh l˛ Euler (1736): Na∏ (un)gcd 1, thì = 1 (a, n (mod ) = n) ,
where (n) = # of x < n such that gcd(x, n) = 1.
a (n) = 1 (mod n). 5 / 48 Carl Friedrich Carl Gauss Friedrich Gauss (1777-1855) (1777-1855)
Published Disquisitiones Aritmeticae at age 21
“The problem of distinguishing prime numbers from com- “The problem posite of distinguishing
numbers and of resolving pr the ime latter numbers into their from prime composite n factors umbers is known to and be of one of resolving the most the latter important and into use- their prime ful in factors is arithmetic.... kno the wn dignity to of be the one science of the itself most seems to
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 6 / 48
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 first factoring challenge:
Factored by Derrick Lehmer in 1903. (89681 96079)
William Stanley Jevons (1835–1882)
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.”
˜Òc phân tích bi Derrick Lehmer vào n´m 1903. (89681 ⇤ 96079) 7 / 48 World War I – Radio A marv Chi∏ elous n tranh new th∏ comm giÓi th˘ unicationI – Radio technology—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ù. • Viªc s Use ˚ d of ˆng cr m™t mã yptogr t´ng aph lên. y soars. Decipherment of B£n gi£Zimmer i mã cıa mann T Zimmermaeleg nn ram by T Br elegram itish bi made Anh trong Amer chi∏n ican tranh in th∏ volv giÓi Iement in World War I inevitable. 8 / 48
Alan Turing (1912–1954)Alan Turing (1912–1954)
Developed foundations of theory of computability
Phát tri∫n cÏ s cıa l˛ thuy∏t tính toán (1936). (1936). 9 / 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).
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). Chi∏n tranh th∏ giÓi II
World War II – Enigma, Purple, JN25, Naval Enigma
Enigma, Purple, JN25, Naval Enigma •Cryptog M™t raph mã y ˜Ò perf c th or ¸ med c hiª b n ybi các máy (typically rotor. , 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
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). Chi∏n tranh th∏ giÓi II
World War II – Enigma, Purple, JN25, Naval Enigma
Enigma, Purple, JN25, Naval Enigma •Cryptog M™t raph mã y ˜Ò perf c th or ¸ med c hiª b n ybi các máy (typically rotor. , 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.
• 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). 10 / 48
Information-theoretic in character—proves
unbreakability of one-time pad. (Published 1949). Claude Shannon (1916–2001) Claude Shannon (1916–2001)
“Communication Theory of Secrecy Systems” Sept
1945 (Bell Labs memo, classified).
• “Communication Theory of Secrecy Systems” Sept 1945 (Bell Labs memo, classified).
• 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). 11 / 48
David Kahn – The Codebreakers (1967) Kahn – The Codebreakers In 1967 David Kahn published The The Codebreakers—The Codebreakers—The Stor Story of y of Secret Secret W Wr riting. iting. ây là Ammon Ît b umental £o tàng l histor ‡ch s˚ycof ıacryptog m™t raph mã. y. NSA ã cË g≠ng cßm xußt
NSA attempted to suppress its publication. b£n nó. 12 / 48
DES – U.S. Data Encryption Standard DES (1976)
U.S. Data Encryption Standard (1976)
DES Designed at IBM; Horst Feistel supplied key elements DES ˜Òc of thi∏t design, k∏ t§i such IBM: Horst as F ladder eistel là ng str ˜Ìi ucture thi∏t k∏ . NSA chính. NSA helped, ã giúp in thi∏t retur k∏, n và f gi or ˙ keeping kích th˜Óc key khóa siz 56 e bit. at (?) 56 bits.(?) 13 / 48 Computational Complexity Î ph˘c t§p tính toán Hartmanis Stearns Blum Cook Karp
Theory of Computational Complexity started in 1965 by• Har L˛ tmanis thuy∏t Î and ph˘c Stear t§p ns; tính expanded toán b≠t ¶u n on ´m by Blum, 1965 bi Cook, and Kar
Hartmanis vàp.Stearns; phát tri∫n bi Blum, Cook, và Karp. Ke•y notions: Các khái ni polynomial-time
ªm chính: quy d®n reductions;
thÌi gian a th˘c; NP- ¶y ı. NP-completeness. 14 / 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
In November 1976, Diffie 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 •Whit Diffie Ralph , inv Merkle, ented và Îc the l™p notion bi of Marty public-k Hellman ey và Whit Diffie, ã cryptog phát raph minh y
ra .khái niªm m™t mã khóa công khai.
• 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”. 16 / 48 M™t mã khóa công khai (theo Diffie/Hellman)
• MÈi bên A có mÎt khóa công khai PKA ∫ ng˜Ìi khác có th∫
dùng nó ∫ mã hóa thông iªp g˚i cho A:
C = PKA(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).
• Dπ dàng tính ˜Òc c∞p khóa công khai/bí m™t.
• Công khai PKA không gây lÎ SKA! Không th∫ tìm (v∑ m∞t tính
toán) SKA t¯ PKA. 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. 17 / 48 Ch˙ k˛ iªn t˚ (theo Diffie/Hellman)
• fi t˜ng: K˛ vÓi SKA; ki∫m tra ch˙ k˛ vÓi PKA.
• ˜a ra mÎt ch˙ k˛ cho thông iªp M = SKA(M)
• ˜a ra PKA, 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: M ?= PKA( ).
• 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ó. . . 18 / 48
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) = Me mod n M = SK (C) = Cd mod n RSA
RSA (Ron Rivest, Adi Shamir, Len Adleman, 1977)
(Ron Rivest, Adi Shamir, Len Adleman, 1977)
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.
• PK = (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 = PK(M) = Me mod n; M = SK(C) = Cd mod n 19 / 48