Ch ng 7ươ
M T MÃ ẬKHÓA Đ I X NGỐ Ứ
7.1 Lý thuy t c b n c a Shannonế ơ ả ủ
Nhi u ng i cho r ng k nguyên c a m t mã h c hi n đ i đ c b t đ u v iề ườ ằ ỷ ủ ậ ọ ệ ạ ượ ắ ầ ớ
Claude Shannon, ng i đ c coi là cha đ c a m t mã toán h c. Năm ườ ượ ẻ ủ ậ ọ 1949 ông đã công
b bài ốLý thuy t v truy n thông trong các h th ng b o m tế ề ề ệ ố ả ậ (Communication Theory
of Secrecy Systems) trên t p san ậBell System Technical Journal - T p san k thu t c aậ ỹ ậ ủ
h th ng Bell - và m t th i gian ng n sau đó, trong cu n ệ ố ộ ờ ắ ố Mathematical Theory of
Communication - Lý thuy t toán h c trong truy n thông - cùng v i tác gi Warrenế ọ ề ớ ả
Weaver. Nh ng công trình này, cùng v i nh ng công trình nghiên c u khác c a ông v ữ ớ ữ ứ ủ ề lý
thuy t v tin h c và truy n thôngế ề ọ ề (information and communication theory), đã thi t l pế ậ
m t n n t ng lý thuy t c b n cho m t mã h c và thám mã h c. V i nh h ng đó,ộ ề ả ế ơ ả ậ ọ ọ ớ ả ưở
m t mã h c h u nh b thâu tóm b i các c quan truy n thông m t c a chính ph ,ậ ọ ầ ư ị ở ơ ề ậ ủ ủ
ch ng h n nh ẳ ạ ư NSA, và bi n m t kh i t m hi u bi t c a công chúng. R t ít các côngế ấ ỏ ầ ể ế ủ ấ
trình đ c ti p t c công b , cho đ n th i kỳ gi a ượ ế ụ ố ế ờ ữ th p niên 1970ậ, khi m i s đ c thayọ ự ượ
đ i.ổ
Claude Shannon xem xét mô hình 7.1, đây ngu n b n tin sinh ra b n rõ X, ngu nở ồ ả ả ồ
khóa t o ra khóa K, khóa K đ c truy n qua kênh m t t n i truy n đ n n i nh n.ạ ượ ề ậ ừ ơ ề ế ơ ậ
Quá trình mã hóa bi n đ i b n rõ X nh khóa thành b n mã Y: ế ổ ả ờ ả
)(XFK
.
Quá trình gi i mã, bi n đ i b n mã nh n đ c Y thành b n rõ X cũng nh khóa K:ả ế ổ ả ậ ượ ả ờ
)(
1YFX K
−
=
.
T i ph m (hay thám mã) s tìm cách nh n đ c b n rõ và khóa trên c s b n mã.ộ ạ ẽ ậ ượ ả ơ ỡ ả
Claude Shannon xem xét các câu h i lý thuy t và th c hành m t. Đ nh n đ c lýỏ ế ự ậ ể ậ ượ
thuy t m t Shannon hình thành các câu h i sau:ế ậ ỏ
1. H th ng n đ nh m c đ nào, n u nh thám mã không gi i h n th i gianệ ố ổ ị ở ứ ộ ế ư ớ ạ ờ
và có t t c các thi t b c n thi t đ i v i vi c phân tích b n mã?ấ ả ế ị ầ ế ố ớ ệ ả
2. B n mã li u có m t nghi m duy nh t hay không?ả ệ ộ ệ ấ
3. V i l ng thông tin b n mã bao nhiêu mà thám mã c n thu nh t đ nghi mớ ượ ả ầ ặ ể ệ
tr nên duy nh t?ở ấ
Đ tr l i câu h i c a Shannon chúng ta đ a vào đ nh nghĩa “tuy t m t” v i s hể ả ờ ỏ ủ ư ị ệ ậ ớ ự ổ
tr các đi u ki n sau: B n mã thu đ c không đêm đ n cho thám mã b t kỳ thông tinợ ề ệ ả ượ ế ấ
nào. Theo đ nh lý Bayesị
)(/)()()( YPYPXPXP
XY
=
Hình 7.1. Mô hình truy n tin Shannonề
V i P(X) là xác su t xu t hi n b n tin X;ớ ấ ấ ệ ả
)(YPX
xác su t đi u ki n, xu t hi n b nấ ề ệ ấ ệ ả
mã Y v i đi u ki n b n tin X đã đ c ch n, có nghĩa là t ng xác su t c a t t c cácớ ề ệ ả ượ ọ ổ ấ ủ ấ ả
khóa, mà các khóa này chuy n b n tin X t ng ng v i b n mã Y; P(Y)-xác su t nh nể ả ươ ứ ớ ả ấ ậ
đ c b n mã Y; ượ ả
)(XP
Y
là xác su t nh n đ c b n rõ X v i đi u ki n nh t đ c b nấ ậ ượ ả ớ ề ệ ặ ượ ả
mã Y. Đ “tuy t m t” thì giá tr c a ể ệ ậ ị ủ
)(XP
Y
và
)(XP
c n ph i b ng nhau v i t t c giáầ ả ằ ớ ấ ả
tr c a X và Y.ị ủ
Đ ch ng l i ph ng pháp phân tích th ng kê b n mã (đây là m t cách thám mã)ể ố ạ ươ ố ả ộ
Shannon đ ra hai ph ng pháp: khuy t tán và pha tr n.ề ươ ế ộ
Đ nh nghĩa Entropy thông tinị. Entropy thông tin mô t m c đ ả ứ ộ h n lo nỗ ạ trong m tộ
tín hi uệ l y t m t s ki n ấ ừ ộ ự ệ ng u nhiênẫ. Nói cách khác, entropy cũng ch ra có bao nhiêuỉ
thông tin trong tín hi u, v i thông tin là các ph n không h n lo n ng u nhiên c a tínệ ớ ầ ỗ ạ ẫ ủ
hi u.ệ
Lý thuy t v thông tin s trình bày đ y đ h n v Entropy, đây chúng tôi ch đ aế ề ẽ ầ ủ ơ ề ở ỉ ư
ra cái c b n.ơ ả
Claude E. Shannon đã xây d ng đ nh nghĩa v entropy đ tho mãn các gi đ nh sau:ự ị ề ể ả ả ị
1. Entropy ph i ảt l thu nỷ ệ ậ liên t cụ v i các ớxác su tấ xu t hi n c a các ph nấ ệ ủ ầ
t ng u nhiên trong tín hi u. Thay đ i nh trong xác su t ph i d n đ n thayử ẫ ệ ổ ỏ ấ ả ẫ ế
đ i nh trong entropy. ổ ỏ
Ngu n ồ
khóa
Ngu n b n ồ ả
tin Mã hóa Gi i mãảNh n b n ậ ả
tin
T i ph mộ ạ
K
K’
X’
X
Y
X
K
2. N u các ph n t ng u nhiên đ u có xác su t xu t hi n b ng nhau, vi cế ầ ử ẫ ề ấ ấ ệ ằ ệ
tăng s l ng ph n t ng u nhiên ph i làm tăng entropy. ố ượ ầ ử ẫ ả
3. Có th t o các chu i tín hi u theo nhi u b c, và entropy t ng c ng ph iể ạ ỗ ệ ề ướ ổ ộ ả
b ng t ng có tr ng s c a entropy c a t ng b c. ằ ổ ọ ố ủ ủ ừ ướ
Shannon cũng ch ra r ng b t c đ nh nghĩa nào c a entropy, cho m t tín hi u có thỉ ằ ấ ứ ị ủ ộ ệ ể
nh n các giá tr r i r c, tho mãn các gi đ nh c a ông thì đ u có d ng:ậ ị ờ ạ ả ả ị ủ ề ạ
∑
=
−n
i
ipipK
1
)(log)(
V i K ớlà m t h ng s , ch ph thu c vào ộ ằ ố ỉ ụ ộ đ n v đoơ ị ; n là t ng s các giá tr có thổ ố ị ể
nh n c a tín hi uậ ủ ệ ; i là giá tr r i r c th ị ờ ạ ứ i; p(i) là xác su t xu t hi n c a giá tr ấ ấ ệ ủ ị i;
N u m t s ki n ế ộ ự ệ ng u nhiên r i r cẫ ờ ạ x, có th nh n các giá tr là 1..ể ậ ị n, thì entropy c aủ
nó là:
∑
=
−= n
i
ipipxH
1
2)(log)()(
,
v i ớp(i) là xác su t x y ra c a giá tr ấ ả ủ ị i.
Entropy thông tin trong tr ng h p ph n t tín hi u ng u nhiên r i r c còn đ c g iườ ợ ầ ử ệ ẫ ờ ạ ượ ọ
là entropy Shannon.
7.2 Đ nh nghĩa m t mã đ i x ngị ậ ố ứ
Đ nh nghĩaị. M t mã đ i x ng là h m t mà quá trình mã hóa và quá trình gi i mãậ ố ứ ệ ậ ả
dùng chung m t khóa m t, và vi c b o m t b n tin ph thu c vào quá trình l u khóaộ ậ ệ ả ậ ả ụ ộ ư
m t. S đ t ng quát c a h mã đ i x ng đ c miêu t hình 7.2.ậ ơ ồ ổ ủ ệ ố ứ ượ ả ở
B n tin ngu n ả ồ
(X)
Quá trình mã
hóa B n mã Y ả
truy n qua ề
kênh
Quá trình gi i ả
mã
(X=)
B n tin gi i ả ả
mã X
Khóa m t (K)ậkhóakhóa
T o ra khóa m tạ ậ
Hình 7.2. S đ m t mã đ i x ngơ ồ ậ ố ứ
đây b n tin ngu n X là thông tin c n mã đ b o m t, tr c khi chuy n đ n n iở ả ồ ầ ể ả ậ ướ ể ế ơ
nh n nó ph i đ c mã hóa b ng hàm mã hóa E, hàm mã hóa E là t ng h p các phép bi nậ ả ượ ằ ổ ợ ế
đ i v i s tham gia c a khóa m t K; qua bi n đ i c a hàm E chúng ta thu đ c b n mãổ ớ ự ủ ậ ế ổ ủ ượ ả
Y; b n mã Y truy n qua kênh thông tin đ n n i ng i c n nh n, n i nh n v i s giúpả ề ế ơ ườ ầ ậ ở ơ ậ ớ ự
đ c a quá trình gi i mã và khóa m t K, s gi i b n mã Y thành b n tin X ban đ u. ở ủ ả ậ ẽ ả ả ả ầ Chú
ý, n u nh khóa K không đúng, ho c b n mã Y b bi n đ i trong quá trình truy n thì quáế ư ặ ả ị ế ổ ề
trình gi i mã không th thu đ c b n tin ban đ u X.ả ể ượ ả ầ
Nh đã nói, m t mã đ i x ng đ c chia ra làm hai ph n, m t mã kh i và m t mãư ậ ố ứ ượ ầ ậ ố ậ
dòng. Chúng ta xem đ nh nghĩa v chúng.ị ề
Đ nh nghĩaị m t mã kh iậ ố . Mã kh i là t h p l nh toán h c (hoán v , thay th ,…)ố ổ ợ ệ ọ ị ế
bi n đ i dãy N bit ế ổ
N
NFxxxx )2(),...,,( 21 ∈=
thành m t dãy N bit ộ
v i s tham gia c a khóa m t k t không gian khóa K, có th vi t d i d ngớ ự ủ ậ ừ ể ế ướ ạ
),( kxFy =
,
đây F là hàm mã hóa hay gi i mã.ở ả
Đ nh nghĩa mã dòng. ịLà m t h mã đ i x ng, trong đó t ng ký t c a b n rõ đ cộ ệ ố ứ ừ ự ủ ả ượ
bi n đ i thành ký t c a b n mã ph thu c không ch vào khóa s d ng mà còn vào vế ổ ự ủ ả ụ ộ ỉ ử ụ ị
trí c a nó trong b n rõ. Mã kh i thì chia b n rõ ra các kh i b ng nhau r i th c hi n mã,ủ ả ố ả ố ằ ồ ự ệ
nên s có m t s kh i gi ng nhau mã cùng m t khóa, mã dòng thì không nh v y.ẽ ộ ố ố ố ộ ở ư ậ
7.3 Các l nh dùng đ xây d ng thu t toán m t mã đ i x ngệ ể ự ậ ậ ố ứ
H u nh t tầ ư ấ c các h m t đ i x ng đ m b o b o m t thông tin th ng đ c xâyả ệ ậ ố ứ ả ả ả ậ ườ ượ
d ng trên c s các l nh c s sau:ự ơ ở ệ ơ ở
7.3.1 L nh hoán đ iệ ổ
Đ nh nghĩaị. Đây là ph ng pháp bi n đ i m t mã đ n gi n, là m t phép hoán đ iươ ế ổ ậ ơ ả ộ ổ
các v trí c a các kí t trong b n rõ theo m t quy lu t nào đó. Chúng ta có th bi u di nị ủ ự ả ộ ậ ể ể ễ
chúng b ng toán h c nh sau:ằ ọ ư
Hoán đ i ổ
π
c a t p h u h n ủ ậ ữ ạ
Ω
, v i ớ
Ω
g m n ph n t , là m t đ n ánh t t pồ ầ ử ộ ơ ừ ậ
Ω
vào
t pậ
Ω
,
{ }
n,...,2,1=Ω
, l nh hoán đ i ệ ổ
π
có d ng sau:ạ
=
n
n
δ
α
δδ
αα
π
...
...
21
21
,
đây hang đ u tiên là v trí ký t c a b n rõ, hang th 2 là các v trí mà ký t ban đ uở ầ ị ự ủ ả ứ ị ự ầ
c n hoán đ i t ng ng,ầ ổ ươ ứ
{ }
jijiii n
ααδδαδ
≠≠∈ ,(,...,2,1,
khi
ji ≠
), t c là v trí th ứ ị ứ
1
α
đ iổ
cho v trí th ị ứ
1
δ
, v trí th ị ứ
2
α
đ i cho v trí th ổ ị ứ
2
δ
t ng t nh th . Giá tr n g i làươ ự ư ế ị ọ
chi u dài hoán đ i.ề ổ
Ví d :ụ
=41
43
32
21
π
.
T p h p t t c các l nh hoán đ i ậ ợ ấ ả ệ ổ
π
ký hi u là ệ
n
π
, và rõ ràng r ng ằ
!n
n=
π
.
Có nhi u cách bi u di n l nh hoán v . Ví d nh t ví d trên ta có các cách bi uề ể ễ ệ ị ụ ư ừ ụ ể
di n sau:ễ
)4)(1,3,2()4)(3,2,1( ==
π
.
Chúng ta th y l nh hoán đ i nh m t hàm, tham s c a nó là s nguyên, hàm này cóấ ệ ổ ư ộ ố ủ ố
th ký hi u ể ệ
)( i
απ
,v i ớ
{ }
ni
ii
,...,2,1,)( ∈∀=
δαπ
.
Tiêu chu n xây d ng nên l nh hoán đ iẩ ự ệ ổ : Chúng ta ph i xây d ng l nh hoán đ iả ự ệ ổ
sao cho đ t đ c đ phát tán t t, nh m tăng hi u ng thác lũ.ạ ượ ộ ố ằ ệ ứ
7.3.2 L nh thay thệ ế.
Đ nh nghĩaị.Trong m t mã, l nh thay th có th hi u là m t qúa trình thay m t sậ ệ ế ể ể ộ ộ ố
ph n t này b ng m t s ph n t khác, hay nói cách khác là thay th m t ký t hayầ ử ằ ộ ố ầ ử ế ộ ự
m t nhóm ký t c a b n tin b ng m t ký t hay m t nhóm ký t khác. Theo toán h c thìộ ự ủ ả ằ ộ ự ộ ự ọ
chúng ta có th đ nh nghĩa nh sau:ể ị ư
L nh thay th S là m t ánh x s:ệ ế ộ ạ
'
ΩΩ
, v i ớ
',ΩΩ
là t p h u h n và v i ậ ữ ạ ớ
Ω∈∀
ω
,
t n t i duy nh t m t ph n t ồ ạ ấ ộ ầ ử
)(':''
ωωω
S=Ω∈
.
Đ i v i ố ớ
{ }
n
ωωω
,...,, 21
=Ω
l nh hoán đ i có d ng:ệ ổ ạ
=''
2
'
1
21
...
...
n
n
S
ω
ω
ωω
ωω
,
V i ớ
',...,, ''
2
'
1Ω∈
n
ωωω
. Các giá tr ị
''
2
'
1,...,, n
ωωω
không b t bu c là khác nhau.ắ ộ
Ví d l nh thay th 2 bit này thành 2 bít khác:ụ ệ ế
=21
43
43
21
S
Tuy nhiên m t s phép thay th có th bi u di n d ng khác ộ ố ế ể ể ễ ở ạ nh đư ồ thị, dùng hàm
số…vv.