Mật mã ứng dụng_Thầy Trần Vĩnh Đức| Bài giảng Mật mã ứng dụng| Trường Đại học Bách Khoa Hà Nội

Mật mã ứng dụng_Thầy Trần Vĩnh Đức| Bài giảng Mật mã ứng dụng| Trường Đại học Bách Khoa Hà Nội. Tài liệu gồm 834 trang giúp bạn đọc ôn tập và đạt kết quả cao trong kỳ thi sắp tới. Mời bạn đọc đón xem.

35 18 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Mật mã ứng dụng

Trường: Đại học Bách Khoa Hà Nội

Thông tin:

834 trang 2 tháng trước

Tác giả:

Profile Trịnh Thảo Anh
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
An unknown period (the circumference of the scytale)
is the secret key, shared by sender and receiver.
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
và ng˜Ìi nh™n.
4 / 48
Pierre de Fermat (1601-1665)
Leonhard Euler (1707–1783)
Pierre de Fermat (1601-1665)
Leonhard Euler (1707–1783)
Fermat’s Little Theorem (1640):
For any prime p and any a,1 a < p:
a
p1
= 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.
‡nh l˛ Fermat nh‰ (1640): VÓi mÂi sË nguyên tË p,
a
p1
= 1 (mod p), vÓi 1 a < p
‡nh l˛ Euler (1736): N∏u gcd(a, n)=1, thì
a
(n)
= 1 (mod n).
5 / 48
Carl Friedrich Gauss (1777-1855)
Car l Fr iedrich Gauss (1777-1855)
Published Disquisitiones Aritmeticae at age 21
“The problem of distinguishing prime numbers from
composite numbers and of resolving the latter into
their prime factors is known to be one of the most
important and useful in arithmetic. . . . the dignity of
the science itself seems to require solution of a
problem so elegant and so celebrated.”
“The problem of distinguishing prime numbers from com-
posite numbers and of resolving the latter into their prime
factors is known to be one of the most important and use-
ful in arithmetic.... the dignity of the science itself seems to
require solution of a problem so elegant and so celebrated.”
6 / 48
William Stanley Jevons (1835–1882)
William Stanley Jevons (1835–1882)
Published The Principles of Science (1874)
Gave world’s first factoring challenge:
“What two numbers multiplied together will
produce 8616460799 ? I think it unlikely that
anyone but myself will ever know.”
Factored by Derr ick Lehmer in 1903. (89681 96079)
ã ˜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 bi Derrick Lehmer vào n´m 1903. (89681
⇤
96079)
7 / 48
Chi∏n tranh th∏ giÓi th˘ I – Radio
•
MÎt công nghª truy∑n thông mÓi – radio (Marconi, 1895) –
cho phép giao ti∏p t˘c thÌi vÓi tu và l¸c l˜Òng xa, nh˜ng các
thông iªp cÙng g˚i cho c£ k¥ thù.
•
Viªc s˚ dˆng m™t mã t´ng lên.
World War I – Radio
A marvelous new communication technology—radio
(Marconi, 1895)—enabled instantaneous
communication with remote ships and forces, but also
gave all transmitted messages to the enemy.
Use of cryptography soars.
Decipherment of
Zimmermann Telegram by
British made American
involvement in World War I
inevitable.
B£n gi£i mã cıa Zimmermann
Telegram bi Anh trong chi∏n
tranh th∏ giÓi I
8 / 48
Alan Turing (1912–1954)
Alan Turing (1912–1954)
Developed foundations of theory of computability
(1936).
Phát tri∫n cÏ s cıa l˛ thuy∏t tính toán (1936).
9 / 48
Chi∏n tranh th∏ giÓi II
Enigma, Purple, JN25, Naval Enigma
World War II – Enigma, Purple, JN25, Naval Enigma
Cryptography performed by
(typically, rotor) machines.
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).
•
M™t mã ˜Òc th¸c hiªn bi các máy
rotor.
•
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
Chi∏n tranh th∏ giÓi II
Enigma, Purple, JN25, Naval Enigma
World War II – Enigma, Purple, JN25, Naval Enigma
Cryptography performed by
(typically, rotor) machines.
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).
•
M™t mã ˜Òc th¸c hiªn bi các máy
rotor.
•
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, classified).
Information-theoretic in character—proves
unbreakability of one-time pad. (Published 1949).
•
“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)
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
DES
U.S. Data Encryption Standard (1976)
DES – U.S. Data Encryption Standard (1976)
DES Designed at IBM; Horst Feistel supplied key
elements of design, such as ladder structure. NSA
helped, in return for keeping key size at 56 bits.(?)
DES ˜Òc thi∏t k∏ t§i IBM: Horst Feistel là ng˜Ìi thi∏t k∏ chính. NSA
ã giúp thi∏t k∏, và gi˙ kích th˜Óc khóa 56 bit. (?)
13 / 48
Î ph˘c t§p tính toán
Computational Complexity
Blum
Cook Stearns
Karp
Hartmanis
Theory of Computational Complexity started in 1965
by Hartmanis and Stearns; expanded on by Blum,
Cook, and Karp.
Key notions: polynomial-time reductions;
NP-completeness.
•
L˛ thuy∏t Î ph˘c t§p tính toán b≠t ¶u n´m 1965 bi
Hartmanis và Stearns; phát tri∫n bi Blum, Cook, và Karp.
•
Các khái niªm chính: quy d®n thÌi gian a th˘c; NP-¶y ı.
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 Diffie, invented the notion of public-key
cryptography.
In November 1976, Diffie and Hellman published New
Directions in Cryptography, proclaiming
“We are at the brink of a revolution in
cryptography.”
•
Ralph Merkle, và Îc l™p bi Marty Hellman và Whit Diffie, ã
phát minh 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 PK
A
∫ ng˜Ìi khác có th∫
dùng nó ∫ mã hóa thông iªp g˚i cho A:
C = PK
A
(M).
•
MÈi bên A cÙng có mÎt khóa bí m™t SK
A
dùng ∫ gi£i mã b£n
mã C nh™n ˜Òc:
M = SK
A
(C).
•
Dπ dàng tính ˜Òc c∞p khóa công khai/bí m™t.
•
Công khai PK
A
không gây lÎ SK
A
! Không th∫ tìm (v∑ m∞t tính
toán) SK
A
t¯ PK
A
. 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 SK
A
; ki∫m tra ch˙ k˛ vÓi PK
A
.
•
˜a ra mÎt ch˙ k˛ cho thông iªp M
= SK
A
(M)
•
˜a ra PK
A
, 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
?
= PK
A
().
•
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)
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)=C
d
mod n
Tính an toàn (mÎt phn) 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)=M
e
mod n; M = SK(C)=C
d
mod n
19 / 48
| 1/834
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

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