Lý thuyết mật mã và An toàn thông tin
Từ khi con người có nhu cầu trao đổi thông tin, thư từ cho nhau thì nhu cầu giữ bí mật và bảo vệ tính riêng tư những thông tin, thư từ trao đổi đó cũng nẩy sinh.mật mã học là một lĩnh vực liên quan với các kỹ thuật ngôn ngữ và toán học để đảm bảo an toàn thông tin, cụ thể là trong thông tin liên lạc. Về phương diện lịch sử, mật mã học gắn...
§¹i häc quèc gia hµ néi
Khoa c«ng nghÖ
Phan §×nh DiÖu
Lý thuyÕt mËt m·
&
an toµn th«ng tin
NXB ®¹i häc quèc gia hµ néi - 2002
1
Lý thuyÕt mËt m·
&
An toµn th«ng tin
2
Lý thuyÕt mËt m·
&
An toµn th«ng tin
Phan §×nh DiÖu
§¹i häc Quèc gia Hµ Néi
Khoa C«ng nghÖ- §HQG Hµ néi
3
Néi dung
Lêi më ®Çu.................................................................4
Ch−¬ng 1
Giíi thiÖu chung vÒ mËt m·......8
1.1. S¬ lùoc lÞch sö vÒ khoa mËt m·.................................. ........ 8
1.2. HÖ thèng mËt m·. M· theo khèi vµ m· theo dßng ........ 12
1.3. MËt m· khãa ®èi xøng vµ mËt m· cã khãa c«ng khai.... 15
1.4. C¸c bµi to¸n an toµn th«ng tin ........................................... 16
1.5. Th¸m m· vµ tÝnh an toµn cña c¸c hÖ mËt m·................... 18
Ch−¬ng 2.
C¬ së to¸n häc cña lý thuyÕt mËt m· ................20
2.1.Sè häc c¸c sè nguyªn.ThuËt to¸n Euclide.......................... 20
2.2. X¸c suÊt vµ thuËt to¸n x¸c suÊt......... ............................... 31
2.3. §é phøc t¹p tÝnh to¸n......................................................... 36
2.4.Sè nguyªn tè. Ph©n tÝch thµnh thõa sè.L«garit rêi r¹c.... 42
1
Ch−¬ng 3
C¸c hÖ mËt m· kho¸ ®èi xøng ...... 55
3.1. C¸c hÖ mËt m· cæ ®iÓn........................................................ 55
3.2. Th¸m m· ®èi víi c¸c hÖ mËt m· cæ ®iÓn ......................... 63
3.3. MËt m· theo dßng vµ c¸c d·y sè gi¶ ngÉu nhiªn ...........72
3.4. HÖ mËt m· chuÈn DES ........................................ 80
Ch−¬ng 4
C¸c hÖ mËt m· kho¸ c«ng khai ...........92
4.1. Giíi thiÖu më ®Çu.................................................................92
4.1. HÖ mËt m· kho¸ c«ng khai RSA ........................................97
4.2. HÖ mËt m· kho¸ c«ng khai Rabin.................................... 101
4.3. HÖ mËt m· kho¸ c«ng khai ElGamal................................103
4.4. C¸c hÖ mËt m· dùa trªn c¸c bµi to¸n NP-®Çy ®ñ............107
4.5. C¸c hÖ mËt m· x¸c suÊt kho¸ c«ng khai...........................111
Ch−¬ng 5
Bµi to¸n x¸c nhËn vµ Ch÷ ký ®iÖn tö......115
5.1. Bµi to¸n x¸c nhËn vµ s¬ ®å ch÷ ký................................ 115
5.2. S¬ ®å ch÷ ký ElGamal vµ chuÈn ch÷ ký ®iÖ tö.......... 118
5.3. Hµm b¨m vµ ch÷ ký......................................................... 122
5.4. Mét sè s¬ ®å ch÷ ký kh¸c............................................... 127
5.5.Ch÷ ký kh«ng phñ ®Þnh ®−îc&kh«ng chèi bá ®−îc 131
2
Ch−¬ng 6
C¸c s¬ ®å x−ng danh vµ x¸c nhËn danh tÝnh 136
6.1. VÊn ®Ò x−ng danh..............................................................136
6.2. S¬ ®å x−ng danh Schnorr..................................................137
6.3. S¬ ®å x−ng danh Okamoto................................................140
6.4. S¬ ®å x−ng danh Guillou-Quisquater..............................142
6.5. Giao thøc Feige-Fiat-Shamir...............................................145
6.6. PhÐp chøng minh kh«ng lé tri thøc..................................147
Ch−¬ng 7
VÊn ®Ò ph©n phèi kho¸ vµ tho¶ thuËn kho¸ 152
7.1. Qu¶n trÞ kho¸ trong c¸c m¹ng truyÒn tin.........................152
7.2. Mét sè hÖ ph©n phèi kho¸................................................153
7.3. Trao ®æi kho¸ vµ tho¶ thuËn kho¸....................................157
Chó dÉn vÒ tµi liÖu tham kh¶o..................................................163
3
Lêi më ®Çu
Tõ khi con ng−êi cã nhu cÇu trao ®æi th«ng tin, th− tõ cho
nhau th× nhu cÇu gi÷ bÝ mËt vµ b¶o vÖ tÝnh riªng t− cña nh÷ng th«ng
tin, th− tõ ®−îc trao ®æi ®ã còng nÈy sinh. H×nh thøc th«ng tin ®−îc
trao ®æi phæ biÕn vµ sím nhÊt lµ d−íi d¹ng c¸c v¨n b¶n, ®Ó gi÷ bÝ
mËt cña th«ng tin ng−êi ta ®· sím nghÜ ®Õn c¸ch che dÊu néi dung
c¸c v¨n b¶n b»ng c¸ch biÕn d¹ng c¸c v¨n b¶n ®ã ®Ó ng−êi ngoµi
kh«ng ®äc hiÓu ®−îc, ®ång thêi cã c¸ch kh«i phôc l¹i nguyªn d¹ng
ban ®Çu ®Ó ng−êi trong cuéc vÉn ®äc hiÓu ®−îc; theo c¸ch gäi ngµy
nay th× d¹ng biÕn ®æi cña v¨n b¶n ®−îc gäi lµ mËt m· cña v¨n b¶n,
c¸ch lËp mËt m· cho mét v¨n b¶n ®−îc gäi lµ phÐp lËp mËt m·, cßn
c¸ch kh«i phôc l¹i nguyªn d¹ng ban ®Çu cña v¨n b¶n tõ b¶n mËt m·
®−îc gäi lµ phÐp gi¶i m·. PhÐp lËp mËt m· vµ phÐp gi¶i m· ®−îc
thùc hiÖn nhê mét ch×a kho¸ riªng nµo ®ã mµ chØ nh÷ng ng−êi trong
cuéc ®−îc biÕt, sau ®©y ta sÏ gäi lµ kho¸ mËt m·. Ng−êi ngoµi cuéc
kh«ng ®−îc biÕt kho¸ mËt m·, nªn dï cã "¨n c¾p" ®−îc b¶n mËt m·
trªn ®−êng truyÒn tin, vÒ nguyªn t¾c còng kh«ng thÓ gi¶i m· ®Ó
hiÓu ®−îc néi dung cña v¨n b¶n truyÒn ®i.
HiÓn nhiªn, tiªu chuÈn cña mét b¶n mËt m· lµ t¹o ®−îc tÝnh
bÝ mËt cho v¨n b¶n; v× vËy kh¸i niÖm bÝ mËt lµ kh¸i niÖm cèt lâi nhÊt
®èi víi mét lý thuyÕt vÒ mËt m·. Cã thÓ cã mét ®Þnh nghÜa khoa häc
cho kh¸i niÖm bÝ mËt hay kh«ng? §· cã nhiÒu c¸ch tiÕp cËn ®Ó t×m
hiÓu néi dung cña kh¸i niÖm bÝ mËt, nh−ng mét ®Þnh nghÜa khoa
häc, hay h¬n n÷a, mét ®Þnh nghÜa to¸n häc cho kh¸i niÖm ®ã th×
ch−a cã. Mét c¸ch tiÕp cËn kh¸ phæ biÕn lµ g¾n kh¸i niÖm bÝ mËt víi
kh¸i niÖm "ngÉu nhiªn", nÕu mét v¨n b¶n râ cã mét néi dung x¸c
®Þnh th× ®iÒu ta mong muèn lµ b¶n mËt m· cña nã ph¶i lµ mét b¶n
gåm c¸c ký tù ®−îc s¾p xÕp hçn ®én, cã vÎ nh− ngÉu nhiªn khiÕn
4
ng−êi ngoµi nh×n vµo kh«ng thÓ x¸c ®Þnh ®−îc néi dung cña v¨n
b¶n gèc. Tuy nhiªn, nÕu "bÝ mËt" lµ kh¸i niÖm ch−a ®Þnh nghÜa
®−îc, th× kh¸i niÖm "ngÉu nhiªn", hay cô thÓ h¬n, kh¸i niÖm "d·y bit
ngÉu nhiªn", còng khã ®Þnh nghÜa nh− vËy, ta ch−a qui ®Þnh ®−îc
mét tiªu chuÈn to¸n häc ®Ó x¸c ®Þnh mét d·y bit cã lµ "ngÉu nhiªn"
hay kh«ng, mµ chØ míi t×m hiÓu ®−îc mét sè thuéc tÝnh gÇn víi
"ngÉu nhiªn", dïng lµm c¨n cø ®Ó t¹m x¸c ®Þnh mét d·y bit cã lµ
"gi¶ ngÉu nhiªn" theo nghÜa cã c¸c thuéc tÝnh ®ã hay kh«ng mµ th«i.
Tõ mÊy thËp niªn gÇn ®©y, b−íc vµo kû nguyªn m¸y tÝnh,
còng nh− ®èi víi nhiÒu lÜnh vùc kh¸c, lÜnh vùc mËt m· còng ®· cã
nh÷ng chuyÓn biÕn to lín tõ giai ®o¹n mËt m· truyÒn thèng sang
giai ®o¹n mËt m· m¸y tÝnh; m¸y tÝnh ®iÖn tö ®−îc sö dông ngµy
cµng phæ biÕn trong viÖc lËp mËt m·, gi¶i mËt m·, vµ nh÷ng chuyÓn
biÕn ®ã ®· kÝch thÝch viÖc nghiªn cøu c¸c gi¶i ph¸p mËt m·, biÕn
viÖc nghiªn cøu mËt m· thµnh mét khoa häc cã ®èi t−îng ngµy cµng
réng lín vµ ®−îc sö dông cã hiÖu qu¶ trong nhiÒu ph¹m vi ho¹t
®éng cña cuéc sèng. V× c¸c nghiÖp vô chñ yÕu cña mËt m· ®−îc
thùc hiÖn b»ng m¸y tÝnh, nªn c¸c kh¸i niÖm bÝ mËt, ngÉu nhiªn còng
dÇn ®−îc "m¸y tÝnh ho¸", vµ víi sù ra ®êi cña Lý thuyÕt vÒ ®é phøc
t¹p tÝnh to¸n vµo gi÷a nh÷ng n¨m 1960, c¸c kh¸i niÖm ®ã t×m ®−îc
mét néi dung chung cã thÓ ®−îc nghiªn cøu mét c¸ch to¸n häc lµ
tÝnh phøc t¹p. B©y giê ta cã thÓ nãi, mét b¶n mËt m· ®èi víi anh lµ
bÝ mËt, nÕu tõ b¶n mËt m· ®ã ®Ó t×m ra b¶n râ anh ph¶i thùc hiÖn
mét tiÕn tr×nh tÝnh to¸n mµ ®é phøc t¹p cña nã v−ît qu¸ mäi n¨ng
lùc tÝnh to¸n (kÓ c¶ mäi m¸y tÝnh) cña anh; mét d·y bit cã thÓ xem lµ
ngÉu nhiªn , nÕu dùa vµo mét ®o¹n bit ®· biÕt ®Ó t×m mét bit tiÕp
theo cña d·y anh còng ph¶i thùc hiÖn mét tiÕn tr×nh tÝnh to¸n cã ®é
phøc t¹p cùc lín t−¬ng tù nh− nãi trªn.
ViÖc chuyÓn sang giai ®o¹n mËt m· m¸y tÝnh tr−íc hÕt ®· cã
t¸c dông ph¸t triÓn vµ hiÖn ®¹i ho¸ nhiÒu hÖ thèng mËt m· theo kiÓu
truyÒn thèng, lµm cho c¸c hÖ thèng ®ã cã c¸c cÊu tróc tinh tÕ h¬n,
®ßi hái lËp mËt m· vµ gi¶i m· phøc t¹p h¬n, do ®ã hiÖu qu¶ gi÷ bÝ
mËt cña c¸c gi¶i ph¸p mËt m· ®−îc n©ng cao h¬n tr−íc rÊt nhiÒu.
Tuy nhiªn, mét b−íc chuyÓn cã tÝnh chÊt c¸ch m¹ng mµ mËt m·
m¸y tÝnh mang l¹i lµ viÖc ph¸t minh ra c¸c hÖ mËt m· cã kho¸ c«ng
khai, b¾t ®Çu tõ cuèi nh÷ng n¨m 1970, c¬ së lý thuyÕt cña c¸c ph¸t
5
minh ®ã lµ sù tån t¹i cña c¸c hµm mét phÝa (one-way function), tøc
lµ nh÷ng hµm sè sè häc y = f (x) mµ viÖc tÝnh theo phÝa thuËn tõ x
tÝnh y lµ t−¬ng ®èi dÔ, nh−ng viÖc tÝnh theo phÝa ng−îc tõ y t×m l¹i
x (x = f--1(y)) lµ cùc kú phøc t¹p. C¸c hÖ mËt m· cã kho¸ c«ng khai ®·
lµm thay ®æi vÒ b¶n chÊt viÖc tæ chøc c¸c hÖ truyÒn th«ng b¶o mËt,
lµm dÔ dµng cho viÖc b¶o mËt trªn c¸c hÖ truyÒn th«ng c«ng céng,
vµ do tÝnh chÊt ®Æc biÖt ®ã chóng ®· lµ c¬ së cho viÖc ph¸t triÓn
nhiÒu giao thøc an toµn th«ng tin kh¸c khi sö dông m¹ng truyÒn
th«ng c«ng céng, ch¼ng h¹n c¸c lo¹i giao thøc vÒ x¸c nhËn nguån tin
vµ ®Þnh danh ng−êi göi, ch÷ ký ®iÖn tö, c¸c giao thøc x¸c nhËn
kh«ng ®Ó lé th«ng tin g× kh¸c ngoµi viÖc x¸c nhËn, c¸c giao thøc trao
®æi kho¸ trong tæ chøc truyÒn tin b¶o mËt vµ trong x¸c nhËn, v.v...,
vµ gÇn ®©y trong viÖc ph¸t triÓn nhiÒu giao thøc ®Æc thï kh¸c trong
c¸c giao dÞch ng©n hµng vµ th−¬ng m¹i ®iÖn tö, ph¸t hµnh vµ mua
b¸n b»ng tiÒn ®iÖn tö,... Còng cÇn nãi thªm lµ lý thuyÕt mËt m· hiÖn
®¹i, tøc lµ mËt m· m¸y tÝnh trªn c¬ së lý thuyÕt vÒ ®é phøc t¹p tÝnh
to¸n tuy cã nhiÒu øng dông ®Æc s¾c vµ cã triÓn väng to lín, nh−ng
còng míi ®ang trong giai ®o¹n ph¸t triÓn b−íc ®Çu, cßn ph¶i kh¾c
phôc nhiÒu khã kh¨n vµ t×m kiÕm thªm nhiÒu c¬ së v÷ng ch¾c míi
®Ó tiÕp tôc hoµn thiÖn vµ ph¸t triÓn. Ch¼ng h¹n, nh− trªn ®· nãi,
mét c¬ së quan träng cña lý thuyÕt mËt m· hiÖn ®¹i lµ sù tån t¹i cña
c¸c hµm mét phÝa, nh−ng ngay cã thËt tån t¹i c¸c hµm mét phÝa hay
kh«ng còng cßn lµ mét bµi to¸n ch−a cã c©u tr¶ lêi! Ta chØ míi ®ang
cã mét sè hµm mét phÝa theo sù hiÓu biÕt cña con ng−êi hiÖn nay,
nh−ng ch−a chøng minh ®−îc cã mét hµm cô thÓ nµo ®ã ch¾c ch¾n
lµ hµm mét phÝa! Tuy nhiªn, nÕu theo quan ®iÓm khoa häc hiÖn ®¹i,
ta kh«ng xem môc ®Ých khoa häc lµ ®i t×m nh÷ng ch©n lý ch¾c ch¾n
tuyÖt ®èi, mµ lµ ®i t×m nh÷ng c¸ch gi¶i quyÕt vÊn ®Ò (problem
solving) gÆp trong thùc tiÔn, th× ta vÉn cã thÓ tin vµo nh÷ng gi¶i
ph¸p "t−¬ng ®èi" rÊt cã hiÖu qu¶ mµ lý thuyÕt hiÖn ®¹i vÒ mËt m·
®ang cèng hiÕn cho con ng−êi hiÖn nay.
TËp gi¸o tr×nh Lý thuyÕt mËt m· vµ an toµn th«ng tin nµy
®−îc so¹n ®Ó phôc vô cho viÖc häc tËp cña sinh viªn c¸c líp theo
ch−¬ng tr×nh ®¹i häc hoÆc cao häc thuéc ngµnh C«ng nghÖ th«ng tin
cña §¹i häc Quèc gia Hµ néi. Trong kho¶ng m−¬i n¨m gÇn ®©y, trªn
thÕ giíi ®· xuÊt hiÖn nhiÒu s¸ch vµ tµi liÖu cã tÝnh chÊt gi¸o khoa
6
hoÆc tham kh¶o vÒ lý thuyÕt mËt m· hiÖn ®¹i vµ øng dông. Ng−êi
viÕt tËp gi¸o tr×nh nµy chØ cã cè g¾ng lùa chän vµ s¾p xÕp mét sè néi
dung mµ m×nh nghÜ lµ cÇn thiÕt vµ thÝch hîp nhÊt ®Ó trong mét
ph¹m vi h¹n chÕ vÒ thêi gian (vµ kh«ng gian) tr×nh bµy vµ giíi thiÖu
®−îc cho ng−êi häc mét c¸ch t−¬ng ®èi hÖ thèng nh÷ng kiÕn thøc
c¬ b¶n vÒ lý thuyÕt mËt m· hiÖn ®¹i, bao gåm c¶ mét sè kiÕn thøc
to¸n häc cÇn thiÕt. Gi¸o tr×nh nµy ®· ®−îc gi¶ng d¹y cho sinh viªn
c¸c kho¸ cao häc vÒ C«ng nghÖ th«ng tin thuéc §¹i häc B¸ch khoa
Hµ néi vµ khoa C«ng nghÖ §¹i häc Quèc gia Hµ néi tõ n¨m 1997
®Õn 2004. Ng−êi viÕt ch©n thµnh c¶m ¬n c¸c b¹n ®ång nghiÖp vµ
ng−êi ®äc chØ cho nh÷ng chç thiÕu sãt ®Ó cã thÓ kÞp thêi söa ch÷a
cho nh÷ng lÇn in sau, nÕu cã.
Th¸ng 12 n¨m 2002
Phan §×nh DiÖu
7
CH¦¥NG I
Giíi thiÖu chung vÒ mËt m·
1.1. S¬ l−îc lÞch sö vÒ mËt m·.
Nh− ®· giíi thiÖu trong Lêi më ®Çu, nhu cÇu sö dông mËt
m· ®· xuÊt hiÖn tõ rÊt sím, khi con ng−êi biÕt trao ®æi vµ truyÒn
®−a th«ng tin cho nhau, ®Æc biÖt khi c¸c th«ng tin ®ã ®· ®−îc thÓ
hiÖn d−íi h×nh thøc ng«n ng÷, th− tõ. LÞch sö cho ta biÕt, c¸c h×nh
thøc mËt m· s¬ khai ®· ®−îc t×m thÊy tõ kho¶ng bèn ngh×n n¨m
tr−íc trong nÒn v¨n mÞnh Ai cËp cæ ®¹i. Tr¶i qua hµng ngh×n n¨m
lÞch sö, mËt m· ®· ®−îc sö dông réng r·i trªn kh¾p thÕ giíi tõ §«ng
sang T©y ®Ó gi÷ bÝ mËt cho viÖc giao l−u th«ng tin trong nhiÒu lÜnh
vùc ho¹t ®éng gi÷a con ng−êi vµ c¸c quèc gia, ®Æc biÖt trong c¸c
lÜnh vùc qu©n sù, chÝnh trÞ, ngo¹i giao. MËt m· tr−íc hÕt lµ mét lo¹i
ho¹t ®éng thùc tiÔn, néi dung chÝnh cña nã lµ ®Ó gi÷ bÝ mËt th«ng
tin (ch¼ng h¹n d−íi d¹ng mét v¨n b¶n) tõ mét ng−êi göi A ®Õn mét
ng−êi nhËn B, A ph¶i t¹o cho v¨n b¶n ®ã mét b¶n m· mËt t−¬ng
øng, vµ thay v× göi v¨n b¶n râ th× A chØ göi cho B b¶n m· mËt, B
nhËn ®−îc b¶n m· mËt vµ sÏ cã c¸ch tõ ®ã kh«i phôc l¹i v¨n b¶n râ
®Ó hiÓu ®−îc th«ng tin mµ A muèn göi cho m×nh. V× b¶n göi ®i
th−êng ®−îc chuyÓn qua c¸c con ®−êng c«ng khai nªn ng−êi ngoµi
cã thÓ "lÊy trém" ®−îc, nh−ng do ®ã lµ b¶n mËt m· nªn kh«ng ®äc
hiÓu ®−îc, cßn A cã thÓ t¹o ra b¶n m· mËt vµ B cã thÓ gi¶i b¶n m·
mËt thµnh b¶n râ ®Ó hiÓu ®−îc lµ do gi÷a hai ng−êi ®· cã mét tháa
thuËn vÒ mét ch×a khãa chung, chØ víi ch×a khãa chung nµy th× A
míi t¹o ®−îc b¶n m· mËt tõ b¶n râ, vµ B míi tõ b¶n m· mËt kh«i
phôc l¹i ®−îc b¶n râ. Sau nµy ta sÏ gäi ®¬n gi¶n ch×a khãa chung ®ã
lµ khãa mËt m·. TÊt nhiªn ®Ó thùc hiÖn ®−îc mét phÐp mËt m·, ta
8
cßn cÇn cã mét thuËt to¸n biÕn b¶n râ, cïng víi khãa mËt m·, thµnh
b¶n m· mËt, vµ mét thuËt to¸n ng−îc l¹i, biÕn b¶n m· mËt, cïng víi
khãa mËt m·, thµnh b¶n râ. C¸c thuËt to¸n ®ã ®−îc gäi t−¬ng øng lµ
thuËt to¸n lËp mËt m· vµ thuËt to¸n gi¶i mËt m·. C¸c thuËt to¸n nµy
th−êng kh«ng nhÊt thiÕt ph¶i gi÷ bÝ mËt, mµ c¸i cÇn ®−îc gi÷ tuyÖt
mËt lu«n lu«n lµ khãa mËt m·. Trong thùc tiÔn, ®· cã ho¹t ®éng b¶o
mËt th× còng cã ho¹t ®éng ng−îc l¹i lµ kh¸m ph¸ bÝ mËt tõ c¸c b¶n
m· mËt "lÊy trém" ®−îc, ta th−êng gäi ho¹t ®éng nµy lµ m· th¸m,
ho¹t ®éng nµy quan träng kh«ng kÐm g× ho¹t ®éng b¶o mËt! V× c¸c
thuËt to¸n lËp mËt m· vµ gi¶i mËt m· kh«ng nhÊt thiÕt lµ bÝ mËt, nªn
m· th¸m th−êng ®−îc tËp trung vµo viÖc t×m khãa mËt m·, do ®ã
còng cã ng−êi gäi c«ng viÖc ®ã lµ ph¸ khãa.
Suèt mÊy ngh×n n¨m lÞch sö, c¸c th«ng b¸o, th− tõ ®−îc
truyÒn ®−a vµ trao ®æi víi nhau th−êng lµ c¸c v¨n b¶n, tøc lµ cã
d¹ng c¸c d·y ký tù trong mét ng«n ng÷ nµo ®ã; v× vËy, c¸c thuËt
to¸n lËp mËt m· th−êng còng ®¬n gi¶n lµ thuËt to¸n x¸o trén, thay
®æi c¸c ký tù ®−îc x¸c ®Þnh bëi c¸c phÐp chuyÓn dÞch, thay thÕ hay
ho¸n vÞ c¸c ký tù trong b¶ng ký tù cña ng«n ng÷ t−¬ng øng; khãa
mËt m· lµ th«ng tin dïng ®Ó thùc hiÖn phÐp lËp mËt m· vµ gi¶i mËt
m· cô thÓ, thÝ dô nh− sè vÞ trÝ ®èi víi phÐp chuyÓn dÞch, b¶ng x¸c
®Þnh c¸c cÆp ký tù t−¬ng øng ®èi víi phÐp thay thÕ hay ho¸n vÞ,...
MËt m· ch−a ph¶i lµ mét khoa häc, do ®ã ch−a cã nhiÒu kiÕn thøc
s¸ch vë ®Ó l¹i, tuy nhiªn ho¹t ®éng b¶o mËt vµ th¸m m· trong lÞch
sö c¸c cuéc ®Êu tranh chÝnh trÞ, ngo¹i giao vµ qu©n sù th× hÕt søc
phong phó, vµ mËt m· ®· cã nhiÒu t¸c ®éng rÊt quan träng ®−a ®Õn
nh÷ng kÕt qu¶ l¾m khi cã ý nghÜa quyÕt ®Þnh trong c¸c cuéc ®Êu
tranh ®ã. Do trong mét thêi gian dµi, b¶n th©n ho¹t ®éng mËt m·
còng ®−îc xem lµ mét bÝ mËt, nªn c¸c tµi liÖu kü thuËt vÒ mËt m·
®−îc phæ biÕn ®Õn nay th−êng chØ ghi l¹i c¸c kiÕn thøc kinh nghiÖm,
thØnh tho¶ng míi cã mét vµi "ph¸t minh" nh− c¸c hÖ mËt m·
VigenÌre vµo thÕ kû 16 hoÆc hÖ mËt m· Hill ra ®êi n¨m 1929 lµ c¸c
hÖ m· thùc hiÖn phÐp chuyÓn dÞch (®èi víi m· VigenÌre) hay phÐp
thay thÕ (m· Hill) ®ång thêi trªn mét nhãm ký tù chø kh«ng ph¶i
trªn tõng ký tù riªng rÏ. VÊn ®Ò th¸m m·, ng−îc l¹i, khi thµnh c«ng
th−êng ®−a ®Õn nh÷ng cèng hiÕn næi tréi vµ Ên t−îng trong nh÷ng
9
t×nh huèng gay cÊn cña c¸c cuéc ®Êu tranh, vµ còng th−êng ®ßi hái
nhiÒu tµi n¨ng ph¸t hiÖn víi nh÷ng kinh nghiÖm vµ suy luËn tinh tÕ
h¬n, nªn ®Ó l¹i nhiÒu chuyÖn hÊp dÉn h¬n. NhiÒu c©u chuyÖn kú thó
cña lÞch sö th¸m m· ®· ®−îc thuËt l¹i trong quyÓn s¸ch næi tiÕng
cña David Kahn The Codebreakers . The Story of Secret Writing ,
xuÊt b¶n n¨m 1967 (s¸ch ®· ®−îc dÞch ra nhiÒu thø tiÕng, cã b¶n
dÞch tiÕng ViÖt Nh÷ng ng−êi m· th¸m, 3 tËp, xuÊt b¶n t¹i Hµ néi
n¨m 1987).
B−íc sang thÕ kû 20, víi nh÷ng tiÕn bé liªn tôc cña kü thuËt
tÝnh to¸n vµ truyÒn th«ng, ngµnh mËt m· còng ®· cã nh÷ng tiÕn bé
to lín. Vµo nh÷ng thËp niªn ®Çu cña thÕ kû, sù ph¸t triÓn cña c¸c kü
thuËt biÓu diÔn, truyÒn vµ xö lý tÝn hiÖu ®· cã t¸c ®éng gióp cho c¸c
ho¹t ®éng lËp vµ gi¶i mËt m· tõ thñ c«ng chuyÓn sang c¬ giíi hãa
råi ®iÖn tö hãa. C¸c v¨n b¶n, c¸c b¶n mËt m· tr−íc ®©y ®−îc viÕt
b»ng ng«n ng÷ th«ng th−êng nay ®−îc chuyÓn b»ng kü thuËt sè
thµnh c¸c d·y tÝn hiÖu nhÞ ph©n, tøc c¸c d·y bit, vµ c¸c phÐp biÕn ®æi
trªn c¸c d·y ký tù ®−îc chuyÓn thµnh c¸c phÐp biÕn ®æi trªn c¸c d·y
bit, hay c¸c d·y sè, viÖc thùc hiÖn c¸c phÐp lËp m·, gi¶i m· trë
thµnh viÖc thùc hiÖn c¸c hµm sè sè häc. To¸n häc vµ kü thuËt tÝnh
to¸n b¾t ®Çu trë thµnh c«ng cô cho viÖc ph¸t triÓn khoa häc vÒ mËt
m·. Kh¸i niÖm trung t©m cña khoa häc mËt m· lµ kh¸i niÖm bÝ mËt.
§ã lµ mét kh¸i niÖm phæ biÕn trong ®êi sèng, nh−ng liÖu cã thÓ cho
nã mét néi dung cã thÓ ®Þnh nghÜa ®−îc mét c¸ch to¸n häc kh«ng?
Nh− ®· l−îc qua trong Lêi më ®Çu, kh¸i niÖm bÝ mËt tho¹t ®Çu
®−îc g¾n víi kh¸i niÖm ngÉu nhiªn, råi vÒ sau trong nh÷ng thËp
niªn gÇn ®©y, víi kh¸i niÖm phøc t¹p, cô thÓ h¬n lµ kh¸i niÖm ®é
phøc t¹p tÝnh to¸n. ViÖc sö dông lý thuyÕt x¸c suÊt vµ ngÉu nhiªn
lµm c¬ së ®Ó nghiªn cøu mËt m· ®· gióp C.Shannon ®−a ra kh¸i
niÖm bÝ mËt hoµn toµn cña mét hÖ mËt m· tõ n¨m 1948, khëi ®Çu
cho mét lý thuyÕt x¸c suÊt vÒ mËt m·. Trong thùc tiÔn lµm mËt m·,
c¸cd·y bit ngÉu nhiªn ®−îc dïng ®Ó trén víi b¶n râ (d−íi d¹ng mét
d·y bit x¸c ®Þnh) thµnh ra b¶n mËt m·. Lµm thÕ nµo ®Ó t¹o ra c¸c
d·y bit ngÉu nhiªn? Cã thÓ t¹o ra b»ng ph−¬ng ph¸p vËt lý ®¬n gi¶n
nh− sau: ta tung ®ång xu lªn, nÕu ®ång xu r¬i xuèng ë mÆt sÊp th× ta
ghi bit 0, ë mÆt ngöa th× ta ghi bit 1; tung n lÇn ta sÏ ®−îc mét d·y n
10
bit, d·y bit thu ®−îc nh− vËy cã thÓ ®−îc xem lµ d·y bit ngÉu nhiªn.
Nh−ng t¹o ra theo c¸ch nh− vËy th× khã cã thÓ sö dông mét c¸ch
phæ biÕn, v× kh«ng thÓ t×m ra qui luËt ®Ó theo ®ã mµ sinh ra d·y bit
ngÉu nhiªn ®−îc. ë ®©y ta gÆp mét khã kh¨n cã tÝnh b¶n chÊt: nÕu
cã qui luËt th× ®· kh«ng cßn lµ ngÉu nhiªn n÷a råi! Nh− vËy, nÕu ta
muèn t×m theo qui luËt, th× kh«ng bao giê cã thÓ t×m ra c¸c d·y bit
ngÉu nhiªn, mµ cïng l¾m còng chØ cã thÓ ®−îc c¸c d·y bit gÇn ngÉu
nhiªn, hay gi¶ ngÉu nhiªn, mµ th«i. Tõ nhiÒu chôc n¨m nay, ng−êi
ta ®· nghiªn cøu ®Ò xuÊt nhiÒu thuËt to¸n to¸n häc ®Ó sinh ra c¸c
d·y bit gi¶ ngÉu nhiªn, vµ còng ®· ®−a ra nhiÒu thuéc tÝnh ®Ó ®¸nh
gi¸ mét d·y bit gi¶ ngÉu nhiªn cã ®¸ng ®−îc xem lµ "gÇn" ngÉu
nhiªn hay kh«ng. Mét vµi thuéc tÝnh chñ yÕu mµ ng−êi ta ®· ®Ò xuÊt
lµ: cho mét d·y bit X = (x1,x2,.....,xn,...); d·y ®ã ®−îc xem lµ gi¶ ngÉu
nhiªn "tèt" nÕu x¸c suÊt xuÊt hiÖn bit 0 hay bit 1 trong toµn d·y ®ã
còng nh− trong mäi d·y con bÊt kú cña nã ®Òu b»ng 1/2; hoÆc mét
tiªu chuÈn kh¸c: nÕu mäi ch−¬ng tr×nh sinh ra ®−îc ®o¹n ®Çu n bit
cña d·y ®Òu ph¶i cã ®é phøc t¹p (hay ®é dµi) cì n ký tù ! VÒ sau
nµy, khi lý thuyÕt vÒ ®é phøc t¹p tÝnh to¸n ®· ®−îc ph¸t triÓn th×
tiªu chuÈn vÒ ngÉu nhiªn còng ®−îc qui vÒ tiªu chuÈn phøc t¹p tÝnh
to¸n, cô thÓ mét d·y bit X ®−îc xem lµ gi¶ ngÉu nhiªn "tèt" nÕu mäi
thuËt to¸n t×m ®−îc bit thø n (xn) khi biÕt c¸c bit tr−íc ®ã (x1,,...,xn-1)
víi x¸c suÊt ®óng > 1/2 ®Òu ph¶i cã ®é phøc t¹p tÝnh to¸n thuéc líp
NP-khã!
Lý thuyÕt vÒ ®é phøc t¹p tÝnh to¸n ra ®êi tõ gi÷a nh÷ng n¨m
1960 ®· cho ta mét c¸ch thÝch hîp ®Ó qui yªu cÇu bÝ mËt hoÆc ngÉu
nhiªn vÒ mét yªu cÇu cã thÓ ®Þnh nghÜa ®−îc lµ yªu cÇu vÒ ®é phøc
t¹p tÝnh to¸n. B©y giê ta cã thÓ nãi: mét gi¶i ph¸p mËt m· lµ b¶o
®¶m bÝ mËt, nÕu mäi thuËt to¸n th¸m m·, nÕu cã, ®Òu ph¶i ®−îc
thùc hiÖn víi ®é phøc t¹p tÝnh to¸n cùc lín! Cùc lín lµ bao nhiªu?
Lµ v−ît qu¸ giíi h¹n kh¶ n¨ng tÝnh to¸n (bao gåm c¶ m¸y tÝnh) mµ
ng−êi th¸m m· cã thÓ cã. VÒ lý thuyÕt, cã thÓ xem ®ã lµ nh÷ng ®é
phøc t¹p tÝnh to¸n víi tèc ®é t¨ng v−ît qu¸ hµm mò, hoÆc thuéc lo¹i
NP-khã. Tuy nhiªn, lý thuyÕt ®é phøc t¹p tÝnh to¸n kh«ng chØ cèng
hiÕn cho ta mét kh¸i niÖm ®Ó gióp chÝnh x¸c hãa tiªu chuÈn bÝ mËt
cña c¸c gi¶i ph¸p mËt m·, mµ cßn më ra mét giai ®o¹n míi cña
ngµnh mËt m·, biÕn ngµnh mËt m· thµnh mét khoa häc cã néi dung
11
lý luËn phong phó vµ cã nh÷ng øng dông thùc tiÔn quan träng
trong nhiÒu lÜnh vùc cña ®êi sèng hiÖn ®¹i. B−íc ngoÆt cã tÝnh c¸ch
m¹ng trong lÞch sö khoa häc mËt m· hiÖn ®¹i xÈy ra vµo n¨m 1976
khi hai t¸c gi¶ Diffie vµ Hellman ®−a ra kh¸i niÖm vÒ mËt m· khãa
c«ng khai vµ mét ph−¬ng ph¸p trao ®æi c«ng khai ®Ó t¹o ra mét
khãa bÝ mËt chung mµ tÝnh an toµn ®−îc b¶o ®¶m bëi ®é khã cña
mét bµi to¸n to¸n häc cô thÓ (lµ bµi to¸n tÝnh "l«garit rêi r¹c"). Hai
n¨m sau, n¨m 1978, Rivest, Shamir vµ Adleman t×m ra mét hÖ mËt
m· khãa c«ng khai vµ mét s¬ ®å ch÷ ký ®iÖn tö hoµn toµn cã thÓ
øng dông trong thùc tiÔn, tÝnh b¶o mËt vµ an toµn cña chóng ®−îc
b¶o ®¶m b»ng ®é phøc t¹p cña mét bµi to¸n sè häc næi tiÕng lµ bµi
to¸n ph©n tÝch sè nguyªn thµnh c¸c thõa sè nguyªn tè. Sau ph¸t
minh ra hÖ mËt m· ®ã (mµ nay ta th−êng gäi lµ hÖ RSA), viÖc nghiªn
cøu ®Ó ph¸t minh ra c¸c hÖ mËt m· khãa c«ng khai kh¸c, vµ øng
dông c¸c hÖ mËt m· khãa c«ng khai vµo c¸c bµi to¸n kh¸c nhau cña
an toµn th«ng tin ®· ®−îc tiÕn hµnh réng r·i, lý thuyÕt mËt m· vµ an
toµn th«ng tin trë thµnh mét lÜnh vùc khoa häc ®−îc ph¸t triÓn
nhanh trong vµi ba thËp niªn cuèi cña thÕ kû 20, l«i cuèn theo sù
ph¸t triÓn cña mét sè bé m«n cña to¸n häc vµ tin häc. Trong c¸c
ch−¬ng vÒ sau cña tËp gi¸o tr×nh nµy ta sÏ lÇn l−ît lµm quen víi mét
sè thµnh qu¶ chñ yÕu cña lý thuyÕt ®ã.
1.2. C¸c hÖ thèng mËt m·.
1.2.1. S¬ ®å hÖ thèng mËt m·.
MËt m· ®−îc sö dông ®Ó b¶o vÖ tÝnh bÝ mËt cña th«ng tin khi
th«ng tin ®−îc truyÒn trªn c¸c kªnh truyÒn th«ng c«ng céng nh− c¸c
kªnh b−u chÝnh, ®iÖn tho¹i, m¹ng truyÒn th«ng m¸y tÝnh, m¹ng
Internet, v.v... Gi¶ thö mét ng−êi göi A muèn göi ®Õn mét ng−êi
nhËn B mét v¨n b¶n (ch¼ng h¹n, mét bøc th−) p, ®Ó b¶o mËt A lËp
cho p mét b¶n mËt m· c, vµ thay cho viÖc göi p, A göi cho B b¶n mËt
m· c, B nhËn ®−îc c vµ "gݶi m·" c ®Ó l¹i ®−îc v¨n b¶n p nh− A
®Þnh göi. §Ó A biÕn p thµnh c vµ B biÕn ng−îc l¹i c thµnh p , A vµ B
ph¶i tháa thuËn tr−íc víi nhau c¸c thuËt to¸n lËp m· vµ gi¶i m·, vµ
®Æc biÖt mét khãa mËt m· chung K ®Ó thùc hiÖn c¸c thuËt to¸n ®ã.
Ng−êi ngoµi, kh«ng biÕt c¸c th«ng tin ®ã (®Æc biÖt, kh«ng biÕt khãa
12
K), cho dï cã lÊy trém ®−îc c trªn kªnh truyÒn th«ng c«ng céng,
còng kh«ng thÓ t×m ®−îc v¨n b¶n p mµ hai ng−êi A, B muèn göi cho
nhau. Sau ®©y ta sÏ cho mét ®Þnh nghÜa h×nh thøc vÒ s¬ ®å mËt m·
vµ c¸ch thøc thùc hiÖn ®Ó lËp mËt m· vµ gi¶i mËt m·.
§Þnh nghÜa 1.2.1. Mét s¬ ®å hÖ thèng mËt m· lµ mét bé n¨m
S = (P , C , K , E , D ) (1)
tháa m·n c¸c ®iÒu kiÖn sau ®©y:
P lµ mét tËp h÷u h¹n c¸c ký tù b¶n râ,
C lµ mét tËp h÷u h¹n c¸c ký tù b¶n m·,
K lµ mét tËp h÷u h¹n c¸c khãa,
E lµ mét ¸nh x¹ tõ KxP vµo C , , ®−îc gäi lµ phÐp lËp mËt m·;
vµ D lµ mét ¸nh x¹ tõ KxC vµo P , ®−îc gäi lµ phÐp gi¶i m·. Víi
mçi K∈K , ta ®Þnh nghÜa eK : P →C , dK :C →P lµ hai hµm cho bëi :
⎠x εP : eK(x) = E (K,x) ; ⎠yε C : dK(y) = D (K,y).
eK vµ dK ®−îc gäi lÇn l−ît lµ hµm lËp m· vµ hµm gi¶i m· øng víi
khãa mËt m· K. C¸c hµm ®ã ph¶i tháa m·n hÖ thøc:
⎠x ε P : dK(eK(x)) = x.
VÒ sau, ®Ó thuËn tiÖn ta sÏ gäi mét danh s¸ch (1) tho¶ m·n c¸c
tÝnh chÊt kÓ trªn lµ mét s¬ ®å hÖ thèng mËt m· , cßn khi ®· chän cè
®Þnh mét kho¸ K, th× danh s¸ch (P , C , eK , dK) lµ mét hÖ mËt m·
thuéc s¬ ®å ®ã.
Trong ®Þnh nghÜa nµy, phÐp lËp mËt m· (gi¶i m·) ®−îc ®Þnh
nghÜa cho tõng ký tù b¶n râ (b¶n m·). Trong thùc tÕ, b¶n râ cña mét
th«ng b¸o th−êng lµ mét d·y ký tù b¶n râ, tøc lµ phÇn tö cña tËp P *,
vµ b¶n mËt m· còng lµ mét d·y c¸c ký tù b¶n m·, tøc lµ phÇn tö cña
tËp C *, viÖc më réng c¸c hµm eK vµ dK lªn c¸c miÒn t−¬ng øng P *
vµ C * ®Ó ®−îc c¸c thuËt to¸n lËp mËt m· vµ gi¶i m· dïng trong thùc
tÕ sÏ ®−îc tr×nh bµy trong tiÕt sau. C¸c tËp ký tù b¶n râ vµ b¶n m·
th−êng dïng lµ c¸c tËp ký tù cña ng«n ng÷ th«ng th−êng nh− tiÕng
ViÖt, tiÕng Anh (ta ký hiÖu tËp ký tù tiÕng Anh lµ A tøc A =
{a,b,c,...,x,y,z } gåm 26 ký tù; tËp ký tù nhÞ ph©n B chØ gåm hai ký tù
13
0 vµ 1; tËp c¸c sè nguyªn kh«ng ©m bÐ h¬n mét sè n nµo ®ã (ta ký
hiÖu tËp nµy lµ Zn tøc Zn = {0,1,2,...., n- 1}). Chó ý r»ng cã thÓ xem B
= Z2. §Ó thuËn tiÖn, ta còng th−êng ®ång nhÊt tËp ký tù tiÕng Anh A
víi tËp gåm 26 sè nguyªn kh«ng ©m ®Çu tiªn Z26 = {0,1,2,...., 24,25}
víi sù t−¬ng øng sau ®©y:
a b c d e f g h i j k l m n o p q r s t u v w x y z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25.
§«i khi ta còng dïng víi t− c¸ch tËp ký tù b¶n râ hay b¶n m· lµ c¸c
tËp tÝch cña c¸c tËp nãi trªn, ®Æc biÖt lµ c¸c tËp Am , B m , Znm .
1.2.2. M· theo khèi vµ m· theo dßng.
Nh− nãi ë trªn, b¶n râ cña th«ng b¸o mµ ta muèn göi ®i
th−êng lµ mét d·y ký tù, trong khi theo ®Þnh nghÜa cña s¬ ®å mËt
m·, hµm lËp mËt m· vµ hµm gi¶i m· ®−îc ®Þnh nghÜa cho tõng ký
tù. Tõ c¸c ®Þnh nghÜa cña hµm lËp mËt m· vµ hµm gi¶i m·, ta më
réng thµnh thuËt to¸n lËp m· (vµ gi¶i m·) x¸c ®Þnh cho mäi b¶n râ
(b¶n m·) nh− sau:
Theo c¸ch m· theo khèi (block cipher), tr−íc hÕt ta x¸c ®Þnh
mét ®é dµi khèi (ch¼ng h¹n lµ k), tiÕp ®ã më réng kh«ng gian khãa
tõ K thµnh Kk , vµ víi mçi K =K1...Kk ε Kk, ta më réng eK vµ dK
thµnh c¸c thuËt to¸n eK : P k→ C k
vµ dK : C k→P k nh− sau: víi mäi
x1...xk ∈P k
vµ y1...yk ∈C k ta cã
eK ( x1 ....xk ) = eK1 ( x1 )....eK k ( xk ); d K ( y1 .... yk ) = d K1 ( y1 )....d K k ( yk ) .
Gi¶ thö b¶n râ mµ ta muèn lËp mËt m· cho nã lµ d·y ký tù X∈ P*
.Ta c¾t X thµnh tõng khèi, mçi khèi cã ®é dµi k, khèi cuèi cïng cã
thÓ cã ®é dµi dK(Y) = dK(Y1)....dK(Ym) = X1....Xm = X.
C¸ch m· theo khèi ®¬n gi¶n vµ th«ng dông nhÊt lµ khi ta chän ®é
dµi khèi k =1. Khi ®ã víi mäi b¶n râ X = x1...xm ∈ P * ta cã
eK(X) = eK(x1....xm ) = eK(x1)....eK(xm).
Víi c¸ch m· theo dßng (stream cipher), tr−íc hÕt ta ph¶i x¸c
®Þnh mét dßng khãa, tøc lµ mét phÇn tö K = K1...Km ∈ K * , víi dßng
khãa ®ã ta x¸c ®Þnh víi mäi b¶n râ X = x1...xm ∈ P * b¶n m· t−¬ng
øng lµ
eK(X) = eK ( x1...xm ) = eK ( x1 )...eK ( xm ).
1 m
Gi¶i m· Y = eK(X) ta ®−îc
dK(Y) = d K (eK ( x1 ))....d K (eK ( xm )) = x1....xm = X .
1 1 m m
§Ó sö dông c¸ch lËp mËt m· theo dßng, ngoµi s¬ ®å mËt m·
gèc ta cßn ph¶i cã mét dßng khãa, tøc lµ mét d·y cã ®é dµi tïy ý c¸c
ký tù khãa. §ã th−êng lµ c¸c d·y c¸c ký tù khãa ®−îc sinh ra bëi
mét bé "t¹o d·y ngÉu nhiªn" nµo ®ã xuÊt ph¸t tõ mét "mÇm" chän
tr−íc. Trong c¸c øng dông thùc tÕ, ng−êi ta th−êng dïng c¸ch m·
theo dßng cã s¬ ®å mËt m· gèc lµ s¬ ®å Vernam víi
P = C = K = {0,1}
vµ c¸c hµm lËp m· vµ gi¶i m· ®−îc x¸c ®Þnh bëi
eK(x) = x + K mod 2, dK(y) = y +K mod 2 (K = 0 hoÆc 1);
dßng khãa lµ d·y bit ngÉu nhiªn ®−îc sinh ra bëi mét bé t¹o d·y bit
ngÉu nhiªn nµo ®ã.
1.3. MËt m· khãa ®èi xøng vµ mËt m· cã khãa c«ng khai.
Theo ®Þnh nghÜa 1.2.1 vÒ s¬ ®å mËt m·, cø mçi lÇn truyÒn tin
b¶o mËt, c¶ ng−êi göi A vµ ng−êi nhËn B ph¶i cïng tháa thuËn
tr−íc víi nhau mét khãa chung K, sau ®ã ng−êi göi dïng eK ®Ó lËp
mËt m· cho th«ng b¸o göi ®i, vµ ng−êi nhËn dïng dK ®Ó gi¶i m·
b¶n mËt m· nhËn ®−îc. Ng−êi göi vµ ng−êi nhËn cïng cã mét khãa
15
chung K, ®−îc gi÷ nh− bÝ mËt riªng cña hai ng−êi, dïng c¶ cho lËp
mËt m· vµ gi¶i m·, ta gäi nh÷ng hÖ mËt m· víi c¸ch sö dông ®ã lµ
mËt m· khãa ®èi xøng, ®«i khi còng gäi lµ mËt m· truyÒn thèng, v×
®ã lµ c¸ch ®· ®−îc sö dông tõ hµng ngµn n¨m nay.
Tuy nhiªn, vÒ nguyªn t¾c hai hµm lËp m· vµ gi¶i m· lµ kh¸c
nhau, kh«ng nhÊt thiÕt ph¶i phô thuéc cïng mét khãa. NÕu ta x¸c
®Þnh mçi khãa K gåm cã hai phÇn K = (K' , K'' ), K' dµnh cho viÖc lËp
mËt m· (vµ ta cã hµm lËp m· eK' ), K'' dµnh cho viÖc gi¶i m· (vµ cã
hµm gi¶i m· dK'' ), c¸c hµm lËp m· vµ gi¶i m· tháa m·n hÖ thøc
dK'' (eK' (x)) = x víi mäi x ∈P ,
th× ta ®−îc mét hÖ mËt m· khãa phi ®èi xøng. Nh− vËy, trong mét
hÖ mËt m· khãa phi ®èi xøng, c¸c khãa lËp m· vµ gi¶i m· (K' vµ K''
) lµ kh¸c nhau, nh−ng tÊt nhiªn cã quan hÖ víi nhau. Trong hai khãa
®ã, khãa cÇn ph¶i gi÷ bÝ mËt lµ khãa gi¶i m· K'' , cßn khãa lËp m· K'
cã thÓ ®−îc c«ng bè c«ng khai; tuy nhiªn ®iÒu ®ã chØ cã ý nghÜa thùc
tiÔn khi viÖc biÕt K' t×m K'' lµ cùc kú khã kh¨n ®Õn møc hÇu nh−
kh«ng thÓ thùc hiÖn ®−îc. Mét hÖ mËt m· khãa phi ®èi xøng cã tÝnh
chÊt nãi trªn, trong ®ã khãa lËp mËt m· K' cña mçi ng−êi tham gia
®Òu ®−îc c«ng bè c«ng khai, ®−îc gäi lµ hÖ mËt m· khãa c«ng khai.
Kh¸i niÖm mËt m· khãa c«ng khai míi ®−îc ra ®êi vµo gi÷a nh÷ng
n¨m 1970, vµ ngay sau ®ã ®· trë thµnh mét kh¸i niÖm trung t©m cña
khoa häc mËt m· hiÖn ®¹i. Ta sÏ dµnh phÇn lín néi dung gi¸o tr×nh
nµy cho c¸c hÖ mËt m· ®ã vµ nh÷ng øng dông cña chóng vµo c¸c
vÊn ®Ò an toµn th«ng tin.
1.4. C¸c bµi to¸n vÒ an toµn th«ng tin.
Chóng ta ®ang sèng trong mét thêi ®¹i bïng næ th«ng tin.
Nhu cÇu trao ®æi th«ng tin vµ c¸c ph−¬ng tiÖn truyÒn ®−a th«ng tin
ph¸t triÓn mét c¸ch nhanh chãng. Vµ cïng víi sù ph¸t triÓn ®ã, ®ßi
hái b¶o vÖ tÝnh bÝ mËt vµ an toµn cña th«ng tin còng cµng ngµy cµng
to lín vµ cã tÝnh phæ biÕn. Cã nhiÒu bµi to¸n kh¸c nhau vÒ yªu cÇu
an toµn th«ng tin tïy theo nh÷ng t×nh huèng kh¸c nhau, nh−ng tùu
16
trung cã mét sè bµi to¸n chung nhÊt mµ ta th−êng gÆp trong thùc
tiÔn lµ nh÷ng bµi to¸n sau ®©y:
- b¶o mËt : gi÷ th«ng tin ®−îc bÝ mËt ®èi víi tÊt c¶ mäi
ng−êi, trõ mét Ýt ng−êi cã thÈm quyÒn ®−îc ®äc, biÕt th«ng tin ®ã;
- toµn vÑn th«ng tin : b¶o ®¶m th«ng tin kh«ng bÞ thay ®æi
hay xuyªn t¹c bëi nh÷ng kÎ kh«ng cã thÈm quyÒn hoÆc b»ng nh÷ng
ph−¬ng tiÖn kh«ng ®−îc phÐp;
- nhËn thùc mét thùc thÓ : x¸c nhËn danh tÝnh cña mét thùc
thÓ, ch¼ng h¹n mét ng−êi, mét m¸y tÝnh cuèi trong m¹ng, mét thÎ
tÝn dông,... ;
- nhËn thùc mét th«ng b¸o : x¸c nhËn nguån gèc cña mét
th«ng b¸o ®−îc göi ®Õn ;
- ch÷ ký : mét c¸ch ®Ó g¾n kÕt mét th«ng tin víi mét thùc thÓ,
th−êng dïng trong bµi to¸n nhËn thùc mét th«ng b¸o còng nh−
trong nhiÒu bµi to¸n nhËn thùc kh¸c ;
- ñy quyÒn : chuyÓn cho mét thùc thÓ kh¸c quyÒn ®−îc ®¹i
diÖn hoÆc ®−îc lµm mét viÖc g× ®ã ;
- cÊp chøng chØ : cÊp mét sù x¸c nhËn th«ng tin bëi mét thùc
thÓ ®−îc tÝn nhiÖm ;
- b¸o nhËn : x¸c nhËn mét th«ng b¸o ®· ®−îc nhËn hay mét
dÞch vô ®· ®−îc thùc hiÖn ;
- lµm chøng : kiÓm thö viÖc tån t¹i mét th«ng tin ë mét thùc
thÓ kh¸c víi ng−êi chñ së h÷u th«ng tin ®ã ;
- kh«ng chèi bá ®−îc : ng¨n ngõa viÖc chèi bá tr¸ch nhiÖm
®èi víi mét cam kÕt ®· cã (thÝ dô ®· ký vµo mét v¨n b¶n) ;
- Èn danh : che giÊu danh tÝnh cña mét thùc thÓ tham gia
trong mét tiÕn tr×nh nµo ®ã (th−êng dïng trong giao dÞch tiÒn ®iÖn
tö) ;
- thu håi : rót l¹i mét giÊy chøng chØ hay ñy quyÒn ®· cÊp;
- v©n v©n........
C¬ së cña c¸c gi¶i ph¸p cho c¸c bµi to¸n kÓ trªn lµ c¸c ph−¬ng ph¸p
mËt m·, ®Æc biÖt lµ mËt m· khãa c«ng khai, ta sÏ xem xÐt kü mét vµi
bµi to¸n ®ã trong c¸c ch−¬ng tiÕp theo.
17