Luận án Tiến sĩ Toán học: Nghiên cứu một số giải pháp nâng cao hiệu năng của thuật toán mã hóa

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG

VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ -------------------------

NGUYỄN THỊ THU NGA NGHIÊN CỨU MỘT SỐ GIẢI PHÁP NÂNG CAO

HIỆU NĂNG CỦA THUẬT TOÁN MÃ HÓA

LUẬN ÁN TIẾN SĨ TOÁN HỌC

HÀ NỘI - 2022

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG

VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ ------------------------

NGUYỄN THỊ THU NGA NGHIÊN CỨU MỘT SỐ GIẢI PHÁP NÂNG CAO

HIỆU NĂNG CỦA THUẬT TOÁN MÃ HÓA

Ngành: Cơ sở toán học cho tin học Mã số: 9 46 01 10

LUẬN ÁN TIẾN SĨ TOÁN HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC:

1. PGS.TS. LÊ MỸ TÚ 2. TS. NGUYỄN NGỌC CƯƠNG

HÀ NỘI - 2022

LỜI CAM ĐOAN

Tôi xin cam đoan, đây là công trình nghiên cứu của riêng tôi. Những nội

dung, số liệu và kết quả trình bày trong luận án là hoàn toàn trung thực và chưa

có tác giả nào công bố trong bất cứ một công trình nào khác. Các tài liệu tham

khảo được trích dẫn đầy đủ.

Hà Nội, ngày tháng năm 2022

Tác giả

Nguyễn Thị Thu Nga

LỜI CẢM ƠN

Luận án được thực hiện tại Viện Khoa học và Công nghệ Quân sự - Bộ

Quốc phòng. Lời đầu tiên, NCS xin bày tỏ lòng biết ơn sâu sắc tới Phó Giáo sư

Tiến sĩ Lê Mỹ Tú, Tiến sĩ Nguyễn Ngọc Cương, đã tận tình giúp đỡ, chỉ dẫn

cho NCS phương pháp nghiên cứu, kinh nghiệm, kiến thức khoa học và kiểm

tra, đánh giá các kết quả nghiên cứu cho NCS.

NCS xin cảm ơn Ban Giám đốc Viện Khoa học và Công nghệ Quân sự,

Thủ trưởng và cán bộ, nhân viên Phòng Đào tạo, Viện Công nghệ Thông tin là

cơ sở đào tạo và đơn vị quản lý đã tạo mọi điều kiện, hỗ trợ, giúp đỡ NCS trong

suốt quá trình học tập, nghiên cứu.

NCS xin cảm ơn Ban lãnh đạo Viện Hàn lâm Khoa học và Công nghệ Việt

Nam, Thủ trưởng Viện Công nghệ Thông tin, Phòng Công nghệ và Giải pháp

Phần mềm đã động viên, hỗ trợ, tạo điều kiện cho NCS được học tập, nghiên cứu.

NCS xin bày tỏ lòng biết ơn chân thành tới các thầy, cô của Viện Khoa

học và Công nghệ quân sự, các nhà khoa học trong và ngoài quân đội đã chỉ

bảo và nâng đỡ các kết quả học tập, nghiên cứu của NCS.

NCS xin được cảm ơn bạn bè, đồng nghiệp và rất nhiều người đã luôn

động viên, chia sẻ, giúp đỡ NCS trong suốt thời gian học tập, nghiên cứu.

Sau cùng, NCS tri ân công ơn của bố mẹ, sự giúp đỡ của gia đình và

xin dành lời cảm ơn đặc biệt tới chồng con, những người đã luôn ở bên cạnh,

động viên và là chỗ dựa về mọi mặt giúp NCS vượt qua khó khăn để hoàn

thành công việc.

Tác giả

iii

MỤC LỤC

Trang

DANH MỤC KÝ HIỆU VÀ CHỮ VIẾT TẮT ................................................ v

DANH MỤC CÁC BẢNG................................................................................ x

DANH MỤC CÁC HÌNH VẼ ......................................................................... xi

MỞ ĐẦU ........................................................................................................... 1

Chương 1. TỔNG QUAN VỀ THUẬT TOÁN MÃ HOÁ ............................... 7

1.1 Thuật toán mã khối ..................................................................................... 8

1.2 Mã hoá bất đối xứng ................................................................................. 15

1.2.1 Thuật toán mã hóa RSA ......................................................................... 16

1.2.2 Thuật toán dựa trên đường cong Elliptic ............................................... 17

1.3 Tình hình nghiên cứu trong và ngoài nước đối với việc nâng cao hiệu

năng một số thuật toán mã hóa ........................................................................ 18

1.3.1 Tình hình nghiên cứu ngoài nước .......................................................... 18

1.3.2 Tình hình nghiên cứu trong nước ........................................................... 21

1.3.3 Một số vấn đề tồn tại và hướng nghiên cứu phát triển .......................... 23

1.4 Kết luận chương 1 ..................................................................................... 26

Chương 2. NÂNG CAO ĐỘ AN TOÀN VÀ HIỆU NĂNG CAO THUẬT

TOÁN MÃ HÓA AES .................................................................................... 27

2.1 Một số khái niệm ....................................................................................... 27

2.2 Thuật toán AES ......................................................................................... 30

2.3 Nâng cao độ an toàn và hiệu năng cao thuật toán AES ............................ 32

2.3.1 Sự khuyếch tán trong tầng biến đổi tuyến tính của mã khối có cấu

trúc SPN .......................................................................................................... 32

2.3.2 Giải pháp nâng cao độ an toàn của thuật toán AES ............................... 37

2.3.3 Nâng cao hiệu năng của thuật toán AES cải tiến với ma trận MDS

mới ................................................................................................................... 43

2.4 Kết luận chương 2 ..................................................................................... 53

Chương 3. NÂNG CAO ĐỘ AN TOÀN VÀ HIỆU NĂNG THUẬT TOÁN

MÃ HÓA DỰA TRÊN ĐƯỜNG CONG ELLIPTIC ..................................... 55

3.1 Tổng quan về đường cong Elliptic ............................................................ 55

3.1.1 Cơ sở toán học ........................................................................................ 55

3.1.2 Nhóm các điểm của đường cong elliptic trên trường hữu hạn ............. 58

3.1.3 Nhân vô hướng của một điểm trên đường cong Elliptic ........................ 60

3.1.4 Đường cong Elliptic trên trườnghữu hạn ......................................... 60

3.2 Phương pháp trao đổi khoá mã an toàn hệ mật dựa trên đường cong

Elliptic ............................................................................................................. 61

3.2.1 Bài toán logarit rời rạc ........................................................................... 61

3.2.2 Ánh xạ song tuyến .................................................................................. 62

3.2.3 Đường cong Elliptic ............................................................................... 64

3.2.4 Các giao thức mật mã sử dụng ánh xạ song tuyến ................................. 68

3.2.5 Kết quả thử nghiệm ứng dụng ................................................................ 71

3.3 Nghiên cứu, đề xuất xây dựng thuật toán hiệu quả nhân nhanh đa thức

với hệ số nguyên.............................................................................................. 73

3.3.1 Biến đổi Fourier nhanh và cách thực hiện ............................................ 74

3.3.2 Biểu diễn các phần tử trường và phép nhân nhanh trong vành đa thức .... 74

3.3.3 Sử dụng định lý phần dư của Trung Hoa để phân chia tính toán giữa

các bộ vi xử lý ................................................................................................. 81

3.3.4 Thực hiện thuật toán nhân nhanh đa thức trên bộ vi xử lý 64 bit .......... 85

3.4 Kết luận chương 3 ..................................................................................... 89

KẾT LUẬN ..................................................................................................... 91

DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ ................ 93

TÀI LIỆU THAM KHẢO ............................................................................... 95

PHỤ LỤC ..................................................................................................... PL1

DANH MỤC KÝ HIỆU VÀ CHỮ VIẾT TẮT

Dấu đồng dư ≡

Dương vô cùng (tương đương vói +∞) ∞

Byte ở dòng i, cột j aij

Đặc số của trưòng char(K)

Bậc của đa thức f. deg(f)

Định thức det

Ký hiệu đường cong elliptic. E

Hàm mã hóa AES với khóa bí mật K

Nhóm các điểm của E trên trường . E()

E[m] Nhóm m-xoắn (m nhỏ nhất sao cho mP = ).

End[E] Vành các tự đồng cấu của E.

Ký hiệu cho trường hữu hạn chứa p phần tử với p là số nguyên

tố.

Ký hiệu cho trường hữu hạn chứa 2n phần tử.

Một điểm trên E sinh ra một nhóm cyclic cấp N. G

Nhóm cyclic được sinh bởi g. g

Ước số chung lớn nhất (greatest common divisor) Gcd

Ước chung lớn nhất của a và b

Khóa bí mật

Nhóm nhân và trường đóng đại số của trường . K* ,

Khóa bí mật của nút i

Bội k lần điểm Q, nghĩa là Q + Q + ... + Q, k số hạng. kQ

Ánh xạ tuyến tính

Tập các số tự nhiên

Tập hợp số tự nhiên khác 0 N∗

Số các cột trong trạng thái

Số các cột của khóa mã

O(f(n)) Hàm g(n) sao cho |g(n)| C|f(n)| với C là hằng số, n đủ lớn.

o(f(n)) Hàm g(n) sao cho .

Cấp của phần tử g trong nhóm. ord(g)

Số các cột trong trạng thái

Tập các số thực

Tập các số nguyên

Chuẩn mã hóa tiên tiến (Advanced Encryption Standard) AES

Vi mạch tích hợp chuyên dụng (Application-specific ASIC

Integrated Circuit)

Một thuật toán mã hóa

Đơn vị cấp phát chứng thư (Certificate Authority) Blowfish CA

Một phương thức mật mã khối CBC (Cipher Block Chaining CBC

mode)

CFB Một phương thức mật mã khối dựa trên chế độ phản hồi bản

mã CFB (Cipher FeedBack Mode)

CIA Bí mật, toàn vẹn, sẵn sàng (Confidentiality, Intergrity,

Availability)

Kiểm tra phần dư Cyclic (Cyclic Redundancy Check) CRC

Định lý phần dư Trung Hoa (Chinese Remainder Theorem)

Chuẩn mã hóa dữ liệu (Data Encryption Standard) CRT DES

vii

Biến đổi Fourier rời rạc

Đường cong Elliptic (EllipticCurve)

DFT EC ECB Chế độ mã điện tử (Electronic Codebook Mode)

Mật mã trên đường cong Elliptic (Elliptic Curve Cryptography)

ECC ECC Hệ mật trên đường cong Elliptic (Elliptic Curve Cryptosystem).

Thuật toán thỏa thuận khóa Diffie-Hellman dựa trên đường ECDH

cong elliptic

Bài toán logarith rời rạc trên đường cong elliptic (Elliptic ECDLP

Curve Logarithm Problem)

Thuật toán chữ ký số dựa trên đường cong Elliptic ECDSA

(Elliptic Curve Digital Signature Algorithm).

ECDSA Thuật toán chữ ký số dựa trên đường cong Elliptic (Elliptic

Curve Digital Signature Algorithm)

Hệ mã hóa tích hợp dựa trên đường cong elliptic (Elliptic ECIES

Curve Integrated Encryption System)

EMV Tiêu chuẩn toàn cầu cho các giao dịch tín dụng và ghi nợ dựa

trên công nghệ chip (Europay, MasterCard, Visa)

Biến đổi Fourier nhanh (Fast Fourier Transform)

FFT FIPS-197 Tiêu chuẩn Xử lý thông tin Liên bang 197 (Federal

Information Processing Standard)

FPGA Vi mạch tích hợp cỡ lớn có thể lập trình được (Field

Programmable Gate Array)

GOST Chuẩn mật mã quốc gia Nga (Liên Xô trước đây)

IDEA Thuật toán mật mã hóa dữ liệu quốc tế (International Data

Encryption Algorithm)

IOT Internet of Things

viii

ISE Công cụ phần mềm thiết kế và tổng hợp vi mạch cỡ lớn có

thể lập trình được (FPGA) của Xilinx (Integrated Software

Enviroment)

ISIM Một trình mô phỏng đầy đủ tính năng được tích hợp trong

ISE (ISE Simulator)

LOKI Mật mã khối được công bố năm 1990 để thay thế cho mật

mã DES

MDS (Các ma trận, mã) khả tách có khoảng cách cực đại

(Maximum Distance Separable)

MIT Học viện Công nghệ Massachusetts (Massachusetts Institute

of Technology)

Nghiên cứu sinh NCS

Viện Công nghệ và Chuẩn Quốc gia Hoa Kỳ (NIST) NIST

(National Institute of Standards and Technology)

Một phương thức mã hóa (Output Feedback) OFB

Khóa mã dùng một lần (One time pad) OTP

Một phần mềm máy tính dùng để mã hóa dữ liệu và xác thực PGP

(Pretty Good Privacy)

Trưòng số hữu tỉ Q

Thuật toán mã khối khóa đối xứng do Ronald Rivest thiết kế RC5

năm 1994, (Rivest Cipher)

Định danh tần số vô tuyến (Radio Frequency Identification). RFID

Rivest-Shamir-Adleman RSA

Cấu trúc thay thế hoán vị (Substitution-Permutation Networds) SPN

Triple DES Ba DES (Triple Data Encription Standard)

WPA Chuẩn bảo mật trên những mạng không dây (Wi-Fi protected

access)

WPA-2 Chuẩn bảo mật thay thế cho WPA vào năm 2006 (Wi-Fi

Protected Access 2 )

WTLS Bảo mật cho các ứng dụng sử dụng các ứng dụng không dây

WAP (Wireless Transport layer Security)

XOR Phép toán cộng modulo 2 (Exclusive-OR)

DANH MỤC CÁC BẢNG

Trang

Bảng 2.1. Các giá trị của cq,p ........................................................................... 39

q,p .......................................................................... 39

Bảng 2.2. Các giá trị của v1

Bảng 2.3. Danh sách ma trận MDS tựa vòng 4x4 .......................................... 41

Bảng 2.4. Bảng tổng hợp đánh giá các phương pháp thiết kế. ....................... 53

Bảng 3.1. Giá trị khóa thỏa thuận được là K = abP = a(bP) = b(aP). ............. 61

Bảng 3.2. Giá trị khóa thỏa thuận được sẽ là K = abcP .................................. 62

Bảng 3.3. Số điểm của các đường cong Elliptic tương ứng trên trường F5 .... 65

Bảng 3.4. Thoả thuận khóa mã một vòng dùng cho ba bên ............................ 68

Bảng 3.5. Các số nguyên tố được sử dụng trong phần mềm. ......................... 85

Bảng 3.6. So sánh thời gian tính toán với phương pháp nhân cổ điển với thuật

toán đề xuất nhân đa thức bậc n từ 210 đến 218 với hệ số 256 ......................... 87

Bảng 3.7. So sánh thời gian tính toán với phương pháp nhân cổ điển với thuật

toán đề xuất nhân đa thức bậc n từ 210 đến 218 với hệ số 512 ......................... 88

DANH MỤC CÁC HÌNH VẼ

Trang

Hình 1.1. Cấu trúc chung của thuật toán mã khối ........................................... 15

Hình 2.1. Cách bố trí của trạng thái và khoá mã cho trường hợp Nb= 4 và Nk .. 29

Hình 2.2. Cấu trúc tổng thể của thuật toán AES ............................................. 31

Hình 2.3. Mô hình kiến trúc mã khối AES-256 theo kiến trúc đường ống .... 44

Hình 2.4. Cấu trúc một module Encryption .................................................... 44

Hình 2.5. Cấu trúc module Encryption 14 ...................................................... 44

Hình 2.6. Sơ đồ nguyên lý RTL và Tần số hoạt động core AES-256 theo kiến

trúc đường ống toàn phần ................................................................................ 46

Hình 2.7. Kết quả thực hiện AES-256 theo mô hình kiến trúc đường ống toàn

phần trên công cụ ISIM ................................................................................... 47

Hình 2.8. Tài nguyên thiết kế AES-256 cải tiến theo kiến trúc đường ống toàn

phần ................................................................................................................. 47

Hình 2.9. Mô hình kiến trúc mã khối AES-256 cải tiến theo kiến trúc lặp .... 48

Hình 2.10. Sơ đồ nguyên lý RTL và Tần số hoạt động core AES-256 cải tiến

theo kiến trúc lặp ............................................................................................. 48

Hình 2.11. Kết quả mô phỏng kiến trúc mã khối AES-256 cải tiến theo kiến

trúc lặp trên công cụ ISIM .............................................................................. 49

Hình 2.12. Tài nguyên thiết kế core AES-256 cải tiến theo kiến trúc lặp ...... 49

Hình 2.13. Mô hình mã khối AES-256 cải tiến theo kiến trúc lai ghép ......... 50

Hình 2.14. Sơ đồ nguyên lý RTL và Tần số hoạt động core AES-256 cải tiến

theo kiến trúc lai ghép ..................................................................................... 51

Hình 2.15. Kết quả kiểm tra mô phỏng mã khối AES-256 cải tiến theo kiến trúc

lai ghép trên công cụ ISIM .............................................................................. 51

Hình 2.16. Tài nguyên thiết kế mã khối AES-256 cải tiến theo kiến trúc lai

ghép ................................................................................................................. 52

xii

Hình 3.1. Phép cộng hai điểm trên EC ............................................................ 58

Hình 3.2. Đường cong elliptic trên mặt phẳng thực ....................................... 64

Hình 3.3. Phép toán trên các điểm của đường cong elliptic ........................... 66

Hình 3.4. Thuật toán thỏa thuận khóa nhiều người dùng ............................... 69

Hình 3.5. Ảnh gốc trước khi mã mật hóa ........................................................ 72

Hình 3.6. Ảnh giải mã mật với khóa mã sai ................................................... 72

Hình 3.7. Ảnh sau khi giải mã mật với khóa mã đúng ................................... 72

Hình 3.8. So sánh tốc độ thực hiện thuật toán nhân cổ điện với thuật toán đề

xuất nhân đa thức bậc n từ 210 đến 218 với hệ số 256 ...................................... 87

Hình 3.9. So sánh tốc độ thực hiện thuật toán nhân cổ điện với thuật toán đề

xuất nhân đa thức bậc n từ 210 đến 218 với hệ số 512 ...................................... 88

MỞ ĐẦU

1. Tính cấp thiết của đề tài luận án

Nhu cầu bảo mật thông tin phục vụ cho chỉ đạo, chỉ huy trong lĩnh vực

An ninh - Quốc phòng và Kinh tế - Xã hội ngày càng cao. Tuy nhiên, do sự

phát triển khoa học công nghệ, đặc biệt trong lĩnh vực Điện tử, Viễn thông,

Toán học và Mật mã, Thu tin mã thám,... thì thông tin trao đổi trên các kênh

thông tin công cộng ngày càng gặp nhiều rủi ro và có nhiều mối đe dọa, vì vậy

đảm bảo an ninh, an toàn thông tin là một vấn đề cấp bách và cần thiết.

Sự phát triển của nền kinh tế hiện đại gắn liền với sự phát triển của cơ sở

hạ tầng CNTT-TT và Internet. Mức độ nhạy cảm của dữ liệu được gửi trong

mạng thông tin công cộng (như: số liệu thẻ tín dụng, dữ liệu cá nhân, tài liệu y

tế, tài liệu tài chính…) và số người dùng cũng tăng lên. Đặt ra một thách thức

lớn đối với mật mã, đòi hỏi cần phải xây dựng các giải pháp vừa đảm bảo độ

bảo mật cao vừa nâng cao hiệu năng về mặt tính toán.

Để nâng cao độ an toàn và bảo mật các thông tin được mã hóa truyền

trên kênh thông tin công cộng, người ta đã đưa ra nhiều thuật toán mật mã, với

độ mật và độ dài khóa ngày càng cao như: DES, Triple DES, IDEA, AES, RC5,

Blowfish, mật mã khóa công khai RSA, Hệ mật trên đường cong Elliptic… Tuy

nhiên, do hạn chế năng lực của các thiết bị tính toán, thiết bị xử lý mật dữ liệu…

để tăng độ mật dữ liệu được mã hóa thì thời gian cần thiết để mã hóa và giải

mã dữ liệu tăng lên và độ phức tạp tính toán cũng tăng theo… trong khi yêu

cầu chỉ đạo, chỉ huy trong An ninh - Quốc phòng và trong bảo mật thông tin

kinh tế - xã hội đòi hỏi phải: bí mật, nhanh chóng, chính xác, an toàn và tiện

dụng…. Vì vậy, nghiên cứu để nâng cao hiệu năng của thuật toán mật mã ứng

dụng trong mã hóa và giải mã dữ liệu trong giai đoạn hiện nay là một nội dung

có tính khoa học có tính cấp thiết và thực tiễn cao.

Mặt khác, sự phát triển năng động của công nghệ phần cứng không thể

trực tiếp làm tăng được một cách đáng kể tốc độ mã hóa và giải mã các thông

tin, vì các thuật toán mã hóa hiện đang sử dụng được thiết kế điển hình theo

các thuật toán tuần tự do các giải pháp công nghệ trước đây..... do đó, chưa sử

dụng hết công suất của máy tính.

Vì vậy việc nghiên cứu xây dựng các thuật toán mật mã đứng trước

những yêu cầu cao hơn, không chỉ cần độ an toàn mật mã cao mà còn phải có

hiệu năng thực hiện mã hóa và giải mã cao, cũng như khả năng làm việc thích

ứng trong các môi trường đặc biệt..., đáp ứng nhu cầu bảo mật thông tin với

dung lượng tin mật cao, trong thời gian thực… phục vụ cho chỉ đạo, chỉ huy

trong lĩnh vực An ninh - Quốc phòng và lĩnh vực kinh tế - xã hội.

Trong nước, bảo mật thông tin là một vấn đề cấp thiết đặt ra và đang

được tập trung nghiên cứu. Ban Cơ yếu Chính phủ là cơ quan có chức năng bảo

vệ thông tin chỉ đạo, điều hành của Đảng và Nhà nước bằng kỹ thuật mật mã.

Đã có một số đề tài nghiên cứu xây dựng hệ tiêu chuẩn tham số an toàn “Hệ

tiêu chuẩn tham số an toàn cho hệ mật RSA và ứng dụng” (LATS-2011-

VNCKH và CNQS-Hoàng Văn Thức), “Nghiên cứu xây dựng tiêu chuẩn an

toàn cho tham số hệ mật Elliptic và ứng dụng” (LATS-2011-VNCKH và

CNQS-Nguyễn Quốc Toàn), “Nghiên cứu xây dựng một số dạng lược đồ mới

cho chữ ký số tập thể”, (LATSTH-2017, VKH và CNQS-Đặng Minh Tuấn),

hoặc các phương pháp tự động bảo mật tín hiệu tiếng nói, cơ sở dữ liệu, xây

dựng giao thức trao đổi khóa an toàn dựa trên chữ ký số như: (“Xây dựng lược

đồ chữ ký số an toàn từ các lược đồ định danh” (Võ Tùng Linh, Tạp chí An

toàn thông tin, Vol 08, N02,2018; “Một lược đồ chữ ký số xây dựng trên tính

khó của việc giải đồng thời 2 bài toán logarit rời rạc và phân tích số/khai căn”,

Tạp chí Nghiên cứu KH&CNQS, 04-2019, “Giải pháp nâng cao độ an toàn cho

lược đồ chữ ký số” Hồ Ngọc Duy, Vũ Long Vân…, SOIS -2017 Thành phố Hồ

Chí Minh; …). Một số công trình nghiên cứu mang tính lý thuyết, học thuật, đề

xuất xây dựng hệ tiêu chuẩn an toàn cho các tham số cho các hệ mật sử dụng

trong bảo mật thông tin; thuật toán mô phỏng thực hiện có tính minh chứng cho

giải pháp đề xuất,… Vì vậy việc nghiên cứu một số giải pháp nâng cao hiệu

quả tạo tham số an toàn và cũng như nâng cao hiệu năng của các thuật toán mã

hóa và giải mã dưới góc độ tối ưu hóa thời gian tính toán, cũng như tối ưu hóa

bộ nhớ của hệ thống dành cho thực hiện các thuật toán mật mã, hoặc tối thiểu

hóa độ phức tạp tính toán…còn là những nội dung nghiên cứu mang tính thời

sự và có ý nghĩa khoa học và tính cấp thiết cao.

Một số đề tài khác nghiên cứu cứng hóa các thuật toán mật mã; tuy

nhiên, do các phần cứng chuyên dụng phải nhập ngoại, công cụ để cứng hóa

hạn chế,… nên kết quả đạt được còn hạn chế. Một số kết quả bảo mật thuộc

lĩnh vực An ninh - Quốc phòng trên thế giới đã được áp dụng, nhưng không

được công bố,… Vì vậy hướng nghiên cứu nâng cao hiệu năng của thuật toán

mật mã bằng phương pháp hiệu quả tạo các tham số an toàn và song song hóa

các thuật toán mã hóa lựa chọn, sẽ là một hướng nghiên cứu đúng đắn, có tính

cấp thiết, khoa học và thực tiễn trong lĩnh vực bảo mật và an toàn thông tin.

Xuất phát từ tình hình thực tế và cách đặt vấn đề như trên, Nghiên cứu

sinh đã chọn đề tài “Nghiên cứu một số giải pháp nâng cao hiệu năng của

thuật toán mã hóa” nhằm mục đích nghiên cứu cơ sở toán học các thuật toán

mật mã dùng trong bảo mật thông tin, từ đó nghiên cứu và đề xuất một số

phương pháp hiệu quả tạo tham số an toàn và nâng cao hiệu năng các thuật toán

đề xuất, có thể ứng dụng trong thực tiễn.

2. Mục tiêu nghiên cứu

Mục tiêu của luận án là:

- Nghiên cứu nâng cao hiệu năng của một số thuật toán mã hóa.

- Cụ thể là: Nghiên cứu đề xuất, xây dựng phương pháp hiệu quả tạo

tham số an toàn và nâng cao hiệu năng thực hiện mã hóa và giải mã, có khả

năng làm việc thích ứng trong các môi trường cho một số hệ mật ứng dụng

trong bảo mật thông tin.

3. Đối tượng và phạm vi nghiên cứu

Đối tượng nghiên cứu của luận án: Luận án tập trung vào nghiên cứu các

hệ mật, phương pháp hiệu quả tạo tham số an toàn và nâng cao hiệu năng một số

thuật toán mã hóa cho một số hệ mật ứng dụng trong bảo mật thông tin.

Phạm vi nghiên cứu của luận án: là các thuật toán mật mã dùng trong

bảo mật thông tin và giải pháp nâng cao hiệu năng của thuật toán mã hóa AES-

256; hệ mật dựa trên đường cong elliptic và giải pháp nâng cao độ an toàn và

hiệu năng cao thuật toán mã hóa dựa trên đường cong Elliptic.

4. Nội dung nghiên cứu

Để đạt được mục tiêu đã đặt ra. Luận án thực hiện các nội dung nghiên

cứu sau:

Nghiên cứu tổng quan về thuật toán mật mã dùng trong bảo mật thông tin.

Nâng cao hiệu năng của thuật toán mã hóa AES-256, trên cơ sở xây dựng

và lựa chọn ma trận MDS mới có các tính chất mật mã tốt cho tầng khuếch tán,

đồng thời lựa chọn một số mô hình kiến trúc cứng hóa và sử dụng linh hoạt các

nguồn tài nguyên phần cứng; cũng như mô phỏng thực tế các giải pháp đề xuất

trên công cụ ISIM của ISE.

Nghiên cứu ứng dụng hệ mật dựa trên đường cong elliptic và phương

pháp trao đổi khóa mã an toàn.

Nghiên cứu đề xuất xây dựng thuật toán mới, hiệu quả nhân nhanh đa

thức với hệ số nguyên sử dụng biến đổi Fourier nhanh (Fast Fourier Transform)

và định lý phần dư Trung Hoa và thực hiện thực tế thuật toán đề xuất trên các

bộ vi xử lý 32-bit hoặc 64-bit.

5. Phương pháp nghiên cứu

Phương pháp nghiên cứu được sử dụng trong luận án bao gồm:

- Nghiên cứu kết hợp giải tích toán học với phương pháp thực nghiệm

cứng hóa và xây dựng chương trình nâng cao hiệu năng một số thuật toán mã

hóa cho một số hệ mật ứng dụng trong bảo mật thông tin.

6. Ý nghĩa khoa học và thực tiễn

Ý nghĩa khoa học: Luận án đóng góp một số kết quả nghiên cứu mới

nhằm nâng cao hiệu năng của một số thuật toán mã hóa. Cụ thể, luận án đã:

- Nghiên cứu một cách hệ thống về các thuật toán mật mã dùng trong bảo

mật thông tin, từ đó đề xuất giải pháp nâng cao hiệu năng của thuật toán mã

hóa AES-256. Nghiên cứu hệ mật dựa trên đường cong elliptic và nghiên cứu,

đề xuất xây dựng thuật toán hiệu quả nhân nhanh đa thức với hệ số nguyên, tạo

ra một phương pháp hiệu quả nhân nhanh các đa thức ứng dụng trong thực tiễn;

đặc biệt là trong các ứng dụng mật mã.

Ý nghĩa thực tiễn: Từ các kết quả đạt được ở trên, luận án đã: Nghiên

cứu, đề xuất kiến trúc, thực thi cứng hóa hệ thống mã hóa và giải mã nhằm nâng

cao hiệu năng thuật toán mã hóa AES - 256. Xây dựng thuật toán, chương trình

hiệu quả thực hiện nhân nhanh đa thức với hệ số nguyên, tạo ra một phương

pháp hiệu quả nhân nhanh các đa thức ứng dụng trong thực tiễn; đặc biệt là

trong các ứng dụng mật mã, đáp ứng nhu cầu bảo mật thông tin trong các lĩnh

vực kinh tế - xã hội và an ninh - quốc phòng.

7. Bố cục của luận án

Luận án gồm 03 chương cùng với các phần mở đầu, kết luận, tài liệu

tham khảo, danh mục các công trình khoa học đã được công bố của tác giả và

phần phụ lục.

Chương 1. Tổng quan về thuật toán mã hóa

Nghiên cứu tổng quan và cơ sở toán học các thuật toán mật mã dùng

trong bảo mật thông tin

Chương 2. Nghiên cứu nâng cao độ an toàn và hiệu năng cao thuật toán

mã hóa AES

Chương này trình bày một số giải pháp nâng cao độ an toàn và hiệu năng

thuật toán mã hóa hệ mật AES, trên cơ sở xây dựng và lựa chọn ma trận MDS

mới có các tính chất mật mã tốt cho tầng khuếch tán, đồng thời lựa chọn một

số mô hình kiến trúc cứng hóa và sử dụng linh hoạt các nguồn tài nguyên phần

cứng; cũng như mô phỏng thực tế các giải pháp đề xuất trên công cụ ISIM của

ISE. Các kết quả đạt được cho phép khẳng định có thể lựa chọn ma trận MDS

mới có các tính chất mật mã tốt cho tầng khuếch tán, đồng thời lựa chọn một

số mô hình kiến trúc cứng hóa các thuật toán mã hóa phức tạp để nâng cao độ

an toàn và hiệu năng của chúng trong bảo mật thông tin.

Chương 3. Nghiên cứu, đề xuất thuật toán nâng cao độ an toàn và hiệu

năng cao dựa trên đường cong Elliptic

Chương này tập trung nghiên cứu về đường cong elliptic và mật mã dựa

trên đường cong Elliptic, đường cong Elliptic mạnh và cách tạo chúng; cũng

như ứng dụng phương pháp trao đổi khóa mã an toàn và những ứng dụng mới

của Hệ mật sử dụng cơ chế nhóm điểm trên đường cong Elliptic.

Nghiên cứu, đề xuất ứng dụng thuật toán mới, hiệu quả nhân nhanh đa

thức với hệ số nguyên sử dụng biến đổi Fourier nhanh (Fast Fourier Transform)

và định lý phần dư Trung Hoa và thực hiện thực tế thuật toán đề xuất. Các kết

quả so sánh thời gian tính bằng thuật toán cổ điển với thời gian thực hiện

trên các bộ vi xử lý đa lõi (4 nhân) dựa trên biến đổi Fourier và định lý phần

dư Trung Hoa chỉ rõ ưu điểm của thuật toán đề xuất là tốc độ tính toán dựa

trên biến đổi Fourier và định lý phần dư Trung Hoa nhanh hơn rất nhiều lần

tốc độ tính toán bằng phương pháp cổ điển.

Chương 1

TỔNG QUAN VỀ THUẬT TOÁN MÃ HOÁ

Chương 1 trình bày tổng quan về thuật toán mã khối và hệ mật dựa trên

đường cong elliptic dùng trong bảo mật thông tin và tình hình nghiên cứu trong

và ngoài nước nhằm nâng cao hiệu năng một số thuật toán mã hóa và định

hướng nghiên cứu chuyên sâu gồm:

- Mô hình cho mã khối được lựa chọn là mô hình có cấu trúc SPN để

đảm bảo độ an toàn và hiệu quả cao, trong đó tầng phi tuyến sử dụng các S-hộp

4 bit và tầng tuyến tính được xây dựng dựa trên các ma trận MDS.

- Nghiên cứu hệ mật dựa trên đường cong elliptic và phương pháp trao

đổi khóa mã an toàn.

- Xây dựng thuật toán hiệu quả nhân nhanh đa thức với hệ số nguyên

sử dụng biến đổi Fourier nhanh (Fast Fourier Transform) và định lý phần dư

Trung Hoa và thực hiện thực tế thuật toán đề xuất trên các bộ vi xử lý 32-bit

hoặc 64-bit.

Tính năng quan trọng nhất sau bảo mật của các thuật toán mật mã theo

quan điểm của người dùng là tốc độ mã hóa, giải mã dữ liệu và tài nguyên tính

toán sử dụng. Trong kỷ nguyên của xã hội thông tin với sự phát triển nhanh

chóng các mạng máy tính, kết nối vạn vật (IoT)... giữa các doanh nghiệp và

trên toàn thế giới, và sự gia tăng đột biến lượng thông tin được gửi qua mạng

đòi hỏi phải đảm bảo tốc độ mã hoá và giải mã thông tin một cách thích hợp,

nói cách khác bài toán rút ngắn thời gian mã hóa và giải mã là một vấn đề rất

quan trọng trong thực tiễn. Để đáp ứng yêu cầu của các hệ thống bảo mật thông

tin hiện đại về mặt tốc độ, nhiều công trình nghiên cứu nhằm nâng cao hiệu

năng, tốc độ mã hóa và giải mã dữ liệu ở cả lĩnh vực phần cứng và phần mềm

đang được quan tâm và đầu tư nghiên cứu như:

• Tăng cường công suất xử lý bộ procesor xử lý dữ liệu,

• Áp dụng các khối phần cứng chuyên dụng.

• Tăng tốc độ các thuật toán tuần tự,

• Các thuật toán mã hóa song song.

Tăng tốc độ các thuật toán tuần tự có thể bằng cách phát triển các thuật

toán mới, nhanh hơn các thuật toán đã được sử dụng hoặc bằng cách tối ưu hóa

mã nguồn thuật toán hiện có, tuy nhiên các kết quả đạt được còn hạn chế, chưa

đáp ứng được yêu cầu thực tế (có thể tham khảo chi tiết hơn trong các tài liệu

sau: [5], [14], [23]..).

Có thể chia ra hai loại thuật toán mã hóa: thuật toán mã hóa khóa đối xứng

(symmetric-key algorithms) và thuật toán mã hóa khóa công khai (public-key

cryptography). Hệ mật được gọi là hệ mật khóa đối xứng nếu khóa mã của bên

mã hóa và bên giải mã như nhau. Hệ mật khóa công khai sử dụng hai loại khóa

mã khác nhau: một loại khóa được sử dụng để mã hóa thông tin và có thể công

khai mà không có nguy cơ tiết lộ nội dung của các thông tin đã được mã hóa (gọi

là khóa công khai). Khóa giải mã được gọi là khóa riêng (hay khóa bí mật).

Thuật toán mã hóa sử dụng khóa đối xứng có thể được chia thành hai

loại chính:

- Thuật toán mã khối: mã hóa dữ liệu bằng các khối, với mỗi khối được

mã hóa một cách độc lập.

- Thuật toán mã luồng: mã hóa luồng dữ liệu một cách liên tục.

Phần tiếp theo trình bày về thuật toán mã khối, cách thức việc của mã

khối, mật mã luồng (dòng), mật mã phi đối xứng và triển khai thực hiện các

thuật toán mã hóa...cũng như tình hình nghiên cứu trong nước và trên thế giới

và định hướng nghiên cứu.

1.1 Thuật toán mã khối

Sự phát triển của kỹ thuật mã thám tiên tiến đặt cho các nhà thiết kế thuật

toán mã mật mới những đòi hỏi độ an toàn mật mã cao và phải đáp ứng các

điều kiện: hiệu năng mã hóa cao, có thể cứng hóa module mật mã, làm việc

thích ứng trong môi trường đặc biệt. Các dữ liệu được truyền trong mạng truyền

thông ngày càng dễ dàng bị chặn thu và gây nhiễu. Một số mạng được cấu trúc

với các phần tử có tài nguyên hạn chế làm cho chúng rất dễ bị tổn thương với

các loại tấn công khác nhau liên quan đến việc truy cập trái phép thông tin hoặc

ngăn chặn hoạt động từng bộ phận của mạng (tấn công từ chối dịch vụ [2]).

Trong những ứng dụng tiềm năng (quân sự, chính phủ điện tử, điều khiển các

quá trình công nghiệp,...) thì tính mở, quy mô, và khả năng truyền dẫn, tính an

toàn của thông tin được tạo ra và truyền dẫn trong mạng cần được xem xét, cân

nhắc khi thiết kế mạng [3]. Vì vậy thuật toán mật mã khối cũng là một sản phẩm

mật mã quan trọng đang được nhiều nước quan tâm đầu tư nghiên cứu.

Năm 1997, NIST (National Institute of Standards and Technology) đã

mở một cuộc thi dành cho các thiết kế cải tiến thuật toán mã khối với khóa mã

đối xứng. Kết quả chọn được năm thuật toán:

- MARS: Một thuật toán mã mới của Hãng IBM,

- RC6: Một thuật toán mã do Ronald Rivest đề xuất,

- Rijandel: Một thuật toán mã do hai người Bỉ (Joan Daemen và Vincent

Rijmen) đề xuất [41], [42],

- Serpent: Một thuật toán mã do đội tuyển mật mã quốc tế từ Anh, Israel

và Na Uy,

- Twofish: Một thuật toán mã do Bruce Schneier (người tạo Blowfish) [13].

Rijndael được xem là thuật toán có tốc độ mã hóa và giải mã nhanh

nhất. Về độ mật thì người ta cho rằng không có sự khác biệt đáng kể giữa các

phương pháp mã hóa đã được trình bày (cho đến thời điểm đó chưa có thuật

toán nào trong số kể trên bị phá mã). Thuật toán này được NIST lựa chọn và

trở thành tiêu chuẩn Quốc gia, gọi là Chuẩn mã hóa dữ liệu tiên tiến AES. Đây

là chuẩn mã khối được xây dựng trên cơ sở cấu trúc mạng thay thế hoán vị

(SPN) với kích thước khối là 128 bit. Mỗi khối đầu vào được biểu diễn dưới

dạng ma trận 4x4 trên trường F_(2^8 ). Chi tiết về thuật toán này có thể tham

khảo trong [41], [42].

Mã khối là một dạng mã đối xứng trong đó dữ liệu được chia thành các

bản rõ có kích thước cố định và mỗi bản rõ như vậy là đầu vào của thuật toán

mã hóa. Thông thường, thuật toán chứa một hàm vòng được lặp lại N lần (N

được gọi là số vòng của thuật toán). Hàm vòng này là một hàm tính toán đơn

giản có tính chất mật mã yếu song được lặp lại rất nhiều lần để tạo ra một thuật

toán mã hóa mạnh hơn. Với một mã khối, nó phải đáp ứng được đầy đủ hai yêu

cầu về tính hiệu quả và độ an toàn. Việc lựa chọn đối với kích cỡ khối, độ dài

khóa, hàm vòng và kích cỡ bản mã phụ thuộc vào đặc điểm kỹ thuật của máy

mã, an toàn cần thiết và mục đích triển khai. Hiện nay, ta có ba chiến lược cho

việc thiết kế các thuật toán mã khối dựa trên mạng Feistel, mạng SP (sử dụng

các phép biến đổi thay thế-hoán vị), mạng ARX (sử dụng phép cộng module

cùng dịch vòng và phép cộng XOR). Các thiết kế này cũng được thực hiện đối

với các mã khối.

 Các thành phần mật mã của một thuật toán mã khối

Để đảm bảo thuật toán mã khối an toàn trước các tấn công thám mã,

Shannon đã đưa ra hai nguyên lý “xáo trộn” và “khuếch tán” [83], với mục đích:

- Xáo trộn. Nguyên lý này được mô tả là sử dụng các biến đổi mật mã

hóa làm phức tạp quan hệ thống kê của bản mã vào bản rõ, hoặc nói ngắn gọn

là làm cho quan hệ giữa khóa và bản mã càng phức tạp càng tốt. Một hàm xáo

trộn tốt sẽ không đưa bất kì thông tin về khóa bởi việc phân tích phân bố của

bản rõ và bản mã. Các hàm xáo trộn thường được cài đặt bởi các S-hộp.

- Khuếch tán. Nguyên lý này đảm bảo tính dàn trải ảnh hưởng của các

đặc tính bản rõ ban đầu qua bản mã càng nhiều càng tốt. Mục đích chính của

hàm khuếch tán là làm mất các hiểu biết của các tính chất thống kê của bản rõ.

Nó phân bố đầu vào thành một miền phức tạp của đầu ra với phân bố bằng

nhau. Hàm khuếch tán thường được cài đặt bởi phép biến đổi tuyến tính như

các hoán vị bit,...

Để thực hiện hai nguyên lý này, các mã khối an toàn thường được thiết

kế với hai tầng biến đổi riêng và đan xen với nhau đó là:

Tầng phi tuyến. Việc sử dụng các S-hộp trong mã khối nhằm mục đích

chính là tạo tính phi tuyến. Chúng thường được đưa ra như các bảng tra lớn, để

thay thế một giá trị bằng một giá trị khác. Ta có thể thấy các ví dụ như các S-hộp

của Rijndael[21], LED[34], PRESENT[12]... Trái lại, một số mã pháp lại không

sử dụng các S-hộp rõ ràng mà tính phi tuyến được đảm bảo bởi một số phép toán

đại số như phép cộng số nguyên, phép nhân số nguyên, phép logarit hoặc phép

mũ như trong các mã khối SIMON và SPECK[6]. Tuy nhiên, sự khác nhau này

khá nhỏ. Chẳng hạn, một hàm logarit hoặc một phép nhân có thể xem như một

S-hộp và các S-hộp được sử dụng trong các thuật toán như AES lại cũng có thể

biểu diễn như là một ánh xạ nghịch đảo x-1 trên trường .

Tầng tuyến tính. Về mặt chức năng, ta có thể xem tầng biến đổi tuyến

tính thực hiện nguyên lý “khuếch tán”. Trên quan điểm của thám mã, thì tầng

biến đổi tuyến tính có mục đích làm cho xác suất lượng sai và xác suất tuyến

tính của hàm vòng đối với mọi sai khác đầu vào khác không và mọi mặt che

đầu ra khác không càng nhỏ càng tốt. Mặt khác, như chính tên gọi của nó, tầng

biến đổi tuyến tính đơn giản là các phép biến đổi tuyến tính dữ liệu ở đầu vào

để tạo dữ liệu đầu ra. Trong thực tế, người thiết kế phải lựa chọn các phép biến

đổi tuyến tính một cách cẩn thận để đạt được sự khuếch tán tối ưu nhất, có khả

năng kháng lại các tấn công đã biết một cách tốt nhất. Ngoài ra, tầng tuyến tính

còn đóng vai trò quan trọng trong việc cài đặt cũng như thực thi hiệu năng của

thuật toán.

 Các yêu cầu trong thiết kế mã khối

Các thuật toán mã khối thông thường và truyền thống không thể sử dụng

đa năng cho mọi kiểu thiết bị cũng như bộ vi xử lý. Lý do đầu tiên ta có thể dễ

nhận thấy là việc thiết kế các thuật toán mật mã hiện đại thường nhắm tới việc

tận dụng tốt công nghệ tiên tiến nhất, đó là các bộ vi xử lý 32-bit hoặc thậm chí

là 64 bit. Do đó, khi cài đặt các thuật toán cho các thiết bị có tài nguyên hạn

chế như bộ vi xử lý 4 bit, 8 bit, kích cỡ RAM nhỏ, tần số hoạt động thấp...

thường sẽ khó cài đặt hơn do nhiều yếu tố: tốn kém nhiều lệnh hoặc mã lệnh

hơn, chi phí cài đặt cao hơn tùy thuộc vào đặc điểm riêng của từng kiến trúc,

cấu hình của vi xử lý; năng lượng tiêu thụ nhiều hơn. Lý do quan trọng nhất là

đối với các thiết bị có tài nguyên hạn chế, đó là vấn đề an toàn cần phải có sự

thỏa hiệp với chi phí cài đặt và tính hiệu quả của thiết bị. Một thiết bị an toàn

có tốc độ thực hiện chậm hoặc chi phí cài đặt quá cao thì rõ ràng không thể ứng

dụng được trong thực tế. Lý do cuối cùng là dữ liệu hoặc thông tin cần bảo mật

thường không phải là dữ liệu mang tính nhạy cảm cao chẳng hạn ở mức tuyệt

mật. Cụ thể đối với AES, thuật toán mã khối này đòi hỏi phải có diện tích chíp

cỡ khoảng 3400 GE và hiệu năng rất chậm trong các thiết bị hạn chế so với khi

triển khai trên các thiết bị mạnh. Ngoài việc hạn chế tài nguyên và hiệu năng,

một vấn đề nữa đòi hỏi sự cần thiết của thuật toán mã khối là AES cung cấp độ

an toàn nhiều hơn những gì cần thiết trong kịch bản triển khai cho các thiết bị

nhỏ, mà kết quả dẫn đến việc tiêu thụ tài nguyên nhiều hơn thậm chí ngay cả

trong trạng thái thụ động. Bên cạnh đó, độ an toàn chỉ là một trong tính năng

của các thiết bị, nó không nên làm lu mờ các tính năng chính của thiết bị hướng

tới. Vì vậy, ta cần một lựa chọn thuật toán mã hóa phù hợp với nhu cầu và chức

năng của các thiết bị nhỏ gọn. Do đó, trong lựa chọn và đánh giá một hệ mật ta

cần phải xem xét hai yêu cầu quan trọng sau:

Về độ an toàn: Mục tiêu trong xây dựng các hệ mật là không quá yếu

và không với mục đích thay thế các thuật toán mã truyền thống khác nhưng

phải đủ an toàn, (tất nhiên không thể kháng lại được các đối phương có đủ mọi

điều kiện), và có chi phí cài đặt thấp. Tóm lại, ta cần có một hệ mật không phải

tốt nhất nhưng phải đạt được độ cân bằng giữa chi phí cài đặt, hiệu suất và độ

an toàn để phù hợp với các thiết bị có tài nguyên hạn chế. Tuy nhiên, đây là bài

toán khó đối với nhà thiết kế vì các tiêu chí này không tỉ lệ thuận với nhau. Với

một mã pháp an toàn khi cài đặt trên phần cứng để đạt hiệu suất cao thì phải sử

dụng kiến trúc FPGA, chống lại các kênh kề, tuy nhiên, điều này lại trả giá bằng

yêu cầu về diện tích mạch lớn (đồng nghĩa là chi phí cao). Ngược lại, nếu tập

trung vào thiết kế một mã pháp an toàn, có cài đặt phần cứng nhỏ thì dẫn tới

hiệu suất bị giảm.

 Chiến lược thiết kế mã khối

Thuật toán mã khối chuyển đổi các khối bit riêng lẻ có chiều dài n đặc

trưng cho dòng thông tin cần mã hóa (bản rõ - Plaintext) thành các khối bit

tương ứng có cùng độ dài biểu diễn dòng thông tin đã mã (bản mã), tùy thuộc

vào tham số K cũng là một dãy bit (khóa riêng) có độ dài k. Biến đổi trên có thể

trình bày theo biểu diễn toán học:

(1.1)

Cần lưu ý rằng, ánh xạ này là một ánh xạ hai chiều (nó có một ánh xạ nghịch

đảo Theo (1.1), các tham số hoạt động của mã khối là:

- Khối (Block) thông tin bản rõ X (trong trường hợp mã hoá) hoặc Khối

(Block) thông tin bản mã C (trong trường hợp giải mã) - có độ dài n-bit (thường

là 64 bit hoặc 128 bit),

- k-bit khóa riêng K.

Mã hóa và giải mã được thực hiện theo các bước sau:

- Lựa chọn khoá phiên K,

- Chia bản rõ plaintext (hoặc bản mã - ciphertext) thành các khối có chiều

dài n-bits cho trường hợp mã hóa, trong trường hợp giải

mã, (trong trường hợp khối cuối cùng có chiều dài nhỏ hơn độ dài cần thiết thì

bổ sung cho đủ độ dài),

- Mã hóa (giải mã) là thực hiện hàm cho từng khối (bock) bản rõ

-(trong trường hợp giải mã - cho mỗi khối bản mã) dựa trên việc sử

dụng một trong các chế độ hoạt động của mã khối

Sự bảo mật của mật mã khối được thực hiện không chỉ nhờ việc sử dụng

các khoá riêng, mà còn qua các hàm có sẵn phức tạp . Theo nguyên tắc

xây dựng thuật toán mã khối, thành phần chủ yếu của hàm là thực hiện

r lần (r là số vòng của thuật toán) biến đổi , với i = 1, 2, ..., r, được gọi là

hàm biến đổi vòng [5]. Do đó, hàm biến đổi vòng có r thông số dưới dạng các

bằng thuật toán đặc biệt để tạo ra các khóa khóa vòng ki thu được từ khoá

vòng. Hàm biến đổi vòng hoạt động dựa trên các khối đầu vào liên tiếp

tạo nên một dãy các phép tính đơn giản:

- Phi tuyến tính (được biểu diễn bởi Si) - thay thế dãy các bit của các khối

con của khối Xi bằng dãy các bit khác thường được gọi là các ô thay thế (Eng.

S-box),

- Tuyến tính (được ký hiệu Li) - phép hoán vị các bit của khối Xi.

Hàm là kết quả của tổng hợp nhiều chức năng của hàm - tập

con thích hợp của phép thay thế và hoán vị các bit trong các khối.

Tính bảo mật của mật mã khối phụ thuộc không chỉ vào các phép tính

được thực hiện trong lớp phi tuyến và hàm tuyến tính mà còn phụ thuộc vào

tham số tính toán của mã khối - đó là số vòng được thực hiện. Thuật toán được

thực hiện nhiều vòng hơn có nghĩa là độ bảo mật lớn hơn và thời gian thực hiện

các phép mã hóa và giải mã dữ liệu cũng dài hơn.

Sơ đồ cấu trúc chung của thuật toán mã khối được trình bày trong hình 1.1

Hình 1.1. Cấu trúc chung của thuật toán mã khối

Công tác nghiên cứu đánh giá thuật toán mã khối cần được tiến hành một

cách nghiêm túc, khoa học và liên tục, thường xuyên cập nhật thông tin và tiến

hành nghiên cứu nâng cao độ an toàn và hiệu năng của thuật toán là thách thức

lớn đối với công tác nghiên cứu khoa học công nghệ mật mã hiện nay.

1.2 Mã hoá bất đối xứng

Ý tưởng cơ bản của mật mã bất đối xứng được công bố năm 1976 bởi

Whitfield Diffie và Martin Hellman [95]. Theo ý tưởng này, mật mã không đối

xứng, còn được gọi là mật mã khoá công khai, sử dụng hai khóa khác nhau (trái

ngược với mật mã đối xứng), khóa bí mật được sử dụng để giải mã các bản mã,

và một khóa được sử dụng để mã hóa văn bản rõ, nhưng theo giả định của thuật

toán này thì không thể có được khóa này dựa trên các thông tin biết được của

khóa kia. Sự bảo mật của mã hóa bằng cách sử dụng mật mã phi đối xứng dựa

trên một trong những bài toán khó của lý thuyết số, thuộc về lớp các bài toán

NP-complete, như phân tích số lớn thành nhân số (mật mã RSA), hệ mật sử dụng

cơ chế cộng điểm trên đường cong Elliptic hoặc tính toán các thuật toán rời rạc

(thuật toán ElGamal) [5], [14].

1.2.1 Thuật toán mã hóa RSA

Thuật toán RSA là thuật toán mật mã phi đối xứng phổ biến nhất. Thuật

toán này được phát minh bởi Ron Rivest, Adi Shamir và Leonard Adleman năm

1977 [77]. Độ an toàn của hệ thống mật mã RSA dựa trên tính khó của bài toán

phân tích số nguyên lớn ra các thừa số nguyên tố. Hiện nay RSA là hệ thống

mật mã khóa công khai được dùng phổ biến trong các ứng dụng bảo mật thông

tin. Nó được sử dụng để cung cấp sự đảm bảo tính bí mật và các chữ ký số.

Trong thuật toán RSA, một cặp khóa (một khóa công khai và một khóa

bí mật) là một hàm của một cặp số nguyên tố lớn, do đó có được văn bản rõ

dựa trên một bản mã khi biết khoá công khai là tương tự như bài toán phân tích

ra nhân tử của tích các số nguyên tố được lựa chọn. Thuật toán RSA bao gồm

ba yếu tố liên quan:

• Thủ tục tạo cặp khóa,

• Thủ tục để mã hóa bản rõ (plaintext) sử dụng khóa công khai,

• Thủ tục để giải mã một bản mã sử dụng khóa bí mật.

Các thuật toán RSA có thể được cải tiến bằng cách sử dụng các phương

pháp và thuật toán nhất định trong lĩnh vực lý thuyết số, ví dụ phương pháp

cộng theo chuỗi [23], phương pháp Montgomery [75], thuật toán Barrett [72],

thuật toán Euclid [24], Định lý Fermat [14], định lý phần dư Trung Hoa [5],

[14], [23] hoặc thuật toán nhân Karacuba [65].

Nếu bài toán phân tích ra thừa số nguyên tố các số nguyên lớn là khó

(không tìm được thuật toán hiệu quả để giải) thì việc phá mã toàn bộ đối với

RSA không thể thực hiện được. Năm 2005, số lớn nhất có thể được phân tích

ra thừa số nguyên tố có độ dài 663 bít với phương pháp phân tán trong khi khóa

của RSA có độ dài từ 1024 tới 2048 bít. Một thiết bị lý thuyết có tên là TWIRL

do Shamir và Tromer mô tả năm 2003 đã đặt ra câu hỏi về độ an toàn của khóa

1024 bít. Vì vậy, hiện nay người ta khuyến cáo sử dụng khóa có độ dài tối thiểu

2048 bít.

Năm 1993, Peter Shor công bố thuật toán Shor chỉ ra rằng: máy tính

lượng tử (trên lý thuyết) có thể giải bài toán phân tích ra thừa số trong thời gian

đa thức. Tuy nhiên, máy tính lượng tử vẫn chưa thể phát triển được tới mức độ

này trong nhiều năm nữa.

Năm 2010, các nhà khoa học thuộc đại học Michigan đã công bố phát

hiện một kẽ hở trong hệ thống mật mã hoá RSA. Cách phá vỡ hệ thống, lấy

khóa bí mật RSA 1024 bit chỉ trong vài ngày thay vì vài năm nếu tấn công theo

cách thông thường - tấn công bằng brute force (dò tìm lần lượt). Các nhà khoa

học tạo một điện thế lớn để gây lỗi hệ thống, từ đó giúp tìm ra khoá bí mật.

Việc tấn công được thực hiện trên một FPGA. Báo cáo được trình bày tại hội

nghị DATE 2010 diễn ra tại Dresden, Đức tháng 3 năm 2010.

Các khuyến nghị về độ dài Modulus N, các điều kiện cần tuân thủ của

các tham số RSA (e, d, p, q) đã được đề cập trong các tiêu chuẩn của thế giới.

1.2.2 Thuật toán dựa trên đường cong Elliptic

Trong vài ba thập kỷ gần đây, đường cong elliptic đóng vai trò quan

trọng đối với lý thuyết số và mật mã. Vào những năm 1980, kỹ thuật đường

cong elliptic đã được phát triển cho bài toán phân tích số, kiểm tra tính nguyên

tố và ứng dụng trong mật mã khóa công khai. Sang thập kỷ 1990, đường cong

elliptic được sử dụng để chứng minh Định lý lớn Fermat. Lý do chính để hệ

mật đường cong elliptic ngày càng được sử dụng nhiều bởi vì chúng cung cấp

tính an toàn tương đương với các hệ mật khóa công khai cổ điển trong khi độ

dài khóa nhỏ hơn rất nhiều. Người ta đã ước lượng rằng cỡ khoá 3248 bit của

hệ mật RSA cho cùng một độ an toàn như 256 bit của hệ mật đường cong

elliptic [50]. Điều này có nghĩa là việc cài đặt các hệ mật đường cong elliptic

sử dụng tài nguyên hệ thống bé hơn, năng lượng tiêu thụ ít hơn.... Việc sinh

một khoá RSA 512 bit mất khoảng 4 phút, trong khi sinh một khoá ECDSA

163 bit mất có 0,597 giây. Mặc dù một số thủ tục, chẳng hạn như việc kiểm tra

chữ ký số, là nhanh hơn không đáng kể đối với RSA, nhưng với ưu thế về độ

dài khóa nhỏ, hệ mật Elliptic đang dần thay thế RSA, trở thành một trong những

hệ mật khóa công khai được ứng dụng rộng rãi.

Đường cong Elliptic là một trường hợp đặc biệt của phương trình

Diophant. Lý thuyết về đường cong Elliptic (EC) rất phong phú và đồ sộ. Trong

nghiên cứu của mình tác giả Serge Lang đã phát biểu về phương diện học thuật:

“Có thể viết vô tận về đường cong Elliptic” [50].

Với ý nghĩa to lớn cả về thực tiễn và học thuật, EC là nền tảng toán học

quan trọng trong đại số hiện đại cũng như lý thuyết mật mã hiện đại. EC cũng

là nền tảng quan trọng trong chính phủ điện tử và thương mại điện tử. Chính vì

những điều này mà “Hệ mật mã khóa công khai dựa trên đường cong Elliptic”

được lựa chọn để trình bày một phần trong luận án. Ngoài ra, cơ sở toán học

của đường cong Elliptic cũng sẽ là nền tảng chủ yếu mà luận án sẽ sử dụng để

phát triển các phương pháp trao đổi khóa và xây dựng thuật toán mới, hiệu quả

nhân nhanh đa thức với hệ số nguyên sử dụng biến đổi Fourier nhanh. Các cặp

song tuyến tính, cũng như hệ mật định danh cũng đều dựa trên nền tảng toán

học của đường cong Elliptic. Hệ mật này cũng sẽ được sử dụng trong luận án.

1.3 Tình hình nghiên cứu trong và ngoài nước đối với việc nâng cao hiệu

năng một số thuật toán mã hóa

1.3.1 Tình hình nghiên cứu ngoài nước

Để tăng độ an toàn và bảo mật các thông tin được mã hóa truyền trên

kênh thông tin công cộng, người ta đưa ra nhiều thuật toán mật mã, với độ mật

và độ dài khóa ngày càng cao như: DES, TripleDES, IDEA, AES, RC5,

Blowfish, mật mã khóa công khai RSA, hệ mật trên đường cong Elliptic như:

“A Signature Scheme Based on Implicit and Explicid Certificates Against k-

Traitors Conllusion Attack” (Tomasz Hyla, JerzyPejas, 2017 tại Hội nghị IFIP

International Conference on Computer Information Systems and Industrial

Managment), “Variantions to the cryptographic alogirhtms AES and TwoFish”

(Freyre P., DíazN., https://eprint.iacr.org, 2019)….

Để xây dựng được một mã khối vừa hiệu quả và đủ an toàn thì bài toán

nghiên cứu cho xây dựng thành phần mật mã như S-hộp và tầng tuyến tính là

cấp thiết. Gần đây, các nhà thiết kế mã khối trên thế giới đã đưa ra nhiều phương

pháp và kết quả lý thuyết lẫn thực hành để giải quyết bài toán này. Đối với

thành phần phi tuyến S-hộp, có thể kể tới các công trình nghiên cứu các S-hộp

4-bit của: Liu Bozhong, Zheng Gong,... (2011) “On the security of 4-bit

involutive S-boxes for lightweight designs”. (Information Security Practice

and Experience. Springer, 247-256) và Zhang Wentao, Zhenzhen Bao,...(2015)

“A New Classification of 4-bit Optimal S-boxes and its Application to

PRESENT, RECTANGLE and SPONGENT”. International Workshop on Fast

Software Encryption. Springer... Đối với phương pháp xây dựng tầng tuyến

tính dựa trên các ma trận MDS thường được sử dụng do tầng tuyến tính nhận

được có tính khuếch tán tối ưu nhưng mặt cài đặt của nó lại có gặp những khó

khăn nhất định do sự hạn chế của tài nguyên thiết bị.

Đối với các mã pháp dạng AES, tầng tuyến tính bao gồm phép biến đổi

AES ShiftRows và phép biến đổi AES MixColumns. Trong đó ShiftRow là một

hoán vị các từ của trạng thái và MixColumns là phép nhân ma trận với một cột

của trạng thái và cũng là phép tính phức tạp tiêu tốn nhiều thời gian trong tầng

tuyến tính ví dụ: Зензин, О. and М. Иванов, “Стардарт криптографической

защиты-AES”. Конечные поля. 2002: КУДРИЦ-ОБРАЗ М..

Trong tầng tuyến tính của AES, ma trận MDS sử dụng là một ma trận

vòng được lựa chọn kỹ lưỡng trên cơ sở đảm bảo độ an toàn và khả năng cài

đặt. Tuy nhiên theo đánh giá trên quan điểm điểm bất động của tác giả Z’aba

M. R. [3] “Analysis of linear relationships in block ciphers”. Luận án tiến sĩ

của Queensland University of Technology, 2010. thì tầng khuếch tán này lại

có 216 điểm bất động, tác giả chỉ ra sự tương quan tỷ lệ nghịch giữa độ khuếch

tán và số điểm bất động đó là càng nhiều điểm bất động thì độ khuếch tán càng

thấp, điều này ảnh hưởng trực tiếp đến tính an toàn của thuật toán mã khối.

Mặt khác, do hạn chế năng lực của các thiết bị tính toán, thiết bị xử lý

mật dữ liệu… mà để tăng độ mật dữ liệu được mã hóa, người ta đưa ra các hệ

mật khác nhau với độ dài khóa mã ngày càng tăng. Điều đó dẫn đến thời gian

cần thiết để mã hóa và giải mã dữ liệu kéo dài (tăng theo), độ phức tạp tính toán

cũng tăng theo... trong khi yêu cầu trong an ninh - quốc phòng và trong bảo mật

thông tin kinh tế - xã hội đòi hỏi phải: bí mật, nhanh chóng, chính xác, an toàn,

hiệu quả và tiện dụng…. Vì vậy, nghiên cứu để nâng cao hiệu năng của một số

thuật toán mật mã ứng dụng trong mã hóa và giải mã dữ liệu… trong giai đoạn

hiện nay là một nội dung có tính thời sự, khoa học và có ý nghĩa thực tiễn.

Để nâng cao hiệu năng của một số thuật toán mật mã, trên thế giới người

ta đã đề xuất nhiều biện pháp khác nhau như: cứng hóa các thuật toán mật mã

bằng cách ứng dụng hệ thống vi mạch có thể lập trình (FPGA) hoặc (ASICs)…

nhằm tăng tốc độ của mã hóa và giải mã của thuật toán cụ thể (ví dụ. DES,

IDEA, AES, RSA), trong số những công trình này [4], [20],...

Trong một số công trình nghiên cứu về khả năng cài đặt cứng hóa trên

FPGA đối với AES như Elbirt, A.J., et al., “An FPGA-based performance

evaluation of the AES block cipher candidate algorithm finalists. Very Large

Scale Integration (VLSI) Systems”, IEEE Transactions on, 9(4); p. 545-557 và

Chodowiec, P. and K. Gaj, “Very compact FPGA implementation of the AES

algorithm”, in Cryptographic Hardware and Embedded Systems-CHES,

Springer. p. 319-333 thì các phương pháp cài đặt tầng tuyến tính chủ yếu dựa

trực tiếp trên phép nhân với các hằng số của ma trận trong biến đổi MixColumns.

Mặc dù các hằng số của ma trận này được lựa chọn để dễ dàng cài đặt, tuy nhiên

phép nhân trực tiếp khi cứng hóa là chưa tối ưu và chưa đưa ra được một đánh

giá trực quan về chiều sâu thiết kế của mạch phần cứng nhận được.

Công trình của Sim, S.M.,... “Lightweight MDS Involution Matrices”. in

FSE. 2015. nhóm tác giả đã đề xuất một số ma trận MDS và MDS cuộn có dạng

Hadamrd hiệu quả trong cài đặt phần cứng. Các tác giả đã đưa ra số cổng XOR

cần thiết đối với mỗi một ma trận đề xuất, tuy nhiên những đánh giá cho tài

nguyên cài đặt phần cứng của nhóm tác giả này chưa đưa ra chiều sâu thiết kế

(số xung nhịp), đây là yếu tố có ảnh hưởng trực tiếp đến tốc độ xử lý của mạch

phần cứng. Hơn nữa tầng tuyến tính mà mã pháp dạng AES sử dụng ma trận

MDS Hadamard cuộn lại có nhiều điểm bất động.

Ngoài thực hiện thiết kế phần cứng cho máy tính tuần tự truyền thống

cũng đang triển khai ứng dụng phần cứng chuyên dụng có thể sử dụng nhiều

bộ xử lý [25]. Tuy nhiên, do hạn chế của các phần cứng chuyên dụng nên các

kết quả đạt được nhằm nâng cao hiệu năng tính toán (cả về độ mật và tốc độ

tính toán mã hóa và giải mã…) vẫn còn hạn chế.

Sự phát triển năng động của công nghệ phần cứng, đáng tiếc là không

thể trực tiếp làm tăng được một cách đáng kể tốc độ mã hóa và giải mã các

thông tin, vì các thuật toán mã hóa hiện đang sử dụng được thiết kế điển hình

theo các thuật toán tuần tự do các giải pháp công nghệ trước đây. Ban đầu người

ta chỉ nhằm mục tiêu cứng hóa (DES),.... và do đó chưa sử dụng hết công suất

của máy tính. Vì vậy, cần nghiên cứu xây dựng, cải tiến các hệ mật, các thuật

toán, các phần mềm chuyên dụng… nhằm nâng cao hiệu suất thực hiện các

thuật toán mã hóa, giải mã... đáp ứng nhu cầu bảo mật thông tin với một dung

lượng tin mật cao, trong thời gian thực… phục vụ cho chỉ đạo, chỉ huy trong

lĩnh vực An ninh - Quốc phòng và lĩnh vực Kinh tế - Xã hội có tính cấp thiết

và ý nghĩa khoa học, thực tiễn cao. Đó cũng là một trong những lý do mà nghiên

cứu sinh đề xuất nội dung nghiên cứu này.

1.3.2 Tình hình nghiên cứu trong nước

Trong nước cũng đã có nhiều đề tài nghiên cứu nhằm tăng độ an toàn

hệ mật như các đề tài:

Công trình “Nghiên cứu, xây dựng giải pháp tích hợp mật mã vào

quá trình truyền tin đảm bảo an toàn thông tin trên mạng máy tính”,

(LATS-2017-Học viện Công nghệ Bưu chính Viễn thông-Nguyễn Ngọc

Điệp) đã nghiên cứu đề xuất 02 ma trận tuyến tính có tính chất mật mã tốt

để cải tiến tầng tuyến tính của các mã pháp dạng AES. Xây dựng mã khối trên

cơ sở mã pháp dạng AES kính thước khối 128 bit, kích thước khóa 256 bit với

ma trận MDS tựa vòng. Tuy nhiên hướng nghiên cứu phát triển luận án ghi rõ

cần tiếp tục nghiên cứu phát triển các thành tố mật mã mới theo hướng đảm bảo

an toàn và hiệu quả trong các môi trường sử dụng và ứng dụng ma trận đã đề

xuất vào cài đặt phần cứng cụ thể đối với mã pháp tựa AES để có thể đánh giá

chính xác hơn ảnh hưởng của tầng tuyến tính đề xuất.

Công trình “Hệ tiêu chuẩn tham số an toàn cho hệ mật RSA và ứng

dụng” (LATS-2011-VNCKH và CNQS-Hoàng Văn Thức), “Nghiên cứu

phương pháp tự động bảo mật tín hiệu tiếng nói trong mạng truyền thông”,

(LATSKT-2009,HVKTQS-Đặng Vũ Hoàng),

Công trình “Nghiên cứu xây dựng tiêu chuẩn an toàn cho tham số hệ

mật Elliptic và ứng dụng” (LATS-2011-VNCKH và CNQS-Nguyễn Quốc

Toàn) nhằm giải quyết bài toán xây dựng và đưa ra tiêu chuẩn an toàn cho

hệ mật Elliptic đáp ứng nhu cầu bảo mật cho lĩnh vực kinh tế xã hội và an

ninh quốc phòng, Đã đề xuất về mặt định lượng cho 05 tiêu chuẩn đã có:

tiêu chuẩn EC1 về ngưỡng an toàn, tiêu chuẩn EC2 về độ dài khóa, tiêu

chuẩn EC3 về độ dài modulo, tiêu chuẩn EC5 về điều kiện MOV, tiêu chuẩn

EC6 về ước của bậc nhóm. Tuy nhiên luận án tập trung nâng cao độ an toàn

của thuật toán mà chưa chú trong đến hiệu năng thực hiện và cách thức cài

đặt vào mạng thông tin mật mã cụ thể.

“Nghiên cứu xây dựng một số dạng lược đồ mới cho chữ ký số tập

thể”, (LATSTH-2017, VKH và CNQS-Đặng Minh Tuấn) đã đề xuất 03 lược

đồ: chữ ký số tập thể đa thành phần dựa trên hệ mật trên đường cong elliptic

và chữ ký số tập thể đa thành phần dựa trên bài toán logarithm rời rạc; chữ

ký số tập thể đa thành phần dựa trên cặp song song tuyến tính...Tuy nhiên

luận án tập trung vào nội dung nâng cao độ an toàn của các thuật toán đề

xuất, chưa giải quyết vấn đề hiệu năng các lược đồ chữ ký số đề xuất (về

tốc độ tính toán và tài nguyên sử dụng...)

“Xây dựng lược đồ chữ ký số an toàn từ các lược đồ định danh” (Võ

Tùng Linh, Tạp chí An toàn thông tin, Vol 08, N02,2018), “Giải mã mềm

cho mã khối dựa trên không gian mã đối ngẫu” (LATSKTĐT-2019,

HVKTQS-Nguyễn Thị Hồng Nhung)…, tuy nhiên các công trình nghiên

cứu mang tính khoa học, đề xuất giải pháp..., thuật toán thực nghiệm có

tính minh chứng cho giải pháp đề xuất...

Một số công trình khác tập trung nghiên cứu cứng hóa các thuật toán

mật mã. Tuy nhiên do các phần cứng chuyên dụng phải nhập ngoại, công

cụ để cứng hóa hạn chế. Sự hạn chế dung lượng bộ nhớ, tốc độ của phần

cứng chuyên dụng… nên kết quả đạt được chưa cao. Một số kết quả bảo

mật thuộc lĩnh vực An ninh - Quốc phòng ở cả trong nước và trên thế giới

thì được bảo mật và không công bố,… Vì vậy hướng nghiên cứu nâng cao

hiệu năng của một số thuật toán mật mã bằng phương pháp hiệu quả tạo các

tham số an toàn và song song hóa các thuật toán mã hóa lựa chọn, vẫn là

một hướng nghiên cứu mang tính thời sự và có tính cấp thiết, khoa học, có

ý nghĩa thực tiễn.

1.3.3 Một số vấn đề tồn tại và hướng nghiên cứu phát triển

Để đảm bảo thông tin phục vụ cho chỉ đạo, chỉ huy dùng trong An ninh

– Quốc phòng và trong lĩnh vực Kinh tế - Xã hội được bí mật, nhanh chóng,

chính xác đòi hỏi các thuật toán mã hóa nói chung (và thuật toán mã khối và hệ

mật dựa trên đường cong elliptic... nói riêng) vừa phải chú trong nâng cao độ

an toàn của thuật toán vừa phải cài đặt, tích hợp được trong môi trường có tài

nguyên hợp lý và có hiệu năng tính toán cao.

Về các mã khối được sử dụng trong nước đòi hỏi có độ an toàn và bảo

mật cao. Hiện nay, các thuật toán mã khối được khuyến nghị sử dụng thường

là chuẩn của nước ngoài như mã hóa dữ liệu AES, TripleDES, chuẩn mã hóa

Châu Âu Camellia, … và chưa có những hệ mã khối nào được xây dựng trong

nước hướng tới các thiết bị tính toán hạn chế. Các kết quả nghiên cứu như đã

trình bày (trong phần 1.4) thường tập trung xây dựng các hệ mã khối có độ an

toàn cao, được xây dựng tầng tuyến tính dựa trên các ma trận khả tách có

khoảng cách cực đại MDS (ví dụ: Nguyễn Ngọc Điệp (2016) "Một đề xuất ma

trận MDS 4x4 an toàn, hiệu quả cho tầng tuyến tính của các mã pháp dạng

AES". Tạp chí Nghiên cứu Khoa học và Công nghệ Quân sự, Số 46/12-2016,

tr. 133-142). tuy nhiên các kết quả này mới nói chung thường quan tâm nhiều

về tính an toàn cho mã khối và chưa phù hợp để xây dựng mã khối cho môi

trường có tài nguyên hạn chế, hay nâng cao hiệu năng thuật toán. Do đó, cần

xây dựng, đánh giá và chọn lựa lại các thành phần mật mã nhằm để xây dựng

một hệ mã mã khối an toàn và hiệu năng cao. Vì vậy phần tiếp theo luận án

định hướng xây dựng các thuật toán mã khối theo mô hình SPN với lý do sau:

- Do mô hình này đạt độ an toàn chứng minh được đối với nhiều phương

pháp thám mã, điển hình là mã khối AES.

- Có hiệu năng thực thi cũng như chi phí cài đặt đạt hiệu quả cao.

- Hơn nữa, mô hình mã pháp dạng SPN cho phép người thiết kế thuận

lợi cho việc định hướng xây dựng các thành phần mật mã bên trong vì có các

phân tích cơ sở rõ ràng và chi tiết.

Về Hệ mật trên đường cong elliptic: Năm1985 Neal Koblitz và Victor

Miller đưa ra những công bố về hệ mật dựa trên đường cong Elliptic (Elliptic

Curve Cryptography - ECC), từ đó hệ mật dựa trên ECC đã được các nhà khoa

học quan tâm nghiên cứu, triển khai ứng dụng thực tế, đặc biệt là trong giai

đoạn phát triển mạng thông tin IoT. Với cùng một mức độ bảo mật như nhau

so với RSA nhưng hệ mật dựa trên ECC yêu cầu độ dài khóa ngắn hơn nhiều

(Jagdish Bhatta and Lok Prakash Pandey, “Perfomance Evaluation of RSA

Variants and Elliptic Curve Cryptography on Handheld Devices

International”, Journal of Computer Science and Network Security, VOL. 11

No. 11, November 2011). Việc nghiên cứu mở rộng ứng dụng hệ mật trên ECC

trong các hệ thống thông tin mật khác nhau và trong việc xây dựng các lược đồ

chữ ký số cũng đang được đẩy mạnh. Nhằm đáp ứng các nhu cầu mở rộng ứng

dụng ECC nêu trên, hàng loạt các nghiên cứu, cải tiến hệ mật dựa trên đường

cong Elliptic đã được triển khai trong thời gian vừa qua. Để ứng dụng hệ mật

dựa trên đường cong Elliptic cho mỗi hệ thống bao giờ bên gửi và bên nhận

thông tin phải thống nhất được đường cong Elliptic sẽ sử dụng, có nghĩa là cần

phải xác định các tham số phù hợp của đường cong, sau đó mới đến tạo đường

cong Elliptic đạt mức bảo mật xác định. Theo các công bố của Viện Tiêu chuẩn

quốc gia Hoa Kỳ miền tham số của đường cong Elliptic có thể kiểm tra được

với các đặc điểm về khả năng tự bảo vệ (các tham số có thể chọn theo

ANSIX962). Cách lựa chọn miền tham số cho đường cong Elliptic hiện tại đang

được áp dụng theo phương pháp lặp ngẫu nhiên và đếm số điểm trên đường

cong tương ứng cho đến khi tìm được các tham số thích hợp (American

National Standards Institute. “Public Key Cryptography for the Financial

Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)”,

http://webstore.ansi.org/ansidocstore). Do tầm quan trọng và tính thời sự của

Hệ mật dựa trên đường cong elliptic, nên có nhiều công trình nghiên cứu về nội

dung này. Tuy nhiên các công trình tập trung vào nội dung nâng cao độ an toàn

của các thuật toán đề xuất, chưa quan tâm giải quyết vấn đề hiệu năng các thuật

toán đề xuất (về tốc độ tính toán và tài nguyên sử dụng...) cũng như khả năng

cài đặt và triển khai thực tế.

Vì vậy Luận án sẽ tập trung vào việc phân tích và phát triển một thuật

toán mới, nhân nhanh các đa thức với hệ số nguyên, dựa trên Định lý Phần dư

Trung Hoa (CRT) và Biến đổi Fourier nhanh (FFT). Thuật toán này là cơ bản

trong quá trình tạo tham số hiệu quả cho các hệ thống sử dụng Thuật toán chữ

ký số dựa trên đường cong Elliptic (ECDSA - Elliptic Curve Digital Signature

Algorithm) và giao thức trao đổi khóa Diffie Hellman trên đường cong elliptic

(ECDH). Kết quả thu được cho phép nâng cao hiệu quả quá trình tạo đường

cong elipttic bằng cách tính toán song song. Phương pháp được đề xuất là sử

dụng định lý phần dư Trung hoa (CRT) để biểu diễn các số nguyên dưới dạng

chuỗi hữu hạn của các số có kích thước nhỏ, và sau đó song song hóa các phép

tính trên các biểu diễn đó. Mặt khác, để tăng tốc độ tính toán trên đa thức người

ta dùng phép biến đổi Fourier nhanh. Phương pháp được đề xuất có thể được

sử dụng để tăng tốc độ tính toán của đa thức và chuỗi lũy thừa với hệ số nguyên.

Tóm lại, một nội dung quan trọng của luận án là thiết kế một thuật toán song

song, hiệu quả để nhân các đa thức và chuỗi lũy thừa với nhờ sử dụng đồng

thời Định lý Phần dư Trung Hoa (CRT) và Biến đổi Fourier nhanh (FFT). Điều

này quan trọng quá trình tạo đường cong elliptic.

1.4 Kết luận chương 1

Trong chương này luận án đã trình bày tổng quan về thuật toán mã khối

và hệ mật dựa trên đường cong elliptic dùng trong bảo mật thông tin và tình

hình nghiên cứu trong và ngoài nước nhằm nâng cao hiệu năng một số thuật

toán mã hóa và định hướng nghiên cứu chuyên sâu gồm:

Mô hình cho mã khối được lựa chọn là mô hình có cấu trúc SPN, do đảm

bảo độ an toàn và hiệu quả cao, trong đó tầng phi tuyến sử dụng các S-hộp

4 bit và tầng tuyến tính được xây dựng dựa trên các ma trận MDS.

Xây dựng thuật toán mới, hiệu quả nhân nhanh đa thức với hệ số nguyên

sử dụng biến đổi Fourier nhanh (Fast Fourier Transform) và định lý phần dư

Trung Hoa và thực hiện thực tế thuật toán đề xuất trên các bộ vi xử lý 32-bit

hoặc 64-bit.

Vì phương pháp nâng cao hiệu năng của các thuật toán mã hóa là một lĩnh

vực rộng và phức tạp nên trong các chương tiếp của luận án tập trung nghiên cứu

giải pháp nâng cao hiệu năng của hệ mật dựa trên thuật toán mã hóa AES-256

và hệ mật dựa trên đường cong Elipptic… Đây là những hệ mật có tính thời sự,

đang được quan tâm đầu tư nghiên cứu cả trong nước và trên thế giới.

Chương 2

NÂNG CAO ĐỘ AN TOÀN VÀ HIỆU NĂNG CAO

THUẬT TOÁN MÃ HÓA AES

Chương 2 trình bày một số giải pháp nâng cao độ an toàn và hiệu năng

thuật toán mã hóa hệ mật AES, trên cơ sở xây dựng và lựa chọn ma trận MDS

mới có các tính chất mật mã tốt cho tầng khuếch tán, đồng thời lựa chọn một

số mô hình kiến trúc cứng hóa và sử dụng linh hoạt các nguồn tài nguyên phần

cứng; cũng như mô phỏng thực tế các giải pháp đề xuất trên công cụ ISIM của

ISE. Các kết quả đạt được cho phép khẳng định tính đúng đắn trong xây dựng

và lựa chọn ma trận MDS mới có các tính chất mật mã tốt cho tầng khuếch tán

cũng như cứng hóa các thuật toán mã hóa phức tạp để nâng cao độ an toàn và

hiệu năng thuật toán mã hóa hệ mật AES.

2.1 Một số khái niệm

Rijndael là một mã khối với độ dài khối và độ dài khoá đều có thể thay

đổi. Độ dài khối và độ dài khoá được gán một cách độc lập bằng bội của 32 bit,

với 128 bit là nhỏ nhất và 256 là lớn nhất. AES là một trường hợp riêng của

Rijndael. AES có độ dài khối bằng 128 bit và hỗ trợ các độ dài khoá bằng 128,

192 hay 256 bit.

Đầu vào và đầu ra của Rijndael được xem như là các mảng một chiều

của các byte có 8 bit. Đối với phép mã, đầu vào là khối rõ (plaintext block) và

khoá (key), và đầu ra là bản mã (ciphertext block). Đối với phép giải mã, đầu

vào là khối mã và khoá, đầu ra là khối rõ. Biến đổi vòng của Rijndael, và các

bước của nó, thao tác trên một kết quả trung gian, được gọi là trạng thái (state).

Trạng thái có thể được vẽ như là một mảng chữ nhật các byte, với 4 dòng. Số

các cột trong trạng thái được ký hiệu bởi Nb và bằng độ dài khối chia cho 32

(đối với AES thì Nb bằng 4). Giả sử khối rõ được ký hiệu bởi:

ký hiệu byte cuối cùng của khối với p0 ký hiệu byte đầu tiên, và

bản rõ.

Tương tự, khối bản mã có thể được ký hiệu bởi:

Giả sử trạng thái được ký hiệu bởi:

với ai,j ký hiệu byte ở tại dòng i và cột j. Các byte đầu vào được ánh xạ

thành các byte trạng thái theo thứ tự a0,0, a1,0, a2,0, a3,0, a0,1, a1,1, a2,1, a3,1, ...

Đối với phép mã, đầu vào là khối rõ và ánh xạ là

Đối với phép giải mã, đầu vào là bản mã và ánh xạ là

Tại điểm kết thúc của phép mã, bản mã được lấy ra từ trạng thái bằng

cách lấy các byte trạng thái theo thứ tự:

Tại điểm kết thúc của phép giải mã, khối rõ được lấy ra từ trạng thái

theo cách:

Tương tự, khoá được ánh xạ thành khoá mã 2-chiều. Khoá mã được vẽ

như một mảng chữ nhật với 4 dòng tương tự như trạng thái. Số các cột của khoá

mã được ký hiệu bởi Nk và bằng độ dài khoá chia cho 32. Các byte của khoá

được ánh xạ thành các byte của khoá mã theo thứ tự: k0,0, k1,0, k2,0, k3,0, k0,1, k1,1,

k2,1, k3,1, k0,2, .... Nếu chúng ta ký hiệu khoá bởi

thì

Biểu diễn của trạng thái và khoá mã và các ánh xạ bản rõ-trạng thái,

khoá-khoá mã (key- cipher key) được minh hoạ ở hình 2.1.

p0 p4 p8 p12 k0 k4 k8 k12 k16 k20

p1 p5 p9 p13 k1 k5 k9 k13 k17 k21

p2 p6 p10 p14 k2 k6 k10 k14 k18 k22

p3 p7 p11 p15 k3 k7 k11 k15 k19 k23

Hình 2.1. Cách bố trí của trạng thái và khoá mã cho trường hợp Nb= 4 và Nk

Cấu Trúc Của Rijdael

Ba tiêu chuẩn thiết kế được tính đến trong thiết kế của Rijndael là như sau:

 Có khả năng chống lại tất cả các tấn công đã biết;

 Tốc độ và tính gọn của mã lệnh trên một miền rộng của các kiến trúc

(platform)

 Tính đơn giản của thiết kế

Rijndael là một mã khối lặp bằng cách áp dụng lặp một ánh xạ vòng trên

trạng thái. Số các vòng được ký hiệu bởi Nr và phụ thuộc vào độ dài khối và độ

dài khoá. Các lựa chọn cụ thể cho các tầng khác nhau một phần lớn dựa trên

việc áp dụng của Chiến lược vệt lan rộng, đó là một phương pháp thiết kế đảm

bảo tính kháng cự chống lại phân tích vi sai và tuyến tính.

Phép mã của Rijndael bao gồm phép cộng khoá ban đầu, được ký hiệu bởi

AddRoundKey, sau đó là Nr-1 lần áp dụng biến đổi Round, và cuối cùng là một

lần áp dụng FinalRound. Phép cộng khoá ban đầu và mỗi vòng nhận đầu vào là

State và khoá vòng. Khoá vòng cho vòng i được ký hiệu bởi ExpandedKey[i],

còn ExpandedKey[0] ký hiệu đầu vào của phép cộng khoá ban đầu. Việc nhận

được ExpandedKey từ CipherKey được ký hiệu bởi KeyExpansion. Mô tả mức

cao của Rijndael ở dạng giả mã-C được cho sau đây.

Rijndael(State, CipherKey)

{

KeyExpansion(CipherKey, ExpandedKey);

AddRoundKey(State, ExpandedKey[0]);

For (i = 1; i < Nr; i++) Round(State, ExpandedKey[i]);

FinalRound(State, ExpandedKey[Nr]);

}

Trước vòng đầu tiên, tầng cộng khoá được áp dụng. Để làm cho chính

phép mã hóa và phép giải mã tương tự về mặt cấu trúc, tầng trộn tuyến tính của

vòng cuối cùng là khác với tầng trộn tuyến tính trong các vòng khác.

2.2 Thuật toán AES

Sự phát triển của kỹ thuật mã thám tiên tiến đặt cho các nhà thiết kế thuật

toán mã mật mới những đòi hỏi độ an toàn mật mã cao và phải đáp ứng các

điều kiện: hiệu năng mã hóa cao, có thể cứng hóa module mật mã, làm việc

thích ứng trong môi trường đặc biệt. Các dữ liệu được truyền trong mạng truyền

thông ngày càng dễ dàng bị chặn thu và gây nhiễu. Một số mạng được cấu trúc

với các phần tử có tài nguyên hạn chế làm cho chúng rất dễ bị tổn thương với

các loại tấn công khác nhau liên quan đến việc truy cập trái phép thông tin hoặc

ngăn chặn hoạt động từng bộ phận của mạng (tấn công từ chối dịch vụ [54]).

Trong những ứng dụng tiềm năng (quân sự, chính phủ điện tử, điều khiển các

quá trình công nghiệp,...) thì tính mở, quy mô, và khả năng truyền dẫn, tính an

toàn của thông tin được tạo ra và truyền dẫn trong mạng cần được xem xét, cân

nhắc khi thiết kế mạng.

Năm 1997, NIST (National Institute of Standards and Technology) đã mở

một cuộc thi dành cho các thiết kế cải tiến thuật toán mã khối với khóa mã đối

xứng. Kết quả chọn được thuật toán Rijandel, một thuật toán mã do hai người

Bỉ (Joan Daemen và Vincent Rijmen) đề xuất [41],[42], là thuật toán có tốc độ

mã hóa và giải mã nhanh nhất. Thuật toán này được NIST lựa chọn và trở thành

tiêu chuẩn Quốc gia, gọi là Chuẩn mã hóa dữ liệu tiên tiến AES. Đây là chuẩn

mã khối được xây dựng trên cơ sở cấu trúc mạng thay thế hoán vị (SPN) với kích

thước khối là 128 bit. Mỗi khối đầu vào được biểu diễn dưới dạng ma trận 4x4

trên trường 𝔽28. Cấu trúc tổng thể của AES được mô tả như trong hình 2.2.

Hình 2.2. Cấu trúc tổng thể của thuật toán AES

Tuy nhiên, thuật toán AES cũng có những nhược điểm nhất định về độ an toàn: chẳng hạn như tầng khuếch tán có số điểm bất động lớn (tồn tại 216

điểm bất động), và còn có thể cải thiện được hiệu năng khi thực hiện bằng phần

cứng chuyên dụng. Phần này trình bày giải pháp nâng cao độ an toàn của thuật

toán mã hóa AES (Advanced Encryption Standards) dựa trên việc cải tiến tầng

khuếch tán và một số kiến trúc, thực thi cứng hóa hệ thống mã hóa và giải mã

thuật toán AES-256 trên các vi mạch chuyên dụng để nâng cao hiệu năng thuật

toán cả về tài nguyên và thời gian tính toán.

2.3 Nâng cao độ an toàn và hiệu năng cao thuật toán AES

2.3.1 Sự khuyếch tán trong tầng biến đổi tuyến tính của mã khối có cấu

trúc SPN

Ma trận MDS (Maximum Distance Separable matrix) là ma trận sinh

của mã tách có khoảng cách cực được ứng dụng nhiều trong mã khối và hàm

băm vì nó đảm bảo tính khuếch tán tốt.

Định nghĩa 1. Cho K là một trường hữu hạn và 𝑝, 𝑞 là hai số nguyên. Giả sử 𝑓: 𝑥 → 𝑀 × 𝑥 là một ánh xạ từ 𝐾𝑝 vào 𝐾𝑞 được xác định bởi ma trận

𝑀 kích cỡ 𝑞 × 𝑝. Chúng ta nói rằng ánh xạ 𝑓 là một đa hoán vị tuyến tính hay

𝑀 là một ma trận MDS nếu tập tất cả các cặp (𝑥, 𝑀 × 𝑥) là một mã MDS, có

nghĩa là một mã tuyến tính có số chiều bằng 𝑝, độ dài là 𝑝 + 𝑞 và khoảng cách

tối thiểu là 𝑞 + 1.

Các ma trận MDS xuất phát từ lý thuyết mã với mã tách có khoảng cách

cực đại. Trong lý thuyết mã có hai định lý quan trọng về ma trận MDS sau đây:

Định lý 1 [83]. Nếu 𝐶 là một mã [𝑛, 𝑘, 𝑑] thì 𝑛 − 𝑘 ≥ 𝑑 − 1.

Những mã với 𝑛 − 𝑘 = 𝑑 − 1 (ℎ𝑎𝑦 𝑑 = 𝑛 − 𝑘 + 1), được gọi là mã tách

có khoảng cách cực đại, hay mã MDS.

Định lý 2 [83]. Một mã [𝑛, 𝑘, 𝑑] với ma trận sinh 𝐺 = [𝐼|𝑀] trong đó A

là một ma trận 𝑘 × (𝑛 − 𝑘) là MDS nếu và chỉ nếu mọi ma trận con vuông

(được tạo ra bởi i hàng bất kỳ và i cột bất kỳ, với 𝑖 = 1, 2, … , 𝑚𝑖𝑛 {𝑘, 𝑛 − 𝑘})

của M đều là ma trận không suy biến.

Từ định lý 2, ta có định nghĩa đơn giản về ma trận MDS là ma trận mà

mọi ma trận con vuông của nó đều không suy biến.

Theo Claude Shannon, xáo trộn và khuếch tán là hai thuộc tính bắt buộc

của một mã khối an toàn [83]. Các mã khối hiện đại được thiết kế chủ yếu dựa

trên hai nguyên lý đó và thường bao gồm hai tầng tương ứng là: tầng xáo trộn

thường được bảo đảm bởi thành phần hộp thế (S-box) phi tuyến, làm cho mối

quan hệ của sự độc lập thống kê giữa xâu bản mã và sự độc lập thống kê của

xâu bản rõ trở nên phức tạp hơn, trong khi tầng khuếch tán thường được bảo

đảm bởi phép biến đổi tuyến tính, gắn với sự phụ thuộc của các bit đầu ra với

các bit đầu vào.

Thuật toán AES được thiết kế theo cấu trúc SPN, với tầng khuếch tán là

sự kết hợp của 2 phép biến đổi gồm ShiftRows và MixCollums. Trong đó, phép

biến đổi MixCollums là một phép biến đổi tuyến tính.

Phép biến đổi đổi tuyến tính trong mạng SPN ở mã khối là một thành phần

quan trọng. Biến đổi này cung cấp tính khuếch tán bằng cách khuếch tán sự xáo

trộn các bit của khối đầu vào cố định và tạo ra khối đầu ra tương ứng có kích thước

không đổi và được đặc trưng bởi số nhánh. Số nhánh là số lượng nhỏ nhất các S-

hộp tích cực của 2 vòng mã hóa liên tiếp nhau [96]. Số lượng này được sử dụng

để ước lượng khả năng kháng lại tấn công vi sai [26] và tuyến tính [8] lên mã khối.

Ngoài đặc trưng số nhánh, theo Muhammat [68], số điểm bất động cũng là một

tính chất mật mã quan trọng, bổ sung cho tính khuếch tán của một biến đổi tuyến

𝑑 → 𝔽2𝑛

tính. Sau đây, chúng ta sẽ xem xét hai khái niệm này:

𝑑×𝑑

Số nhánh của phép biến đổi tuyến tính: Giả sử 𝐿 là ánh xạ tuyến tính hoạt 𝑑 với 𝑍 = (𝑍0, 𝑍1, … , 𝑍𝑑−1)𝑇 động trên các vectơ từ (mỗi từ n bít) 𝐿: 𝔽2𝑛 là vectơ cột đầu vào, còn 𝑋 = (𝑋0, 𝑋1, … , 𝑋𝑑−1)𝑇 là vectơ cột đầu ra của ánh là ma trận không suy biến trên trường 𝔽2𝑛, xạ này, định nghĩa 𝑀 = [𝑚𝑖,𝑗]

ma trận này biểu diễn biến đổi tuyến tính 𝐿, khi đó:

(2.1)

Gọi Γ𝑍 = (Γ𝑍0, Γ𝑍1, … , Γ𝑍𝑑−1, ) là ký hiệu một véc tơ nhị phân có chiều dài d, ở đây Γ𝑍𝑖 = 1 khi 𝑍𝑖 ≠ 0 còn bằng 0 trong trường hợp còn lại. Ký hiệu 𝑤𝑡(Γ𝑍) là trọng số Hamming của Γ𝑍. Khi đó số nhánh của biến đổi tuyến tính

𝐿 ký hiệu là 𝐵(𝐿) chính là số lượng nhỏ nhất các S-hộp tích cực trong 2 vòng

mã liên tiếp nào đó. Số nhánh được tính như sau:

(2.2) 𝐵(𝐿) = min{𝑤𝑡(Γ𝑍) + 𝑤𝑡(Γ𝑋): 𝑍 ≠ 0, 𝑋 = 𝐿(𝑍)}

ở đây, 𝐵(𝐿) ≤ 𝑑 + 1.

Số nhánh của biến đổi tuyến tính 𝐿 tối ưu là bằng 𝑑 + 1 và mã tuyến tính

trong trường hợp này có khoảng cách nhỏ nhất cực đại (gọi là mã MDS). Như

vậy, nếu phép biến đổi tuyến tính với một ma trận MDS thì phép biến đổi tuyến

tính đó sẽ đảm bảo độ khuếch tán cực đại.

Phép biến đổi tuyến tính MixCollums của thuật toán AES sử dụng một

ma trận MDS kích thước 4 x 4 nên số nhánh của tầng biến đổi tuyến tính tương

ứng là bằng 5.

Điểm bất động của tầng khuếch tán trong mã khối: Khái niệm điểm bất

𝑑 nếu 𝑋 =

động của một biến đổi tuyến tính trong mã khối lần đầu tiên được xem xét trong

𝑑 → 𝔽2𝑛

𝑑 , có nghĩa là giá trị của nó không thay đổi dưới tác động của biến

[42]. Theo đó 𝑋 là điểm bất động của biến đổi tuyến tính 𝐿: 𝔽2𝑛

𝑑 luôn có thể được biểu

𝑑 → 𝔽2𝑛

𝐿(𝑋), 𝑋 ∈ 𝔽2𝑛

đổi tuyến tính này. Một biến đổi tuyến tính 𝐿: 𝔽2𝑛 diễn bởi một ma trận không suy biến 𝑀 có kích thước 𝑑 × 𝑑, các phần tử của

ma trận này thuộc trường 𝔽2𝑛. Như vậy, số lượng điểm bất động của biến đổi

tuyến tính trên chính là số nghiệm của hệ phương trình:

(2.3) (𝑀 − 𝐼)𝑋 = 0

trong đó 𝐼 là ma trận đơn vị kích thước 𝑑 × 𝑑. Từ đó số lượng điểm bất

động cho biến đổi tuyến tính nói trên được tính theo công thức sau:

(2.4)

𝑁𝐿 = 2𝑛(𝑟𝑎𝑛𝑘(𝑀)−𝑟𝑎𝑛𝑘(𝑀−𝐼)) = 2𝑛(𝑑−𝑟𝑎𝑛𝑘(𝑀−𝐼) Do đó, số lượng các điểm bất động phụ thuộc vào hạng của ma trận 𝑀 − 𝐼.

Đối với thuật toán AES, tầng khuếch tán là sự kết hợp của hai phép toán

ShiftRows và MixCollums:

Biến đổi 𝐿0 - ShiftRows là phép dịch vòng các byte

Biến đổi 𝐿1- MixCollums là phép nhân với ma trận MDS trên 𝔽28, 𝑋 = 𝑀𝑍, trong đó Z là khối đầu vào, X là khối đầu ra và 𝑀 là ma trận MDS kích

thước 4x4:

Cả hai biến đổi tuyến tính 𝐿0 và 𝐿1 này có thể biểu diễn dưới dạng phép nhân một ma trận A kích thước 16x16 với một cột. Trong [68] tác giả đã tính

được ma trận 𝐴 cỡ 16 × 16 biểu diễn cho tầng khuếch tán của AES (bao gồm

ShiffRows và MixColumns), có dạng sau:

[ 2 0 0 0 0 0 0 1 0 0 1 0 0 3 0 0 1 0 0 0 0 0 0 1 0 0 3 0 0 2 0 0 1 0 0 0 0 0 0 3 0 0 2 0 0 1 0 0 3 0 0 0 0 0 0 2 0 0 1 0 0 1 0 0 0 3 0 0 2 0 0 0 0 0 0 1 0 0 1 0 0 2 0 0 1 0 0 0 0 0 0 1 0 0 3 0 0 1 0 0 1 0 0 0 0 0 0 3 0 0 2 0 0 1 0 0 3 0 0 0 0 0 0 2 0 0 1 0 0 0 1 0 0 3 0 0 2 0 0 0 0 0 0 1 0 0 3 0 0 2 0 0 1 0 0 0 0 0 0 1 0 0 2 0 0 1 0 0 1 0 0 0 0 0 0 3 0 0 1 0 0 1 0 0 3 0 0 0 0 0 0 2 0 0 0 1 0 0 1 0 0 3 0 0 2 0 0 0 0 0 0 1 0 0 3 0 0 2 0 0 1 0 0 0 0 0 0 3 0 0 2 0 0 1 0 0 1 0 0 0 0 0 0 2 0 0 1 0 0 1 0 0 3 0 0 0]

Tuy nhiên, theo tính toán của luận án, ma trận 𝐴 có dạng chính xác

như sau:

[ 2 0 0 0 0 3 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 2 0 0 0 0 3 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 2 0 0 0 0 3 3 0 0 0 0 1 0 0 0 0 1 0 0 0 0 2 0 0 0 1 2 0 0 0 0 3 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 2 0 0 0 0 3 0 0 0 0 3 1 0 0 0 0 1 0 0 0 0 2 0 0 0 0 2 3 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 2 0 0 0 0 3 0 0 0 0 3 0 0 0 0 1 1 0 0 0 0 2 0 0 0 0 2 0 0 0 0 3 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 2 3 0 0 0 0 1 0 0 0 3 0 0 0 0 1 0 0 0 0 1 2 0 0 0 0 2 0 0 0 0 3 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 2 0 0 0 0 3 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 2 3 0 0 0 ]

Sau khi tính hạng của các ma trận ta nhận được 𝑟𝑎𝑛𝑘(𝐴) = 16. Ma trận

𝐴 − 𝐼, với 𝐼 là ma trận đơn vị kích thước 16 x 16, phép “−“ ở đây là phép XOR,

nên

𝐴 − 𝐼 =

𝟑 0 0 0 0 3 0 0 0 0 1 0 0 0 0 1 1 𝟏 0 0 0 2 0 0 0 0 3 0 0 0 0 1 1 0 𝟏 0 0 1 0 0 0 0 2 0 0 0 0 3 3 0 0 𝟏 0 1 0 0 0 0 1 0 0 0 0 2 0 0 0 1 𝟑 0 0 0 0 3 0 0 0 0 1 0 0 0 0 1 1 𝟏 0 0 0 2 0 0 0 0 3 0 0 0 0 3 1 0 𝟏 0 0 1 0 0 0 0 2 0 0 0 0 2 3 0 0 𝟏 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 𝟑 0 0 0 0 3 0 0 0 0 3 0 0 0 0 1 1 𝟏 0 0 0 2 0 0 0 0 2 0 0 0 0 3 1 0 𝟏 0 0 1 0 0 0 0 1 0 0 0 0 2 3 0 0 𝟏 0 1 0 0 0 3 0 0 0 0 1 0 0 0 0 1 𝟑 0 0 0 0 2 0 0 0 0 3 0 0 0 0 1 1 𝟏 0 0 0 1 0 0 0 0 2 0 0 0 0 3 1 0 𝟏 0 0 1 0 0 0 0 1 0 0 0 0 2 3 0 0 𝟏 ] [

Tính được 𝑟𝑎𝑛𝑘(𝐴 − 𝐼) = 14. Số điểm bất động đối với tầng khuếch tán

của AES theo (2.4) là 𝑁𝐴 = 28(16−14) = 216. Rõ ràng tầng khuếch tán của AES có số điểm bất động khá lớn. Thuật toán này đề xuất lựa chọn ma trận MDS khác

cho phép biến đổi tuyến tính giảm bớt số điểm bất động của tầng khuếch tán để

nâng cao độ an toàn của thuật toán AES.

2.3.2 Giải pháp nâng cao độ an toàn của thuật toán AES

Trong phần trước đã trình bày một số tính chất mật mã quan trọng của

tầng khuếch tán trong mã khối, phân tích các tính chất đó đối với tầng khuếch

tán của thuật toán mật mã AES. Kết quả phân tích cho thấy, tầng khuếch tán

của AES có số nhánh không cao (bằng 5) và số điểm bất động nhiều (bằng 216).

Tất nhiên ngoài các tiêu chí yêu cầu về số nhánh cao, số điểm bất động ít, còn

có các tiêu chí khác cần xem xét, chẳng hạn như tiêu chí về tốc độ thực hiện và

chi phí cài đặt. Như vậy để nâng cao độ an toàn của thuật toán AES, chúng ta

có thể cải tiến ma trận MDS để tăng số nhánh, hoặc giảm số điểm bất động,

hoặc vừa tăng số nhánh và giảm số điểm bất động. Để tăng số nhánh, chúng ta

có thể sử dụng một ma trận MDS kích thước lớn hơn, tối đa cỡ 16x16. Khi đó

số nhánh cực đại sẽ được tăng lên, tối đa bằng 17. Tuy nhiên khi tăng kích

thước của ma trận MDS thì cũng làm tăng chi phí cài đặt và ảnh hưởng đến tốc

độ mã hóa/giải mã.

Vì vậy, luận án đề xuất giải pháp lựa chọn một ma trận MDS mới nhằm

giảm đáng kể số điểm bất động, trong khi không làm tăng quá nhiều chi phí cài

đặt và đặc biệt không làm giảm nhiều tốc độ thực thi của thuật toán AES. Nghĩa

là có sự cân bằng giữa độ an toàn và chi phí, tốc độ thực thi.

Như chúng ta đã biết, có nhiều phương pháp để xây dựng ma trận MDS

[46], [73], [97]. Tuy nhiên, việc xây dựng ma trận MDS sao cho tầng khuếch

tán có chi phí thực thi thấp vẫn là một vấn đề khó đối với các nhà thiết kế. Ý

tưởng về một ma trận tựa vòng có nhiều phần tử bằng 1 và giá trị của các phần

tử là nhỏ, số phần tử khác nhau ít nhằm tăng tốc độ và giảm chi phí thực thi là

một ý tưởng được nhiều người quan tâm. Chi tiết về phương pháp xây dựng ma

trận MDS tựa vòng hiệu quả có thể tìm đọc trong các tài liệu chuyên sâu [46],

[73], [97]. Sau đây luận án sẽ trình bày tóm lược về phương pháp này.

Các tiêu chí thiết kế ma trận MDS được các tác giả trong [73], [96] đề

cập là:

- Có nhiều nhất số lượng phần tử có giá trị bằng 1 (ký hiệu số lượng này

là 𝑣1).

- Số lượng ít nhất các phần tử khác nhau trong ma trận (ký hiệu số lượng

này là 𝑐).

- Các phần tử của ma trận có trọng số Hamming thấp nhằm tối thiểu hóa

chi phí thực thi (ký hiệu trọng số này là H). Giá trị H càng thấp thì số phép

XOR và số biến tạm cần sử dụng sẽ càng ít.

Dựa trên các tiêu chí đó, các tác giả đã xây dựng các ma trận MDS có

chi phí thực thi thấp dựa trên các mảng song chính quy (bi-regular). Họ cho

rằng cách xây dựng như vậy sẽ tạo ra các ma trận tối ưu theo nghĩa số các phép

XOR, các biến tạm và bảng tra là nhỏ nhất. Các giá trị tối ưu cho 𝑣1 và 𝑐 đối

với một ma trận cỡ 𝑞 × 𝑝 được các tác giả xác định qua Bảng 2.1 và Bảng 2.2.

Bảng 2.1. Các giá trị của cq,p

4 5 6 7 3 2 8

2 3 3 3 2 2 3 2

3 3 3 3 2 2 4 3

3 3 4 4 3 2 4 4

3 3 4 4 3 3 4 5

4 4 4 4 3 3 5 6

4 4 4 4 3 3 5 7

4 4 5 5 4 3 5 8

Tuy nhiên, trong công trình này, các tác giả mới chỉ xây dựng được các

𝑞,𝑝

ma trận MDS cỡ 4 × 4 và 8 × 8 tối ưu một phần: hoặc theo 𝑣1, hoặc theo 𝑐. Bên cạnh đó, ma trận nghịch đảo của các ma trận này chưa chắc đã tối ưu.

Bảng 2.2. Các giá trị của 𝑣1 7 4 2 5 3 6 8

4 3 5 6 7 8 9 2

6 4 7 8 9 10 11 3

7 5 9 10 12 13 14 4

8 6 10 12 13 14 17 5

9 7 12 13 16 18 19 6

8 10 13 14 18 21 22 7

9 11 14 17 19 22 24 8

Cũng theo hướng xây dựng trên, các tác giả trong [46] đã đề xuất và đưa

ra một số kết quả về các ma trận MDS kiểu “ma trận tựa vòng” (circulant

matrix). Có 2 kiểu ma trận tựa vòng được định nghĩa như sau.

Định nghĩa 2.1 (Ma trận tựa vòng Kiểu-I).

Ma trận 𝑑 × 𝑑 dạng sau:

] 𝟏 𝑎 [ 𝟏𝑇 𝐴

được gọi là ma trận tựa vòng Kiểu-I, với 𝐴 = 𝐶𝑖𝑟𝑐(1, 𝑎1, … , 𝑎𝑑−2), , 1 là phần tử đơn vị, và phần tử 𝑎𝑖 và 𝑎 là những phần tử khác 𝟏 = (1, … ,1) ⏟ 𝑑−1 𝑙ầ𝑛

0 và khác 1 bất kì của trường cơ sở. Ma trận này được kí hiệu là

𝐾𝑖ể𝑢_𝐼(𝑎, 𝐶𝑖𝑟𝑐(1, 𝑎1, … , 𝑎𝑑−2)) .

Ở đây, 𝐶𝑖𝑟𝑐(𝑎0, 𝑎1, … , 𝑎𝑑−1) là ký hiệu của một ma trận vòng () cỡ 𝑑 ×

𝑑, có dạng sau:

]

𝑎0 𝑎1 ⋯ 𝑎𝑑−1 𝑎𝑑−1 𝑎0 ⋯ 𝑎𝑑−2 [ ⋮ ⋮ ⋮ ⋮ 𝑎1 𝑎2 ⋯ 𝑎0

Ma trận tựa vòng kiểu-I có đặc điểm thú vị là số lượng các phần tử khác

nhau trong ma trận là nhỏ (thường bằng kích cỡ của ma trận), số lượng số 1

trong ma trận là khá cao, ngoài ra nghịch đảo của nó cũng có dạng tương tự

như nó. Dạng nghịch đảo này được định nghĩa như sau:

Định nghĩa 2.2 (Ma trận tựa vòng Gần_Kiểu-I).

Ma trận 𝑑 × 𝑑 dạng sau:

[ ] 𝑎 𝒃 𝒃𝑇 𝐴

được gọi là Ma trận tựa vòng Gần_Kiểu-I, với 𝐴 = 𝐶𝑖𝑟𝑐(𝑎0, 𝑎1, … , 𝑎𝑑−2),

, và 𝑎, 𝑏 và phần tử 𝑎𝑖 là những phần tử bất kì của trường cơ sở. 𝒃 = (𝑏, … , 𝑏) ⏟ 𝑑−1 𝑙ầ𝑛

Ma trận này được kí hiệu là: 𝐺ầ𝑛_𝐾𝑖ể𝑢_𝐼(𝑎, 𝑏, 𝐶𝑖𝑟𝑐(𝑎0, … , 𝑎𝑑−2)).

Các tác giả còn đề xuất một kiểu ma trận tựa vòng khác gọi là ma trận

tựa vòng Kiểu-II, có khả năng tự nghịch đảo, phù hợp cho các mạng SPN.

Định nghĩa 2.3 (Ma trận tựa vòng Kiểu-II).

Ma trận 2𝑑 × 2𝑑 dạng sau:

] [ 𝐴 𝐴3 + 𝐴 𝐴−1 𝐴

được gọi là ma trận tựa vòng Kiểu-II, với 𝐴 = 𝐶𝑖𝑟𝑐(𝑎0, … , 𝑎𝑑−1) và

được kí hiệu là 𝐾𝑖ể𝑢_𝐼𝐼(𝐶𝑖𝑟𝑐(𝑎0, … , 𝑎𝑑−1)).

Theo đó, trong [46] các tác giả đã tìm được một số ma trận tựa vòng

kiểu-I cỡ 4 × 4, 8 × 8, và một số ma trận tựa vòng kiểu-II cỡ 6 × 6.

Ma trận MDS trong thuật toán AES được xây dựng có dạng tựa vòng và

hướng đến các tiêu chí như vậy. Trong phần này, luận án ứng dụng phương

pháp xây dựng ma trận tựa vòng [46], [97] để xây dựng một ma trận MDS tựa

vòng mới kích thước 4 x 4 và có chi phí thực thi tương đương với ma trận MDS

của AES, nhưng ma trận MDS tựa vòng mới này tạo ra tầng khuếch tán với số

điểm bất động bằng 1, đó chính là điểm 0 tầm thường.

Đây là một số thuộc tính mật mã tốt muốn có của các ma trận tựa vòng

MDS. Những dạng ma trận nào thỏa mãn được những thuộc tính trên sẽ được

phân tích, lựa chọn phương pháp xây dựng các ma trận đó. Để có các ma trận

tựa vòng, chương trình tìm kiếm ma trận MDS tựa vòng cỡ 4 x 4 được xây

dựng, mẫu ma trận được sử dụng có dạng như sau:

Các phần tử 𝑎, 𝑏, 𝑐, 𝑑 được chọn bất kỳ trong trường 𝐺𝐹(28). Ứng với 8

đa thức nguyên thủy bậc 8 để xây dựng, chương trình cho phép tìm kiếm được 32 ma trận MDS tựa vòng 4x4. Ứng với đa thức nguyên thủy là x8 + x6 + x5 +

x3 + 1 chương trình tìm được 4 ma trận MDS tựa vòng theo dạng trên,

danh sách 4 ma trận này được trình bày như trong bảng 2.3

Bảng 2.3. Danh sách ma trận MDS tựa vòng 4x4

[ ] [ ]

08 01 01 01 01 08 01 0A 01 01 0A 08 01 0A 08 01 01 01 0C 05 01 0C 05 01 05 01 01 01 01 05 01 0C

[ [ ]

01 01 10 1D ] 32 10 1D 32 01 01 65 20 49 65 20 49

(𝑣1 = 9, 𝑐 = 3, 𝐻 = 4) 1D 01 01 32 01 1D 01 10 (𝑣1 = 6, 𝑐 = 5, 𝐻 = 8) (𝑣1 = 9, 𝑐 = 3, 𝐻 = 6) 20 01 01 49 01 20 01 65 (𝑣1 = 6, 𝑐 = 4, 𝐻 = 10)

Sau đó luận án tiến hành đánh giá (theo tiêu chí nhiều số 1 nhất - 𝑣1 và

có ít phần tử khác nhau nhất - 𝑐, trọng số Hamming của các phần tử thấp nhất

- 𝐻) và lựa chọn được ma trận MDS tựa vòng như sau:

] 𝑀𝑛𝑒𝑤 = [

0x08 0x01 0x01 0x01 0x01 0x01 0x0A 0x08 0x01 0x08 0x01 0x0A 0x01 0x0A 0x08 0x01 Do ma trận này có nhiều số 1 nhất 𝑣1 = 9, có ít phần tử khác nhau nhất

𝑐 = 3, trọng số Hamming bé nhất 𝐻 = 4 (phần tử 0𝑥08 có 1 bít 1 do đó trọng

số Hamming là 1, tương tự ta có 0𝑥01 có trọng số Haming là 1 và phần tử

0𝑥0𝐴 có trọng số Hamming là 2. Vì vậy, tổng trọng số Hamming của các phần

tử là H=4).

Xem xét ma trận MDS của AES

[ ]

0x02 0x03 0x01 0x01 0x01 0x02 0x03 0x01 0x01 0x01 0x02 0x03 0x03 0x01 0x01 0x02

có thể tính được 𝑣1 = 8, 𝑐 = 3, 𝐻 = 4

Ma trận MDS tựa vòng 𝑀𝑛𝑒𝑤 ở trên được luận án đề xuất ứng dụng vào

cải tiến thuật toán AES.

Ma trận nghịch đảo tương ứng dùng cho quá trình giải mã của thuật

−1 = [

toán là:

] 𝑀𝑛𝑒𝑤

0x1A 0xD1 0xD1 0xD1 0xD1 0xCE 0x5B 0x02 0xD1 0x02 0x01 0x0A 0xD1 0x5B 0x02 0xCE

Ứng dụng ma trận MDS 𝑀𝑛𝑒𝑤 này vào thuật toán AES và tiến hành đánh

giá tầng khuếch tán mới theo cách tương tự như trong phần 2 ở trên. Kết quả

đánh giá cho thấy số điểm bất động của tầng khuếch tán mới có số điểm bất

động là 20(chính là điểm 0 tầm thường), trong khi đó với thuật toán AES gốc

(sử dụng ma trận MDS gốc) có số điểm bất động như đã đánh giá ở trên là 216

điểm. Tức là đã giảm đi được 216 − 1 điểm (tương ứng đã giảm đi được cỡ

99%) , đây là số điểm bất động tối ưu nhất mà một tầng khuếch tán của mã khối

luôn mong muốn đạt được. Như vậy số điểm bất động của thuật toán AES cải

tiến (là thuật toán AES sử dụng ma trận MDS mới 𝑀𝑛𝑒𝑤 mà luận án đề xuất ở

trên) được giảm đi đáng kể so với số điểm bất động của thuật toán AES gốc (sử

dụng ma trận MDS gốc), trong khi xét về chi phí thực thi (thông qua các tiêu

chí 𝑣1, 𝑐, 𝐻) là tương đương nhau, tức là chi phí thực thi sẽ không bị giảm đi

đáng kể (trong khi về mặt độ an toàn thì số điểm bất động càng ít thì độ an toàn

càng cao, với ma trận MDS mới của luận án đề xuất thì tầng khuếch tán mới

chỉ tồn tại 01 điểm bất động duy nhất, ứng với trường hợp đầu vào X = 0 nên

𝐴 ∗ 𝑋 = 0).

Để đảm bảo hiệu năng của thuật toán AES cải tiến với ma trận MDS mới

này. Trong phần tiếp theo, luận án sẽ trình bày một số giải pháp thực thi cứng

hóa hiệu quả.

2.3.3 Nâng cao hiệu năng của thuật toán AES cải tiến với ma trận MDS mới

Kiến trúc cho module thực hiện thuật toán mã khối có thể chia ra mấy

nhóm chính: kiến trúc lặp, kiến trúc kết hợp, đường ống toàn phần, kiến trúc lai

ghép. Người thiết kế sẽ căn cứ vào các yếu tố sau: độ mật, tốc độ mã hóa, tài

nguyên tính toán, tính hiệu quả, môi trường ứng dụng để lựa chọn kiến trúc

phần cứng cho các module mật mã. Sau đây là một số kiến trúc của module mật

mã được đề xuất và thực thi nhằm nâng cao hiệu năng của thuật toán mã hóa

AES-256.

a. Kiến trúc đường ống toàn phần

Từ nguyên lý hoạt động của thuật toán mã khối AES cải tiến được trình

bày, luận án đã thiết kế và thực hiện cứng hóa thuật toán AES-256 cải tiến theo

kiến trúc mô hình đường ống toàn phần như hình 2.3.

Hình 2.3. Mô hình kiến trúc mã khối AES-256 theo kiến trúc đường ống (Rõ - Bản rõ; Mã - Bản mã)

Hình 2.4 Cấu trúc một module Encryption

Hình 2.5. Cấu trúc module Encryption 14

Đối với kiến trúc đường ống toàn phần, 14 vòng lặp trong quá trình mã

hóa AES cải tiến được thực hiện riêng rẽ trên 14 module Encryption. Trong

đó, mỗi một module Encryption gồm các hàm xử lý: Add_Round_Key cộng

module 2 giữa dữ liệu Ri và khóa con Ki , phép biến đổi Subbyte theo bảng thế

1 với các giá trị Sbox, thực hiện phép biến đổi dịch vòng Shift_Row, thực hiện

phép biến đổi Mixcolumn. Riêng module "Encryption14" không thực hiện

phép biến đổi Mixcolumn.

Toàn bộ kiến trúc của mô hình giống một “ống nước”. Sau khi dữ liệu

đầu vào sẽ đi qua lần lượt 14 module Encryption, cho kết quả đầu ra mã hóa.

Với mô hình này yêu cầu lượng tài nguyên rất lớn (do cần lượng tài nguyên đủ

cho 14 module riêng rẽ), nhưng bù lại tốc độ xử lý rất cao; sau 14 chu kỳ clock

đầu tiên, cứ một nhịp clock sẽ có một khối dữ liệu 128-bit đã được mã hóa ở

đầu ra. Thuật toán AES-256 cải tiến thực hiện theo mô hình đường ống toàn

phần đạt tốc độ mã hóa/giải mã cao nhất, tuy nhiên tài nguyên sử dụng cho mô

hình này lớn.

Kết quả đạt được khi thiết kế tổng hợp core trên chip FPGA với tần số

hoạt động 100 Mhz. Core mã hóa AES hoạt động được với tần số tối đa 1008,827

Mhz. Nếu ta cung cấp được tối đa tần số hoạt động cho core mã hóa AES thì tốc

độ mã hóa lớn nhất của core AES có thể đạt đây

là tốc độ mã hóa rất cao có thể đáp ứng đầy đủ các ứng dụng hiện nay. Kết quả

quá trình thực thi thiết kế cứng hóa trên FPGA mô hình kiến trúc đường ống toàn

phần (hình 2.7).

Hình 2.6. Sơ đồ nguyên lý RTL và Tần số hoạt động core AES-256

theo kiến trúc đường ống toàn phần

Kết quả kiểm tra mô phỏng AES-256 cải tiến theo kiến trúc đường ống

toàn phần trên công cụ ISIM của ISE:

Để kiểm tra tính đúng đắn của mô hình đề xuất, luận án đã thực nghiệm

mô phỏng trên bộ công cụ ISIM của ISE như sau:

Khối dữ liệu đầu vào và khóa được lấy theo tài liệu chuẩn Fips.197

Bản rõ đầu vào, khóa và bản mã đầu ra:

Data_in = 128'h 00112233445566778899aabbccddeeff

Key_in = 256'h000102030405060708090a0b0c0d0e0f1

01112131415161718191a1b1c1d1e1f

Data_out = 128'h 8ea2b7ca516745bfeafc49904b496089

Thời gian tính toán bắt đầu khi tín hiệu start = 1'b1; kết thúc khi tín hiệu

Done_aes = 1'b1;

Dựa vào kết quả mô phỏng trên công cụ ISIM ta thấy thời gian thực hiện

quá trình mã hóa trong 1 chu kỳ clock.

Hình 2.7. Kết quả thực hiện AES-256 theo mô hình kiến trúc

đường ống toàn phần trên công cụ ISIM

Hình 2.8. Tài nguyên thiết kế AES-256 cải tiến

theo kiến trúc đường ống toàn phần

b. Mô hình kiến trúc lặp

Thuật toán mã khối AES-256 cải tiến theo mô hình kiến trúc lặp sử dụng

duy nhất block Encryption 1 khi đó kết quả đầu ra được lặp lại 13 vòng, cuối

cùng dữ liệu được đưa tới khối Encrypt_14 ta có bản mã đầu ra 128 bit. Quá

trình hoạt động của core AES cải tiến thiết kế theo kiến trúc lặp được thực hiện

thông qua máy trạng thái trong khối điều khiển. Dựa trên nguyên tắc này, mô

hình kiến trúc lặp chỉ sử dụng tài nguyên thực hiện đủ cho một vòng xử lý, sau

đó kết quả đầu ra lại được đưa trở lại thành đầu vào của vòng tiếp theo. Như

vậy với mô hình này tài nguyên sử dụng để cứng hóa thuật toán được rút gọn

đi tối đa và đồng nghĩa với tốc độ của thuật toán giảm đi 14 lần so với mô hình

đường ống toàn phần. Tuy nhiên tốc độ thực hiện của mô hình này trên thực tế

thường vẫn rất cao. Tần số tổng hợp tối đa core AES cứng hóa theo mô hình

kiến trúc lặp là 358,641 Mhz. Nếu ta đáp ứng tối đa tần số hoạt động cho core

thì tốc độ mã hóa lớn nhất của core có thể thực hiện được là

. Kết quả quá trình thực thi thiết kế cứng hóa

trên FPGA mô hình kiến trúc lặp (hình 2.11).

Hình 2.9. Mô hình kiến trúc mã khối AES-256 cải tiến theo kiến trúc lặp (Rõ - Bản rõ; Mã - Bản mã)

Hình 2.10. Sơ đồ nguyên lý RTL và Tần số hoạt động core AES-256

cải tiến theo kiến trúc lặp

Kết quả kiểm tra mô phỏng trên công cụ ISIM của ISE:

Khối dữ liệu đầu vào và khóa được lấy theo tài liệu chuẩn Fips.197

Bản rõ đầu vào, khóa, bản mã đầu ra:

Data_in = 128'h00112233445566778899aabbccddeeff

Key_in = 256'h000102030405060708090a0b0c0d0e0f1

01112131415161718191a1b1c1d1e1f

Data_out = 128'h 8ea2b7ca516745bfeafc49904b496089Thời gian tính

toán bắt đầu khi tín hiệu start = 1'b1; kết thúc khi tín hiệu Done_aes = 1'b1;

Dựa vào kết quả mô phỏng trên công cụ ISIM ta thấy thời gian thực hiện

quá trình mã hóa trong 14 chu kỳ clock.

Hình 2.11. Kết quả mô phỏng kiến trúc mã khối AES-256

cải tiến theo kiến trúc lặp trên công cụ ISIM

Hình 2.12. Tài nguyên thiết kế core AES-256 cải tiến theo kiến trúc lặp

c. Kiến trúc lai ghép

Mô hình kiến trúc lai ghép dựa trên ý tưởng chia nhỏ số vòng lặp của

thuật toán ra thành từng phần, mỗi phần sẽ đảm nhiệm thực thi một số vòng lặp

nhất định. Hình 2.13 là mô hình lai giữa mô hình đường ống toàn phần và mô

hình kiến trúc lặp.

Hình 2.13. Mô hình mã khối AES-256 cải tiến theo kiến trúc lai ghép (Rõ - Bản rõ; Mã - Bản mã)

Hình 2.14. Sơ đồ nguyên lý RTL và Tần số hoạt động core AES-256

cải tiến theo kiến trúc lai ghép

Với sơ đồ mô hình kiến trúc lai ghéo AES-256 cải tiến trên hình 2.14 là

mô hình đường ống 2 tầng, tầng thứ nhất thực hiện 7 vòng lặp của thuật toán

AES cải tiến trên một module mã hóa Encryption, sau đó chuyển dữ liệu đến

tầng thứ 2 của module mã hóa và tiếp tục nhận dữ liệu đầu vào mới ở tầng thứ

nhất. Như vậy chỉ cần sau 6 chu kỳ clock là có thể có dữ liệu đã mã hóa ở đầu

ra. Tốc độ của thuật toán được cải thiện tương đối so với mô hình rút gọn,

nhưng bù lại lượng tài nguyên cũng phải tăng lên. Mô hình này, thích hợp với

các ứng dụng yêu cầu tốc độ cao. Tần số tổng hợp tối đa core AES cải tiến cứng

hóa theo mô hình kiến trúc lặp là: 354,427 Mhz. Nếu ta đáp ứng tối đa tần số

hoạt động cho core thì tốc độ mã hóa lớn nhất của core có thể thực hiện được

là . Kết quả quá trình thực thi thiết kế cứng hóa

trên FPGA mô hình kiến trúc lai ghép (hình 2.15).

Hình 2.15. Kết quả kiểm tra mô phỏng mã khối AES-256

cải tiến theo kiến trúc lai ghép trên công cụ ISIM

Kết quả kiểm tra mô phỏng mã khối AES-256 cải tiến theo kiến trúc lai

ghéptrên công cụ ISIM của ISE:

Khối dữ liệu đầu vào và khóa được lấy theo tài liệu chuẩn Fips.197

Bản rõ đầu vào, khóa, bản mã đầu ra:

Data_in = 128'h 00112233445566778899aabbccddeeff

Key_in = 256'h000102030405060708090a0b0c0d0e0f1

01112131415161718191a1b1c1d1e1f

Data_out = 128'h 8ea2b7ca516745bfeafc49904b496089

Thời gian tính toán bắt đầu khi tín hiệu start = 1'b1; kết thúc khi tín hiệu

Done_aes = 1'b1;

Dựa vào kết quả mô phỏng trên công cụ ISIM ta thấy thời gian thực hiện

quá trình mã hóa trong 4 chu kỳ clock.

Hình 2.16. Tài nguyên thiết kế mã khối AES-256

cải tiến theo kiến trúc lai ghép

d. Đánh giá kết quả thực thi 3 mô hình kiến trúc đề xuất

Để đánh giá kết quả thực thi 3 mô hình kiến trúc đề xuất luận án đã sử

dụng chip FPGA Zynq XC7Z045 -FFG900- Speed = -2 để thực thi cứng hóa

thuật toán AES-256 cải tiến theo 3 mô hình kiến trúc đề xuất và đạt được kết

quả sau:

Thời

Thông

Tài nguyên

Tần số

gian

lượng

thiết kế

hoạt động

Phương pháp

mã

cực đại

(number

lớn nhất

(clock)

(Gbps)

Slice LUT)

(Mhz)

Kiến trúc toàn phần (full pipeline)

9,01

12848

1008,827

Kiến trúc lai ghép (half full

6,48

5104

354,427

pipeline)

Kiến trúc lặp

3,28

4519

358,641

Bảng 2.4. Bảng tổng hợp đánh giá các phương pháp thiết kế.

Dựa vào bảng tổng hợp đánh giá, so sánh lựa chọn giữa các phương

pháp thiết kế ta thấy có sự tương quan giữa tốc độ thực hiện mã hóa của core

với tài nguyên thiết kế. Đối với phương án thực tế tối ưu về mặt năng lực

tính toán mà không yêu cầu về tài nguyên thiết kế thì ta có thể lựa chọn

phương án thiết kế theo mô hình kiến trúc đường ống toàn phần. Đối với

phương án tối ưu về mặt tài nguyên tính toán ta có thể thực hiện thiết kế theo

phương pháp lặp. Đối với những phương pháp yêu cầu về sự cân đối giữa tài

nguyên thiết kế với năng lực tính toán, ta nên chọn phương pháp thiết kế

kiến trúc lai ghép vừa tận dụng được về mặt tài nguyên và đảm bảo năng lực

tính toán.

2.4 Kết luận chương 2

Chương 2 trình bày một số giải pháp nâng cao độ an toàn và hiệu năng

thuật toán mã hóa hệ mật AES - 256, trên cơ sở xây dựng và lựa chọn ma trận

MDS mới có các tính chất mật mã tốt cho tầng khuếch tán, đồng thời lựa chọn

một số mô hình kiến trúc cứng hóa và sử dụng linh hoạt các nguồn tài nguyên

phần cứng; cũng như mô phỏng thực tế các giải pháp đề xuất trên công cụ ISIM

của ISE. Các kết quả đạt được cho phép khẳng định tính đúng đắn trong xây

dựng và lựa chọn ma trận MDS mới có các tính chất mật mã tốt cho tầng khuếch

tán cũng như cứng hóa các thuật toán mã hóa phức tạp để nâng cao độ an toàn

và hiệu năng thuật toán mã hóa hệ mật AES - 256.

Kết quả chính của chương 2 được công bố trong các công trình [CT2],

[CT3], và [CT7] trong danh mục các công trình khoa học đã công bố.

Chương 3

NÂNG CAO ĐỘ AN TOÀN VÀ HIỆU NĂNG THUẬT TOÁN MÃ HÓA

DỰA TRÊN ĐƯỜNG CONG ELLIPTIC

Chương 3 luận án tập trung nghiên cứu về đường cong elliptic và mật

mã dựa trên đường cong elliptic, đường cong Elliptic mạnh và cách tạo chúng;

cũng như phương pháp trao đổi khóa mã an toàn và những ứng dụng mới của

Hệ mật sử dụng cơ chế nhóm điểm trên đường cong Elliptic.

Phần cuối chương đề xuất ứng dụng thuật toán mới, hiệu quả nhân

nhanh đa thức với hệ số nguyên sử dụng biến đổi Fourier nhanh (Fast Fourier

Transform) và định lý phần dư Trung Hoa và thực hiện thực tế thuật toán đề

xuất. Các kết quả so sánh thời gian tính bằng thuật toán cổ điển với thời gian

thực hiện trên các bộ vi xử lý đa lõi (4 nhân) dựa trên biến đổi Fourier và định

lý phần dư Trung Hoa chỉ rõ ưu điểm của thuật toán đề xuất là tốc độ tính toán

dựa trên biến đổi Fourier và định lý phần dư Trung Hoa nhanh hơn rất nhiều

lần tốc độ tính toán bằng phương pháp cổ điển

3.1 Tổng quan về đường cong Elliptic

3.1.1 Cơ sở toán học

Định nghĩa 3.1: Một đường cong elliptic dạng Weierstrass đầy đủ là

tập tất cả các điểm với 3 toạ độ x, y, z thoả mãn phương trình:

(3.1)

với .

Đường cong có một điểm ở vô cực với hệ số z = 0, là điểm (0, 1, 0).

Điểm này được ký hiệu bởi . Để đơn giản và phù hợp với mục đích sử dụng

thực tế, ta chỉ xem xét  là một trường nguyên tố với . Khi đó

phương trình đường cong elliptic dạng Weierstrass rút gọn sẽ được biểu diễn

bởi phương trình:

(3.2)

Định nghĩa 3.2: Biệt thức của đường cong E được xác định bởi công thức:

(3.3)

Định nghĩa 3.3: Gọi . Một điểm

được gọi là điểm không kì dị nếu có ít nhất một trong hai đạo hàm hoặc

khác 0. Điều này có nghĩa là nếu cả hai đạo hàm này bằng 0 thì điểm P sẽ được

coi là điểm kì dị.

Định nghĩa 3.4: Đường cong elliptic E được coi là đường cong không

kì dị nếu tất cả các điểm của nó là không kì dị. Ngược lại, nếu có ít nhất một

điểm kì dị thì đường cong sẽ được coi là đường cong kì dị.

Ta dễ dàng chứng minh được rằng đa thức bậc ba có nghiệm

bội khi và chỉ khi (sử dụng công thức Cardano). Như vậy, một

đường cong được gọi là không kì dị khi và chỉ khi  0 (mod p).

Định nghĩa 3.5: Đại lượng j-bất biến của đường cong E khi  0 là:

(3.4)

Định nghĩa 3.6: Hai đường cong E và E xác định bởi phương trình

Weierstrass rút gọn với các biến số tương ứng là (x, y) và (x, y) được gọi là đẳng

cấu trên trường  nếu và chỉ nếu tồn tại các hằng số r, s, t và u * sao cho

khi thực hiện đổi biến thì E biến thành E.

Tính đẳng cấu là một quan hệ tương đương. Hai đường cong đẳng cấu sẽ

có giá trị j-bất biến bằng nhau [50]. Tuy nhiên, nếu ta làm việc với trường không

đóng đại số  thì có thể có hai đường cong elliptic có cùng j-bất biến nhưng

không thể biến đổi một đường cong trở thành đường cong còn lại nhờ các hàm

hữu tỷ với các hệ số trong . Có hai giá trị đặc biệt của j-bất biến là:

j = 0: Khi đó đường cong elliptic có dạng .

j = 1728: Đường cong elliptic có dạng .

Các đường cong với j = 0 và j = 1728 là dạng đặc biệt, chúng có các tự

đẳng cấu (tức là một song ánh đảm bảo tính đồng cấu từ đường cong vào chính

nó) khác với tự đẳng cấu đã xác định bởi (x, y) (x, - y) vốn là tự đẳng cấu của

một đường cong elliptic bất kì trong dạng Weierstrass.

có một tự đẳng cấu (x, y) (x, - y) với  là một căn bậc ba

không tầm thường của 1.

có tự đẳng cấu (x, y) (-x, iy), với .

Định nghĩa 3.7: Nếu hai đường cong elliptic khác nhau được xác định

trên một trường  có cùng một j - bất biến thì ta gọi chúng là “xoắn đôi” (twist)

của nhau.

Đường cong xoắn đôi với đường cong với j-bất biến là j có dạng:

(3.5)

Định nghĩa 3.8: Đường cong elliptic E định nghĩa trên được gọi là

đường cong siêu kì dị nếu không có điểm cấp p trên (nghĩa là ).

Mệnh đề 4.30 trong [50]phát biểu rằng E là siêu kì dị khi và chỉ khi

. Chú ý rằng định nghĩa siêu kì dị ở đây không liên quan đến

tính chất kì dị như trong định nghĩa 3.4.

Định nghĩa 3.9: Đường cong elliptic E định nghĩa trên thỏa mãn

được gọi là các đường cong bất quy tắc.

3.1.2 Nhóm các điểm của đường cong elliptic trên trường hữu hạn

Luật nhóm

Tập hợp tất cả các điểm (x, y) với x, y thoả mãn phương trình của

đường cong E và với một điểm  ở vô cực cùng với một phép toán cộng sẽ tạo

thành một nhóm, gọi là nhóm các điểm trên đường cong elliptic trong , ký

hiệu là E( ). Nhóm này được sử dụng để xây dựng nên hệ mật Elliptic.

Phép toán trên đường cong Elliptic

Phép cộng hai đi m: Cho hai điểm và phân biệt trên đường cong

elliptic E. Tổng của và , ký hiệu là , được định nghĩa như sau: Kẻ một

đường thẳng đi qua và . Đường thẳng này sẽ cắt E tại một điểm thứ 3, được

ký hiệu là . Tiếp tục kẻ đường thẳng đi qua và vuông góc với trục x, đường

thẳng này sẽ cắt E tại điểm thứ hai chính là điểm (xem hình 3.1).

-R

Hình 3.1. Phép cộng hai điểm trên EC

Phép nhân đôi một đi m: Cho là một điểm trên E. Nhân đôi điểm ,

ký hiệu là , được định nghĩa như sau: Kẻ qua một tiếp tuyến của

E, tiếp tuyến này cắt E tại điểm thứ hai, ký hiệu là . Kẻ đường thẳng đi qua

và vuông góc với trục x, đường thẳng này cắt E tại điểm thứ hai chính là .

Mệnh đề 3.1

Cho E là một đường cong elliptic xác định bởi phương trình

. Gọi và là các điểm trên E với

. Khi đó với được tính như sau:

1) (Công thức cộng điểm) Nếu , thì

, với (3.6)

Nếu nhưng thì .

2) (Công thức nhân đôi điểm) Nếu và , thì

. (3.7) với

Nếu và , thì .

Phép cộng điểm trên đường cong Elliptic E thỏa mãn các tính chất sau:

(1). Tính giao hoán: với mọi trên E.

(2). Tồn tại phần tử đơn vị: P +  = P với mọi P trên E.

(3). Tồn tại phần tử nghịch đảo: Với điểm P cho trước trên E,

tồn tại một điểm Ptrên E sao cho P + = . Điểm

thường được kí hiệu là -P.

(4). Tính kết hợp: .

Nói cách khác, các điểm trên E cùng với phép cộng điểm tạo thành một

nhóm abel với  như là phần tử đơn vị.

3.1.3 Nhân vô hướng của một điểm trên đường cong Elliptic

Với n ∈ N\{0} định nghĩa phép nhân vô hướng của điểm P nằm trên

đường cong E là phép cộng n lần chính bản thân điểm P:

Để tối ưu phép nhân vô hướng, có thể sử dụng phương pháp Nhân đôi-

và- cộng, đầu tiên biểu diễn số n dưới dạng:

với (3.8)

Không tồn tại phép nhân 2 điểm trên đường cong E, có nghĩa là không

tồn tại P×Q với P, Q ∈ E.

Không tồn tại thuật toán chia vô hướng Q : n. Biết rằng Q = nP, bài toán

tìm số n là bài toán Logarithm rời rạc.

Đây là bài toán khó, thông thường phải thử lần lượt phép

cộng điểm P, cho đến khi tổng bằng Q, tuy nhiên có một số thuật toán tối ưu

hơn để tìm n nhưng vẫn không thể giải được bài toán này trong thời gian đa

thức vì thế dựa vào độ khó này có thể xây dựng ra hệ mật đường cong Elliptic

với các giao thức cho mã hóa và trao đổi khóa.

3.1.4 Đường cong Elliptic trên trườnghữu hạn

Các ứng dụng về mật mã của đường cong Elliptic đa số chỉ sử dụng các

đường cong trên trường hữu hạn.

Xét là một trường hữu hạn (hữu hạn số phần tử số nguyên dương):

(3.9)

Trong đó: là một số nguyên tố hoặc có dạng với p là một số

nguyên tố và m là một số nguyên dương. Khi này p được gọi là đặc số

và m là bậc mở rộng của .

Trong thực tế và đặc biệt trong các thiết bị phần cứng [62], người ta

thường sử dụng trường hữu hạn . Khi đó phép cộng trong trường này đơn

giản chỉ là phép toán XOR. Nhiều tài liệu cho thấy làm việc với hiệu quả

40% so với làm việc với trường .

3.2 Phương pháp trao đổi khoá mã an toàn hệ mật dựa trên đường cong Elliptic

3.2.1 Bài toán logarit rời rạc

Bài toán logarit rời rạc (DLP) được quan tâm nghiên cứu kể từ khi xuất

hiện mật mã khóa công khai năm 1975. Vấn đề được đặt ra là với nhóm cyclic

G =

bậc n, tìm kiếm một số thỏa mãn phương trình:

Bài toán này khó tính toán và các nhóm như vậy thường là nhóm nhân trên

trường hữu hạn và nhóm các điểm của đường cong Elliptic trên trường hữu hạn.

Bài toán Diffie-Hellman liên quan đến bài toán logarit rời rạc. Đó là tìm

kiếm đại lượng abP trên cơ sở P, aP, và bP. Có thể chỉ ra rằng đối với bất kỳ

nhóm nào, bài toán logarit rời rạc có thể rút gọn về bài toán Diffie-Hellman. Bài

toán ngược đã được chứng minh chỉ đúng trong một số trường hợp nhất định.

Độ khó của bài toán Diffie-Helman là cơ sở cho độ an toàn của giao thức

thỏa thuận khóa. Giả sử chúng ta có một nhóm cho G =

bậc n, quá trình

thỏa thuận khóa như sau:

1. Bên A chọn ngẫu nhiên số và tính aP, gửi cho Bên B.

2. Bên B chọn ngẫu nhiên số và tính bP, gửi cho Bên A.

Bên A

Bên B

a, bP

b, aP

Đã có

K = a(bP) = abP

K = b(aP) = abP

Cần tính

Bảng 3.1. Giá trị khóa thỏa thuận được là K = abP = a(bP) = b(aP).

Giao thức này được gọi một vòng, vì mỗi bên nhận dữ liệu từ đối tác của

mình chỉ một lần.

Thỏa thuận về một khóa chung bởi ba bên thì phức tạp hơn và đòi hỏi

một giao thức thỏa thuận khóa hai vòng. Dưới đây là các bước thực hiện:

1. Vòng đầu tiên.

(a) Bên A chọn ngẫu nhiên số và tính aP, gửi cho Bên B.

(b) Bên B chọn ngẫu nhiên số và tính bP, gửi cho Bên C.

2. Vòng thứ hai.

(a) Bên A dựa vào giá trị a và cP tính acP, sau đó sẽ gửi cho Bên B.

(b) Bên B dựa vào giá trị b và aP tính baP, sau đó sẽ gửi cho Bên C.

Bên A

Bên B

Bên C

Vòng 1

a, cP

b, aP

c, bP

Vòng 2

a, cP, bcP

b, aP, acP

c, bP, abP

Cần tính

K = a(bcP)

K = b(acP)

K = c(abP)

Bảng 3.2. Giá trị khóa thỏa thuận được sẽ là K = abcP

Ở đây nảy sinh một câu hỏi tự nhiên là: có tồn tại giao thức một vòng nào

phù hợp với ba bên? Câu hỏi vẫn mở cho đến khi Joux đề xuất giải pháp sử dụng

biến đổi song tuyến [43]. Sau đó xuất hiện đề xuất thú vị dựa trên ánh xạ song

tuyến mà cụ thể là kết hợp các cặp điểm trên đường cong Elliptic. Những đề xuất

nổi tiếng nhất cho đến nay là sơ đồ mã hóa dựa trên định danh (Boneh và

Franklin) [22] và sơ đồ chữ ký số ngắn (Boneh, Lynn và Shacham) [36].

3.2.2 Ánh xạ song tuyến

Giả sử rằng n là số nguyên tố. Cho G1 =

là một nhóm cyclic bậc n

có tính chất cộng và một phần tử trung hòa ∞, GT là một một nhóm cyclic bậc

n có tính chất nhân và phần tử đơn vị 1. Khi đó biến đổi song tuyến có thể định

nghĩa như sau:

Định nghĩa 3.10: Biến đổi song tuyến trên (G1, GT) được gọi là biến đổi

ê: G1× G1 → GT,

thỏa mãn các điều kiện sau đây:

1.(Song tuyến tính - Bilinear) Cho mỗi R, S, T ∈ G1, ta có:

ê(R + S, T) = ê(R, T) ê(S, T) và ê(R,S + T) = ê(R, S) ê(R, T).

2. (Không suy biến Non-Degeneracy) ê(P,P) ≠ 1.

3. (Khả năng tính toán) Giá trị ê(P,R) được xác định một cách hiệu quả.

1. ê(S, ∞) = 1, và ê(∞, S) = 1.

2. ê(S,-T) = ê(-S,T) = ê(S,T)-1.

3. ê(aS,bT) = ê(S,T)ab với mọi a, b ∈ ℤ

4. ê(S,T) = ê(T,S).

5. Nếu ê(S,R) = 1 thì đối với tất cả R∈G1 ta có S = ∞.

Có thể chứng minh rằng ánh xạ song tuyến có các tính chất sau:

Một trong những kết quả từ một ánh xạ song tuyến là bài toán logarit rời

rạc trong nhóm G1 có thể được đơn giản hóa một cách hiệu quả thành bài toán

logarit rời rạc trong một nhóm GT. Bởi vì, nếu chúng ta tìm kiếm một lời giải

của phương trình Q = xP nhóm G1, số x cần tìm cũng là nghiệm của phương

trình ê(P,Q) = ê(P,xP) = ê(P,P)x trong nhóm GT.

Độ an toàn của nhiều giao thức dựa trên các ánh xạ song tuyến dựa vào

độ khó tính toán của bài toán sau

Định nghĩa 3.11 Nếu ê là ánh xạ song tuyến, thì bài toán song tuyến

Diffie-Hellman ba bên được định nghĩa như sau: Với P, aP, bP và cP cho trước

cần tính ê(P, P)abc.

Độ khó của việc tính toán bài toán song tuyến Diffie-Hellman dẫn đến

độ khó của bài toán Diffie-Hellman cả trong nhóm G1 và nhóm GT. Giả thiết

chúng ta có thể giải bài toán Diffie-Hellman một cách hiệu quả trong nhóm G1,

trên cơ sở aP và bP và ta có thể tính abP, dẫn đến việc tìm

. Nếu biết phương pháp giải bài toán Diffie-Hellman

hiệu quả trong nhóm GT, thì tính toán g = ê(P,P), gab = ê(aP,bP), gc = ê(P,cP),

có thể xác định gabc =ê(P,P)abc.

Sự tồn tại của một ánh xạ song tuyến cho phép giải chính xác bài toán

Diffie-Hellman trong nhóm G1. Liên quan đến câu hỏi liệu bốn phần tử P, aP,

bP và cP có thỏa mãn đẳng thức abP = cP. Sử dụng ánh xạ song tuyến có thể

viết , và . Điều này có nghĩa

đẳng thức abP = cP xảy ra khi và chỉ khi .

3.2.3 Đường cong Elliptic

Đường cong elliptic E trên trường K được xác định bởi phương trình

Weierstrass không suy biến:

(3.10)

trong đó, K. Tập E(K) là tập hợp các điểm K hữu tỷ

của đường cong và bao gồm một điểm ở vô cực ∞, và những điểm (x, y) ∈ K ×

K mà thỏa mãn phương trình đường cong E.

Hình 3.2. Đường cong elliptic trên mặt phẳng thực

Nếu K là một trường hữu hạn 𝔽𝑞 với đặc trưng p, thì định lý Hasse cho

một giới hạn về số lượng các điểm K hữu tỷ:

với

(3.11)

Do đó, chúng ta có thể giả định rằng , Nếu

p | t, chúng ta nói rằng đường cong E là siêu kỳ dị.

Trong trường hợp khi p>3, phương trình Weierstrass có thể đơn giản hóa

bằng cách sử dụng biến đổi tuyến tính các biến về dạng:

(3.12)

Ví dụ, cho p=5, thì . Như vậy, số điểm của đường cong

Elliptic trên trường hữu hạn F5 là trong khoảng từ 2 đến 10. Thực tế, tất các các

đường cong Elliptic có thể có trên F5 và số điểm tương ứng được mô tả như

trong Bảng 3.3.

Bảng 3.3. Số điểm của các đường cong Elliptic tương ứng trên trường F5

STT

Số đi m

Đường cong Elliptic y2=x3+2x y2=x3+4x+2 y2=x3+x y2=x3+3x+2 y2=x3+1 y2=x3+2x+1 y2=x3+4x y2=x3+x+1 y2=x3+3x

Phương pháp cát tuyến và tiếp tuyến cho thấy cách thực hiện phép toán

trên các điểm của đường cong Elliptic. Phép toán trên các điểm của đường cong

trên trường số thực được minh họa trong hình 3.4. Cụ thể:

i) Với 2 điểm P, Q bất kỳ, kẻ một đường thẳng đi qua P và Q thì sẽ cắt

đường cong Elliptic tại một điểm thứ 3 là điểm S. Phép cộng P và Q sẽ là

. Trong trường hợp P và Q đối xứng nhau qua trục hoành, nói

cách khác Q = -P thì đường thẳng nối P và Q sẽ cắt đường cong tại một điểm

thứ 3 ở vô cực, hay P+ -(P)=.

ii) Để tính P+P, ta vẽ đường thẳng tiếp tuyến với đường cong Elliptic tại

điểm P, đường thẳng này sẽ cắt đường cong Elliptic tại điểm S, lúc đó

Hình 3.3. Phép toán trên các điểm của đường cong elliptic

Giả sử: điểm P ∈ E(𝔽𝑞) thỏa mãn các điều kiện sau đây:

1. Là một điểm bậc n,

2. Bậc của P là một số nguyên tố,

3. Hai số n và q là các số nguyên tố cùng nhau.

khi đó, bài toán logarit rời rạc trong nhóm

được định nghĩa như sau:

Cho trước một điểm P và điểm Q ∈

cần phải tìm số nguyên l, thỏa

mãn phương trình lP = Q.

Hiện nay, phương pháp tốt nhất để giải bài toán này là thuật toán Pollard

[43], thời gian thực hiện dự kiến khoảng O( ). Nếu n ≈ q, thì thời gian thực

hiện của thuật toán trên theo cấp số nhân đối với logq. Cần lưu ý rằng cũng có

những phương pháp khác trong việc giải bài toán logarit rời rạc, mà áp dụng

cho từng loại đường cong cụ thể. Đặc biệt, có thể sử dụng phép nhân Weil và

k. Số k được gọi là mức độ nhúng của đường cong

Tate [50] để chuyển bài toán từ các nhóm điểm của đường cong sang nhóm

nhân trên trường hữu hạn 𝔽q

và được định nghĩa như sau:

Định nghĩa 3.12 Giả sử E là một đường cong Elliptic xác định trên

trường 𝔽q, và P ∈ E (𝔽𝑞) là điểm có bậc là số nguyên tố n. Nếu USCLN (n, q)

= 1, thì mức độ nhúng của

là số nguyên k nhỏ nhất sao cho n |qk - 1.

Nếu độ nhúng k thấp, thì sử dụng phép nhân Weil, chúng ta có thể sử

k so với thuật toán Pollard trong

dụng các thuật toán tiểu hàm mũ cho việc tìm kiếm logarit rời rạc (phương pháp

chỉ số); trong đó, có thể tính nhanh hơn trong 𝔽 q

. Vì lý do này, trong mật mã bài toán logarit rời rạc trên đường cong Elliptic

chỉ sử dụng những đường cong có độ nhúng k lớn.

Với đường cong elliptic, độ nhúng thấp cho phép thực hiện hiệu quả phép

nhân Weil và Tate, điều đó dẫn đến các ánh xạ song tuyến.

3.2.4 Các giao thức mật mã sử dụng ánh xạ song tuyến

Thoả thuận khóa mã một v ng dùng cho ba bên

Giả sử rằng có thể tính toán một cách hiệu quả ánh xạ song tuyến trên nhóm

G1 và GT, trong đó bài toán song tuyến Diffie-Hellman là bài toán khó. Ánh xạ đó

là cơ sở để thực hiện giao thức thỏa thuận khóa mã một vòng cho ba bên:

1. Bên A chọn ngẫu nhiên một số a ∈ [0, n - 1], tính aP và gửi cho các

bên B, C.

2. Bên B chọn ngẫu nhiên một số b ∈ [0, n - 1], tính bP và gửi cho các

bênA, C.

3. Bên C chọn ngẫu nhiên một số c ∈ [0, n - 1], tính cP và gửi cho các

bên A, B.

Ta thấy rằng sau vòng này, tất cả những người tham gia tự mình tạo ra

một khóa mã bí mật chung.

Bảng 3.4. Thoả thuận khóa mã một vòng dùng cho ba bên

a, bP và cP

b, aP và cP

c, aP và bP

Bên A Bên B Bên C

K= (bP,cP)a

K= ê(aP,cP)b

K= ê(aP,bP)c

Đã có

= ê(P,P)abc

Cần tính

Phân tích sơ đồ trên có thể đặt ra câu hỏi: Liệu có khả năng xây dựng

l → GT. Và từ ánh xạ đó có thể tạo lập giao thức thỏa

ánh xạ đa tuyến êl: Gl-1

thuận khóa mã một vòng cho l người tham gia.

Thuật toán thỏa thuận khóa như được mô tả trong hình 3.4 sau đây:

Hình 3.4. Thuật toán thỏa thuận khóa nhiều người dùng

Câu hỏi về sự tồn tại của ánh xạ đa tuyến như vậy hiện nay vẫn còn là

bài toán mở.

Mật mã dựa trên định danh

Shamir [11] đã đề xuất khái niệm về mật mã dựa trên định danh để giải

quyết các vấn đề phát sinh trong quản lý chứng chỉ. Đề xuất Shamir giả định:

1. Khóa công khai của người dùng là định danh của họ (ví dụ như địa

chỉ email).

2. Sẽ có một bên thứ ba đáng tin cậy chịu trách nhiệm cho việc tạo ra các

khóa bí mật cho người sử dụng.

3. Mã hóa có thể được thực hiện ngay cả trước khi tạo khóa riêng của

người sử dụng (Phép mã hóa chỉ yêu cầu định danh (ID) của người dùng và

khóa công khai của một bên thứ ba tin cậy).

Đề xuất của Shamir đã phải chờ đến khi Boneh và Franklin [22] đề xuất

sơ đồ mã hóa định danh (ID) dựa trên ánh xạ song tuyến mới được thực hiện.

Sơ đồ này giả định rằng:

1. Chúng ta thực hiện một ánh xạ song tuyến ê: G1 → GT, mà bài toán

song tuyến Diffie-Hellman là bài toán tính toán khó.

2. Tồn tại hàm băm H1 và H2, sao cho:

H1: {0, 1}* → G1 \ {∞} và H2: GT → {0, 1}l.

trong đó l là số bit của bản rõ.

3. Bên thứ ba tin cậy cung cấp khóa riêng t ∈[0, n-1] và khóa công khai

T = tP (khóa T được phổ biến rộng rãi).

Khi một người dùng cần có một khóa riêng dA, thì bên thứ ba tin cậy cấp

một mã định danh IDA, tính khóa dA = tQA = tH1(IDA) và gửi qua một kênh an

toàn cho người dùng. Chú ý rằng khóa riêng dA có thể được coi là một chữ ký

của bên thứ 3 tin cậy vào mã dạng IDA.

Để mã hóa một thông điệp m ∈ {0, 1}l sử dụng sơ đồ Boneh-Franklin,

phải làm như sau:

1. Thiết lập một khóa công khai dựa trên mã định danh QA = H1(IDA).

2. Chọn một số ngẫu nhiên r ∈ [0, n - 1] và tính toán R = rP.

3. Tạo bản mã c = m⊕H2 (ê (QA,T)r).

4. Gửi cặp (R, c) cho người nhận.

Để giải mã một thông điệp của người dùng sử dụng khóa riêng của mình

dA và tính toán ra bản rõ m = c⊕ H2(ê(dA, R)). Quá trình giải mã thông điệp

đúng nhờ vào đẳng thức sau:

ê(dA,R) = ê(tQA, rP) = ê(QA, P)tr = ê(QA, tP)r = ê(QA, T)r.

Để nhận được thông điệp từ bản mã (R, c) cần tính (QA, T)r trên cơ sở (P,

QA, T, R) và đó là bài toán song tuyến DH.

Cần nhấn mạnh rằng, phương pháp mô tả trên chống được tấn công thụ

động, nhưng lại dễ bị tấn công bản mã lựa chọn. Tuy nhiên, có thể cải tiến để

loại bỏ vấn đề này.

Tóm lại: Phần này luận án đã trình bày một cơ chế mã hóa mới, trong đó

có thể thực hiện bằng cách ghép cặp điểm trên đường cong elliptic. Đã chỉ ra

khả năng ghép cặp điểm trên đường cong cho phép xây dựng các giao thức như:

1. Thỏa thuận khóa một vòng giữa ba bên.

2. Mã hóa dựa trên định danh.

3.2.5 Kết quả thử nghiệm ứng dụng

Trên cơ sở các kết quả lý thuyết nói trên, dựa trên thuật toán thỏa thuận

khóa nhiều người dùng (Hình 3.4) luận án đã xây dựng một phần mềm bảo mật

thông tin trên đường truyền sử dụng phương pháp trao đổi khóa mã an toàn và

một số ứng dụng của hệ mật trên đường cong elliptic có tích hợp nghiệp vụ mật

mã với thông điệp đầu vào cần bảo mật là các file rõ cần gửi (có thể là các file

dữ liệu cụ thể: chữ viết, hình ảnh tĩnh, tiếng nói tĩnh...). Các file rõ sau khi mã

mật hóa (file mã) sẽ được chuyển đến người nhận tương ứng và người nhận sử

dụng khóa riêng của mình được cấp tính toán giải mã và nhận được thông điệp

rõ (file rõ) ban đầu. Các hình: 3.5; 3.6; 3.7 trình bày một thông điệp là một file

hình ảnh cụ thể trước khi mã mật hóa và sau khi giải mã mật bằng khóa mã sai

và giải mã mật khóa mã đúng.

Hình 3.5. Ảnh gốc trước khi mã mật hóa

Hình 3.6. Ảnh giải mã mật với khóa mã sai

Hình 3.7. Ảnh sau khi giải mã mật với khóa mã đúng

Các kết quả đạt được đã minh chứng tính đúng đắn khi sử dụng phương

pháp thỏa thuận khóa mã ứng dụng giao thức mật mã dựa trên ánh xạ song

tuyến thực hiện bằng cách ghép cặp điểm trên đường cong elliptic cho phép

xây dựng các giao thức như: thỏa thuận khóa một vòng giữa ba bên và mã

hóa dựa trên định danh.

3.3 Nghiên cứu, đề xuất xây dựng thuật toán hiệu quả nhân nhanh đa thức

với hệ số nguyên

Năm 1971, Schönhage và Strassen đã đưa ra một thuật toán mới cho phép

nhân các số nguyên lớn. Kể từ đó các thuật toán nhân nhanh dựa trên biến đổi

Fourier nhanh FFT (Fast Fourier Transform) đã được cải tiến liên tục. Ngày

nay chúng ta có nhiều thuật toán nhân nhanh các số nguyên lớn [39] và nhân

nhanh đa thức [81]. Một số thuật toán không phụ thuộc vào kiến trúc bộ xử lý

và một số khác được thiết kế giành cho một hệ thống tính toán cụ thể. Mặc dù

FFT có một lợi thế so với các thuật toán nhân cổ điển, nhưng phiên bản giành

cho các máy tính đa nhân không dễ thực hiện. Ngoài ra, khi nhân các số nguyên

lớn bằng phương pháp FFT chỉ hiệu quả khi các số có trên 100.000 bit [66]. Để

khắc phục điều này cần tạo một thuật toán cùng một lúc sử dụng FFT và định

lý phần dư Trung Hoa CRT (Chinese Remainder Theorem). Định lý phần dư

Trung Hoa thường được sử dụng để tăng tốc độ tính toán trong thuật toán mật

mã RSA. Việc sử dụng CRT cho phép tách và thực hiện song song các phép

toán ký hoặc giải mã.

Vì vậy, trong phần này luận án tập trung nghiên cứu, xây dựng thuật toán

mới, hiệu quả nhân nhanh đa thức với hệ số nguyên sử dụng biến đổi Fourier

nhanh (FFT - Fast Fourier Transform) và định lý phần dư Trung Hoa (CRT)

và thực hiện thực tế thuật toán đề xuất.

Thuật toán này dùng trong quá trình tạo ra các tham số một cách hiệu

quả cho các hệ thống mật mã ECDSA và ECDH hoạt động trên các đường cong

elliptic. Kết quả thu được cho phép tăng hiệu quả của quá trình tạo đường cong

bằng cách tính toán song song. Phương pháp được đề xuất là sử dụng định lý

CRT để biểu diễn các số nguyên dưới dạng chuỗi hữu hạn của các số có kích

thước nhỏ hơn, và sau đó song song hóa các phép tính trên các biểu diễn đó.

Mặt khác, để tăng tốc độ tính toán trên đa thức, bằng cách sử dụng phép biến

đổi Fourier nhanh, thực chất là phép biến đổi đa thức từ biểu diễn bằng hệ số

thành các giá trị trong điểm. Các phương pháp được đề xuất có thể được sử

dụng để tăng tốc độ tính toán của các phép tính khác trong các vòng của đa thức

và chuỗi lũy thừa với hệ số nguyên. Đây là ưu điểm của phương pháp đề xuất,

bởi vì bằng phương pháp này có thể sử dụng đầy đủ khả năng tính toán của các

bộ vi xử lý đa lõi hiện đại.

3.3.1 Biến đổi Fourier nhanh và cách thực hiện

Phép biến đổi Fourier nhanh (FFT) là một thuật toán hiệu quả tính toán

biến đổi Fourier rời rạc (DFT). Cơ sở của DFT là biểu diễn các đa thức không

qua các hệ số mà qua giá trị các điểm. Xác định DFT cho trước trong n điểm

dựa trên định nghĩa hệ số O(n2) các phép tính số học. Việc sử dụng FFT rất

thuận lợi cho phép nhận được DFT sau khi thực hiện O(n logn) phép tính. Đây

là lý do chính mà FFT được xem xét rộng rãi trong các công trình công bố liên

quan đến hiệu năng tính toán [18], [32], [91]. Trong các thực nghiệm về số,

luận án sử dụng thuật toán FFT cổ điển nhưng cũng không gặp trở ngại gì khi

sử dụng một phiên bản FFT khác. Đặc biệt phù hợp với bộ nhớ cache rút gọn

FFT [37], được tối ưu với kiến trúc các bộ xử lý hiện đại. Chi tiết của thuật toán

được trình bày trong phần thực hành các thuật toán nhân. Phần này cũng gồm

định lý chứng minh tính đúng đắn của thuật toán đề xuất trong luận án.

3.3.2 Biểu diễn các phần tử trường và phép nhân nhanh trong vành đa thức

Trong phần này sẽ trình bày ngắn gọn về phương pháp tối giản Montgomery.

Bổ đề 3.1 sau đây là cơ sở cho phương pháp tối giản Montgomery [64]:

Bổ đề 3.1 Cho a, b, M, R là các số nguyên sao cho gcd(M, R) = 1, a,

t1 = a • b

t2 = t1 mod R

t3= t2 • q

t4 = t3 mod R

t5 = t4•M

t = (t1 + t5)/R.

Khi đó, một trong những phương trình sau đây là đúng:

abR-1 mod M = t hoặc abR-1 mod M = t - M

Trong thực tế, số M thường là số lẻ, và R là lũy thừa của số 2. Điều này

có nghĩa việc tính mod và div chỉ là lấy số lượng bit thấp của và

dịch sang phải bit với là số mũ của . Thực tế rút gọn Montgomery [64]

cho phép thực hiện tính toán hiệu quả trên vành ℤ/Mℤ.

Định lý 3.1 Cho M và R là các số nguyên dương. Nếu gcd(M, R) = 1,M

< R và vành

R1= <{0,1 ,. . . M - 1}, 0, 1, + , − , • >,

R2 = <{0,1, . . . , M-1}, 0, R mod M, + , - , ⊙ >

và được định nghĩa như sau:

a ± b = a ± b mod M

a • b = ab mod M

a ⊙ b = abR-1 mod M,

thì R1 và R2 đẳng cấu cùng nhau

Chứng minh: Chúng ta định nghĩa biến đổi h: R1 → R2 như sau:

h (x) = xR mod M

Vì M và R nguyên tố cùng nhau, luôn tồn tại . Điều này

có nghĩa là h trong thực tế là một song ánh. Để hoàn thành chứng minh chúng

ta phải chỉ ra rằng biến đổi h là một đồng cấu:

Điều này đã được chứng minh.

Giả thiết rằng: n là một số lũy thừa của 2 và lớn hơn bậc tối đa của đa thức

muốn nhân. Giả định rằng giá trị tuyệt đối các hệ số của đa thức nhỏ hơn B.

Định nghĩa 3.13: cho .

Chúng ta định nghĩa f(X) mod M như sau:

f(X) mod M = (fn-1 mod M)Xn−1+ • • • + (f0 mod M),

Trong đó với i từ 0 đến n-1

Nếu lựa chọn được một số hợp lý M thì nhân hai đa thức trong vành

(ℤ/Mℤ)[X] cho cùng kết quả như nhân chính các đa thức đó cùng trong vành

ℤ[X]. Bổ đề sau chỉ ra cách chọn số M để đạt được kết quả này.

Bổ đề 3.2 Cho ,

là các đa thức có hệ số nguyên, sao cho | với .

Nếu số nguyên M thỏa mãn điều kiện: 2nB2

Chứng minh: Nếu thì

Bởi vì | fi | < B và | gi | < B nên chúng ta có

với i từ 0 đến n-1.

Điều đó có nghĩa là |hi|2nB2 thì tất cả các hệ số (được mô tả trong định lý 3.1) của các đa thức f(X), g(X) và h(X) được biểu diễn trong vành là phần dư theo module M mà không cần rút gọn. Điều đó suy ra phương trình f(X) g(X) mod M = f(X) g(X).

Định lý 3.2

là các Cho

đa thức có hệ số nguyên, sao cho |fi|

mãn các điều kiện sau:

(1) 2nB2
(2) với và r ∈ ℤ, thì

f(X)g(X) = f(X)g(X) mod p = (f(X) mod p)(g(X) mod p) mod p

và trường 𝔽p có thể sử dụng để nhân đa thức f và g bằng cách sử dụng

thuật toán FFT.

Chứng minh: Bởi vì toán tử mod p đồng cấu tự nhiên của vành ℤ, nên

(f(X) mod p)(g(X) mod p) mod p = f(X)g(X) mod p

Trên cơ sở của Bổ đề 3.2 chúng ta có được đẳng thức

f(X)g(X) mod p = f(X)g(X).

78

Như vậy, việc nhân các đa thức f (X), g (X) ∈ℤ[X] cho cùng kết quả như

phép nhân đa thức f(X) mod p, g(X) mod p ∈𝔽p[X] với điều kiện các phần tử

của trường 𝔽p[X] được biểu diễn bằng các số

Số nguyên tố có dạng được chọn khi sử dụng thuật toán

FFT, do thực tế là với một số p xác định, trường 𝔽p có căn nguyên thủy bậc

của đơn vị.

Áp dụng biến đổi Fourier nhanh trên trường hữu hạn thay vì trên trường

số phức cho phép loại bỏ các phép toán dài, phức tạp trên số dấu phẩy động và

thay bằng các phép tính nhanh trên số nguyên. Điều này cho phép xây dựng

một thuật toán nhanh hơn, bởi vì trên bộ vi xử lý Intel Core 2 thì thực hiện phép

nhân các số nguyên khoảng 30 lần nhanh hơn so với thực hiện phép nhân trên

số dấu phẩy động. Trường hữu hạn được đề xuất sử dụng vì hai lý do:

1. Tối đa hóa tốc độ của thuật toán,

2. Loại bỏ lỗi làm tròn, được đặc trưng bởi các phép toán trên các số dấu

phẩy động.

Tất nhiên, ở đây phát sinh câu hỏi về các điều kiện cần phải thỏa mãn

sao cho việc thực hiện các thuật toán nhân đa thức nhanh nhất. Để trả lời câu

hỏi này, cần lưu ý rằng phép toán chính được thực hiện khi nhân đa thức là

phép nhân trong trường hữu hạn 𝔽p. Gồm phép nhân các số nguyên và rút gọn

theo module. Tối ưu hóa việc rút gọn theo module cho kết quả tốt nhất về tốc

độ thuật toán nhân đa thức. Thông thường, bài toán quy về theo module được

giải quyết bằng một trong ba cách:

(a) Tìm một số nguyên tố p, sao cho phép toán rút gọn theo module dẫn đến

thực hiện một số phép cộng và phép trừ. Thực tế là có rất nhiều số nguyên tố như

vậy. Ví dụ: 2224- 296 + 1 = 296(2128 - 1) + 1 hoặc 2512 - 232 + 1 = 232(2480 - 1) + 1.

79

(b) Một phương pháp tối ưu hóa khác phép rút gọn theo module là sử

dụng thuật toán rút gọn Montgomery [64]. Phương pháp này tổng quát hơn và

có thể áp dụng cho bất kỳ số nguyên tố nào khác 2.

(c) Cuối cùng, có thể sử dụng thuật toán cổ điển để tính toán tỉ số và phần

dư của phép chia, nhược điểm của phương pháp này là rất khó thực hiện một

cách hiệu quả [64].

Phương pháp đề xuất trong (a) cho phép tính tích các phần tử phần tử

trường hữu hạn chỉ sử dụng một phép nhân số nguyên và chắc chắn là nhanh

nhất trong số các phép tính được đề xuất. Các số nguyên tố dạng đặc biệt này

có vai trò quan trọng trong mật mã và thường được sử dụng trong các thuật toán

dựa trên đường cong elliptic (FIPS 186-3 và ANSI X509.62).

Việc nhân các đa thức bao gồm các phép toán sau: Thực hiện biến đổi

Fourier, nhân các vectơ thu được và thực hiện phép biến đổi Fourier nghịch

đảo. Trong tất cả các phép toán này tốn kém nhất là phép nhân trong trường 𝔽p.

Do đó, chúng ta đánh giá độ phức tạp của thuật toán dựa trên số phép nhân cần

thiết theo modulep.

Định lý 3.3 Cho trước hai đa thức có bậc nhỏ hơn n, trong đó, giá trị

tuyệt đối của từng hệ số nhỏ hơn B. Nếu số nguyên tố p thỏa mãn các điều kiện

của Định lý 3.2, việc nhân các đa thức trên bằng cách sử dụng thuật toán FFT

cần thực hiện n(2 + 3log(n)) phép nhân trong trường hữu hạn 𝔽p.

Chứng minh: Một phép nhân FFT (đơn) riêng biệt gồm ba bước sau:

1. Biến đổi Fourier của hai đa thức có bậc bé hơn n đòi hỏi 2nlog(n) phép

nhân trong trường 𝔽p (chúng ta biến đổi mỗi một đa thức thành một véc tơ có

2n hệ số).

2. Nhân các tọa độ tương ứng của hai véc tơ với 2n hệ số yêu cầu n2

phép nhân trong 𝔽p.

80

3. Biến đổi Fourier ngược của vector với 2n hệ số đòi hỏi n log (n) phép

nhân trong 𝔽p.

Điều này có nghĩa là một phép nhân đơn hai đa thức sử dụng thuật toán

FFT cần có n(2+3log (n)) phép nhân trong trường 𝔽p, Điều cần chứng minh.

Các thuật toán nhân được đề xuất có thể sử dụng để tính toán biến đổi

ngược trên vành các chuỗi lũy thừa với các hệ số nguyên. Một chuỗi như vậy

có thể đảo ngược khi và chỉ khi hệ số của nó có số mũ thấp nhất bằng 1 hoặc -

1. Sử dụng phương pháp lặp Newton cho các vành (padded ring) cho phép

chúng ta nhanh chóng xác định nghịch đảo của chuỗi. Phương pháp Newton

tính toán nghịch đảo nhanh vì chỉ sử dụng phép nhân, phép cộng và trừ chuỗi.

Để biến đổi ngược chuỗi có n hệ số chúng ta phải thực hiện log n phép lặp. Nếu

chuỗi lũy thừa có tính nghịch đảo có dạng:

(3.13)

thì giao thức sau cho phép tìm nghịch đảo của nó với n hệ số:

Data: Chuỗi lũy thừa ;

Result: chuỗi lũy thừa I thỏa mãn ;

Begin

;

While 2m < n do

End;

Return I; End.

81

Thuật toán 1. Đảo ngược chuỗi lũy thừa bằng cách sử dụng phương pháp

lặp Newton

3.3.3 Sử dụng định lý phần dư của Trung Hoa để phân chia tính toán giữa

các bộ vi xử lý

Để giảm độ phức tạp tính toán của thuật toán trên, chúng ta sử dụng định

lý phần dư Trung Hoa. Cách tiếp cận này sẽ cho phép chúng ta thay thế phép

nhân đơn trong trường 𝔽p bằng nhiều phép nhân nhỏ hơn trong trường 𝔽p. Một

ưu điểm khác của cách tiếp cận này là khả năng phân chia tính toán trong trường

𝔽p giữa các bộ vi xử lý. Để đạt được mục đích, trước hết phải tìm ra các số

nguyên tố pi cho phép thực hiện ý tưởng đề xuất trong thực tế.

Định lý 3.4

Cho là

các đa thức với hệ số nguyên, sao cho |fi|
thỏa mãn các điều kiện sau:

sao cho và thì

và trường 𝔽pi có thể sử dụng để nhân song song các đa thức f và g bằng

sử dụng biến đổi nhanh Fourier (Fast Fourier Transform - FFT).

Chứng minh: Chứng minh định lý này sẽ rất giống với cách chứng minh

Định lý 3.2 vì toán tử mod M đồng cấu tự nhiên trên vành ℤ thì:

(f(X) mod M) (g(X) mod M) mod M = f(X)g(X) mod M.

Sử dụng Bổ đề 3.1 chúng ta có được đẳng thức sau:

f(X) g(X) mod M = f(X) g(X).

82

Điều này có nghĩa là phép nhân các đa thức g(X), f(X) ∈ Z [X] cho cùng

kết quả như nhân các đa thức g(X) mod M, f(X) mod M ∈(ℤ/Mℤ) [X] miễn là

các phần tử của vành ℤ/Mℤ được biểu diễn bằng các số từ tập hợp:

(3.14)

Giả định rằng M là tích của các số nguyên tố khác nhau pi, khi đó có thể

áp dụng định lý phần dư Trung Hoa và ta có được đẳng cấu sau:

(3.15) ℤ/Mℤ≃𝔽p1× • • • × 𝔽pk .

Các đẳng cấu trên có thể mở rộng thành đồng cấu vành đa thức:

(3.16) (ℤ/Mℤ )[X] ≃ 𝔽p1 [X] × • • • × 𝔽pk[X].

Điều này có nghĩa là phép nhân trong vành (ℤ/Mℤ )[X] có thể được thay

thế bởi k phép nhân trong các vành 𝔽pi[X], và mỗi phép nhân trong chúng có

thể được thực hiện một cách độc lập. Điều này cho phép chia tách các phép tính

giữa k bộ xử lý (processor) và thực hiện chúng một cách song song. Ngoài ra,

tất cả các số nguyên tố pi = 2m + 1 ri + 1 được chọn, sao cho phép nhân có thể

được thực hiện bằng thuật toán FFT. Thực tế là mỗi trường 𝔽pi chứa nghiệm

nguyên thủy với phần tử đơn vị bậc 2m + 1.

Cách giải quyết được đề xuất trong định lý 3.3 trên hiệu quả hơn rất nhiều

so với phương pháp tiêu chuẩn được trình bày trong phần trước. Để đảm bảo hiệu

suất tối đa tính toán cần chọn các số nguyên tố pi có thể chứa trong một thanh ghi

của bộ xử lý. Điều này dễ dàng thực hiện với các bộ xử lý 32 và 64 bit.

Giả sử chúng ta đã tìm được k số nguyên tố pi có cùng số bit và thỏa mãn

giả thuyết của Định lý 3.4 thì định lý 3.5 sau là đúng:

Định lý 3.5 Cho trước hai đa thức hệ số nguyên bậc nhỏ hơn n, với giá

trị tuyệt đối từng hệ số nhỏ hơn B. Nếu các số nguyên tố pi thỏa mãn điều kiện

định lý 3.4 và ⌊log2(pi)⌋= ⌊log2(pj)⌋, khi đó khi nhân các đa thức như vậy sử

83

dụng thuật toán FFT đòi hỏi thực hiện phép

nhân trong trường 𝔽pi. Trong đó c1, c2 là các hằng số xác định.

Chứng minh: Vì nên chúng ta có thể giả định

rằng chi phí để thực hiện phép nhân trong mỗi phần tử trường Fpi là như nhau.

Phép nhân các đa thức sử dụng biến đổi Fourier nhanh FFT gồm ba bước sau: 1. Việc rút gọn các hệ số theo module đòi hỏi phải thực hiện c1k2n phép

nhân trong trường 𝔽pi. Mỗi hệ số đa thức có độ chính xác k liên quan đến số đo

của số pi. Do đó, một hệ số duy nhất có thể được giảm bằng cách sử dụng

(1∕2)c1k phép nhân trong trường 𝔽pi . Bởi vì chúng ta có hai đa thức như vậy,

mỗi một trong số chúng đều có n hệ số, và số các số nguyên tố là k, thì tổng số phép nhân cần thiết bằng (1/2) c1.k.2.n.k = c1k2n.

2. Chúng ta sử dụng thuật toán nhân nhanh FFT trong các trường 𝔽pi với

i ∈{1 ,. . . , k}:

(a) Biến đổi Fourier của hai đa thức bậc nhỏ hơn n đòi hỏi phải thực hiện

2nlog(n) phép nhân trong trường 𝔽pi(các đa thức được biến đổi thành các vectơ

với 2n hệ số),

(b) Việc nhân hai vectơ mà mỗi vectơ có 2n hệ số đòi hỏi thực hiện 2n

phép nhân trong trường 𝔽pi,

(c) Biến đổi Fourier ngược đối với vector có 2n hệ số cần nlog (n) phép

nhân trong trường 𝔽pi.

3. Sử dụng định lý phần dư Trung Hoa cho phép tạo ra các hệ số của tích nhờ c2k2n phép nhân trong trường 𝔽pi. Kết quả trên là do mỗi một lời giải của hệ phương trình x ≡ ai mod pi có thể được tạo nên nhờ sử dụng (1/2)c2k2phép

nhân trong trường 𝔽pi. Bởi vậy chúng ta phải tạo ra 2n hệ số, thì tổng số phép nhân cần thiết bằng (1/ 2)c2k2 • 2n = c2k2n.

Do đó, thuật toán mô tả trong định lý 3.4 đòi hỏi thực hiện:

c1k2n + kn (2+3 log (n)) + c2k2n

Phép nhân trong trường 𝔽pi.

84

Bây giờ chúng ta so sánh độ phức tạp tính toán của các thuật toán được

mô tả trong các định lý 3.2 và 3.3. Để làm điều này, trước tiên chúng ta phải

đưa vào một đơn vị đo thống nhất về độ phức tạp tính toán của cả hai thuật

toán. Trong trường hợp này là số phép nhân trong trường 𝔽p. Chúng ta có thể

đưa ra kết luận sau:

- So sánh thuật toán mới với phương pháp áp dụng phép biến đổi Fourier

nhanh cả để nhân các đa thức và nhân các số. Nếu chúng ta giả định rằng số pi

chứa trong một thanh ghi bộ xử lý, thì độ phức tạp tính toán của thuật toán nhân

đa thức và các hệ số của nó nhờ sử dụng phép biến đổi Fourier nhanh FFT khoảng:

O((n log n)(k log k))

Còn thuật toán của chúng ta có độ phức tạp tính toán:

O(kn log n + k2n)

Giả sử rằng k = O(n), thì thuật toán dựa hoàn toàn trên phép biến đổi

Fourier FFT nhanh hơn nhiều. Độ phức tạp tính toán của nó là O(n2 log2n)

trong khi thuật toán đề xuất hoạt động trong khoảng thời gian O(n3). Giả sử

các hệ số đa thức nhỏ hơn và k= O(log n). Khi đó, thuật toán dựa hoàn toàn

trên phép biến đổi Fourier nhanh (FFT) có sự phức tạp tính toán O(n log2n log

log n) trong khi phương pháp đề xuất có phức tạp tiệm cận O(n log2 n). Vì

vậy, thuật toán hiệu quả nhân nhanh đa thức đã được phát triển.

Hệ quả 3.1 Nếu k = O(log n), thì độ phức tạp tính toán của thuật toán đề

xuất nhỏ hơn độ phức tạp tính toán của thuật toán nhân chỉ dựa trên việc sử

dụng phép biến đổi Fourier FFT và bằng: O(n log2n), trong khi độ phức tạp tính

toán của thuật toán dựa trên phép biến đổi FFT khoảng: O(n log2 n log log n).

Như đã thể hiện trong các thực nghiệm, thuật toán đề xuất có ưu điểm

rõ ràng trong trường hợp hệ số của các đa thức có giá trị cỡ vài trăm bit, có

nghĩa là ứng dụng có hiệu quả đối với các giá trị bé của k và n.

85

3.3.4 Thực hiện thuật toán nhân nhanh đa thức trên bộ vi xử lý 64 bit

Luận án đã thực hiện thuật toán nhân đa thức trên cơ sở của định lý 3.4 trên

bộ vi xử lý 64 bít đa lõi (4 nhân) thông qua thư viện OpenMP với bậc đa thức 𝑛 =

2𝑡 với t = 10, 11, ..., 18 và ngưỡng của các hệ số là 𝐵 = 2256 và 𝐵 = 2512.

3.3.4.1 Các tham số 𝒑𝒋 được sử dụng

Bộ vi xử lý 64 bít cho phép tính toán trực tiếp phép toán số học theo các

modulo 32 bít nên các số nguyên tố 𝑝𝑗 là các số 32 bít. Từ yêu cầu (4) trong

định lý 3.4 thì các số được sử dụng cần có dạng 𝑝 = 2𝑚+1𝑟 + 1 với 2𝑚+1 ≥ 2𝑛

hay m ≥ t. Luận án đã tìm được 56 số nguyên tố dạng a × 222 + 1 có thể dùng

cho việc nhân các đa thức có bậc n lên đến 221 cùng các căn nguyên thủy của

đơn vị, ký hiệu σ, với cấp tương ứng được cho trong bảng sau.

Bảng 3.5. Các số nguyên tố được sử dụng trong phần mềm.

σ

j

a

σ

j

a

σ

a

σ

a

j

j

7

29

742

3

43

862

3

513

7

639

15

1

11

30

757

3

44

865

3

517

6

645

16

2

5

31

765

13

45

874

3

544

3

648

17

3

3

32

768

5

46

879

5

553

3

649

18

4

6

33

772

3

47

894

5

559

3

655

19

5

10

34

790

6

48

915

31

565

3

663

20

6

15

35

814

3

49

928

3

573

5

669

21

7

11

36

819

10

50

939

10

589

3

670

22

8

35

37

823

3

51

940

3

592

3

684

23

9

3

38

832

3

52

957

19

604

3

688

24

10

3

39

837

41

53

972

7

610

3

694

25

11

10

40

847

3

54

979

3

627

13

714

26

12

3

41

853

3

55

1000

3

628

3

715

27

13

3

42

859

3

56

1014

5

637

3

733

28

14

86

3.3.4.2 Số các số 𝒑𝒋 dùng cho 𝑩 = 𝟐𝟐𝟓𝟔 và 𝑩 = 𝟐𝟓𝟏𝟐.

𝑘 𝑗=1 > 2𝑛𝐵2. Với các 𝑝𝑗 cho trong bảng 3.5 và với giá trị tối đa của n cần thử nghiệm là 218

Để đảm bảo điều kiện (3) đưa ra trong định lý 3.4 tức là ∏ pj

chúng ta có k = 18 ứng với 𝐵 = 2256 và k = 34 ứng với 𝐵 = 2512.

3.3.4.3 Phân việc cho 4 nhân.

Luận án tiến hành việc tính nhân các hệ số theo phương pháp CRT bao

gồm k phép tính trên các trường 𝔽𝑝𝑗 song song trên 4 nhân tính toán. Như vậy

với k = 18 thì sẽ có 2 tiến trình thực hiện tuần tự 4 phép và 2 tiến trình thực

hiện tuần tự 5 phép trên các trường 𝔽𝑝𝑗; tương tự với k = 34 thì sẽ có 2 tiến

trình thực hiện tuần tự 8 phép và 2 tiến trình thực hiện tuần tự 9 phép trên các

trường 𝔽𝑝𝑗.

3.3.4.4 Kết quả thực nghiệm với 𝑩 = 𝟐𝟐𝟓𝟔 và 𝑩 = 𝟐𝟓𝟏𝟐.

Các kết quả thu được nhờ kết hợp biến đổi Fourier nhanh với định lý

phần dư Trung Hoa đã làm tăng một cách đáng kể tốc độ tính toán. Để so sánh

kết quả các phép đo, thực nghiệm cũng xác định thời gian thực hiện thuật toán

nhân đa thức bằng phương pháp cổ điển. Các kết quả so sánh thời gian tính với

thuật toán cổ điển với thời gian thực hiện trên các bộ vi xử lý đa lõi (4 nhân) dựa

trên biến đổi Fourier và định lý phần dư Trung Hoa được trình bày trong trong

bảng 3.6 và bảng 3.7, hình 3.8 và hình 3.9 kết quả cho thấy tốc độ thực hiện

thuật toán nhân cổ điển với thuật toán đề xuất hai đa thức bậc n từ 210 đến 218

với hệ số 256 bit và 512 bit.

87

Bảng 3.6. So sánh thời gian tính toán với phương pháp nhân cổ điển với thuật

Bậc đa thức n

PP cổ điển

FFT-CRT

t1/t2

t1

t2

t = log2n

0,184

0,03

6,133333334

10

0,79

0,05875

13,44680851

11

2,222

0,085

26,14117647

12

7,213

0,14375

50,1773913

13

28,034

0,33875

82,7571956

14

112,151

0,65625

170,8967619

15

455,09

1,45625

312,5081545

16

18228,65

3,39125

539,2265389

17

6639,125

5,16375

1285,717744

18

toán đề xuất nhân đa thức bậc n từ 210 đến 218 với hệ số 256

Hình 3.8. So sánh tốc độ thực hiện thuật toán nhân cổ điện với thuật toán

đề xuất nhân đa thức bậc n từ 210 đến 218 với hệ số 256

88

Bảng 3.7. So sánh thời gian tính toán với phương pháp nhân cổ điển với thuật

Bậc đa thức n

PP cổ điển

FFT-CRT

t1/t2

t1

t2

t = log2n

0,528

0,6525

8,091954023

10

1,666

0,070875

23,50617284

11

5,471

0,108

50,6574074

12

20,673

0,24075

85,86915888

13

79,745

0,507375

157,1717172

14

345,858

1,04175

331,9971203

15

1300,515

2,179125

596,8060575

16

5141,672

4,417875

1163,833744

17

20597,99

9,127125

2256,78842

18

toán đề xuất nhân đa thức bậc n từ 210 đến 218 với hệ số 512

Hình 3.9. So sánh tốc độ thực hiện thuật toán nhân cổ điện với thuật toán

đề xuất nhân đa thức bậc n từ 210 đến 218 với hệ số 512

89

Kết quả thực nghiệm chỉ ra rằng thời gian tính toán bằng phương pháp

nhân cổ điển với thuật toán đề xuất nhân hai đa thức với hệ số 256 bit (Bảng

3.6) và với các hệ số 512 bit (Bảng 3.7) thì thời gian tính toán bằng phương

pháp cổ điển lâu hơn rất nhiều lần (thể hiện qua tỉ số t1/t2) so với thời gian tính

toán dựa trên biến đổi Fourier và định lý phần dư Trung Hoa; có nghĩa là: thuật

toán dựa trên định lý phần dư Trung Hoa (CRT) và biến đổi Fourier nhanh

(FFT) được đề xuất nhanh hơn nhiều lần, ngay cả khi không thực hiện nhân

song song. So sánh tốc độ thực hiện các thuật toán nhân các đa thức với hệ số

256 bit (Hình 3.8) và tốc độ thực hiện của các thuật toán nhân đa thức với các

hệ số 512 bit (Hình 3.9) cũng chỉ rõ ưu điểm tuyệt đối của thuật toán đề xuất là

tốc độ tính toán dựa trên biến đổi Fourier và định lý phần dư Trung Hoa nhanh

hơn rất nhiều lần tốc độ tính toán bằng phương pháp cổ điển (thể hiện bằng thời

gian tính toán ít hơn rất nhiều). Có thể kết luận rằng các thuật toán đề xuất đã

tạo ra một phương pháp mới hiệu quả nhân nhanh các đa thức ứng dụng trong

thực tiễn; đặc biệt là trong các ứng dụng mật mã.

3.4 Kết luận chương 3

Chương 3 đã tập trung phân tích chi tiết về phương pháp nhân đa thức

và chuỗi lũy thừa được đề xuất dựa trên ý tưởng tận dụng tối đa khả năng

tính toán của bộ vi xử lý đa nhân hiện đại và sử dụng định lý phần dư Trung

Hoa. Thuật toán trên được thực hiện bằng sử dụng chuẩn lập trình song song

mở OpenMP.

Thuật toán dựa trên định lý phần dư Trung Hoa (CRT) và biến đổi Fourier

nhanh (FFT) nên sử dụng trong trường hợp số lượng các hệ số của đa thức lớn

hơn nhiều so với độ chính xác của chúng, khi đó tính toán được thực hiện trên các

đa thức hoặc chuỗi lũy thừa với sự rút gọn module các hệ số đa thức.

Các kết quả kiểm định, đánh giá thu được cho thấy phương pháp đề xuất

có ý nghĩa thực tiễn cao. Thuật toán đề xuất đã được so sánh với việc thực hiện

90

thuật toán cổ điển nhân các hệ số trong các trường 𝔽p lớn. Kết quả thực nghiệm

chỉ ra rằng thuật toán dựa trên định lý phần dư Trung Hoa (CRT) và biến đổi

Fourier nhanh (FFT) được đề xuất nhanh hơn nhiều lần, ngay cả khi không

thực hiện nhân song song. So sánh với thuật toán nhân đa thức bằng phương

pháp cổ điển với độ phức tạp O (n2) (Bảng 3.6 và 3.7) cũng chỉ rõ ưu điểm tuyệt

đối của thuật toán đề xuất. Có thể kết luận rằng các thuật toán đề xuất đã tạo ra

một phương pháp mới hiệu quả nhân nhanh các đa thức ứng dụng trong thực

tiễn; đặc biệt là trong các ứng dụng mật mã.

Kết quả chính của chương 3 được công bố trong các công trình [CT1],

[CT4], [CT5] và [CT6] trong danh mục các công trình khoa học đã công bố.

91

KẾT LUẬN

Với mục tiêu nghiên cứu đề xuất, xây dựng phương pháp hiệu quả tạo

tham số an toàn và nâng cao hiệu năng một số thuật toán thực hiện mã hóa và

giải mã, làm việc thích ứng trong các môi trường cho một số hệ mật ứng dụng

trong bảo mật thông tin. Sau một thời gian nghiên cứu và dưới sự hướng dẫn

tận tình của tập thể hướng dẫn khoa học, cơ sở đào tạo..., nghiên cứu sinh đã

cố gắng, nỗ lực hết mình để hoàn thành các mục tiêu của luận án. Có thể tóm

lược một số kết quả chính mà luận án đã đạt được, bao gồm:

A. Các kết quả đạt được của Luận án

1. Đã nghiên cứu chuyên sâu về cơ sở toán học các thuật toán mật mã

dùng trong bảo mật thông tin.

2. Đã nghiên cứu, đề xuất giải pháp nâng cao độ an toàn và hiệu năng thuật

toán mã hóa hệ mật AES, trên cơ sở xây dựng và lựa chọn ma trận MDS mới có

các tính chất mật mã tốt cho tầng khuếch tán, đồng thời lựa chọn một số mô hình

kiến trúc cứng hóa và sử dụng linh hoạt các nguồn tài nguyên phần cứng; cũng

như mô phỏng thực tế các giải pháp đề xuất trên công cụ ISIM của ISE.

3. Đã nghiên cứu về đường cong elliptic và mật mã dựa trên đường cong

elliptic, đường cong elliptic mạnh và cách tạo chúng; cũng như phương pháp

trao đổi khóa mã an toàn cùng những ứng dụng mới của Hệ mật sử dụng cơ chế

nhóm điểm trên đường cong elliptic.

4. Đã nghiên cứu, xây dựng thuật toán mới, hiệu quả nhân nhanh đa thức

với hệ số nguyên sử dụng biến đổi Fourier nhanh (Fast Fourier Transform) và

định lý phần dư Trung Hoa và thực hiện thực tế thuật toán đề xuất.

B. Đóng góp mới của Luận án

1. Đề xuất giải pháp nâng cao hiệu năng thuật toán mã hóa hệ mật AES-

256, bằng cách lựa chọn xây dựng ma trận MDS mới và giải pháp xây dựng

kiến trúc module mật mã, thực thi cứng hóa hệ thống mã hóa và giải mã thuật

toán AES-256 trên các vi mạch chuyên dụng.

92

2. Đề xuất, xây dựng thuật toán hiệu quả nhân nhanh đa thức với hệ số

nguyên sử dụng biến đổi Fourier nhanh và định lý phần dư Trung Hoa và thực

hiện thực tế thuật toán đề xuất.

C. Hướng nghiên cứu tiếp theo

- Tiếp tục nghiên cứu ứng dụng thuật toán nhân nhanh đa thức với hệ số

nguyên sử dụng biến đổi Fourier nhanh và định lý phần dư Trung Hoa để nâng

cao hiệu năng thuật toán tạo các đường cong elliptic mạnh về mật mã.

- Nghiên cứu đưa các kết quả về nâng cao hiệu năng thuật toán mã hóa

hệ mật AES dựa trên ma trận MDS mới có các tính chất mật mã tốt cho tầng

khuếch tán và một số mô hình kiến trúc cứng hóa sử dụng linh hoạt các nguồn

tài nguyên phần cứng vào các ứng dụng trong thực tế các hệ thống thông tin

mật mã;

93

DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ

[CT1]. Nguyễn Nam Hải, Nguyễn Thị Thu Nga, “Về một phương pháp trao

đổi khoá mã an toàn”, Tạp chí Nghiên Cứu Khoa Học và Công Nghệ

Quân Sự, ISSN: 1859 - 1043, Số 48- 04/2017, p119-128.

[CT2]. Nguyen Thi Thu Nga, Hoang Duc Tho, Le My Tu, “On the improving

Diffusion layer and Performance of AES algorithm”, International

conference on information and communication (ICIC) 2017, IEEE

Communications Society of Vietnam chapter, p 288-292.

[CT3]. Hoang Duc Tho, Nguyen Truong Thang, Nguyen Thi Thu Nga, Pham

Quoc Hoang, “An algorithm for improving algebraic degree of S-box

coordinate Boolean functions based on affine equivalence

transformation”, Vol.10, Nos.1&2, PP.339-350, 2018, Journal of

Informatics and Mathematical Sciences (ESCI - ISI).

[CT4]. Nguyễn Thị Thu Nga, “Về một phương pháp nhân đa thức dựa trên

định lý phần dư Trung Hoa và phép biến đổi Fourier nhanh”, Tạp chí

Nghiên Cứu Khoa Học và Công Nghệ Quân Sự, ISSN: 1859 - 1043,

Số 59- 02/2019, p187-195.

[CT5] Nguyễn Thị Thu Nga, Nguyễn Trường Thắng, Nguyễn Ngọc Cương,

Trần Thị Lan Anh, "Về một phương pháp mã hóa ứng dụng trong hệ

mật dựa trên đường cong Elliptic", Tạp chí Nghiên Cứu Khoa Học và

Công Nghệ Quân Sự, ISSN: 1859 - 1043, Số 64- 12/2019, p182-187.

[CT6] Nguyễn Thị Thu Nga, Nguyễn Trường Thắng, Nguyễn Đức Tâm, Lê

Mỹ Tú, Nguyễn Ngọc Cương, “Đề xuất phương pháp mã hóa có thể chối

từ khóa công khai sử dụng thuật toán Elgamal”, ISBN 978-604-67-1744-

7, Báo cáo Hội thảo quốc gia năm 2020.

94

[CT7] Nguyễn Thị Thu Nga, Nguyễn Trường Thắng, Trần Mạnh Đông,

Nguyễn Hoài Nam, “Về một thuật toán mã hóa xác thực hiệu năng cao”,

Tạp chí Nghiên Cứu Khoa Học và Công Nghệ Quân Sự - ISSN 1859-

1043, p153-p160, số 73-06/2021.

95

TÀI LIỆU THAM KHẢO

Tiếng Anh

[1] Achiya Bar-On and Orr Dunkelman and Nathan Keller and Eyal Ronen

and Adi Shamir, “Improved Key Recovery Attacks on Reduced-Round

AES with Practical Data an d Memory Complexities”,

https://eprint.iacr.org, 2018.

[2] ANSI X9.62-1998, “Public Key Cryptography for the Financial Services

Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)”, 2005.

[3] Ashokkumar C., Bholanath Roy, M Bhargav Sri Venkatesh, and Bernard

L.Menezes, "S-Box” Implementation of AES is NOT side channel

resistant", https://eprint.iacr.org, 2018.

[4] A.Elbirt, W.Yip, B.Chetwynd, C.Paar, “An FPGA-Based Performance

Evaluation of the AES Block Cipher Candidate Algorithm Finalists”,

IEEE Transactions on VLSI Design, Volume 9, 2001.

[5] A.Menezes, P.van Oorschot, S.Vanstone, “Kryptografia

stosowana”, WNT, 2005

[6] Beaulieu Ray, Stefan Treatman-Clark, Douglas Shors, Bryan Weeks,

Jason Smith, Louis Wingers (2015) The SIMON and SPECK lightweight

block ciphers. Design Automation Conference (DAC), 2015 52nd

ACM/EDAC/IEEE. IEEE.

[7] Biham E., Shamir A., Differential Cryptanalysis of DES-like

Cryptosystems, In Proceedings of CRYPTO’90, Lecture Notes in

Computer Science, Springer-Verlag, vol. 537, pp. 2-21, (1990).

[8] Biham, E.: On Masui’s Linear Cryptanalysis, EUROCRYPT, (1994).

[9] Boneh D., Franklin M., “Identity-based encryption from the Weil pairing”,

Advances in Cryptology- CRYPTO 2001, pp. 586-615, 2001.

[10] Boneh D., Lynn B., Shacham H., “Short signatures from the Weil pairing”,

Advances in Cryptology- ASIACRYPT 2001, pp. 297-319, 2001.

96

[11] Brown M., Hankerson D., López J., Menezes A., “Software

Implementation of the NIST Elliptic Curves Over Prime Fields”,

Proceedings of the 2001 Conference on Topics in Cryptology: The

Cryptographer’s Track at RSA, 2001.

[12] Bogdanov Andrey, Lars R Knudsen, Gregor Leander, Christof Paar, Axel

Poschmann, Matthew JB Robshaw, Yannick Seurin, Charlotte Vikkelsoe

(2007) PRESENT: An ultra-lightweight block cipher, Springer

[13] Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall and

Neils Ferguson. “Twofish Encryption Algorithm - A 128-bit Block Cipher”.

[14] B.Schneier, “Kryptografia dla praktyków. Protokoły, algorytmy i

programy źródłowe w języku C”, WNT, 2002, Wydanie II.

[15] Chan W. O., Cryptanalysis of SIGABA, Master’s Thesis, Department

of Computer Science, San Jose State University, May 2007.

[16] Cheung O.Y.H., Tsoi K.H., Leong P.H.W., and Leong M.P., “Tradeoffs

in Parallel and Serial Implementations of the International Data

Encryption Algorithm IDEA”, in Preceedings of 3rd International

Workshop on Cryptographic Hardware and Embedded Systems, vol.

2162, 2005

[17] Cormen T. H., Leiserson C. E., Rivest R. L., Stein C., “Introduction to

Algorithms”, MIT Press, 2003.

[18] Crandall R., Fagin B., “Discrete weighted transforms and large integer

arithmetic”, Mathematics of Computation, vol. 62, str. 305-324, 1994.

[19] C.Radu, “Implementing Electronic Card Payment Systems”, Artech

House Publishers, 2002.

[20] D.Runje, M.Kovac, “Universal Strong Encryption FPGA Core

implementation”, in Proceedings of Design, Automation, and Test in

Europe, 1998.

97

[21] Daemen Joan, Vincent Rijmen (2002) The design of Rijndael: AES-the

advanced encryption standard, Springer,

[22] D. Boneh, M. Franklin, “Identity-based encryption from the Weil

[23] David Harvey, Joris van der Hoeven, “Polynomial multiplication over

pairing”, Advances in Cryptology- CRYPTO 2001, pp. 586-615, 2001.

finite fields in time O(n log n)”. https://hal.archives-ouvertes.fr/hal-

02070816, Mar 2019

[24] D.Knuth, “Sztuka programowania. Tom 2: Algorytmy seminumeryczne”,

WNT, 2002

[25] E. Swankoski, R. Brooks, N. Vijaykrishnan, M. Kandemir, M. J. Irwin,

“A Parallel Architecture for Secure FPGA Symmetric Encryption”, in

Proceedings of the 11th Reconfigurable Architectures Workshop

(RAW'04).

[26] E. Biham, A. Shamir, Differential Cryptanalysis of DES-like

Cryptosystems, In Proceedings of CRYPTO’90, Lecture Notes in

Computer Science, Springer-Verlag, vol. 537, pp. 2-21, (1990).

[27] Felix Wegener and Lauren De Meyer and Amir Moradi, "Spin Me Right

Round: Rotational Symmetry for FPGA-specific AES",

https://eprint.iacr.org, 2019.

[28] FIPS PUB 46-3, “Data Encryption Standard”, National Institute of

Standards and Technology, U.S.Department of Commerce, 1999

[29] FIPS-197, “Advanced Encryption Standard (AES)”, 2001

[30] Freyre P., DíazN., and Cuellar O., “Variantions to the cryptographic

alogirhtms AES and TwoFish”, https://eprint.iacr.org, 2019.

[31] Garner H. L., “The Residue Number System”, IRE Trans. Electronic

Computers, vol. EL-8, No. 6, str. 140-147, 1959.

[32] Grama A., Gupta A., Karypis G., Kumar V., “Introduction to Parallel

Computing”, Addison Wesley, 2003.

98

[33] Ghada F. Elkabbany, Heba K. Aslan, Mohamed N. Rasslan, “A Design of

a Fast Parallel-Pipelined Implementation of AES: Advanced Encryption

Standard”, International Journal of Computer Science & Information

Technology (IJCSIT), Vol. 6, No. 6, Dec. 2014.

[34] Guo Jian, Thomas Peyrin, Axel Poschmann, Matt Robshaw (2011) The

LED block cipher. Cryptographic Hardware and Embedded Systems-

CHES 2011. Springer,326-341.

[35] G.Simmons, “Contemporary Cryptology: The Science of Information

Integrity”, IEEE Press, 1992

[36] H. Shacham, B. Lynn, D. Boneh, “Short signatures from the Weil

pairing”, Advances in Cryptology- ASIACRYPT 2001, pp. 297-319, 2001.

[37] Harvey D., “A cache-friendly truncated FFT”, Theoretical Computer

Science, vol. 410, str. 2649-2658, 2009.

[38] Hendrik Lenstra. (1987), “Factoring Integers with Elliptic Curves”, The

Annals of atematics, 126 (3), pp. 649-673.

[39] H. J. Nussbaumer, “Fast polynomial transform algorithms for digital

convolution”,IEEE Trans. Acoust. Speech Signal Process., vol. 28 (2),

str.205-215, 1980.

[40] Ivan Damgard and Rasmus Zakarias, Fast Oblivious AES A dedicated

application of the MiniMac protocol, https://eprint.iacr.org, 2015.

[41] Joan Daemen, Vincent Rijmen. The Rijndael Block Cipher AES

Proposal, 1999.

[42] Joan Daemen, Vincent Rijmen. The Design of Rijndael AES—The

Advanced Encryption Standard, 2001.

[43] J. Pollard, “Monte Carlo methods for index computation mod p”,

Mathematics of Computation, pp.918-924, 1978.

99

[44] Junod P. and Vaudenay S., Perfect diffusion primitives for block cipher -

Building efficient MDS matrices in Selected Areas in Cryptology (SAC

2004), LNCS 3357, pp. 84-99, Springer-Verlag, 2004.

[45] J.Daemen, V.Rijmen, “AES Proposal: Rijndael”, in Proceedings of the

First Advanced Encryption Standard Candidate Conference, NIST, 1998.

[46] Kishan Chand Gupta and Indranil Ghosh Ray, On Constructions of MDS

Matrices From Circulant-Like Matrices For Lightweight Cryptography,

Technical Report No. ASU/2014/1, Dated : 14th February, 2014.

[47] K. Lauter,D. Charles, “Computing modular polynomials”, Journal of

Computational Mathematics, pp. 195-204, 2005.

[48] Koblitz (1987) N., “Elliptic curve cryptosystem”, Math.Comp, 48 (16), pp.

203- 209.

[49] Kutyłowski M, Strothmann WB, Lý thuyết mật mã và thực hành đảm bảo an

toàn các hệ thống máy tính, Nhà xuất bản Read Me, Warsawa 1998.

[50] Lawrence C. Washington (2008), “Elliptic Curves-Number theory and

Cryptography”, CRC Press.

[51] Lorenzo Grassi, “MixColumns Properties and Attacks on (round-reduced)

AES with a Single Secret S-Box”, https://eprint.iacr.org, 2017.

[52] L.Brown, M Kwan, J Pieprzyk, J Seberry, " Improving Resistance to

Differential Cryptanalysis and the Redesign of LOKI", Advances in

Cryptology - Asiacrypt'91, Lecture Notes in Computer Science, vol 739,

Springer-Verlag, 1993

[53] L.Saadi, “Stealth Ciphers”, Trafford Pub, 2004.

[54] M. Kutyłowski, WB. Strothmann, Lý thuyết mật mã và thực hành đảm bảo

an toàn các hệ thống máy tính, Nhà xuất bản Read Me, Warsawa 1998.

[55] Maurer U. M., Wolf S., “Diffie-Hellman Oracles”, Lecture Notes in

Computer Science, CRYPTO ’96, vol.1109, str.268-282, Springer-

Verlag, 1996.

100

[56] Maurer U. M., Wolf S., “The relationship between breaking the

iffieHellman protocol and computing discrete logarithms”, SIAM Journal

on Computing, vol. 28, str. 1689-1721, 1999.

[57] Maurer U. M., Wolf S, “The Diffie-Hellman protocol”, Designs, Codes,

and Cryptography, vol. 19, str. 147-171, 2000.

[58] Menezes A., Okamoto T, Vanstone S., “Reducing elliptic curve

logarithms to a finite field”, IEEE Trans. Info. Theory, vol. 39, str. 1639-

1646, 1993.

[59] Menezes A. J., Van Orschot P. C., Vanstone S. A., “Handbook of Applied

Cryptography”, CRC Press, 1997.

[60] Michael J. Wiener and Robert J. Zuccherato (1999), “Faster Attacks on

Elliptic Curve Cryptosystems”, Entrust Technologies.

[61] Miller V, “Use of elliptic curves in cryptography”, CRYPTO 85, str. 417-

426, 1985.

[62] Miller Victor S. (1985), “Use of Elliptic Curves in Cryptography”,

CRYPTO ’85, pp. 417-428.

[63] Miller V, “The Weil pairing, and its efficient calculation”, Journal of

Cryptology, pp. 235-261, 2004.

[64] Montgomery P, “Modular Multiplication Without Trial Division”,

Mathematics of Computation, vol. 44, str. 519-521, 1985.

[65] M.Shan, J.Vuillemin, “Fast Implementations of RSA Cryptography”,

inProceedings of the 11th IEEE Symposium on Computer Arithmetic, 1993.

[66] L. Garcia, “Can Schönhage multiplication speed up the RSA encryption

or decryption?”, University of Technology, Darmstadt, 2005.

[67] M¨uller V., “Ein Algorithmus zur Bestimmung der Punktzahlen

elliptischer Kurven ¨uber endlichen K¨orpern der Charakteristik gr¨osser

drei”, Ph.D. Thesis, Universit¨at des Saarlandes, 1995.

101

[68] Muhammad Reza Z’aba. “Analysis of linear relationships in block

ciphers”. PhD thesis, Queensland University of Technology. 2010.256p.

[69] Muzereau A., Smart N. P., Vrecauteren F., “The equivalence between the

DHP and DLP for elliptic curves used in practical applications”, LMS J.

Comput. Math., vol. 7(2004), str. 50-72, 2004.

[70] Mustafa Khairallah, Anupam Chattopadhyay, and Thomas Peyrin,

“Looting the LUTs : FPGA Optimization of AES and AES-like Ciphers for

Authenticated Encryption”, https://eprint.iacr.org, 2017.

[71] Pollard J., “Monte Carlo methods for index computation mod p”,

Mathematics of Computation, pp.918-924, 1978.

[72] P.Barrett, “Implementing the Rivest Shamir and Adleman Public Key

Encryption Algorithm on a Standard Digital Signal Processor”, in

Proceedings of Advanced in Cryptography-CRYPTO’86, Springer-

Verlag, 1987.

[73] P.Junod and S. Vaudenay, “Perfect diffusion primitives for block cipher -

Building efficient MDS matrices in Selected Areas in Cryptology” (SAC

2004), LNCS 3357, pp. 84-99, Springer-Verlag, 2004.

[74] P.Campbell, B.Calvert, S.Boswell, “Security+ In Depth”, Course

Technology PTR, 2003

[75] P. Montgomery, “Modular Multiplication Without Trial Division”,

Mathematics of Computation, vol. 44, str. 519-521,1985.

[76] Riddhi Ghosal, “Analysing Relations involving small number of

Monomials in AES S- Box”, https://eprint.iacr.org, 2017.

[77] R. Rivest, A. Shamir, L. Adleman,. “A Method for Obtaining Digital

Signatures and Public-Key Cryptosystems”, Communications of the

ACM, Vol. 21 (2), 1978.

102

[78] Sakallı, MuharremTolga, et al. “On the Construction of and Binary

Matrices with Good Implementation Properties for Lightweight Block

Ciphers and Hash Functions.” Mathematical Problems in

Engineering 2014 (2014).

[79] Satoh T., Araki K., “Fermat quotients and the polynomial time discrete

log algorithm for anomalous elliptic curves”, Comm. Math. Univ. Sancti

Pauli, vol. 47, str. 81-92, 1998.

[80] Sch¨onchage A., “Asymptotically fast algorithms for the numerical

multiplication and division of polynomials with complex coefficients”,

Lecture Notes in Computer Science, vol. 144, str. 3-15, 1982.

[81] Sch¨onchage A., “Asymptotically fast algorithms for the numerical

multiplication and division of polynomials with complex coefficients”,

Lecture Notes in Computer Science, vol. 144, str. 3-15, 1982.

[82] Schoof R., “Elliptic curves over finite fields and the computation of square

roots mod p”, Math. Comp., vol. 44, str. 483-494, 1985.

[83] Shannon, Claude E “Communication Theory of Secrecy Systems”, Bell

System Technical Journal, 28(4), pp. 656--715 (1949).

[84] Shamir A., “Identity-based cryptosystems and signature schemes”,

Advances in Cryptology -CRYPTO 84, pp. 47-53, 1984.

[85] Sikhar Patranabis, Abhishek Chakraborty, Debdeep Mukhopadhyay, and

Chakrabart P.P. , “Fault Space Transformation: A Generic Approach to

Counter Differential Fault Analysis and Differential Fault Intensity

Analysis on AES-like Block Ciphers”, https://eprint.iacr.org, 2015.

[86] Silverman J. H., “The arithmetic of elliptic curves”, Graduate Texts in

Mathematics, vol 106, Springer-Verlag, New York, 1986.

[87] Silverman J. H., Tate J., “Rational points on elliptic curves”,

Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1992.

[88] Skjernaa B., “Satoh’s algorithm in characteristic 2”, Preprint, 2000.

103

[89] Smart N., “The discrete logarithm problem on elliptic curves of trace

one”, J. Crypto., vol. 12, str. 193-196, 1999.

[90] Swankoski E., Brooks R., Vijaykrishnan N., Kandemir M., Irwin M. J.,

“A Parallel Architecture for Secure FPGA Symmetric Encryption”, in

Proceedings of the 11th Reconfigurable Architectures

Workshop(RAW'04).

[91] Takahashi D., Kanada Y., “High-performance radix-2, 3 and 5 parallel 1-

D complex FFT algorithms for distributed-memory parallel computers”,

Journal of Supercomputing, vol. 15, str. 207-228, 2000.

[92] Xiongwei Fei, Kenli Li, Wangdong Yang, Keqin Li, “Practical parallel

AES algorithms on cloud for massive users and their performance

evaluation",.2012

[93] Van der Hoeven J., “The truncated Fourier transform and applications”,

in: ISSAC 2004, ACM, str. 290-296, 2004.

[94] Van der Hoeven J., “Notes on the truncated Fourier transform”,

unpublished, retrieved from http://www.math.u-psud.fr/˜vdhoeven/, 2005.

[95] W.Diffie and MEHellman, “New directions in cryptography”, IEEE

Transactions on Information Theory, IT-22, 6, 1976.

[96] W. O. Chan, Cryptanalysis of SIGABA, Master’s Thesis, Department

[97] Wu, Shengbao, Mingsheng Wang, and Wenling Wu. “Recursive diffusion

of Computer Science, San Jose State University, May 2007.

layers for (lightweight) block ciphers and hash functions”. Selected Areas

in Cryptography p.355-371.Springer Berlin Heidelberg, (2013).

[98] Zhou Lijing, Licheng Wang, Yiru Sun (2018) "On Efficient Constructions

of Lightweight MDS Matrices". IACR Transactions on Symmetric

Cryptology, 2018 (1), 180-200.

P1

PHỤ LỤC

Phụ lục 1. Thư viện Module nhân nhanh đa thức ........................................... P2

Phụ lục 2. Mã nguồn của thư viện nhân nhanh đa thức .................................. P6

Phụ lục 3. Module chương trình trao đổi khóa ............................................. P24

P2

Phụ lục 1. THƯ VIỆN MODULE NHÂN NHANH ĐA THỨC

Biên dịch thư viện

Phụ lục 2 chứa mã nguồn của thư viện để nhân nhanh đa thức với hệ số

là các số nguyên không âm. Triển khai này được chuẩn bị dựa trên chuẩn ngôn

ngữ ANSI C và phần mở rộng OpenMP

Mã thư viện gồm các tệp có chứa các bản khai cần thiết và thực hiện

thuật toán nhân.

- uintpoly.h: tệp tiêu đề chính có chứa giao diện bậc cao đến các hàm

hoạt động trên đa thức.

- uintpoly.c: tệp chứa việc thực hiện các hàm cơ bản hoạt động trên các

đa thức (chiếm và giải phóng bộ nhớ, so sánh, hiển thị và nhân theo phương

pháp phổ thông).

- arth.c: tệp chứa việc thực hiện các phép tính số học (cộng, nhân, rút

gọn module) và các hàm khởi tạo cố định cho thuật toán Garner (CRT).

- dft fp32.c: tệp chứa việc thực hiện hàm tạo ra dữ liệu cần thiết để thực

hiện biến đổi Fourier (DFT).

- dft fp32 crt.c: tệp chứa việc thực hiện thuật toán nhân nhanh, song

song các đa thức. Chuẩn bị thực hiện sử dụng các Directive OpenMP và thực

hiện tính toán trên bộ vi xử lý đa nhân.

Sử dụng thư viện

Đoạn mã sau cho thấy cách sử dụng các hàm của thư viện. Bậc tối đa

#include "uintpoly.h"

main(int argc, char *argv[])

{

clock_t start1, end1, start2, end2;

double cpu_time_used1, cpu_time_used2;

được chấp nhận bởi phiên bản của thư viện này là 222- 1.

/* Declaration of polynomials. */

UINT_Poly a, b, c, d;

/*

* Khởi tạo cấu trúc cần thiết để nhanh chóng thực hiện

* DFT i CRT.

*

* Trong đó giả thiết rằng, chúng ta sẽ không thực hiện tính toán với đa thức

bậc lớn hơn 127. Điều này cũng áp dụng với

* các phép nhân.

*/

UINT_Poly_dft_crt_init(4095);

/* Khởi tạo các đa thức. */

UINT_Poly_init(&a);

UINT_Poly_init(&b);

UINT_Poly_init(&c);

UINT_Poly_init(&d);

/*

* Ghi a là một đa thức ngẫu nhiên bậc 2, có

* các hệ số 64-bitowe (2*32).

*/

UINT_Poly_random(&a, 9, 200);

/*

* Ghi b là một đa thức ngẫu nhiên bậc 4, có

* các hệ số 96-bitowe (3*32).

*/

UINT_Poly_random(&b, 10, 300);

/*

* Thực hiện nhân thep phương pháp cổ điển và ghi tích của chúng là

* đa thức c.

P3

*/

start1 = clock();

UINT_Poly_mul(&c, &a, &b);

end1 = clock();

cpu_time_used1 = ((double)(end1 - start1)/CLOCKS_PER_SEC );

/*

* Thực hiện phép nhân bằng phương pháp FFT + CRT ghi tích của chúng là

* đa thức d.

*/

start2 = clock();

UINT_Poly_dft_crt_mul(&d, &a, &b);

end2 = clock();

cpu_time_used2 = ((double)(end2 - start2) / CLOCKS_PER_SEC);

/*

* In các thừa số và thương số tính được dựa vào hai thuật toán

* (Các đa thức c i d đồng nhất với độ chính xác

* đến các số 0 trong hệ số.

*/

printf("a = \n");

UINT_Poly_print(&a);

printf("b = \n");

UINT_Poly_print(&b);

printf("c = \n");

UINT_Poly_print(&c);

printf("d = \n");

UINT_Poly_print(&d);

printf("conventional method took %f seconds to execute \n",

cpu_time_used1);

printf("conventional method start at %u clk \n", start1);

P4

printf("conventional method start at %u clk \n", end1);

printf("FFT + CRT method took %f seconds to execute \n",

cpu_time_used2);

printf("FFT + CR method start at %u clk \n", start2);

printf("FFT + CR method start at %u clk \n", end2);

/* Giải phóng bộ nhớ bị chiếm bởi các đa thức. */

UINT_Poly_clear(&a);

UINT_Poly_clear(&b);

UINT_Poly_clear(&c);

UINT_Poly_clear(&d);

/* Giải phóng cấu trúc dùng để tính toán DFT i CRT. */

UINT_Poly_dft_crt_finish();

getchar;

return 0;

}

P5

P6

Phụ lục 2. MÃ NGUỒN CỦA THƯ VIỆN NHÂN NHANH ĐA THỨC

file uintpoly.c: Những phép tính cơ bản trên đa thức

IntUINT_Poly_init(UINT_Poly * a)

{ memset(a, 0, sizeof(UINT_Poly));

a->deg = -1;

return 0;}

IntUINT_Poly_init_mem(UINT_Poly * a, int digits, int deg)

{ int i;

a->digits = digits;

a->deg = deg;

if ((a->v = calloc(a->deg + 1, sizeof(uint32_t *))) == 0) {

return -1;

}

memset(a->v, 0, (a->deg + 1) * sizeof(uint32_t));

for (i = 0; i <= deg; i++) {

if ((a->v[i] = calloc(a->digits, sizeof(uint32_t))) == 0) {

UINT_Poly_clear(a);

return -1;

}

memset(a->v[i], 0, a->digits * sizeof(uint32_t)); }

return 0;}

IntUINT_Poly_init_coef(UINT_Poly * a, const uint32_t * coef, int digits, int

deg)

{ if (a->deg < deg) {

return -1;

}

if (a->digits < digits) {

return -1;

}

memset(a->v[deg], 0, a->digits * sizeof(uint32_t));

memcpy(a->v[deg], coef, digits * sizeof(uint32_t));

return 0;}

IntUINT_Poly_clear(UINT_Poly * a)

{ int i;

if (a->v) {

for (i = 0; i <= a->deg; i++) {

if (a->v[i]) {

free(a->v[i]);}

}

free(a->v);}

memset(a, 0, sizeof(UINT_Poly));

a->deg = -1;

return 0;}

intUINT_Poly_random(UINT_Poly * a, int digits, int deg)

{ int i, j, k;

if (UINT_Poly_init_mem(a, digits, deg) < 0){

return -1;}

for (i = 0; i <= deg; i++) {

for (j = 0; j < digits; j++) {

for (k = 0; k < sizeof(uint32_t); k++) {

a->v[i][j] += (uint32_t)rand() << 8 * k; }}}

return 0;}

intUINT_Poly_eq(const UINT_Poly * a, const UINT_Poly * b)

{ int deg = a->deg;

int i;

if (b->deg < a->deg) {

deg = b->deg;

}

for (i = 0; i <= deg; i++) {

if (ARTH_cmp(a->v[i], a->digits, b->v[i], b->digits) != 0) {

return 0;}}

if (a->deg < b->deg) {

for (i = a->deg + 1; i <= b->deg; i++) {

if (ARTH_cmp_digit(b->v[i], 0, b->digits) != 0) {

return 0;}}}

else if (b->deg < a->deg) {

for (i = b->deg + 1; i <= a->deg; i++) {

P7

if (ARTH_cmp_digit(a->v[i], 0, a->digits) != 0) {

return 0;}}}

return 1;}

intUINT_Poly_mul(UINT_Poly * c, const UINT_Poly * a, const UINT_Poly *

b)

{

UINT_Poly t;

uint32_t *d;

int i, j;

/* Phân bổ bộ nhớ cho kết quả. */

UINT_Poly_init_mem(&t, a->digits + b->digits + 1, a->deg + b->deg);

d = calloc(t.digits - 1, sizeof(uint32_t));

/* Phép nhân. */

for (i = 0; i <= a->deg; i++) {

for (j = 0; j <= b->deg; j++) {

ARTH_mul(d, a->v[i], a->digits, b->v[j], b->digits);

t.v[i + j][t.digits - 1] += ARTH_add(t.v[i + j], d, t.digits - 1);}}

/* Ghi kết quả. */

UINT_Poly_clear(c);

c->v = t.v;

c->digits = t.digits;

c->deg = t.deg;

free(d);

return 0;}

intUINT_Poly_print(const UINT_Poly * a)

{

int i, j;

for (i = 0; i <= a->deg; i++) {

printf("[%d] ", i);

for (j = a->digits - 1; j > -1; j--) {

printf(":%08x", a->v[i][j]);}

P8

printf("\n");}

return 0; }

P9

File dft fp32.c: dữ liệu cho DFT

mont_mul(uint32_t a, uint32_t b, uint32_t p, uint32_t q)

{

uint64_t t1, t2, t3;

t1 = (uint64_t)a *b;

t2 = (uint64_t)(uint32_t)t1 *q;

t2 = (uint64_t)(uint32_t)t2 *p;

t3 = (t1 >> 32) + (t2 >> 32);

if ((uint32_t)t1 != 0) {

t3 += 1;

}

if ((uint64_t)p <= t3) {

t3 -= (uint64_t)p;}

return (uint32_t)t3;}

static uint32_tmont_exp(uint32_t a, int e, uint32_t p, uint32_t q)

{

uint32_t t = (uint32_t)(0x0100000000ULL % p);

int mask = 1 << 30;

while (mask != 0) {

t = mont_mul(t, t, p, q);

if (e & mask) {

t = mont_mul(t, a, p, q);

}

mask >>= 1;}

return t;}

static intdft_index(int i, int prec)

{

int rprec = 1;

int di = 0;

while (1 < prec) {

prec >>= 1;

if (i & prec) {

di |= rprec;}

rprec <<= 1;}

return di;}

intARTH_Fp32_dft_init(ARTH_Fp32_dft * dft, int prec, uint32_t p, uint32_t r)

{

uint32_t q, s, t1, t2, ir, i2;

int i, idx;

memset(dft, 0, sizeof(ARTH_Fp32_dft));

if (p < 3) {

return -1;}

/* Xác định kích thước tối đa của vector để thực hiện biến đổi. */

dft->n = 1;

while (1) {

/* Quá ít nghiệm. */

if (((dft->n & (p - 1)) == 1) && (dft->n < prec)) {

return -1;}

/* Đủ số lượng các nghiệm. */

if (prec <= dft->n) {

break;}

dft->n <<= 1;}

dft->roots = dft->n / 2;

/* Tính hệ số q để nhân theo phương pháp Montgomery. */

q = 1;

while (p * q != 1) {

q = q * (2 - p * q);}

q = -q;

/* t1 = t2 = 2^32 % p. */

t1 = (uint32_t)(0x0100000000ULL % p);

t2 = t1;

/* s = 2^64 % p. */

P10

s = (uint32_t)(((uint64_t)t1 * t1) % p);

dft->p = p;

dft->q = q;

dft->s = s;

/* Biến đổi r i 1/2 theo dạng Montgomery. */

r = mont_mul(r, s, p, q);

i2 = mont_mul((p + 1) / 2, s, p, q);

dft->i2 = i2;

/* Khoanh vùng bộ nhớ. */

if ((dft->r = calloc(dft->roots, sizeof(uint32_t))) == 0) {

return -1;}

if ((dft->ir = calloc(dft->roots, sizeof(uint32_t))) == 0) {

free(dft->r);

return -1;}

/* Tính nghiệm nguyên thủy và nghịch đảo của nó theo độ chính xác cho trước.

*/

r = mont_exp(r, (p - 1) / dft->n, p, q);

ir = mont_exp(r, dft->n - 1, p, q);

/* Chuẩn bị bảng các nghiệm và nghịch đảo của chúng. */

for (i = 0; i < dft->roots; i++) {

idx = dft_index(i, dft->roots);

dft->r[idx] = t1;

dft->ir[idx] = t2;

t1 = mont_mul(t1, r, p, q);

t2 = mont_mul(t2, ir, p, q);}

return 0;}

intARTH_Fp32_dft_free(ARTH_Fp32_dft * dft)

{

if (dft->r != 0) {

free(dft->r);}

if (dft->ir != 0) {

P11

free(dft->ir);}

return 0;}

P12

file dft fp32 crt.c: thuật toán nhân nhanh

/* 32-Số nguyên tố 32bit dạng b*2^22 + 1. */

static const uint32_t p32[56] = {

513 * 0x400000U + 1, 517 * 0x400000U + 1, 544 * 0x400000U + 1,

553 * 0x400000U + 1, 559 * 0x400000U + 1, 565 * 0x400000U + 1,

573 * 0x400000U + 1, 589 * 0x400000U + 1, 592 * 0x400000U + 1,

604 * 0x400000U + 1, 610 * 0x400000U + 1, 627 * 0x400000U + 1,

628 * 0x400000U + 1, 637 * 0x400000U + 1, 639 * 0x400000U + 1,

645 * 0x400000U + 1, 648 * 0x400000U + 1, 649 * 0x400000U + 1,

655 * 0x400000U + 1, 663 * 0x400000U + 1, 669 * 0x400000U + 1,

670 * 0x400000U + 1, 684 * 0x400000U + 1, 688 * 0x400000U + 1,

694 * 0x400000U + 1, 714 * 0x400000U + 1, 715 * 0x400000U + 1,

733 * 0x400000U + 1, 742 * 0x400000U + 1, 757 * 0x400000U + 1,

765 * 0x400000U + 1, 768 * 0x400000U + 1, 772 * 0x400000U + 1,

790 * 0x400000U + 1, 814 * 0x400000U + 1, 819 * 0x400000U + 1,

823 * 0x400000U + 1, 832 * 0x400000U + 1, 837 * 0x400000U + 1,

847 * 0x400000U + 1, 853 * 0x400000U + 1, 859 * 0x400000U + 1,

862 * 0x400000U + 1, 865 * 0x400000U + 1, 874 * 0x400000U + 1,

879 * 0x400000U + 1, 894 * 0x400000U + 1, 915 * 0x400000U + 1,

928 * 0x400000U + 1, 939 * 0x400000U + 1, 940 * 0x400000U + 1,

957 * 0x400000U + 1, 972 * 0x400000U + 1, 979 * 0x400000U + 1,

1000 * 0x400000U + 1, 1014 * 0x400000U + 1

};

/* Nghiệm nguyên thủy giành cho số nguyên tố theo bảng p32. */

static const uint32_t p32_r[56] = {

7, 6, 3, 3, 3, 3, 5, 3, 3, 3, 3, 13, 3, 3, 7, 11, 5, 3, 6, 10, 15, 11,

35, 3, 3, 10, 3, 3, 3, 3, 13, 5, 3, 6, 3, 10, 3, 3, 41, 3, 3, 3, 3, 3,

3, 5, 5, 31, 3, 10, 3, 19, 7, 3, 3, 5};

/* Kích thước tối đa của vector để thực hiện biến đổi. */

static int dft_size = 0;

/* Hệ số dùng để thực hiện phép biến đổi cho số nguyên tố từ bảng p32. */

static ARTH_Fp32_dft dft[56];

/* Các hệ số cho CRT với các số nguyên tố theo bảng p32. */

static ARTH_Fp32_crt crt;

static uint32_tmont_add(uint32_t a, uint32_t b, uint32_t p)

{

uint32_t c = 0;

ARTH_ADC(a, a, b, c)

if ((c == 1) || (p <= a)) {

a -= p; }

return a;}

static uint32_tmod_mul(uint32_t a, uint32_t b, uint32_t m)

{

uint32_t c = 0;

ARTH_MUL(a, a, b, c);

ARTH_DIV(c, a, c, a, m);

return a;}

static uint32_tmont_sub(uint32_t a, uint32_t b, uint32_t p)

{ uint32_t c = 0;

ARTH_SBB(a, a, b, c)

if (c == 1) {

a += p;

}

return a;}

static uint32_tmont_mul(uint32_t a, uint32_t b, uint32_t p, uint32_t q)

{

uint64_t t1, t2, t3;

t1 = (uint64_t)a *b;

t2 = (uint64_t)(uint32_t)t1 *q;

t2 = (uint64_t)(uint32_t)t2 *p;

P13

t3 = (t1 >> 32) + (t2 >> 32);

if ((uint32_t)t1 != 0) {

t3 += 1;

}

if ((uint64_t)p <= t3) {

t3 -= (uint64_t)p;}

return (uint32_t)t3;}

static intdft_size_for_poly(int deg)

{

int size = 2;

while (size < deg + 1) {

size *= 2;}

return size;}

intUINT_Poly_dft_crt_init(int deg_max)

{

int i, j;

dft_size = dft_size_for_poly(deg_max + 1);

if (ARTH_Fp32_crt_init(&crt, p32, 56) < 0) {

return -1;

}

for (i = 0; i < 56; i++) {

if (ARTH_Fp32_dft_init(dft + i, dft_size, p32[i], p32_r[i]) < 0) {

for (j = 0; j < i; j++) {

ARTH_Fp32_dft_free(dft + j);

}

ARTH_Fp32_crt_free(&crt);

return -1;}}

return 0;}

intUINT_Poly_dft_crt_finish()

{

int i;

dft_size = 0;

for (i = 0; i < 56; i++) {

ARTH_Fp32_dft_free(dft + i);

}

P14

ARTH_Fp32_crt_free(&crt);

return 0;}

intUINT_Poly_dft_crt_mul(UINT_Poly * c, const UINT_Poly * a, const

UINT_Poly * b)

{

uint32_t *dft_a, *dft_b, *pa, *pb, *ha, *la, *hb, *lb;

uint32_t p, q, r, ir, s, t, i2e;

int deg_c;

int primes;

int m, n, bs, i, j, k;

/* Bậc của đa thức kết quả nằm ngoài phạm vi được hỗ trợ. */

deg_c = a->deg + b->deg;

if (dft_size < deg_c + 1) {

return -1;}

/* Các hệ số phép nhân quá lớn để có thể được đại diện. */

primes = a->digits + b->digits + 2;

if (56 < primes) {

return -1;}

/* Alokacja pamięci. */

n = dft_size_for_poly(deg_c);

dft_a = calloc(n * primes, sizeof(uint32_t));

dft_b = calloc(n * primes, sizeof(uint32_t));

/*

* 1) Chuẩn bị vector để thực hiên biến đổi dưới dạng Montgomery.

* 2) Chuẩn bị thực hiện biến đổi FFT.

* 3) Thực hiện phép nhân.

* 4) Thực hiện biến đổi ngược.

* 5) Chuyển đổi sang biểu diễn dạng cổ điển.

*/

#pragma omp parallel for default(none) shared(dft, a, b, c, dft_a, dft_b, deg_c,

primes, n) \

P15

private(pa, pb, ha, la, hb, lb, p, q, r, ir, s, t, i2e, m, bs, i, j, k)

for (i = 0; i < primes; i++) {

p = dft[i].p;

q = dft[i].q;

s = dft[i].s;

pa = dft_a + i * n;

pb = dft_b + i * n;

memset(pa, 0, n * sizeof(uint32_t));

memset(pb, 0, n * sizeof(uint32_t));

/* (1) Przejście do reprezentacji Montgomeryego. */

for (j = 0; j <= a->deg; j++) {

pa[j] = mont_mul(ARTH_mod_digit(a->v[j], a->digits, p), s, p,

q);}

for (j = 0; j <= b->deg; j++) {

pb[j] = mont_mul(ARTH_mod_digit(b->v[j], b->digits, p), s, p,

q);}

/* (2) FFT. */

m = n;

while (m != 1) {

bs = n / m;

m /= 2;

for (j = 0; j < bs; j++) {

r = dft[i].r[j];

la = pa + 2 * j * m;

ha = la + m;

lb = pb + 2 * j * m;

hb = lb + m;

for (k = 0; k < m; k++, la++, ha++, lb++, hb++) {

t = mont_mul(*ha, r, p, q);

*ha = mont_sub(*la, t, p);

*la = mont_add(*la, t, p);

P16

t = mont_mul(*hb, r, p, q);

*hb = mont_sub(*lb, t, p);

*lb = mont_add(*lb, t, p);}}}

/* (3) Nhân các vector theo hệ số với hệ số. */

for (j = 0; j < n; j++) {

pa[j] = mont_mul(pa[j], pb[j], p, q);}

/* (4) FFT^(-1). */

m = 1;

i2e = dft[i].ir[0];

while (m < n) {

bs = n / (2 * m);

i2e = mont_mul(i2e, dft[i].i2, p, q);

for (j = 0; j < bs; j++) {

ir = dft[i].ir[j];

la = pa + 2 * j * m;

ha = la + m;

for (k = 0; k < m; k++, la++, ha++) {

t = mont_add(*la, *ha, p);

*ha = mont_sub(*la, *ha, p);

*la = t;

*ha = mont_mul(*ha, ir, p, q);}}

m *= 2;

}

for (j = 0; j < n; j++) {

pa[j] = mont_mul(pa[j], i2e, p, q);}

/* (5) Chuyển đổi sang biểu diễn dạng kinh điển. */

for (j = 0; j < n; j++) {

pa[j] = mont_mul(pa[j], 1, p, q); }}

/*

* 6) Sử dụng thuật toán Garner để tái cấu trúc kết quả.

*/

P17

#pragma omp parallel for default(none) shared(dft, crt, a, b, c, dft_a, dft_b,

deg_c, primes, n) \

private(pa, pb, ha, la, hb, lb, p, q, r, ir, s, t, i2e, m, bs, i, j, k)

for (i = 0; i <= deg_c; i++) {

pa = dft_a + i;

pb = dft_b + i * primes;

memset(pb, 0, primes * sizeof(uint32_t));

pb[0] = pa[0];

for (j = 1; j < primes; j++) {

t = ARTH_mod_digit(pb, j, crt.p[j]);

if (t != 0) {

t = crt.p[j] - t;}

t += pa[j * n];

if ((t < pa[j * n]) || (crt.p[j] <= t)) {

t -= crt.p[j];}

t = mod_mul(t, crt.c[j], crt.p[j]);

ARTH_mul_digit_add(pb, j + 1, crt.pp + j * crt.n, j, t);}}

UINT_Poly_clear(c);

/* Xác định số chữ số tối đa cho hệ số c. */

c->digits = 1;

for (i = 0; i <= deg_c; i++) {

pb = dft_b + i * primes;

for (j = 0; j < primes; j++) {

if ((pb[j] != 0) && (c->digits <= j)) {

c->digits = j + 1;}}}

/* Copy kết quả. */

c->deg = deg_c;

c->v = calloc(c->deg + 1, sizeof(uint32_t *));

for (i = 0; i <= deg_c; i++) {

c->v[i] = calloc(c->digits, sizeof(uint32_t));

pb = dft_b + i * primes;

P18

for (j = 0; j < c->digits; j++) {

c->v[i][j] = pb[j];}}

free(dft_a);

free(dft_b);

return 0;}

P19

fileArth.c: CRT và các hàm số học

static uint32_tmod_mul(uint32_t a, uint32_t b, uint32_t m)

{

uint32_t c = 0;

ARTH_MUL(a, a, b, c);

ARTH_DIV(c, a, c, a, m);

return a;}

static uint32_t

mod_exp(uint32_t a, uint32_t e, uint32_t m)

{

uint32_t t = 1;

while (e) {

if (e & 1) {

t = mod_mul(t, a, m);

}

a = mod_mul(a, a, m);

e >>= 1;}

return t;}

intARTH_cmp(const uint32_t * op1, int len1, const uint32_t * op2, int len2)

{

int len = len1;

int i;

if (len2 < len1) {

len = len2;

}

for (i = len - 1; i > -1; i--) {

if (op1[i] < op2[i]) {

return 1;}

else if (op1[i] > op2[i]) {

return -1;}}

if (len1 < len2) {

return ARTH_cmp_digit(op2 + len1, 0, len2 - len1);}

else if (len2 < len1) {

return ARTH_cmp_digit(op1 + len2, 0, len1 - len2);}

return 0;

}

IntARTH_cmp_digit(const uint32_t * op1, uint32_t op2, int len)

{

int i;

for (i = len - 1; i > 0; i--) {

if (op1[i] != 0) {

return -1;}}

if (op1[0] < op2) {

return 1;}

else if (op1[0] > op2) {

return -1;}

return 0;}

intARTH_add(uint32_t * dst, const uint32_t * src, int len)

{

uint32_t c = 0;

int i;

for (i = 0; i < len; i++) {

ARTH_ADC(dst[i], dst[i], src[i], c);}

return (int)c;}

intARTH_add_digit(uint32_t * dst, uint32_t src, int len)

{

uint32_t c = 0;

P20

int i;

ARTH_ADC(dst[0], dst[0], src, c);

if (c == 1) {

for (i = 1; i < len; i++) {

dst[i] += 1;

if (dst[i] != 0) {

return 0;}}}

return (int)c;}

uint32_tARTH_mul_digit(uint32_t * a, int na, uint32_t b)

{

uint32_t c = 0;

int i;

for (i = 0; i < na; i++) {

ARTH_MUL(a[i], a[i], b, c);}

return c;}

uint32_tARTH_mul_digit_add(uint32_t * a, int na, const uint32_t * b, int nb,

uint32_t d)

{

uint32_t c = 0;

int i;

for (i = 0; i < nb; i++) {

ARTH_MUL_ADD(a[i], b[i], d, c);}

for (i = nb; i < na; i++) {

ARTH_ADC(a[i], a[i], 0, c);}

return c;}

voidARTH_mul(uint32_t * d, const uint32_t * a, int na, const uint32_t * b, int

nb)

{

uint32_t c;

int i;

int j;

P21

for (i = 0; i < na + nb; i++) {

d[i] = 0;}

for (i = 0; i < na; i++) {

c = 0;

for (j = 0; j < nb; j++) {

ARTH_MUL_ADD(d[i + j], a[i], b[j], c);}

d[i + j] = c;}}

uint32_tARTH_mod_digit(const uint32_t * a, int na, uint32_t b)

{

uint32_t q = 0;

uint32_t r = 0;

while (na--) {

ARTH_DIV(q, r, r, a[na], b)}

return r;}

intARTH_Fp32_crt_init(ARTH_Fp32_crt * crt, const uint32_t * p, int n)

{

int i, j;

crt->n = n;

/* Alokacja pamięci. */

if ((crt->p = calloc(crt->n, sizeof(uint32_t))) == 0) {

return -1;}

if ((crt->c = calloc(crt->n, sizeof(uint32_t))) == 0) {

free(crt->p);

return -1;}

if ((crt->pp = calloc(crt->n * crt->n, sizeof(uint32_t))) == 0) {

free(crt->p);

free(crt->c);

return -1;}

/* Copy số nguyên tố. */

for (i = 0; i < n; i++) {

crt->p[i] = p[i];

}

P22

/* Tính toán các hệ hệ sô cho thuật toán Garner:

*

* q[i] = (p[0]*p[1]*...*p[i-1])^(-1) mod p[i]

* pp[i*n] = p[0]*p[1]*...*p[i-1]

*/

for (i = 0; i < n; i++) {

crt->c[i] = 1;

for (j = 0; j < i; j++) {

crt->c[i] =

mod_mul(crt->c[i], mod_exp(crt->p[j], crt->p[i] - 2, crt-

>p[i]),

crt->p[i]);}}

crt->pp[0] = 1;

for (i = 1; i < n; i++) {

crt->pp[i * n] = crt->p[0];}

for (i = 1; i < n - 1; i++) {

for (j = i + 1; j < n; j++) {

crt->pp[j * n + i] = ARTH_mul_digit(crt->pp + j * n, i, crt-

>p[i]);}}

return 0;}

VoidARTH_Fp32_crt_free(ARTH_Fp32_crt * crt)

{

if (crt->p) {

free(crt->p);

crt->p = 0;}

if (crt->c) {

free(crt->c);

crt->c = 0;}

if (crt->pp) {

free(crt->pp); crt->pp = 0;}}

P23

P24

#include #include "FiniteFieldElement.hpp"

#include "sha256.hpp"

#include "rijndael.h"

namespace Cryptography {

template

class EllipticCurve

{

public: typedef FiniteFieldElement
ffe_t;

class Point

{

friend class EllipticCurve
;

typedef FiniteFieldElement
ffe_t; ffe_t x_;

ffe_t y_;

EllipticCurve *ec_;

void addDouble(int m, Point& acc)

{

if ( m > 0 )

{

Point r = acc;

for ( int n=0; n < m; ++n )

{

r += r; // doubling step } acc = r; } } Point scalarMultiply(int k, const Point& a)

{

Phụ lục 3. MODULE CHƯƠNG TRÌNH TRAO ĐỔI KHÓA

Point acc = a;

Point res = Point(0,0,*ec_);

int i = 0, j = 0; int b = k;

while( b )

{ if ( b & 1 )

{ // bit is set; acc = 2^(i-j)*acc addDouble(i-j,acc);

res += acc;

j = i; // last bit set

} b >>= 1;

++i;

}

return res;

}

void add(ffe_t x1, ffe_t y1, ffe_t x2, ffe_t y2, ffe_t & xR, ffe_t &

yR) const

{ if ( x1 == 0 && y1 == 0 )

{ xR = x2;

yR = y2;

return;

}

if ( x2 == 0 && y2 == 0 )

{xR = x1;

yR = y1; return;

} if ( y1 == -y2 ) {xR = yR = 0; return; } ffe_t s; if ( x1 == x2 && y1 == y2 )

P25

{ s = (3*(x1.i()*x1.i()) + ec_->a()) / (2*y1);

xR = ((s*s) - 2*x1);

} else

{

//P+Q

s = (y1 - y2) / (x1 - x2); xR = ((s*s) - x1 - x2); }

if ( s != 0 )

{ yR = (-y1 + s*(x1 - xR));

} else

{ xR = yR = 0;

}

}

Point(int x, int y) : x_(x), y_(y), ec_(0) {}

Point(int x, int y, EllipticCurve
& EllipticCurve): x_(x), y_(y),

ec_(&EllipticCurve) {}

Point(const ffe_t& x, const ffe_t& y, EllipticCurve
&

EllipticCurve)

: x_(x),y_(y), ec_(&EllipticCurve) {}

public:

static Point ONE;

Point(const Point& rhs)

{x_ = rhs.x_;

y_ = rhs.y_; ec_ = rhs.ec_;}

Point& operator=(const Point& rhs) {x_ = rhs.x_; y_ = rhs.y_; ec_ = rhs.ec_; return *this; } ffe_t x() const { return x_; }

P26

ffe_t y() const { return y_; }

unsigned int Order(unsigned int maxPeriod = ~0) const

{Point r = *this; unsigned int n = 0;

while( r.x_ != 0 && r.y_ != 0 )

{ ++n;

r += *this; if ( n > maxPeriod ) break; }

return n; }

Point operator-()

{ return Point(x_,-y_);} friend bool operator==(const Point& lhs, const Point& rhs)

{

return (lhs.ec_ == rhs.ec_) && (lhs.x_ == rhs.x_) && (lhs.y_ ==

rhs.y_);

}

// !=

friend bool operator!=(const Point& lhs, const Point& rhs)

{ return (lhs.ec_ != rhs.ec_) || (lhs.x_ != rhs.x_) || (lhs.y_ !=

rhs.y_);

}

friend Point operator+(const Point& lhs, const Point& rhs)

{ ffe_t xR, yR;

lhs.add(lhs.x_,lhs.y_,rhs.x_,rhs.y_,xR,yR);

return Point(xR,yR,*lhs.ec}

friend Point operator*(int k, const Point& rhs) { return Point(rhs).operator*=(k);}

Point& operator+=(const Point& rhs) { add(x_,y_,rhs.x_,rhs.y_,x_,y_); return *this } Point& operator*=(int k) { return (*this = scalarMultiply(k,*this)); } friend ostream& operator <<(ostream& os, const Point& p) {return (os << "(" << p.x_ << ", " << p.y_ << ")");} };

P27

EllipticCurve(int a, int b)

: a_(a),

b_(b), m_table_(),

void CalculatePoints()

{ int x_val[P];

int y_val[P]; for ( int n = 0; n < P; ++n )

{int nsq = n*n;

x_val[n] = ((n*nsq) + a_.i() * n + b_.i()) % P;

y_val[n] = nsq % P} for ( int n = 0; n < P; ++n )

{ for ( int m = 0; m < P; ++m )

{ if ( x_val[n] == y_val[m] )

{m_table_.push_back(Point(n,m,*this)); } } }

table_filled_ = true;

}

// get a point (group element) on the curve

Point operator[](int n)

{

if ( !table_filled_ )

{

CalculatePoints(); }

return m_table_[n];

}

// number of elements in this group size_t Size() const { return m_table_.size(); }

// the degree P of this EC int Degree() const { return P; } // the parameter a (as an element of Fp) FiniteFieldElement
a() const { return a_; } // the paramter b (as an element of Fp) FiniteFieldElement
b() const { return b_; }

P28

// ostream handler: print this curve in human readable form

template

friend ostream& operator <<(ostream& os, const EllipticCurve&

EllipticCurve);

// print all the elements of the EC group

ostream& PrintTable(ostream &os, int columns=4);

private:

typedef std::vector m_table_t;

m_table_t m_table_; // table of points FiniteFieldElement
a_; // paramter a of the EC equation

FiniteFieldElement
b_; // parameter b of the EC equation

bool table_filled_; // true if the table has been calculated

};

ostream& operator <<(ostream& os, const EllipticCurve& EllipticCurve)

{

os << "y^2 mod " << T << " = (x^3" << showpos;

if ( EllipticCurve.a_ != 0 )

{

os << EllipticCurve.a_ << "x"; }

if ( EllipticCurve.b_.i() != 0 )

{

os << EllipticCurve.b_; }

os << noshowpos << ") mod " << T;

return os; } template

ostream& EllipticCurve
::PrintTable(ostream &os, int columns) { if ( table_filled_ ) { int col = 0; typename EllipticCurve
::m_table_t::iterator iter =

m_table_.begin();

P29

for ( ; iter!=m_table_.end(); ++iter )

{

os << "(" << (*iter).x_.i() << ", " << (*iter).y_.i() << ") "; if ( ++col > columns )

{

os << "\n";

col = 0; }

}

}

else {

os << "EllipticCurve, F_" << P;

}

return os;

}

}

unsigned long rk[RKLENGTH(KEYBITS)]; // --> rk[256/8 + 28] = rk[60] :=

60 phan tu

unsigned char key[KEYLENGTH(KEYBITS)] =

{0x60,0x3d,0xeb,0x10,0x15,0xca,0x71,0xbe,0x2b,0x73,0xAE,0xF0,0x85,0x7d,0x7

7,0x81,0x1F,0x35,0x2C,0x07,0x3B,0x61,0x08,0xD7,0x2D,0x98,0x10,0xA3,0x09,

0x14,0xDF,0xF4}; //0x2E

unsigned char plaintext[16];

unsigned char ciphertext[16]= {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00};

unsigned char IV_InputE[16] = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06,

0x07, 0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F};

unsigned char IV_InputD[16] = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06,

0x07, 0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F};

unsigned char IV_Output[16]; int nrounds; char iv_count=0;

P30

int main(int argc, char *argv[])

{

typedef EllipticCurve<263> ec_t; int A,B,N,D;

unsigned int m1[50],m2[50],m1d[50],m2d[50];

int i;

char data[100]; ec_t::ffe_t encrypt_c[100],decrypt_c[100];

for (i=0;i<=100;i++)

{

data[i]=0;}

cout << "Elliptic Curve Diffie-Hellman Key agreement demonstration

example \n Created by Ba Anh Dao _ Academy of Cryptography Technique \n\n";

cout << "Please enter two parameters A & B of the Elliptic Curve:\n";

cout << "A =\n";

cin >> A;

cout << "\n";

cout << "B =\n";

cin >> B;

cout << "\n";

ec_t myEllipticCurve(A,B);

cout << "The elliptic curve: " << myEllipticCurve << "\n";

myEllipticCurve.CalculatePoints();

myEllipticCurve.PrintTable(cout,5); cin >> N;

int n = (int)(frand()*myEllipticCurve.Size()); ec_t::Point G = myEllipticCurve[n]; while( (G.y() == 0 || G.x() == 0) || (G.Order()<2) ) { int n = (int)(frand()*myEllipticCurve.Size()); G = myEllipticCurve[n]; } cout << "G = " << G << ", order(G) is " << G.Order() << "\n";

P31

// Calculate the Public key = Base point * random number

int Private_key[N];

ec_t::Point Public_key[N]=G;

for (int n=0; n<=N; n++)

{

Private_key[n] = irand(1,myEllipticCurve.Degree()-1);

cout << "Person A" << n <<" has the private, random number " <<

Private_key[n] << endl;

Public_key[n] = Private_key[n] * G;

cout << "Person A" << n <<" has the public key " << Public_key[n]

<< endl;

cout << endl;

}

// Key agreement for A.0 to A.N-1; A.N does not have agreed key

for (int l=0; l
{

ec_t::Point temp_point = Public_key[N-1];

for(int l1=N-1 ; l1>0 ; l1--)

{

Public_key[l1] = Private_key[l1] * Public_key[l1-1];

}

Public_key[0] = Private_key[0]*temp_point;

/* xem qua trinh thoa thuan khoa*/

for (int n=0; n<=N; n++)

{

cout << "Public_key_" << n <<" = " << Public_key[n] << endl;

}

cout << endl;

sstr << Public_key[0].x(); std::string str1 = sstr.str(); string output1 = sha256(str1);

} std::stringstream sstr; // cout << output1 << endl;

P32

const char *src = &output1[0];

unsigned char test[32];

unsigned char *dst = key; unsigned char *end = key + sizeof(key);

unsigned int u;

while (dst < end && sscanf(src,"%2x", &u) == 1)

*dst++ = u&0xff;

{

src += 2;

}

for (int i=0;i<32;i++) {printf("%2.2x",key[i]);

}

nrounds = rijndaelSetupEncrypt(rk, key, KEYBITS);

cout << endl;

// Input image file

FILE *f_in,*f_out;

unsigned char *buffer ;

long filelen;

f_in = fopen("flower.jpg", "rb"); // Open the file in binary mode

fseek(f_in, 0, SEEK_END); // Jump to the end of the file

filelen = ftell(f_in); // Get the current byte offset in the file

long cryptlen = filelen / 16;

rewind(f_in); // Jump back to the beginning of the file

buffer = (unsigned char *)malloc((filelen+1)*sizeof(char)); // Enough

memory for file + \0

f_out = fopen("encrypted.bin","wb");

for (int i=0; i
fread(buffer, 16, 1, f_in); if (i%2==0) {

{ AES_OFB(rk,nrounds,IV_InputE,IV_Output,buffer,ciphertext);

P33

fwrite(ciphertext,16,1,f_out);

}

else {

AES_OFB(rk,nrounds,IV_Output,IV_InputE,buffer,ciphertext);

}

fwrite(ciphertext,16,1,f_out);

}

fclose(f_in);

fclose(f_out);

cout << "A.0 encrypted the image, who will decrypt it? A...? \n";

cin >> D;

std::stringstream sstr2;

sstr2 << Public_key[D].x();

str1 = sstr2.str();

output1 = sha256(str1);

src = &output1[0];

dst = key;

while (dst < end && sscanf(src,"%2x", &u) == 1)

{

*dst++ = u&0xff;

src += 2;

}

for (int i=0;i<32;i++)

{printf("%2.2x",key[i]); }

f_in = fopen("encrypted.bin", "rb"); // Open the file in binary mode fseek(f_in, 0, SEEK_END); // Jump to the end of the file filelen = ftell(f_in); // Get the current byte offset in the file

nrounds = rijndaelSetupEncrypt(rk, key, KEYBITS); cout << endl; // Input image file cryptlen = filelen / 16;

P34

rewind(f_in); // Jump back to the beginning of the file

buffer = (unsigned char *)malloc((filelen+1)*sizeof(char)); // Enough

memory for file + \0

f_out = fopen("decrypted.jpg","wb");

for (int i=0; i
fread(buffer, 16, 1, f_in);

{

if (i%2==0)

{

AES_OFB(rk,nrounds,IV_InputD,IV_Output,buffer,ciphertext);

fwrite(ciphertext,16,1,f_out);

}

else

{

AES_OFB(rk,nrounds,IV_Output,IV_InputD,buffer,ciphertext);

fwrite(ciphertext,16,1,f_out);

}

}

fclose(f_in);

fclose(f_out);

cout << endl;

system("PAUSE");

return EXIT_SUCCESS;

}

P35

Luận án Tiến sĩ Toán học: Nghiên cứu một số giải pháp nâng cao hiệu năng của thuật toán mã hóa

Tags: