Đề tài Các hệ mật mã
Tài liệu Đề tài Các hệ mật mã: Lời Nói Đầu Thế giới của chúng ta luôn sôi sục trong muôn vàn biến động được tạo ra bởi con người. Và trong thế kỷ 20 này, máy tính là một trong những sản phẩm vĩ đại nhất. Cùng với thời gian, người ta không muốn sử dụng một máy tính đơn lẻ nữa mà sẽ kết nối các máy này lại thành một mạng máy tính nhằm tăng khả năng làm việc, hiểu biết, trao đổi, cập nhật các thông tin … Mạng Internet là xu hướng phát triển của thế giới ngày nay. Hiện nay, Internet đã trở nên rất phổ biến trên toàn thế giới. Thông qua mạng Internet mọi người có thể trao đổi thông tin với nhau một cách nhanh chóng thuận tiện. Những công ty phát triển và kinh doanh trên môi trường Intranet/Internet họ phải đối diện với khó khăn lớn là làm thế nào để bảo vệ những dữ liệu quan trọng, ngăn chặn những hình thức tấn công, truy xuất dữ liệu bất hợp pháp từ bên trong (Intranet), lẫn ca...
Bạn đang xem trước 20 trang mẫu tài liệu Đề tài Các hệ mật mã, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Lôøi Noùi Ñaàu
Theá giôùi cuûa chuùng ta luoân soâi suïc trong muoân vaøn bieán ñoäng ñöôïc taïo ra bôûi con ngöôøi. Vaø trong theá kyû 20 naøy, maùy tính laø moät trong nhöõng saûn phaåm vó ñaïi nhaát. Cuøng vôùi thôøi gian, ngöôøi ta khoâng muoán söû duïng moät maùy tính ñôn leû nöõa maø seõ keát noái caùc maùy naøy laïi thaønh moät maïng maùy tính nhaèm taêng khaû naêng laøm vieäc, hieåu bieát, trao ñoåi, caäp nhaät caùc thoâng tin … Maïng Internet laø xu höôùng phaùt trieån cuûa theá giôùi ngaøy nay. Hieän nay, Internet ñaõ trôû neân raát phoå bieán treân toaøn theá giôùi. Thoâng qua maïng Internet moïi ngöôøi coù theå trao ñoåi thoâng tin vôùi nhau moät caùch nhanh choùng thuaän tieän. Nhöõng coâng ty phaùt trieån vaø kinh doanh treân moâi tröôøng Intranet/Internet hoï phaûi ñoái dieän vôùi khoù khaên lôùn laø laøm theá naøo ñeå baûo veä nhöõng döõ lieäu quan troïng, ngaên chaën nhöõng hình thöùc taán coâng, truy xuaát döõ lieäu baát hôïp phaùp töø beân trong (Intranet), laãn caû beân ngoaøi (Internet). Khi moät ngöôøi muoán trao ñoåi thoâng tin vôùi moät ngöôøi hay moät toå chöùc naøo ñoù thoâng qua maïng maùy tính thì yeâu caàu quan troïng laø laøm sao ñeå ñaûm baûo thoâng tin khoâng bò sai leäch hoaëc bò loä do söï xaâm nhaäp cuûa keû thöù ba. Tröôùc caùc yeâu caàu caàn thieát ñoù, moät soá giaûi thuaät maõ hoùa ñaõ döôïc xaây döïng nhaèm ñaûm baûo tính an toaøn döõ lieäu taïi nôi löu tröõ cuõng nhö khi döõ lieäu ñöôïc truyeàn treân maïng, nhö caùc giaûi thuaät maõ hoùa ñoái xöùng (DES), giaûi thuaät maõ hoùa coâng khai, ... Vieäc tìm hieåu vaø xaây döïng chöông trình caùc giaûi thuaät naøy cuõng khoâng naèm ngoaøi muïc ñích cuûa baûn luaän vaên naøy. Luaän vaên coù nhieäm vuï tìm hieåu lyù thuyeát veà maät maõ hoaù thoâng tin, xaây döïng server taïo khoùa cho user trong vaán ñeà baûo maät döõ lieäu.
Do thôøi gian vaø khaû naêng coù haïn, trong khi phaïm vi ñeà taøi laïi roäng, nhöõng ngöôøi thöïc hieän chæ coù theå tìm hieåu ñöôïc moät soá giaûi thuaät chính nhö : DES, ECB, CBC, RSA, MD5 vaø qua ñoù ñöa ra moâ hình server taïo khoùa cho caùc user, cuï theå laø laøm theá naøo ñeå quaûn lyù vaø phaân phoái khoùa moät caùch an toaøn, hieäu quaû. Chaéc chaén raèng taäp thuyeát minh naøy seõ khoâng traùnh khoûi nhöõng thieáu soùt, ngöôøi thöïc hieän mong nhaän ñöôïc söï goùp yù, chæ daãn theâm cuûa caùc Thaày Coâ, baïn beø ñeå baûn thuyeát minh ñöôïc hoaøn thieän hôn. Chuùng toâi xin chaân thaønh caûm ôn Thaày höôùng daãn, caùc Thaày Coâ trong khoa ñaõ taïo ñieàu kieän thuaän lôïi ñeå baûn thuyeát minh naøy coù theå hoaøn thaønh ñuùng thôøi haïn.
Chöông 1: Caùc heä maät maõ
Heä maät maõ ñoái xöùng:
1.1. Giôùi thieäu:
Caùc giaûi thuaät maät maõ ñoái xöùng laø caùc giaûi thuaät söû duïng cuøng moät khoùa bí maät cho taùc vuï maõ hoùa vaø taùc vuï giaûi maõ. Ví du ïnhö caùc giaûi thuaät thay theá vaø hoaùn vò, giaûi thuaät DES,…. ÔÛ ñaây ta chæ tìm hieåu giaûi thuaät DES (Data Encryption Standard) laø giaûi thuaät maät maõ ñoái xöùng ñöôïc söû duïng phoå bieán nhaát.
1.2. Giaûi thuaät DES (Data Encryption Standard) :
Vaøo naêm 1977, "National Bureau of standard" ñaõ ñöa ra chuaån DES ñeå söû duïng cho caùc öùng duïng ôû Myõ. DES maõ hoùa caùc khoái data 64 bits vôùi khoùa 56 bits. Giaûi thuaät duøng ñeå maõ hoùa laãn giaûi maõ ñöôïc moâ taû toùm taét nhö hình 1.
Tröôùc tieân 64 bit input T ñöôïc hoaùn vò bôûi pheùp hoaùn vò hoaùn vò khôûi ñoäng IP, vôùi To = IP(T). Sau khi qua 16 voøng laëp (moãi voøng söû duïng moät khoùa 48 bit ñöôïc taïo ra töø khoùa input 56 bits) vôùi taùc ñoäng cuûa haøm F, noù ñöôïc hoaùn vò baèng pheùp hoaùn vò ñaûo IP-1 ñeå taïo ra 64 bit output cuoái cuøng. IP vaø IP-1 ñöôïc cho trong caùc baûng (baûng 1a vaø baûng 1b). Caùc baûng naøy ñöôïc ñoïc töø traùi sang phaûi, töø treân xuoáng döôùi theo daïng:
T = t1t2…..t64 à T0 = t58t50…….t7
Ñaàu tieân khoái T ñöôïc taùch thaønh hai khoái traùi vaø phaûi (moãi khoái 32 bits):
T = L0R0 vôùi L0 = t1…..t32 , R0 = t33…..t64.
ÔÛ voøng laëp thöù i (0 < i < 16) : Li = Ri-1 , Ri = Li-1 Å F(Ri-1, Ki) trong ñoù Å laø pheùp coäng exclusive_or vaø Ki laø khoùa 48 bits. ÔÛ voøng laëp cuoái cuøng caùc nhaùnh traùi vaø phaûi khoâng ñoåi choã cho nhau vì vaäy input cuûa IP-1 laø R16L16 .
Haøm F vaø S_boxes: (hình 3)
Tröôùc tieân Ri-1 ñöôïc môû roäng thaønh khoái 48 bits E(Ri-1) vôùi E laø baûng löïa choïn bit ñöôïc cho trong baûng 2. Sau ñoù thöïc hieän pheùp XOR E(Ri-1) vôùi Ki vaø keát quaû ñöôïc taùch thaønh 8 khoái 6 bit töø B1 tôùi B8 :
E(Ri-1) Å Ki = B1B2...B8
Moãi khoái Bj sau ñoù ñöôïc ñöa vaøo moät haøm Sj (S - box) : Sj (Bj) traû veà moät khoái 4 bit (baûng 4). Caùc khoái naøy ñöôïc noái laïi vaø khoái keát quaû 32 bit ñöôïc hoaùn vò baèng pheùp P (baûng 3).
F(Ri-1 , Ki) = P(S1(B1) …. S8(B8))
Hoaït ñoäng cuûa S-box: soá nguyeân töông öùng vôùi b1b6 seõ choïn Row trong baûng, coøn soá nguyeân töông öùng vôùi b3b4b5b6 seõ choïn Column. Giaù trò cuûa Sj(Bj) ñöôïc choïn seõ laø moät soá nguyeân 4 bit ôû vò trí Row vaø Column ñoù.
Tính khoùa: (hình 2)
DES taïo ra 16 khoùa, moãi khoùa chieàu daøi 48 bit töø moät khoùa input 56 bit, duøng cho 16 voøng laëp. Löu ñoà tính toaùn khoùa ñöôïc cho trong hình 2:
Khoùa input laø moät khoái 64 bit, vôùi 8bit parity taïi caùc vò trí 8, 16,.…, 64. Permutation PC-1 seõ loaïi boû caùc bit parity vaø seõ hoaùn vò 56 bit coøn laïi theo baûng 5. Keát quaû, PC-1(K) sau ñoù ñöôïc chia thaønh hai phaàn C0 vaø D0 moãi phaàn 28 bit. Khoùa Ki duøng trong voøng thöù i ñöôïc taïo ra töø Ci-1 vaø Di-1 theo quy taéc nhö sau: trong caùc voøng 1, 2, 9 vaø 16, Ci-1 vaø Di-1 ñöôïc quay voøng moät bít qua traùi, trong caùc voøng coøn laïi thì ñöôïc quay voøng hai bít qua traùi. Qua pheùp quay voøng naøy Ci-1 vaø Di-1 seõ ñöôïc bieán ñoåi thaønh Ci vaø Di . Hoaùn vò Ci vaø Di theo baûng 6. Sau khi hoaùn vò Ci boû qua caùc bít 9, 18, 22, 25 taïo thaønh nöõa traùi cuûa Ki (24 bít), coøn Di boû ñi caùc bít 35, 38, 43, 54 taïo ra nöõa phaûi cuûa Ki (24 bít). Gheùp nöõa traùi vaø nöõa phaûi taïo ra khoùa Ki 48 bít.
Giaûi maõ:
Quaù trình giaûi maõ ñöôïc thöïc hieän theo cuøng giaûi thuaät naøy theo thöù töï ngöôïc laïi nhö sau: IP-1 laø ñaûo cuûa IP vaø ôû voøng laëp thöù i söû duïng khoùa K17-i (K16 ôû voøng laëp ñaàu tieân, K1 ôû voøng laëp cuoái cuøng) vaø:
Ri-1 = Li
L i-1 = Ri Å F(Li, Ki)
8 48 16 56 24 64 32
7 47 15 55 23 63 31
6 46 14 54 22 62 30
5 45 13 53 21 61 29
4 44 12 52 20 60 28
3 43 11 51 19 59 27
2 42 10 50 18 58 26
33 1 41 9 49 17 57 25
50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
54 46 38 30 22 14 6
56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
Baûng 1a: Baûng hoaùn vò ñaàu tieân IP Baûng 1b: Baûng hoaùn vò cuoái cuøng IP-1
7 20 21
12 28 17
15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25
32 1 2 3 4 5
4 5 6 7 8 9
9 10 11 12 13
13 14 15 16 17
17 18 19 20 21
21 22 23 24 25
25 26 27 28 29
28 29 30 31 32 1
Baûng 2: Baûng choïn bít E Baûng 3: Baûng hoaùn vò P
57 49 41 33 25 17 9
1 58 50 42 34 26 18
2 59 51 43 35 27
19 11 3 60 52 44 36
63 55 47 39 31 23 15
62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4
14 17 11 24 1 5
3 8 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
52 31 37 47 55
40 51 45 33 48
49 39 56 34 53
46 42 50 36 29 32
Baûng 5: Baûng hoaùn vò khoùa PC-1 Baûng 6: Baûng hoaùn vò khoùa PC-2
Column
Row
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Box
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
14
0
4
15
15
3
0
13
10
13
13
1
7
13
10
3
2
14
4
11
12
10
9
4
4
13
1
6
13
1
7
2
4
15
1
12
1
13
14
8
0
7
6
10
13
8
6
15
12
11
2
8
1
15
14
3
11
0
4
11
2
15
11
1
13
7
14
8
8
4
7
10
9
0
4
13
14
11
9
0
4
2
1
12
10
4
15
2
2
11
11
13
8
13
4
14
1
4
8
2
14
7
11
1
14
9
9
0
3
5
0
6
1
12
11
7
15
2
5
12
14
7
13
8
4
8
1
7
2
14
13
4
6
15
10
3
6
3
8
6
0
6
12
10
7
4
10
1
9
7
2
9
15
4
12
1
6
10
9
4
15
2
6
9
11
2
4
15
3
4
15
9
6
15
11
1
10
7
13
14
2
12
8
5
0
9
3
4
15
3
12
10
11
13
2
1
3
8
13
4
15
6
3
8
9
0
7
13
11
13
7
2
6
9
12
15
8
1
7
10
11
7
14
8
8
1
11
7
4
14
1
2
5
10
0
7
10
3
13
8
6
1
8
13
8
5
3
10
13
10
14
7
1
4
2
13
3
10
15
5
9
12
5
11
1
2
11
4
1
4
15
9
8
5
15
6
0
6
7
11
3
14
10
9
10
12
0
15
10
6
12
11
7
0
8
6
13
8
1
15
2
7
1
4
5
0
9
15
13
1
0
14
12
3
15
5
9
5
6
12
6
12
9
3
2
1
12
7
12
5
2
14
8
2
3
5
3
15
12
0
3
13
4
1
9
5
6
0
3
6
0
9
12
11
7
14
13
10
6
12
7
14
12
3
5
12
14
11
15
10
5
9
4
14
10
7
7
12
8
15
14
11
13
0
5
9
3
10
12
6
9
0
11
12
5
11
11
1
5
12
13
3
6
10
14
0
1
6
5
2
0
14
5
0
15
3
9
5
10
0
0
9
3
5
4
11
10
5
12
10
2
7
0
9
3
4
7
11
13
0
10
15
5
2
0
14
3
6
0
3
5
6
5
11
2
14
2
15
14
2
4
14
8
2
14
8
0
5
5
3
11
8
6
8
9
3
12
9
5
5
7
8
0
13
10
5
15
9
8
1
7
12
15
9
4
14
9
6
14
3
11
8
6
13
1
6
2
12
7
2
8
11
S1
S2
S3
S4
S5
S6
S7
S8
Baûng 4: Baûng choïn (S-boxex)
1.2.1. DES In Electronic CodeBook Mode (ECB) :
ÔÛ mode naøy, caùc khoái data döôùi daïng roû (clear text) ñöôïc ñöa vaøo input cuûa DES. Caùc khoái keát quaû döôùi daïng maät maõ (ciphertext) coù theå ñöôïc söû duïng cho caùc öùng duïng khaùc. Quaù trình bieán ñoåi dieãn ra nhö sau: (hình 4)
Clear text à Input block à DES à Output block à Ciphertext.
ECB encryption ECB decription
Clear text
(D1, D2, ... D64)
Cipher text
(C1, C2, … C64)
Input block
(I1, I2, … I64)
Input block
(I1, I2, … I64)
DES encrypt
DES decrypt
Output block
(O1, O2, … O64)
Output block
(O1, O2, … O64)
Cipher text
(C1, C2, … C64)
Clear text
(D1, D2, ... D64)
Hình 4: Electronic Codebook Mode (ECB)
1.2.2. DES In Cipher Block Chaining Mode (CBC) :
Khoái data caàn maõ hoùa ñöôïc chia thaønh caùc khoái B1, B2, … Bn vôùi kích thöôùc moãi khoái laø 64 bits. Vectô khôûi taïo IV (64 bits) ñöôïc choïn. Sô ñoà maät maõ ñöoïc cho trong hình 5:
+ Quaù trình maõ hoùa:
Maõ hoùa
(1) IV Å B1 C1
(2) C1 Å B2 C2
. .
(n) Cn-1 Å Bn Cn
+ Quaù trình giaûi maõ:
Giaûi maõ
C1 IV Å B1 , (IV Å B1) Å IV = B1
C2 C1 Å B2 , (C1 Å B2) Å C1 = B2
. .
Cn Cn-1 Å Bn , (Cn-1 Å Bn) Å Cn-1 = Bn
Time = 1 Time = 2 ..................... Time = n
Bn
B2
B1
IV
+
+
+
Maõ hoùa
I
I
I
DES encry
DES encry
DES encry
........
Cn
C2
C1
.........
IV
I
I
I
DES decry
DES decry
DES decry
Giaûi maõ
+
+
+
Bn
B2
B1
Hình 5: Cipher Block Chaining (CBC) mode
2. Heä maät maõ baát ñoái xöùng
2.1. Giôùi thieäu:
- Söï phaùt trieån cuûa maät maõ khoùa coâng khai laø raát lôùn vaø coù leõ chính noù taïo ra cuoäc caùch maïng trong toaøn boä lòch söû cuûa maät maõ khoùa.
- Nhöõng giaûi thuaät khoùa coâng khai ñeàu döïa treân nhöõng haøm toaùn hoïc hôn laø nhöõng pheùp thay theá vaø hoaùn vò trong maät maõ khoùa coå ñieån. Quan troïng hôn maät maõ khoùa coâng khai coù tính chaát baát ñoái xöùng, bao goàm vieäc söû duïng 2 khoùa rieâng bieät töông phaûn vôùi maõ hoùa qui öôùc coù tính ñoái xöùng maø chæ söï duïng 1 khoùa. Vieäc söû duïng 2 khoùa coù taàm quan troïng saâu saéc trong lónh vöïc caàn tính bí maät, phaân boá khoùa vaø söï chöùng thöïc.
- Moät soá quan nieäm sai lieân quan ñeán maõ hoùa khoùa coâng khai :
+ Maõ hoùa khoùa coâng khai thì baûo maät ñoái vôùi nhaø phaân tích maät maõ hôn laø maõ hoùa qui öôùc. Thaät ra, tính baûo maät cuûa baát kyø sô ñoà maõ hoùa naøo ñeàu phuï thuoäc vaøo chieàu daøi cuûa khoùa vaø vieäc tính toaùn ñeå giaûi quyeát vieäc beû khoùa.
+ Maõ hoùa khoùa coâng khai coù muïc tieâu chung, kyõ thuaät ñöôïc thöïc hieän baèng maõ hoùa qui öôùc loãi thôøi. Ngöôïc laïi, bôøi vì vieäc tính toaùn ñöôïc ñaët haøng ñaàu trong sô ñoà maõ hoùa khoùa coâng khai, cho neân döôøng nhö khoâng theå thaáy tröôùc khaû naêng xaûy ra raèng maõ hoùa qui öôùc seõ bò boû rôi. Moät trong nhöõng ngöôøi ñaõ khaùm phaù ra maõ hoùa khoùa coâng khai ñaõ phaùt bieåu : “Haïn cheá cuûa maät maõ khoùa coâng khai ñeå quaûn lyù khoùa vaø söû duïng chöõ kyù laø haàu nhö ñöôïc chaáp nhaän phoå bieán”.
+ Coù caûm giaùc raèng söï phaân boá khoùa thì khoâng quan troïng trong khi söû duïng maõ hoùa khoùa coâng khai, so saùnh thì cô cheá baét tay trôû ngaïi hôn, bao goàm nhöõng trung taâm phaân boá khoùa cho maõ hoùa qui öôùc. Thaät ra, 1 vaøi khuoân daïng giao thöùc laø caàn thieát, noùi chung bao goàm 1 taùc nhaân trung taâm vaø nhöõng thuû tuïc lieân quan thì khoâng ñôn giaûn maø cuõng khoâng hieäu quaû hôn yeâu caàu cho vieäc maõ hoùa khoùa coâng khai naøy.
2.2. Lyù thuyeát veà maät maõ khoùa coâng khai:
- Khaùi nieäm maät maõ khoùa coâng khai ñaõ taïo ra söï coá gaéng ñeå giaûi quyeát 2 vaán ñeà khoù khaên nhaát trong maõ khoùa qui öôùc, ñoù laø söï phaân boá khoùa vaø chöõ kyù soá:
+ Trong maõ hoùa qui öôùc söï phaân boá khoùa yeâu caàu hoaëc laø hai ngöôøi truyeàn thoâng cuøng (share) tham gia moät khoùa maø baèng caùch naøo ñoù ñaõ ñöôïc phaân boá tôùi hoï hoaëc laø söû duïng chung moät trung taâm phaân boá khoùa. Whitfield Diffie, moät trong nhöõng ngöôøi khaùm phaù ra maät maõ khoùa coâng khai (cuøng vôùi Martin Hellman) ñaõ giaûi thích raèng yeâu caàu naøy ñaõ phuû ñònh baûn chaát cuûa maät maõ: khaû naêng baûo veä tính bí maät hoaøn haûo qua vieäc truyeàn thoâng rieâng cuûa baïn: “Noù seõ laøm toát nhö theá naøo sau moïi söï phaùt trieån, heä thoáng khoâng theå xuyeân qua ñöôïc neáu caùc user bò baét buoäc tham gia (share) caùc khoùa cuûa noù vôùi moät KDC maø coù theå ñöôïc thoûa hieäp bôûi keû troäm?”.
+ Neáu vieäc söû duïng maät maõ ñaõ trôû neân phoå bieán, khoâng chæ trong quaân ñoäi maø coøn trong thöông maïi vaø nhöõng muïc ñích caù nhaân thì nhöõng ñoaïn tin vaø taøi lieäu ñieän töû seõ caàn nhöõng chöõ kyù töông ñöông ñaõ söû duïng trong caùc taøi lieäu giaáy. Töùc laø, moät phöông phaùp coù theå ñöôïc nghó ra coù quy ñònh laøm haøi loøng taát caû nhöõng ngöôøi tham gia khi maø moät ñoaïn tin soá ñöôïc gôûi bôûi moät caù nhaân ñaëc bieät hay khoâng?.
- Trong sô ñoà maõ hoùa quy öôùc, caùc khoùa ñöôïc duøng cho maõ hoùa vaø giaûi maõ moät ñoaïn tin laø gioáng nhau. Ñaây laø moät ñieàu kieän khoâng caàn thieát. Thay vì noù coù theå phaùt trieån giaûi thuaät maõ hoùa döïa treân moät khoùa cho maõ hoùa vaø moät khoùa khaùc (coù quan heä vôùi khoùa treân) cho giaûi maõ. Hôn nöõa caùc giaûi thuaät naøy coù nhöõng ñaëc ñieåm quan troïng sau:
+ Ñoù laø vieäc tính toaùn moät caùch khoâng khaû thi ñeå xaùc ñònh khoùa giaûi maõ trong khi chæ bieát giaûi thuaät maät maõ vaø khoùa maõ hoùa.
+ Trong giaûi thuaät RSA coøn coù ñaëc ñieåm hoaëc moät trong hai khoùa quan heä coù theå ñöôïc söû duïng cho maõ hoùa coøn khoùa kia ñöôïc duøng cho giaûi maõ.
- Caùc böôùc caàn thieát trong quaù trình maõ hoùa khoùa coâng khai:
+ Moãi heä thoáng cuoái trong maïng taïo ra moät caëp khoùa ñeå duøng cho maõ hoùa vaø giaûi maõ ñoaïn tin maø noù seõ nhaän.
+ Moãi heä thoáng coâng boá roäng raõi khoùa maõ hoùa baèng caùch ñaët khoùa vaøo moät thanh ghi hay moät file coâng khai. Ñaây laø khoùa coâng khai, khoùa coøn laïi ñöôïc giöõ rieâng.
+ Neáu A muoán gôûi moät ñoaïn tin tôùi B thì A maõ hoùa ñoaïn tin baèng khoùa coâng khai cuûa B.
+ Khi B nhaän ñoaïn tin maõ hoùa, noù giaûi maõ baèng khoùa bí maät cuûa mình. Khoâng moät ngöôøi naøo khaùc coù theå giaûi maõ ñoaïn tin maõ naøy bôûi vì chæ coù mình B bieát khoùa bí maät ñoù thoâi.
Khoùa coâng khai cuûa B
User A
User B
Giaûi thuaät giaûi maõ
Giaûi thuaät maõ hoùa
khoùa bí maät cuûa B
ñoaïn tin maät maõ ñoaïn tin
Vôùi caùch tieáp caän naøy, taát caû nhöõng ngöôøi tham gia coù theå truy xuaát khoùa coâng khai. Khoùa bí maät ñöôïc taïo ra bôûi töøng caù nhaân, vì vaäy khoâng bao giôø ñöôïc phaân boá. ÔÛ baát kyø thôøi ñieåm naøo, heä thoáng cuõng coù theå chuyeån ñoåi caëp khoùa ñeå ñaûm baûo tính baûo maät.
- Baûng sau toùm taét moät soá khía caïnh quan troïng veà maõ hoùa quy öôùc vaø maõ hoùa coâng khai: ñeå phaân bieät giöõa hai loaïi, chuùng ta seõ toång quaùt hoùa lieân heä khoùa söû duïng trong maõ hoùa quy öôùc laø khoùa bí maät, hai khoùa söû duïng trong maõ hoùa coâng khai laø khoùa coâng khai vaø khoùa bí maät.
Maõ hoùa quy öôùc
Maõ hoùa coâng khai
* Yeâu caàu:
- Giaûi thuaät töông töï cho maõ hoùa vaø giaûi maõ.
- Ngöôøi gôûi vaø ngöôøi nhaän phaûi tham gia cuøng giaûi thuaät vaø cuøng khoùa.
* Tính baûo maät:
- Khoùa phaûi ñöôïc giöõ bí maät.
- Khoâng theå hay ít nhaát khoâng coù tính thöïc teá ñeå giaûi maõ ñoaïn tin neáu thoâng tin khaùc khoâng coù saün.
- Kieán thöùc veà giaûi thuaät coäng vôùi caùc maãu veà maät maõ khoâng ñuû ñeå xaùc ñònh khoùa.
* Yeâu caàu:
- Moät giaûi thuaät cho maõ hoùa vaø moät giaûi thuaät cho giaûi maõ.
- Ngöôøi gôûi vaø ngöôøi nhaän , moãi ngöôøi phaûi coù caëp khoùa cho rieâng mình.
* Tính baûo maät:
- Moät trong hai khoùa phaûi ñöôïc giöõ bí maät.
- Khoâng theå hay ít nhaát khoâng coù tính thöïc teá ñeå giaûi maõ ñoaïn tin neáu thoâng tin khaùc khoâng coù saün.
- Kieán thöùc veà giaûi thuaät coäng vôùi moät trong caùc khoùa, coäng vôùi caùc maãu veà maät maõ khoâng ñuû ñeå xaùc ñònh khoùa kia.
- Caùc sô ñoà maät maõ quy öôùc vaø maät maõ khoùa coâng khai: xem sô ñoà beân
2.3. ÖÙng duïng cuûa maät maõ khoùa coâng khai:
- Tuøy thuoäc vaøo öùng duïng, ngöôøi gôûi söû duïng hoaëc khoùa bí maät cuûa ngöôøi gôûi hoaëc khoùa coâng khai cuûa ngöôøi nhaän hoaëc caû hai maø hình thaønh moät soá kieåu chöùc naêng cuûa maät maõ khoùa. Coù 3 chieán löôïc sau:
+ Maõ hoùa/giaûi maõ: ngöôøi gôûi maõ hoùa ñoaïn tin baèng khoùa coâng khai cuûa ngöôøi nhaän, ngöôøi nhaän giaûi maõ baèng khoùa bí maät cuûa mình.
+ Chöõ kyù soá: ngöôøi gôûi maõ hoùa ñoaïn tin (kyù teân) baèng khoùa bí maät cuûa mình, ngöôøi nhaän giaûi maõ baèng khoùa coâng khai cuûa ngöôøi gôûi. Chöõ kyù ñöôïc aùp duïng tôùi ñoaïn tin hay tôùi moät khoái döõ lieäu nhoû maø ñöôïc lieân keát trong moät soá phöông thöùc tôùi ñoaïn tin.
+ Chuyeån ñoåi khoùa: ngöôøi gôûi maõ hoùa ñoaïn tin hai laàn, laàn 1 söû duïng khoùa bí maät cuûa baûn thaân, laàn 2 söû duïng khoùa coâng khai cuûa ngöôøi nhaän. Ngöôøi nhaän giaûi maõ ñoaïn tin nhaän ñöôïc baèng khoùa bí maät cuûa baûn thaân vaø khoùa coâng khai cuûa ngöôøi gôûi.
- Moät soá giaûi thuaät cho maät maõ khoùa coâng khai: RSA, ECC, LUC, DSS, Diffie_Hellman…. Trong ñoà aùn naøy, chæ trình baøy giaûi thuaät RSA.
2.4. Caùc yeâu caàu cuûa maät maõ khoùa coâng khai:
- Coâng vieäc tính toaùn thì deã daøng cho ngöôøi nhaän B à taïo caëp khoùa: khoùa coâng khai KU vaø khoùa bí maät KR.
- Coâng vieäc tính toaùn thì deã daøng cho ngöôøi gôûi A à bieát khoùa coâng khai vaø ñoaïn tin caàn maõ hoùa M, ñeå taïo maät maõ töông öùng: C=EKUb (M).
- Coâng vieäc tính toaùn thì deã daøng cho ngöôøi nhaän B à söû duïng khoùa bí maät ñeå giaûi maõ ñoaïn tin maõ hoùa C, khoâi phuïc laïi ñoaïn tin ñaàu:
M= DKRb (C)= DKRb [EKUb (M)]
- Coâng vieäc tính toaùn khoâng theå thaáy tröôùc ñoái vôùi ñòch thuû bieát khoùa coâng khai KUb, ñeå xaùc ñònh khoùa bí maät KRb.
- Coâng vieäc tính toaùn khoâng theå thaáy tröôùc ñoái vôùi ñòch thuû bieát khoùa coâng khai KUb vaø moät maät maõ C, ñeå khoâi phuïc ñoaïn tin ban ñaàu M.
- Chöùc naêng maõ hoùa vaø giaûi maõ coù theå ñöôïc aùp duïng theo thöù töï:
M= DKRb [EKUb (M)]
M= EKUb [DKRb (M)]
Coù theå nhaän thaáy raèng vieäc tính Y=f(X) thì deã daøng trong khi tính X=f –1(Y) laø khoâng theå thaáy tröôùc. Noùi chung töø “deã daøng” ñöôïc xaùc ñònh bôûi 1 baøi toaùn laø noù coù theå ñöôïc giaûi quyeát trong thôøi gian nhaát ñònh (haøm cuûa chieàu daøi input). Neáu chieàu daøi input laø n bít thì thôøi gian ñeå tính haøm ñoù tæ leä vôùi na (a=const). Ñeå ñaûm baûo tính baûo maät, phaûi söû duïng khoùa coù kích thöôùc ñuû lôùn (thöôøng treân 100 chöõ soá thaäp phaân). Ví duï kích thöôùc khoùa vaø thôøi gian beû khoùa (MIPS naêm) trong caùc giaûi thuaät RSA/DSS vaø ECC nhö sau:
RSA (bít)
ECC (bít)
MIPS naêm
512
768
1024
106
132
160
104
108
1012
2.5. Giaûi thuaät RSA (Rivest, Shamir vaø Adleman – 1977):
2.5.1. Moâ taû giaûi thuaät:
- Sô ñoà RSA laø sô ñoà maõ hoùa khoái: ñoaïn tin ñöôïc maõ hoùa töøng khoái, vôùi moãi khoái coù giaù trò nhoû hôn n. Vieäc maõ hoùa vaø giaûi maõ theo hình thöùc sau, cho khoái vaên baûn M vaø khoái baûo maät C:
C = Me mod n
M = Cd mod n = (Me)d mod n = Mde mod n
- Caû hai ngöôøi gôûi vaø nhaän phaûi bieát giaù trò n, ngöôøi gôûi bieát e vaø chæ coù ngöôøi nhaän bieát d. Cho neân ñaây laø giaûi thuaät maõ hoùa vôùi khoùa coâng khai KU=[e,n] vaø khoùa bí maät KR=[d,n]. Vì giaûi thuaät naøy thoûa giaûi thuaät maät maõ khoùa coâng khai neân caùc yeâu caàu sau phaûi ñöôïc ñaùp öùng:
+ Coù theå tìm thaáy giaù trò d,e,n ñeå M=Mde mod n vôùi moïi M<n hay khoâng?
+ Moät caùch töông ñoái deã daøng tính Me vaø Cd vôùi moïi M<n hay khoâng?
+ Khoâng theå xaùc ñònh d khi bieát e vaø n.
- Theo lí thuyeát cuûa Euler: cho 2 soá nguyeân toá p vaø q, 2 soá nguyeân n vaø m (n=p*q , 0<m<n) vaø soá nguyeân k. Ta coù:
mk0 (n) + 1 = mk (p-1) (q-1) + 1 = m mod n
0(n) = 0(pq) = (p-1)(q-1)
Do ñoù:
neáu: de = k0(n) +1 vaø gcd(0(n),e) = 1 (gcd: öôùc soá chung)
thì : de mod 0(n) = 1 vaø d mod 0(n) = e-1
- Sô ñoà RSA:
+ Giaû söû user A ñaõ coâng boá khoùa coâng khai e cuûa noù vaø user B muoán gôûi ñoaïn tin M tôùi A. Khi ñoù B tính C = Me mod n vaø truyeàn C. Khi nhaän ñöôïc ñoaïn tin C naøy, user A giaûi maõ baèng caùch tính Cd mod n. Coù theå thaáy raèng M = Cd mod n vì:
de mod 0(n) = 1 hay de = k0(n) + 1
à Mk0 (n) + 1 = Mk (p-1) (q-1) + 1 = M mod n = (Mde mod n) mod n = Mde mod n
Cd mod n = (Me)d mod n = Mde mod n = M
+ Coù theå toùm taét giaûi thuaät RSA nhö baûng sau:
Taïo khoùa
Ñoä phöùc taïp
Taïo 2 soá nguyeân toá lôùn p vaø q
Tính n = p*q, 0(n) = (p-1)*(q-1)
Choïn 1 soá ngaãu nhieân 1<e<0(n): gcd(0(n), e) = 1
Tính d: d = e-1 mod 0(n) (giaûi thuaät Extended Euclidean)
Khoùa coâng khai KU = [e, n]
Khoùa bí maät KR = [d, n]
0((logn)2)
0((log(0(n))2)
0((logn)3)
Maõ hoùa
Ñoaïn tin : M < n
Maõ hoùa : C = Me mod n
Giaûi maõ
Ñoaïn tin maõ: C
Giaûi maõ : M = Cd mod n
- Ñoä phöùc taïp:
+ Coäng 2 soá k bít: 0(k)
+ Nhaân 2 soá k bít: 0(k2)
+ 2 k bít mod n : 0(k2)
+ xc mod n : 0(k3)
Ñeå tính xc mod n caàn c-1 pheùp nhaân modulus à khoâng hieäu quaû (do c lôùn) à söû duïng giaûi thuaät square_multiply ñeå giaûm soá pheùp nhaân mod nhieàu nhaát 2l (l laø soá bít nhò phaân cuûa c, l<=k vôùi k laø soá bít nhò phaân cuûa x)
- Toác ñoä maõ hoùa trong RSA:
Toác ñoä vaø hieäu quaû cuûa nhieàu phaàn meàm thöông maïi coù saün vaø coâng cuï phaàn cöùng cuûa RSA ñang gia taêng 1 caùch nhanh choùng. Vôùi pentium 90Mhz, boä toolkit BSAFE 3.0 cuûa cô quan baûo maät döõ lieäu RSA ñaït toác ñoä tính khoùa bí maät laø 21,6Kbps vôùi khoùa 512 bít vaø 7,4Kbps vôùi khoùa 1024 bít. Phaàn cöùng RSA nhanh nhaát ñaït hôn 300 Kbps vôùi khoùa 512 bít, neáu ñöôïc xöû lyù song song thì ñaït 600 Kbps vôùi khoùa 512 bít vaø 185Kbps vôùi khoùa 970 bít. Ngöôøi ta mong ñôïi raèng toác ñoä RSA seõ ñaït 1Mbps vaøo cuoái naêm1999. So saùnh vôùi giaûi thuaät DES vaø caùc giaûi thuaät maõ khoái khaùc thì RSA chaäm hôn: veà phaàn meàm DES nhanh hôn RSA 100 laàn, veà phaàn cöùng DES nhanh hôn RSA töø 1000 tôùi 10000 laàn tuøy thuoäc coâng cuï (implementation) söû duïng (thoâng tin naøy ñöôïc laáy töø
- Kích thöôùc khoùa trong RSA:
Tuøy thuoäc vaøo tính baûo maät caàn thieát cuûa moãi ngöôøi vaø thôøi gian soáng cuûa khoùa maø khoùa coù chieàu daøi thích hôïp:
+ Loaïi Export : 512 bít
+ Loaïi Personnal : 768 bít
+ Loaïi Commercial: 1024 bít
+ Loaïi Militery : 2048 bít
- Chu kyø soáng cuûa khoùa phuï thuoäc:
+ Vieäc ñaêng kyù vaø taïo khoùa.
+ Vieäc phaân boá khoùa.
+ Vieäc kích hoaït hoaëc khoâng kích hoaït khoùa.
+ Vieäc thay theá hoaëc caäp nhaäp khoùa.
+ Vieäc huûy boû khoùa.
+ Vieäc keát thuùc khoùa bao goàm söï phaù hoaïi hoaëc söï löu tröõ.
2.5.2. Tính baûo maät cuûa giaûi thuaät RSA:
- Vì khoùa laø coâng khai, neân ngöôøi giaûi maõ thöôøng döïa vaøo caëp khoùa naøy ñeå tìm caëp khoùa bí maät. Ñieàu quan troïng laø döïa vaøo n ñeå tính hai thöøa soá p, q cuûa n töø ñoù tính ñöôïc d. Coù nhieàu giaûi thuaät nhö theá, ñaàu tieân ta xeùt tröôøng hôïp ñôn giaûn nhaát laø ngöôøi giaûi maõ bieát ñöôïc F(n) . Khi ñoù tính p, q ñöa veà vieäc giaûi hai phöông trình sau:
n = p.q
F(n) = (p-1)(q-1)
Thay q=n/p ta ñöôïc phöông trình baäc hai:
p2 – (n - F(n) + 1)p + n = 0
Hai nghieäm cuûa phöông trình baäc hai naøy seõ laø p, q. Tuy nhieân vaán ñeà coù ñöôïc F(n) coøn khoù hôn tính hai thöøa soá cuûa n nhieàu.
2.5.2.1. Phöông phaùp p-1:
Chuùng ta bieát raèng neáu n<1012 thì vieäc tìm hai thöøa soá cuûa n khoâng maáy khoù khaên, bôûi vieäc chia n cho caùc soá töø 1 ñeán Ö n . Giaûi thuaät p-1 ñöôïc ñöa ra vaøo naêm 1974 : soá nhaäp soá leû n , vaø moät soá B raøng buoät. Giaûi thuaät :
Nhaäp n vaø B
1. a=2
2. For j=2 to B
A=aj mod n
3. d=gcd(a-1, n)
4. if 1<d<n then
d is factor of n (succcess)
else no factor of n is found (failure)
Noäi dung cuûa giaûi thuaät naøy nhö sau: giaû söû n=p.q (p, q chöa bieát) vaø B laø 1 soá nguyeân ñuû lôùn, vôùi moãi thöøa soá nguyeân toá k , k<=B maø k | (p-1) , ta phaûi coù:(p-1) | B!
Taïi cuoái cuûa voøng laëp böôùc 2 : a=2B!(mod n)
Vì theá : a= 2B!(mod p)
Vì p | n. Theo ñònh lyù Fermat , ta coù: 2p-1 =1 (mod p)
Do (p-1) | B! , neân chuùng ta coù : a=1 (mod p) (trong böôùc 3).
Vì theá ôû böôùc 4 : p | (a-1) vaø p | n, neân neáu d=gcd(a-1, n) thì d=p
Trong giaûi thuaät naøy coù B-1 pheùp tính modular baèng luõy thöøa, moãi pheùp ñoøi hoûi 2log2B pheùp modular, pheùp tính USCLN caàn thôøi gian O((log)3), giaûi thuaät Euclidean caàn thöïc hieän trong thôøi gian O((log n)3 ). Neân ñoä phöùc taïp cuûa giaûi thuaät laø O(BlogB(logn)2 +(logn)3)
Tuy nhieân xaùc xuaát thaønh coâng trong vieäc choïn B laø raát nhoû, maët khaùc neáu gia taêng kích thöôùc B raát lôùn chaúng haïn sqrt(n) thì giaûi thuaät seõ thaønh coâng , nhöng khoâng nhanh hôn giaûi thuaät chia daàn nhö trình baøy treân . Ñieàu ruùt ra töø giaûi thuaät naøy laø: n coù thöøa soá nguyeân toá p maø (p-1) chæ coù caùc öôùc soá nguyeân toá “nhoû” . Raát deã daøng ñeå xaây döïng maõ hoùa coâng khai maø khoâng bò taán coâng cuûa phöông phaùp naøy. Caùch ñôn giaûn nhaát laø tìm moât soá nguyeân toá p1 lôùn , maø p=2p1+1 cuõng laø soá nguyeân toá, töông töï tìm q1 nguyeân toá lôùn vaø q=2q1+1 nguyeân toá (söû duïng giaûi thuaät Monte _ Carlos).
2.5.2.2. Beû khoùa khi bieát ñöôïc soá muõ d cuûa haøm giaûi maõ:
- Vieäc tính soá d khoâng deã daøng, bôûi vì ñaây laø khoùa bí maät neân neáu bieát noù thì coù theå giaûi maõ ñöôïc moïi ñoaïn tin töông öùng . Tuy nhieân giaûi thuaät naøy mang nhieàu yù nghóa lyù thuyeát, noù cho chuùng ta bieát raèng neáu coù d thì ta coù theå tính caùc thöøa soá cuûa n .Neáu ñieàu naøy xaûy ra thì ngöôøi sôû höõu khoùa naøy khoâng theå thay ñoåi khoùa coâng khai, maø phaûi thay luoân soá n.
- Giaûi thuaät naøy döïa treân cô baûn laø neáu n=pq vôùi p, q laø hai soá nguyeân toá leû vaø x2 =1 (mod n) coù keát quaû chæ laø x=1 hay –1 (mod n), töông töï x2=1 (mod n) coù lôøi giaûi nhö theá.
Ta coù x2=1 (mod n) töông ñöông x2 = 1 (mod p) vaø x2 = 1 (mod q). Vì theá coù boán caên baäc hai cuûa 1 modulo n, chuùng ta coù theå söû duïng lyù thuyeát soá dö Trung Hoa.
- Giaûi thuaät nhö sau :
+ Chuùng ta coù theå phaân tích giaûi thuaät, ñaàu tieân neáu may maén choïn w laø boäi soá cuûa n thì tìm ra p, q ngay. Neáu w nguyeân toá cuøng nhau vôùi n thì chuùng ta tính wr, w2r, w4r,… modulo n cho ñeán khi toàn taïi t sao cho:
w2r T =1 (mod n)
vaø ab –1 =2sr=0(mod F(n))
+ Cuoái cuøng, taïi cuoái voøng laëp while chuùng ta tìm thaáy vo sao cho v2o =1 (mod n) nhöng vo 1 (mod n). Böôùc 12 tìm USCLN(vo +1,n) ta tìm ñöôïc p hay q.
1. choïn w baát kyø maø 1<= w<=n
2. tính x=uscln(w,n)
3. if 1<x<n then quit (thaønh coâng neáu x=p hay x=q)
4. tính a=A(b)
5. ñaët ab-1=2sr , r leû
6. tính v=wr mod n
7. if v=1 (mod n)then quit (thaát baïi)
8. while v1 (mod n) do
9. v0=v
v=v2 mod n
10. if vo=-1 (mod n) thenquit (thaát baïi)
11. else tính x=uscln(vo+1,n) ( thaønh coâng x=p;x=q)
2.5.2.3. Beû khoùa döïa treân caùc attack laëp laïi:
Siimons vaø Norris ñaõ chæ ra raèng heä thoáng RSA coù theå bò toån thöông khi söû duïng taán coâng laëp lieân tieáp (iteration attack). Ñoù laø khi ñoái thuû bieát caëp khoùa coâng khai {n,e} vaø maät maõ C thì anh ta coù theå tính chuoãi caùc maät maõ sau:
C1 = Ce (mod n)
C2 = C1e (mod n)
………………………………..
Ci = Ci-1e (mod n)
Neáu coù moät phaàn töû Cj trong chuoãi C1, C2, …, Ci, … sao cho Cj = C thì khi ñoùanh ta seõ tìm ñöôïc M = Cj-1 bôûi vì:
Cj = Cj-1e (mod n)
C = Me (mod n)
Ví duï: giaû söû ñoái thuû bieát {n, e, C} = {35, 17, 3} vaø anh ta tính:
C1 = Ce (mod n) = 317 (mod 35) = 33
C2 = C1e (mod n) = 3317 (mod 35) = 3
Vì C2 = C neân M = C1 = 33.
2.5.3. Söï che daáu thoâng tin trong heä thoáng RSA
Heä thoáng RSA coù moät ñaëc ñieåm ñaëc tröng laø thoâng tin khoâng phaûi luoân luoân ñöôïc che daáu. Giaû söû ngöôøi gôûi coù e = 17, n = 35. Neáu anh ta muoán gôûi baát cöù data naøo thuoäc taäp sau:
{1, 6, 7, 8, 13, 14, 15, 20, 21, 22, 27, 28, 29, 34}
thì moïi maät maõ cuõng chính laø data ban ñaàu. Nghiaõ laø: M = Me mod n. Coøn khi p=109, q=97, e=865 thì heä thoáng hoaøn toaøn khoâng coù söï che daáu thoâng tin , bôûi vì:
M = M865 mod (109*97) vôùi moïi M
Vôùi moãi modulus n, khoâng che daáu ñöôïc ít nhaát laø 9 message:
M = Me mod n (1)
Hay: M = Me mod p vaø M = Me mod q (2)
Vôùi moãi e, (2) coù ít nhaát 3 giaûi phaùp thuoäc taäp {0, 1, -1}. Do ñoù taát caû message thoûa (1) laø:
{M = [M (mod p), M (mod q)] / M (mod p), M (mod q) Î {0, 1, -1}}
Ñeå xaùc ñònh chính xaùc soá message khoâng ñöôïc che daáu (khoâng bò thay ñoåi sau khi maõ hoùa) ta söû duïng ñònh lyù sau:
“ Neáu caùc message ñöôïc maõ hoùa trong heä thoáng RSA ñöôïc xaùc ñònh bôûi soá modulus n = pq (p, q la nguyeân toá) vaø khoùa coâng khai e thì coù:
m = [1 + gcd(e-1, p-1)][1 + gcd(e-1), q-1]
message khoâng bò che daáu”.
2.5.4. Caùc giaûi thuaät toaùn hoïc ñöôïc söû duïng trong RSA:
2.5.4.1. Giaûi thuaät Euclidean – tìm USCLN cuûa hai soá nguyeân:
Cho hai soá nguyeân ro vaø r1, giaûi thuaät Euclidean goàm nhöõng pheùp tính sau:
ro = q1.r1 + r2
r1 = q2.r2 +r3
. .
.
rm-2 = qm-1.rm-1 + rm
rm = qm.rm
Thì gcd(ro,r1) = rm
2.5.4.2. Lyù thuyeát soá dö Trung Hoa:
Giaû söû m1,m2, …mr coù töøng caëp nguyeân toá cuøng nhau vaø giaû söû a1,a2,…ar laø nhöõng soá nguyeân . Cho r phöông trình x= aI (mod mi) (1<= I<=r) coù moät lôøi giaûi duy nhaát
x=S aiMiyi
i=1
trong ñoù Mi =M/mI vaø yI =MI-1 mod mI , M=m1*m2*…mr
2.5.4.3. Giaûi thuaät Euclidean môû roäng:
n0=n
bo=b
to=t
t=1
q=[no/bo]
r= no – q.bo
while r>0 do
temp=to –q.t
if temp>=0 then temp=temp mod n
if temp<0 then temp =n-((-temp) mod n)
to =t
t=temp
no=bo
bo =r
q=[no /bo ]
r= no –q.bo
if bo1 then
b has no inverse modulo n
else b-1 = t mod n
2.5.4.4. Giaûi thuaät Miller –Rabin kieåm tra soá nguyeân toá leû:
1. Write n-1 =2km , where m is odd
2. Chose a random integer a , 1<=a<=n-1
3. Compute b=am mod n
4. If b=1 (mod n) then anwser “n is prime “ and quit
5. for i=0 to k-1 do
if b=-1(mod n) then anwser “n is prime “ and quit
else b=b2 mod n
6. answer “n is composite”
2.5.4.5. Giaûi thuaät tính xb mod n:
Ñaàu tieân ta phaân tích soá nguyeân b döôùi daïng nhò phaân b=S bI 2I (I=0 ñeán l)
z=1
for i=l-1 downto do
z=z2 mod n
if bI =1 then z=z .z mod n
3. Giaûi thuaät baêm MD5
- Ñeå kieåm tra tính toaøn veïn cuûa moät khoái data lôùn, ngöôøi ta söû duïng chöõ kyù soá ñeå ñaïi dieän cho khoái data ñoù (gioáng nhö chöõ kyù treân vaên baûn) baèng caùch duøng haøm baêm: vôùi input laø moät message baát kyø, output laø moät chuoãi bít coù chieàu daøi xaùc ñònh tröôùc, chuoãi bít naøy ñöôïc goïi laø message_digest.
- Caùc tính chaát cô baûn cuûa haøm baêm:
+ Laø haøm moät chieàu, khoâng theå thöïc hieän pheùp bieán ñoåi ngöôïc nhö trong quaù trình maõ hoùa vaø giaûi maõ, nghóa laø vôùi moät message_digest cho tröôùc, khoù coù theå tìm ñöôïc moät message naøo maø coù haøm baêm baèng message_digest naøy.
+ Khoù coù theå tìm ñöôïc hai message maø coù cuøng moät message_digest.
- Caùc giaûi thuaät baêm ñöôïc söû duïng hieän nay laø: MD2, MD4, MD5, SHS. Trong ñoù MD5 laø giaûi thuaät baêm ñöôïc söû duïng phoå bieán vaø noù seõ ñöôïc trình baøy trong phaàn döôùi.
- Giaûi thuaät MD5 ñöôïc phaùt trieån bôûi Ron Rivest ôû MIT: nhaän ñaàu vaøo laø moät khoái data (message) coù chieàu daøi baát kyø, xöû lyù noù thaønh caùc khoái 512 bít, taïo ñaàu ra laø moät message_digest 128 bít. Quaù trình bao goàm caùc böôùc sau:
* Böôùc 1: message ban ñaàu ñöôïc theâm (padding) moät soá bít (baét ñaàu laø bít 1, keá tieáp laø caùc bít 0, soá bít theâm vaøo töø 1 tôùi 512 bít) sao cho toång soá bít sau khi theâm vaøo coäng vôùi 64 (chieài daøi cuûa message ban ñaàu) laø boäi soá cuûa 512.
Boäi soá cuûa 512 bít
Chieàu daøi message
1..512 bít
K bít
K mod 264
100 ... 000
Message
512 bít
512 bít
512 bít
512 bít
Y0
Y1
YL-1
Yp
… … …
… … …
512
512
512
512
ABCD
HMD5
HMD5
HMD5
HMD5
128
128
128
128
Digest 128 bít
Hình 1: Taïo message_digest söû duïng MD5.
* Böôùc 2: khôûi taïo boä ñeäm MD. Boä ñeäm 128 bít ñöôïc duøng ñeå chöùa keát quaû trung gian vaø cuoái cuøng cuûa haøm baêm. Coù theå xem boä ñeäm nhö laø 4 thanh ghi 32 bít. Caùc thanh ghi naøy ñöôïc khôûi taïo (daïng soá hex) nhö sau:
A = 01234567; B = 89abcdef; C = fedcba98; D = 76543210
* Böôùc 3: xöû lyù message thaønh töøng khoái 512 bít (16 töø 32 bít). Quaù trình tính toaùn ñöôïc chia thaønh töøng giai ñoaïn, soá giai ñoaïn baèng soá chieàu daøi (tính theo bít) cuûa message sau khi ñaõ padding chia cho 512. Moãi giai ñoaïn nhaän ñaàu vaøo laø khoái 512 bít cuûa message ñaõ ñöôïc padding vaø message_digest cuûa giai ñoaïn tröôùc, cho ra keát quaû laø message_digest môùi (xem hình 1). Moãi giai ñoaïn thöïc hieän trong 4 böôùc (voøng), boán voøng coù caáu truùc gioáng nhau nhöng moãi voøng söû duïng moät haøm luaän lyù khaùc nhau, ñöôïc ñaëc taû laø F, G, H, I. Trong hình 2, boán voøng ñöôïc ñaët nhaõn laø fF , fG , fH , fI , ñeå chæ raèng moãi voøng coù caáu truùc haøm toång quaùt nhö nhau nhöng tuøy thuoäc vaøo söï khaùc nhau cuûa haøm thao taùc (F, G, H, I).
Yq
MDq
128
512
32
A B C D
ABCD fF(ABCD, Yq, T[1..16]
A B C D
ABCD fG(ABCD, Yq, T[17..32]
A B C D
ABCD fH(ABCD, Yq, T[33..48]
A B C D
ABCD fI(ABCD, Yq, T[49..64]
+
+
+
+
128
MDq+1
Hình 2: Xöû lyù MD5 cuûa khoái ñôn 512 bít (HDMD5).
Moãi voøng ñöôïc thöïc hieän 16 böôùc tuaàn töï treân caùc data A, B, C, D (hình 3). Bieåu thöùc tính toaùn ñöôïc söû duïng trong moãi voøng coù daïng:
a = b + CLSs(a + g(b,c,d) + X[k] + T[i]).
Trong ñoù:
. a, b, c, d: laø 4 word A, B, C, D theo thöù töï naøo ñoù.
. g: laø moät trong caùc haøm F, G, H, I.
F(b,c,d) = (b & c) | (~b & d)
G(b,c,d) = (b & d) | (c & ~d)
H(b,c,d) = b ^ c ^ d
I(b,c,d) = c ^ (b & ~d)
. CLSs: dòch voøng beân traùi s bít.
. X[k] = M[q*16 + k] : töø 32 bít thöù k cuûa khoái 512 bít thöù q cuûa message.
. T[i] = 232 * abs(sin(i)) : töø 32 bít thöù i (i tính theo radian) (xem baûng).
. Pheùp toaùn coäng (+) tính cho modulo 232
d
c
b
a
g
X[k]
+
T[i]
+
CLSs
+
Hình 3: Taùc vuï cuûa MD5: [abcd k s i]
Baûng T ñöôïc xaây döïng töø haøm sin
T1 = D76AA478
T17 = F61E2562
T33 = FFFA3942
T49 = F4292244
T2 = E8C7B756
T18 = C040B340
T34 = 8771F681
T50 = 432AFF97
T3 = 242070D8
T19 = 265E5A51
T35 = 69D96122
T51 = AB9423A7
T4 = C1BDCEEE
T20 = E9B6C7AA
T36 = FDE5380C
T52 = FC93A039
T5 = F57C0FAF
T21 = D62F105D
T37 = A4BEEA44
T53 = 655B59C3
T6 = 4787C62A
T22 = 02441453
T38 = 4BDECFA9
T54 = 8F0CCC92
T7 = A8304613
T23 = D8A1E681
T39 = F6BB4B60
T55 = FFEFF47D
T8 = FD469501
T24 = E7D3FBC8
T40 = BEBFBC70
T56 = 85845DD1
T9 = 698098D8
T25 = 21E1CDE6
T41 = 289B7EC6
T57 = 6FA87E4F
T10 = 8B44F7AF
T26 = C33707D6
T42 = EAA127FA
T58 = FE2CE6E0
T11 = FFFF5BB1
T27 = F4D50D87
T43 = D4EF3085
T59 = A3014314
T12 = 895CD7BE
T28 = 455A14ED
T44 = 04881D05
T60 = 4E0811A1
T13 = 6B901122
T29 = A9E3E905
T45 = D9D4D039
T61 = F7537E82
T14 = FD987193
T30 = FCEFA3F8
T46 = E6DB99E5
T62 = BD3AF235
T15 = A679438E
T31 = 676F02D9
T47 = 1FA27CF8
T63 = 2AD7D2BB
T16 = 49B40281
T32 = 8D2A4C8A
T48 = C4AC5665
T64 = EB86D391
- Caùc taùc vuï [abcd k s i] trong moãi voøng laø:
Voøng 4
Voøng 3
Voøng 1
Voøng 2
ABCD
0
7
1
1
5
17
5
4
33
0
6
49
DABC
1
12
2
6
9
18
8
11
34
7
10
50
CDAB
2
17
3
11
14
19
11
16
35
14
15
51
BCDA
3
22
4
0
20
20
14
23
36
5
21
52
ABCD
4
7
5
5
5
21
1
4
37
12
6
53
DABC
5
12
6
10
9
22
4
11
38
3
10
54
CDAB
6
17
7
15
14
23
7
16
39
10
15
55
BCDA
7
22
8
4
20
24
10
23
40
1
21
56
ABCD
8
7
9
9
5
25
13
4
41
8
6
57
DABC
9
12
10
14
9
26
0
11
42
15
10
58
CDAB
10
17
11
3
14
27
3
16
43
6
15
59
BCDA
11
22
12
8
20
28
6
23
44
13
21
60
ABCD
12
7
13
13
5
29
9
4
45
4
6
61
DABC
13
12
14
2
9
30
12
11
46
11
10
62
CDAB
14
17
15
7
14
31
15
16
47
2
15
63
BCDA
15
22
16
12
20
32
2
23
48
9
21
64
- Caùc pheùp toaùn duøng trong giaûi thuaät MD5 goàm coù:
+ Pheùp toaùn ñoái (~): buø bít.
+ Pheùp toaùn and (&): and caùc bít cuûa hai toaùn haïng 32 bít vôùi nhau.
+ Pheùp toaùn or (|): or caùc bít cuûa hai toaùn haïng 32 bít vôùi nhau.
+ Pheùp toaùn xor (^): xor caùc bít cuûa hai toaùn haïng 32 bít vôùi nhau.
+ Pheùp toaùn coäng (+): coäng modulo 232 hai toaùn haïng 32 bít vôùi nhau.
+ Pheùp toaùn dòch traùi voøng (w << s): dòch traùi voøng w (32 bít) vôùi s bít.
* Böôùc 4: xuaát (output). Taát caû khoái 512 bít L ñaõ ñöôïc xöû lyù thì ñaàu ra ôû giai ñoaïn thöù L laø message_digest 128 bít.
Coù theå toùm taét hoaït ñoäng cuûa MD5 nhö sau:
MD0 = IV
MDq+1 = MDq + fI(Yq , fH(Yq , fG(Yq ,fF(Yq ,MDq))))
MD = MDL-1
Trong ñoù:
+ IV: giaù trò khôûi taïo cuûa boä ñeäm ABCD ñöôïc xaùc ñònh trong böôùc 2.
+ Yq: khoái message 512 bít thöù q.
+ L: soá khoái message (ñaõ ñöôïc padding).
+ MD: giaù trò message_digest cuoái cuøng.
Chöông2: Phaân boá vaø quaûn lyù khoùa
1. Toång quan veà maõ hoùa vaø moät soá khaùi nieäm:
- Trong moät maïng lieân laïc döõ lieäu, giaû söû raèng moät user ôû moät terminal ñang lieân laïc vôùi moät chöông trình öùng duïng hay 1 user ôû moät terminal khaùc ôû trong cuøng moät vuøng hay ôû 1 vuøng khaùc, caùc user naøy duøng chung 1 khoùa chung (khoùa chính K) maø noù coù theå laø moät khoùa bí maät (khoùa rieâng tö = private key) ñöôïc cung caáp vaø ñöôïc chaáp nhaän tröôùc bôûi caùc user hoaëc moät khoùa ñöôïc caáp phaùt ñoäng bôûi heä thoáng vaø gaùn cho caùc user naøy, ñöôïc goïi laø khoùa maõ hoùa döõ lieäu hoaëc khoùa giaûi maõ döõ lieäu (hình 1.1).
- Moät khoùa chính ñöôïc duøng ñeå baûo maät lieân laïc ñöôïc goïi laø khoùa lieân laïc chính (primary communication key = KC). Khoùa maõ hoùa döõ lieäu chæ coù taùc duïng trong khoaûng thôøi gian cuûa moät phieân lieân laïc (communication session) vaø ñöôïc goïi laø khoùa phieân lieân laïc (session key = KS).
- Ñoái vôùi baûo maät taäp tin, khoùa maõ hoùa döõ lieäu duøng ñeå baûo veä taâp tin ñöôïc goïi laø khoùa taäp tin KF (file key). Khoùa taäp tin naøy ñöôïc taïo bôûi user cuoái cuøng hoaëc bôûi heä thoáng . Taäp tin ñaõ maõ hoùa coù theå ñöôïc giaûi maõ ôû moät terminal hoaëc moät host baát kyø naøo coù chöùa saün khoùa KF naøy.
- Khoùa phuï (secondary key = KN) trong ñoù N bieåu dieãn nuùt laø moät loaïi khoùa maõ hoùa khoùa ñöôïc duøng ñeå baûo veä caùc khoùa chính. Khi moät khoùa phuï ñöôïc duøng ñeå baûo veä khoùa trong moâi tröôøng lieân laïc thì ñöôïc goïi laø khoùa lieân laïc phuï (secondary communication key = KNC), coøn khi aùp duïng trong moâi tröôøng cô sôû döõ lieäu thì noù ñöôïc goïi laø khoùa taäp tin phuï (secondary file key = KNF).
- Trong moät moâi tröôøng lieân laïc, moät khoùa chính chæ toàn taïi trong khoaûng thôøi gian hai user cuoái cuøng trao ñoåi döõ lieäu vôùi nhau. Thoâng thöôøng khoùa seõ toàn taïi trong khoaûng vaøi phuùt hoaëc vaøi giôø ít khi toàn taïi hôn moät ngaøy. Ngöôïc laïi moät khoùa chính ñöôïc duøng ñeå baûo veä döõ lieäu löu tröõ coù theå toàn taïi trong khoaûng vaøi naêm hoaëc trong suoát thôøi gian maø taäp tin ñöôïc löu giöõ. Coøn khoùa phuï thoâng thöôøng ñöôïc ñöa vaøo trong heä thoáng luùc coù yeâu caàu caøi ñaët thoâng qua boä taïo khoùa, caùc khoùa phuï ñöôïc löu giöõ laâu daøi (vaøi thaùng hoaëc vaøi naêm) vaø khoâng ñöôïc thay ñoåi.
- Ñoái vôùi baûo maät lieân laïc, caùc khoùa phieân lieân laïc ñöôïc taïo ra ôû host vaø sau ñoù ñöôïc truyeàn ñeán moät nuùt nhaän (terminal hoaëc host) thoâng qua moät maïng lieân laïc (giaû söû laø khoâng ñöôïc baûo maät). Khoùa phieân lieân laïc ñöôïc baûo maät baèng caùch maõ hoùa noù bôûi moät khoùa khaùc (khoùa maõ hoùa khoùa) maø ñöôïc caøi saün ôû nuùt nhaän. Moãi nuùt nhaän coù moät khoùa maõ hoùa khoùa duy nhaát. Do ñoù neáu khoùa naøy bò hoûng thì chæ aùnh höôûng ñeán söï baûo maät ôû taïi terminal naøy maø khoâng laøm aûnh höôûng ñeán söï baûo maät cuûa toaøn boä maïng.
- Trong moät heä thoáng rieâng bieät, moät taäp caùc khoùa maõ hoùa khoùa ñöôïc duøng ñeå maõ hoùa caùc khoùa phieân lieân laïc ñöôïc truyeàn töø host naøy ñeán host khaùc vaø moät taäp caùc khoùa maõ hoùa khoùa khaùc ñöôïc duøng ñeå maõ hoùa caùc khoùa phieân lieân laïc ñöôïc truyeàn töø host ñeán terminal. Vì vaäy moãi host phaûi chöùa khoùa maõ hoùa khoùa ñeán host vaø terminal maø noù lieân laïc ñeán (ñöôïc goïi laø khoùa chuû cuûa host = KM), trong khi moãi terminal chæ caàn chöùa moät khoùa maõ hoùa khoùa ñeán host maø noù lieân laïc (ñöôïc goïi laø khoùa chuû cuûa terminal = KTM).
- Heä maät maõ (crytographic facility) laø vuøng chöùa giaûi thuaät maät maõ (nhö laø DES) vaø moät boä nhôù coá ñònh ñeå chöùa caùc khoùa chuû (nhö laø KM, KTM ôû host hoaëc KTM ôû terminal). Noù chæ coù theå ñöôïc truy xuaát thoâng qua caùc giao tieáp hôïp phaùp. Vì moät soá löôïng lôùn caùc khoùa maõ hoùa ñöôïc duøng ôû boä xöû lyù cuûa host neân caàn phaûi coù caùc thuû tuïc töï ñoäng taïo ra vaø quaûn lyù caùc khoùa naøy. Boä taïo khoùa seõ taïo ra caùc khoùa maõ hoùa khoùa maø chuùng ñöôïc yeâu caàu bôûi host hoaëc coù theå ñöôïc chæ ñònh bôûi caùc user. Noù coù ñaëc quyeàn theâm vaøo, thay ñoåi vaø huûy boû caùc khoùa. Boä quaûn lyù khoùa coù nhieäm vuï maõ hoùa laïi moät khoùa töø vieäc maõ hoùa bôûi moät khoùa naøy thaønh vieäc maõ hoùa bôûi moät khoùa khaùc.
- Caùc nuùt maø ôû ñoù ñoøi hoûi maõ hoùa döõ lieäu thì phaûi chöùa caùc giaûi thuaät maõ hoùa gioáng nhau vaø moãi nuùt phaûi coù moät baûn sao cuûa cuøng moät khoùa maõ hoùa K (hình 1.2). Hai nuùt phaûi luoân luoân söû duïng moät khoùa maõ hoaù döõ lieäu chung ñeå cho pheùp lieân laïc baûo maät vôùi nhau, vieäc baûo maät seõ ñöôïc thöïc hieän toát hôn neáu caùc caëp nuùt lieân laïc söû duïng caùc khoùa maõ hoùa döõ lieäu khaùc nhau. Nhôø vaäy seõ giaûm toái thieåu hö hoûng neáu moät khoùa bò phaù hoûng.
(h1.3c)
- Ñeå baûo maät khi truyeàn thoâng thöôøng ngöôøi ta söû duïng caùc giaûi thuaät maõ hoùa ñoái xöùng (heä thoáng khoùa bí maät) vaø maõ hoùa baát ñoái xöùng (heä thoáng khoùa coâng khai). Heä thoáng khoùa coâng khai coù thuaän lôïi hôn heä thoáng khoùa bí maät laø keânh baûo maät khoâng caàn thieát phaûi chuyeån ñoåi khoùa bí maät, nhöng haàu heát caùc heä thoáng khoùa coâng khai ñeàu chaäm hôn nhieàu so vôùi caùc heä thoáng khoùa bí maät nhö laø DES. Vì vaäy trong thöïc teá heä thoáng khoùa bí maät vaãn thöôøng ñöôïc söû duïng ñeå maõ hoùa ñoaïn tin daøi nhöng phaûi giaûi quyeát baøi toaùn veà chuyeån ñoåi khoùa bí maät.
- Söï phaân boá khoùa (key distibution) ñöôïc xaùc ñònh bôûi cô cheá moät ngöôøi trong maïng choïn 1 khoùa bí maät vaø sau ñoù truyeàn noù tôùi moät hay nhieàu ngöôøi khaùc.
- Söï ñoàng yù khoùa (key agreement) bieåu thò bôûi moät giao thöùc giöõa hai hay nhieàu ngöôøi tham gia thieát laäp moät khoùa bí maät treân keânh truyeàn thoâng coâng khai.
- TA (Trusted Authority) coù nhieäm vuï laøm roû ñònh danh cuûa user, choïn vaø truyeàn khoùa tôùi user …
- Ñoái phuông bò ñoäng (passive adversary) nghóa laø hoaït ñoäng cuûa anh ta bò haïn cheá ñeå nghe troäm ñoaïn tin maø ñöôïc truyeàn treân keânh.
- Ñoái phöông chuû ñoäng (active adversary) coù theå thöïc hieän:
. Thay ñoåi ñoaïn tin maø haén quan saùt khi noù ñang döôïc truyeàn treân maïng.
. Löu ñoaïn tin cho vieäc söû duïng laïi ôû laàn sau.
. Coá gaéng giaû daïng laøm user khaùc trong maïng.
- Muïc tieâu cuûa ñoái phöông chuû ñoäng laø:
. Gaït user U vaø V chaáp nhaän 1 khoùa khoâng hôïp leä laø 1 khoùa hôïp leä (khoùa khoâng hôïp leä coù theå laø 1 khoùa cuõ ñaõ heát haïn hay 1 khoùa ñöôïc choïn bôûi ñoái phöông).
. Laøm cho U vaø V tin raèng hoï ñaõ ñöôïc chuyeån ñoåi 1 khoùa baèng 1 khoùa khaùc trong khi hoï khoâng coù.
- Muïc tieâu cuûa söï phaân boá khoùa vaø ñoàng yù khoùa laø ôû cuoái moãi giao thöùc caû hai ñoái taùc ñeàu coù cuøng khoùa K vaø giaù trò cuûa K thì khoâng ñöôïc bieát bôûi baát kyø moät ngöôøi naøo khaùc (ngoaïi tröø TA coù khaû naêng).
- Söï tieàn phaân boá khoùa (key predistribution): cho moãi caëp user {U,V}, TA choïn moät khoùa ngaãu nhieân KU,V = KV,U vaø truyeàn noù tôùi U, V qua keânh bí maät (vieäc truyeàn khoùa khoâng xaûy ra treân maïng bôûi vì ñoä baûo maät cuûa maïng thì khoâng cao). Caùch tieáp caän naøy laø baûo maät khoâng ñieàu kieän nhöng noù ñoøi hoûi moät keânh baûo maät giöõa TA vaø moãi user trong maïng. Moãi user phaûi löu tröõ n-1 khoùa vaø TA caàn truyeàn n(n-1) khoùa moät caùch baûo maät. Trong moät maïng töông ñoái nhoû, ñieàu naøy coù theå trôû neân quaù toán keùm, vì theá noù khoâng phaûi laø giaûi phaùp thöïc teá.
- Moät caùch tieáp caän thöïc teá hôn laø söï phaân boá khoùa tröïc tuyeán bôûi TA. Trong sô ñoà nhö theá , TA hoaït ñoäng nhö laø moät server khoùa. TA tham gia khoùa bí maät KU vôùi moãi user trong maïng. Khi U muoán truyeàn thoâng vôùi V, U yeâu caàu moät khoùa phieân lieân laïc töø TA, TA taïo moät khoùa phieân lieân laïc K vaø gôûi noù (trong daïng maõ hoùa) cho U vaø V ñeå giaûi maõ. Heä thoáng ñöôïc bieát laø Kerberos.
- Giao thöùc ñoàng yù khoùa: U, V lieân keát choïn ra moät khoùa thoâng qua keânh truyeàn thoâng coâng khai. Caùc heä thoáng ñöôïc bieát laø Diffie_Hellman, MTI vaø Girault.
2. Phaân boá caùc khoùa baûo maät
2.1. Söï tieàn phaân boá khoùa:
- Ñoái vôùi maïng n user, TA phaûi taïo vaø truyeàn n(n-1) khoùa. Neáu n lôùn, giaûi phaùp naøy raát khoâng thöïc teá vì phaûi ñaûm baûo löôïng thoâng tin ñöôïc truyeàn moät caùch baûo maät vaø löôïng thoâng tin maø moãi user phaûi löu tröõ moät caùch bí maät (teân, khoùa bí maät cuûa n-1 user khaùc). Sô ñoà tieàn phaân boá khoùa Blom cho pheùp giaûm löôïng thoâng tin maø caàn ñeå truyeàn vaø löu tröõ, trong khi vaãn cho pheùp moãi caëp user U vaø V coù theå tính moät caùch ñoäc laäp khoùa bí maät KU,V.
2.1.1. Sô ñoà cuûa Blom:
- Giaû söû maïng coù n user, khoùa ñöôïc choïn thuoäc mieàn xaùc ñònh Zp vôùi p laø soá nguyeân toá (p >= n).
- K laø moät soá nguyeân : 1 =< K <= n-2 bieåu thò cho kích thöôùc lôùn nhaát choáng laïi söï lieân keát cuûa K user maø sô ñoà vaãn coøn baûo maät.
- TA seõ truyeàn K + 1 phaàn töû cuûa Zp tôùi moãi user qua keânh baûo maät (trong sô ñoà tieàn phaân boá khoùa cô baûn laø n-1). Moãi caëp user U vaø V seõ coù theå tính khoùa KU,V = KV,U. Ñieàu kieän baûo maät nhö sau: taäp nhieàu nhaát K user khoâng lieân keát töø {U,V} khoâng theå xaùc ñònh baát kyø thoâng tin veà KU,V.
- Xeùt tröôøng hôïp ñaët bieät cuûa sô ñoà Blom khi K=1 (hình beân): TA seõ truyeàn hai phaàn töû thuoäc Zp tôùi moãi user qua keânh baûo maät vaø baát kyø user rieâng leû W seõ khoâng theå xaùc ñònh baát kyø thoâng tin veà KU,V neáu W khaùc U, V.
- Ví duï: giaû söû coù ba user U, V, vaø W, p=17, caùc phaàn töû coâng khai laø rU=12, rV=7, rW=1. Giaû söû raèng TA choïn a=8, b=7, c=2. Khi ñoù:
f(x,y) = 8 + 7(x+y) + 2xy
gU(x) = 7 + 14x
gV(x) = 6 + 4x
gW(x) =15 + 9x
KU,V = 3, KU,W = 4, KV,W = 10
. U tính KU,V nhö sau: KU,V = gU(rV) = 7 + 14*7 mod 17 = 3
. V tính KV,U nhö sau: KV,U = gV(rU) = 6 + 4*12 mod 17 = 3
Sô ñoà phaân boá khoùa cuûa Blom (K=1)
Soá nguyeân toá p ñöôïc choïn coâng khai vaø cho moãi user U, moät phaàn töû rU thuoäc Zp ñöôïc choïn coâng khai. Caùc phaàn töû rU phaûi khaùc bieät nhau.
TA choïn ba phaàn töû ngaãu nhieân a, b, c thuoäc Zp (khoâng caàn khaùc bieät) vaø tính:
f(x,y) = a + b(x+y) + cxy mod p
Ñoái vôùi moãi user U, TA tính
gU(x) = f(x,rU) mod p
Vaø truyeàn gU(x) tôùi user U qua keânh baûo maät. Vì gU(x) laø
haøm tuyeán tính theo x neân coù theå ñöôïc ghi nhö sau:
gU(x) = aU + bUx
Vôùi aU = a + brU mod p
bU = b + crU mod p
Neáu U vaø V muoán truyeàn thoâng thì chuùng söû duïng khoùa
KU,V = KV,U = f(rU,rV) = a + b(rU + rV) + crUrV mod p
Vôùi U tính KU,V = f(rU, rV) = gU(rV)
V tính KV,U = f(rU, rV) = gV(rU)
- Khi coù söï lieân keát cuûa hai user {W, X} thì coù theå xaùc ñònh baát kyø khoùa KU,V maø {W, X} khaùc {U, V}. Bôûi vì W vaø X cuøng bieát:
aW = a + brW bW = b + crW
aX = a + brX bX = b + crX
Vôùi 4 phöông trình 3 aån treân ta coù theå deã daøng tính a, b, c. Töø ñoù tính ñöôïc khoùa KU,V.
- Ñeå taïo sô ñoà vaãn coøn baûo maät choáng laïi söï lieân keát cuûa K user, TA seõ söû duïng haøm f(x,y) coù daïng :
k
k
i=0 j=0
f(x,y) = å å ai,j xi yj mod p (ai,j thuoäc Zp vaø ai,j = aj,i )
2.1.2. Diffie-Hellman:
Diffie_Hellman
Soá nguyeân toá p vaø phaàn töû ñôn giaûn a thuoäc Zp ñöôïc laøm coâng khai.
V tính
KU,V = aauav mod p = bU av mod p
Söû duïng giaù trò coâng khai bU töø söï chöùng thöïc cuûa U, cuøng vôùi giaù trò baûo
maät aV cuûa rieâng mình.
U tính
KU,V = aauav mod p = bV au mod p
Söû duïng giaù trò coâng khai bV töø söï chöùng thöïc cuûa V, cuøng vôùi giaù trò baûo
maät aU cuûa rieâng mình.
- Sô ñoà tieàn phaân boá khoùa naøy cung caáp baøi toaùn Diffie-Hellman quan heä vôùi baøi toaùn Discrete Logarithm laø khoâng theå beû gaõy.
- Sô ñoà ñöôïc xeùt treân Zp, vôùi p laø soá nguyeân toá, a laø phaàn töû ñôn giaûn cuûa Zp , giaù trò cuûa p vaø a laø coâng khai vôùi moïi ngöôøi trong maïng, ID(U) seõ bieåu thò thoâng tin ñònh danh nhaát ñònh cho moãi user trong maïng (ví duï: teân, ñòa chæ email, soá ñieän thoaïi hay caùc thoâng tin thích hôïp khaùc). Moãi user U coù moät muõ baûo maät aU (0 <= aU <= p-2) (TA khoâng bieát giaù trò naøy) vaø giaù trò coâng khai töông öùng: bU = aau mod p.
- TA seõ coù moät sô ñoà chöõ kyù vôùi giaûi thuaät laøm roû (coâng khai) verTA vaø giaûi thuaät chöõ kyù baûo maät sigTA.
- Moãi user U khi tham gia maïng seõ coù söï chöùng thöïc:
C(U) = (ID(U), bU, sigTA(ID(U), bU))
Söï chöùng thöïc naøy coù theå ñöôïc löu tröõ trong cô sôû döõ lieäu coâng khai hay moãi user coù theå löu tröõ söï chöùng thöïc cuûa rieâng mình. Chöõ kyù cuûa TA treân söï chöùng thöïc cho pheùp baát kyø ngöôøi naøo trong maïng laøm roû thoâng tin maø noù chöùa.
Thaät deã daøng cho user U vaø V ñeå tính khoùa:
KU,V = a auav mod p
Ví duï: p = 25307, a = 2
. Giaû söû U choïn aU = 3578 vaø tính
bU = a au mod p = 23578 mod 25307 = 6113
Sau ñoù U ñaët bU vaøo trong söï chöùng thöïc cuûa mình.
. Giaû söû V choïn aV = 19956 vaø tính
bV = a av mod p = 219956 mod 25307 = 7984
Sau ñoù V ñaët bV vaøo trong söï chöùng thöïc cuûa mình.
. Giôø ñaây U vaø V coù theå tính khoùa:
KU,V = bVau mod p = bUav mod p
= 79843578 mod 25307 = 611319956 mod 25307
= 3694
- Nhôø coù chöõ kyù cuûa TA treân söï chöùng thöïc cuûa user neân ngaên caûn moät caùch hieäu quaû söï xaâm nhaäp cuûa user W khaùc.
Caâu hoûi ñaët ra laø W coù theå tính KU,V neáu W khaùc U, V hay khoâng? Hoaëc neáu W bieát bU, bV thì noù coù theå xaùc ñònh KU,V hay khoâng? Baøi toaùn naøy ñöôïc goïi laø baøi toaùn Diffie_Hellman.
Baøi toaùn Diffie_Hellman
I = (p, a, b, g ) trong ñoù p laø soá nguyeân toá, a thuoäc Zp* laø phaàn töû
ñôn giaûn vaø b, g thuoäc Zp*.
Muïc tieâu : tính blog ag mod p (=glog ab mod p)
Sô ñoà tieàn phaân boá khoùa Diffie_Hellman laø baûo maät choáng laïi ñoái phöông bò ñoäng neáu vaø chæ neáu baøi toaùn Diffie_Hellman laø khoù giaûi ra. Tuy nhieân vieäc phoûng ñoaùn khoâng chöùng minh raèng baát kyø giaûi thuaät maø giaûi baøi toaùn Diffie_Hellman cuõng coù theå ñöôïc söû duïng ñeå giaûi baøi toaùn Discrete Log (gioáng nhö trong giaûi thuaät RSA , vieäc beû gaõy RSA thì töông ñöông vôùi vieäc phaân tích thöøa soá).
2.2. Heä phaân boá khoùa Kerberos
- Do vaán ñeà khoâng an toaøn khi söû duïng cuøng moät khoùa trong moät thôøi gian daøi, cho neân thöôøng söû duïng moät phöông phaùp tröïc tuyeán thích hôïp hôn maø trong ñoù khoùa lieân laïc môùi ñöôïc taïo ra cho moãi caëp user muoán truyeàn thoâng (tính chaát laøm töôi khoùa).
- Neáu söï phaân boá khoùa tröïc tuyeán ñöôïc söû duïng thì khoâng caàn thieát cho baát kyø user trong maïng phaûi löu tröõ khoùa ñeå truyeàn thoâng vôùi user khaùc (moãi user seõ tham gia moät khoùa vôùi TA). Caùc khoùa phieân lieân laïc seõ ñöôïc truyeàn theo yeâu caàu cuûa TA.
- Kerberos laø moät heä thoáng phuïc vuï khoùa phoå bieán döïa treân heä maät maõ khoùa bí maät (khoâng döïa vaøo maõ hoùa khoùa coâng khai). Moãi user U tham gia moät khoùa bí maät (DES) KU vôùi TA, trong haàu heát caùc version cuûa Kerberos, taát caû ñoaïn tin khi truyeàn ñöôïc maõ hoùa söû duïng kieåu CBC (Cipher Block Chain).
- Khi coù yeâu caàu veà khoùa phieân lieân laïc ñöôïc gôûi tôùi TA, TA seõ taïo moät khoùa phieân lieân laïc ngaãu nhieân K. TA seõ ghi thôøi gian maø taïi ñoù yeâu caàu ñöôïc thöïc hieängoïi laø thôøi gian timestamp T vaø moâ taû khoaûng thôøi gian soáng L maø khoùa K coøn hôïp leä (töø T tôùi T+L). Taát caû caùc thoâng tin naøy ñöôïc maõ hoùa vaø ñöôïc truyeàn tôùi U vaø V. Giao thöùc truyeàn khoùa phieân lieân laïc nhö sau:
U yeâu caàu TA cho moät khoùa phieân lieân laïc ñeå truyeàn thoâng vôùi V.
TA choïn moät khoùa phieân lieân laïc ngaãu nhieân K, timestamp T vaø L.
TA tính: m1 = eKu (K, ID(V), T, L) vaø m2 = eKv (K, ID(U), T, L) vaø gôûi m1, m2 tôùi U.
U söû duïng haøm giaûi maõ dKu ñeå tính K, T, L vaø ID(V) töø m1.
Sau ñoù tính: m3 = eK (ID(U), T) Vaø gôûi m3 tôùi V cuøng vôùi m2 maø ñaõ nhaän töø TA.
U söû duïng haøm giaûi maõ dKv ñeå tính K, T, L vaø ID(U) töø m2.
Sau ñoù söû duïng dK ñeå tính T vaø ID(U) töø m3, roài kieåm tra xem hai giaù trò
Cuûa T vaø hai giaù trò cuûa ID(U) coù gioáng nhau khoâng? Neáu thoûa thì tính:
m4 = eK (T+1). Vaø gôûi m4 tôùi U.
U giaûi maõ m4 söû duïng dK vaø laøm roû raèng keát quaû laø T+1.
Neáu ñuùng thì K ñaõ ñöôïc truyeàn thaønh coâng tôùi V.
Trong ñoù:
. KU, KV : khoùa tham gia cuûa U vaø V vôùi TA.
. U (V) söû duïng cuûa mình ñeå giaûi maõ eKu (eKv).
. m1, m2 : cung caáp söï baûo maät trong khi truyeàn khoùa K.
. m3, m4 : cung caáp söï xaùc nhaän khoùa.
- Muïc ñích cuûa T vaø L laø nhaèm ngaên caûn ñoái phöông chuû ñoäng töø vieäc löu tröõ ñoaïn tin cuõ cho vieäc taùi truyeàn ôû laàn sau. Caùc khoùa seõ khoâng ñöôc coi laø hôïp leä moät khi chuùng ñaõ heát haïn.
- Moät trong nhöõng nhöôïc ñieåm cuûa Kerberos laø taát caû user trong maïng phaûi coù ñoàng hoà ñoàng boä bôûi vì thôøi gian hieän taïi ñöôïc söû duïng ñeå xaùc ñònh khi naøo moät khoùa phieân lieân laïc ñaõ cho laø hôïp leä. Trong thöïc teá raát khoù khaên ñeå cung caáp suï ñoàng boä hoaøn haûo bôûi vì thöôøng trong maùy söï thay ñoåi moät löôïng thôøi gian phaûi ñöôïc cho pheùp.
2.3. Trao ñoåi khoùa Diffie_Hellman:
Neáu chuùng ta khoâng muoán söû duïng server khoùa tröïc tuyeán thì söû duïng giao thöùc ñoàng yù khoùa ñeå trao ñoåi caùc khoùa bí maät:
U choïn aU ngaãu nhieân : 0 <= aU <= p-2
U tính a au mod p vaø gôûi noù tôùi V
V choïn aV ngaãu nhieân : 0 <= aV <= p-2
V tính a av mod p vaø gôûi noù tôùi U
U tính K = (a av)au mod p
V tính K = (a au)av mod p
Giao thöùc naøy raát gioáng söï tieàn phaân boá khoùa Diffie_Hellman, noù chæ khaùc ôû choã aU vaø aV ñöôïc choïn moãi laàn giao thöùc ñöôïc chaïy thay vì laø coá ñònh. Caû U vaø V ñeàu ñaûm baûo vieäc laøm töôi khoùa bôûi vì khoùa phieân lieân laïc phuï thuoäc vaøo caû hai soá muõ ngaãu nhieân aU vaø aV.
2.3.1. Giao thöùc traïm tôùi traïm (station_to _station):
fig15
Giao thöùc naøy coù theå bò taán coâng bôûi moät ñoái pjöông chuû ñoäng W, W seõ chaën laïi ñoaïn tin giöõa U vaø V vaø thay theá baèng ñoaïn tin cuûa rieâng mình:
Fig16
Ôû cuoái giao thöùc U thieát laäp khoùa bí maät aau a’v vôùi W vaøV thieát laäp khoùa bí maät aa’u av vôùi W. Khi U thöû maõ hoùa ñoaïn tin gôûi tôùi V, W seõ coù theå giaûi maõ noù nhöng V thì khoâng laøm ñöôïc. Töông töï khi V gôûi ñoaïn tin tôùi U. Ñeå traùnh söï xaâm nhaäp cuûa W thì U vaø V neân thieát laäp vieäc ñònh danh laãn nhau cuøng thôøi ñieåm maø khoùa ñöôc thieát laäp. Giao thöùc nhö theá ñöôïc goïi laø söï ñoàng yù khoùa coù chöùng thöïc laø moät daïng moâ phoûng cuûa söï trao ñoåi khoùa Diffie_Hellman. Giao thöùc giaû thieát moät soá nguyeân toá p vaø moät phaàn töû cô baûn a ñöôïc bieát moät caùch coâng khai. Moãi user U seõ coù moät sô ñoà chöõ kyù vôùi giaûi thuaät laøm roû verU vaø giaûi thuaät kyù teân sigU. TA cuõng coù moät sô ñoà chöõ kyù vôùi giaûi thuaät laøm roû coâng khai verTA. Moãi user U coù moät söï chöùng thöïc:
C(U) = (ID(U), verU, sigTA(ID(U), verU))
Vôùi ID(U) laø thoâng tin ñònh danh cho U.
Giao thöùc station_to_station coù chöùng thöïc cuûa Diffie, Van Oorschot vaø Wiener nhö sau:
U choïn moät soá ngaãu nhieân aU : 0 <= aU <= p-2
U tính aau mod p vaø gôûi noù tôùi V
V choïn moät soá ngaãu nhieân aV : 0 <= aV <= p-2
V tính: aav mod p
Vaø K = (aau)av mod p
yV = sigV (aav, aau)
vaø gôûi (C(V), aav, yV ) tôùi U
U tính K = (aav)au mod p
Vaø laøm roû yV söû duïng verV, laøm roû C(V) söû duïng verTA.
U tính yU = sigU (aau, aav)
Vaø gôûi (C(U), yU ) tôùi V.
7. V laøm roû yU söû duïng verU vaø laøm roû C(U) söû duïng verTA
khoâng theå tính chöõ kyù cuûa V treân (aa’v, aau) bôûi vì V khoâng bieát giaûi thuaät kyù teân sigV, neân W khoâng theå thay sigV (aav, aa’u) baèng sigV (aa’v, aau). Töông töï W khoâng theå thay sigU (aau, aa’v) baèng sigU (aa’u, aav) bôûi vì W khoâng bieát giaûi thuaät kyù teân cuûa U (sigU).
Toùm laïi nhôø söû duïng chöõ kyù maø coù theå traùnh ñöôïc söï taán coâng cuûa W.
- Giao thöùc naøy khoâng cung caáp söï xaùc nhaän khoùa. Thaät deã daøng ñeå moâ taû ñieàu ñoù baèng caùch:
yV = eK(sigV (aav, aau)) trong böôùc 4
Vaø yU = eK (sigU (aau, aav)) trong böôùc 6.
2.3.2. Giao thöùc ñoàng yù khoùa MTI (Matsumoto, Takashima, Imai):
- Giao thöùc naøy khoâng yeâu caàu U vaø V tính baát kyø chöõ kyù naøo. Noù laø giao thöùc hai chuyeán (pass) bôûi vì coù söï truyeàn thoâng hai phía giöõa U vaø V (trong giao thöùc station_to_station coù 3 pass). Vieäc thieát laäp giao thöùc naøy thì töông töï nhö söï tieàn phaân boá khoùa Diffie_Hellman:
U choïn rU ngaãu nhieân (0 <= rU <= p-2) vaø tính sU = aru mod p
U gôûi (C(U), sU) tôùi V
V choïn rV ngaãu nhieân (0 <= rV <= p-2) vaø tính sV = arv mod p
V gôûi (C(V), sV) tôùi U
U tính:
K = sVaubVru mod p = arvau + ruav mod p (bV ñöôïc laáy töø C(V))
Vaø V tính:
K = sUavbUrv mod p = aruav + rvau mod p (bU ñöôïc laáy töø C(U))
Trong ñoù:
. p, a: ñöôïc bieát coâng khai.
. Moãi user U coù xaâu ID(U), soá muõ bí maät aU (0 <=aU<=p-2), vaø giaù trò coâng khai töông öùng: bU = aau mod p. Töông töï ñoái vôùi V.
. TA coù sô ñoà chöõ kyù vôùi giaûi thuaät laøm roû (coâng khai) verTA vaø giaûi thuaät chöõ kyù baûo maät sigTA.
. Moãi user U coù söï chöùng thöïc :
C(U) = (ID(U), bU, sigTA(ID(U), bU)
Töông töï cho V.
. Caû U vaø V coù cuøng khoùa:
K = aruav + rvau mod p.
- Ví duï: p = 27803, a = 5 ñöôïc bieát coâng khai
. Giaû thieát U choïn aU = 21131, V choïn aV = 17555. Khi ñoù:
bU = 521131 mod 27803 = 21420
bV = 517555 mod 27803 = 17100
(bU, bV ñöôïc ñaët treân söï chöùng thöïc cuûa U vaø V)
. Giaû söû U choïn rU = 169, V choïn rV = 23456. Khi ñoù:
sU = 5169 mod 27803 = 6268
sV = 523456 mod 27803 = 26759
U seõ gôûi sU tôùi V vaø V seõ gôûi sV tôùi U.
. U tính khoùa:
KU,V = sVaubVru mod p
= 267592113117100169 mod 27803 = 21600
. V tính khoùa:
KU,V = sUavbUrv mod p
= 6268175552142023456 mod 27803 = 21600
Söï baûo maät cuûa giao thöùc MTI choáng laïi ñoái phöông bò ñoäng cuõng töông töï nhö baøi toaùn Diffie_Hellman. Khi coù söï xaâm nhaäp cuûa ñoái phöông chuû ñoäng W thì U vaø V seõ tính nhöõng khoùa khaùc nhau:
. U tính khoùa: K = aruav + r’vau mod p.
. V tính khoùa: K = ar’uav + rvau mod p.
- Maëc duø U vaø V ñaõ tính ñöôïc nhöõng khoùa khaùc nhau (dó nhieân laø khoâng coù lôïi cho hoï) thì nhöõng khoùa naøy cuõng khoâng ñöôïc tính bôûi W (vì W khoâng bieát caùc soá muõ bí maät aU, aV). Ñaây laø kieåu chöùng thöïc khoùa töôøng minh.
2.3.3. Söï ñoàng yù khoùa söû duïng chöùng thöïc baûn thaân (Girault):
- Khoâng yeâu caàu vieâc chöùng thöïc, giaù trò cuûa khoùa coâng khai vaø ñònh danh cuûa chuû noù thì ñöôïc chöùng thöïc moät caùch töôøng minh tôùi moãi caùi khaùc.
- Sô ñoà cuûa Girault keát hôïp nhöõng ñaët ñieåm cuûa giaûi thuaät RSA vaø giaûi thuaät rôøi raïc. Giaû söû n =pq, p = 2p1 + 1, q = 2q1 + 1 vaø p, q, p1, q1 laø caùc soá nguyeân toá lôùn (baûo maät). Giaù trò n chæ ñöôïc bieát bôûi TA. TA choïn moät soá muõ maõ hoùa RSA e (coâng khai) vaø soá muõ giaûi maõ d (baûo maät) maø d = e-1 mod F(n).
. Moãi user U coù moät xaâu ID(U) vaø ñöa ra moät khoùa coâng khai chöùng thöïc baûn thaân pU töø TA:
U choïn moät soá muõ baûo maät aU vaø tính:
bU = aau mod n
U gôûi aU vaø bU tôùi TA.
TA tính: pU = (bU – ID(U))d mod n.
TA gôûi pU tôùi U.
.
Coù theå tính bU töø pU nhö sau:
bU = pUe + ID(U) mod n
Giao thöùc ñoàng yù khoùa Girault:
U choïn rU ngaãu nhieân vaø tính:
sU = aru mod n
U gôûi ID(U), pU vaø sU tôùi V.
V choïn rV ngaãu nhieân vaø tính:
sV = arv mod n
V gôûi ID(V), pV vaø sV tôùi U.
U tính: K = sVau(pVe + ID(V))ru mod n
U tính: K = sUav(pUe + ID(U))rv mod n
ÔÛ cuoái giao thöùc U vaø V tính khoùa:
K = aruav + rvau mod n.
- Ví duï: p = 839, q = 863, a = 5.
. Khi ñoù: n = pq = 724057, F(n) = (p - 1)(q - 1) = 722356.
. TA choïn d = 125777 ® e = 84453 (RSA).
. Giaû söû U coù ID(U) = 500021 vaø aU = 111899 thì:
bU = 48889 vaø pU = 650704.
. Töông töï khi V coù ID(V) = 500022 vaø aV = 123456 thì:
bV = 111692 vaø pV = 683556.
. Giôø ñaây khi U vaø V muoán trao ñoåi khoùa thì:
U choïn rU = 56381 ® sU = 171007
V choïn rV = 356935 ® sV = 320688
. Caû U laãn V ñeàu tính cuøng khoùa: K = 42869.
- Khi ñoái phöông W muoán giaû daïng U thì W baét ñaàu vôùi ID(U) vaø giaù trò giaû b’U. Khi ñoù khoâng coù caùch naøo ñeå W tính soá muõ a’U töông öùng vôùi b’U (neáu baøi toaùn Discrete Log khoâng bò beû gaõy). Khoâng coù a’U thì vieäc tính toaùn khoùa khoâng theå ñöôïc thöïc hieän bôûi W.
- Khi W ngaên caûn U vaø V töø vieäc tính toaùn khoùa chung (W ôû giöõa ñöôøng truyeàn U vaø V) thì W cuõng khoâng theå sao laïi vieäc tính toaùn cuûa U hoaëc V. Vì vaäy sô ñoà naøy cung caáp söï chöùng thöïc töôøng minh nhö trong giao thöùc MTI.
- Taïi sao U ñöôïc yeâu caàu cung caáp giaù trò aU tôùi TA trong khi TA coù theå tính pU tröïc tieáp töø bU khoâng caàn bieát aU?. Lí do laø ñeå ñaûm baûo tính baûo maät thì giaù trò aU phaûi ñöôïc bieát tröôùc khi TA tính pU cho U (TA tính bU döïa vaøo aU, sau ñoù so saùnh vôùi bU nhaän töø U: neáu gioáng nhau thì chaáp nhaän, ngöôïc laïi thì huûy), giaû söû W choïn moät giaù trò giaû a’U vaø tính giaù trò töông öùng: b’U = aa’u mod n.
® p’U = (b’U – ID(U))d mod n
. W seõ tính b’W = b’U – ID(U) + ID(W) vaø gôûi b’W , ID(W) tôùi TA. Giaû söû TA tính vaø gôûi khoùa bí maät p’W tôùi W: p’W = (b’W – ID(W))d mod n.
. Vì b’W – ID(W) = b’U – ID(U) mod n, neân p’W = p’U.
. Giaû söû moät thôøi gian sau, U vaø V thöïc thi giao thöùc vaø W thay theá thoâng tin nhö sau:
. V seõ tính khoùa : K’ = ar’uav + rva’u mod n = KW.
. U seõ tính khoùa : K = aruav + rvau mod n.
Cho neân W vaø V seõ tham gia cuøng moät khoùa, trong khi V nghó laø mình ñang tham gia khoùa vôùi U. Vì vaäy W seõ coù theå giaûi maõ ñoaïn tin gôûi töø V tôùi U.
2.4. Phaân boá khoùa coâng khai
Trong heä thoáng maät maõ khoâng ñoái xöùng (heä thoáng khoùa coâng khai), baát kyø moät thöïc theå naøo cuõng coù theå taïo ra moät caëp khoùa cho rieâng mình, trong ñoù moät khoùa laø coâng khai, ñöôïc gôûi ñi treân keânh truyeàn thoâng (khoâng baûo maät), khoùa coøn laïi (khoùa bí maät) ñöôïc baûo maät taïi nôi taïo ra noù. Khoù khaên lôùn nhaát trong heä thoáng khoùa coâng khai laø söï phaân boá baûo maät caùc khoùa coâng khai: giaû söû user A nhaän ñöôïc khoùa coâng khai cuûa user B, vaán ñeà laø laøm sao coù theå ñaûm baûo khoùa coâng khai ñoù laø cuûa B trong khi moät user khaùc coù theå giaû daïng B. Do ñoù ñoøi hoûi khoùa coâng khai phaûi ñöôïc chöùng thöïc. Moät phöông phaùp giaûi quyeát ñôn giaûn nhaát laø löu tröõ taát caû caùc khoùa coâng khai trong moät thö muïc khoùa. Thö muïc naøy coù nhieäm vuï baûo trì, caäp nhaät vaø phaân phoái taát caû caùc khoùa coâng khai ñöôïc söû duïng treân maïng.
3. Quaûn lyù khoùa:
3.1. Quaûn lyù caùc khoùa coâng khai:
Giaû söû user A muoán chöùa khoùa coâng khai tin caäy cuûa user B (vì coù theå user C giaû danh B ñeå ñöa khoùa coâng khai cho A) thì nhöõng caùch tieáp caän sau coù theå ñöôïc söû duïng:
- B chöùa khoùa coâng khai treân ñóa meàm vaø trao noù cho A, sau ñoù A coù theå naïp khoùa vaøo heä thoáng cuûa A töø ñóa meàm, phöông phaùp naøy raát baûo maät nhöng thöïc teá noù bò giôùi haïn do baát tieän.
- Laøm roû qua ñieän thoaïi: A goïi cho B vaø yeâu caàu B cho bieát khoùa daïng cô soá 64. Thöïc teá hôn, B coù theå truyeàn khoùa thoâng qua email tôùi A, A coù theå taïo message digest 128 bit cuûa khoùa vaø trình baøy noù ôû daïng cô soá 64, sau ñoù A coù theå goïi B vaø yeâu caàu B cho bieát khoùa daïng cô soá 64. A so saùnh hai khoùa treân neáu töông xöùng thì xem nhö khoùa coâng khai ñoù laø hôïp leä.
- Thoâng qua caù nhaân tin caäy D: D taïo chöùng thöïc chöõ kyù goàm coù khoùa coâng khai cuûa B, thôøi gian taïo khoùa vaø chu kyø hôïp leä cuûa khoùa, D taïo message digest cuûa chöùng thöïc naøy, maõ hoùa noù baèng khoùa bí maät cuûa mình vaø gôûi noù tôùi A. Sau ñoù A coù theå giaûi maõ ñeå laøm roû khoùa coâng khai cuûa B.
- Thoâng qua moät CA (Certifying Authority)
3.2. Quaûn lyù caùc khoùa bí maät:
Bôûi vì nhieàu ngöôøi ñeàu bieát caùc giaûi thuaät baûo maät, do ñoù möùc ñoä baûo veä ñöôïc cung caáp bôûi heä thoáng maät maõ phuï thuoäc vaøo caùc khoùa maõ hoùa ñöôïc löu giöõ bí maät nhö theá naøo. Nhö vaäy muïc tieâu cuûa quaûn lyù khoùa laø baûo ñaûm caùc khoùa maõ hoùa khoâng bao giôø ôû daïng roõ khi chuùng ôû beân ngoaøi heä maät maõ, ngoaïi tröø döôùi caùc ñieàu kieän maät trong khi caùc khoùa ñöôïc khôûi taïo laàn ñaàu tieân, ñöôïc phaân boá vaø ñöôïc caøi ñaët hoaëc khi chuùng ñöôïc löu tröõ hoaëc phuïc hoài nhaèm ñaûm baûo an toaøn khi coù hö hoûng.
- Trong moät heä thoáng baûo maät khoâng ñoái xöùng, chæ caàn baûo maät khoùa bí maät taïi nôi ñaõ taïo ra noù. Khi caëp khoùa coâng khai/baûo maät bò loä thì coù theå tính toaùn moät caëp khoùa khaùc moät caùch deã daøng.
- Trong moät heä thoáng baûo maät ñoái xöùng, coù nhieàu kieåu khoùa bí maät khaùc nhau, song coù theå xeáp chung vaøo hai lôùp chính:
. Caùc khoùa duøng tröïc tieáp ñeå maõ hoùa caùc ñoaïn tin.
. Caùc khoùa duøng ñeå maõ hoùa caùc khoùa khaùc, chaúng haïn nhö caùc khoùa KM (Host Master Key), KMT (Terminal Master Key) maø töông öùng chuùng ñöôïc ñaët trong maùy host vaø maùy terminal. Khi caùc khoùa naøy bò loä thì seõ aûnh höôûng ñeán tính baûo maät toaøn boä cuûa maùy host hoaëc cuûa maùy terminal. Coøn khi caùc khoùa naøy bò huûy thì nhöõng khoùa maø ñöôïc maõ hoùa bôûi chuùng seõ khoâng coøn giaù trò (vieäc giaûi maõ caùc ñoaïn tin ñaõ maõ hoùa seõ cho caùc ñoaïn tin khaùc vôùi ñoaïn tin goác). Giaù trò cuûa caùc khoùa naøy ñöôïc coá ñònh trong moät khoaûng thôøi gian thöôøng thì khoaûng vaøi tuaàn hoaëc vaøi thaùng. Vì vaäy vieäc phaùt sinh vaø löu tröõ chuùng laø moät vaán ñeà quan troïng trong baûo maät. Trong thöïc teá “master key” ñöôïc choïn ngaãu nhieân trong soá caùc giaù trò coù theå cuûa vuøng khoùa. Sau khi choïn xong, khoùa ñöôïc ñöa vaøo heä maät maõ (cryptography facility) maø vaán ñeà bò loä thì raát khoù xaûy ra. Ngoaøi ra coù theå kieåm tra khoùa coù hôïp leä hay khoâng nhö sô ñoà sau (h3.1): maõ hoùa ñoaïn tin M baèng khoùa KM, sau ñoù caát EKM(M) vaø M vaøo boä nhôù, khi coù yeâu caàu kieåm tra tính xaùc thöïc cuûa KM thì M seõ ñöôïc laáy töø boä nhôù vaø maõ hoùa noù baèng khoùa KM ñang xeùt, keát quaû maõ hoùa seõ ñöôïc so saùnh vôùi EKM(M) coù trong boä nhôù: neáu gioáng nhau thì khoùa KM ñöôïc coi laø hôïp leä.
3.2.1. Baûo veä caùc khoùa “master key”:
- Bôûi vì terminal chæ quaûn lyù moät khoùa KMT (duøng chung vôùi host) neân caùc taùc vuï baûo maät cuûa terminal thì khoâng phöùc taïp so vôùi cuûa host, neân coù theå chöùa tröïc tieáp khoùa naøy trong vuøng chöùa khoùa chuû cuûa heä maät maõ. Do host phaûi quaûn lyù caùc hoaït ñoäng cuûa toaøn boä heä thoáng maät maõ neân noù phaûi quaûn lyù moät soá luôïng lôùn caùc khoùa chính vaø caùc khoùa phuï. Trong heä thoáng nhö vaäy terminal ñoùng vai troø thuï ñoäng baèng caùch ñaùp öùng cho caùc yeâu caàu ñöôïc thöïc hieän bôûi host, trong khi ñoù host ñoùng vai troø tích cöïc hôn baèng vieäc quaûn lyù vaø khôûi ñoäng caùc yeâu caàu.
- Quaù trình phuïc hoài moät khoùa phieân lieân laïc ôû terminal nhö sau: tröôùc tieân, khoùa KMT ñöôïc sao cheùp töø vuøng chöùa khoùa chuû ñeán vuøng chöùa khoùa laøm vieäc. Sau ñoù söû duïng KMT ñeå giaûi maõ EKMT(KS) nhaän töø host, thu ñöôïc khoùa phieân lieân laïc KS, khoùa naøy ñöôïc truyeàn ñeán vuøng chöùa khoùa laøm vieäc thay theá khoùa KMT. Töø ñaây terminal coù theå thöïc hieän caùc taùc vuï maõ hoùa söû duïng khoùa phieân lieân laïc KS.
- Baûo veä caùc khoùa KM cuûa host: thöôøng chuùng ñöôïc chöùa ôû beân trong heä maät maõ. Trong moät maïng coù nhieàu host, ñeå baûo maät toát thì khoùa KM ôû caùc host neân khaùc nhau. Ngoaøi vieäc caùc khoùa ñöôïc baûo veä baèng caùch chöùa chuùng trong heä maät maõ hoaëc maõ hoùa chuùng thì caàn phaûi kieåm soaùt vieäc söû duïng caùc khoùa naøy, nghóa laø chæ coù nhöõng ngöôøi söû duïng coù thaåm quyeàn môùi ñöôïc truy xuaát ñeán caùc khoùa caàn thieát.
3.2.2. Baûo veä caùc khoùa chính:
Coù theå baûo maät caùc khoùa chính baèng caùch chöùa chuùng (ôû daïng roû) trong moät vuøng nhôù maø noù chæ coù theå ñöôïc ñoïc bôûi heä maät maõ (vuøng nhôù ñöôïc baûo veä). Hoaëc maõ hoùa chuùng vaø kieåm tra vieäc söû duïng chuùng thoâng qua heä thoáng chuû (maõ hoùa theo khoùa KM: EKM(K)).
3.3. Caùc taùc vuï maät maõ cuûa heä thoáng chuû:
3.3.1. Baûo maät lieân laïc ñôn vuøng duøng caùc khoùa chính ñaõ ñöôïc taïo tröôùc:
- Caùc khoùa chính ñaõ ñöôïc taïo ra tröôùc laø caùc khoùa ñöôïc taïo ra döôùi caùc ñieàu kieän baûo maät thaønh moät nhoùm lôùn tröôùc khi chuùng ñöôïc söû duïng vaø ñöôïc chöùa beân trong heä thoáng ñeå söû duïng sau naøy. Heä thoáng maät maõ vôùi moät khoùa chuû KM0 cho pheùp maõ hoùa caùc khoùa chính KCi treân:
EKM0(KC1), EKM0(KC2), … , EKM0(KCn).
- Caùc taùc vuï maät maõ cô baûn ôû heä thoáng host laø: thieát laäp khoùa chuû (SMK), maõ hoùa theo khoùa chuû (EMK), maõ hoùa döõ lieäu (ECPH) vaø giaûi maõ döõ lieäu (DCPH):
. SMK: {KM0}
. EMK: {KC }® EKM0(KC)
. ECPH: {EKM0(KC), Data} ® EKC(Data)
. DCPH: {EKM0(KC), EKC(Data)} ® Data
- Nhöôïc ñieåm cuûa caùch tieáp caän naøy laø soá löôïng caùc khoùa lieân laïc chính caàn thieát cho heä thoáng maät maõ phaûi ñöôïc xaùc ñònh tröôùc vaø khoâng gian löu tröõ cho caùc khoùa naøy phaûi ñöôïc caáp phaùt bôûi heä thoáng host. Ñieàu naøy raát nguy hieåm bôûi vì ñoái phöông chæ caàn bieát KM0 laø coù theå bieát ñöôïc taát caû caùc khoùa chính.
3.3.2. Baûo maät lieân laïc ñôn vuøng duøng caùc khoùa chính ñaõ ñöôïc taïo ñoäng:
- Giaû söû KSi (i=1…n) laø caùc khoùa phieân lieân laïc ñöôïc taïo ra moät caùch ñoäng duøng ñeå maõ hoùa döõ lieäu. Vaø chuùng ñöôïc maõ hoùa theo KM0:
EKM0(KS1), EKM0(KS2), … , EKM0(KSn).
- Bôûi vì caùc khoùa phieân lieân laïc ñöôïc taïo ra döôùi daïng maõ hoùa neân khoâng theå giaûi maõ chuùng moät caùch tröïc tieáp theo khoùa chuû cuûa terminal (KMT). Do ñoù caàn phaûi coù moät taùc vuï maät maõ ñeå bieán ñoåi KS töø vieäc maõ hoùa theo KM0 thaønh maõ hoùa theo KMT nhö sau: ôû heä thoáng host caàn chöùa theâm khoùa KMT ñöôïc maõ hoùa theo KM0 (EKM0(KMT)) vaø khoùa KS ñöôïc maõ hoùa theo KMT (EKMT(KS)). Tuy nhieân khi ñoù seõ laøm loä caùc khoùa phieân lieân laïc bôûi vì coù theå duøng EKM0(KMT) vaø EKMT(KS) nhö laø caùc döõ lieäu nhaäp cho taùc vuï DCPH ñeå laøm roû KS:
DCPH: { EKM0(KMT), EKMT(KS)} ® KS
Ñieàu naøy vi phaïm yeâu caàu: “ khoâng theå phuïc hoài caùc khoùa ôû daïng roû khi ôû beân ngoaøi vuøng baûo maät vaät lyù, ví duï nhö heä maät maõ”. Ñeå khaéc phuïc, ta coù theå duøng theâm moät khoùa chuû KM1 (bieán ñoåi caùc bit thích hôïp cuûa KM0) ñeå maõ hoùa caùc khoùa KMT:
EKM1(KMT1), EKM1(KMT2), … , EKM1(KMTn).
- Caùch tieáp caän naøy caàn theâm moät taùc vuï maõ hoùa laïi töø khoùa chuû:
(RFMK): { EKM1(KMT), EKM0(KS)} ® EKMT(KS).
3.3.3. Baûo maät lieân laïc ñôn vuøng vaø baûo maät taäp tin duøng caùc khoùa chính ñaõ ñöôïc taïomoät caùch ñoäng:
- Giaû söû ta muoán baûo veä döõ lieäu ñöôïc löu tröõ gioáng nhö ñaõ baûo veä döõ lieäu ñöôïc truyeàn nghóa laø ta muoán söû duïng moät khoùa phieân lieân laïc ôû daïng EKM0(KS) nhö döõ lieäu nhaäp cho caùc taùc vuï maõ hoùa döõ lieäu vaø giaûi maõ döõ lieäu nhaèm muïc ñích taïo laäp vaø phuïc hoài caùc taäp tin döõ lieäu. Muoán vaäy thì EKM0(KS) phaûi ñöôïc löu laïi ñeå söû duïng sau naøy hoaëc ngöôïc laïi coù theå taïo laïi noù khi caàn thieát: (h3.3.3)
- Neáu EKM0(KS) ñöôïc löu ôû beân trong heä thoáng, ñaët bieät trong khoaûng thôøi gian daøi thì noù phaûi ñöôïc baûo veä bôûi moät phöông phaùp truy xuaát coù ñieàu khieån thích hôïp, bôûi vì neáu noù bò loä thì döõ lieäu seõ bò giaûi maõ. EKM0(KS) coù theå ñöôïc löu tröõ trong heä thoáng hay ñöôïc duøng nhö moät khoùa caù nhaân. Tuy nhieân khoùa chuû KM0 ñöôïc thay ñoåi theo ñònh kyø do ñoù ñoøi hoûi phaûi coù moät phöông phaùp ñeå phuïc hoài KS ôû daïng roû sao cho noù coù theå ñöôïc maõ hoùa laïi theo moät khoùa chuû môùi hoaëc ñeå dòch KS tröïc tieáp töø daïng maõ hoùa theo khoùa chuû cuõ sang daïng maõ hoùa theo khoùa chuû môùi. Trong caû hai tröôøng hôïp thuû tuïc seõ röôøm raø. Moät vaán ñeà khaùc laø khi caùc host trao ñoåi taäp tin vôùi nhau, ñoøi hoûi khoùa KM0 ôû caùc host phaûi gioáng nhau. Ñieàu naøy thì khoâng toát cho löôïc ñoà quaûn lyù khoùa. Ñeå khaéc phuïc thì KS neân ñöôïc maõ hoùa theo moät khoùa taäp tin phuï KNF (EKNF(KS)). Khi ñoù khoùa KNF seõ ñöôïc löu tröõ (maõ hoùa) nhö theá naøo?
. Neáu maõ hoùa KNF theo KM0 thì bò vi phaïm yeâu caàu bôûi vì:
DCPH: {EKM0(KNF), EKNF(KS)} ® KS
. Neáu maõ hoùa KNF theo KM1 thì coù theå phuïc hoài EKM0(KS) töø EKM1(KNF) vaø EKNF(KS) hoaëc töø EKM1(KMT) vaø EKMT(KS).
. Do ñoù KNF neân ñöôïc maõ hoùa theo moät khoùa chuû thöù ba KM2 (EKM2(KNF)). KM2 ñöôïc suy ra töø KM0 theo moät caùch thöùc töông töï nhö KM1 ñöôïc suy ra töø KM0.
- Trong baûo maät taäp tin thì KS chính laø KF, KF chæ duøng trong khoaûng thôøi gian soáng cuûa Taäp tin ñaõ ñöôïc maõ hoùa vaø KF ñöôïc maõ hoùa theo khoùa KNF (EKNF(KF)).- Caùch tieáp caän naøy coù theâm moät taùc vuï maõ hoùa laïi thaønh khoùa chuû (RTMK) nhö sau:RTMK: {EKM2(KNF), EKNF(KF)} ® EKM0(KF) .Toùm laïi ñeå baûo maät ôû heä thoáng host caàn phaûi coù ba khoùa chuû KM0, KM1, KM2 vaø caùc khoùa chính ñöôïc maõ hoùa döôùi daïng: EKM0(KS1), EKM0(KS2), … , EKM0(KSn). EKM1(KMT1), EKM1(KMT2), … , EKM1(KMTn).EKM2(KNF1), EKM2(KNF2), … , EKM2(KNFn). EKNF(KF1), EKNF(KF2), … , EKNF(KFn).
Chöông 3: Caùc Tieâu Chuaån
3.1. Tieâu chuaån maät maõ khoùa coâng khai :
(PKCS: Public_Key Cryptography Standards)
- PKCS laø moät taäp hôïp caùc tieâu chuaån ñeå hoaøn thieän heä maät maõ khoùa coâng khai, ñöôïc phaùt trieån vaøo naêm 1991. Noù ñöôïc soaïn bôûi cô quan baûo maät döõ lieäu RSA, cuøng hôïp taùc vôùi lieân hieäp caùc coâng ty kyõ thuaät maùy tính bao goàm Apple, Microsoft, DEC Lotus, Sun vaø MIT. PKCS ñaõ ñöôïc trích daãn bôûi OIW (OSI Implementor’s Workshop) nhö laø moät phöông phaùp ñeå hoaøn thieän caùc tieâu chuaån OSI. Noù töông thích vôùi PEM (Privacy Enhanced Mail) nhöng môû roäng ngoaøi PEM. Chaúng haïn nôi naøo PEM chæ coù theå xöû lyù data ASCII thì PKCS coù theå xöû lyù data binary toát töông ñöông. Ngoaøi ra PKCS cuõng töông thích vôùi tieâu chuaån X.509 cuûa CCITT.
- Caùc tieâu chuaån PKCS bao goàm: maõ hoùa RSA, ñoàng yù khoùa Diffie_Hellman, maõ hoùa döïa treân password, caáu truùc chöùng thöïc môû roäng. PKCS bao goàm caû vieäc ñaëc taû giaûi thuaät laãn caùc tieâu chuaån hoaøn thieän ñoäc laäp giaûi thuaät. Caùc giaûi thuaät ñaëc taû ñaõ hoã trôï bao goàm: RSA, DES, vaø söï trao ñoåi khoùa Diffie_Hellman . Noù cuõng xaùc ñònh caáu truùc cho chöõ kyù soá, bì thö soá (digital evelope) (cho vieäc maõ hoùa) vaø söï chöùng thöïc ñoäc laäp vôùi giaûi thuaät. Ñieàu naøy cho pheùp moät ngöôøi naøo ñoù hoaøn thieän baát kyø giaûi thuaät maät maõ sao cho phuø hôïp vôùi caáu truùc tieâu chuaån. Hieän nay coù caùc tieâu chuaån PKCS sau:
PKCS #1: tieâu chuaån maõ hoùa RSA.
PKCS #3: tieâu chuaån ñoàng yù khoùa Diffie_Hellman.
PKCS #5: tieâu chuaån heä maät maõ döïa treân password.
PKCS #6: tieâu chuaån caáu truùc chöùng thöïc môû roäng.
PKCS #7: tieâu chuaån caáu truùc ñoaïn tin heä maät maõ.
PKCS #8: tieâu chuaån caáu truùc thoâng tin khoùa bí maät.
PKCS #9: tieâu chuaån caùc kieåu thuoäc tính ñöôïc choïn.
PKCS #10: tieâu chuaån caáu truùc yeâu caàu söï chöùng thöïc.
PKCS #11: tieâu chuaån giao tieáp token heä maät maõ.
PKCS #12: tieâu chuaån caáu truùc trao ñoåi thoâng tin caù nhaân.
PKCS #13: tieâu chuaån heä maät maõ Elliptic Curve.
Caùc tieâu chuaån PKCS #2 vaø PKCS #4 ñaõ ñöôïc hôïp nhaát vaøo PKCS #1.
PKCS #1 v1.5: laø tieâu chuaån heä maät maõ RSA.
- Caùc kyù hieäu:
(n,e): khoùa coâng khai RSA.
n: modulus (n = pq).
e: soá muõ coâng khai
d: soá muõ bí maät (d = e-1 mod phiN, phiN = (p-1)(q-1)).
p,q: caùc thöøa soá nguyeân toá cuûa modulus n.
dP: soá muõ cuûa p, laø moät soá nguyeân xaùc ñònh sao cho: dP = e-1 mod (p-1).
dQ: soá muõ cuûa q, laø moät soá nguyeân xaùc ñònh sao cho: dQ = e-1 mod (q-1).
qInv: heä soá CRT (Chinese Remainder Theorem) thoûa: qInv = q-1 mod p.
K: khoùa bí maät RSA.
||M||: chieàu daøi cuûa ñoaïn tin M.
+ Khoùa coâng khai RSA (n, e): goàm hai thaønh phaàn modulus n vaø soá muõ coâng khai e. Khoùa coâng khai laø hôïp leä khi: n = pq vaø e phaûi naèm trong khoaûng 3 vaø n-1 vaø thoûa gcd(e, phiN) = 1 vôùi phiN = (p-1)(q-1).
+ Khoùa bí maät RSA (K): coù theå ôû moät trong hai daïng:
. Caëp (n, d).
. Bao goàm caùc phaàn töû: (p, q, dP, dQ, qInv).
Moät tieâu chuaån khaùc cho vieäc xaùc ñònh kieåu khoùa coâng khai vaø khoùa bí maät laø tieâu chuaån ASN.1:
. RSAPublicKey = {n, e}
. RSAPrivateKey = {n, e, d, p, q, dP, dQ, qInv}
Caùc öùng duïng cuûa tieâu chuaån naøy bao goàm chöùng thöïc X.509, PKCS #8, vaø PKCS #12.
- Caùc thao taùc bieán ñoåi data:
+ I2OSP: bieán ñoåi soá nguyeân lôùn thaønh xaâu.
+ OS2IP: bieán ñoåi xaâu thaønh soá nguyeân.
Vôùi xaâu: X = X1X2 … Xl
soá nguyeân: x = xl - 1256l - 1 + xl - 2256l - 2 + … + x1256 + x0
(xaâu Xi coù giaù trò xl – i vôùi 1=< i <= l).
- Caùc thao taùc heä maät maõ:
+ Maõ hoùa: RSAEP ((n, e), m) : c = me mod n.
Nhaäp: (n, e) khoùa coâng khai RSA.
m ñoaïn tin roû (0 < m < n – 1).
Xuaát: maät maõ c (0 < c < n –1) hay thoâng baùo “ñoaïn tin ngoaøi vuøng”.
Giaû thieát: (n, e) phaûi hôïp leä.
Giaûi thuaät:
. Neáu m khoâng thuoäc 0 vaø n – 1 thì xuaát “ñoaïn tin ngoaøi vuøng” vaø döøng.
. Tính c = me mod n.
. Xuaát c.
+ Giaûi maõ: RSADP (K, c)
Nhaäp: K khoùa bí maät RSA (ôû moät trong hai daïng treân).
c maät maõ (0 < c < n – 1).
Xuaát: m ñoaïn tin giaûi maõ (0 < m < n – 1) hay “maät maõ ngoaøi vuøng”.
Giaû thieát: khoùa bí maät K laø hôïp leä.
Giaûi thuaät:
. Neáu c khoâng thuoäc 0 vaø n – 1 thì xuaát “maät maõ ngoaõi vuøng” vaø döøng. . Neáu K ôû daïng (n, d) thì tính m = cd mod n.
. Ngöôïc laïi tính m1 = cdP mod p
m2 = cdQ mod q
h = qInv (m1 – m2) mod p
m = m2 + hp.
. Xuaát m.
Caàn chuù yù raèng tröôùc khi nhaäp vaø sau khi xuaát trong caùc thao taùc maät maõ ñoaïn tin phaûi ñöôïc bieán ñoåi töø xaâu sang soá nguyeân (khi nhaäp) hoaëc töø soá nguyeân sang xaâu (khi xuaát).
- Quaù trình maät maõ baèng khoùa coâng khai:
+ Hoaït ñoäng maõ hoùa: EME_PKCS1_v1.5_ENCODE (M, emLen)
Nhaäp: M ñoaïn tin roû, xaâu coù chieàu daøi toái ña laø emLen – 11.
emLen chieàu daøi döï ñònh cho ñoaïn tin ñaõ maõ hoùa (chieàu daøi modulus)
Xuaát: EM maät maõ (xaâu coù chieàu daøi emLen) hay “ñoaïn tin quaù daøi”.
Giaûi thuaät:
. Neáu chieàu daøi M > emLen – 11 thì xuaát “ñoaïn tin quaù daøi” vaø döøng.
. Taïo xaâu PS coù chieàu daøi emLen - ||M|| - 3 bao goàm caùc byte khaùc 0 ñöôïc taïo moät caùch giaû ngaãu nhieân. Chieàu daøi PS ít nhaát laø 8 byte.
. Noái PS, M vaø phaàn theâm (padding) ñeå hình thaønh maät maõ EM
EM = 02 || PS || 0 || M
. Xuaát EM.
+ Hoaït ñoäng giaûi maõ: EME_PKCS1_v1.5_DECODE (EM)
Nhaäp: EM ñoaïn tin maät maõ (xaâu coù chieàu daøi ít nhaát laø 11).
Xuaát: M ñoaïn tin giaûi maõ (xaâu coù chieàu daøi nhieàu nhaát laø ||EM|| - 11)
hay thoâng baùo “loãi giaûi maõ”.
Giaûi thuaät:
. Neáu chieàu daøi EM < 11 thì xuaát “loãi giaûi maõ” vaø döøng.
. Taùch EM thaønh xaâu PS bao goàm caùc byte khaùc 0 vaø ñoaïn tin M:
EM = 02 || PS || 0 || M
Neáu hai byte ñaàu cuûa EM khaùc 0 vaø 2 hay neáu khoâng coù byte 0 ñeå taùch PS khoûi M thì xuaát “loãi giaûi maõ” vaø döøng.
. Neáu chieàu daøi PS < 8 byte thì xuaát “loãi giaûi maõ” vaø döøng.
. Xuaát M.
- Quaù trình maät maõ baèng khoùa bí maät:
Töông töï quaù trình maät maõ baèng khoùa coâng khai chæ khaùc:
EM = 01 || PS || 0 || M
+ Hai byte ñaàu cuûa EM laø 0 vaø 1.
+ Caùc byte PS ñeàu baèng 1.
3.2. Tieâu chuaån chöùng thöïc khoùa coâng khai X.509:
- Ñöôïc CCITT giôùi thieäu vaøo 1988 vaø ñeán naêm1993 thì ñöôïc söûa ñoãi vaø ñöôïc phaùt haønh.
- X.509 laø moät server chöùa cô sôû döõ lieäu veà thoâng tin cuûa caùc user. Thoâng tin bao goàm söï aùnh xaï töø teân user tôùi ñòa chæ maïng cuõng nhö caùc thuoäc tính vaø thoâng tin khaùc veà user.
- X.509 laø moät tieâu chuaån quan troïng bôûi vì noù xaùc ñònh 1 khung laøm vieâc (framework) cho caùc dòch vuï chöùng thöïc bôûi thö muïc X.500 tôùi caùc user cuûa noù vaø X.500 ñöôïc söû duïng moät caùch roäng raõi. Theâm vaøo ñoù caáu truùc vaø caùc giao thöùc chöùng thöïc trong X.509 coù theå ñöôïc söû duïng trong caùc ngöõ caûnh khaùc chaúng haïn noù ñöôïc söû duïng trong PEM (Privary Enhanced Mail).
- X.509 döïa treân vieäc söû duïng heä maät maõ khoùa coâng khai vaø chöõ kyù soá. Tieâu chuaån khoâng yeâu caàu söû duïng giaûi thuaät ñaëc taû nhöng giôùi thieäu RSA. Sô ñoà chöõ kyù soá ñöôïc giaû thieát yeâu caàu söû duïng haøm baêm nhöng khoâng yeâu caàu ñaëc taû giaûi thuaät baêm.
3.2.1. Söï chöùng thöïc:
- Ñieåm maáu choát cuûa sô ñoà X.509 laø söï chöùng thöïc khoùa coâng khai lieân heä vôùi moãi user. Söï chöùng thöïc cuûa caùc user naøy ñöôïc giaû thieát laø ñöôïc taïo bôûi moät vaøi CA (Certification Authority) tin caäy ñöôïc ñaët trong thö muïc bôûi CA hay bôûi user. Baûn thaân server thö muïc khoâng coù traùch nhieäm cho vieäc taïo caùc khoùa coâng khai hay cho haøm chöùng thöïc nhöng noù gaàn nhö cung caáp vò trí coù theå truy xuaát deã daøng cho user ñeå ñöa ra söï chöùng thöïc.
- Daïng thöùc toång quaùt cuûa söï chöùng thöïc bao goàm caùc phaàn töû sau:
Version
Serial number
algorithm
parameters
Issuer
not before
not after
Subject
algorithm
parameters
key
Signature
Algorithm identifier Period of validdity
Subject’s public key . Version: chæ ra caùc version thaønh coâng cuûa daïng thöùc chöùng thöïc, maëc ñònh laø vaøo 1988.
. Serial number: giaù trò nguyeân duy nhaát trong CA maø ñöôïc lieân keát moät caùch khoâng chaéc tôùi söï chöùng thöïc naøy.
. Algorithm identifier: giaûi thuaät ñaõ söû duïng ñeå kyù baûn chöùng thöïc cuøng vôùi baát kyø caùc thoâng soá lieân quan.
. Issuer: CA maø ñaõ taïo vaø kyù chöùng thöïc naøy.
. Period of validity: thôøi gian hôïp leä cuûa chöùng thöïc.
. Subject: user maø tham khaûo chöùng thöïc naøy.
. Public key information: khoùa coâng khai cuûa subject coäng vôùi ñònh danh cuûa giaûi thuaät maø khoùa naøy ñöôïc söû duïng.
. Signature: bao goàm maõ baêm cuûa caùc vuøng khaùc ñöôïc maõ hoùa baèng khoùa bí maät cuûa CA.
- Tieâu chuaån söû duïng yù töôûng sau ñeå xaùc ñònh söï chöùng thöïc:
CA > = CA {V, SN, AI, CA, TA, A, AP }
Trong ñoù:
. Y > = chöùng thöïc cuûa user X ñöôïc laøm roû bôûi CA Y
. Y {I} = chöõ kyù cuûa I bôûi Y. Noù bao goàm I cuøng vôùi maõ baêm ñaõ ñöôïc maõ hoùa keøm theo.
- CA kyù baûn chöùng thöïc baèng khoùa bí maät cuûa noù. Neáu khoùa coâng khai töông öùng ñöôïc bieát tôùi user thì user ñoù coù theå laøm roû raèng chöùng thöïc ñöôïc kyù bôûi CA laø hôïp leä. Sô ñoà chöùng thöïc nhö sau:
H
M
||
M
So saùnh
D
E
H
KRa
KUa
EKra[H(M)]
3.2.2. Ñöa ra chöùng thöïc cuûa user:
- Söï chöùng thöïc cuûa user ñöôïc taïo bôûi CA coù caùc ñaëc ñieåm:
. Baát kyø user naøo truy xuaát khoùa coâng khai cuûa CA thì coù theå khoâi phuïc khoùa coâng khai cuûa user maø ñaõ chöùng thöïc.
. Khoâng moät ai khaùc hôn CA coù theå moâ phoûng söï chöùng thöïc.
- Bôûi vì söï chöùng thöïc laø khoâng theå ñoaùn tröôùc neân chuùng coù theå ñöôïc ñaët trong moät thö muïc maø khoâng caàn thieát phaûi coá gaéng ñeå baûo veä chuùng.
- Neáu taát caû user moâ taû tôùi cuøng CA thì coù ñoä tin caäy chung cuûa CA ñoù. Taát caû chöùng thöïc cuûa user coù theå ñöôïc ñaët trong thö muïc cho taát caû caùc user truy xuaát. Ngoaøi ra user coù theå truyeàn chöùng thöïc cuûa mình tröïc tieáp tôùi caùc user khaùc.
- Neáu caùc user ôû trong moät maïng truyeàn thoâng lôùn thì khoâng theå aùp duïng cho taát caû caùc user moâ taû cuøng moät CA bôûi vì CA kyù chöùng thöïc, moãi user tham gia phaûi coù moät baûn sao khoùa coâng khai cuûa rieâng CA ñeå laøm roû chöõ kyù. Khoùa coâng khai naøy phaûi ñöôïc cung caáp tôùi moãi user trong caùch thöùc baûo maät tuyeät ñoái ñeå cho moãi user ñaûm baûo tính bí maät trong söï chöùng thöïc lieân quan.
- Giaû söû A ñaõ ñöa ra moät chöùng thöïc töø CA X1 vaø B ñaõ ñöa ra moät chöùng thöïc töø CA X2. Neáu A khoâng bieát söï baûo maät khoùa coâng khai cuûa X2 thì chöùng thöïc cuûa B khoâng coù ích vôùi A. A coù theå ñoïc chöùng thöïc cuûa B nhöng A khoâng theå laøm roû chöõ kyù. Tuy nhieân neáu hai CA coù söï trao ñoåi moät caùch baûo maät caùc khoùa coâng khai cuûa chuùng thì thuû tuïc sau seõ cho pheùp A ñöa ra khoùa coâng khai cuûa B:
. A ñöa ra töø thö muïc söï chöùng thöïc cuûa X2 ñöôïc kyù bôûi X1. Bôûi vì A bieát khoùa coâng khai cuûa X1 neân A coù theå ñöa ra khoùa coâng khai cuûa X2 töø söï chöùng thöïc cuûa noù vaø laøm roû noù baèng chöõ kyù treân baûn chöùng thöïc cuûa X1.
. Sau ñoù A quay laïi thö muïc vaø ñöa ra baûn chöùng thöïc cuûa B ñöôïc kyù bôûi X2.. Bôûi vì giôø ñaây A ñaõ coù moät baûn sao tin caäy veà khoùa coâng khai cuûa X2 neân A coù theå laøm roû chöõ kyù vaø ñöa ra khoùa coâng khai cuûa B.
- A ñaõ söû sduïng moät daây chuyeàn caùc chöùng thöïc ñeå ñöa ra khoùa coâng khai cuûa B nhö sau:
X1 > X2 >
Töông töï B coù theå ñöa ra khoùa coâng khai cuûa A:
X2 > X1 >
- Môû roäng daây chuyeàn vôùi N phaàn töû:
X1 > X2 > … Xn >
Trong daây chuyeàn naøy moãi caëp CA (Xi, Xi+1) coù theå taïo chöùng thöïc cho moãi caëp khaùc.
- Taát caû söï chöùng thöïc cuûa CA bôûi CA naøy caàn xuaát hieän trong thö muïc vaø user caàn bieát laøm sao ñeå lieân keát chuùng theo moät ñöôøng daãn tôùi söï chöùng thöïc khoùa coâng khai cuûa user khaùc. X.509 ñeà nghò chuùng ñöôïc toå chöùc theo thöù töï phaân caáp. Ví duï:
U>
V>
U
V >
Y >
V>
W>
V
W>
X>
Y >
Z >
W
Y
X
Z
C
A
B
Z>
X>
X>
Ñöôøng noái caùc voøng troøn chæ moái quan heä phaân caáp giöõa caùc CA, caùc hoäp vuoâng chæ ra caùc chöùng thöïc ñaõ duy trì trong thö muïc cho moãi CA. Moãi CA X bao goàm hai kieåu chöùng thöïc:
. Chöùng thöïc veà phía tröôùc: chöùng thöïc cuûa X ñöôïc taïo ra bôûi CA khaùc.
. Chöùng thöïc ñaûo ngöôïc (quay lui): chöùng thöïc cuûa CA khaùc ñöôïc taïo ra bôûi X.
Trong ví duï naøy user A coù theå yeâu caàu söï chöùng thöïc sau töø thö muïc ñeå thieát laäp moät ñöôøng daãn tôùi B:
X > W > V > Y > Z >
Khi ñoù A coù theå bieát ñöôïc khoùa coâng khai cuûa B.
Töông töï khi B caàn bieát khoùa coâng khai cuûa A:
Z > Y > V > W > X >
3.2.3. Huûy boû söï chöùng thöïc:
- Vì moãi chöùng thöïc chæ coù moät thôøi gian hôïp leä neân moät chöùng thöïc môùi seõ ñöôïc taïo ra ñuùng khi chöùng thöïc cuõ heát haïn. Ngoaøi ra, ngöôøi ta mong muoán coù dòp ñeå huûy boû chöùng thöïc tröôùc khi noù heát haïn vì moät trong caùc lí do sau:
. Khoùa bí maät cuûa user ñöôïc giaû thieát laø ñaõ ñöôïc thoûa hieäp.
. Moät thôøi gian daøi user khoâng ñöôïc chöùng thöïc bôûi CA naøy.
. Khoùa bí maät cuûa CA ñöôïc giaû thieát laø ñaõ ñöôïc thoûa hieäp.
- Moãi CA phaûi duy trì moät danh saùch bao goàm taát caû caùc chöùng thöïc bò huûy nhöng chöa heát haïn tôùi caùc user vaø caùc CA khaùc. Danh saùch naøy cuõng neân ñöôïc gôûi neân thö muïc. Moãi danh saùch huûy boû chöùng thöïc ñaõ gôûi tôùi thö muïc ñöôïc kyù nhaän bôûi issuer vaø bao goàm caû teân cuûa issuer, ngaøy thaùng danh saùch ñaõ ñöôïc taïo vaø moät muïc töø (entry) cho moãi chöùng thöïc bò huûy. Moãi entry bao goàm serial number cuûa chöùng thöïc vaø ngaøy thaùng huûy boû chöùng thöïc ñoù.
- Khi user nhaän ñöôïc chöùng thöïc trong ñoaïn tin thì user phaûi xaùc ñònh coù bò huûy chöa. User coù theå kieåm tra thö muïc moãi laàn nhaän ñöôïc chöùng thöïc. Ñeå traùnh söï trì hoaõn vaø caùc chi phí coù theå lieân quan ñeán thö muïc tìm kieám, thaät laø toát neáu user duy trì moät boä nhôù (cache) cuïc boä veà caùc chöùng thöïc vaø danh saùch caùc chöùng thöïc ñaõ huûy.
3.2.4. Caùc thuû tuïc chöùng thöïc:
X.509 bao goàm ba thuû tuïc chöùng thöïc khaùc nhau cho caùc uùng duïng khaùc nhau. Taát caû caùc thuû tuïc naøy ñeàu söû duïng chöõ kyù khoùa coâng khai. Noù ñöôïc giaû thieát raèng hai ngöôøi tham gia phaûi bieát khoùa coâng khai laãn nhau hoaëc baèng caùch ñöa ra chöùng thöïc laãn nhau töø thö muïc hoaëc chöùng thöïc ñöôïc bao goàm trong ñoaïn tin khôûi taïo töø moãi phía.
- Chöùng thöïc moät phía (one-way): (h.a)
Ñaây laø söï truyeàn thoâng ñôn thoâng tin töø user A ñeán user B vaø thieát laäp caùc vieäc sau:
Ñònh danh cuûa A vaø ñoaïn tin ñöôïc taïo bôûi A.
Ñoaïn tin döï kieán cho B.
Söï töôøng minh vaø nguoàn goác cuûa ñoaïn tin.
ÔÛ möùc toái thieåi ñoaïn tin bao goàm: timestamp tA (goàm coù thôøi gian taïo vaø thôøi gian heát haïn), nonce rA, ñònh danh cuûa B, sgnData (chöõ kyù), Kab (khoùa phieân lieân laïc ñöôïc maõ hoùa baèng khoùa coâng khai cuûa B). Giaù trò rA laø duy nhaát trong thôøi gian hôïp leä cuûa ñoaïn tin, noù ñöôïc söû duïng ñeå choáng laïi caùc cuoäc taán coâng laëp laïi vaø noù ñöôïc löu tröõ ôû B cho ñeán khi heát haïn, B seõ khoâng nhaän baát kyø ñoaïn tin môùi naøo coù rA töông töï.
- Chöùng thöïc hai phía (two-way): (h.b)
Ngoaøi ba phaàn töû ôû chöùng thöïc moät phía thì chöùng thöïc hai phía coøn thieát laäp theâm caùc phaàn töû sau:
Ñònh danh cuûa B vaø ñoaïn tin ñaùp laïi ñöôïc taïo ra bôûi B.
Ñoaïn tin döï kieán cho A.
Tính töôøng minh vaø nguoàn goác cuûa söï hoài aâm.
Chöùng thöïc hai phía cho pheùp caû hai ñoái taùc truyeàn thoâng laøm roû ñònh danh laãn nhau.
- Chöùng thöïc ba phía (three-way): (h.c)
Töông töï nhö chöùng thöïc hai phía nhöng coù theâm söï ñaùp laïi rB töø A tôùi B. Vôùi kieåu thieát keá naøy thì timestamp khoâng caàn thieát phaûi ñöôïc kieåm tra bôûi vì moãi nonce ñeàu ñöôïc quay laïi phía gôûi, neân moãi phía coù theå kieåm tra nonce quay veà ñeå doø caùc cuoäc taán coâng laëp laïi. Caùch tieáp caän naøy thì caàn thieát khi ñoàng hoà ñoàng boä khoâng coù saün.
1. A |tA, rA, B, sgnData, EKUb|Kab||
A
B
(h.a)
1. A |tA, rA, B, sgnData, EKUb|Kab||
B
A
2. B |tB, rB, A, sgnData, EKUa|Kba||
Chöông 4: Thuyeát minh chöông trình
1.1. Giôùi thieäu:
- Nhö ñaõ trình baøy trong phaàn lyù thuyeát, chuùng ta coù theå ruùt ra moät soá keát luaän trong vaán ñeà baûo maät döõ lieäu nhö sau:
+ Khi maõ hoùa:
. Duøng khoùa DES (KS) ñeå maõ hoùa data (M): EKs (M).
. Duøng khoùa coâng khai RSA (KU) ñeå maõ hoùa khoùa DES: EKU (KS).
+ Khi giaûi maõ:
. Duøng khoùa bí maät RSA (KR) ñeå giaûi maõ khoùa DES: DKR (EKU (KS)) = KS.
. Duøng khoùa DES (KS) ñeå giaûi maõ data (M): DKs (EKs (M)) = M.
Vaán ñeà quan troïng laø phaûi ñaûm baûo tính xaùc thöïc cuûa caëp khoùa RSA (ñaëc bieät laø khoùa coâng khai) nghóa laø khi ngöôøi gôûi söû duïng khoùa coâng khai KU cuûa moät ngöôøi naøo ñoù thì phaûi ñaûm baûo khoùa coâng khai ñoù laø cuûa chính ngöôøi ñoù chöù khoâng phaûi cuûa moät ngöôøi naøo khaùc (ngöôøi muoán giaû daïng). Chöông trình naøy cuõng khoâng ngoaøi muïc ñích ñoù, xaây döïng server taïo khoùa cho user, thoâng qua web server user coù theå xem khoùa coâng khai cuûa caùc user khaùc thoâng qua thö muïc khoùa coâng khai vaø neáu coù yeâu caàu thì server seõ taïo caëp khoùa RSA cho user. Khoùa coâng khai ñöôïc caäp nhaät vaøo thö muïc khoùa coâng khai, coøn khoùa bí maät thì ñöôïc maõ hoùa baèng khoùa DES maø caû server laãn user cuøng söû duïng (moät caùch ñôn giaûn laø söû duïng password cuûa user) vaø ñöôïc gôûi trôû veà cho user (user seõ söû duïng password cuûa mình ñeå giaûi maõ, tìm ñöôïc khoùa bí maät RSA). Trang web server cô baûn nhö sau:
Taïo khoùa coâng khai
Thö muïc khoùa coâng khai
+ Thö muïc khoùa coâng khai: yeâu caàu user nhaäp vaøo password. Neáu ñuùng thì lieân keát ñeán phaàn töû (thö muïc khoùa coâng khai, tìm kieám, caäp nhaät…), neáu sai thì yeâu caàu nhaäp laïi:
OK
Password: ……………………………………
Cancel
Password confirm: ……………………
OK
Danh saùch caùc khoùa coâng khai
Cancel
Caäp nhaät
Tìm kieám
Danh saùch khoùa coâng khai
KeyID Bits Type UserID
399c57aa 1024 e Tien1024Encrypt
7dc3fb84 1024 s Tien1024Sign
+ Taïo khoùa coâng khai:
Neáu baïn laø user môùi thì kích nuùt Next, neáu khoâng thì
kích vaøo nuùt Form ñeå ñaêng kyù
Cancel
Next
Form
Form
Name :
Addr. :
Email :
Passsword:
Other infor.:
OK
Cancel
Key length
o 512
o 1024
o 2048
User name
o Curren Login User
o Other user
Other User Name
Enter Password
Reenter Password
OK
Cancel
- Chöông trình ñöôïc vieát baèng ngoân ngöõ C vaø ñöôïc bieân dòch trong TC3. Chöông trình goàm coù:
+ Caùc taäp tin ñaàu (*.h): global, nn, prime, r_random, md5, des, rsa, rsatool.
+ Caùc taäp tin nguoàn (*.c): nn, prime, r_random, r_stdlib, md5, desc, rsa, r_keygen,
r_enhanc.
+ Caùc taäp tin demo (*.c): rsagen, pubfind, pubdir.
+ Thö muïc khoùa coâng khai default laø: keypub.
+ Thö muïc chöùa thoâng tin cuûa user default laø: usrpass.
1.2. Caùc haèng:
. Lieân quan ñeán soá DIGIT:
NN_DIGIT_BITS = 32 (soá bít cuûa soá digit).
NN_HALF_DIGIT_BITS = 16 (soá bít cuûa moät nöûa soá digit).
NN_DIGIT_LEN = NN_DIGIT_BITS / 8 (soá byte cuûa soá digit).
MAX_NN_DIGIT = 0xffffffff (soá byte toái ña cuûa soá digit).
MAX_NN_HALF_DIGIT = 0xffff (soá byte toái ña cuûa nöûa soá digit).
NN_LT = -1 (giaù trò nhoû hôn).
NN_EQ = 0 (giaù trò baèng nhau).
NN_GT = 1 (giaù trò lôùn hôn).
. Lieân quan ñeán khoùa RSA:
MIN_RSA_MODULUS_BITS = 145
(soá bít toái thieåu cuûa modulus).
MAX_RSA_MODULUS_BITS = 512
(soá bít toái ña cuûa modulus).
MAX_RSA_MODULUS_LEN = (MAX_RSA_MODULUS_BITS + 7) / 8
(soá byte toái ña cuûa modulus).
MAX_RSA_PRIME_BITS = (MAX_RSA_MODULUS_BITS + 1) / 2
(soá bít toái ña cuûa soá nguyeân toá).
MAX_RSA_PRIME_LEN = (MAX_RSA_MODULUS_BITS + 7) / 8
(soá byte toái ña cuûa soá nguyeân toá).
MAX_NN_DIGITS = (MAX_RSA_MODULUS_LEN+ NN_DIGIT_LEN –1)
/(NN_DIGIT_LEN + 1)
(soá chöõ soá digit toái ña).
MAX_ENCRYPTED_KEY_LEN = MAX_RSA_MODULUS_LEN
(chieàu daøi toái ña cuûa khoùa maõ hoùa khoùa).
RANDOM_BYTES_RQ = 256
(soá byte random yeâu caàu ñeå seed caáu truùc random ñaàu tieân ñeå söû duïng).
RANDOM_BYTES_RQINT = 512
(soá byte random töø haøm thôøi gian ANSI yeâu caàu ñeå seed caáu truùc
random ñaàu tieân ñeå söû duïng).
MAX_NN_DIGITS thì ñuû daøi ñeå chöùa baát kyø modulus RSA. Taát caû caùc soá töï nhieân (DIGIT) coù nhieàu nhaát MAX_NN_DIGITS chöõ soá, ngoaïi tröø caùc giaù trò trung gian coù chieàu daøi gaáp ñoâi trong NN_Mult(t), NN_ModMult(t), NN_ModInv(w), NN_ModDiv(c).
.3. Caùc taäp tin ñaàu (*.h):
Global.h: ñònh nghóa caùc kieåu data cô sôû nhö:
unsigned char * POINTER, BYTE;
unsigned long int UINT4;
unsigned short int UNIT2;
PROTO_LIST (list) = list (traû veà moät danh saùch) hoaëc
PROTO_LIST(list) = () (traû veà moät danh saùch roãng).
NN.h:
+ Ñònh nghóa caùc haèng lieân quan ñeán DIGIT
+ Ñònh nghóa caùc haøm bieán ñoåi data: töø xaâu sang soá DIGIT vaø ngöôïc laïi:
NN_Decode(a, digits, b, len): bieán ñoåi xaâu coù chieàu daøi len thaønh soá DIGIT a coù chieàu daøi digits.
NN_Decode(b, len, a, digits): bieán ñoåi soá DIGIT a coù chieàu daøi digits thaønh xaâu b coù chieàu daøi len.
+ Ñònh nghóa caùc haøm thieát laäp (assign):
NN_Assign(a, b, digits): assign a = b
NN_AssignZero(a, digits): assign a = 0
NN_Assign2Exp(a, b, digits): assign a = 2b
+ Ñònh nghóa caùc haøm tính toaùn soá hoïc:
NN_Add(a, b, c, digits): tính a = b + c
NN_Sub(a, b, c, digits): tính a = b - c
NN_Mult(a, b, c, digits): tính a = b * c
NN_LShift(a, b, c, digits): tính a = b * 2c
NN_RShift(a, b, c, digits): tính a = b / 2c
NN_LRotate(a, b, c, digits): quay traùi c bit
+ Ñòng nghóa caùc haøm tính toaùn lyù thuyeát soá:
NN_Mod(a, b, bdigitsc, c, cdigits): tính a = a mod c
NN_ModMult(a, b, c, d, digits): tính a = b * c mod d
NN_Div(a, b, c, cdigits, d, ddigits): tính a = c div d, b = c mod d
NN_ModExp(a, b, c, cdigitsc, d, ddigits): tính a = bc mod d
NN_ModInv(a, b, c, digits): tính a = 1/b mod c
NN_Gcd(a, b, c, digits: tính a = gcd(b, c)
+ Ñònh nghóa caùc haøm tính toaùn khaùc:
NN_EVEN(a, digits): traû veà 1 neáu a chaün
NN_EQUAL(a, b, digits): traû veà 1 neáu a = b
NN_Zero(a, digits): traû veà 1 neáu a = 0
NN_Cmp(a, b, digits): traû veà 1 neáu a > b, 0 : a = b, -1 : a<b
NN_Digits(a, digits): traû veà chieàu daøi cuûa a baèng digits
NN_Bits(a, digits): traû veà chieàu daøi cuûa a baèng bits
1.3.3 Prime.h: ñònh nghóa haøm R_GeneratePrime (taïo soá nguyeân toá).
1.3.4. R_random.h: ñònh nghóa haøm R_GenerateBytes (taïo soá byte ngaãu nhieân).
Rsa.h: ñònh nghóa caùc haøm maät maõ cuûa RSA:
RSAPublicEncrypt: maõ hoùa baèng khoùa coâng khai RSA.
RSAPrivateEncrypt: maõ hoùa baèng khoùa bí maät RSA.
RSAPublicDecrypt: gi
Các file đính kèm theo tài liệu này:
key.doc
