An tồn và An ninh thơng tin
Nguy n Linh Giang
B mơn Truy n thơng
và M ng máy tính


I.
II.
III.
IV.
V.
VI.

Nh p mơn An tồn thơng tin
Các ph ng pháp mã hóa đ i x ng
Các h m t khóa công khai
Xác th c thông đi p
Ch ký s và các giao th c xác th c
ánh d u n vào d li u


Ch ng II.
Các ph ng pháp mã hóa đ i x ng
1.

2.

3.
4.

S đ chung c a ph ng pháp mã hóa

đ i x ng
M t s ph ng pháp mã hóa đ i x ng
kinh đi n
Ph ng pháp DES
Qu n tr và phân ph i khóa


S đ mã hóa đ i x ng
Gi thi t
–

–

Thu t tốn mã hóa ph i đ m nh đ không th gi i
mã đ c thông đi p n u ch d a trên duy nh t n i
dung c a v n b n đ c mã hóa( ciphertext ).
S an toàn c a ph ng pháp mã hóa đ i x ng ch
ph thu c vào đ bí m t c a khóa mà khơng ph
thu c vào đ bí m t c a thu t tốn.


S mó húa i x ng
X*

Thám mÃ

Nguồn thông
điệp

X


Khối mà hóa
K

Y

K*

Khối giải mÃ

Kênh mật

Khóa
mật

Mụ hỡnh h th ng mó húa i x ng.

X

Nguồn thông
điệp


S đ chung c a ph
đ i x ng

ng pháp mã hóa

Ngu n thơng tin:
–


–

–

T p h p thơng đi p c a ngu n:
Các xâu ký t X = { X1, X2, ..., XM };
Thông đi p: xâu ký t đ dài m:
Xi = [ xi1, xi2, ..., xim ]
xik∈ A; A – b ng ký t ngu n; thông th ng A= {0, 1}
M i thông đi p Xi có m t xác su t xu t hi n P( X = Xi )


S đ chung c a ph
hóa đ i x ng

ng pháp mã

Khóa m t mã
–
–

T p h p khố K = { K1, K2, ... KL},
Khóa đ dài l: Ki=[ki1, ..., kil];
kij ∈ C, C - b ng ký t khóa; thơng th
= {0, 1}

ng C



S đ chung c a ph
hóa đ i x ng

ng pháp mã

Mã m t:
–
–
–

T p h p thông đi p mã m t Y = [ Y1, Y2, ..., YN ]
Thông đi p mã m t: Yj = [yj1, yj2, ..., yjn]
yjp ∈B, B – b ng ký t mã m t; thông th ng B = {0, 1}


S đ chung c a ph
hóa đ i x ng

ng pháp mã

Q trình mã hóa và gi i mã:
–

Q trình mã hóa:
Y = EK( X )

–

Q trình gi i mã:
Bên nh n gi i mã thông đi p b ng khóa đ


c phân ph i:

X = DK( Y ) = DK ( EK,R( X ) )


S đ chung c a ph
hóa đ i x ng

ng pháp mã

Phía t n cơng
–

V n đ đ t ra: đ i ph ng nh n đ c thông đi p
Y, nh ng khơng có đ c khóa K. D a vào thông
đi p Y, đ i ph ng ph i khôi ph c l i ho c K,
ho c X ho c c hai.


S đ chung c a ph
đ i x ng

ng pháp mã hóa

M t mã
–

Phân lo i các h th ng m t mã
D ng c a phép toán tham gia vào mã hóa v n b n t d ng

thơng th ng sang d ng đ c m t mã hóa;
S l ng khóa đ c dùng trong thu t tốn.
–
–

Ph
–
–

H th ng mã hóa đ i x ng.
H th ng mã hóa khơng đ i x ng.

ng th c mà v n b n ban đ u đ
Mã hóa kh i;
Mã hóa dịng.

c x lý:


S đ chung c a ph
hóa đ i x ng

ng pháp mã

Thám mã
–
–
–
–
–


Ch bi t v n b n đ c mã hoá;
Bi t m t s v n b n g c và m t mã t ng ng;
T n công b ng v n b n rõ đ c l a ch n tr c;
T n công b ng m t mã cho tr c;
T n công b ng b n rõ tùy ch n.


S đ chung c a ph
hóa đ i x ng
S đ mã hóa đ
–

ng pháp mã

c coi là an tồn vô đi u ki n

V n b n mã m t không ch a đ thông tin đ xác đinh
duy nh t v n b n g c t ng ng;

S đ mã m t đ
tốn

c coi là an tồn theo tính

Giá thành t n cơng v t q giá tr c a thông tin m t;
– Th i gian gi i m t v
t quá th i h n gi m t c a thông
tin.
–



S đ chung c a ph
hóa đ i x ng
–

ng pháp mã

Ví d : thu t tốn DES ( Data Encryption Standard ): Khố nh phân
•
dài 32 bit ⇒S l ng khoá: 232 ⇒ 35.8 phút x lý v i t c đ
1 phép mã hoá/μs ⇒ 2.15 ms v i t c đ 106 phép mã hố / μs.
•
dài 56 bit ⇒S l ng khoá: 256 ⇒ 1142 n m x lý v i t c
đ 1 phép mã hoá/μs ⇒ 10.01 gi v i t c đ 106 phép mã hố /
μs.
•
dài 128 bit ⇒S l ng khố: 2128 ⇒ 5.4 x 1024 n m x lý v i
t c đ 1 phép mã hoá/μs ⇒ 5.4 x 1018 n m v i t c đ 106 phép
mã hoá / μs.


M t s ph ng pháp mã hóa đ i
x ng kinh đi n
Các ph
–

ng pháp thay th

Mã Caesar

Các ký t ch cái đ c gán giá tr ( a = 1, b = 2, ... )
C = E( p ) = ( p + k ) mod ( 26 )
Trong đó k = 1 .. 25.
k là khố m t mã.
Quá trình gi i mã:
p = D( C ) = ( C – k ) mod ( 26 )


M t s ph ng pháp mã hóa đ i
x ng kinh đi n
Các v n đ c a mã Caesar:
–
–

–

Thu t toán mã hoá và gi i mã đã bi t tr c.
Thám mã:
Khơng gian khóa nh : ch có 25 khố;
Khi thám mã b ng ph ng pháp vét c n: ch c n th
v i 25 khóa;
Ngơn ng trong b n g c đã bi t tr c và d dàng nh n
bi t.


M t s ph ng pháp mã hóa đ i
x ng kinh đi n
–

Mã m t Hill

Thu t toán mã hoá
– M i ký t đ
c gán giá tr s : a = 0, b = 1, ..., z = 25
– L a ch n m ký t liên ti p c a v n b n g c;
– Thay th các ký t đã l a ch n b ng m ký t mã m t,
đ c tính b ng m ph ng trình tuy n tính.
– H ph
ng trình mã hóa:
C = KP ( mod 26 )
K- ma tr n khóa
Thu t tốn gi i mã
P = K-1C ( mod 26 )


M t s ph ng pháp mã hóa đ i
x ng kinh đi n
–

Ví d : v i m = 3, h các ph ng trình tuy n tính có d ng
sau:
C1 = ( k11p1 + k12p2 + k13p3 ) mod 26
C2 = ( k21p1 + k22p2 + k23p3 ) mod 26
C3 = ( k31p1 + k32p2 + k33p3 ) mod 26

⎛ C1 ⎞ ⎛ k11
⎜ ⎟ ⎜
⎜ C2 ⎟ = ⎜ k 21
⎜C ⎟ ⎜k
⎝ 3 ⎠ ⎝ 31


k12
k 22
k32
C = KP

k13 ⎞⎛ p1 ⎞
⎟⎜ ⎟
k 23 ⎟⎜ p2 ⎟
k33 ⎟⎠⎜⎝ p3 ⎟⎠


M t s ph ng pháp mã hóa đ i
x ng kinh đi n
Ma tr n K là ma tr n khố m t mã
– Ví d : v i ma tr n K b ng:

–

⎛ 17 17
⎜
K = ⎜ 21 18
⎜2
2
⎝

5⎞
⎟
21 ⎟
19 ⎟⎠


Xâu ký t : “paymoremoney” s đ c mã hoá thành
“LNSHDLEWMTRW”
“pay” ⇔ (15, 0, 24 ); K( 15, 0, 24 )T mod 26 = ( 11, 13, 18) ⇔ “LNS”


M t s ph ng pháp mã hóa đ i
x ng kinh đi n
–

Gi i mã thông đi p b ng ma tr n K-1.

9
⎛ 4
⎜
-1
K = ⎜ 15 17
⎜ 24 0
⎝

15 ⎞
⎟
6⎟
17 ⎟⎠

H mã Hill:
– Các phép toán th c hi n theo modulo 26
–

C = E K (P) = KP
⎧

⎨
−1
−1
=
=
=
P
D
(C)
K
C
K
KP = P
K
⎩


M t s ph ng pháp mã hóa đ i
x ng kinh đi n
M c đ an toàn c a h mã Hill
–

–

Mã m t Hill có tính m t cao khi phía t n cơng ch có v n b n
m t.
Thám mã h mã Hill: d dàng b b khóa n u bên t n cơng bi t
đ c v n b n rõ và v n b n m t t ng ng ( known plaintext
attack )
H mã m t Hill m x m;

Thám mã đã có m c p v n b n g c – v n b n m t, m i
v n b n có đ dài m;
T o các c p: Pj = ( p1j, p2j, ..., pmj ) và Cj = ( C1j, C2j, ..., Cmj )
sao cho Cj = KPj v i 1≤ j ≤ m đ i v i m t khoá K ch a
bi t.
Xác đ nh hai ma tr n m x m, X = ( pij ) và Y = ( Cij )


M t s ph ng pháp mã hóa đ i
x ng kinh đi n
Ta có Y = XK ⇒ K = X-1Y.
– Ví d : v n b n g c: “friday” đ
Hill 2 x 2 thành “PQCFKU”.
–

c mã hoá b ng mã m t

Ta có: K( 5 17 ) = ( 15 16 ); K( 8 3 ) = ( 2 5 ); K( 0 24 ) = ( 10
20 )
V i hai c p ban đ u ta có :

⎛15 16 ⎞ ⎛ 5 17 ⎞
⎜⎜
⎟⎟ = ⎜⎜
⎟⎟K ⇒
⎝ 2 5 ⎠ ⎝8 3 ⎠
−1

⎛ 5 17 ⎞ ⎛15 16 ⎞ ⎛ 9 1 ⎞⎛15 16 ⎞ ⎛ 7 19 ⎞
⎟⎟ ⎜⎜

⎟⎟ = ⎜⎜
⎟⎟⎜⎜
⎟⎟ = ⎜⎜
⎟⎟
K = ⎜⎜
⎝ 8 3 ⎠ ⎝ 2 5 ⎠ ⎝ 2 15 ⎠⎝ 2 5 ⎠ ⎝ 8 3 ⎠


M t s ph ng pháp mã hóa đ i
x ng kinh đi n
–

H th ng Vernam.
ch ng l i quá trình thám mã, c n l a ch n khố tho mãn:
–
–

Khố có đ dài b ng v n b n rõ.
Khóa đ c ch n sao cho khố và v n b n g c đ c l p th ng kê.

H mã m t Vernam:
Dùng cho mã nh phân
– Ci = pi ⊕ ki
– pi: bit th i c a v n b n g c;
– ki: bit th i c a khoá;
– Ci: bit th i c a v n b n đ
c mã hoá;
– ⊕: phép toán XOR.
–



M t s ph ng pháp mã hóa đ i
x ng kinh đi n
Gi i mã b ng phép toán ng c: pi = Ci ⊕ ki
T o khoá: t o vịng l p v i m t khố. Nh v y th c t , h
th ng làm vi c v i m t khóa r t dài nh ng l p l i.
H th ng Vernam có th b phá n u đ i ph ng bi t m t
v n b n mã có đ dài đ l n, s d ng m t s v n b n
g c đã bi t.
V i khoá đ c sinh ng u nhiên, có đ dài b ng đ dài
v n b n g c, không l p l i: s đ mã s d ng m t l n (
one-time pad ): khơng th phá khố.
u ra đ c l p th ng
kê v i v n b n g c.
V n đ n y sinh: đ m b o m t cho quá trình g i và nh n
khoá ng u nhiên.


Mã hóa kh i ( block cipher )
nh ngh a
–

–

Mã kh i là m t mã khóa đ i x ng th c hi n trên
nhóm bit có đ dài c đ nh. Nhóm bit này đ c g i
là m t kh i. Quá trình chuy n đ i khơng thay đ i.
Khi mã hóa, mã kh i có th th c hi n trên t ng kh i
đ dài 128 bit c a b n rõ t i đ u vào th nh t và cho
ra kh i 128 bit c a mã m t.

Quá trình bi n đ i đ
khóa m t

–

c ki m sốt b ng đ u vào th hai:

Quá trình gi i mã th c hi n t ng t : nh n t i đ u
vào th nh t kh i 128 bit c a m t mã, khóa m t và
t i đ u ra ta nh n đ c kh i 128 bit c a b n rõ