1
BỘ GIÁO DỤC VÀ ĐÀO
TẠO
TẬP ĐOÀN BƯU CHÍNH VI
ỄN THÔNG
VIỆT NAM
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
NGUYỄN TRUNG HIẾU

ỨNG DỤNG FPGA THỰC HIỆN THUẬT TOÁN NHÂN V
À BÌNH
PHƯƠNG TRÊN VÀNH ĐA THỨC

CHUYÊN NGÀNH : KỸ THUẬT ĐIỆN TỬ

MÃ SỐ:23.060.52.704.3898
TÓM TẮT LUẬN VĂN THẠC SỸ KỸ THUẬT

Người hướng dẫn khoa học: TS. NGUYỄN NGỌC MINH

HÀ NỘI - 2010


3

………………………………………………………

4
LỜI NÓI ĐẦU
Nâng cao hiệu quả của hệ thống truyền tin là một yêu cầu thực
tiễn luôn chứa đựng tính cấp thiết, tính đa dạng, lại vừa chứa đựng tính
phát triển không ngừng. Các phương pháp mã hóa, mật mã đã đóng góp
không nhỏ vào việc nâng cao hiệu quả và đảm bảo độ an toan, tin cậy
của các hệ thống truyền tin.
Thuật toán nhân và bình phương đa thức có lặp được ứng dụng và
đóng vai trò quan trọng trong việc xây dựng nhiều bộ mã hóa, mật mã
như: Các bộ mã hóa xyclic, xyclic cục bộ, Mật mã AES, các hệ mật
RSA, Chor-Rivest, Merkele-Hellman, Elgamal, Rabin,
Ngày nay, sự phát triển không ngừng của thiết kế số cho các cấu
kiện logic khả trình theo công nghệ CPLD/FPGA mở ra cho chúng ta
hướng nghiên cứu xây dựng thuật toán nhân và bình phương đa thức có
lặp trên các cấu kiện logic khả trình, từ đó ứng dụng xây dựng các bộ
mã hóa, mật mã trên các cấu kiện FPGA.
Luận văn nghiên cứu ứng dụng của thuật toán cho việc xây dựng
một số bộ mã xyclic và xyclic cục bộ. Mã xyclic cục bộ được
GS.TSKH. Nguyễn Xuân Quỳnh, GS.TS. Nguyễn Bình đưa ra đầu tiên.
Những nghiên cứu từ trước cho thấy những ưu điểm nổi bật của mã
như: Tính đa dạng, tốc độ lập mã nhanh, mạch giải mã đơn giản.
Phương pháp luận của đề tài dựa vào các khái niệm đã có như:
- Lưu đồ thực hiện thuật toán nhân và bình phương đa thức có
lặp cho ngôn ngữ lập trình thông dụng để xây dựng lưu đồ thực
hiện thuật toán trên FPGA.

n
, F
p
m
và
một số ví dụ áp dụng, cuối chương đưa ra các đề xuất ứng dụng thuật
toán và hướng nghiên cứu cho các chương tiếp theo.
1.2. LÝ THUYẾT ĐẠI SỐ
1.2.1. Những vấn đề cơ bản về lý thuyết số
Định lý 1.1:
Với mỗi số nguyên n  2 ta luôn phân tích được dưới dạng tích
lũy thừa các số nguyên tố:
1 2 3
1 2 3
. .
k
e e e e
k
n p p p p

Trong đó: p
i
là các số nguyên tố khác nhau.
e
i
là các số nguyên dương.
Ví dụ 1.1:
2 2
36 2 .3


n

INPUT: a

Z, và số nguyên 0

k < n có biểu diễn nhị phân:
0
2
t
i
i
i
k k



(hay
0 1 2 1
0 1 2 1
.2 .2 .2 .2 .2
t t
t t
k k k k k k


     
)
OUTPUT:
mod

m
k p
  
có biểu diễn:
0
2
t
i
i
i
k k



hay
0 1 2 1
0 1 2 1
.2 .2 .2 .2 .2
t t
t t
k k k k k k


      .
(Trường






= 1 thì gán s(x) = g(x)
B4: for (i = 1; i <= t; i++)
B41: Đặt G(x) =G(x)
2
mod f(x)

7
B42: N
ế
u k
i

= 1 thì
đ
ặ
t
s(x)
=
G(x)*s(x)
mod
f(x)

B5: return (s(x))
Ví dụ 1.15:




22
7 6 4 2 9 3


0

0


7 6 4 2
1
g x x x x x x
     

1
1

1
5 3 2
1
x x x
  

5 3 2
1
x x x
  

2

1
6 2
1


1.4.3. Các ứng dụng của thuật toán trên vành đa thức
Thuật toán có nhiều ứng dụng trong việc tìm kiếm phần dư của
phép chia lũy thừa cho một số, lũy thừa của một đa thức cho một đa
thức, ứng dụng xây dựng các bộ mã hóa, mật mã: mã xyclic; Mật mã
AES, hệ mật RSA, Chor-Rivest, Merkele-Hellman, Elgamal, Rabin,
Nội dung luận văn tập trung tìm hiểu phương pháp thực hiện
thuật toán nhân và bình phương đa thức ở dạng tổng quát trên FPGA, từ
đó xây dựng thuật toán tạo nhóm nhân cho các mã xyclic và xyclic cục
bộ trên vành x
n
+ 1, là thành phần quan trọng cho việc xây dựng các bộ
mã xyclic và xyclic cục bộ ứng dụng cho việc mã hóa dữ liệu.
1.5. KẾT LUẬN
Chương này đã trình bày những kiến thức cơ bản nhất về cơ sở lý
thuyết đại số, vành đa thức và thuật toán nhân và bình phương có lặp
trên Z
n
và F
p
m
. Từ đó tìm hiểu những ứng dụng của thuật toán này.
Trong nội dung nghiên cứu của luận văn sẽ tập trung vào nghiên cứu
ứng dụng FPGA để thực hiện thuật toán áp dụng cho việc xây dựng các
bộ mã xyclic trên vành đa thức phục vụ cho việc mã hóa dữ liệu.

8
CHƯƠNG 2:
CÁC MÃ XYCLIC TRÊN VÀNH ĐA THỨC
2.1. MỞ ĐẦU

GF
, vành đa thức ký hiệu
2
[ ]/ 1
n
x x

Z .
2.2.2. Ideal của vành đa thức
Định nghĩa 2.2: Ideal I của vành đa thức gồm tập các đa thức
( )
a x

là bội của một đa thức
( )
g x
thỏa mãn:

( )| 1
n
g x x

(
( )
g x
là ước của
1
n
x


Mã xyclic là một bộ mã tuyến tính có tính chất sau: Nếu a(x)là
một từ mã thì dịch vòng của a(x) cũng là một từ mã thuộc bộ mã này.
2.2.4. Ma trận sinh và ma trận kiểm tra của mã xyclic
Vì mã xyclic
( , )
n k
là một mã tuyến tính nên có thể mô tả nó
thông qua ma trận sinh G chứa k véc tơ hàng độc lập tuyến tính. Ma
trận G được viết như sau :
1
( )
. ( )

( )
k
g x
x g x
G
x g x

 
 
 

 
 
 
 

Vì

và
( )
h x
được
gọi là các đa thức trực giao.
2.3. PHÂN HOẠCH VÀNH ĐA THỨC VÀ MÃ XYCLIC CỤC BỘ
2.3.1. Nhóm nhân xyclic trên vành đa thức
Định nghĩa 2.7:
Nhóm nhân xyclic (CMG-Cyclic Multiplicate Group) trong vành
đa thức là tập hợp các phần tử đều bằng lũy thừa của một phần tử gọi là
phần tử sinh. Trong vành đa thức có nhiều nhóm nhân xyclic, số nhóm
nhân bằng số các lũy đẳng có thể có trong vành.
2 3
{ , , , }
m
A
    

Trong đó: A là nhóm nhân xyclic; α là phần tử sinh (đa thức
sinh); m là cấp của nhóm nhân, cũng chính là cấp của phần tử sinh

.
Cấp của nhóm là tổng số các phần tử của nhóm.
Phần tử đơn vị của nhóm chính là một lũy đẳng
( )
e x
có cấp bằng 1.

10
Định nghĩa 2.8:

A
.
2.3.4.2. Cách biểu diễn mã XCB
a) Biểu diễn theo trưởng lớp kề
Định nghĩa 2.13: Lớp kề là một tập hợp có tối đa k phần tử mà giá
trị của chúng được xác định từ phần tử trưởng lớp kề theo một biểu
thức toán học (trưởng lớp kề là phần tử đứng đầu tiên trong một lớp
kề). Nếu gọi giá trị của trưởng lớp kề là

0
thì các phần tử khác
trong lớp kề được tính:


0
.2 mod ; 1, 1
i
i
p i k
    

b) Biểu diễn theo ma trận sinh
Đây là cách biểu diễn truyền thống, mã XCB
( , )
n k
là mã hệ
thống tuyến tính nên có thể mô tả theo ma trận sinh


,

Trên cơ sở đã xác định được các nhóm nhân sinh, ta chọn phần
tử đầu tiên nhân với nhóm nhân sinh (lớp kề sinh) sẽ tạo được cấp số
nhân xyclic tương đương với lớp kề mới, phần tử sinh của lớp kề
(trưởng lớp kề) tương ứng số hạng đầu của cấp số nhân xyclic. Nếu ta
gắn dấu thông tin cho nhóm nhân sinh ta sẽ tạo được mã XCB tương
ứng với nhóm nhân đó. Có hai cách chọn nhóm nhân sinh:
+ Cách thứ nhất: Chọn nhóm nhân đơn vị I, các dấu thông tin
được gắn vào nhóm nhân đơn vị I để tạo mã.
+
Cách thứ hai:
Chọn nhóm nhân sinh là nhóm nhân xyclic bất kỳ.
2.3.4.4. Các lớp mã XCB
a) Mã xyclic cục bộ tự trực giao (XCBTTG)
Định nghĩa 2.14:
Mã XCBTTG là bộ mã XCB (n, k) với:
1
; 1
m
i
k
i
n C m k

  


Với k dấu thông tin là k phần tử của nhóm nhân xyclic cấp k.
Các dấu kiểm tra là một tập con không trống nào đó của tất cả các
phần tử trong nhóm kề liên tiếp (từ nhóm kề thứ hai trở đi).
b) Mã XCB có khả năng trực giao (XCBCKNTG)

 
 
.
Mã XCBCKNTG được xây dựng theo nguyên tắc sau:
 k dấu thông tin là k phần tử của nhóm nhân xyclic cấp k.


Các dấu kiểm tra được lấy là các phần tử ở các lớp kề lẻ liên tiếp.

12
lập được
1
2
k

 
 
 
bộ mã
Mỗi giá trị của k có thể
XCBCKNTG.
2.3.5. Phương pháp giải mã ngưỡng
Có nhiều phương pháp giải mã cho mã xyclic và XCB, trong số
đó phương pháp giải mã ngưỡng là một phương pháp khá hiệu quả và
có sơ đồ giải mã đơn giản. Các phương pháp giải mã ngưỡng bao gồm:
 Giải mã ngưỡng theo đa số các tổng kiểm tra (GMĐS)
 Giải mã ngưỡng trên đa số 1 biểu quyết (GMĐS+ 1), giải mã
ngưỡng trên đa số 2 biểu quyết (GMĐS + 2).
Các phương pháp giảm mã ngưỡng đều sử dụng các tổng kiểm tra
(TKT) trực giao, hoặc các tổng kiểm tra có khả năng trực giao.

a x

V
àn
h c
á
c l
ớp

c
á
c
phần tử liên hợp
P
h
â
n ho
ạch
c
ực

tiểu
( ) 1
a x


P
h
â
n ho

cục bộ
Mã xyclic
truyền
thống

Hình 2.1: Các phân hoạch của vành đa thức và các lớp mã tuyến tính

13
2.5. CÁC KẾT QUẢ NGHIÊN
CỨU VỀ MÃ XCB
2.6. KẾT LUẬN
Trong chương này đã nghiên cứu về các mã xyclic và xyclic cục
bộ trên vành đa thức, về các nhóm nhân, các kiểu phân hoạch vành đa
thức, phương pháp mã hóa, giải mã, mối quan hệ giữa mã xyclic và
xyclic cục bộ. Ngoài ra có thống kê các kết quả nghiên cứu về mã
xyclic cục bộ, cũng như tham khảo các hướng nghiên cứu mở.
CHƯƠNG 3: THIẾT KẾ VÀ MÔ PHỎNG TRÊN FPGA
3.1. GIỚI THIỆU
Trong những chương trước đã nghiên cứu về cơ sở lý thuyết số,
vành đa thức, thuật toán nhân và bình phương đa thức có lặp, các mã
xyclic trên vành đa thức. Nội dung chương này là tìm hiểu tổng quan về
công nghệ FPGA, xây dựng các thuật toán nhân và bình phương đa
thức có lặp trên FPGA (dạng tổng quát và trường hợp riêng), làm cơ sở
cho việc tạo ra các nhóm nhân cho các bộ mã hóa xyclic và xyclic cục
bộ. Tiếp đó sẽ nghiên cứu xây dựng các bộ giải mã thực hiện trên
FPGA dựa trên phương pháp giải mã ngưỡng để tạo thành các bộ mã
xyclic hoàn chỉnh (gồm cả mã hóa và giải mã).
3.2. TỔNG QUAN VỀ FPGA
Những ưu điểm của FPGA đối với mã hoá, mật mã: Dễ dàng
chuyển thuật toán; Dễ dàng cập nhật thuật toán; Mang lại hiệu quả về

phân thông thường. Chia giá trị bit từ trọng số cao xuống bit có trọng số
thấp. Chú ý sử dụng một mảng để lưu dữ liệu số bị chia, một mảng để
lưu dữ liệu số chia, sử dụng phép dịch vòng trái để dịch vòng số chia
đến cùng vị trí bit giá trị 1 có trọng số cao nhất rồi tiến hành phép
XOR. Kết quả sau mỗi phép XOR (giữa số bị chia với số chia đã dịch
vòng) được lưu đè trong mảng chứa dữ liệu số bị chia. Phép chia sẽ
dừng lại khi trọng số bit 1 lớn nhất lưu trong mảng chứa số bị chia nhỏ
hơn trọng số bit 1 lớn nhất lưu trong mảng chứa số chia (cụ thể là phép
chia dừng lại sau (n-2) nhịp). Và phần dư chính là giá trị (n-1) bit trọng
số thấp nhất chứa trong mảng số bị chia.
- Lặp đến lũy thừa k: Thuật toán nhân và lấy dư được thực hiện lặp đi
lặp lại đến k lần, đảm bảo thực hiện nhân và mode lũy thừa k.
3.3.2. Thuật toán áp dụng cho f(x) = x
n
+ 1
Chi tiết trình bày trong luận văn.
3.4. XÂY DỰNG BỘ MÃ XCB (15, 5)
Phần này sẽ đi nghiên cứu và thực hiện các công việc xây dựng
một bộ mã hóa XCB (15,5). Muốn xây dựng bộ mã này cần phải làm
hai phần việc như sau: Thứ nhất, là xây dựng bộ mã hóa theo phương
pháp xây dựng mã XCB đã nêu ở chương 2; Thứ hai, đó là xây dựng bộ
giải mã theo phương pháp giải mã ngưỡng.

16
Trong phần này ta xây dựng bộ mã (15,5) cho đa thức sinh
có cấp là 15 (cấp cực đại của vành)





i
A a x


Mã cyclic được xây dựng theo nhóm nhân A sẽ là mã (15,5,7).
Đây là mã hệ thống với ma trận sinh như sau:
1 1 0 1 1 0 0 1 0 1 0 0 0 0 1
0 0 1 1 1 0 1 1 0 0 1 0 1 0 0
1 0 0 0 0 1 1 1 0 1 1 0 0 1 0
0 1 0 1 0 0 0 0 1 1 1 0 1 1 0
1 1 0 0 1 0 1 0 0 0 0 1 1 1 0
G
 
 
 
 

 
 
 
 

Trong ma trận sinh G, ta có thể thấy:
 Cột thứ nhất 1
(10101)
tương ứng với
a(x)=(024)
.
 Cột thứ nhất 2
(10011)


5
mod( 1)
i
G a x x
 
 
 

Ta có sơ đồ thực hiện mã hóa như hình 3.5. Trong đó 5 ô X
0
, X
1
,
X
2
, X
3
, X
4
chứa 5 bit thông tin, sau mỗi nhịp xung đồng hồ sẽ có 1 bit
tại đầu ra. Kết quả là từ 5 bit thông tin ban mã hóa theo xung nhịp
thành 15 bit để phát đi.

17

Hình 3.2: Sơ đồ mã hóa mã (15,5,7) với thức sinh (024)
* Giải mã: Thuật toán giải mã sẽ tuân theo luật giải mã ngưỡng 2 cấp:
 Cấp ngưỡng đầu tiên: hệ TKTTG với cặp dấu thông tin (0)+ (1)
(01) = (0) + (1) = (024) + (124) = (034) + (134)

12
a
13
a
14
a
15
a
12 15
a a

9 12
a a

6 9
a a

3 6
a a

3 15
a a


Hình 3.3: Sơ đồ giải mã cyclic (15, 5) trên


5
2
/( 1)

Mô hình thử nghiệm thuật toán mã hóa và giải mã cyclic cục bộ
trên vành Z
2
[x]/x
5
+1 tức vành Z
5
bằng FPGA như hình 3.7.

Hình 3.4: Sơ đồ mô hình thử nghiệm dưới dạng RTL

19
a) Thiết kế mạch mã hóa
Sơ đồ thiết kế mạch mã hóa như hình 3.8. Thành phần mạch bao
gồm một thanh ghi lưu trữ thông tin cần mã hóa, các cổng AND và
XOR để thực hiện.

Hình 3.5: Sơ đồ mã hóa thông tin theo nhóm nhân xyclic
b) Thiết kế mạch giải mã
Khối DeCoding gồm: 5 nhánh để thực hiện giải mã song song cả
5 bit thông tin Io(0:4). Mỗi nhánh gồm: Mạch đệm dịch vòng trái;
Mạch tính tổng kiểm tra “S”; Mạch giải mã ngưỡng “M”.

Hình 3.6: Sơ đồ RTL của mạch khối DeCoding
Kết quả tổng hợp, cấu hình và mô phỏng sử dụng FPGA
XC3S500E-4CPG132 như ở hình 3.10 và hình 3.11.

20
Sơ đồ mã hóa cho mã XCB này ở hình 3.12.

Hình 3.8: Sơ đồ mã hóa XCB {1, 7, 11}

21
Số nhịp dịch của đa thức thông tin, lớp kề 1 và lớp kề 2 là 9
nhịp; Tổng cộng sau 27 nhịp thì được toàn bộ từ mã.
* Giải mã: Đây là mã XCBCKNTG nên đi xây dựng hệ TKTCKNTG
+ Cấp ngưỡng đầu tiên: Hệ TKTCKNTG cho cặp dấu (01).
(01) = (0) + (1) = (2) + (012)
= (3) + (013) = (8) + (018)
= (078) + (178) = (1) + (5) + (567)
= (124) + (028) + (456) + (568)
+ Cấp ngưỡng thứ 2 với dấu thông tin (0) trong cặp dấu (0)+ (1).
(0) = (01) + (1) = (12) + (012)
= (01) + (12) + (2) = (12) + (23) + (013)
= (01) + (08) + (018) = (78) + (08) + (7)
= (08) + (8) = (67) + (067)
Trong mã này, khoảng cách Hamming sẽ là: d
0
= 7; sửa sai được
3 bit. Sơ đồ giải mã XCB (27, 9) với 3 lớp kề {1, 7, 11} như hình 3.13 Hình 3.13: Sơ đồ bộ giải mã XCB {1, 7, 11}
3.5.2. Thiết kế và mô phỏng trên FPGA
Mô hình thử nghiệm thuật toán mã hóa và giải mã cyclic cục bộ
trên vành Z
2
[x]/x

hóa và giải mã ngưỡng, giúp ta xây dựng được các bộ mã xyclic và
xyclic cục bộ thực hiện trên FPGA với một số ví dụ như đã khảo sát.
KẾT LUẬN VÀ KIẾN NGHỊ
Đề tài “Ứng dụng FPGA thực hiện thuật toán nhân và bình
phương trên vành đa thức” với những nội dung đã thực hiện được
như sau:
 Tìm hiểu về cơ sở lý thuyết số, vành đa thức và thuật toán
nhân và bình phương đa thức có lặp trên Z
n
, F
p
m
với các ví
dụ minh họa cho thuật toán.
 Tìm hiểu các mã xyclic trên vành đa thức, phương pháp
phân hoạch vành theo các nhóm nhân xyclic.
 Tìm hiểu phương pháp mã hóa và giải mã cho các mã
xyclic. Về mặt kỹ thuật việc mã hóa được thực hiện bằng
các bộ cộng modul 2 và bộ nhân đa thức, việc giải mã thì
sử dụng phương pháp giải mã ngưỡng theo đa số chỉ bao
gồm các bộ cộng modul 2 và bộ so sánh ngưỡng.
 Nghiên cứu xây dựng lưu đồ thuật toán cho phép nhân và
bình phương đa thức có lặp trên vành đa thức. Xây dựng
được lưu đồ thuật toán cho đa thức f(x) tổng quát và đa
thức f(x) = x
n
+ 1.
 Xây dựng mạch thực hiện và mô phỏng trên FPGA việc
tạo ra các nhóm nhân xyclic.
 Xây dựng mạch thực hiện và mô phỏng trên FPGA cho các