1

ĐẠI HỌC BÁCH KHOA HÀ NỘI

LUẬN VĂN THẠC SĨ

NGHIÊN CỨU HỆ MẬT KHÁNG LƯỢNG TỬ
MCÉLIECE

Nguyen Thanh Long

Hà Nội - 2023


2
MỤC LỤC
LỜI CẢM ƠN.................................................................................................... i
LỜI CAM ĐOAN .............................................................................................. ii
MỤC LỤC ........................................................................................................ iii
DANH MỤC HÌNH VẼ .................................................................................... v
DANH MỤC BẢNG BIỂU .............................................................................. vi
LỜI MỞ ĐẦU ................................................................................................. vii
CHƯƠNG 1: TỔNG QUAN VỀ MÁY TÍNH LƯỢNG TỬ VÀ MẬT MÃ
KHÁNG LƯỢNG TỬ .................................................................................. 1
1.1 Tổng quan về máy tính lượng tử .............................................................. 1
1.1.1 Khái niệm về máy tính lượng tử ............................................................... 1
1.1.2 Nguyên lý hoạt động của máy tính lượng tử ............................................ 1
1.1.3 Ưu nhược điểm của máy tính lượng tử ..................................................... 4
1.1.4 Các máy tính lượng tử hiện nay ............................................................... 5
1.2 Mật mã kháng lượng tử ........................................................................... 5
CHƯƠNG 2: HỆ MẬT MCELIECE ............................................................... 11

2.1 Cơ sở toán học ...................................................................................... 11
2.1.1 Lý thuyết mã sửa lỗi .............................................................................. 11
2.1.2 Mã tuyến tính ........................................................................................ 20
2.1.3 Mã Goppa.............................................................................................. 27
2.1.3.3 ........................................................................................................... 34
2.2 Hệ mật McEliece ....................................................................................... 37
2.2.1 Q trình tạo khóa ................................................................................. 37
2.2.2 Q trình mã hóa ................................................................................... 37
2.2.3 Quá trình giải mã ................................................................................... 37
2.3 Đánh giá độ an tồn của hệ mật ............................................................. 38
2.3.1. Tấn cơng thông thường ......................................................................... 38
2.3.2. Tấn công lượng tử ................................................................................ 43
CHƯƠNG 3. CÀI ĐẶT CHƯƠNG TRÌNH MƠ PHỎNG HỆ MẬT ............... 55
3.1 Các tham số của hệ mật McEliece ..........................................................55


3
3.2 Mơ phỏng hệ mật ...................................................................................55
3.2.1 Mơ-đun tạo khóa .....................................................................................55
3.2.2 Mơ-đun mã hóa ......................................................................................56
3.2.3 Mơ-đun giải mã ......................................................................................57
3.2.4 Đánh giá hiệu quả thuật toán ..................................................................58
KẾT LUẬN ......................................................................................................60
TÀI LIỆU THAM KHẢO ............................................................................... 61
PHỤ LỤC ........................................................................................................ 63


4
DANH MỤC HÌNH VẼ
Hình 1.1 Mặt cầu Block ..................................................................................... 2

Hình 3.1 Lưu đồ thuật tốn tạo khóa McEliece
56
Hình 3.2 Kết quả tạo khóa McEliece ...............................................................56
Hình 3.3Lưu đồ mã hóa McEliece ....................................................................57
Hình 3.4 Kết quả mã hóa McEliece .................................................................57
Hình 3.5 Lưu đồ giải mã McEliece..................................................................58
Hình 3.6 Kết quả giải mã McEliece ................................................................. 58


5
DANH MỤC BẢNG BIỂU
Bảng 1.1 Ví dụ về các lược đồ mật mã được triển khai rộng rãi và độ an toàn của
các lược đồ này chống lại các tấn công tiền lượng tử và hậu lượng tử tốt nhất
được biết đến [7] ................................................................................................ 7
Bảng 3.1 Các tham số của McEliece
55
Bảng 3. 2 So sánh các hệ mật McEliece, NTRU, SABER và Kyber .................58


6
LỜI MỞ ĐẦU
Các nghiên cứu đầu tiên về máy tính lượng tử bắt đầu từ năm 1980 và cho
đến năm 1994 thuật tốn Shor được cơng bố đã cho thấy được sự ảnh hưởng của
máy tính lượng tử đối với mật mã. Đứng trước nguy cơ máy tính lượng tử có thể
phá được mật mã khóa cơng khai, các nhà khoa học đã đề xuất các hướng nghiên
cứu mới là “mật mã kháng lượng tử” để chống lại ảnh hưởng của máy tính lượng
tử trong tương lai.
Năm 2016, NIST đã khởi động một dự án nhằm thu hút, đánh giá và tiêu
chuẩn hóa các thuật tốn mật mã khóa cơng khai kháng lượng tử nhằm bảo vệ các
thông tin nhạy cảm trước sự ra đời của máy tính lượng tử. Một trong số ứng viên

đã lọt vào vòng 3 là hệ mật mã McEliece được đề xuất năm 1978, tác giả là Robert
McEliece và qua các phiên bản mức độ bảo mật của hệ mật mã McEliece vẫn rất
ổn định và có khả năng kháng lại tấn cơng máy tính lượng tử.
Nội dung đồ án được chia làm 3 chương như sau:
Chương 1: Tổng quan về máy tính lượng tử và mật mã hậu lượng tử
Chương này giới thiệu về máy tính lượng tử và mật mã kháng lượng tử
Chương 2: Hệ mật McEliece
Chương này tìm hiểu về cơ sở toán học của hệ mật: lý thuyết mã sửa sai,
mã tuyến tính và mã Goppa, hệ mật McEliece và đánh giá độ an toàn của hệ mật.
Chương 3: Cài đặt chương trình mơ phỏng hệ mật
Chương này trình bày các tham số của hệ mật McEliece, mô phỏng hệ mật
McEliece và đánh giá hiệu quả của hệ mật McEliec với Keyber, SABER, NTRU.


1
CHƯƠNG 1: TỔNG QUAN VỀ MÁY TÍNH LƯỢNG TỬ VÀ MẬT MÃ
KHÁNG LƯỢNG TỬ
1.1 Tổng quan về máy tính lượng tử
1.1.1 Khái niệm về máy tính lượng tử
Máy tính lượng tử (cịn gọi là siêu máy tính lượng tử) là một thiết bị tính
tốn sử dụng trực tiếp các hiệu ứng của cơ học lượng tử như tính chồng chập và
vướng víu lượng tử để thực hiện các phép tốn trên dữ liệu đưa vào. Máy tính
lượng tử có phần cứng khác hẳn với máy tính kỹ thuật số dựa trên tranzitor. Trong
khi máy tính kỹ thuật số địi hỏi dữ liệu phải được mã hóa thành các chữ số nhị
phân (bit), mà mỗi số được gán cho một trong hai trạng thái (0 và 1), tính tốn
lượng tử sử dụng các qubit (bit lượng tử) mà chúng có thể ở trong trạng thái chồng
chập lượng tử. Các thuật toán lượng tử tận dụng điều này và biến đổi tất cả các
trạng thái cùng một lúc. Các thuộc tính này cho phép máy tính lượng tử chạy các
thuật tốn có thể giải các bài tốn được coi là khó đối với máy tính cổ điển, vốn bị
hạn chế ở một trạng thái duy nhất.

1.1.2 Nguyên lý hoạt động của máy tính lượng tử
Nguyên lý hoạt động của máy tính lượng tử hiện đại hoàn toàn nằm trên lý
thuyết ứng dụng cơ học lượng tử. Trong máy tính lượng tử, dữ liệu không được
xử lý bởi các electron đi qua transistor nữa, mà xử lý bởi các nguyên tử được "giam
giữ" với tên gọi là quantum bit hay qubits.
1.1.2.1 Thông tin về qubit
Máy tính lượng tử thực hiện hoạt động với qubit (quantum bit, hay còn gọi
là bit lượng tử) thay vì các bit nhị phân như máy tính vốn dựa trên các bóng bán
dẫn. Qubit mở ra tiềm năng cho máy tính lượng tử thơng qua các thuật tốn phức
tạp và thực hiện các phép tính nhanh hơn nhiều so với các hệ thống hiện có.
Bit là đơn vị thơng tin cơ bản trong công nghệ truyền thông tin hiện nay.
Mỗi bit chỉ có thể mang giá trị là 0 hay 1 dựa vào các tín hiệu điện: khơng hoặc
có.
Qubit cũng có một vài thuộc tính như thế nhưng nhìn chung về tồn diện thì
khác. Các khác biệt này giúp cho qubit có một khả năng vượt trội.
Một qubit hay bit lượng tử, là một đơn vị của thông tin lượng tử. Thông tin


2
đó miêu tả một hệ cơ học lượng tử có hai trạng thái cơ bản, thường được ký hiệu
|0> và |1>.
Một trạng thái qubit thuần túy là chồng chập lượng tử tuyến tính của hai
trạng thái cơ bản trên. Điều này khác với bit của thông tin cổ điển, chỉ nhận một
trong hai giá trị 0 hoặc 1.
1.1.2.2 Các trạng thái của qubit, khả năng mang vô hạn thông tin
Các trạng thái của qubit được xác định dựa vào 2 trạng thái cơ bản đó là |0>
và |1>. Như đã nói, khác với bit cổ điển, qubit khơng chỉ nhận các giá trị ứng với
các trạng thái đó mà nó còn nhận giá trị chồng chập là sự tổ hợp tuyến tính của 2
trạng thái đó:
|P> = a|0> + b|1>

Với a, b là các hằng số tỉ lệ với cường độ của trạng thái tổ hợp ứng với trạng
thái cơ bản tương ứng |a|2 + |Ạ| 2 = 1

Hình 1.1 Mặt cầu Block
Theo hệ thức đó, ta thấy rằng, khơng gian trạng thái tổ hợp |P> của một đơn
qubit về phương diện hình học được biểu diễn trên một mặt cầu, gọi là mặt cầu
Block. Đây là một không gian 2 chiều.
Về bản chất, mỗi điểm trên mặt cầu biểu diễn cho một trạng thái của qubit.
Mặt cầu thì có vơ hạn điểm, do đó, ta thấy ngay khả năng biểu diễn thông tin lượng
tử lên đến vô hạn chứ không phải chỉ là 0 hoặc 1 như bit cổ điển.
1.1.2.3 Trao đổi thông tin lượng tử giữ các qubit
Mỗi qubit đều mang thông tin lượng tử. Thông tin phải được trao đổi qua
lại giữa các qubit và một trong các lĩnh vực mới là tìm hiểu cơ chế trao đổi thông


3
tin giữa các qubit và cách xử lý thông tin thu được.
Thơng tin máy tính lượng tử cũng có thể được biểu diễn như là sự chồng
chất lượng tử đồng thời của cả hai mã 0 hoặc 1 (bit lượng tử hay “qubit”). Trong
thời gian thực hiện chồng chất, các qubit tương tác và tính tốn với các qubit khác
thơng qua các lượng tử thành phần xung quan. Cuối cùng, mỗi qubit sẽ thực hiện
phân biệt lượng tử và chọn các mã 0 hoặc 1 như là hình thức làm việc cổ điển của
nó.
Trạng thái chồng chất lượng tử là một yếu tố lượng tử sẽ chỉ trả về một kết
quả trong một tiêu chuẩn khi được đo lường. Tiếp theo là một ngun tắc về
“vướng víu lượng tử”, nó được hiểu như là một quá trình tương đối phức tạp, nói
lên sự tương tác của các điện tử, phân tử, các photon và các hạt khác: “Vướng víu
lượng tử được xem như là một sự tương quan của các trạng thái qubit khác nhau
với nhau. Khi chúng ta thực hiện các hoạt động và các phép đo trên một qubit và
vướng mắc với qubit khác, chúng sẽ tự động tìm hiểu và thay đổi trạng thái của

các đối tác. Điều này sẽ cung cấp một loại giao thức song song, gần như cho phép
một hệ thống lượng tử có thể thực hiện một số tính tốn nhanh hơn so với một hệ
thống máy tính cổ điển”.
Tính chất "song song lượng tử'' trên này là thế mạnh cơ bản của máy tính
lượng tử.
Thuật tốn được sử dụng để chạy các qubit giống như thuật toán mà Simon
đưa ra, được cho là nhanh hơn bất cứ điều gì so với một máy tính dựa trên bóng
bán dẫn để thực hiện thuật tốn.
Theo phân tích của Ars Technica cho biết: “Các máy tính lượng tử là khá
đơn giản, hai qubit đăng ký thực hiện từ SQUID (được hiểu như là một thiết bị
giao thoa lượng tử siêu dẫn), hai SQUID có thể bổ sung cho các hoạt động không
đăng ký trước (chẳng hạn như hoạt động đọc/xuất) và kết hợp với hiện tượng cộng
hưởng sóng nhằm tạo ra sản phẩm như là một bộ nhớ. Tuy nhiên, phần quan trọng
nhất đó là băng thông bus cho các cặp qubit giao tiếp với nhau, thực hiện các hoạt
động logic khác nhau. Các bộ cộng hưởng có hình học cố định và chỉ có thể cộng
hưởng ở một tần số sóng. Vì vậy, bộ nhớ có thể được điều dọc hoặc bằng văn bản
thơng qua các thay đổi từ trường để nó giống như là một hiện tượng cộng hưởng.
Do đó có thể hiểu rằng hoạt động giữa các qubit được thực hiện bằng cách áp dụng
các cơng nghệ vi sóng dựa trên cơng nghệ bus trang bị sẵn bên trong”.
Cuối cùng, khi chấm dứt hợp các thuật toán, kết quả cần phải được đọc ra.


4
Trong trường hợp của một máy tính cổ điển, lấy mẫu từ phân bố xác suất trên sổ
đăng ký bit để có được một chuỗi bit xác định. Quantum máy móc, đo lường trạng
thái qubit, tương đương với sụp đổ các lượng tử nhà nước xuống đến một phân
phối cổ điển (với các hệ số trong trạng thái cổ điển là độ lớn bình phương của hệ
số của các trạng thái lượng tử), tiếp theo là lấy mẫu từ phân phối. Lưu ý rằng điều
này phá hủy các trạng thái lượng tử ban đầu. Nhiều thuật toán sẽ chỉ cung cấp cho
câu trả lời chính xác với một xác suất nhất định. Tuy nhiên, bằng cách liên tục

khởi tạo, chạy và đo lường máy tính lượng tử, xác suất nhận được câu trả lời chính
xác có thể được tăng lên.
1.1.3 Ưu nhược điểm của máy tính lượng tử
1.1.3.1 Ưu điểm
Máy tính lượng tử sẽ có thể thực hiện bất kỳ nhiệm vụ mà một máy tính cổ
điển có thể làm. Nếu chúng ta sử dụng các thuật toán cổ điển trên một máy tính
lượng tử, nó sẽ chỉ đơn giản là thực hiện các tính tốn một cách tương tự như một
máy tính cổ điển.
Máy tính lượng tử quy mơ lớn sẽ có khả năng giải được các vấn đề phức tạp
một cách nhanh hơn bất kỳ một máy tính cổ điển sử dụng các thuật toán tốt nhất
hiện nay, như thuật tốn Shor để phân tích số tự nhiên thành tích các số ngun tố,
hoặc mơ phỏng hệ lượng tử nhiều hạt. Cũng có những thuật tốn lượng tử, như
thuật tốn Simon, cho phép máy tính hoạt động nhanh hơn bất kỳ một máy tính
dựa trên thuật tốn xác suất cổ điển.
Có khả năng ứng dụng thực tế.
Được sử dụng trong các ngành khoa học cần độ xử lý cao và tốc độ lớn, dữ
liệu nhiều như: trung tâm khí tượng thủy văn,y khoa,...
Được sử dụng vào các dịng sản phẩm điện tử.
Trên máy tính lượng tử có thể thực hiện cùng một lúc một phép tính lên vơ
vàn các giá trị đầu vào khác nhau, tức là thực hiện tính tốn song song, thay vì làm
tuần tự từng phép tính như vậy cho từng đầu vào như ở máy tính truyền thống.
Sự phát triển của "máy tính lượng tử" dựa trên vật liệu silicon có thể sẽ
khơng cịn là giấc mơ. Giáo sư Murdin cho rằng: "Máy tính lượng tử có thể giải
quyết một số vấn đề hiệu quả hơn nhiều so với máy tính thơng thường và chúng
đặc biệt hữu ích cho an ninh bởi vì họ có thể nhanh chóng giải mã số hiện có và
tạo ra các mã không thể giải”.


5
1.1.3.2 Nhược điểm

Hạn chế chính của máy tính lượng tử là giống như sức mạnh của nó. Các
tính tốn được thực hiện trong khi qubit hàm sóng lượng tử là ở trong trạng thái
chồng chất, đó là những gì cho phép nó để thực hiện các tính tốn sử dụng cả 1 &
0 cùng một lúc.
Công nghệ cần thiết để xây dựng một máy tính lượng tử hiện đang vượt quá
tầm tay của con người. Điều này thực tế là do các nhà sản xuất, cơ bản là do hoạt
động của máy tính lượng tử, bị phá hủy ngay sau khi hoạt động, chịu ảnh hưởng
bởi môi trường . Nỗ lực đấu tranh chống vấn đề này đã không mấy thành cơng,
một số vấn đề mã hóa cũng gặp phải nhiều khó khăn chủ yếu là tất cả các thuật
tốn mã hóa - giải mã
1.1.4 Các máy tính lượng tử hiện nay
a) Máy tính lượng tử của Google
Máy tính lượng tử của Google có tên Sycamore được trang bị một con chip
lượng tử 54 qubit, hay còn gọi là các hạt lượng tử có kiểm sốt - mỗi hạt lượng tử
có thể duy trì hai trạng thái 0 và 1 cùng lúc[12].
b) Máy tính lượng tử của Trung Quốc
Zuchongzhi 2 - chiếc máy tính lượng tử siêu dẫn có thể lập trình 66 qubit
được đặt theo tên một cuốn sách toán học từ Thế kỷ - nhanh hơn 10 triệu lần so
với siêu máy tính nhanh nhất thế giới và mạnh hơn nhiều so với Sycamore 55 qubit
của Google[13].
1.2

Mật mã kháng lượng tử
Do sự phát triển trong lĩnh vực máy tính lượng tử , nhu cầu phát triển và

triển khai các thuật toán mật mã kháng lượng tử trở nên cấp thiết hơn. Dẫn đến
nhiều thuật toán phổ biến nhất hiện nay sẽ bị phá vỡ bởi thuật toán Shor. Thuật
toán Shor được Peter Shor [4] đề xuất đã khám phá ra các thuật tốn máy tính
lượng tử thời gian đa thức giải quyết bài tốn phân tích số ngun và bài toán



6
logarit rời rạc trong các nhóm liên quan đến mật mã khóa cơng khai. Hệ quả của
thuật tốn Shor là nếu một máy tính lượng tử có khả năng mở rộng, khả năng xử
lý lỗi có thể được xây dựng, thì mật mã khóa cơng khai dựa trên các bài tốn phân
tích số ngun và logarit rời rạc sẽ bị phá vỡ hồn tồn. Các lược khóa cơng khai
sử dụng phổ biến như lược đồ RSA, các lược đồ dựa trên đường cong eliptic khơng
cịn an tồn.
Thuật tốn Shor (Shor’s algorithm) . Ý tưởng của thuật tốn Shor là tính
bậc của phần tử x trong Zn*, tức là số nguyên r nhỏ nhất sao cho xr = 1 (mod n).
Như vậy sẽ giảm ngẫu nhiên từ phân tích số thành tìm bậc của một phần tử. Bậc
của phần tử này là một ước của ộ(n) và giá trị này sẽ xác định một một thừa số
không tầm thường của n. Chính xác hơn, thuật tốn Shor có độ phức tạp O((logn)2
(loglogn)(logloglogn)) để phân tích số nguyên dương n [5]. Đây là một thuật toán
thời gian đa thức như là một hàm của "kích thước" của n, là logn. Tương tự như
vậy, thuật toán Shor cũng đã đưa ra thuật toán sử dụng hai lũy thừa mô-đun và hai
phép biến đổi Fourier lượng tử để tính được logarit rời rạc trong thời gian đa thức
với độ phức tạp tính tốn là O (n3). Các thuật toán lượng tử của Shor đối với phân
tích số ngun và tính logarit rời rạc có độ phức tạp tính tốn gần bằng nhau và
vào khoảng O( n3). Nhưng có khoảng cách lớn về độ phức tạp tính tốn giữa tiền
lượng tử và lượng tử đối với bài tốn logarit rời rạc so với phân tích số nguyên.
Kết quả tốt nhất công bố bởi S.Beauregard [6] rơi vào khoảng 2n qubit đối với các
thuật toán lượng tử phân tích số nguyên. Và cần 6n qubit đối với các thuật tốn
lượng tử tính logarit rời rạc.
Tác động của máy tính lượng tử đối với mật mã khóa bí mật ít mạnh mẽ
hơn nhiều so với mật mã khóa cơng khai. Phương pháp tấn cơng chính có thể được
thực hiện bởi một máy tính lượng tử dựa trên thuật toán của Grover.
Thuật toán Grover (Grover’s algorithm). Thuật toán lượng tử được gọi là
thuật toán Grover [9] là một thuật tốn tìm kiếm có khả năng tìm một phần tử trong
cơ sở dữ liệu khơng có thứ tự gồm N = 2n phần tử bước

trên một máy tính lượng tử. Đây là tốc độ tăng bậc hai so

chỉ chỉ trong O ^y/N

)

với phương pháp
. ....................., Ă N ,
Ắ, Ắ
trên máy tính cổ điển, u cầu trung bình — bước sử dụng tìm kiếm tuyến tính.


7
Thuật toán hoạt động bằng cách trước tiên khởi tạo hệ thống với một phân
phối có cùng biên độ ở mỗi số N với các trạng thái n-bit, trong đó bình phương của
giá trị tuyệt đối của biên độ ở một trạng thái bằng xác suất ở trạng thái đó.

)

Thuật tốn sau đó lặp lại một vịng lặp hoạt động O (JN lần. Các phép toán được
thực hiện là một ước lượng của trạng thái bởi một tiên tri lượng tử (quantum
oracle), một phép quay pha có điều kiện tùy thuộc vào việc ước lượng trạng thái
trước đó và một phép biến đổi khuếch tán (diffusion transform).
Đối với mỗi lần lặp của vịng lặp đã đề cập trước đó, biên độ ở trạng thái
lặp, biên độ ở trạng thái mong muốn sẽ đạt đến O (1). Khi lấy mẫu, trạng thái kết
quả sẽ ở trạng thái mong muốn, nghĩa là phần tử được tìm kiếm đã được tìm thấy,
với xác suất ít nhất là 1/2.
mong muốn được tăng thêm O

. Điều này có nghĩa là sau O (yfN


) lần

Dựa trên kịch bản có thể xảy ra này, các nhà nghiên cứu đã nghiên cứu các
cách tiềm năng để xây dựng mật mã khóa cơng khai dựa trên các vấn đề tính tốn
khác nhau, hy vọng các thuật tốn này sẽ khơng dễ bị tấn cơng bởi máy tính lượng
tử. Thuật ngữ mật mã kháng lượng tử được sử dụng để mơ tả các lược đồ mật mã
như vậy. Nói một cách tổng quát hơn, cụm từ “mật mã kháng lượng tử” cũng có
thể áp dụng cho các lược đồ khóa cơng khai ngun thủy khác.
Bảng 1.1 Ví dụ về các lược đồ mật mã được triển khai rộng rãi và độ an toàn
của các lược đồ này chống lại các tấn công tiền lượng tử và hậu lượng tử tốt
nhất được biết đến [7]
Tên thuật tốn

Hàm

Độ an tồn tiền

Độ an tồn hậu

lượng tử

lượng tử

Mật mã khóa bí mật
AES-128

Mã khối

128


64 (Grover)

AES-256

Mã khối

256

128 (Grover)

Salsa20

Mã dòng

256

128 (Grover)


8
GMAC

MAC

128

Không tác động

Poly1305


MAC

128

Không tác động

SHA-256

Hàm băm

256

128 (Grover)

SHA-3

Hàm băm

256

128 (Grover)

Mật mã khóa cơng khai
RSA-3072

Mã hóa

128


Bị phá vỡ (Shor)

RSA-3072

Chữ ký số

128

Bị phá vỡ (Shor)

DH-3072

Trao đổi khóa

128

Bị phá vỡ (Shor)

DSA-3072

Chữ ký số

128

Bị phá vỡ (Shor)

ECDH 256 bit

Trao đổi khóa


128

Bị phá vỡ (Shor)

ECDSA 256 bit

Chữ ký số

128

Bị phá vỡ (Shor)

Hiện tại, các nghiên cứu về mật mã kháng lượng tử ch lủ yếu tập trung vào
một số cách tiếp cận như sau.
Mật mã dựa trên lưới: Các thuật tốn dựa trên lưới được Miklós Ajtai đưa
ra đầu tiên năm 1996, với ý tưởng các thuật tốn mật mã an tồn có thể được xây
dựng dựa trên một bài tốn lưới khó. Cách tiếp cận này bao gồm các thuật toán
mật mã như Learning With Error (LWE), Ring Learning With Error (Ring-LWE),
trao đổi khóa LWE và chữ ký số LWE, mật mã khóa cơng khai NTRU hoặc lược
đồ mã hóa GGH, chữ ký số NTRU và BLISS mới. Các cấu trúc dựa trên lưới hiện
là ứng cử viên quan trọng cho mật mã hậu lượng tử. Khơng giống như các lược đồ
mật mã khóa cơng khai RSA, Diffie-Hellman hoặc mật mã trên đường cong elliptic
dễ dàng bị tấn cơng bởi một máy tính lượng tử, một số cấu trúc dựa trên lưới có
khả năng chống lại sự tấn cơng của cả máy tính cổ điển và máy tính lượng tử. Hơn
nữa, nhiều cấu trúc dựa trên lưới được coi là an toàn với giả định rằng một số bài
tốn tính tốn lưới được nghiên cứu kỹ lưỡng không thể giải quyết một cách hiệu
quả. Các nghiên cứu chỉ ra rằng NTRU có thuộc tính an toàn hơn các kỹ thuật dựa
trên lưới khác.



9
Mật mã đa biến: Cách tiếp cận này bao gồm các hệ mật như lược đồ
Rainbow dựa trên độ khó của việc giải các hệ phương trình đa biến. Giải hệ phương
trình đa biến được chứng minh là NP đầy đủ. Đó là lý do tại sao những lược đồ
này được coi là những ứng cử viên sáng giá cho mật mã kháng lượng tử. Hiện nay,
mật mã đa biến ổn định hơn và các lược đồ tốt nhất đã chống lại được thử thách
của thời gian. Các chứng minh đã thừa nhận rằng mật mã đa biến thành công hơn
khi tiếp cận để xây dựng các lược đồ chữ ký số vì các lược đồ đa biến cung cấp
chữ ký ngắn nhất trong số các thuật toán kháng lượng tử.
Mật mã dựa trên hàm băm: Cách tiếp cận này bao gồm các thuật toán mật
mã như lược đồ chữ ký số Lamport, lược đồ chữ ký số Merkle, các lược đồ XMSS
và SPHINCS. Chữ ký số dựa trên hàm băm được phát minh vào cuối những năm
1970 bởi Ralph Merkle và kể từ đó đã được nghiên cứu như một sự thay thế cho
các chữ ký số như RSA và DSA. Hạn chế chính của các lược đồ này là đối với bất
kỳ khóa cơng khai dựa trên hàm băm nào giới hạn về số lượng chữ ký có thể được
ký bằng cách sử dụng bộ khóa riêng tương ứng. Điều này đã làm giảm sự quan
tâm đến các lược đồ này cho đến khi xuất hiện mối đe dọa từ các tấn cơng của máy
tính lượng tử đối với mật mã. Và các lược đồ chữ ký số Merkle, lược đồ chữ ký số
dựa trên hàm băm XMSS và gần đây nhất là lược đồ chữ ký số không trạng thái
SPHINCS được biết đến rộng rãi với khả năng kháng lại các tấn cơng của máy tính
lượng tử.
Mật mã dựa trên mã: Năm 1978, Robert McEliece công bố đề xuất của
mình về hệ mật mã dựa trên mã. Các thuật toán mật mã dựa trên mã sửa lỗi, chẳng
hạn như thuật tốn mã hóa McEliece, Niederreiter và lược đồ chữ ký số Courtois,
Finiasz và Sendrier Signature liên quan. Chữ ký McEliece ban đầu sử dụng mã
Goppa ngẫu nhiên đã tồn tại trong hơn 30 năm. Các hệ mật dựa trên mã có tốc độ
cao và độ phức tạp thấp trong q trình mã hóa và giải mã nhưng nó u cầu lượng
lớn bộ nhớ do khóa cơng khai lớn. Đã có nhiều biến thể của lược đồ McEliece tìm
cách đưa thêm cấu trúc vào mã được sử dụng để giảm kích thước của các khóa, đã
được chứng minh là khơng an tồn. Nhóm nghiên cứu mật mã kháng lượng tử

được tài trợ bởi Ủy ban Châu Âu đã khuyến nghị hệ thống mã hóa khóa cơng khai
McEliece như một ứng cử viên để bảo vệ lâu dài trước các cuộc tấn cơng bởi máy
tính lượng tử.
Mật mã dựa trên đẳng giống (isogeny): Cách tiếp cận này dựa trên một


10
số hình thái nhất định giữa các đường cong elliptic khác nhau. Máy tính lượng tử
có thể giải quyết bài tốn lơgarit rời rạc trên đường cong elliptic một cách hiệu
quả, vì vậy mật mã trên đường cong elliptic hiện nay khơng có khả năng chống lại
các tấn cơng của máy tính lượng tử. Mật mã dựa trên đẳng giống dựa trên các
đường cong elliptic, nhưng không trực tiếp như các phương pháp ECC hiện tại.
Trong khi các phương pháp ECC hiện tại thực hiện các phép tính trên một đường
cong elliptic, các phương pháp isogeny dựa trên mạng lưới các hàm giữa các
đường cong elliptic.


11
CHƯƠNG 2: HỆ MẬT MCELIECE
2.1 Cơ sở toán học
2.1.1 Lý thuyết mã sửa lỗi
2.1.1.1 Các khái niệm cơ bản
Mã sửa lỗi (Error Correction coding) là kỹ thuật khống chế, phát hiện và
sửa lỗi trong quá trình truyền dữ liệu qua kênh có nhiễu.
Mã sửa lỗi sử dụng thơng tin dư thừa (Redundancy) được mã hóa thêm vào
dữ liệu phía bên phát. Thơng tin dư thừa sẽ được phía thu sử dụng để sửa lỗi mà
không cần phát lại tin.
Phân loại mã sửa lỗi:
•


Mã khối (Block codes) thơng tin được mã hóa và chèn thêm phần dư thừa
theo từng khối.
- Mã khối
- Mã khối tuyến tính
- Mã vịng CRC
- Mã BCH, LDPC, Reed Solomon

•

Mã chập (Convolutional codes) thơng tin được biến đổi theo các hàm truyền
đạt (phép tích chập). Khơng có giới hạn rõ ràng giữa thông tin và phần dư
thừa.
- Mã chập
- Mã turbo

Định nghĩa 1.1 Tốc độ mã
Giả thiết K là tập hợp 2 phần tử 0 và 1
V biểu diễn vector n phần tử của F2
Số binary (n,k) là tập hợp 2k điểm trong không gian F”
Mã (n, k) là chấp nhận k bit đầu vào và tạo ra n bit đầu ra


12
Tốc độ mã của mã
Định nghĩa 1.2
1. Cho các từ mã trong C : X = X
được xác định như sau:

1


1
d

( ,, y, ) =
x

if xi £ yf

0 if X i = yt

x2...xn

và y = y1 y2...yn

ta ký hiệu

, khi đó khoảng cách Hamming của hai từ mã X, y e C
( , y ) = ẳ d (xi, yt)

d x

i=

1

2. Trọng số Hamming của từ mã X là số ký hiệu khác không trong X ký hiệu w
X

(


)

Như vậy khoảng cách Hamming giữ 2 từ mã trong C X =

X1 x2...xn

và y = yy2...yn là

tổng các vị trí tương ứng mà chúng khác nhau tức là các số i(i = 1,2,...n) sao cho
xi £ yi

Ví dụ 1.1
1. d (10100,10001) = 2, d (11100,10011) = 2
2. w (10101) = 3, w (10111) = 4
Định nghĩa 1.3
Khoảng cách Hamming cực tiểu của từ mã C là khoảng cách Hamming nhỏ
nhất của 2 từ mã khác nhau trong 8 được ký hiệu như sau:

|

d (C) = min d (X, y) | Vx, y e C, X £

Như vậy mã C có 3 đặc tính chủ yếu là:
1. Chiều dài của các từ mã trong C
2. Tổng số các từ mã trong C
3. Khoảng cách Hamming cực tiểu của C
Ta ký hiệu mã (n, k, d) là mã có độ dài n, chứa k từ mã và khoảng cách cực tiểu d


13


= d (C )
2.1.1.2 Phát hiện lỗi và sửa lỗi
a) Nguyên lý phát hiện lỗi và sửa lỗi
Giả sử kênh truyên gửi đi một từ mã c e C và bên kia nhận được một xâu x.
Nguyên lý phát hiện lỗi và sửa lỗi như sau:
•

Nguyên lý phát hiện lỗi: Kiểm tra xâu nhận được có phải là một từ mã trong
C hay khơng, nếu khơng phải từ mã thì xâu nhận được là sai, có lỗi.

•

Ngun lý sửa lỗi: Khi phát hiện xâu nhận được là sai, một từ mã

cx

có

khoảng cách Hamming gần nhất với x ( theo quy tắc giải mã Nearest
Neighbor) để thay cho xâu x bị lỗi, tức là đã sửa được lỗi, và coi c là từ mã
x

c đã được gửi đi. (c là giải mã của xâu x). Như vậy nguyên lý phát hiện lỗi
x

và sửa lỗi đều dựa trên khoảng cách Hamming
Định nghĩa 1.4
Cho C là mã với độ dài n, khi đó
1. Mã C gọi được là phát hiện được s lỗi, nếu Vc e C và mọi xâu x c ta có: nếu d


(x, c) < 5 thì x £ C.
2.

Mã C gọi là sửa được t lỗi, nếu Vc e C và mọi xâu x c ta có: nếu d (x, c) <

t thì x là từ mã gần nhất với c.
Ta có thể giải thích rõ hơn cho định nghĩa trên như sau:
1. Mã C gọi là phát hiện được 5 lỗi nếu với mọi từ mã c gửi đi, mà có s bit bị thay
đổi ở xâu nhận được x, thì xâu này khơng phải là một từ mã trong C, vì vậy phát
hiện được từ mã gửi đi đã bị lỗi.
2. Mã C gọi là sửa được t lỗi nếu khi gửi đi từ mã c, mà có t bit bị thay đổi ở xâu
nhận được x, thì sẽ thay thế được xâu này với một từ mã gần nó nhất có d (x, c) <
t (theo quy tắc giải mã Nearest Neighbor)
Định lý 1.1
Cho C là mã với độ dài n, khi đó:


14
1. Mã C phát hiện được k lỗi trong mọi từ mã nếu khoảng cách Hamming d(C)>
k +1
2. Mã C sửa được k lỗi trong mọi từ mã nếu khoảng cách Hamming d (C )> 2k
+1

Như vậy, khả năng phát hiện và sửa lỗi của một mã phụ thuộc vào khoảng cách
Hamming cực tiểu d (c) của bộ mã đó, và d (C) càng lớn thì khả năng phát hiện
lỗi và sửa lỗi của mã càng cao.
Hệ quả 1.1.1
Nếu mã £ có khoảng cách Hamming cực tiểu là d (C) = d, thì C có thể
phát hiện được tối đa k = |_d - 1J lỗi, và có thể sửa được tối đa k =


lỗi

Ví dụ 1.2 Giả sử C là bộ mã gồm các từ mã

{c = 00000000, c2 = 11111000, c3 = 01010111, c4 = 10101111}
1. C có thể phát hiện và sửa bao nhiêu lỗi trong một từ mã bị nhận sai?
2. Khi gửi đi từ mã c = 00000000, nếu nhận được một trong các xâu: x

=11011000
x

=11111000

x = 10101000
Trường hợp nào thì xâu nhận được bị coi là bị lỗi,tại sao?
3. Nếu gửi đi từ mã c4 = 10101111, nhận được xâu x = 10100011. Có thể phát
hiện lỗi và sửa lỗi khơng?
Giải:
1. Tính khoảng cách Hamming cực tiểu giữa các từ mã, ta có d (c) = 5. Vậy mã
có thể phát hiện tối đa 5 -1 = 4 lỗi trong một từ mã. Số lỗi tối đa có thể sửa được là
=2

2

2. Xâu x1 nhận được từ C, với 4 lỗi (ở bit 1, bit 2, bit 4 và bit 5), mã C phát hiện
được x1 có lỗi và yêu cầu gửi lại. Với xâu x , mắc 5 lỗi, do đó khơng phát hiện được
2



15
lỗi, người nhận cho rằng đã gửi đi từ mã c . Với xâu nhận được x , chỉ mắc 3 lỗi nên
2

3

phát hiện được đây là từ mã bị lỗi,và yêu cầu gửi lại.
3. Do số lỗi là 2, nên có thể sửa được, dùng phương pháp giải mã Nearest
Neighbor, có thể giải mã được D (x) = c4, chính là từ mã gửi đi.
b) Các mã phát hiện lỗi
Mã chẵn lẻ (Paritycode)
Giả sử thông điệp nguồn là các xâu gồm k bit. Mã chẵn lẻ thêm vào thông
điệp nguồn một bit thứ k +1, gọi là bit kiểm tra (parity check bit) theo cách sau:
- Nếu thông điệp là xâu có chứa một số chẵn các bit ‘1’ ta thêm ‘0’ vào
cuối xâu.
- Nếu thông điệp là xâu có chứa một số lẻ các bit ‘1’ ta thêm ‘ 1 ’ vào cuối
xâu.
Tổng qt, ta mã hóa thơng điệp x =

x

k

x1 x2...xk

thành x =

x1 x2...xkxk+1

, trong đó:


x

k+1

=( 1
x

+ x2 +

...

+

) mod2
Mã mới nhận được là một mã (k +1, M, k), trong đó k là độ dài tin nguồn,

M là số tin nguồn, k +1 là độ dài từ mã của mã.
Nhận xét:
Việc thêm bit kiểm tra để đảm bảo số các bit 1 trong mỗi từ mã (xâu mở
rộng) phải là một số chẵn (khi đó ta nói từ mã này là hợp lệ). Như vậy, khi bit kiểm
tra được thêm vào một xâu các bit, nếu có một lỗi duy nhất trong việc truyền tin
đi từ một từ mã thì tổng số các bit 1 trong từ mã đó sẽ là một số lẻ. Do đó, có thể
phát hiện được lỗi này. Tuy nhiên, nếu có 2 lỗi sảy ra thì những lỗi này khơng thể
phát hiện được vì tổng các bit 1 trong xâu mở rộng vẫn sẽ là một số chẵn. Nói
chung, một số lẻ bất kỳ các lỗi có thể được phát hiện, trong khi một số chẵn các
lỗi không thể được phát hiện. Máy thu kiểm tra bit của thông điệp thu được và nếu
nó phát hiện ra một sự bất đồng, nó sẽ u cầu máy phát truyền tin lại thơng điệp.
Mã sánh hợp
Một cách đơn giản khác để phát hiện lỗi là lặp lại mỗi bit trong thông điệp



16
2 lần, khi đó chúng ta có thể phá thiện các lỗi trong một từ mã theo cách sau:
Vì các từ mã của các xâu bit này chứa các cặp bit sánh hợp (giống nhau),
như vậy, ta có thể phát hiện các lỗi làm thay đổi không quá một bit ở mỗi cặp bit
sánh hợp này.
c) Các mã sửa lỗi
Sự dư thừa trong các từ mã, như khi bit kiểm tra được thêm vào một xâu
các bit, ta có thể phát hiện được những lỗi truyền tin. Thậm chí có thể làm tốt hơn
nếu đưa vào nhiều dư thừa hơn. Ta khơng chỉ có thể phát hiện sai mà cịn có thể
sửa sai. Chính xác hơn, nếu số lỗi xảy ra trong một từ mã được truyền là đủ nhỏ,
chúng ta có thể xác định được chính xác từ mã nào đã được truyền đi
Mã lặp lại (repetition codes)
Mã hóa một thông điệp nhị phân x =

x1 x2

...x ...x bằng cách lặp lại xâu bit cần
i

k

truyền m lần, tứclà:
E

() =
x

x


.. x.. . k1

11 x21

x

x

12x22

.. x2 ..

x

k2

.. . 1m 2m .. . im .. . km
x

x

X

X

Trong đó, xộ. là bit thứ i của thông điệp được lặp lại lần thứ j trong từ mã

(i = 1,2,..., k; j = 1,2,..., m)
Dùng quy tắc lấy đa số đơn giản, bằng cách so sánh các bit có cùng chỉ số i

với nhau 1 < i < k, nếu số lương các bit xộ. bằng 0 lớn hơn số lương các x.. bằng 1
thì ta có thể kết luận xi = 0 khi giải mã, trái lại kết luận x{ = 1. Trong trường hợp
hai số lương này bằng nhau thì ta chưa thể kết luân về xi, tuy nhiên có thể lấy số
lần lặp lại m là một số lẻ để tránh tình huống này.
Mã được tạo ra theo phương pháp tạo mã như trên gọi là mã lăp lại
(Repetition codes).
Mã lăp lại có nhươc điểm là đơ dài của từ mã trong mã lăp lại sẽ rất
lớn nếu k và m lớn.
Nhận xét
1. Việc mã hóa bằng các mã lặp lại có nhược điểm là độ dài từ mã sẽ rất lớn nếu
k và

m lớn,và như vậy sẽ làm giảm tốc độ tuyền tin. Tuy nhiên, việc này lại làm


17
tăng độ tin cậy,do các mã lặp lại có khả năng phát hiện lỗi và sửa lỗi rất tốt. Trong
nhiều trường hợp sự tin cậy cần hơn tốc độ.
2. Việc sử dụng các mã chống nhiễu (mã phát hiện lỗi và mã sửa lỗi) làm tăng
khoảng cách Hamming cực tiểu của các mã, từ đó làm tăng khả năng phát hiện lỗi
và sửa lỗi.
2.1.1.3 Phát hiện lỗi và sửa lỗi cho các mã tuyến tính
a) Giải mã cho các mã tuyến tính bằng tập giải mã coset
Vấn đề giải mã và vector lỗi
Giả sử từ mã c = c1c2...cn được gửi đi trên một kênh có nhiễu, xâu nhận
được là x = x x2...x .
1

n


Xâu e = e1e2...e được gọi là vector lỗi (error vector) nếu e
n

= x — c (*) Nếu

xác định được vector lỗi e, thì từ xâu x ta sẽ xác định được từ mã nào đã được gửi
đi, vì từ (*) ta có: c = x — e.
Bộ giải mã cần phải quyết định rằng với xâu nhận được x thì từ mã nào đã
được gửi đi, hoặc là xác định được vector lỗi e đã xuất hiện trong quá trình truyền
tin, từ mã là giải mã của x ký hiệu là c
Có nhiều cách để xác định

cx

x

, chẳng hạn phương pháp giải mã Nearest

Neighbor. Một phương pháp hiệu quả hơn cho các mã tuyến tính là phương pháp
dùng các tập giải mã (coset).
Định nghĩa 1.5 Tập giải mã coset
Cho mã tuyến tính C

[ n, k ] trên trường GF (q) và một vector tùy ý a G

F"
, khi đó tập giải mã của C (coset của C) được ký hiệu và xác định như sau: a + C

= {a + c | Vc G C}
Từ định nghĩa trên, ta thấy mã C có thể có nhiều coset, mỗi vector a

xác định một tập coset của C , tuy nhiên một số tập có thể trùng nhau.
Định lý 1.2

đều


18
Cho mã tuyến tính C

[ n, k ] trên trường GF (q), khi đó:

(i) Mọi vector tùy ý a € F” thuộc về một coset nào đó của C.
(ii) Mọi coset của C đều chứa đúng qk vector.
(iii) Hai coset bất kỳ của C hoặc trùng nhau hoặc rời nhau.
Ví dụ 1.3
Cho C là mã nhị phân tuyến tính [4,2] có ma trận sinh:
1 1
01
Dễ thấy C =

{0000,1011,0101,1110}, ở đây q — 2, k = 2, n = 4, theo định lý

trên, mọi coset của C đều có đúng qk — 22 — 4 vector. Mặt khác, F4 có tất cả 24 =

16 vector nhị phân độ dài 4, các vector này phải xắp xếp trong các coset khác nhau
của C. Vì vậy, ta chọn 4 vector có trọng số nhỏ nhất trong F 4 để tạo nên 4 coset
của C .
Coset 1: 0000 + C = {0000,1011,0101,1110} (bằng chính C, do 0000 € C)
Coset 2: 1000 + C = {1000,0011,1101,0110}
Coset 3: 0100 + C = {0100,1111,0001,1010}

Coset 4: 0010 + C = {0010,1001,0111,1100}
Chú ý rằng nếu chọn a = 0001 thì
coset 0001 + C = {0100,1111,0001,1010} = cos et 0100+C bởi vì

[ ]

0001 € 0100 + C (coset 3). Do đó để tìm tất cả các coset của mã C 4,2 ta chỉ cần

chọn 4 vector có trọng số nhỏ nhất với vị trí bit ‘1’ tăng theo thứ tự từ trái qua
phải. Vector có trọng số nhỏ nhất trong mỗi coset của mã tuyến C

[ n, k ] gọi là

coset leader của coset đó.
Nếu một coset có nhiều vector có cùng trọng số nhỏ nhất, ta có thể chọn ngẫu


19
nhiên một vector như vậy làm coset leader. Chẳng hạn trong ví dụ trên, các coset
leader của các coset lần lượt là: 0000, 1000, 0100, 0010. Với coset 0100 + C (coset
3),ta cũng có thể chọn vector 0001 làm coset leader thay cho 0100.
b) Phát hiện lỗi bằng ma trận kiểm tra
Liên hệ giữa ma trận sinh và ma trận kiểm tra
Cho C

[ n, k ] là mã nhị phân tuyến tính, khi đó:

•

Mã đối ngẫu của C là:


•

Gọi G là ma trận sinh của C , G có cấp k X n

•

Gọi H là ma trận sinh của mã đối ngầu C , H

•

Ma trận H gọi là ma trận kiểm tra của mã C, (tương tự, ma trận G là ma trận
kiểm tra của mã C ). Người ta cũng gọi H là ma trận kiểm tra liên kết với ma

x

có cấp (n - k )X n

x

trận G.
Phát hiện lỗi bằng ma trận kiểm tra
Cho H là ma trận kiểm tra của mã nhị phân tuyến tính C

[ n, k ]. Một xâu

bit x độ dài n là một từ mã của C khi và chỉ khi: x.HT = O
Trong đó: HT là ma trận chuyển vị H, O là ma trận khơng ( gồm tồn số khơng)
Chứng minh:
•


Điều kiện cần: Giả sử x = (xx...x„) là một từ mã trong C. Do đó x phải trực
giao với mọi hàng của ma trận H, hay trực giao với mọi cột của ma trận H.
Từ đó ta có x.HT = O.

•

Điều kiện đủ: Giả sử x thỏa mãn x.HT = O, điều này chứng tỏ x trực giao
với tất cả các cột của ma trận

HT,

hay x trực giao với các hàng của H, theo

kết quả của đại số tuyến tính, x thuộc khơng gian con trực giao với khơng
gian con sinh bởi H. Do H là ma trận sinh của mã đối ngẫu

c) Sửa lỗi bằng ma trận kiểm tra

C

x

nên suy ra x