›
›

Đồ án Mã hóa lượng tử và ứng dụng - Nguyễn Thanh Tùng

pdf 78 trang huongle 2130
Download
Bạn đang xem 20 trang mẫu của tài liệu "Đồ án Mã hóa lượng tử và ứng dụng - Nguyễn Thanh Tùng", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfdo_an_ma_hoa_luong_tu_va_ung_dung_nguyen_thanh_tung.pdf

Nội dung text: Đồ án Mã hóa lượng tử và ứng dụng - Nguyễn Thanh Tùng

  1. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng MỤC LỤC LỜI CẢM ƠN 3 MỞ ĐẦU 4 CHƢƠNG 1: CÁC KHÁI NIỆM CƠ BẢN 6 1.1 Một số khái niệm tốn học 6 1.1.1 Số nguyên tố và nguyên tố cùng nhau 6 1.1.2 Đồng dƣ thức 6 * 1.1.3 Khơng gian Zn và Zn 7 1.1.4 Phần tử nghịch đảo 7 1.1.5 Khái niệm nhĩm, nhĩm con, nhĩm Cyclic 8 1.1.6 Bộ phần tử sinh (Generator-tuple) 9 1.1.7 Bài tốn đại diện (Presentation problem). 9 1.1.8 Hàm băm. 10 1.2 Các khái niệm mã hĩa 11 1.2.1 Khái niệm mã hĩa. 11 1.2.1.1 Hệ mã hĩa. 11 1.2.1.2 Những khả năng của hệ mật mã. 12 1.2.2 Các phƣơng pháp mã hĩa. 12 1.2.2.1 Mã hĩa đối xứng 12 1.2.2.2 Mã hĩa phi đối xứng (Mã hĩa cơng khai). 13 1.2.3 Một số hệ mã hố cụ thể. 14 1.2.3.1 Hệ mã hố RSA. 14 1.2.3.2 Hệ mã hố ElGamal. 14 1.2.3.3 Mã hố đồng cấu. 15 1.2.3.4 Mã nhị phân. 16 1.3.1 Định nghĩa 17 1.3.2 Phân loại sơ đồ chữ ký điện tử. 18 1.3.3 Một số sơ đồ ký số cơ bản. 18 1.3.3.1 Sơ đồ chữ ký Elgamal 18 1.3.3.2 Sơ đồ chữ ký RSA. 19 1.3.3.3 Sơ đồ chữ ký Schnorr. 19 1.4 Phân phối khĩa và thỏa thuận khĩa 20 1.4.1 Phân phối khĩa 21 1.4.1.1 Sơ đồ phân phối khố trước Blom. 21 1.4.2 Thỏa thuận khĩa 31 1.4.2.1 Sơ đồ trao đổi khố Diffie-Hellman. 31 1.4.2.2 Giao thức thoả thuận khố trạm tới trạm. 33 1.4.2.3 Giao thức thoả thuận khố MTI. 36 2.1 Ký hiệu Bra-Ket 43 2.2 Nguyên lý cơ bản của cơ học lƣợng tử 44 2.3.1 Khái niệm Qubit 46 2.3.2 Khái niệm thanh ghi lƣợng tử 47 Nguyễn Thanh Tùng 1
  2. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng 2.4 Nguyên lý rối lƣợng tử (Nguyên lý Entanglement) 50 2.5 Nguyên lý song song lƣợng tử 50 2.7 Mạch và Cổng logic lƣợng tử 52 2.7.1 Cổng 1 qubit 54 2.7.2 Cổng 2 qubit 56 CHƢƠNG 3. MÃ HĨA LƢỢNG TỬ 61 3.1 Giao thức phân phối khố lƣợng tử BB84 62 3.1.1 Giao thức BB84 trƣờng hợp khơng nhiễu 62 3.1.1.1 Giai đoạn 1: Giao tiếp qua kênh lượng tử 63 3.1.1.2 Giai đoạn 2: Giao tiếp qua kênh cơng cộng 64 3.1.1.3 Ví dụ 66 3.1.2 Giao thức phân phối khố lƣợng tử BB84 trƣờng hợp cĩ nhiễu 66 3.1.2.2 Giai đoạn 2: Giao tiếp qua kênh cơng cộng. 66 3.1.3 Một số nhƣợc điểm của giao thức BB84. 68 3.1.4 Về độ an tồn của giao thức phân phối khố BB84. 69 3.1.4.1 Tạo bảng tham chiếu. 70 3.1.4.3 Kết luận về độ an tồn của giao thức BB84. 72 3.2. Kết luận về mã hố lƣợng tử và thám mã lƣợng tử. 72 CHƢƠNG 4. MƠ PHỎNG GIAO THỨC BB84 73 KẾT LUẬN 77 TÀI LIỆU THAM KHẢO 78 Nguyễn Thanh Tùng 2
  3. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng LỜI CẢM ƠN Ngƣời xƣa cĩ câu: “Uống nƣớc nhớ nguồn, ăn quả nhớ kẻ trồng cây”. Với em sinh viên khố 9 của trƣờng Đại Học Dân Lập Hải Phịng luơn luơn ghi nhớ những cơng lao to lớn của các thầy giáo, cơ giáo. Những ngƣời đã dẫn dắt chúng em từ khi mới bƣớc chân vào giảng đƣờng đại học những kiến thức, năng lực và đạo đức chuẩn bị hành trang bƣớc vào cuộc sống để xây dựng đất nƣớc khi ra trƣờng sau 4 năm học. Em xin hứa sẽ lao động hết mình đem những kiến thức học đƣợc phục vụ cho Tổ quốc. Em xin chân thành cảm ơn đến: Cha, mẹ ngƣời đã sinh thành và dƣỡng dục con, hỗ trợ mọi điều kiện về vật chất và tinh thần cho con trên con đƣờng học tập lịng biết ơn sâu sắc nhất. Thầy cơ của trƣờng và các thầy cơ trong Ban giám hiệu, thầy cơ trong Bộ mơn CNTT của trƣờng Đại học Dân lập Hải Phịng đã tận tình giảng dạy và tạo mọi điều kiện cho chúng em học tập trong suốt thời gian học tập tại trƣờng. Thầy Trần Ngọc Thái– Giáo viên hƣớng dẫn tiểu án tốt nghiệp đã tận tình, hết lịng hƣớng dẫn em trong suốt quá trình nghiên cứu để hồn thành đồ án tốt nghiệp này. Em mong thầy luơn luơn mạnh khoẻ để nghiên cứu và đào tạo nguồn nhân lực cho đất nƣớc. Một lần nữa em xin chân thành cảm ơn. Hải Phịng, ngày tháng năm 2009 Sinh viên thực hiện Nguyễn Thanh Tùng Nguyễn Thanh Tùng 3
  4. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng MỞ ĐẦU Hiện nay, sự kết hợp của vật lý lƣợng tử và cơ sở tốn học hiện đại đã tạo nền mĩng cho việc xây dựng máy tính lƣợng tử trong tƣơng lai. Theo các dự báo thì máy tính lƣợng tử sẽ xuất hiện vào khoảng những năm 2010-2020. Isaac L. Chuang, ngƣời đứng đầu nhĩm nghiên cứu của IBM về máy tính lƣợng tử cũng đã khẳng định “Máy tính lượng tử sẽ bắt đầu khi định luật Moore kết thúc – vào khoảng năm 2020, khi mạch được dự báo là đạt đến kích cỡ của nguyên tử và phân tử”). Với khả năng xử lý song song và tốc độ tính tốn nhanh, mơ hình máy tính lƣợng tử đã đặt ra các vấn đề mới trong lĩnh vực CNTT. Vào năm 1994, Peter Shor đã đƣa ra thuật tốn phân tích số ra thừa số nguyên tố trên máy tính lƣợng tử với độ phức tạp thời gian đa thức. Nhƣ vậy khi máy tính lƣợng tử xuất hiện sẽ dẫn đến các hệ mã đƣợc coi là an tồn hiện nay nhƣ RSA sẽ khơng cịn an tồn. Điều này đặt ra vấn đề nghiên cứu các hệ mật mới để đảm bảo an tồn khi máy tính lƣợng tử xuất hiện. Đồng thời, do máy tính lƣợng tử hiện nay mới chỉ xuất hiện trong phịng thí nghiệm, nhu cầu mơ phỏng các thuật tốn lƣợng tử trên máy tính thơng thƣờng là tất yếu. Ở Việt Nam hiện nay, các nhà tốn học cũng bƣớc đầu cĩ những nghiên cứu về tính tốn lƣợng tử và mơ phỏng tính tốn lƣợng tử trên máy tính thơng thƣờng. Ví dụ nhƣ nhĩm Quantum của trƣờng Đại học Bách Khoa Hà Nội. Tuy nhiên vẫn cịn nhiều vấn đề để mở, và việc này cần cĩ sự đầu tƣ thích đáng, tìm tịi, thực nghiệm trên cơ sở những thành tựu về lý thuyết và kinh nghiệm sẵn cĩ trên thế giới, đồng thời áp dụng vào thực tế. Nguyễn Thanh Tùng 4
  5. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Mục đích, đối tƣợng và nội dung của luận văn Trong khuơn khổ luận văn này, trên những cơ sở những thành tựu đã cĩ trên thế giới và trong nƣớc em sẽ trình bày tổng quan các nghiên cứu lý thuyết về tính tốn lƣợng tử, đồng thời mơ phỏng thuật tốn mã hĩa lƣợng tử BB84. Luận văn gồm cĩ phần mở đầu, kết luận và 04 chƣơng đề cập tới các nội dung chính nhƣ sau: Chƣơng 1: Giới thiệu tổng quan về an tồn bảo mật thơng tin,các khái niệm tốn học, các hệ mã cổ điển,các chữ ký số Chƣơng 2: Các khái niệm cơ bản về mã hĩa lƣợng tử, đặc trƣng và một số vấn đề liên quan Chƣơng 3: Mã hĩa lƣợng tử và giao thức phân phối khĩa BB84 Chƣơng 4: Mơ phỏng giao thức BB84 Nguyễn Thanh Tùng 5
  6. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng CHƢƠNG 1: CÁC KHÁI NIỆM CƠ BẢN 1.1 Một số khái niệm tốn học 1.1.1 Số nguyên tố và nguyên tố cùng nhau Số nguyên tố là số nguyên dƣơng chỉ chia hết cho 1 và chính nĩ. Ví dụ: 2, 3, 5, 7, 17, là những số nguyên tố. Hệ mật mã thƣờng sử dụng các số nguyên tố ít nhất là lớn hơn 10150. Hai số m và n đƣợc gọi là nguyên tố cùng nhau nếu ƣớc số chung lớn nhất của chúng bằng 1. Ký hiệu: gcd(m, n) = 1. Ví dụ: 9 và 14 là nguyên tố cùng nhau. 1.1.2 Đồng dƣ thức Cho a và b là các số nguyên tố, n là số nguyên dƣơng thì a đƣợc gọi là đồng dƣ với b theo modulo n nếu n|a-b (tức a - b chia hết cho n, hay khi chia a và b cho n đƣợc cùng một số dƣ nhƣ nhau). Số nguyên n đƣợc gọi là modulo của đồng dƣ. Kí hiệu: a ≡ b (mod n) Ví dụ: 67 ≡ 11 (mod 7), bởi vì 67 (mod 7) = 4 và 11 (mod 7) = 4. Tính chất của đồng dƣ: Cho a, a1, b, b1, c Z. Ta cĩ các tính chất: a ≡ b mod n nếu và chỉ nếu a và b cĩ cùng số dƣ khi chia cho n. Tính phản xạ: a ≡ a mod n. Tính đối xứng: Nếu a ≡ b mod n thì b ≡ a mod n. Tính giao hốn: Nếu a ≡ b mod n và b ≡ c mod n thì a ≡ c mod n. Nếu a ≡ a1 mod n, b ≡ b1 mod n thì a + b ≡ (a1 + b1) mod n và ab ≡ a1b1 mod n. Nguyễn Thanh Tùng 6
  7. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng * 1.1.3 Khơng gian Zn và Zn Khơng gian Zn (các số nguyên theo modulo n) Là tập hợp các số nguyên {0, 1, 2, , n-1}. Các phép tốn trong Zn nhƣ cộng, trừ, nhân, chia đều đƣợc thực hiện theo module n. Ví dụ: Z11 = {0, 1, 2, 3, , 10} Trong Z11: 6 + 7 = 2, bởi vì 6 + 7 = 13≡ 2 (mod 11). * Khơng gian Zn Là tập hợp các số nguyên p Zn, nguyên tố cùng n. * * Tức là: Zn = {p Zn | gcd (n, p) =1}, (n) là số phần tử của Zn * Nếu n là một số nguyên tố thì: Zn = {p Zn |1 ≤ p ≤ n-1} * Ví dụ: Z2 = {0, 1} thì Z2 = {1} vì gcd(1, 2) = 1. 1.1.4 Phần tử nghịch đảo Định nghĩa: Cho a Zn. Nghịch đảo của a theo modulo n là số nguyên x Zn sao cho ax ≡ 1 (mod n). Nếu x tồn tại thì đĩ là giá trị duy nhất, và a đƣợc gọi là khả nghịch, nghịch đảo của a ký hiệu là a-1. Tính chất: -1 Cho a, b Zn. Phép chia của a cho b theo modulo n là tích của a và b theo modulo n, và chỉ đƣợc xác định khi b cĩ nghịch đảo theo modulo n. Cho a Zn, a là khả nghịch khi và chỉ khi gcd(a, n) = 1. Giả sử d=gcd (a, n). Phƣơng trình đồng dƣ ax ≡ b mod n cĩ nghiệm x nếu và chỉ nếu d chia hết cho b, trong trƣờng hợp các nghiệm d nằm trong khoảng 0 đến n - 1 thì các nghiệm đồng dƣ theo modulo n/d. Ví dụ: 4-1 = 7 (mod 9) vì 4.7 ≡ 1 (mod 9) Nguyễn Thanh Tùng 7
  8. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng 1.1.5 Khái niệm nhĩm, nhĩm con, nhĩm Cyclic Nhĩm là bộ các phần tử (G, *) thỏa mãn các tính chất: Kết hợp: ( x * y ) * z = x * ( y * z ) Tồn tại phần tử trung lập e G: e * x= x * e = x , x G Tồn tại phần tử nghịch đảo x’ G: x’ * x = x * x’ = e Nhĩm con của nhĩm (G,*) là bộ các phần tử (S,*) thỏa mãn các tính chất: S G, phần tử trung lập e S . x, y S => x * y S. Nhĩm Cyclic: Là nhĩm mà mọi phần tử của nĩ đƣợc sinh ra từ một phần tử đặc biệt g G. Phần tử này đƣợc gọi là phần tử sinh (nguyên thủy), tức là: Với x G: n N mà gn = x. Ví dụ: (Z+, *) là nhĩm cyclic cĩ phần tử sinh là 1. Định nghĩa: Ta gọi Cấp của nhĩm là số các phần tử trong nhĩm đĩ. * Nhƣ vậy, nhĩm Zn cĩ cấp (n). * Nếu p là số nguyên tố thì nhĩm Zp cĩ cấp là p-1 Định nghĩa: * Cho a Zn , cấp của a ký hiệu là ord(a) đƣợc định nghĩa là số nguyên dƣơng nhỏ nhất t thoả mãn: at ≡ 1 (mod n). * * Ví dụ: Z21 ={1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}, (21) = 12 = |Z21 | * và cấp của từng thành phần trong Z21 là: * a Z21 1 2 4 5 8 10 11 13 16 17 19 20 Cấp của a 1 6 3 6 2 6 6 2 3 6 6 2 Nguyễn Thanh Tùng 8
  9. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng 1.1.6 Bộ phần tử sinh (Generator-tuple) {g1, , gk} đƣợc gọi là bộ phần tử sinh nếu mỗi gi là một phần tử sinh và những phần tử này khác nhau (gi ≠ gj nếu i ≠ j). * Ví dụ: {3, 5} là bộ phần tử sinh của Z7 , bởi vì: 1 = 36 mod 7 = 56 mod 7 2 = 32 mod 7 = 54 mod 7 3 = 31 mod 7 = 55 mod 7 4 = 34 mod 7 = 52 mod 7 5 = 35 mod 7 = 51 mod 7 6 = 33 mod 7 = 53 mod 7. * 2 khơng phải là phần tử sinh của Z7 , bởi vì: {2, 22, 23 , 24, 25 , 26} = {2,4,1,2,4,1} {1,2,4} * Tuy nhiên {1,2,4} là tập con của {1, 2, 3, 4, 5, 6} = Z7 , do đĩ số 2 đƣợc gọi là “phần tử sinh của nhĩm G(3)”, G(3) là nhĩm cĩ 3 thành phần {1,2,4}. 1.1.7 Bài tốn đại diện (Presentation problem). * Gọi g là phần tử sinh của nhĩm con G(q) thuộc Zn . Bài tốn logarit rời rạc liên quan đến việc tìm số mũ a, sao cho: a = loggh mod n (với h G(q)). Cho k>= 2, 1<=ai<= q, i = 1 k. Bài tốn đại diện là: cho h thuộc G(q), tìm {a1, , ak}, của bộ phần tử sinh {g1, , gk} , sao cho: a1 a2 ak h g1 * g2 * * gk modn {ak, , ak} đƣợc gọi là đại diện (representation). Nguyễn Thanh Tùng 9
  10. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Ví dụ: * Cho tập Z 23, thì ta cĩ thể tìm đƣợc: nhĩm con G(11)={1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18} với những phần tử sinh gi là: 2, 3, 4, 6, 8, 9, 12, 13, 16, 18. * {2, 3} là 2 phần tử sinh của nhĩm con G(11) trong Z 23. Bài tốn đại diện là với h = 13 G(11), tìm {a1, a2} sao cho: 13 2a1 *3a2 mod23 Logarit hai vế, cĩ a1*log (2) + a2*log (3) = log (13) mod 23. 2 2 Kết quả là: a1 = 2 và a2 = 2, vì 2 * 3 = 4*9 = 36 = 13 mod 23. 7 11 Hay a1 = 7 và a2 = 11, vì 2 * 3 = 128*177147 = 13 mod 23. 1.1.8 Hàm băm. Hàm băm h là hàm một chiều (one-way hash) với các đặc tính sau: Với thơng điệp đầu vào x thu đƣợc bản băm z = h(x) là duy nhất. Nếu dữ liệu trong thơng điệp x thay đổi hay bị xĩa để thành thơng điệp x’ thì h(x’) ≠ h(x). Cho dù chỉ là một sự thay đổi nhỏ hay chỉ là xĩa đi 1 bit dữ liệu của thơng điệp thì giá trị băm cũng vẫn thay đổi. Điều này cĩ nghĩa là: hai thơng điệp hồn tồn khác nhau thì giá trị hàm băm cũng khác nhau. Nội dung của thơng điệp gốc “khĩ” suy ra từ giá trị hàm băm. Nghĩa là: với thơng điệp x thì dễ dàng tính đƣợc z = h(x), nhƣng lại “khĩ” suy ngƣợc lại x nếu chỉ biết giá trị hàm băm h(x). Tính chất: Hàm băm h là khơng va chạm yếu: Nếu cho trƣớc một bức điện x, thì khơng thể tiến hành về mặt tính tốn để tìm ra một bức điện x’ ≠ x mà h(x’) = h(x).Hàm băm h là khơng va chạm mạnh: Nếu khơng cĩ khả năng tính tốn để tìm ra hai bức thơng điệp x và x’ mà x ≠ x’ và h(x) = h(x’). Nguyễn Thanh Tùng 10
  11. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng 1.2 Các khái niệm mã hĩa 1.2.1 Khái niệm mã hĩa. Ta biết rằng tin truyền trên mạng rất dễ bị lấy cắp. Để đảm bảo việc truyền tin an tồn ngƣời ta thƣờng mã hố thơng tin trƣớc khi truyền đi. Việc mã hố thƣờng theo quy tắc nhất định gọi là hệ mật mã. Hiện nay cĩ hai loại hệ mật mã mật mã cổ điển và mật mã khố cơng khai. Mật mã cổ điển dễ hiểu, dễ thực thi nhƣng độ an tồn khơng cao. Vì giới hạn tính tốn chỉ thực hiện trong phạm vi bảng chữ cái sử dụng văn bản cần mã hố (ví dụ Z26 nếu dùng các chữ cái tiếng anh, Z256 nếu dùng bảng chữ cái ASCII ). Với các hệ mã cổ điển, nếu biết khố lập mã hay thuật tốn thuật tốn lập mã, ngƣời ta cĩ thể "dễ" tìm ra đƣợc bản rõ. Ngƣợc lại các hệ mật mã khố cơng khai cho biết khố lập mã K và hàm lập mã Ck thì cũng rất "khĩ" tìm đƣợc cách giải mã. 1.2.1.1 Hệ mã hĩa. Hệ mã hĩa là hệ bao gồm 5 thành phần ( P, C, K, E, D ) thỏa mãn các tính chất sau: P (Plaitext): là tập hợp hữu hạn các bản rõ cĩ thể. C (Ciphertext): Là tập hữu hạn các bản mã cĩ thể K (Key): Là tập hợp các bản khố cĩ thể E (Encrytion): Là tập hợp các quy tắc mã hố cĩ thể D (Decrytion): Là tập hợp các quy tắc giải mã cĩ thể. Chúng ta đã biết một thơng báo thƣờng đƣợc xem là bản rõ. Ngƣời gửi sẽ làm nhiệm vụ mã hố bản rõ, kết quả thu đƣợc gọi là bản mã. Bản mã đƣợc gửi đi trên đƣờng truyền tới ngƣời nhận. Ngƣời nhận giải mã để tìm hiểu nội dung bản rõ. Dễ dàng thấy đƣợc cơng việc trên khi định nghĩa hàm lập mã và hàm giải mã: Ek(P) = C và Dk (C) = P Nguyễn Thanh Tùng 11
  12. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng 1.2.1.2 Những khả năng của hệ mật mã. o Cung cấp một mức cao về tính bảo mật, tính tồn vẹn, chống chối bỏ và tính xác thực. o Tính bảo mật: Bảo đảm bí mật cho các thơng báo và dữ liệu bằng việc che dấu thơng tin nhờ các kỹ thuật mã hố. o Tính tồn vẹn: Bảo đảm với các bên rằng bản tin khơng bị thay đổi trên đƣờng truyền tin. o Chống chối bỏ: Cĩ thể xác nhận rằng tài liệu đã đến từ ai đĩ, ngay cả khi họ cố gắng từ chối nĩ. o Tính xác thực: Cung cấp hai dịch vụ: . Nhận dạng nguồn gốc của một thơng báo và cung cấp một vài bảo đảm rằng nĩ là đúng sự thực. . Kiểm tra định danh của ngƣời đang đăng nhập một hệ thống, tiếp tục kiểm tra đặc điểm của họ trong trƣờng hợp ai đĩ cố gắng kết nối và giả danh là ngƣời sử dụng hợp pháp. 1.2.2 Các phƣơng pháp mã hĩa. 1.2.2.1 Mã hĩa đối xứng Hệ mã hố đối xứng: là hệ mã hố tại đĩ khố mã hố cĩ thể “dễ” tính tốn ra đƣợc từ khố giải mã và ngƣợc lại. Trong rất nhiều trƣờng hợp, khố mã hố và khố giải mã là giống nhau. Thuật tốn này cĩ nhiều tên gọi khác nhau nhƣ thuật tốn khố bí mật, thuật tốn khố đơn giản, thuật tốn một khố. Thuật tốn này yêu cầu ngƣời gửi và ngƣời nhận phải thoả thuận một khố trƣớc khi thơng báo đƣợc gửi đi và khố này phải đƣợc cất giữ bí mật. Độ an tồn của thuật tốn này phụ thuộc vào khố, nếu để lộ ra khố này nghĩa là bất kỳ ngƣời nào cũng cĩ thể mã hố và giải mã thơng báo trong hệ thống mã hố. Sự mã hố và giải mã của hệ mã hố đối xứng biểu thị bởi: Ek : P C Và Dk: C P Nguyễn Thanh Tùng 12
  13. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Nơi ứng dụng: Sử dụng trong mơi trƣờng mà khố đơn dễ dàng đƣợc chuyển, nhƣ là trong cùng một văn phịng. Cũng dùng để mã hố thơng tin khi lƣu trữ trên đĩa nhớ. Các vấn đề đối với Hệ mã hố đối xứng: Phƣơng pháp mã hố đối xứng địi hỏi ngƣời mã hố và ngƣời giải mã phải cùng chung một khố. Khố phải đƣợc giữ bí mật tuyệt đối. "Dễ dàng" xác định một khố nếu biết khố kia và ngƣợc lại. Hệ mã hố đối xứng khơng an tồn nếu khố bị lộ với xác xuất cao. Hệ này khố phải đƣợc gửi đi trên kênh an tồn. Vấn đề quản lý và phân phối khố là khĩ khăn, phức tạp khi sử dụng hệ mã hố đối xứng. Ngƣời gửi và ngƣời nhận phải luơn thống nhất với nhau về khố. Việc thay đổi khố là rất khĩ và dễ bị lộ. Khuynh hƣớng cung cấp khố dài mà nĩ phải đƣợc thay đổi thƣờng xuyên cho mọi ngƣời, trong khi vẫn duy trì cả tính an tồn lẫn hiệu quả chi phí, sẽ cản trở rất nhiều tới việc phát triển hệ mật mã. 1.2.2.2 Mã hĩa phi đối xứng (Mã hĩa cơng khai). Hệ mã hố khố cơng khai: là Hệ mã hố trong đĩ khố mã hố là khác với khố giải mã. Khố giải mã “khĩ” tính tốn đƣợc từ khố mã hố và ngƣợc lại. Khố mã hố gọi là khố cơng khai (Public key). Khố giải mã đƣợc gọi là khố bí mật (Private key). Nơi ứng dụng: Sử dụng chủ yếu trong việc trao đổi dữ liệu cơng khai. Các điều kiện của một hệ mã hố cơng khai: Việc tính tốn ra cặp khố cơng khai KB và bí mật kB dựa trên cơ sở các điều kiện ban đầu, phải đƣợc thực hiện một cách dễ dàng, nghĩa là thực hiện trong thời gian đa thức. Ngƣời gửi A cĩ đƣợc khố cơng khai của ngƣời nhận B và cĩ bản tin P cần gửi B, thì cĩ thể dễ dàng tạo ra đƣợc bản mã C. C = EKB (P) = EB (P) Nguyễn Thanh Tùng 13
  14. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Ngƣời nhận B khi nhận đƣợc bản mã C với khố bí mật kB, thì cĩ thể giải mã bản tin trong thời gian đa thức. P = DkB (C) = DB [EB(P)] Nếu kẻ địch biết khố cơng khai KB cố gắng tính tốn khố bí mật thì chúng phải đƣơng đầu với trƣờng hợp nan giải, đĩ là gặp bài tốn "khĩ". 1.2.3 Một số hệ mã hố cụ thể. 1.2.3.1 Hệ mã hố RSA. Cho n=p*q với p, q là số nguyên tố lớn. Đặt P = C = Zn Chọn b nguyên tố với (n), (n) = (p-1)(q-1) Ta định nghĩa: K={(n,a,b): a*b 1(mod (n))} Giá trị n và b là cơng khai và a là bí mật Với mỗi K=(n, a, b), mỗi x P, y C định nghĩa b Hàm mã hĩa: y = ek(x) = x mod n a Hàm giải mã: dk (x) = y mod n 1.2.3.2 Hệ mã hố ElGamal. Hệ mã hĩa với khố cơng khai ElGamal cĩ thể đƣợc dựa trên tuỳ ý các nhĩm mà với họ đĩ bài tốn lơgarit rời rạc đƣợc xem là “khĩ” giải đƣợc. Thơng thƣờng ngƣời ta dùng nhĩm con Gq (cấp q) của Zp; ở đĩ p, q là các số nguyên tố lớn thoả mãn q|(p-1). Ở đây giới thiệu cách xây dựng nhĩm Zp, với p là một số nguyên tố lớn. Sơ đồ: Chọn số nguyên tố lớn p sao cho bài tốn logarit rời rạc trong Zp là “khĩ” 150 * (ít nhất p = 10 ). Chọn g là phần tử sinh trong Z p . Nguyễn Thanh Tùng 14
  15. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Lấy ngẫu nhiên một số nguyên thoả mãn 1 p-2 và tính tốn h = g mod p. Khố cơng khai chính là (p, g, h), và khố bí mật là . Mã hố: khố cơng khai là (p, g, h) muốn mã hố thƣ tín m (0 m < p) Lấy ngẫu nhiên một số nguyên k, 0 k p-2. Tính tốn x = gk mod p , y = m * hk mod p. Giải mã. Để phục hồi đƣợc bản gốc m từ c = (x, y), ta làm nhƣ sau: Sử dụng khố riêng , tính tốn r = x p 1 . (Chú ý rằng r = x = x = (gk) = g k ). Phục hồi m bằng cách tính tốn m = y*r mod p. 1.2.3.3 Mã hố đồng cấu. Xét một sơ đồ mã hố xác suất. Giả sử P là khơng gian các văn bản chƣa mã hố và C là khơng gian các văn bản mật mã. Cĩ nghĩa là P là một nhĩm với phép tốn 2 ngơi và C là một nhĩm với phép tốn . Ví dụ E của sơ đồ mã hố xác suất đƣợc hình thành bởi sự tạo ra khố riêng và khố cơng khai của nĩ. Giả sử Er(m) là sự mã hố thƣ tín m sử dụng tham số (s) r ta nĩi rằng sơ đồ mã hố xác suất là ( , ) đồng cấu. Nếu với bất kỳ ví dụ E của sơ đồ này, ta cho c1 = Er1(m1) và c2 = Er2(m2) thì tồn tại r sao cho: c1 c2 = Er(m1 m2) Chẳng hạn, sơ đồ mã hố Elgamal là đồng cấu. Ở đây, P là tập tất cả các số nguyên modulo p ( P = Zp ), cịn C = {(a,b) a,b Zp }. Phép tốn là phép nhân modulo p . Đối với phép tốn 2 ngơi đƣợc định nghĩa trên các văn bản mật mã, ta dùng phép nhân modulo p trên mỗi thành phần. Hai văn bản gốc m0, m1 đƣợc mã hố: ko ko Eko(mo) = (g , h mo) k1 k1 Ek1(m1) = (g , h m1) Ở đĩ ko,k1 là ngẫu nhiên. Nguyễn Thanh Tùng 15
  16. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng ko ko k1 k1 Từ đĩ: Eko(mo) Ek1(m1) = (g , h mo) (g , h m1) = Ek(mom1) với k = ko + k1 Bởi vậy, trong hệ thống bí mật ElGamal từ phép nhân các văn bản mật mã chúng ta sẽ cĩ đƣợc phép nhân đã đƣợc mã hố của các văn bản gốc tƣơng ứng. 1.2.3.4 Mã nhị phân. Giả sử rằng Alice muốn gửi cho Bob 1 chữ số nhị phân b. Cơ ta khơng muốn tiết lộ b cho Bob ngay. Bob yêu cầu Alice khơng đƣợc đổi ý, tức là chữ số mà sau đĩ Alice tiết lộ phải giống với chữ số mà cơ ta nghĩ bây giờ. Alice mã hố chữ số b bằng một cách nào đĩ rồi gửi sự mã hố cho Bob. Bob khơng thể phục hồi đƣợc b tới tận khi Alice gửi chìa khố cho anh ta. Sự mã hố của b đƣợc gọi là một blob. Một cách tổng quát, sơ đồ mã nhị phân là một hàm : {0, 1} x X Y, trong đĩ X, Y là những tập hữu hạn. Mỗi mã hố của b là giá trị (b, k), k X. Sơ đồ mã nhị phân phải thoả mãn những tính chất sau: - Tính che đậy (Bob khơng thể tìm ra giá trị b từ (b, k)) - Tính mù (Alice sau đĩ cĩ thể mở (b, k) bằng cách tiết lộ b, k thì đƣợc dùng trong cách xây dựng nĩ. Cơ ta khơng thể mở blob bởi 0 hay 1). Nếu Alice muốn mã hố một xâu những chữ số nhị phân, cơ ta mã hố từng chữ số một cách độc lập. Sơ đồ mã hố số nhị phân mà trong đĩ Alice cĩ thể mở blob bằng 0 hay 1 đƣợc gọi là mã hố nhị phân cửa lật. Mã hố số nhị phân cĩ thể đƣợc thực hiện nhƣ sau: Giả sử một số nguyên tố lớn p, một phần tử sinh g Zp và G Zp đã biết logarit rời rạc cơ số g của G thì cả Alice và Bob đều khơng biết (G cĩ thể chọn ngẫu nhiên). Sự mã hố nhị phân : {0,1} x Zp Zp là: (b, k) = gkGb Nguyễn Thanh Tùng 16
  17. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Đặt loggG = a. Blob cĩ thể đƣợc mở bởi b bằng cách tiết lộ k và mở bởi -b bằng cách tiết lộ k-a nếu b=0 hoặc k+a nếu b=1. Nếu Alice khơng biết a, cơ ta khơng thể mở blob bằng –b. Tƣơng tự, nếu Bob khơng biết k, anh ta khơng thể xác định b với chỉ một dữ kiện (b, k) = gkGb. Sơ đồ mã hố chữ số nhị phân cửa lật đạt đƣợc trong trƣờng hợp Alice biết a. Nếu Bob biết a và Alice mở blob cho Bob thơng qua kênh chống đột nhập đƣờng truyền (untappable channel) Bob cĩ thể sẽ nĩi dối với ngƣời thứ ba về sự mã hố chữ số nhị phân b. Rất đơn giản, anh ta nĩi rằng anh ta nhận đƣợc k-a hoặc k+a (mà thực tế là k). Sơ đồ mã hố số nhị phân mà cho phép ngƣời xác minh (Bob) nĩi dối về việc mở blob, đƣợc gọi là sự mã hố nhị phân chameleon. Thay vì mã hố từng chữ số nhị phân trong sâu s một cách độc lập, Alice cĩ thể mã hố một cách đơn giản 0 ≤ s ≤ p bằng (b, k) = Gs gk. Hơn nữa, những thơng tin về số a sẽ cho Alice khả năng mở (s,k) bởi bất kì s’, k’ thoả mãn as + k = as’ + k’.1.3 Khái niệm về chữ ký điện tử 1.3.1 Định nghĩa Một sơ đồ chữ ký gồm bộ 5 (P, A, K, S, V) thoả mãn các điều kiện dƣới đây: P là tập hữu hạn các bức điện (thơng điệp) cĩ thể A là tập hữu hạn các chữ kí cĩ thể K khơng gian khố là tập hữu hạn các khố cĩ thể Sigk là thuật tốn ký P A x P y = Sigk(x) Verk là thuật tốn kiểm thử: (P, A) (Đúng, sai) Verk(x, y) = Đúng Nếu y = Sigk(x) Sai Nếu y Sigk(x) Nguyễn Thanh Tùng 17
  18. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng 1.3.2 Phân loại sơ đồ chữ ký điện tử. Chữ ký “điện tử” đƣợc chia làm 2 lớp, lớp chữ ký kèm thơng điệp (message appendix) và lớp chữ ký khơi phục thơng điệp (message recovery). Chữ ký kèm thơng điệp: Địi hỏi thơng điệp ban đầu là đầu vào của giải thuật kiểm tra. Ví dụ: chữ ký Elgamal. Chữ ký khơi phục thơng điệp: Thơng điệp ban đầu sinh ra từ bản thân chữ ký. Ví dụ: chữ ký RSA. 1.3.3 Một số sơ đồ ký số cơ bản. 1.3.3.1 Sơ đồ chữ ký Elgamal. Chọn p là số nguyên tố sao cho bài tốn log rời rạc trong Zp là khĩ. * Chọn g là phần tử sinh Z p ; a Z . Tính ga mod p. Chọn r ngẫu nhiên Z*p-1 Ký trên x: Sig(x) = ( , ), Trong đĩ = gk mod p , = (x - a ) r-1 mod (p-1). Kiểm tra chữ ký: Ver(x, , )=True gx mod p Ví dụ: Chọn p=463; g=2; a=211; 2211mod 463=249; chọn r =235; r-1=289 Ký trên x = 112 Sig(x,r) = Sig (112,235)=( , )=(16,108) = 2235 mod 463 =16 = (112-211*16)*289 mod (463-1)=108 Kiểm tra chữ ký: Ver(x, , )=True gx mod p Nguyễn Thanh Tùng 18
  19. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng = 24916* 16108 mod 463 = 132 gx mod p = 2112 mod 463 = 132 1.3.3.2 Sơ đồ chữ ký RSA. Chọn p, q nguyên tố lớn . Tính n=p.q; (n)=(p-1)(q-1). Chọn b nguyên tố cùng (n). Chọn a nghịch đảo với b; a=b-1 mod (n). Ký trên x: Sig (x) = xa mod n Kiểm tra chữ ký: b Ver (x,y)= True x y mod n Ví dụ: p=3; q=5; n=15; (n)= 8; chọn b=3; a=3 Ký x =2: Chữ ký : y = xa mod n = 23 mod 15=8 Kiểm tra: x = yb mod n = 83 mod 15 =2 (chữ ký đúng) 1.3.3.3 Sơ đồ chữ ký Schnorr. Chuẩn bị: * Lấy G là nhĩm con cấp q của Zn , với q là số nguyên tố. Chọn phần tử sinh g G sao cho bài tốn logarit trên G là khĩ giải. x Chọn x ≠ 0 làm khĩa bí mật, x Zq. Tính y = g làm khĩa cơng khai. Lấy H là hàm băm khơng va chạm. Nguyễn Thanh Tùng 19
  20. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Ký trên thơng điệp m: Chọn r ngẫu nhiên thuộc Zq Tính c = H(m, gr) Tính s = (r - c x) mod q Chữ ký Schnorr là cặp (c, s) Kiểm tra chữ ký: Với một văn bản m cho trƣớc, một cặp (c, s) đƣợc gọi là một chữ ký Schnorr hợp lệ nếu thỏa mãn phƣơng trình: c = H(m, gs*yc) Để ý rằng ở đây, c xuất hiện ở cả 2 vế của phƣơng trình 1.4 Phân phối khĩa và thỏa thuận khĩa Nhƣ chúng ta đã biết, hệ thống mã khĩa cơng khai cĩ ƣu điểm hơn hệ thống mã khĩa cổ điển ở chỗ cĩ thể cơng khai thuật tốn mã hố cho nhiều ngƣời sử dụng. Tuy nhiên, hầu hết các hệ thống mã khĩa cơng khai đều chậm hơn hệ thống mã khĩa cổ điển, chẳng hạn nhƣ DES. Vì thế thực tế các hệ thống mã khĩa riêng đƣợc sử dụng để mã các bức điện dài. Giả sử, cĩ một mạng khơng an tồn gồm n ngƣời sử dụng, cĩ trung tâm đƣợc uỷ quyền (TT) để đáp ứng những việc nhƣ xác minh danh tính của ngƣịi sử dụng, chọn và gửi khố đến ngƣời sử dụng Do mạng khơng an tồn nên cần đƣợc bảo vệ trƣớc các đối phƣơng. Đối phƣơng cĩ thể là ngƣời bị động, nghĩa là hành động của anh ta chỉ hạn chế ở mức nghe trộm bức điện truyền trên kênh. Song mặt khác, anh ta cĩ thể là ngƣời chủ động, tức là anh ta cĩ thể tráo đổi khố mật của 2 đối tác tham gia truyền tin. Ta phân biệt giữa phân phối khĩa và thỏa thuận khĩa. Phân phối khĩa là cơ chế một nhĩm chọn khĩa mật và sau đĩ truyền nĩ đến các nhĩm khác. Thoả thuận khĩa là giao thức để hai nhĩm (hoặc nhiều hơn) liên kết với nhau cùng thiết lập một khĩa mật bằng cách liên lạc trên kênh cơng khai. Mục tiêu của phân phối khố và giao thức thoả thuận khố là tại thời điểm kết thúc thủ tục, hai nhĩm đều cĩ cùng khố K song nhĩm khác khơng biết đƣợc . Nguyễn Thanh Tùng 20
  21. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng 1.4.1 Phân phối khĩa * Vấn đề. n Theo phƣơng pháp cơ bản, TT tạo ra khĩa và đƣa mỗi khố cho duy 2 nhất một cặp ngƣời sử dụng trong mạng n dùng. Nhƣ đã nêu ở trên ta cần một kênh an tồn giữa TT và mỗi ngƣời sử dụng để truyền đi các khĩa này. Nếu n lớn, giải pháp này khơng thực tế cả về lƣợng thơng tin cần truyền đi an tồn, lẫn thơng tin mà mỗi ngƣời sử dụng phải cất giữ an tồn (nghĩa là các khố mật của n – 1 ngƣời dùng khác). Nhƣ vậy, điều cần quan tâm là cố gắng giảm đƣợc lƣợng thơng tin cần truyền đi và cất giữ trong khi vẫn cho phép mỗi cặp ngƣời sử dụng U và V cĩ khả năng tính khố mật Ku,v. 1.4.1.1 Sơ đồ phân phối khố trước Blom. Ta giả thiết rằng cĩ một mạng gồm n ngƣời sử dụng. Giả sử rằng các khố đƣợc chọn trên trƣờng hữu hạn Z p , trong đĩ p là số nguyên tố (p n). Cho k là số nguyên, 1 k n-2. Giá trị k để hạn chế kích thƣớc lớn nhất mà sơ đồ vẫn duy trì đƣợc độ mật. TT sẽ truyền đi k+1 phần tử của , cho mỗi ngƣời sử dụng trên kênh an tồn (so với n-1 trong sơ đồ phân phối trƣớc cơ bản). Mỗi cặp ngƣời sử dụng U và V sẽ cĩ khả năng tính khố Ku, v = Kv, u nhƣ trƣớc đây. Điều kiện an tồn nhƣ sau: tập bất kì gồm nhiều nhất k ngƣời sử dụng khơng liên kết từ U, V phải khơng cĩ khả năng xác định bất kì thơng tin nào về Ku, v. Xét trƣờng hợp đặc biệt của sơ đồ Blom khi k =1. Nguyễn Thanh Tùng 21
  22. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng a. Sơ đồ phân phối khố Blom với k=1. 1. Số nguyên tố p cơng khai, với mỗi ngƣời sử dụng U, phần tử ru Z p là cơng khai, khác nhau. 2. TT chọn 3 phần tử ngẫu nhiên bí mật a, b, c (khơng cần khác biệt) và thiết lập đa thức: f(x, y) = (a + b*(x + y) + c*x*y) mod p. 3. Với mỗi ngƣời sử dụng U, TT tính đa thức: gu(x) = f(x, ru) mod p và truyền gu(x) đến U trên kênh an tồn. gu(x) là đa thức tuyến tính theo x, cĩ thể viết: gu(x) = f(x, ru) mod p = (a+b.(x+ ru) + c.x. ru mod p ) mod p gu(x) = au + bu*x, trong đĩ: au = a + b*ru mod p bu = b + c*ru mod p 4. Nếu U và V muốn liên lạc với nhau, họ sẽ dùng khố chung Ku, v = Kv, u = f(ru, rv) = (a + b*(ru+ rv) + c.ru.rv ) mod p. U tính Ku, v : f(ru, rv) = gu(rv). V tính Ku, v : f(ru,rv) = gv(ru). Ví dụ 1: Giả sử cĩ 3 ngƣời sử dụng là U,V và W. Chọn số nguyên tố p =17, các phần tử cơng khai của họ là ru = 12, rv = 7, rw = 1. Giả thiết rằng TT chọn ngẫu nhiên, bí mật a = 8, b = 7, c = 2. Khi đĩ đa thức f nhƣ sau: f(x, y) = (8 + 7*(x + y) + 2*x*y) mod 17. Các đa thức g của U, V, W tƣơng ứng là: gu(x) = (8 + 7*(x + 12) + 12*2*x ) mod 17 = 7 + 14*x. gv(x) = (8 + 7*(x + 7) + 7*2*x ) mod 17 = 6 + 4*x. gw(x) = (8 + 7*(x + 1) + 12*2*x ) mod 17 = 15 + 9*x. Nguyễn Thanh Tùng 22
  23. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Nhƣ vậy 3 khố là: Ku, v = f(ru,rv) = (8 + 7*(12 + 7) + 2*12*7 ) mod 17 = 3. Ku, w = f(ru,rw) =(8 + 7*(12 + 1) + 2*12*71) mod 17 = 4. Kv, w = f(rv,rw) = (8 + 7*(7 + 1) + 2*7*1 ) mod 17 = 10. Nếu U và V muốn trao đổi với nhau thì. U sẽ tính khố Ku, v nhƣ sau: gu(rv) = f(ru,rv) = 7 + 14*7 mod 17 = 3. V sẽ tính khố Ku, v nhƣ sau: gv(ru) = f(ru,rv) = 6 + 4*12 mod 17 =3. Ví dụ 2: Giả sử cĩ 3 ngƣời sử dụng là U,V và W. Chọn số nguyên tố p =83, các phần tử cơng khai của họ là ru = 42, rv = 31, rw = 53. Giả thiết rằng TT chọn ngẫu nhiên, bí mật a = 10, b = 20, c = 30. Khi đĩ đa thức f nhƣ sau: f(x, y) = (10 + 20*(x + y) + 30*x*y) mod 83. Các đa thức g của U, V, W tƣơng ứng là: gu(x) = (10 + 20*(x + 42) + 30*42*x ) mod 83 = 20 + 35*x. gv(x) = (10 + 20*(x + 31) + 30*31*x ) mod 83 = 49 + 37*x. gw(x) = (10 + 20*(x + 53) + 30*53*x ) mod 83 =74 + 33*x. Nhƣ vậy 3 khố là: Ku, v = f(ru,rv) = (10 + 20*(42 + 31) + 30*42*31 ) mod 83 =26. Ku, w = f(ru,rw) = (10 + 20*(42 + 53) + 30*42*53 ) mod 83 =49. Kv, w = f(rv,rw) = (10 + 20*(31 + 53) + 30*31*53 ) mod 83 =18. Nếu U và V muốn trao đổi với nhau thì. U sẽ tính khố Ku, v nhƣ sau: gu(rv) = f(ru,rv) = 20 + 35*31 mod 83 = 26. V sẽ tính khố Ku, v nhƣ sau: gv(ru) = f(ru,rv) = 49 + 37*42 mod 17 = 26. Nguyễn Thanh Tùng 23
  24. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Sự an tồn của sơ đồ Blom với k=1. a. Sơ đồ an tồn với 1 đối thủ. Khơng một ngƣời sử dụng nào cĩ thể xác định đƣợc thơng tin về khố của 2 ngƣời sử dụng khác. Định lý: Theo sơ đồ Blom với k =1, khố của một cặp đối tác là an tồn khơng điều kiện trƣớc bất kì ngƣời sử dụng thứ ba. Chứng minh: Giả sử ngƣời sử dụng thứ ba là W muốn thử tính khố. Ku, v = (a + b*(ru + rv) + c*ru*rv ) mod p Trong đĩ các giá trị ru, rv là cơng khai, cịn a, b, c khơng đƣợc biết. W tìm biết đƣợc các giá trị: aw = a + b*rw mod p. bw = b + c*rw mod p. Vì chúng là hệ số của đa thức gw(x) đƣợc TT gửi đến cho W. Ta sẽ chỉ ra rằng thơng tin mà W biết phù hợp với giá trị tùy ý t Z p của khố Ku, v. Xét phƣơng trình ma trận sau: 1 ru + rv rurv a t 1 rw 0 b = aw 0 1 rw c bw Phƣơng trình đầu tiên thể hiện giả thiết rằng Ku,v = t, các chƣơng trình thứ hai và ba chứa thơng tin cho thấy W biết a, b và c từ gw(x). Định thức của ma trận hệ số là: 2 rw + rurv – (ru + rv)rw = (rw - ru)(rw - rv). Các phép số học đƣợc thực hiện trong . Vì rw ru và rw rv nên định thức ma trận hệ số khác khơng. Do đĩ phƣơng trình ma trận cĩ nghiệm duy nhất cho a, b, c. Nĩi cách khác, bất kì giá trị t nào thuộc cũng cĩ thể nhận là khố Ku,v. Nguyễn Thanh Tùng 24
  25. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng b. Sơ đồ khơng an tồn với liên minh 2 đối thủ. Liên minh của 2 ngƣời sử dụng W, X sẽ cĩ khả năng xác định khố Ku,v bất kì , ở đây W, X U, V = 0. W và X cùng biết rằng: aw = a + b*rw. bw = b + c*rw. ax = a + b*rx. bx = b + c*rx. Nhƣ vậy, họ cĩ bốn phƣơng trình trong đĩ ba ẩn chƣa biết và dễ dàng tính ra nghiệm duy nhất cho a, b, c. Một khi đã biết a, b, và c, họ cĩ thể thiết lập đa thức f(x, y) và tính khố bất kì mà họ muốn . c. Cách thức khắc phục liên minh k đối thủ. Để tạo lập sơ đồ cĩ độ an tồn chống lại đƣợc liên minh k đối thủ, TT sẽ dùng đa thức f(x, y) cĩ dạng: k k i j f (x, y) ai, j x y mod p. i 0 j o Trong đĩ: ai,j Z p (0 i k, 0 j k) và ai,j = aj,i với mọi i, j Phần cịn lại của giao thức khơng thay đổi. 1.4.1.2 Sơ đồ phân phối khố trước Diffie-Hellman. a. Sơ đồ. Ta sẽ mơ tả một sơ đồ phân phối khố trƣớc là cải tiến của giao thức trao đổi khố Diffie-Hellman và gọi nĩ là sơ đồ phân phối khố trƣớc Diffie-hellman. Sơ đồ này an tồn về mặt tính tốn vì nĩ liên quan đến bài tốn logarit rời rạc “khĩ giải”. Mơ tả sơ đồ trên (p là số nguyên tố), bài tốn logarit rời rạc trong là khĩ giải. * Giả sử là phần tử nguyên thuỷ của Z p , trong đĩ các giá trị và p là cơng khai. Trong sơ đồ này, ID(U) là thơng tin định danh nào đĩ cho ngƣời sử dụng U trên mạng, chẳng hạn nhƣ tên, địa chỉ thƣ điện tử, số điện thoại Cũng nhƣ vậy, mỗi ngƣời sử dụng U đều cĩ số mũ mật au (trong đĩ 0 au p - 2) và một giá trị cơng khai tƣơng ứng : Nguyễn Thanh Tùng 25
  26. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng au b u = mod p. TT cĩ sơ đồ chữ ký với thuật tốn xác minh (cơng khai) verTT và thuật tốn kí mật sigTT. Ta giả thiết rằng tất cả thơng tin đều đƣợc chia nhỏ ra nhờ dùng hàm hash cơng khai trƣớc khi nĩ đƣợc kí. Thơng tin về ngƣời sử dụng U sẽ đƣợc xác thực bằng cách dùng dấu xác nhận của TT, trong đĩ cĩ chữ ký của TT. Mỗi ngƣời sử dụng U sẽ cĩ một dấu xác nhận : C(U) = (ID(U), bu, sigTT (ID(U), bu)) . Trong đĩ bu đƣợc thiết lập theo mơ tả ở phần trên. Dấu xác nhận của ngƣời sử dụng U sẽ đƣợc đĩng vào khi U nối mạng. Cĩ thể lƣu các dấu xác nhận trong cơ sở dữ liệu cơng khai hoặc mỗi ngƣời sử dụng lƣu dấu xác nhận của chính họ. Chữ ký xác nhận của TT cho phép bất kì ai trên mạng đều cĩ thể xác minh đƣợc thơng tin trên nĩ. U và V rất dễ dàng tính ra khố chung: au av Ku,v mod p Sơ đồ phân phối khố trước của Diffie- Hellman. * 1. Số nguyên tố p, phần tử nguyên thuỷ Z p là cơng khai. 2. V tính: au av av Ku,v mod p = bu mod p bu cơng khai nhận từ dấu xác nhận của U, giá trị av mật riêng của V. 3. U tính: a au av u Ku,v mod p = bv mod p bv cơng khai nhận từ dấu xác nhận của V, giá trị au mật riêng của U. Nguyễn Thanh Tùng 26
  27. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Ví dụ: * Cho số nguyên tố p = 25307, phần tử nguyên thuỷ = 2 Z p , chúng là cơng khai. Giả sử U chọn au = 3578. Sau đĩ U tính: au 3578 bu = mod p = 2 mod 25307 = 6113. Giả sử V chọn av = 19956. Sau đĩ V tính: av 19956 bv = mod p = 2 mod 25307 = 7984. U tính khố: au 3578 Ku, v = bv mod p = 7984 mod 25307 = 3694. V tính khố: av 19956 Ku,v = bu mod p = 6113 mod 25307 = 3694. Hai giá trị khố bằng nhau. Sự an tồn của sơ đồ. Chữ ký của TT trên dấu xác thực của ngƣời dùng U ngăn chặn W cĩ thể biến đổi thơng tin nào đĩ trên dấu xác thực của ngƣời sử dụng U. Vì thế ta chỉ cần lo lắng trƣớc những tấn cơng thụ động. Nhƣ vậy câu hỏi là: liệu W cĩ thể tính Ku, v nếu W U,V hay khơng. Mặt khác, khi biết và av mod p thì cĩ khả năng tính đƣợc au av mod p hay khơng? Vấn đề này gọi là bài tốn Diffie-Hellman, nĩ đƣợc mơ tả hình thức nhƣ sau: Bài tốn: * I = (p, , , ), trong đĩ p là số nguyên tố, Z p là phần tử nguyên thuỷ, cịn , Mục tiêu: Tính log mod p ( log mod p ) . Rõ ràng, sơ đồ phân khối khố trƣớc Diffie-Hellman là an tồn trƣớc đối phƣơng thụ động khi và chỉ khi bài tốn Diffie-Hellman khĩ giải. Nếu W cĩ thể xác định đƣợc au từ bu hoặc av từ bv thì anh ta cĩ thể tính Ku,v một cách chính xác nhƣ U hoặc V. Song cả hai tính tốn này đều là các trƣờng hợp của bài tốn logarit rời rạc. Vì thế chỉ cần bài tốn logarit rời rạc trong Z p là bài tốn khĩ giải, thì sơ đồ phân phối khố trƣớc Diffie-Hellman sẽ an tồn trƣớc kiểu tấn cơng này. Tuy nhiên, giả định cho rằng thuật tốn bất kì giải đƣợc Nguyễn Thanh Tùng 27
  28. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng bài tốn Diffie-Hellman thì cũng cĩ thể giải đƣợc bài tốn logarith rời rạc vẫn chƣa đƣợc chứng minh. (Điều này cũng tƣơng tự nhƣ tình huống với RSA, trong đĩ giả định cho rằng việc phá RSA tƣơng đƣơng đa thức với bài tốn phân tích số cũng khơng đƣợc chứng minh). Theo nhận xét trên, bài tốn Diffie-Hellman khơng khĩ hơn bài tốn logarit rời rạc. Mặc dù khơng thể nĩi chính xác bài tốn này khĩ nhƣ thế nào song ta cĩ thể nĩi rằng độ an tồn của nĩ tƣơng đƣơng với độ mật của hệ mã hố Elgamal. Định lý: Việc phá hệ mã hố Elgamal tƣơng đƣơng với việc giải bài tốn Diffie- Hellman. Chứng minh: Theo cách mã hĩa và giải mã của hệ mã hố Elgamal ta cĩ: Khố mã K = (p, , a, ), = a mod p trong đĩ a bí mật cịn p, và cơng khai. Với số ngẫu nhiên bí mật k Z p 1 ta cĩ : ek(x, k) = (y1, y2). k k Trong đĩ: y1 = mod p và y2 = x* mod p. * a –1 Với y1, y2 Z p thì dk(y1, y2) = y2 * (y1 ) mod p. 1. Giả sử cĩ thuật tốn A để giải bài tốn Diffie-Hellman và cĩ phép mã Elgamal (y1, y2). Áp dụng thuật tốn A với các đầu vào p, , y1, và . Khi đĩ ta nhận đƣợc giá trị: k a ka k A(p, , y1, ) = A(p, , , ) = mod p = mod p Khi đĩ, phép giả mã (y1, y2) cĩ thể dễ dàng tính nhƣ sau: k –1 x = y2( ) mod p. 2. Đối lập lại, giả thiết rằng ta cĩ thuật tốn B để thực hiện giải mã Elgamal, nghĩa là B tính các đầu vào p, , y1, và y2 và tính lƣợng: log –1 x = y2( y1 ) mod p. Áp dụng các đầu vào p, , và đối với bài tốn Diffie-Hellman, dễ dàng nhận thấy: B(p, , , , 1) –1 = 1(( log ) –1 ) –1 mod p = mod p. Nguyễn Thanh Tùng 28
  29. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng 1.4.1.3 Sơ đồ phân phối khố trực tiếp Kerboros. Nếu mỗi cặp ngƣời sử dụng khơng muốn tính một khố cố định nhƣ trong phƣơng pháp phân phối trƣớc khố thì cĩ thể dùng phƣơng pháp trực tiếp, trong đĩ khố của phiên làm việc mới chỉ đƣợc tạo ra mỗi khi hai ngƣời sử dụng muốn liên lạc với nhau (gọi là tính tƣơi mới của khố). Dùng phân phối khố trực tiếp, ngƣời sử dụng mạng khơng cần lƣu các khố khi muốn liên lạc với những ngƣời sử dụng khác (Tuy nhiên mỗi ngƣời đều đƣợc chia sẻ khố với TT). Khĩa của phiên làm việc (khố session) sẽ đƣợc truyền đi theo yêu cầu của TT. Đĩ là sự đáp ứng của TT để đảm bảo khố tươi. Sơ đồ Kerboros. Kerboros là hệ thống dịch vụ khố phổ cập dựa trên mã khố riêng. Mỗi ngƣời sử dụng U sẽ chia sẻ khố DES mật Ku cho TT. Mọi thơng báo cần truyền đƣợc mã hố theo chế độ xích khối (CBC). ID(U) chỉ thơng tin định danh cơng khai cho U. Khi cĩ yêu cầu khố session gửi đến, TT sẽ tạo ra một khố session mới ngẫu nhiên K. Cũng nhƣ vậy TT sẽ ghi lại thời gian khi cĩ yêu cầu T và chỉ ra thời gian tồn tại L để K cĩ hiệu lực. Điều đĩ cĩ nghĩa là khố K chỉ cĩ hiệu lực từ T đến T+L. Tất cả thơng tin này đều đƣợc mã hố và truyền đến U và V. 1. U yêu cầu TT khố session để liên lạc với V. 2. TT chọn một khố session ngẫu nhiên K, thời gian hệ thống T và thời gian tồn tại L. 3. TT tính: m = e (K, ID(V), T, L) 1 Ku và m = e (K, ID(U), T, L) 2 Kv sau đĩ gửi m1 và m2 tới U. 4. U dùng hàm giải mã d để tính K, T, L và ID(U) từ m . Ku 1 Sau đĩ anh ta tính: m3 = eK(ID(U), T) và gửi m3 đến V cùng với bức điện m mà anh ta nhận đƣợc từ TT. 2 5. V dùng hàm giải mã d K để tính K, T, L và ID(U) từ m2. v Sau đĩ dùng dK để tính T và ID(U) từ m3 và kiểm tra xem 2 giá trị của T và 2 giá trị của ID(U) cĩ bằng nhau khơng. Nếu đúng thì V tính : m = e (T + 1) và gửi nĩ đến U. 4 K 6. U giải mã m4 bằng dK và xác minh thấy kết quả bằng T+ 1. Nguyễn Thanh Tùng 29
  30. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Thực hiện giao thức 1. Thơng tin truyền đi trong giao thức đƣợc minh hoạ nhƣ sau: m = e (K, ID(V), T, L) m = e (ID(U), T) 1 Ku 3 K m = e (K, ID(U), T, L) m = (K, ID(U), T, L) 2 Kv 2 TA U V m4= eK(T + 1) 2. TT tạo ra K, T và L trong bƣớc 2. 3. Trong bƣớc 3 thơng tin này cùng với ID(V) đƣợc mã hố bằng khố Ku (đƣợc U và TT chia sẻ) để tạo lập m1. Cũng nhƣ vậy, K, T, L và ID(U) đƣợc mã hố bằng Kv (đƣợc V và TT chia sẻ) để lập m2. Cả hai bức điện đã mã hố này đƣợc gửi đến U. 4. U cĩ thể dùng khố của mình để giải mã m1, để nhận đƣợc K, T, L. Anh ta xác minh xem thời gian hiện tại cĩ nằm trong khoảng T đến T + L hay khơng. Anh ta cũng kiểm tra khố session K đƣợc phát ra cho liên lạc giữa anh ta và V bằng cách xác minh thơng tin ID(V) đã giải mã từ m1. Tiếp theo, U sẽ làm trễ thời gian m2 đến V. Cũng nhƣ vậy, anh ta sẽ dùng khố session K mới để mã T và ID(U) và gửi kết quả m3 tới V. 5. Khi V nhận đƣợc m2 và m3 từ U thì V sẽ giải mã m2 thu đƣợc T, K, L và ID(U). Khi đĩ V sẽ dùng khố session mới K để giải mã m3 và xác minh xem T và ID(U) nhận đƣợc từ m2 và m3 cĩ nhƣ nhau khơng. Điều này đảm bảo cho V rằng khố session đƣợc mã từ m2 cũng là khố đã dùng để mã m3. Khi đĩ V dùng khố K để mã T + 1 và gửi kết quả m4 trở về U. 6. Khi U nhận đƣợc m4, anh ta dùng K để giải mã nĩ và xác minh xem kết quả cĩ bằng T + 1 khơng. Điều này đảm bảo cho U là khố session K đã đƣợc truyền thành cơng đến V vì K đã đƣợc dùng để tạo ra m4. Nguyễn Thanh Tùng 30
  31. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Sự an tồn của sơ đồ. 1. Chức năng khác nhau của các thơng báo trong giao thức: + m1 và m2 dùng để đảm bảo an tồn trong việc truyền khố session. + m3 và m4 dùng để khẳng định khố, nghĩa là cho phép U và V cĩ thể thuyết phục nhau rằng họ sở hữu cùng một khố session K. Thời gian hệ thống T và thời hạn L để ngăn đối phƣơng tích cực khỏi “lƣu” thơng báo cũ nhằm tái truyền lại sau này. Đây là phƣơng pháp hiệu quả vì các khố khơng đƣợc chấp nhận khi chúng quá hạn. 2. Mọi ngƣời sử dụng trong mạng đều phải cĩ đồng hồ đồng bộ với nhau vì cần cĩ thời gian hiện tại để xác định khố session K cho trƣớc là hợp lệ. Thực tế, rất khĩ cĩ đƣợc sự đồng bộ hồn hảo, nên phải cho phép cĩ khoảng thay đổi nào đĩ về thời gian. 1.4.2 Thỏa thuận khĩa 1.4.2.1 Sơ đồ trao đổi khố Diffie-Hellman. Nếu khơng muốn dùng dịch vụ khố trực tiếp thì phải dùng giao thức thoả thuận khố để trao đổi khố mật. Giao thức thoả thuận khố nổi tiếng nhất là giao thức trao đổi khố Diffie-Hellman. Sơ đồ. * Giả sử rằng p là số nguyên tố, là phần tử nguyên thuỷ Z p và chúng đều cơng khai. 1. U chọn au ngẫu nhiên, bí mật ( 0 au p – 2). 2. U tính : au mod p và gửi nĩ đến V. 3. V chọn av ngẫu nhiên, bí mật ( 0 av p – 2). 4. V tính : av mod p và gửi nĩ đến U. 5. U tính khố K = ( av ) au mod p. 6. V tính khố K = ( au ) av mod p. Cuối giao thức, U và V tính ra cùng một khố: K = auav mod p. Nguyễn Thanh Tùng 31
  32. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Giao thức này cũng tƣơng tự với sơ đồ phân phối trƣớc khố của Diffie- Hellman đã đƣợc mơ tả. Sự khác nhau ở chỗ các số mũ au, av của U và V đều đƣợc chọn lại mỗi lần thực hiện giao thức này thay vì cố định. Nhƣ vậy cả U và V đều đƣợc đảm bảo khố tươi vì khố session phụ thuộc vào cả hai số ngẫu nhiên bí mật au và av. Thơng tin trao đổi trong giao thức đƣợc mơ tả nhƣ sau: a u U av V Sự an tồn của sơ đồ. 1. Hạn chế: chưa cĩ xác thực danh tính. Giao thức này dễ bị tổn thƣơng trƣớc đối phƣơng tích cực – những ngƣời sử dụng cách tấn cơng “kẻ xâm nhập vào giữa cuộc”. Đĩ là tình tiết của vở “The Lucy show”, trong đĩ nhân vật Vivian Vance đang dùng bữa tối với ngƣời bạn, cịn Lucille Ball đang trốn dƣới bàn. Vivian và ngƣời bạn của cơ đang cầm tay nhau dƣới bàn. Lucy cố tránh bị phát hiện đã nắm lấy tay của cả hai ngƣời, cịn hai ngƣời trên bàn vẫn nghĩ rằng họ đang cầm tay nhau. Cuộc tấn cơng kiểu “kẻ xâm nhập vào giữa cuộc“ trên giao thức trao đổi khố Diffie-Hellman hoạt động cũng nhƣ vậy. W sẽ ngăn chặn các bức điện trao đổi giữa U và V và thay thế bằng các bức điện của anh ta. Ta cĩ sơ đồ nhƣ sau: ' a u ' a v W a U v V ' Tại thời điểm của cuối giao thức, U thiết lập thực sự khố mật au av cùng ' với W, cịn V thiết lập khố mật a u av với W. Khi U cố giải mã bức điện để gửi cho V, W cũng cĩ khả năng giải mã nĩ song V thì khơng thể, (tƣơng tự tình huống nắm tay nhau nếu V gửi bức điện cho U). Nguyễn Thanh Tùng 32
  33. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng 2. Cải tiến: Bổ sung xác thực danh tính. Điều cơ bản đối với U và V là bảo đảm rằng, họ đang trao đổi khố cho nhau mà khơng cĩ W. Trƣớc khi trao đổi khố, U và V cĩ thể thực hiện những giao thƣc tách bạch để thiết lập danh tính cho nhau. Tuy nhiên, điều này cĩ thể đƣa đến việc khơng bảo vệ đƣợc trƣớc tấn cơng “kẻ xâm nhập giữa cuộc” nếu W vẫn duy trì một cách đơn giản sự tấn cơng thụ động cho đến khi U và V đã chứng minh danh tính của họ cho nhau. Vì thế giao thức thoả thuận khố tự nĩ cần xác thực đƣợc các danh tính của những ngƣời tham gia cùng lúc khố đƣợc thiết lập. Giao thức nhƣ vậy đƣợc gọi là giao thức thoả thuận khố đã xác thực. 1.4.2.2 Giao thức thoả thuận khố trạm tới trạm. Phần này sẽ mơ tả một giao thức thoả thuận khố là cải tiến của sơ đồ trao đổi khố Diffie-Hellman, bổ sung xác thực danh tính C(U). Sơ đồ. * Giả sử p là số nguyên tố, là phần tử nguyên thuỷ Z p . Trong đĩ p, cơng khai và nĩ dùng với các dấu xác nhận. Mỗi ngƣời sử dụng U sẽ cĩ một sơ đồ chữ ký với thuật tốn xác minh veru. TT cũng cĩ sơ đồ chữ ký với thuật tốn xác minh cơng khai verTT . Mỗi ngƣời sử dụng U cĩ dấu xác nhận: C(U) = (ID(U), veru , sigTT(ID(U), veru)). Nguyễn Thanh Tùng 33
  34. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Trong đĩ ID(U) là thơng tin định danh cho U. 1. U chọn số ngẫu nhiên a , bí mật ( 0 a p – 2). u u 2. U tính: mod p và gửi nĩ đến V. 3. V chọn số ngẫu nhiên av, bí mật ( 0 av p – 2). 4. V tính: mod p K = ( au ) av mod p yv = sigv( , ) 5. V gửi (C(V), , yv) đến U. 6. U tính: K = ( av ) au mod p U dùng verv để xác minh yv và xác minh C(V) nhờ . verTT 7. U tính: yu = sigu( , ) và gửi (C(U), yu) đến V. 8. V xác minh yu bằng veru và xác minh C(U) bằng verTT. Thơng tin trao đổi trong sơ đồ trạm đến trạm (STS) đƣợc minh hoạ nhƣ sau: Đây là giao thức 3 lần truyền tin. au av U , sigv( , ) V sigu( , ) Nguyễn Thanh Tùng 34
  35. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Sự an tồn của sơ đồ. 1. Xét cách bảo vệ trƣớc tấn cơng kẻ xâm nhập giữa cuộc. ' Nhƣ trƣớc , W sẽ chặn bắt au và thay nĩ bằng a u . Sau đĩ W nhận ' a a v đƣợc v , sigv( , ) từ V. Anh ta cũng muốn thay bằng nhƣ trƣớc đây. Tuy nhiên điều này cĩ nghĩa anh ta cũng phải thay sigv( , ) bằng sigv( , ). Đáng tiếc là đối với W, anh ta khơng thể tính chữ ký của V trên ( , ) vì khơng biết thuật tốn ký sigv của V. Tƣơng tự, W khơng thể thay sigu( , ) bằng sigv( , ) do anh ta khơng biết thuật tốn ký của U. Minh hoạ bằng sơ đồ sau: U , sigv( , )=? W , sigv( , ) V sigu( , ) sigu( , ) = ? Đĩ là cách sử dụng các chữ ký mà khơng sợ kiểu tấn cơng kẻ xâm nhập giữa cuộc. 2. Giao thức, nhƣ mơ tả khơng đƣa ra sự khẳng định khố. Tuy nhiên, dễ dàng biến đổi để thực hiện đƣợc điều đĩ bằng cách: Trong bƣớc 4 mã hố yv bằng khố session K: yv = eK(sigv( , )) = eK(yv). Trong bƣớc 7 mã hố yu bằng khố session K: yu = eK(sigu( , )) = eK(yu). Nguyễn Thanh Tùng 35
  36. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng 1.4.2.3 Giao thức thoả thuận khố MTI. Matsumoto, Takashima và Imai đã xây dựng giao thức thoả thuận khố đáng chú ý, bằng cách biến đổi giao thức trao đổi khố của Diffie-Hellman. Giao thức này gọi là MTI. Giao thức khơng địi hỏi U và V phải tính bất kỳ chữ ký nào. Chúng là các giao thức hai lần vì chỉ cĩ hai lần truyền thơng tin riêng biệt (một từ U đến V và một từ V đến U). Giao thức STS là giao thức ba lần truyền tin. Sơ đồ. * Giả thiết p là số nguyên tố, là phần tử nguyên thuỷ Z p . Các giá trị này cơng khai. Mỗi ngƣời sử dụng U đều cĩ định danh ID(U), số mũ bí mật au (0 au p -2) và giá trị cơng khai tƣơng ứng: au bu = mod p. TT cĩ sơ đồ chữ ký với thuật tốn xác minh (cơng khai) verTT và thuật tốn ký mật sigTT. Mỗi ngƣời sử dụng U sẽ cĩ dấu xác nhận: C(U) = (ID(U), bu , sigTT (ID(U), bu)). 1. U chọn ngẫu nhiên ru , 0 ru p – 2 ru và tính: su = mod p. 2. U gửi (C(U), su) đến V. 3. V chọn ngẫu nhiên rv , 0 rv p – 2 rv và tính: sv = mod p. 4. V gửi (C(V), sv) đến U. 5. U tính khố: au ru K = sv *bv mod p. U nhận đƣợc giá trị bv từ C(V). 6. V tính khố: a r K = s v *b v mod p. u u V nhận đƣợc giá trị bu từ C(U). Cuối giao thức U và V đều tính cùng một khố : K = ru *av rv *au mod p. Thơng tin đƣợc truyền trong giao thức: C(U), ru mod p U r V C(V), v mod p Nguyễn Thanh Tùng 36
  37. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Sự an tồn của sơ đồ. 1. Độ mật của giao thức MTI trƣớc tấn cơng thụ động đúng bằng bài tốn Diffie-Hellman. Cũng nhƣ nhiều giao thức, việc chứng minh tính an tồn trƣớc tấn cơng chủ động khơng phải đơn giản. Khi khơng dùng chữ ký trong suốt quá trình thực hiện giao thức, cĩ thể xuất hiện tình huống khơng cĩ sự bảo vệ nào trƣớc tấn cơng xâm nhập vào điểm giữa. 2. Hãy xét giao thức MTI, W cĩ thể tráo đổi các giá trị mà U và V gửi cho nhau. Minh họa bằng sơ đồ sau: ' C(U), ru C(U), r u W U ' V C(V), r v C(U), rv Trong trƣờng hợp này, U và V sẽ tính các khố khác nhau: U tính khố: ' K = ru av rv au mod p. V tính khố: ' K = r u av rv au mod p. Tuy nhiên, W khơng thể tính tốn ra khố của U và V vì chúng địi hỏi phải biết số mũ mật au và av tƣơng ứng. Thậm chí ngay cả khi U và V tính ra các khố khác nhau (dĩ nhiên là khơng dùng chúng) thì W cũng khơng thể tính đƣợc khố nào trong chúng. Nĩi cách khác, cả U và V đều đƣợc đảm bảo rằng, ngƣời sử dụng khác trên mạng chỉ cĩ thể tính đƣợc khố mà họ tính đƣợc (đĩ là các khố rởm). Tính chất này cịn đƣợc gọi là xác thực khố ẩn (implicit key authentication). Nguyễn Thanh Tùng 37
  38. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Ví dụ: Giao thức thoả thuận khố MTI: * Giả sử số nguyên tố p = 27803, = 5 là phần tử nguyên thuỷ Z p . U chọn bí mật au = 21131. Sau đĩ tính: 21131 bu = 5 mod 27803 = 21420. đƣợc đặt trên giấy xác nhận của U. V chọn bí mật av = 17555. Sau đĩ tính: 17555 bv = 5 mod 27803 = 17100. đƣợc đặt trên giấy các nhận của V. Giả sử rằng U chọn ru = 169, tính: 169 su = 5 mod 27803 = 6268. Sau đĩ U gửi giá trị su đến V. Giả sử rằng V chọn rv = 23456, tính: 23456 sv = 5 mod 27803 = 26759. Sau đĩ V gửi giá trị sv đến U. U tính khố: au ru Ku, v = sv *bv mod p = 26759 21131 17100 169 mod 27803 = 21600. V tính khố: av rv Ku, v = su *bu mod p = 626817555 21420 23456 mod 27803 = 21600. Nhƣ vậy U và V đã tính cùng một khố. Nguyễn Thanh Tùng 38
  39. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng 1.4.2.4 Thoả thuận khố dùng các khố tự xác nhận. Phần này mơ tả phƣơng pháp thoả thuận khố do Girault đƣa ra khơng cần dấu xác nhận. Giá trị của khố cơng khai và danh tính ngƣời sử hữu nĩ sẽ ngầm xác thực lẫn nhau. Sơ đồ Girault kết hợp các tính chất của RSA và logarit rời rạc. Sơ đồ. Giả sử p, q, p1, q1 là các số nguyên tố lớn. Trong đĩ n = p*q, p = 2p1 + 1, q = 2q1 + 1. * * Nhĩm nhân Z n là đẳng cấu với Z p . Bậc cực đại của phần tử bất kỳ trong bởi vậy là bội số chung nhỏ nhất của p-1 và q-1 hoặc 2p1q1. Cho là phần tử cĩ bậc 2p1q1. Khi đĩ nhĩm con cyclic của do tạo ra là thiết lập thích hợp của bài tốn logarit rời rạc. Trong sơ đồ Girault, chỉ cĩ TT biết đƣợc phân tích nhân tử của n. Các giá trị n, cơng khai, cịn p, q, p1 và q1 là bí mật. TT chọn số mũ cơng khai RSA, ký kiệu là e. Số mũ giải mã tƣơng ứng bí mật là d (trong đĩ d = e –1 mod (n) ). Mỗi ngƣời sử dụng U cĩ một định danh ID(U). U nhận đƣợc khố tự xác nhận cơng khai pu từ TT nhƣ sau: 1. U chọn một số mũ bí mật au và tính: au bu = mod n. 2. U chuyển au và bu tới TT. 3. TT tính: d pu = (bu – ID(U)) mod n. 4. TT chuyển pu cho U. Ở đây, U cần TT giúp đỡ để tạo pu. Chú ý rằng, bu cĩ thể tính đƣợc từ pu và ID(U) bằng thơng tin cơng khai cĩ sẵn. e bu = pu + ID(U) mod n. Nguyễn Thanh Tùng 39
  40. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Giao thức thoả thuận khố Girault: 1. U chọn ngẫu nhiên, bí mật ru và tính: su = mod n. 2. U gửi ID(U), pu và su tới V. 3. V chọn ngẫu nhiên, bí mật rv và tính: sv = mod n. 4. V gửi ID(V), pv và sv tới U. 5. U tính khố: au e ru K = sv ( pv ID(V )) mod n. 6. V tính khĩa: a e K = s v ( p ID(U))rv mod n. u u Thơng tin đƣợc truyền trong giao thức nhƣ sau: ru ID(U), pu , mod n U rv ID(V), pv , mod n V Cuối giao thức, U và V tính khố: K = ru av rv au mod n. Ví dụ: Giả sử p = 839, q = 863. Khi đĩ n = p*q = 839*863 = 724057. (n) = (p - 1)*(q - 1) = 838*862 = 722356. Giả sử TT chọn d =125777 làm số mũ giải mã RSA, thì e = 84453. Giả sử U cĩ ID(U) = 500021 và au = 111899. au 111899 U tính: bu = mod n = 5 mod 724057 = 488889. d Và pu = (bu – ID(U)) = 650704. V cĩ ID(V) = 500022 và av = 123456. av 123456 V tính: bv = mod n = 5 mod 724057 = 111692. d Và pv = (bv – ID(V)) = 683556. Nguyễn Thanh Tùng 40
  41. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Bây giờ U và V muốn trao đổi khố. Giả sử U chọn ru = 5638, tính: 5638 su = 5 mod 724057 = 171007. V chọn rv = 356935, tính: 356935 sv = 5 mod 724057 = 320688. Khi đĩ cả U lẫn V sẽ tính cùng một khố: K = 42869. Sự an tồn của sơ đồ. Xét cách các khĩa tự xác thực chống lại một kiểu tấn cơng: 1. Vì các giá trị bu , pu và ID(U) khơng đƣợc TT ký nên khơng cĩ cách nào để ai đĩ xác minh trực tiếp tính xác thực của chúng. Giả thiết thơng tin này bị W (ngƣời muốn giả danh U, tức là khơng hợp ’ tác với TT để tạo nĩ). Nếu W bắt đầu bằng ID(U) và giá trị giả mạo b u. Khi ’ ’ đĩ khơng cĩ cách nào để W tính đƣợc số mũ a u tƣơng ứng với b u nếu bài tốn logarit rời rạc khĩ giải. ’ Khơng cĩ a u thì W khơng thể tính đƣợc khố. 2. Nếu W hoạt động nhƣ kẻ xâm nhập giữa cuộc thì W sẽ cĩ thể ngăn đƣợc U và V tính ra khố chung, song W khơng thể đồng thời thực hiện các tính tốn của U và V. Nhƣ vậy, sơ đồ cho khả năng xác thực ngầm nhƣ giao thức MTI. 3. Theo sơ đồ trên, TT cĩ thể tính pu trực tiếp từ bu mà khơng cần biết au, song điều quan trọng ở đây là TT sẽ đƣợc thuyết phục rằng, U biết au trƣớc khi TT tính pu cho U. 4. Sơ đồ cĩ thể bị tấn cơng nếu TT phát bừa bãi các khố cơng khai pu cho những ngƣời sử dụng mà khơng kiểm tra trƣớc xem họ cĩ sở hữu các au tƣơng ứng với các bu của họ hay khơng. ’ Giả sử W chọn một giá trị giả mạo a u và tính giá trị tƣơng ứng: ' ’ a u b u = mod n. Anh ta cĩ thể xác định khố cơng khai tƣơng ứng: ’ ’ d p u = (b u – ID(U)) mod n. ’ ’ W sẽ tính: b w = b u – ID(U) + ID(W). ’ và sau đĩ đƣa b w và ID(W) tới TT. Giả sử TT phát ra khố cơng khai cho W là: ’ ’ d p w = (b w – ID(W)) mod n Nguyễn Thanh Tùng 41
  42. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng ’ ’ Nhờ dùng yếu tố: b w – ID(W) b u – ID(U) (mod n) ’ ’ Cĩ thể suy ra rằng : p w = p u . 5. Giả sử U và V thực hiện giao thức cịn W thay thế thơng tin nhƣ sau: ' ru ’ r u ID(U), pu , mod n ID(U), pu , mod n U rv W ID(V), pv , mod n ID(V), pv , mod n V W V sẽ tính khố: ' ' K’ = r u av rva u mod n. U sẽ tính khố: K = ru av rvau mod n. W cĩ thể tính khố: ' ' a u e r u K’ = sv ( pv ID(V )) mod n. Nhƣ vậy, W và V chia sẻ nhau một khố, song V nghĩ anh ta đang chia sẻ khố với U. Nhƣ vậy, W sẽ cĩ thể giải mã đƣợc các bức điện mà V gửi cho U. Nguyễn Thanh Tùng 42
  43. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng CHƢƠNG 2 CÁC KHÁI NIỆM CƠ BẢN VỀ MÃ HĨA LƢỢNG TỬ 2.1 Ký hiệu Bra-Ket Ký hiệu Bra-ket, đƣợc đƣa ra bởi Paul Dirac (do vậy cịn đƣợc gọi là ký hiệu Dirac). Ký hiệu Bra-ket là ký hiệu chuẩn đƣợc sử dụng rộng rãi trong vật lý lƣợng tử, dùng để mơ tả trạng thái lƣợng tử trong lý thuyết cơ học lƣợng tử. Trong cơ học lƣợng tử, trạng thái của một hệ vật lý đƣợc mơ tả bởi một vector trong khơng gian Hilbert phức H (sẽ nĩi rõ hơn ở phần sau), mỗi vector đĩ đƣợc gọi là ket và ký hiệu là (đọc là psi ket). Ứng với mỗi ket cĩ một bra và ký hiệu là (đọc là psi bra) là ánh xạ tuyến tính liên tục từ khơng gian Hilbert phức H tới khơng gian số phức H đƣợc định nghĩa bởi | ( , ) với mọi ket . Trong đĩ (,) là tích vơ hƣớng trong khơng gian Hilbert H. Trong ngơn ngữ ma trận, bra là ma trận chuyển vị liên hợp với ket và ngƣợc lại. Ký hiệu | đƣợc gọi là tích bra-ket (hay bracket). Tính chất của bra-ket: - Tính tuyến tính của bra và ket: với c1 và c2 là các số phức, ta cĩ o c1 1 c 2 2 c 1|| 1 c 2 2 o c1 1 c 2 2 c 1 1|| c 2 2 - Cho ket 1 và 2 bất kỳ, c1 và c2 là các số phức, từ tính chất của tích vơ hƣớng ta cĩ cc là vector đối ngẫu với cc trong đĩ c * 1 1 2 2 1212 1 * và c2 là các số phức liên hợp với c1 và c2 - Cho bra và ket bất kỳ, từ tính chất của tích vơ hƣớng trong khơng gian Hilbert ta cĩ | | * Nguyễn Thanh Tùng 43
  44. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng 2.2 Nguyên lý cơ bản của cơ học lƣợng tử Trong cơ học cổ điển (hay cơ học Newton), trạng thái của một hệ n phần tử tại thời điểm t0 đƣợc xác định bởi vị trí {x1(t0), x2(t0), , xn(t0)} và vận tốc ’ ’ ’ của hệ là đạo hàm bậc nhất của các phần tử {x1 (t0), x2 (t0), , xn (t0)}. Nếu trạng thái khởi đầu đƣợc xác định, nhờ các định luật về cơ học cổ điển của Newton, chúng ta cĩ thể hồn tồn xác định (ít nhất là về mặt nguyên lý) trạng thái của hệ tại bất cứ thời điểm t nào. Tuy nhiên, cơ học lƣợng tử hồn tồn dựa trên một nền tảng tốn học hồn tồn khác so với cơ học cổ điển. Dƣới đây, tơi sẽ đề cập đến một số tiên đề cơ sở của cơ học lƣợng tử. Tiên đề 1. Trạng thái của một hệ vật lý S được mơ tả bằng một vector đơn vị | , được gọi là vector trạng thái hoặc hàm sĩng, nằm trong một khơng gian Hilbert HS gắn liền với hệ vật lý. Sự tiến triển theo thời gian của vector trạng thái | của hệ tuân theo phương trình Schrưdinger trong đĩ H là tốn tử tự liên hợp của hệ thống (cịn gọi là tốn tử Hamiltonian) và ħ là hằng số Planck-Dirac (hay cịn gọi là hằng số Planck đơn giản), ħ=h/2π, với h là hằng số Planck. Giá trị của h ≈ 6.626x10-34 J.s (J là Joule và s là giây) được xác định bằng thực nghiệm. Nguyễn Thanh Tùng 44
  45. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Nhƣ ta thấy ở trên, phƣơng trình Schrưdinger là phƣơng trình vi phân tuyến tính bậc nhất. Do đĩ ta cĩ thể áp dụng nguyên lý siêu trạng thái (Superposition principle): Nếu | 1(t) và | 2(t) là nghiệm của phƣơng trình Schrưdinger, khi đĩ siêu trạng thái | (t) = α| 1(t) + β| 2(t) (với α β là số phức) cũng là nghiệm của phƣơng trình. Do vậy tốn tử phát triển theo thời gian của hệ sẽ là: | (t) = U (t, t0) | (t0) và U là tốn tử tuyến tính. U sẽ là tốn tử Unita. Chính vì vậy trong mơ hình tốn học cho cơ học lƣợng tử, chúng ta sẽ sử dụng các phép biến đổi Unita. Tiên đề 2. Trạng thái của một hệ vật lý S được mơ tả bằng một vector đơn vị | , được gọi là vector trạng thái hoặc hàm sĩng, nằm trong một khơng gian Hilbert HS gắn liền với hệ vật lý. Nguyên lý bất định Heisenberg. Cho A và B là hai tốn tử Hermiltian gắn liền với các quan sát, A B là hai tốn tử khơng giao hốn và | là hàm sĩng gắn liền với trạng thái lượng tử. Khi đĩ bất đẳng thức sau luơn thoả mãn: |AB , | AB 2 trong đĩ [A,B] = AB - BA Nguyên lý Heisenberg cho ta biết rằng khi đo một trạng thái lƣợng tử theo hai đại lƣợng (như vị trí và vận tốc của hạt cơ bản), ta khơng thể đo chính xác đƣợc đồng thời cả hai giá trị đĩ. Nguyên lý Heisenberg đƣợc ứng dụng trong các hệ phân phối khố lƣợng tử nhƣ BB84 mà chúng ta sẽ xem xét ở phần sau. Nguyễn Thanh Tùng 45
  46. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng 2.3 Qubit và thanh ghi lƣợng tử 2.3.1 Khái niệm Qubit Trƣớc hết ta xét cách quan niệm mới về bit - đơn vị thơng tin cơ bản trong mơ hình mới này: đĩ là qubit. Nhƣ ta đã biết: 1 bit cổ điển cĩ thể biểu diễn một trong hai trạng thái: 0 hoặc 1 (ở tại một thời điểm xác định). Do đĩ, n bit cĩ thể biểu diễn 2n trạng thái khác nhau. Nhƣng theo cách quan niệm cổ điển, nếu một thanh ghi đƣợc tạo nên từ n bit cổ điển, tại một thời điểm, nĩ chỉ cĩ thể biểu đúng một giá trị nguyên trong khoảng từ0 2n 1. Theo quan niệm mới về mơ hình tính tốn lƣợng tử dựa trên nền tảng vật lý lƣợng tử, chúng ta thấy rằng tại một thời điểm một thanh ghi lƣợng tử cĩ thể chứa đƣợc tổ hợp nhiều giá trị. Xét theo mơ hình vật lý, qubit là một vi hạt cĩ hai trạng thái, nĩ cĩ thể là: spin hạt nhân trong phân tử, ion bị bẫy (trapped ions), . Chúng ta quan tâm đến hai trạng thái đặc biệt đƣợc ký hiệu là 0 & 1 , đƣợc coi là hai trạng thái cơ sở tính tốn. Theo mơ hình tốn học, xét khơng gian Hilbert H2 (H là trƣờng số phức). Nĩ cĩ cơ sở trực giao là (1, 0) và (0, 1), ta ký hiệu tƣơng ứng là & . Qubit cơ sở bao gồm hai dạng hoặc . Khi đĩ, một 1-qubit tổng quát biểu diễn một vector đơn vị trong khơng gianH2, trong đĩ trạng thái 0 ứng với vector (1, 0), cịn trạng thái 1 sẽ ứng với vector (0, 1) đồng thời thoả mãn điều kiện chuẩn hố về xác suất. Nhƣ vậy, dạng tổng quát của một 1-qubit là: 01 , Nguyễn Thanh Tùng 46
  47. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Đối với qubit cĩ trạng thái tổng quát là 01, chúng ta cĩ thể tiến hành đo (sẽ nĩi rõ hơn ở phần sau) trạng thái của qubit. Khi đĩ, theo các nguyên lý của cơ học lƣợng tử thì xác suất để nhận đƣợc trạng thái 0 là α2, xác suất để nhận đƣợc trạng thái 1 là β2, do đĩ α, β phải thoả mãn điều kiện xác suất α2 + β2 = 1. Nhƣ vậy sử dụng 0 & 1 ta cĩ thể biểu diễn trạng thái của một qubit, cũng giống nhƣ 0 & 1 biểu diễn trạng thái của bit cổ điển. Để đi đến khái niệm thanh ghi lƣợng tử (quantum register), ngƣời ta mở rộng khơng gian trạng thái bằng cách sử dụng tích tensor của các khơng gian H2. 2.3.2 Khái niệm thanh ghi lƣợng tử Định nghĩa: Một thanh ghi lƣợng tử (quantum register) biểu diễn một vector trong khơng gian Hilbert H = ((H2) n), đã đƣợc chuẩn hố. (H2) n là tích Tensor của n khơng gian H2) Do cơ sở của (H2) n là: 0 0 0ii00 00 0 0 0 0 1ii 00 1 1 11 n 1 1 1iinn 11 1 2 1 nên trạng thái tổng quát của một thanh ghi n-qubit X cĩ dạng: 21n X ci i i 0 n cii ; 0,2 1 n 21 2 ci 1 i 0 X cĩ toạ độ trong khơng gian Hilbert H là (c0, c1, c2, , cn) Nguyễn Thanh Tùng 47
  48. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Trạng thái lƣợng tử đƣợc biểu diễn một thanh ghi đƣợc gọi là một siêu trạng thái (Superposition). Ta cũng thấy rằng một quantum register cĩ thể lƣu trữ đồng thời 2n thơng tin khác nhau: 0 2n 1. Tồn tại siêu trạng thái của thanh ghi cĩ thể mơ tả bởi: X i12 i in ; trong đĩ i j là qubit thứ j. Tuy nhiên cũng cĩ những siêu trạng thái khơng thể biểu diễn đƣợc dƣới dạng nhƣ vậy. Ta xét hai ví dụ với thanh ghi 2-qubit cĩ thể biểu diễn đƣợc bằng tích tensor của hai 1-qubit: Ví dụ: 1 1 1 1 X0 2 00 10 0 1 0 q q 2 2 2 2 12 Nhƣ vậy, trạng thái của X đƣợc viết dƣới dạng tích của trạng thái hệ thống 1 con: q 01 và q 0 . Với những trạng thái nhƣ thế này, các 1 2 2 phép biến đổi Unita, các phép đo chỉ làm thay đổi trạng thái của hệ thống con mà khơng làm ảnh hƣởng đến các hệ thống cịn lại. Ví dụ, khi tiến hành đo qubit thứ nhất đƣợc giá trị 0 hay 1 thì qubit thứ hai luơn đo đƣợc kết quả . Cĩ thể so sánh với trạng thái rối lƣợng tử ở mục sau. 2.3.3 Phép biến đổi Unita và phép đo. Đối với tính tốn lƣợng tử, cĩ 2 loại phép biến đổi cơ bản là phép biến đổi Unita và phép biến đổi khơng Unita. Đối với lớp phép biến đổi khơng Unita chỉ cĩ phép đo. Các phép biến đổi Unita là các phép biến đổi khơng mất năng lƣợng. Do vậy các phép biến đổi Unita là các phép biến đổi khả nghịch. Về mặt tốn học cĩ thể coi là các ánh xạ trong các khơng gian Hilbert đẳng cấu. Nguyễn Thanh Tùng 48
  49. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng U:∑H ∑H' trong đĩ H và H’ là hai khơng gian Hilbert cĩ cùng số chiều (ở đây chúng ta chỉ xét đến khơng gian Hilbert hữu hạn chiều, với các khơng gian Hilbert vơ hạn chiều, sẽ cĩ cách tiếp cận khác khơng đƣợc đề cập đến trong luận văn này) Cịn phép đo là phép biến đổi mất năng lƣợng, do đĩ phép đo là phép biến đổi bất khả nghịch. Về mặt tốn học cĩ thể coi là phép đo là phép ánh xạ về khơng gian Hilbert cĩ số chiều ít hơn. U:∑H ∑H' trong đĩ H và H’ là hai khơng gian Hilbert, H’ cĩ số chiều nhỏ hơn H. Đối với hệ lƣợng tử, khi áp dụng phép đo thì ta sẽ khơng thể tiên đốn độ xác định của kết quả (nguyên lý bất định Heisenberg). Kết quả thu đƣợc phụ thuộc vào xác suất của các trạng thái đƣợc biểu diễn bởi hệ lƣợng tử. Đồng thời theo các nguyên lý của cơ học lƣợng tử, ngay sau khi đo lập tức hệ lƣợng tử sẽ sụp đổ về giá trị đo đƣợc. Ví dụ: Trong trƣờng hợp tổng quát, một n-qubit X đang ở trạng thái lƣợng tử: 21n X ci i i 0 n cii ; 0,2 1 n 21 2 ci 1 i 0 Khi tiến hành phép đo, chúng ta sẽ khơng biết trƣớc kết quả đo đƣợc là bao nhiêu. Theo các nguyên lý của cơ học lƣợng tử, chúng ta chỉ cĩ thể biết 2 đƣợc xác suất đo đƣợc giá trị i là ci . Đồng thời ngay sau khi tiến hành đo, X 21n sẽ khơng cịn ở siêu trạng thái cii mà sụp đổ về trạng thái i đo đƣợc. i 0 Nguyễn Thanh Tùng 49
  50. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng 1 1 1 Ví dụ với hệ lƣợng tử q 0 1 0 1 , khi tiến hành phép 2 2 2 đo, chúng ta sẽ khơng xác định đƣợc kết quả là 0 hay 1 mà chỉ cĩ thể biết đƣợc rằng khi đo, chúng ta sẽ thu đƣợc kết quả là 0 hay 1 với xác suất bằng nhau (là 50%). Đồng thời, ngay sau khi đo, chẳng hạn ta đo đƣợc giá trị 0 thì ngay lập tức q sẽ sụp đổ về trạng thái 0 . 2.4 Nguyên lý rối lƣợng tử (Nguyên lý Entanglement) Nguyên lý rối lƣợng tử là một trong những nguyên lý quan trọng của tính tốn lƣợng tử. Nguyên lý rối lƣợng tử cho phép việc tính tốn diễn ra một cách đồng thời trên các thành phần của qubit đầu vào khi nĩ ở trạng thái rối lƣợng tử. 11 Ví dụ : Ta xét ví dụ sau đây: X 0 3 00 11 22 Khi tiến hành đo một qubit, tuỳ theo kết quả của phép đo mà ta cĩ ngay trạng thái của qubit cịn lại. Tức là phép đo đã ảnh hƣởng đến tồn bộ hệ thống: Nếu kết quả là 0 thì trạng thái qubit cịn lại là Nếu kết quả là 1 thì trạng thái qubit cịn lại là Suy ra: giữa hai hệ thống con cĩ mối quan hệ nào đĩ. Ngƣời ta gọi những trạng thái nhƣ vậy là rối lượng tử hay vướng lượng tử (Quantum Entanglement). Trạng thái này của hệ 2-qubit khơng thể phân tích thành tích tensor của hai hệ thống con 1-qubit. 2.5 Nguyên lý song song lƣợng tử Thanh ghi lƣợng tử cùng một lúc cĩ thể lƣu trữ nhiều trạng thái đơn lẻ khác nhau nhƣng cĩ một đặc điểm đáng chú ý là: bất kỳ một phép tác động nào lên một thanh ghi lƣợng tử thì nĩ sẽ tác động lên đồng thời tồn bộ các trạng thái mà thanh ghi đĩ lƣu trữ (ta khơng thể tách rời các trạng thái để thao tác trên chúng một cách riêng lẻ) Nguyễn Thanh Tùng 50
  51. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng 2nn 1 2 1 Nghĩa là U cii i cU i với U là một phép biến đổi Unita nào đĩ. Ở ii00 đây ta cĩ thể thấy sức mạnh của tính tốn lƣợng tử vì nếu trong tính tốn cổ điển để thực hiện đƣợc phép biến đổi trên, chúng ta cần nhân ma trận ma trận C = (c0, n n c1, c2, , cn) với ma trận U cỡ 2 x 2 cịn trong tính tốn lƣợng tử, chúng ta chỉ cần một phép biến đổi Unita (cĩ thể biểu diễn bằng một cổng lượng tử, xem 1.7). Tức là độ phức tạp cĩ thể giảm theo cấp luỹ thừa. 2.6 Nguyên lý khơng thể sao chép (No-Cloning Theorem) Trong tính tốn cổ điển, cĩ một tính chất của bit cổ điển là chúng ta cĩ thể dễ dàng tạo một bản sao chứa cùng thơng tin. Tuy nhiên, đối với tính tốn lƣợng tử, trạng thái của qubit tổng quát nĩi chung khơng thể sao chép. Định lý: Khơng thể tạo ra một máy thực hiện các phép biến đổi Unita cĩ khả năng sao chép hồn hảo trạng thái của một qubit bất kỳ. Chứng minh: Thực vậy, giả sử ta cĩ đƣợc một máy sao chép hồn hảo. Khi đĩ xét hệ bao gồm hai qubit (qubit đƣợc sao chép, qubit sao chép) và máy sao chép trạng thái. Qubit đƣợc sao chép ở trạng thái tổng quát: 01 Trong đĩ biên độ α và β là các số phức ràng buộc bởi phƣơng trình 221 Trong khi đĩ qubit thứ hai và máy sao chép đang ở trạng thái và Ai (trạng thái khởi đầu trƣớc khi tiến hành sao chép). Khi đĩ máy sao chép sẽ tác động phép biến đổi Unita U lên hệ: UAAAi f0 1 0 1 f (1.6.1) Nguyễn Thanh Tùng 51
  52. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng trong đĩ trạng thái cuối cùng của máy sao chép Af sẽ phụ thuộc vào trạng thái của qubit thứ nhất . Chúng ta sẽ chứng minh phép biến đổi Unita trên khơng thể tồn tại. Thực vậy, nếu trạng thái của qubit thứ nhất là 0 , phép biến đổi Unita U sẽ tác động là: UAA0if 0 0 0 (1.6.2) Tƣơng tự, nếu trạng thái của qubit thứ nhất là 1 , phép biến đổi Unita U sẽ tác động là: UAA1if 1 1 1 (1.6.3) Khi đĩ, với trạng thái tổng quát của qubit thứ nhất và do tính tuyến tính của tốn tử Unita U, ta cĩ UAUAii01 UAUA01ii (1.6.4) 0 0AAff01 1 1 Ta thấy trạng thái (1.6.4) này khác hồn tồn so với trạng thái (1.6.1) chúng ta mong muốn, suy ra điều cần phải chứng minh. Ở đây, định lý này muốn khẳng định khơng tồn tại một máy sao chép trạng thái bất kỳ, tuy nhiên với một số trạng thái lƣợng tử đặc biệt nhƣ hay thì ta cĩ thể tạo đƣợc máy sao chép. 2.7 Mạch và Cổng logic lƣợng tử Trong mơ hình máy tính cổ điển, các nhà khoa học đã mơ hình hố tốn học bằng các mơ hình nhƣ cổng và mạch logic cổ điển, máy tính Turing. Tƣơng tự vậy, trong tính tốn lƣợng tử, các nhà khoa học cũng đƣợc xây dựng các mơ hình nhƣ mơ hình cổng và mạch logic lƣợng tử, máy tính Turing lƣợng tử. Yao đã chỉ ra rằng với mỗi máy Turing lƣợng tử, tồn tại mơ hình mạch logic lƣợng tử mơ phỏng máy Turing lƣợng tử đĩ với thời gian đa thức. Do đĩ chúng ta chỉ cần nghiên cứu một mơ hình cổng và mạch logic lƣợng tử, do mơ hình này đơn giản Nguyễn Thanh Tùng 52
  53. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng và gần gũi với cách thiết kế máy tính lƣợng tử. Từ đĩ dẫn đến kết quả tƣơng tự trong mơ hình máy Turing lƣợng tử. Một cách tƣơng tự nhƣ máy tính cổ điển, đƣợc xây dựng dựa trên các cổng logic cơ bản nhƣ AND, OR, NOT, trong mơ hình tính tốn lƣợng tử, chúng ta cũng xây dựng các cổng lƣợng tử. Do yêu cầu của cơ học lƣợng tử là các phép biến đổi hệ lƣợng tử bắt buộc là Unita do đĩ trong mơ hình tốn học của tính tốn lƣợng tử, chúng ta sử dụng các tốn tử Unita. Định nghĩa: Một cổng logic lượng tử n-qubit được sử dụng để biến đổi n- qubit được biểu về mặt tốn học bởi một phép biến đổi Unita tác động lên vector siêu trạng thái của n-qubit đĩ. Ma trận biến đổi Unita tác động lên n-qubit là ma trận 2nx2n. Định nghĩa: Mạch lơgic lượng tử là một tập các cổng lơgic lượng tử liên kết theo một đồ thị cĩ hướng khơng chu trình, trong đĩ đầu ra của cổng này cĩ thể là đầu vào của cổng kia. Dƣới đây là một số cổng logic lƣợng tử cơ bản Nguyễn Thanh Tùng 53
  54. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng 2.7.1 Cổng 1 qubit Các cổng logic lƣợng tử tác động lên 1 qubit đều cĩ thể mơ tả bằng ma trận Unita tổng quát sau: eii()() cos()() e sin 22 U 2( , , , ) eii()() sin()() e cos 22 với ,,, R i/ NOT: Thực hiện: 01 10 Dạng ma trận: 01 X 10 Cổng NOT cĩ thể biểu diễn bằng cổng U2 là 01 XU2( ,0,0,0) 10 Biểu diễn trong mạch: Hình 1.1. Biểu diễn cổng NOT ii/ Z-gate: Thực hiện: 00 11 Nguyễn Thanh Tùng 54
  55. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Dạng ma trận: 10 Z 01 Biểu diễn trong mạch: Hình 1.2. Biểu diễn cổng Z iii/ Cổng Hadamard Thực hiện: 1 0 0 1 2 1 1 0 1 2 Dạng ma trận 1 11 H 2 11 Cổng Hadamard cĩ thể biểu diễn bằng cổng U2 là 1 11 HU2( , , , ) 222 2 11 Biểu diễn trong mạch: Hình 1.3. Biểu diễn cổng Hadamard Nguyễn Thanh Tùng 55
  56. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng 2.7.2 Cổng 2 qubit i/ Controlled NOT (CNOT) Cổng CNOT này thực hiện tƣơng tự phép tốn XOR trong tính tốn cổ điển. Thực hiện: ab, 0,1 b giữ nguyên nếu a = 0 b đảo bit nếu a = 1 Dạng ma trận 1 0 0 0 0 1 0 0 CNOT 0 0 0 1 0 0 1 0 Biểu diễn trong mạch: Bit điều khiển Bit đích Hình 1.4. Biểu diễn cổng CNOT Nguyễn Thanh Tùng 56
  57. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng ii/ Cổng hốn vị hai bit (Cổng Swap) Ứng dụng cổng CNOT: hốn vị hai bit Hình 1.5. Biểu diễn cổng Swap iii/ Cổng dịch pha cĩ điều khiển (Controlled phase shift gate) Cổng dịch pha cĩ điều khiển là cổng khơng cĩ cổng tƣơng tự trong tính tốn cổ điển. Thực hiện: Cổng dịch pha sẽ dịch pha của qubit nguồn chỉ khi qubit điều khiển bằng 1 Dạng ma trận: 1 0 0 0 0 1 0 0 CPHASE() 0 0 1 0 000ei Biểu diễn trong mạch: i x ex R y Hình 1.6. Biểu diễn cổng dịch pha cĩ điểu khiển2.7.3. Cổng 3 qubit Nguyễn Thanh Tùng 57
  58. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng i/ Cổng Controlled-Controlled NOT (CCNOT) - Cổng Toffoli Thực hiện a b c a’ b’ c’ 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 Dạng ma trận: 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 Nguyễn Thanh Tùng 58
  59. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Biểu diễn trong mạch: Hình 1.7. Biểu diễn cổng Toffoli Cổng Toffoli áp dụng cổng Not lên qubit cuối cùng nên ta cĩ thể biểu diễn dƣới dạng mạch nhƣ sau: Hình 1.8. Biểu diễn cổng Toffoli Chúng ta cĩ thể sử dụng cổng Toffoli và cổng CNOT để biểu diễn mạch cộng nhị phân cĩ nhớ nhƣ sau: Hình 1.9. Biểu diễn cổng cộng nhị phân cĩ nhớ2.7.4. Cổng phổ dụng Trên thực tế, chúng ta muốn xây dựng và sử dụng chỉ một số cổng cơ bản tác động lên một số lƣợng nhỏ qubit (độc lập với số lượng n qubit cần xử lý, n cĩ thể rất lớn) nhƣng phải đảm bảo yêu cầu cĩ thể tính đƣợc một hàm bất kỳ. Các cổng đĩ đƣợc gọi là cổng phổ dụng. Trong tính tốn cổ điển, ta đã biết đƣợc Nguyễn Thanh Tùng 59
  60. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng cổng NOT và AND là cổng phổ dụng. Tƣơng tự, trong tính tốn lƣợng tử, chúng ta sẽ định nghĩa về cổng phổ dụng. Định nghĩa: Một tập cổng lượng tử G được gọi là phổ dụng nếu > 0 và mọi ma trận Unita U tác động trên số bít bất kì, U cĩ thể được xấp xỉ với độ chính xác > 0 bằng một dãy cổng của G. Nĩi cách khác nhĩm con tạo nên bởi G là trù mật trong nhĩm nhĩm các tốn tử Unita, n. Tức là UU, 0, ' được tạo nên bằng tích các cổng của G sao cho UU' . Deutsch là ngƣời đầu tiên chỉ ra một cổng lƣợng tử phổ dụng 3 qubit. Đĩ là cổng Toffoli dạng tổng quát. Sau đĩ, Di Vincenzo chỉ ra những cổng 2 qubit là phổ dụng. Cho đến nay, cĩ rất nhiều tập cổng phổ dụng đã đƣợc đƣa ra. Một ví dụ về tập cổng phổ dụng là tập cổng CNOT, Hadamard, các cổng dịch pha. Nguyễn Thanh Tùng 60
  61. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng CHƢƠNG 3. MÃ HĨA LƢỢNG TỬ Hệ mã hố cơng khai lần đầu đƣợc đƣa ra bởi Diffie và Hellman trong bài báo cĩ tên “New directions in cryptography” vào năm 1976. Sau đĩ 2 năm, vào năm 1978, Rivest, Shamir và Adleman cơng bố một hệ mã cơng khai (do đĩ được mang tên RSA) dựa trên bài tốn khĩ là phân tích ra thừa số nguyên tố của số lớn trong bài báo “A method for obtaining digital signatures and public-key cryptosystems”. Ngày nay, hệ mã cơng khai RSA và các biến thể đƣợc sử dụng rộng rãi trong các ứng dụng thƣơng mại và dân sự. Tuy nhiên, nhƣ chúng ta đã thấy ở trên, với sức mạnh của tính tốn lƣợng tử và thuật tốn thích hợp, chúng ta cĩ thể phá vỡ các thuật tốn mã hố đƣợc coi là an tồn hiện nay nhƣ RSA. Do vậy nhu cầu cấp thiết đƣợc đặt ra là thiết kế phƣơng pháp mã hố và phân phối khố mới để đảm bảo an tồn dữ liệu khi máy tính lƣợng tử ra đời, đặc biệt là khi máy tính lƣợng tử đƣợc thƣơng mại hố. Nhƣ vậy, vấn đề đặt ra là chúng ta phải sử dụng sức mạnh của lƣợng tử để chống lại các phƣơng pháp tấn cơng bằng lƣợng tử. Trong đĩ, sức mạnh của tính tốn lƣợng tử cĩ thể kết hợp với một hệ mã cĩ độ mật hồn thiện, hệ mật One- time-pad. Trong bài báo của mình vào năm 1949, Shannon đã chứng minh hệ mật một lần đệm (One-time-pad) là hệ mật cĩ độ mật hồn thiện dựa trên lý thuyết thơng tin. Tuy nhiên trên thực tế, hệ mật One-time-pad khơng đƣợc sử dụng rộng rãi do nhƣợc điểm của hệ mật One-time-pad là yêu cầu khơng gian khố lớn (tối thiểu bằng khơng gian bản rõ) dẫn đến nhiều khĩ khăn trong quá trình phân phối khố, bảo mật và lƣu trữ khố. Nhƣng khi kết hợp với tính tốn lƣợng tử, hệ mã One-time-pad lại cho thấy tiềm năng to lớn về độ an tồn bảo mật của dữ liệu cũng nhƣ tính hiệu quả trong việc phân phối và lƣu trữ khố. Mục đích của chƣơng này là đề cập đến một ví dụ về một giao thức phân phối khố lƣợng tử đơn giản trong bức tranh hết sức sơi động của lĩnh vực mã Nguyễn Thanh Tùng 61
  62. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng hố lƣợng tử và thám mã lƣợng tử. Giao thức phân phối khố lƣợng tử này cĩ thể sử dụng để phân phối khố của hệ mật One-time-pad. 3.1 Giao thức phân phối khố lƣợng tử BB84 Giao thức phân phối khố lƣợng tử BB84 là giao thức lƣợng tử đầu tiên đƣợc Bennett và Brassard cơng bố trong bài báo "Quantum cryptography: Public key distribution and coin tossing" vào năm 1984 và cài đặt lần đầu vào năm 1992 [21]. Trên thực tế giao thức BB84 đã đƣợc cài đặt chuyển thơng tin trên khoảng cách 10 km vào năm 1994 qua cáp quang [58] và hi vọng cĩ thể chuyển thơng tin ở khoảng cách xa hơn [55]. 3.1.1 Giao thức BB84 trƣờng hợp khơng nhiễu Trong giao thức phân phối khố lƣợng tử BB84, chúng ta cần chuẩn bị 4 1 1 trạng thái lƣợng tử 0 , 1 , 0 ( 0 1 ) và 1 ( 0 1 ) chia x 2 x 2 làm hai nhĩm (mà chúng ta sẽ gọi là hai bảng chữ cái): - Bảng chữ cái z gồm hai trạng thái , - Bảng chữ cái x gồm hai trạng thái và Giao thức BB84 sẽ bao gồm hai giai đoạn: - Giai đoạn 1: Giao tiếp qua kênh lƣợng tử\ - Giai đoạn 2: Giao tiếp qua kênh cơng cộng (gồm 2 pha) Sơ đồ của giao thức BB84 cĩ thể mơ tả bởi hình sau: trong đĩ Alice và Bob muốn giao tiếp với nhau, cịn Eve là kẻ thứ ba muốn đọc trộm thơng tin trao đổi giữa Alice và Bob. Nguyễn Thanh Tùng 62
  63. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Hình 3.1. Sơ đồ của giao thức BB84 Ta sẽ xem xét từng giai đoạn. 3.1.1.1 Giai đoạn 1: Giao tiếp qua kênh lượng tử Trong giai đoạn này, Alice sẽ truyền trên kênh lƣợng tử với xác suất ngẫu nhiên bằng nhau các trạng thái của bảng chữ cái z và x. Vì khơng cĩ tốn tử đo trạng thái của bảng chữ cái z hốn vị với tốn tử đo trạng thái của bảng chữ x [55] nên theo nguyên lý bất định Heisenberg, khơng ai, kể cả Bob và Eve cĩ thể nhận đƣợc các bit truyền đi từ Alice với xác xuất lớn hơn ¾ (75%). Điều này cĩ thể chứng minh nhƣ sau: vì khơng ai cĩ thể chọn tốn tử đo chính xác cả hai bảng chữ cái z và x đồng thời do Alice chọn ngẫu nhiên nên việc chọn tốn tử đo sẽ đúng với xác suất 50% (do cĩ 2 bảng chữ cái). Đồng thời nếu chọn sai bảng chữ cái, xác suất để đo đúng là 50% (do cĩ 2 trạng thái trong 1 bảng chữ cái). Vì vậy xác suất đốn đúng trạng thái Alice truyền đi là 1 1 1 3 P *1 * 2 2 2 4 Xác suất để Bob đốn sai là 1-P = ¼ Nguyễn Thanh Tùng 63
  64. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Ngồi ra, theo nguyên lý khơng thể sao chép (no-clone theorem), Eve khơng thể đo thơng tin của Alice gửi đi rồi sao chép lại để gửi chuyển tiếp cho Bob. Trong trƣờng hợp nếu cĩ Eve thực hiện tốn tử đo các bit do Alice truyền đi với xác suất λ, 0 ≤ λ ≤ 1, và khơng thực hiện các tốn tử đo với xác suất 1 - λ Bởi vì Bob và Eve lựa chọn các phép tốn đo hồn tồn ngẫu nhiên độc lập với nhau và độc lập với sự lựa chọn của Alice nên khi Eve thực hiện phép đo ở giữa đƣờng truyền sẽ ảnh hƣởng đến bit lƣợng tử nhận đƣợc của Bob. Việc này sẽ làm cho tỷ lệ lỗi của Bob nhận đƣợc từ ¼ thành: 1 3 1 P (1 ) Error 4 8 4 8 Do vậy nếu Eve “đọc lén” tất cả các bit do Alice truyền đến cho Bob (nghĩa là λ=1) thì xác suất lỗi của Bob là 3/8 (tăng gần 50%) 3.1.1.2 Giai đoạn 2: Giao tiếp qua kênh cơng cộng Giai đoạn này sẽ làm hai pha: - Pha 1: Tạo khố thơ - Pha 2: Phát hiện sự do thám của Eve thơng qua phát hiện lỗi Pha 1. Tạo khố thơ. Pha 1 của giai đoạn 2 là pha loại bỏ vị trí các bit lỗi (và các bit tại vị trí đấy). Các lỗi này bao gồm lỗi xác suất chọn cơ sở đo (bằng ¼) và lỗi do Eve đo trên đƣờng truyền. Bob truyền trên đƣờng truyền cơng cộng tên bảng chữ cái mình sử dụng để đo (z và x) cho Alice. Khi đĩ Alice sẽ thơng báo cho Bob biết bảng chữ cái nào đúng. Sau khi hai bên trao đổi thơng tin, Alice và Bob sẽ cùng xố đi các bit tƣơng ứng tại các vị trí khơng tƣơng ứng giữa bảng chữ mà Alice chọn để truyền thơng tin và bảng chữ cái mà Bob dùng để đo. Các bit cịn lại của Alice và Bob đƣợc gọi là khố thơ. Nguyễn Thanh Tùng 64
  65. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Nếu khơng cĩ sự do thám của Eve, khi đĩ khố thơ của Alice và khố thơ của Bob là giống nhau và cĩ thể sử dụng làm khố bí mật. Tuy nhiên do cĩ sự do thám của Eve nên xác suất để khố thơ của Alice và Bob khơng giống nhau là 1 0.(1 ) . 44 Pha 2. Phát hiện sự do thám của Eve thơng qua phát hiện lỗi. Với giả thiết ban đầu là khơng cĩ nhiễu trên đƣờng truyền do vậy mọi sự khác nhau giữa khố thơ của Alice và Bob đều chứng tỏ là do sự do thám của Eve. Vì vậy để phát hiện sự do thám của Eve, Alice và Bob cùng chọn thoả thuận cơng khai dựa trên tập con ngẫu nhiên m bit của khố thơ, và so sánh cơng khai các bit tƣơng ứng, đảm bảo rằng khơng cĩ sự sai khác nào giữa hai tập con ngẫu nhiên đĩ. Nếu cĩ bất cứ sự sai khác nào giữa hai tập con ngẫu nhiên, nguyên nhân chắc chắn do sự do thám của Eve. Khi đĩ Alice và Bob quay trở lại từ giai đoạn 1 để bắt đầu lại. Nếu khơng cĩ sự sai khác nào, xác suất để Eve thốt khỏi sự kiểm tra trên là m P 1 false 4 trong trƣờng hợp λ=1 và m = 200, khi đĩ 13200 200 P 1 10 25 false 44 là xác suất rất nhỏ. Do vậy Alice và Bob cĩ thể coi khố thơ là khố bí mật để sử dụng trong hệ mã One-time-pad. Nguyễn Thanh Tùng 65
  66. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng 3.1.1.3 Ví dụ Dƣới đây là ví dụ về giao thức BB84 trong trƣờng hợp khơng cĩ nhiễu và khơng cĩ sự do thám của Eve Bit dữ liệu của 1 0 0 0 1 1 0 1 0 1 Alice Bảng chữ Alice x z x z x x x z z x chọn Qubits truyền đi |1 x |0 |0 x |0 |1 x |1 x |0 x |1 |0 |1 x Bảng chữ Bob chọn x z x x z x z x z z Kết quả đo 1 0 0 0 0 1 0 0 0 1 Bit dữ liệu của Bob 1 0 0 0 0 1 0 0 0 1 Các vị trí khơng √ √ √ √ √ khớp Khố thơ 1 0 0 1 0 3.1.2 Giao thức phân phối khố lƣợng tử BB84 trƣờng hợp cĩ nhiễu Ở đây, giao thức BB84 sẽ đƣợc mở rộng trong trƣờng hợp mơi trƣờng cĩ nhiễu. Khi đĩ, Alice và Bob sẽ khơng phân biệt đƣợc lỗi do nhiễu hay lỗi do Eve do thám. Do đĩ, Alice và Bob sẽ phải giả thiết rằng tồn bộ lỗi của khố thơ là do Eve do thám trên đƣờng truyền. Trong trƣờng hợp trên đƣờng truyền cĩ nhiễu, chúng ta vẫn cĩ hai giai đoạn của giao thức BB84. 3.1.2.1 Giai đoạn 1: Giao tiếp qua kênh lượng tử. Trong giai đoạn này, mọi thủ tục của giao thức tƣơng tự nhƣ giai đoạn 1 của giao thức BB84 trong trƣờng hợp khơng cĩ nhiễu. 3.1.2.2 Giai đoạn 2: Giao tiếp qua kênh cơng cộng. Trong trƣờng hợp cĩ nhiễu, Alice và Bob sẽ trao đổi với nhau qua kênh cơng cộng trong 4 pha. Pha 1 là tạo khố thơ, pha 2 là đánh giá lỗi, pha 3 là đồng bộ (để tạo khố đồng bộ - reconciled key), pha 4 là khuyếch đại bí mật (privacy amplification). Nguyễn Thanh Tùng 66
  67. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Pha 1. Tạo khố thơ. Pha này thực hiện giống pha 1 (giai đoạn 2) của giao thức BB84 trong trƣờng hợp khơng cĩ nhiễu, ngoại trừ trƣờng hợp Alice và Bob cũng xố các bit tại vị trí mà Bob khơng nhận đƣợc thơng tin. Việc khơng nhận đƣợc thơng tin do cĩ sự do thám của Eve hoặc do nhiễu trên đƣờng truyền. Pha 2. Đánh giá lỗi của khố thơ. Alice và Bob sử dụng kênh cơng cộng để đánh giá tỷ lệ lỗi của khố thơ bằng cách cơng bố các đoạn mẫu chọn ngẫu nhiên của khố thơ đã đƣợc thoả thuận giữa hai bên, cơng khai so sánh các bit này để cĩ đƣợc tỷ lệ lỗi R. Những bit cơng khai này sẽ đƣợc loại bỏ ra khỏi khố thơ. Nếu R đạt quá ngƣỡng RMax, khi đĩ Alice và Bob sẽ phải quay lại giai đoạn 1 để bắt đầu lại. Nếu R nhỏ hơn ngƣỡng RMax, khi đĩ Alice và Bob sẽ chuyển qua pha 3. Pha 3. Tạo khố đồng bộ. Mục đích của pha 3 là Alice và Bob sẽ xố tất cả các bit lỗi từ khố thơ và đƣợc thực hiện trong 2 bƣớc. Bước 1. Alice và Bob cơng bố một thoả thuận hốn vị ngẫu nhiên và sử dụng nĩ vào phần khố tƣơng ứng, Kế tiếp Alice và Bob phân hoạch phần cịn lại của khố thơ (sau khi xử lý ở pha 2) thành các khối độ dài l, trong đĩ l đƣợc chọn sao cho cĩ khơng quá 1 lỗi trong khối đĩ. Sau đĩ Alice và Bob cơng bố cơng khai bit kiểm tra chẵn lẻ. Nếu bit kiểm tra chẵn lẻ khơng bằng nhau. Alice và Bob sẽ sử dụng thuật tốn tìm kiếm nhị phân để tìm bit lỗi bằng cách chia khối làm 2 khối con, sau đĩ kiểm tra bit chẵn lẻ của hai khối con và tiếp tục tìm kiếm bit lỗi tại khối cĩ bit kiểm tra chẵn lẻ khác nhau cho đến khi tìm và loại bỏ đƣợc bit lỗi. Alice và Bob tiếp tục lặp lại với các khối độ dài l khác. Alice và Bob cĩ thể lặp lại nhiều lần bƣớc 1 với các hốn vị ngẫu nhiên khác nhau, chiều dài block l khác nhau để làm loại bỏ các bit lỗi. Nguyễn Thanh Tùng 67
  68. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Bước 2. Alice và Bob sử dụng một thủ tục đồng bộ khác để làm mịn kết quả. Đầu tiên, Alice và Bob cơng khai lựa chọn một tập con ngẫu nhiên của khố thơ, so sánh bit kiểm tra chẵn lẻ. Nếu bit chẵn lẻ khơng giống nhau, Alice và Bob sẽ áp dụng chiến lƣợc tìm kiếm nhị phân nhƣ ở bƣớc 1 để tìm và loại bỏ bit lỗi. Với xác suất cao, khố thơ cuối cùng khơng chứa các bit lỗi. Lúc này, khố thơ đƣợc gọi là khố đồng bộ và tiếp tục chuyển sang pha 4. Pha 4. Khuyếch đại bí mật (tạo khố bí mật cuối cùng). Lúc này, Alice và Bob đã cĩ khố đồng bộ nhƣng chỉ một phần là bí mật với Eve. Vì vậy Alice và Bob sẽ bắt đầu tiến trình khuyếch đại bí mật để tách phần bí mật của khố đồng bộ. Dựa trên tỷ lệ lỗi R, Alice và Bob dự đốn cận trên k của số lƣợng các bit biết bởi Eve trong số n bit của khố đồng bộ. Gọi s là tham số an tồn mà Alice và Bob mong muốn, khi đĩ Alice và Bob cơng bố n – k – s tập con ngẫu nhiên từ khố đồng bộ (khơng cần quan tâm đến nội dung). Sau đĩ Alice và Bob xố khỏi khố đồng bộ các phần mà cả hai cùng cơng khai, phần cịn lại của khố đồng bộ sẽ là khố bí mật cuối cùng. Thơng tin trung bình mà Eve cĩ đƣợc về khố bí mật cuối cùng này sẽ nhỏ hơn 2-s/ln 2 bit [55]. 3.1.3 Một số nhƣợc điểm của giao thức BB84. - Eve cĩ thể phá hoại kênh lƣợng tử (bằng cách đo các thơng tin chuyển đi từ Alice dẫn đến xác suất lỗi tăng), khi đĩ Alice và Bob bắt buộc phải giao tiếp qua kênh cổ điển. - Chi phí lớn cho khơng gian khố: cần khơng gian khố cĩ độ lớn bằng độ lớn của khơng gian bản rõ mới đảm bảo an tồn tuyệt đối. - Alice cĩ thể gian lận mà Bob khơng phát hiện đƣợc: o Alice tạo một cặp qubit ở trạng thái rối lƣợng tử o Gửi đi một qubit cho Bob và giữ qubit cịn lại Nguyễn Thanh Tùng 68
  69. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng o Sau khi Bob tiến hành đo, Alice sẽ đo qubit cịn lại và đốn đƣợc sự lựa chọn của Bob. - Khơng cĩ sự định danh trƣớc khi tiến hành trao đổi khố thơng qua kênh lƣợng tử nên Alice cĩ thể bị giả mạo. 3.1.4 Về độ an tồn của giao thức phân phối khố BB84. Các hệ mã hố lƣợng tử, sử dụng các hiện tƣợng lƣợng tử nhƣ nguyên lý bất định Heisenberg, nguyên lý khơng thể sao chép, nguyên lý rối lƣợng tử để bảo vệ và phân phối khố mã hố. Các hệ mã hố lƣợng tử cho phép hai ngƣời (hoặc hai tổ chức), khơng chia sẻ thơng tin bí mật trƣớc đĩ, cĩ thể giao tiếp trên các kênh cơng cộng một cách an tồn. Do dựa trên các nguyên lý nhƣ trên (đặc biệt là nguyên lý khơng thể sao chép hồn hảo và nguyên lý bất định Heisenberg) nên các hệ mã lƣợng tử đƣợc coi là an tồn chống lại các phƣơng pháp tấn cơng của bên thứ ba. Tuy nhiên một số sơ đồ tấn cơng các hệ mã lƣợng tử đã đƣợc phát triển nhƣ sơ đồ chặn/chuyển tiếp (intercept/resend scheme), sơ đồ phân tia sáng (beamsplitting scheme) tuy nhiên các sơ đồ tấn cơng trên vẫn làm nhiễu thơng tin Bob thu đƣợc và sẽ bị phát hiện trong giao thức phân phối khố BB84. Trong phần này, tơi sẽ trình bày một sơ đồ tấn cơng cĩ tên là Sao chép gián tiếp (Indirect Coping) mà Eve cĩ thể sử dụng để thu đƣợc thơng tin chuyển đi từ Alice mà khơng bị phát hiện bởi Alice và Bob trong giao thức phân phối khố lƣợng tử BB84 (cũng nhƣ trong các giao thức tƣơng tự nhƣ B92). Đây là phƣơng pháp tấn cơng thuộc loại man-in-middle. Sơ đồ này cĩ thể mơ tả nhƣ sau: - Eve xây dựng một hàm quy tắc. Hàm này là hàm đơn trị với mọi trạng thái lƣợng tử khác nhau đƣợc sử dụng bởi Alice và Bob trong giao thức, nghĩa là mọi giá trị của hàm sẽ tƣơng ứng với các trạng thái lƣợng tử khác nhau. Nguyễn Thanh Tùng 69
  70. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng - Khi Alice gửi các bit lƣợng tử ngẫu nhiên đến cho Bob, Eve sẽ nhận mọi trạng thái này và tính giá trị tƣơng ứng bởi hàm trên sau đĩ huỷ qubit nhận đƣợc. - Sau đĩ Eve sẽ gửi một trạng thái lƣợng tử mới tới Bob dựa trên bảng tham chiếu trong đĩ mọi giá trị của hàm sẽ tƣơng ứng với một trạng thái lƣợng tử. Theo sơ đồ này, Eve sẽ cĩ đƣợc chính xác thơng tin trao đổi giữa Alice và Bob mà khơng bị phát hiện. Sơ đồ này cĩ tên là Sao chép gián tiếp (Indirect Coping) do Eve khơng thực sự sao chép giá trị mà Alice gửi mà tạo một trạng thái lƣợng tử mới cĩ trạng thái giống hệt trạng thái lƣợng tử Alice tạo. 3.1.4.1 Tạo bảng tham chiếu. Trong giao thức phân phối khố BB84, để thực hiện việc trao đổi thơng tin, Alice và Bob sẽ phải cơng khai các trạng thái lƣợng tử sử dụng trong giao thức (mà Eve dễ dàng biết). Ở trên ta đã biết đĩ là các trạng thái thuộc: - Bảng chữ cái z gồm hai trạng thái 0 , 1 1 - Bảng chữ cái x gồm hai trạng thái 0 ( 0 1 ) và x 2 1 1 ( 0 1 ) x 2 31 Xét một trạng thái lƣợng tử phụ thích hợp, ví dụ 01 22 Nguyễn Thanh Tùng 70
  71. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Khi đĩ 33 | 0 m 0.75 241 11 |1 m 0.25 242 2 6 2 6 2 | m 0.933 443 2 6 2 6 2 | m 0.067 444 trong đĩ mj (j = 1, 2, 3, 4) theo cơ học lƣợng tử là xác suất để trạng thái lƣợng tử 0 , 1 , , sụp đổ vào trạng thái khi tiến hành phép đo (theo cơ sở ). Ta xây dựng bảng tham chiếu sau: Trạng thái lƣợng tử mj 0.75 0.25 0.933 0.067 Dựa vào bảng tham chiếu trên, ta xây dựng hàm đơn trị Sk = f ( jk ), k = 1, 2, 3, 4, là một trong bốn trạng thái sử dụng trong BB84. 3.1.4.2 Sơ đồ tấn cơng. - Eve xây dựng bảng tham chiếu và hàm đơn trị nhƣ trên - Eve nhận tất cả các trạng thái lƣợng tử ngẫu nhiên mà Alice gửi cho Bob và tiến hành đo các trạng thái lƣợng tử nhận đƣợc. - Theo kết quả đo đƣợc, Eve sẽ biết đƣợc trạng thái lƣợng tử mà Alice gửi đi là gì dựa trên bảng tham chiếu. Ví dụ, nếu kết quả đo đƣợc là 0.25, Eve sẽ biết đƣợc trạng thái lƣợng tử Alice gửi đi là . - Eve sẽ huỷ trạng thái lƣợng tử nhận đƣợc từ Alice, do theo nguyên lý bất định, sau khi tiến hành phép đo, trạng thái lƣợng tử sẽ bị nhiễu loạn và thay đổi ngẫu nhiên so với trƣớc khi đo. - Eve tạo trạng thái lƣợng tử mới cĩ giá trị tƣơng ứng và gửi cho Bob Nguyễn Thanh Tùng 71
  72. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng 3.1.4.3 Kết luận về độ an tồn của giao thức BB84. Nhƣ trên ta thấy, giao thức phân phối khố lƣợng tử BB84 hồn tồn khơng an tồn mặc dù theo các nguyên lý của cơ học lƣợng tử thì giao thức BB84 là giao thức an tồn. Tuy nhiên với sự ra đời của giao thức BB84 cũng cho thấy một tiềm năng hết sức lớn lao của các hệ mã lƣợng tử trong tƣơng lai. 3.2. Kết luận về mã hố lƣợng tử và thám mã lƣợng tử. Hiện nay, mã hố lƣợng tử và thám mã lƣợng tử đang là một lĩnh vực nghiên cứu hết sức sơi động trên thế giới. Chƣơng này đã đƣa ra một ví dụ đơn giản về mã hố lƣợng tử và thám mã lƣợng tử. Giao thức phân phối khố BB84 chỉ là một giao thức đơn giản và hồn tồn khơng an tồn. Nhƣng cũng đã cho ta thấy bức tranh về một lĩnh vực hồn tồn mới mẻ, cịn nhiều vấn đề mở cần đầu tƣ nghiên cứu phát triển. Nguyễn Thanh Tùng 72
  73. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng CHƢƠNG 4. MƠ PHỎNG GIAO THỨC BB84 Nguyễn Thanh Tùng 73
  74. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Nguyễn Thanh Tùng 74
  75. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Nguyễn Thanh Tùng 75
  76. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng Nguyễn Thanh Tùng 76
  77. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng KẾT LUẬN Ngày nay, cùng với sự phát triển của khoa học hiện đại và Cơng nghệ thơng tin, ngành mật mã đã cĩ những bƣớc phát triển mạnh mẽ, đạt đƣợc nhiều kết quả lý thuyết sâu sắc và tạo cơ sở cho việc phát triển các giải pháp bảo mật, an tồn thơng tin trong mọi lĩnh vực hoạt động của con ngƣời: Bƣớc đầu tìm hiểu về tính tốn lƣợng tử và thuật tốn lƣợng tử trong đĩ chú trọng đi sâu vào ba chuyên đề chính là: Cơ sở tính tốn lƣợng tử, Cổng và mạch lƣợng tử, Thuật tốn lƣợng tử. Đồ án cũng bƣớc đầu tìm hiểu về mã hĩa lƣợng tử và thám mã lƣợng tử, đại diện là giao thức phân phối khĩa lƣợng tử BB84. Đồ án tập trung vào nghiên cứu cơ sở lý thuyết.Tuy cịn nhiều điểm cần phải nghiên cứu và hồn thiện nhƣng do thời gian và trình độ cịn hạn chế nên khơng thể tránh khỏi những nhƣợc điểm, rất mong đƣợc sự gĩp ý của các Thầy, Cơ và các bạn. Cuối cùng em xin cảm ơn thầy giáo Thạc Sĩ Trần Ngọc Thái đã tận tình chỉ bảo giúp đỡ em hồn thành đồ án này Nguyễn Thanh Tùng 77
  78. Đồ án tốt nghiệp Mã hĩa lượng tử và ứng dụng TÀI LIỆU THAM KHẢO [1] Kim Cƣơng – Tốn học cao cấp, Tập 1, Phần 1: Đại số, Nhà xuất bản Giáo dục, 1993 [2] Lê Quang Minh – Tenxơ và Toocxơ, Nhà xuất bản Giáo dục, 1998 Giải tích hàm, Nhà xuất bản Khoa học và Kỹ thuật, 1998 [3] Phạm Quý Tƣ, Đỗ Đình Thanh – Cơ học lượng tử, Nhà xuất bản Đại học Quốc Gia Hà Nội, Tái bản lần thứ nhất, 2003 [4] Nguyễn Quốc Khánh, Nguyễn Hữu Mạc – Cơ học lượng tử 2, Nhà xuất bản Đại học Quốc Gia Thành phố Hồ Chí Minh, 2000 [5] Vũ Văn Hùng – Cơ học lượng tử, Nhà xuất bản Đại học Sƣ phạm, 2004 [6] Nguyễn Hồng Phƣơng – Lý thuyết Nhĩm và ứng dụng vào Vật lý học lượng tử, Nhà xuất bản Khoa học và Kỹ thuật, 2002 [7] Phạm Việt Hùng – Mã hĩa lượng tử và và mơ phỏng trên máy tính, Đồ án tốt nghiệp cao học Trƣờng Đại Học Quốc Gia Hà Nội, 2006 Nguyễn Thanh Tùng 78