Bài giảng Mật mã ứng dụng: Lịch sử mật mã - Đại học Bách khoa Hà Nội

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:58

Thêm vào BST

Báo xấu

10
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Mật mã ứng dụng: Lịch sử mật mã" trình bày các nội dung chính sau đây: Phát minh mật mã khóa công khai và RSA; Mật mã trong thương mại; Chính sách mật mã;... Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Mật mã ứng dụng: Lịch sử mật mã - Đại học Bách khoa Hà Nội

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 bí m™t là chu vi cıa que tròn. Khóa này chiathe gi˙a ng˜Ìi g˚i An unknown period (the circumference of s¥ scytale) is the secret key, và ng˜Ìi nh™n. shared by sender and receiver. 4 / 48
Pierre de Fermat (1601-1665) Pierre de Fermat (1601-1665) Euler (1707–1783) Leonhard Leonhard Euler (1707–1783) Fermat’s Little Theorem (1640): ‡nh l˛ Fermat nh‰ (1640): VÓi mÂi sËanguyên tË p, For any prime p and any a, 1 < p: p 1 a = 1 (mod p) p 1 Euler’s Theorem(mod p), a = 1 (1736): vÓi 1  a < p If gcd(a, n) = 1, then a gcd(a, n) = n) , ‡nh l˛ Euler (1736): N∏u(n) = 1 (mod 1, thì where (n) = # of x < n such that gcd(x, n) = 1. (n) a = 1 (mod n). 5 / 48
Friedrich Gauss (1777-1855) (1777-1855) Carl Friedrich Gauss Published problem of distinguishing prime numbersage 21 “The Disquisitiones Aritmeticae at from com- “The problem of distinguishing primeinto their prime posite numbers and of resolving the latter numbers from 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 factorsofis problem soto be onesoof the most require solution a known elegant and celebrated.” important and useful in arithmetic. . . . the dignity of the science itself seems to require solution of a 6 / 48
m Stanley JevonsStanley Jevons (1835–1882) William (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
A marvelous new communicationItechnology—radio Chi∏n tranh th∏ giÓi th˘ – Radio (Marconi, 1895)—enabled instantaneous • communication with remote ships and forces, but als MÎt công nghª truy∑n thông mÓi – radio (Marconi, 1895) – gave allgiao ti∏p t˘c thÌi messagesl˜Òng  xa, nh˜ng các cho phép transmitted vÓi t¶u và l¸c to the enemy. thông iªp cÙng g˚i cho c£ k¥ thù. • Uses˚ dˆng m™t mã t´ng lên. Viªc of cryptography soars. 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
an 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
Chi∏n tranh th∏ giÓi II World War II – Enigma, Purple, JN25, Naval Enigma Enigma, Purple, JN25, Naval Enigma • Cryptography performed by các máy M™t mã ˜Òc th¸c hiªn bi 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
Chi∏n tranh th∏ giÓi II World War II – Enigma, Purple, JN25, Naval Enigma Enigma, Purple, JN25, Naval Enigma • Cryptography performed by các máy M™t mã ˜Òc th¸c hiªn bi 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. • 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
Claude Shannon (1916–2001) 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). • 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 TheThe Codebreakers—The Story of Secret Writing. Codebreakers—The Story of Secret Writing. ây là A monumentall‡ch s˚ cıa cryptography. ã cË g≠ng cßm xußt mÎt b£o tàng history of m™t mã. NSA b£n nó.NSA attempted to suppress its publication. 12 / 48
ES – U.S. Data Encryption Standard (1976) DES U.S. Data Encryption Standard (1976) DES Designed at IBM; Horst Feistel supplied key elements of k∏ t§i IBM:such as ladder structure. NSA DES ˜Òc thi∏t design, Horst Feistel là ng˜Ìi thi∏t k∏ chính. NSA helped, in return for keeping key size (?) 56 bits.(?) ã giúp thi∏t k∏, và gi˙ kích th˜Óc khóa 56 bit. at 13 / 48
omputational Complexity Î ph˘c t§p tính toán Hartmanis Stearns Blum Cook Karp Theory of Computational Complexity started in 1965 • L˛ thuy∏t Î ph˘c t§p tính toán b≠t ¶u n´m by Blum, by Hartmanis and Stearns; expanded on 1965 bi Hartmanis và Stearns; phát tri∫n bi Blum, Cook, và Karp. Cook, and Karp. • Các khái niªm chính: quy d®n thÌi gian a th˘c; NP- ¶y ı. Key notions: polynomial-time reductions; 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
Phát minh m™t mã khóa công khai Invention of Public Key Cryptography Ralph Merkle, and independently Marty Hellman and • Whit Difﬁe, invented the bi Marty Hellman và Whit Diffie, ã Ralph Merkle, và Îc l™p notion of public-key cryptography.khái niªm m™t mã khóa công khai. phát minh ra • 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 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). • 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. 17 / 48
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: ? M = P KA( ). • 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
RSA (Ron Rivest, Adi Shamir, Len Adleman, 1977) RSA (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. • P K = (n, e) vÓi n = pq và gcd(e, (n)) = 1. • SK = d vÓi d e = 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 19 / 48