Bài giảng Mật mã hóa hiện đại - Chương 1: Các khái niệm căn bản

Nội dung text: Bài giảng Mật mã hóa hiện đại - Chương 1: Các khái niệm căn bản

1. Ch ươ ng 1: Các khái ni m căn bn 1.1Đ khơngch cch n
2. 2 Hu ỳnh V ăn Kha 9/30/2010 Mơ hình truy n thơng • Lý thuy t thơng tinkh o sát v h th ng truy n thơng.Sơ đ nh ư sau. Nhi u Ngu n Mã Kênh Gi i mã Đích
3. 3 Hu ỳnh V ăn Kha 9/30/2010 Mơ hình truy n thơng • Ngu n:phát ra thơng tin • Mã:th tc chuy n đi mu tinthành “th c th ” thích hp đ truy n qua kênh • Kênh:truy n đi mu tinđã mã hĩa,trong quá trình này ch u s tác đng ca Nhi u • Gi i mã:th tc bi n đi outputca kênh thành mu tinbanđu • Đích:nh n thơng tin
4. 4 Hu ỳnh V ăn Kha 9/30/2010 Mc đích ca LTTT • LTTTnh m xây dng mơ hình tốn hc cho mi kh i trong sơ đ truy n thơng • Khơng đi sâu vào chi ti t k thu t mà ch kh o sát ch yu v lý thuy t mã hĩa và gi i mã • Đnh lý căn bn ca LTTTphát bi u: Cĩ th truy n thơng tinquamt kênh b nhi u theo mt đnh lư ng truy n bt kỳ nh hơn dunglư ng kênh theo mt xác su t sai nh tùy ý.
5. 5 Hu ỳnh V ăn Kha 9/30/2010 Ýnghĩa ca ðnh lý căn bn • Gi s ngu n sinh ra mt chu i bit0,1vi xác su t nh ư nhau vi đnh lư ng sinh 1bit/giây.Gi s các bit đư c sinh ra đc lp nhau . • Chúng đư c truy n quamt kênh cĩ xác su t truy n sai 1bitbt kỳ là ¼.Gi s tc đ truy n quakênh là 1bit/giây. ¾ 0 0 ¼ Ngu n ¼ 1 1 ¾
6. 6 Hu ỳnh V ăn Kha 9/30/2010 Ýnghĩa ca ðnh lý căn bn • Doxác su t sai ¼là quá ln,ta tìm cách làm gi m xác su t này xu ng. • Mt cách làm là mi bit sinh ra đư c truy n qua kênh 3ln và gi i mã theo nguyên tc đa s. • Xác xu t đ gi i mã sai là:
7. 7 Hu ỳnh V ăn Kha 9/30/2010 Ýnghĩa ca ðnhlý căn bn • Nh ư vy đã gi m đư c xác su t sai • Nh ưng ph i tr giá:Gi m đnh lư ng sinh ca ngu n xu ng cịn 1/3bit/ giây • Tng quát,xác su t sai ca kênh là β <½,mi bitngu n đư c truy n 2n+1ln và gi i mã theo đa s.Thì:
8. 8 Hu ỳnh V ăn Kha 9/30/2010 Ýnghĩa ca ðnh lý cănbn • p(e)
   0khi n
   ∞ • Nh ư vy cĩ th gi m xác su t sai xu ng bt kỳ nu gi m đnh lư ng sinh xu ng nh gn bng 0 • Đi u ct lõi ca đnh lý căn bn là nĩ kh ng đnh: Khơng cn ph i gi m đnh lư ng sinh v 0mà ch cn gi m v mt đi lư ng gi là dunglư ng kênh. • Đ đt đư c đi u này chúng ta cn ti lý thuy t mã
9. 9 Hu ỳnh V ăn Kha 9/30/2010 Hàm đo đ khơng ch c ch n • Bi n ng u nhiên Xcĩ các giá tr và xác su t tươ ng ng • Ký hi u: • Hàm đo đ khơng ch c ch n ca bi n Xđư c đnh nghĩa (logđư c ly theo cơ s 2): • Th nh tho ng ta cũng vi t thay cho
10. 10 Hu ỳnh V ăn Kha 9/30/2010 Hàm đo đ khơng ch c ch n • Ví d 1:bi n ng u nhiên Xcĩ • Ví d 2:bi n ng u nhiên Xcĩ
11. 11 Hu ỳnh V ăn Kha 9/30/2010 Hàm đo đ khơng ch c ch n • H(X)dùngđ đolư ng thơng tincn xác đnh ca mt bi n ng u nhiên • Xét bi n ng u nhiên Wnh n các giá tr : trong đĩ • Thì H(X)chính là kỳ vng (trung bình)ca W • H(X)là s câu hi “yesno ”trung bình cc ti u đ xác đnh kt qu ca X
12. 12 Hu ỳnh V ăn Kha 9/30/2010 B đ 1.1 Cho và là các s dươ ng tùy ý th a . Thì: Du b ng x y ra khi và ch khi
13. 13 Hu ỳnh V ăn Kha 9/30/2010 Ch ng minhb đ 1.1 Áp d ng b t đng th c (d u bng x y ra khi và ch khi ), v i , nhân 2 v cho ri l y t ng theo : T đây ta suy ra điu c n ch ng minh.
14. 14 Hu ỳnh V ăn Kha 9/30/2010 ðnh lý 1.2 , d u b ng x y ra khi và ch khi vi m i ðây là h qu ca B đ phía trên, v i tt c
15. 15 Hu ỳnh V ăn Kha 9/30/2010 Hàm đo đ khơng ch c ch n c a đng th i hai bi n ng u nhiên Xét hai bi n ng u nhiên: • Bi n X l y giá tr vi xác su t l n l ưt là: • Bi n Y l y giá tr vi xác su t l n l ưt là: ðt . ð khơng ch c ch c đng th i c a X và Y đưc đnh ngh ĩa là:
16. 16 Hu ỳnh V ăn Kha 9/30/2010 ðnh lý 1.3 Du b ng x y ra khi và ch khi đc l p Ch ng minh:
17. 17 Hu ỳnh V ăn Kha 9/30/2010 ðt: , Thì: Áp d ng B đ 1.1, ta đưc: