Tóm tắt luận án Tiến sỹ Kỹ thuật H nội 2007 Luận án đợc hoàn thành tại
Học viện Kỹ thuật Quân sự. Bộ Quốc Phòng
Ngời hớng dẫn khoa học:
1. GS. TS Nguyễn Bình
2. TS. Nguyễn Đức Thắng
Phản biện 1: PGS. TS Lê Mỹ Tú

Phản biện 2: PGS.TS Nguyễn Quốc Trung

Phản biện 3: PGS.TS Phan Hữu Huân


AIC
Conference (Ha Noi), (WG1, Distribution only)
5. Bùi Việt Hồng, Bạch Nhật Hồng, Nguyễn Thế Hiếu, Phạm
Việt Trung (2005), "Xây dựng thuật toán chơng trình an toàn
thông tin, áp dụng cho mô hình an toàn th điện tử", Tạp chí
nghiên cứu KHKT và công nghệ quân sự, số 12, pp 49 - 52
6. Th.S Phạm Việt Trung (2005), Xây dựng hệ mật McEliece
trên mã xyclic cục bộ, Tạp chí nghiên cứu KHKT và công
nghệ quân sự, số 13, pp 63 - 69. 1
A. Mở đầu

Tính cấp thiết: ngày nay với sự phát triển mạnh mẽ của công nghệ
thông tin và truyền thông, mạng máy tính đang trở thành một phơng
tiện điều hành thiết yếu trong mọi lĩnh vực hoạt động của toàn xã hội do
vậy an toàn thông tin truyền trên mạng đóng một vai trò rất quan trọng.
Trong những thập kỷ 70 và 80 của thế kỷ trớc công nghệ mã hoá
thông tin đã có bớc phát triển vợt bậc [27] [36] [45], các hội nghị khoa
học thờng niên của hiệp hội quốc tế về nghiên cứu công nghệ mã đợc
tổ chức liên tục, các hội nghị Euro Crypt tại châu âu, Crypto tại Mỹ thu
hút đợc sự quan tâm của các chuyên gia công nghệ hàng đầu trên thế
giới. Các công nghệ mã hoá hiện đại đều không dựa vào khả năng giữ bí
mật về công nghệ mã hoá ( thuật toán là công khai), mà chỉ dựa vào bí
mật chìa khoá giải mã, một hệ mã nh vậy đợc gọi là hệ mật khoá công
khai. Một hệ mật nh vậy đáp ứng đợc đầy đủ đòi hỏi của các chuyên

trên mã XCB.
- Kết quả nghiên cứu của luận án sẽ góp phần phát triển lý thuyết
mã XCB nói riêng và mã sửa sai nói chung. Đa ra một kết quả
mới trong việc xây dựng hệ mật khoá công khai dựa trên lý thuyết
mã đại số.
Bố cục của luận án
Luận án gồm: 104 trang, có 13 bảng số liệu, 13 hình vẽ, 83 tài liệu
tham khảo. Nội dung của luận án đợc chia làm 3 chơng, kết luận, tài
liệu tham khảo, phụ lục và đĩa chơng trình:
Chơng 1. Tổng quan về hệ mật khoá công khai
Chơng 2. Lý thuyết về mã XCB và phân hoạch vành theo các phần tử
liên hợp.
Chơng 3.Xây dựng hệ mật McEliece trên mã XCB
Kết luận. Kết luận về kết quả nghiên cứu đã đạt đợc, những kết quả
nghiên cứu mới của luận án và kiến nghị về hớng phát triển
tiếp theo.
Phụ lục. Phụ lục A: Chơng trình nguồn của thuật toán phân hoạch vành
dựa trên nhóm nhân xyclic đơn vị (kèm theo 01 đĩa
CD chơng trình).
Phụ lục B: Chơng trình nguồn xây dựng hệ mật McEliece trên
mã XCB: chơng trình mã hoá, chơng trình giải
mã, chơng trình tạo khoá (kèm theo 01 đĩa CD
chơng trình).

B. Nội dung nghiên cứu của luận án
Chơng 1. Tổng quan về hệ mật khoá công khai
Nghiên cứu tổng quan về hệ mật khoá công khai: Khái quát chung về hệ
mật mã cổ điển, trên cơ sở đó phân tích các u nhợc điểm của hệ mật
mã cổ điển và sự ra đời của hệ mật khoá công khai. Nghiên cứu tổng
quan về hệ mật khoá công khai phân tích quá trình phát triển của hệ mật

n = 2
m
, d = 2t+1 và k = n - mt. Cho s là một ma trận khả
nghịch cấp
k x k trên Z
2
. Giả sử P là một ma trận hoán vị cấp n x n, ta đặt
G = SGP. Cho P = (Z
2
)
2
, C = (Z
2
)
n
và ký hiệu: K = {(G, S, P,
G)}
Trong đó G, S, P đợc xây dựng nh mô tả ở trên và đợc giữ
kín, còn G đợc công khai. Với K = (G, S, P, G), ta định
nghĩa:
e
k
(x, e) = x.G + e.
ở đây, e

(Z
2
)
n
là một vector ngẫu nhiên có trọng số t.

2
)
k
sao cho x
0
G=x
1

4. Tính x = x
0
S
-1

- Đánh giá chung: McEliece đã đa ra hệ mật mã khoá công khai đầu
tiên dựa trên lý thuyết mã hoá đại số vào năm 1978. ý tởng đằng sau
của hệ mật mã khoá công khai này dựa trên một thực tế là vấn đề giải mã
của một mã tuyến tính bất kỳ là một vấn đề rất khó khăn. Trong quá khứ,
rất nhiều nhà nghiên cứu đã rất cố gắng để phá vỡ lợc đồ McEliece
nhng không ai trong số họ thành công, một số ngời quả quyết rằng họ
đã phá đợc lợc đồ McEliece, tuy nhiên, hầu hết các nhà mật mã đều
không tin vào kết quả của họ bởi vì có quá ít các bằng chứng rõ ràng để

4
chứng thực giới hạn thời gian họ đã đạt đợc. Theo đánh giá của
McEliece, một mã sửa sai có khả năng tạo ra nhiều lớp mã khác nhau có
thể đợc ứng dụng vào để xây dựng hệ mật.
Ưu nhợc điểm của hệ mật McEliece dùng mã Goppa:
- Dung lợng khoá lớn
- Mã hóa và giải mã khá phức tạp
- Cha có thuật toán tìm mã hữu hiệu.

2.1.2 Phân hoạch của vành theo các nhóm nhân Xyclic
Trong vành R
n
, trớc tiên xác định nhóm nhân xyclic A, số phần tử
nhóm nhân nhiều nhất là max ord a(x) và các đa thức.
* Các bớc thực hiện:

5
1. Chọn a(x) thuộc vành R
n
.
2. Xây dựng nhóm nhân Xyclic A = {a
i
(x)}
3. Xây dựng các lớp kề của A. Về thực chất là xây dựng cấp số nhân
Xyclic có công bội a(x) có phần tử sinh b(x) R
n
, b(x) không thuộc
A và không thuộc bất cứ cấp số nhân nào chúng ta thiết lập.

Hình 2.1. Xây dựng các lớp kề của A
Ví dụ: xét vành R
5
; I = {x
i
, i = 0 ữ 4}. Phân hoạch vành thành các
phần tử:


Trong mọi phân hoạch bất kỳ luôn tồn tại nhóm nhân cấp 1 tầm thờng.
Nh vậy chọn hạt nhân khác nhau sẽ cho các phân hoạch khác nhau.Nếu
a(x) = 1 + x
2
+ x
3
{0 2 3}. Ta có phân hoạch vành:

A

b(x) R
n6
023 014 0
1 134 012
123 2 024
4 124 034
234 3 013
14 23 1234
0234 02 34
04 0134 13
0123 03 12
01 0124 24
01234

x
x
a
a

==


IJ = S = {0,1,2,,n-1}
IJ =
2.1.3 Định nghĩa m XCB
Định nghĩa 2.2
Mã XCB là một mã tuyến tính mà từ mã bao gồm các dấu mã là một tập
con không trống tuỳ ý các lớp kề trong phân hoạch của vành đa thức
theo một nhóm nhân Xyclic nào đó.
Mã XCB đợc lựa chọn là mã hệ thống nếu các lớp kề đợc chọn chứa
các phần tử trong nhóm nhân Xyclic đơn vị ngợc lại mã XCB là một mã
tuyến tính không hệ thống.
2.1.4. M XCB xây dựng trên các nhóm nhân Xyclic
Trờn Z
2
[x]/(x
k
+ 1) xột nhúm nhõn Xyclic sau: A = {a
i
(x)} i = 1, 2,
Gi s ord a(x) = n. Mi nhúm nhõn Xyclic s to nờn mt mó Xyclic

phần tử liên hợp.
2.2 Phân hoạch vành đa thức theo nhóm nhân xyclic đơn vị
2.2.1 Phân hoạch vành đa thức theo nhóm nhân xyclic đơn vị
Ta ký hiệu vành đa thức Z
2
[x] / [x
k
+1] có nhóm nhân xyclic đơn vị đợc
biểu diễn: [I] = {x
0
, x
1
, , x
k-1
}. Hạt nhân phân hoạch của nhóm nhân
xyclic đơn vị chính là x Vấn đề cơ bản là phải xây dựng thuật toán xác
định chính xác các lớp kề cần có và các phần tử trong các lớp kề. Thực
chất vành đa thức bao gồm nhóm nhân xyclic đơn vị và các lớp kề đợc
tạo từ nhóm nhân xyclic đơn vị [I]. Việc xây dựng các lớp kề đợc thực
hiện nh sau:
Bớc 1. Chọn A(x) không thuộc nhóm nhân [I], là tổ hợp của các đơn
thức trong nhóm nhân [I], A(x) chính là trởng lớp kề. Tiếp theo lần lợt
xây dựng các phần tử trong lớp kề này bằng cách nhân với hạt nhân phân
hoạch.
Bớc 2. Tiếp tục thực hiện bớc 1 cho đến khi quét hết các lớp kề có thể
có của vành đa thức. Phân hoạch này có số phần tử của vành là (2
n
-1) đa
thức khác 0. Trong các nghiên cứu trớc đây đều phân hoạch vành với k
nhỏ, tuy nhiên để phân hoạch đợc vành với các k lớn cần phải hoàn

8 k=23 44 giờ 25 phút 250 Mbyte
Qua quá trình thử nghiệm chơng trình chạy rất ổn định và không có lỗi
phát sinh. Vì vậy đây có thể là một kết quả của luận án nghiên cứu sinh.
Toàn bộ chơng trình nguồn và các file dữ liệu cùng với bộ cài đặt đợc
ghi trong một đĩa CD kèm với phụ lục 1.
2.3. Phân hoạch hỗn hợp
Xét một vành đa thức Z
2
[x]/ x
k
+ 1, giả sử D
1
và D
2
là hai phân hoạch
không suy biến của vành tơng ứng với hai hạt nhân phân hoạch là
q
1
(x)
và
q
2
(x). Khi ta kết hợp toàn bộ các phần tử lẻ của D
1
với toàn bộ các
phần tử chẵn của
D
2
(hoặc ngợc lại) ta đợc kiểu phân hoạch hỗn hợp
mới, và kiểu phân hoạch này cũng là kiểu không suy biến vì nó chứa tất

suy biến của vành).
Bớc 2: Phân hoạch vành theo hai hạt nhân trong đó phải có ít nhất một
hạt nhân có trọng số lẻ. Chọn một hạt nhân phân hoạch q
1
(x) sao cho
q
1
(x) = k, một hạt nhân phân hoạch thứ hai q
2
(x) với ord q
2
(x) là bội số
của n. Một hạt nhân có trọng số lẻ đợc dùng để phân hoạch các phần tử
có trọng số lẻ của vành, hạt nhân còn lại đợc dùng để phân hoạch các
phần tử có trọng số chẵn của vành.
Bớc 3: Kết hợp các CGP của hai phân hoạch với nhau để đợc một
phân hoạch mới.

9
2.4. Mã xyclic và xyclic cục bộ xây dựng trên các vành đa thức có độ
dài chẵn
Xét phân hoạch vành đa thức theo lớp các phần tử liên hợp. Với n lẻ ta
xét vành
Z
2
[x]/x
2k
+1, ta ký hiệu là Z
2k
. Ta có các khái niệm sau.

phần tử là các QR.
Định lý 2.2. Các căn bậc hai của một thặng d bậc hai với f(x)

Q
2n

đợc xác định:
Sqr[f(x)] = g(x) = (1 + x
n
)(
t
x
tU


) + ()
f
x (2.2)
()
f
x đợc gọi là căn bậc hai chính (các phần tử có số mũ chẵn).
Tập hợp U là tổ hợp tuỳ ý các giá trị trong tập hợp S bao gồm các giá trị
0, 1, 2, , k-1
S = {0, 1, 2, , k-1}

U bao gồm 2
k
phần tử kể cả tập trống.
Ví dụ2.1: Xét Z
6
x
1 + x + x
3

x
4

1 + x
2
+ x
51 + x
3
+ x
4

1 + x + x
2
+ x
3
+ x
5


4
)

Sqr= (1+x
4
)
Sqr = (x
4
)
Sqr = (x
2
) Sqr = (0)
Sqr =
(
x
2
+x
4
)

Nhận xét:
- Ta có 8 căn bậc hai của x
2
. Bằng phơng pháp tơng tự tính đợc
các 8 căn bậc hai của các QR còn lại. Số căn bậc 2 của thặng d
bậc 2 là 2
k
.
2.4.2. Phân hoạch vành
Z
Hình 2.2. Các thặng d bậc 2 trong vành Z
6

Tập tất cả căn bậc hai của các phần tử trong Q
6
xem bảng 2.5
Bảng 2.5. Lớp các phần tử liên hợp trên Z
6S
r
(x
2
) S
r
(x
4
)

S
r
(1) S
r
(1+x


11

2.4.3. Đặc tính của các phần tử liên hợp (Đặc tính các căn bậc hai của
các thặng d bậc hai)
2.4.3.1. Tính chất chung
Bổ đề 1:
a. Nếu a(x) là một căn bậc hai của f(x) thì
()ax cũng là một căn bậc
hai của f(x).
b. Tổng của hai phần tử liên hợp là một căn bậc hai của zero (0)
c. Tổng của 3 phần tử liên hợp là một phần tử liên hợp
Chứng minh:
Bổ đề 1.a. Giả sử a(x) là một căn bậc 2 của f(x): f(x) = [a(x)]
2
. Xét
b(x) là đa thức đối xứng của a(x). Ta có
21
0
() ()
n
i
i
bx ax x

=
=+

(2.3)
Bình phơng hai vế của (2.3), áp dụng nhị thức Newton ta có

= f(x) (đpcm)

Nh vậy b(x) cũng là một căn bậc 2 của f(x).
2.4.3.2. Tính chất các căn bậc 2 của các luỹ dẳng
Bổ đề 2: (Nghiên cứu đặc tính căn bậc hai của các luỹ đẳng)
Các căn bậc hai của một luỹ đẳng trong Z
2n
là một nhóm nhân có phần
tử đơn vị là e
i
(x
2
).
Chứng minh: Xét hai phần tử liên hợp a(x) và b(x) ta có;
C(x) = a(x).b(x)
C
2
(x) = a
2
(x).b
2
(x) = e
i
(x
2
).e
i
(x
2
) = e

(x
2
) cũng đợc gọi là luỹ đẳng
nuốt.Trong Z
n
ta có x.e
0
(x) = e
0
(x). Trong Z
2n
ta có x
2
.e
0
(x) = e
0
(x
2
)
Bổ đề 3: (Nghiên cứu luỹ đẳng đặc biệt, luỹ đẳng nuốt)
Dịch vòng của một căn bậc hai của e
0
(x
2
) là một căn bậc hai của e
0
(x
2
)

2.5.1. M XCB xây dựng trên phân hoạch chuẩn (sử dụng nhóm nhân
Xyclic đơn vị).
Các lớp kề đều chứa phần tử liên hợp có độ dài tối đa là 2
k
. Mọi phần tử
lớp kề đều nằm trong căn bậc hai.
Bổ đề 5: Mỗi cấp số nhân Xyclic với công bội x trong các phần tử liên
hợp của e
0
(x
2
) là một lớp kề tự đối xứng.
Chứng minh: Giả sử a(x) là một căn bậc hai của e
0
(x
2
) thì a(x) phải có
dạng:
1
0
() (1 )( )
k
ii
k
iu i
ax x
x
x



i
iV
ax
x

=

) + (
in
iU
x
+


)
Trong đó: UV = S UV =
Thực hiện dịch vòng a(x) k cấp:
().
ik
k
iV
ax x
x
+

=


i
iV

Tổng hai phần tử này là hai phần tử đối xứng, a(x) là một căn bậc hai thì
a(x).x
k
là căn bậc hai.
Bổ đề 6: Các phần tử liên hợp với luỹ đẳng nuốt là các đa thức có cùng
trọng số n.
Nhận xét:
a. Không phải mọi đa thức có trọng số n đều là các phần tử liên hợp
với luỹ đẳng nuốt.
b. Tập các đa thức có trọng số n > 2
k
(tập các phần tử liên hợp của luỹ
đẳng nuốt e
0
(x
2
)).
Ví dụ: với k= 5: trong Z
10
có 32 phần tử liên hợp của:
e
0
(x
2
) = 1 + x
2
+ x
4
+ x
6

k
+1 có thể thiết lập đợc
trong tập 2
k
phần tử với luỹ đẳng nuốt bằng 2
k-1
.
Chứng minh: Giả sử a(x) là một phần tử liên hợp của luỹ đẳng e
0
(x
2
),
chúng ta có: a(x) = (1 + x
k
)(
i
iU
x


) + e
0
(x)
e
0
(x) là căn bậc hai chính của e
0
(x
2
)

n-1
).
Đây là mã tối u thoả mãn giới hạn Grismer.[14]
2.5.2. M xyclic cục bộ xây dựng trên phân hoạch cực đại
Xét vành Z
2
[x]/(x
k
+1). Biết tồn tại đa thức a(x) sao cho lấy a(x) bằng giá
trị lớn nhất của đa thức f(x) trong đó f(x) là đa thức bất kỳ trong vành.
Tồn tại a(x) ord(a(x)) = max ord(f(x)), f(x) Z
2
[x]/(x
k
+1). Chọn a(x) là
phần tử sinh đa thức f(x)
2.5.3. M xyclic trên các phần tử liên hợp với 0
Giả sử a(x) là một căn bậc hai của 0.
Ta có: a(x) = (1 + x
k
)(
{0}
t
tT
x
+

); T S
n
= {0,1,2,,k-1}. Vì hai tính chất

+ Mã XCB(n,k) đợc xây dựng từ các lớp kề có cùng trọng số, và có
trọng số lẻ làm dấu kiểm tra là mã XCB có khả năng trực giao.
+ Số lợng khóa tồn tại trong lớp mã phải đủ lớn.
3.1.2 Mô hình toán học xây dựng hệ mật McEliece với m XCB
3.1.2.1 Tạo khoá
Mỗi đối tợng trong hệ thống trao đổi thông tin cần tạo ra một khoá
công khai và một khoá bí mật, khoá công khai là
'
i
G
, khoá bí mật là S
i
,
G
i
, P
i
Khóa bí mật
+ G là ma trận sinh của một mã XCB [n,k,d] có khả năng sửa sai t lỗi
theo phơng pháp giải mã ngỡng, có số lợng phân phối khóa đủ
lớn.
+ S là ma trận khả nghịch [k x k] trên Z
2
.
+ P là ma trận hoán vị [n x n] trên Z
2
.
Khóa công khai:
G = S.G.P
3.1.2.2 Mã hoá và giải mã

- Tính
x
0
(Z
2
)
k
sao cho x
0
.G=x
1

-

Tính x = x
0
.S
-1
3.2 Sơ đồ khối xây dựng hệ mật McEliece với mã XCB
3.2.1 Sơ đồ m hoá
Theo đề xuất của nghiên cứu sinh bộ mã đợc lựa chọn là (512,49,64)
đây là bộ mã đợc xây dựng từ mã XCB(64,7,32) và mã (8,7,2).
Trong lợc đồ mã hoá này ta sử dụng mã XCB (64,7) để xây dựng ma
trận sinh G. Ma trận này đợc rút gọn từ mã XCB (64,8). Ma trận S là
ma trận khả nghịch [7x7], ma trận đơn vị P là ma trận hoán vị cấp [64 x
64]. Khoá công khai G' = S.G.P là ma trận [ 7x 64]. Bản rõ m đợc
tách ra thành từng đoạn dữ liệu 49 bit và đoạn dữ liệu có chứa tối đa 31
bit 1 và có độ dài tối đa 512 bit. Đoạn dữ liệu 49 bit đợc sắp xếp thành
ma trận [7x7], và đợc mã hoá bằng khoá công khai G' tạo ra ma trận [8
x 64] với hàng thứ 8 bằng tổng các cột từ 1 đến 7. Từ ma trận này đợc

Qua thuật giải mã XCB dựa trên phơng pháp giải mã ngỡng theo đa
số, ta thu đợc dữ liệu 49 bít mã hoá là ma trận M
3
.
Sau khi nhân M
3
với ma trận S
-1
[7x7] ta thu đợc m: m = M
3
.S
-1
ta sẽ thu
đợc 49 bít dữ liệu của bản rõ.
Để giải mã vectơ sai e có chứa tốiđa 31 bít 1 đợc cộng thêm, ta lại tiếp
tục thực hiện mã hoá lại 49 bít đó theo phần 3.2.1 ta sẽ thu đợc 512 bít
mã hoá. Sử dụng 512 bít này cộng module 2 với 512 bít đã mã hoá ban
đầu ta thu đợc vectơ e có chứa 31 bít 1 của bản rõ đã cộng thêm trong
quá trình mã hoá. Sơ đồ giải mã đợc trình bày trên hình 3.2.

16

hệ mật mã hoá khoá công khai McEliece với mã XCB. 7
1
(,8) (, )
j
iij
=
=


File mó húa
Hỡnh 3.1. S khi mó hoỏ ca h mt McEliece vi mó XCB
+
Ma trn
[8x64]

Ma trn
[1x512]
Ma trn sinh G
[7 x 64]
Ma trn
[7x7]
Vộc t sai [1x n] cú
cha ti a 31 bớt 1
v n 512

File gc
File gc

7x7
]
Thc hin mó húa theo
s hỡnh 3.1
Ma trn [1x n] cú
cha ti a 31 bớt 1
v n 512
Ma trn
[1x512]

17
3.3 Về một phơng pháp xây dựng hệ mật McEliece trên mã Xyclic
cục bộ
3.3.1 Phơng pháp tạo khoá m:
Hệ mật McEliece trên mã Xyclic cục bộ sử dụng ma trận sinh G dựa trên
phân hoạch vành theo nhóm nhân xyclic đơn vị với k = 8, Trên cơ sở đó
ta chỉ lựa chọn các lớp kề có trọng số là 3 để xây dựng bộ mã (64,8,32).
Bảng 3.1. Các lớp kề lựa chọn để xây dựng bộ mã (64,8,32)
(0) (1) (2) (3) (4) (5) (6) (7) a
0
012 123 234 345 456 567 670 017 b
0

023 134 245 356 467 057 016 127 c
0

034 145 256 367 047 015 126 237 d
0

045 156 267 037 014 125 236 347 e

1 0 0 0 0 0 1 1
1 1 0 0 0 0 0 1
1 1 1 0 0 0 0 0
0 1 1 1 0 0 0 0
0 0 1 1 1 0 0 0
0 0 0 1 1 1 0 0
0 0 0 0 1 1 1 0
0 0 0 0 0 1 1 1
1 0 0 0 1 1 0 0
0 1 0 0 0 1 1 0
0 0 1 0 0 0 1 1
1 0 0 1 0 0 0 1
1 1 0 0 1 0 0 0
0 1 1 0 0 1 0 0
0 0 1 1 0 0 1 0
0 0 0 1 1 0 0 1
1 0 0 1 1 0 0 0
0 1 0 0 1 1 0 0
0 0 1 0 0 1 1 0
0 0 0 1 0 0 1 1
1 0 0 0 1 0 0 1
1 1 0 0 0 1 0 0
0 1 1 0 0 0 1 0
0 0 1 1 0 0 0 1
1 0 0 0 0 1 1 0
0 1 0 0 0 0 1 1
1 0 1 0 0 0 0 1
1 1 0 1 0 0 0 0
0 1 1 0 1 0 0 0
0 0 1 1 0 1 0 0
3
8
8.7.6
56
3.2
C
=
=

18
Bảng 3.3. Ma trận sinh G(7,64)
1 0 0 0 0 0 0 1
0 1 0 0 0 0 0 1
0 0 1 0 0 0 0 1
0 0 0 1 0 0 0 1
0 0 0 0 1 0 0 1
0 0 0 0 0 1 0 1
0 0 0 0 0 0 1 1
1 0 0 0 0 1 0 0
1 1 0 0 0 1 1 0
1 1 1 0 0 1 1 1
0 1 1 1 0 1 1 1
0 0 1 1 1 1 1 1
0 0 0 1 1 0 1 1
0 0 0 0 1 0 0 1
1 0 0 1 0 1 0 1
0 1 0 1 1 1 1 1
0 0 1 1 1 0 1 0

0 1 0 0 0 0 0 1
0 0 1 1 1 1 1 1
1 0 1 1 0 1 1 1
0 1 1 0 1 1 0 0
1 0 0 0 0 0 0 1
0 1 1 1 0 1 1 1
0 0 0 0 1 1 0 0
1 0 1 1 0 0 0 1
0 1 1 0 1 1 1 1
Với bảng phân hoạch trên khi dịch vòng các phần tử trên cùng một lớp
kề hoặc hoán vị các lớp kề khác nhau ta xây dựng đợc các ma trận sinh
G khác nhau. Với lớp mã này ta có thể xây dựng đợc 8
8
.8! 676 tỷ
khóa .
Trên cơ sở lợc đồ của hệ mật McEliece ta có khóa công khai G=S.G.P
(S là ma trận khả nghịch cấp 7x7, P là ma trận hoán vị 64x64) do đó
ngoài việc hoán vị các vị trí trên phân hoạch để tạo ra các ma trận sinh G
khác nhau, ta còn có thể thay đổi ma trận S và P để tăng khả năng tạo
khoá cho hệ mật.
3.3.2 Thuật toán m hoá
3.3.2.1. Nguyên tắc chung
Để tăng khả năng tốc độ thông tin ta sử dụng mã XCB (64,7,32) kết hợp
với mã Elias (8,7,2): (512,49,64) = (64,7,32)(8,7,2)
Thông tin đầu vào đợc chia nh sau:
7 bit 7 bit 7 bit 7 bit 7 bit 7 bit 7 bit Có chứa 31 bit 1 và độ dài #512 bit
Khi mã hoá ta sẽ mã hoá mỗi lần 7x7=49 bit chứa thông tin thông qua
khóa công khai G' (7,64)= S.G.P
Trong đó: S là ma trận khả nghịch 7x7
G là ma trận sinh 7x64

KK
MO M MO M
LL
19
3.3.2.2. Thuật toán mã hoá
Sơ đồ thuật toán mã hoá đợc trình bầy trên hình 3.3

ỡnh 3.3.
S
thut toỏn mó hoỏ
Kt thỳc
512 bit ó mó hoỏ
Cng
module 2
K< T
Vec t sai V ly t
bn tin
Sai
ỳng
Chốn thờm du gi
thụng tin
Bt u
c khúa cụng khai G
i

(G
i
= S.G
i
.P)
K=0
c file d liu
c kớch thc file T
Phõn tớch d liu theo bit
- M(49 bit d liu )
- V(vect sai cha ti a 31 bit
1 v di 512 bit)

thu đợc ma trận M
3
-
(7x7)
- Nhân ma trận M
3
với ma trận nghịch đảo của S thu đợc ma trận
M.
M

= M
3
*S
-1
với ma trận M (7x7) là ma trận chứa 49 bit thông tin
mã hoá.
Do sử dụng vectơ sai chứa thông tin lên phải thực hiện thêm một số bớc
sau:
- Mã hoá lại ma trận M(7x7) thu đợc: M(7x7)*G'(7x64) thu đợc
ma trận 8x64 chứa dữ liệu mã hoá cha có vectơ sai (Hàng thứ 8
bằng tổng các hàng phía trên).
- Xắp xếp thành chuỗi 512 bit, sau đó thực hiện cộng module 2 với
512 bit thu đợc ta sẽ thu đợc vectơ sai.
3.3.3.2. Xây dựng các tổng kiểm tra
Do sử dụng mã xyclic cục bộ nên ta sử dụng phơng pháp giải mã
ngỡng cho nên ta phải xây dựng các tổng kiểm tra để giải mã.
Các tổng kiểm tra cấp 1 (Giải mã cho các cặp dấu)
A(0)
a
0

A(6)
a
6
+ a
7

A(7)
a
7
+ a
0
Dựa trên phân hoạch vành theo nhóm nhân xyclic đơn vị với k=8 ta xây
dựng đợc 32 tổng kiểm tra cho cặp dấu A
0
(a
0
+ a
1
). Đối với tính chất
của mã (512,49,64) = (64,7,32) (8,7,2)
Ta thiết lập đợc thêm 32 tổng kiểm tra cho cặp dấu
01
00
+
aa
:
Sau đó xây dựng 64 tổng kiểm tra cho cấp ngỡng thứ 2 thông qua phân
hoạch vành theo nhóm nhân xyclic đơn vị với k=8 và tính chất của mã
(512,49,64) để giải mã cho từng dấu thông tin.
3.3.3.3. Thuật toán giải mã
Vectơ sai có
chứa dữ liệu
Cộng
Module 2
Kết thúc
Sắp xếp về
ma trận M
1
(8,64)
Đọc file mã hóa
Đọc kich thước file T
H
ình 3.4. Sơ đồ thu
ậ
t toán
g

M = M
3
* S
i
-1

Sắp xếp thành 512 bít
Bắt đầu
Đọc P
i
-1
, S
i
-1
Đọc ma trận tổng kiểm tra của G
i
K=0
Phân tích dữ liệu theo bit
M (512 bit dữ liệu mã hóa)
K=K+Leng(M)
49 bit dữ liệu của bản tin
Ghi kết quả
Mã hóa lại dữ liệu với G
i
’ tạo Ma trận (8,64)
22 3.4 Nghiên cứu thử nghiệm hệ mật McEliece trên mã Xyclic cục bộ.
Phần này là ví dụ về xây dựng hệ mật McEliece trên mã Xyclic cục bộ.

Tỷ lệ
bản mã / bản rõ
.pdf 4677 19975 < 1 s 137.56 4.27 (512/117)
.txt 12905 44163 <1s 138.76 3.42 (512/148)
.exe 24576 46746 <1s 261.45 1.9 (512/271)
.doc 30720 48461 <1s 331.4 1.57 (512/322)
Tỷ lệ mã và giải mã có sử dụng nén (Winrar)
Dạn
g

File

Kích
thớc
(byte)
Kích
thớc
sau nén
(byte)
Kích
thớc bản
mã (byte)
Tốc độ
mã hoá
(byte/giây)
Tốc độ
giải mã
(byte/giây)
Tỷ lệ
bản mã / bản