1
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
---------------------------------------
Hoàng Thị Xuân
NGHIÊN CỨU HỆ MẬT ĐƯỜNG CONG ELLIPTIC VÀ ỨNG DỤNG
LUẬN VĂN THẠC SĨ KỸ THUẬT
HÀ NỘI - 2013
Luận văn được hoàn thành tại:
2
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
Người hướng dẫn khoa học: GS. Nguyễn Bình
Phản biện 1: ……………………………………………………………………………
Phản biện 2: …………………………………………………………………………..
Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công nghệ
Bưu chính Viễn thông
Vào lúc:
....... giờ ....... ngày ....... tháng ....... .. năm ...............
Có thể tìm hiểu luận văn tại:
- Thư viện của Học viện Công nghệ Bưu chính Viễn thông
3
MỞ ĐẦU
Lý do chọn đề tài
Sự phát triển của công nghệ thông tin, truyền thông nói chung và Internet nói riêng đã giúp cho việc trao đổi thông tin nhanh chóng, dễ dàng. Do vậy một số vấn đề phát sinh là thông tin có thể bị trộm cắp, có thể sai lệch, có thể giả mạo. Điều đó có thể ảnh hưởng đến các tốc chức, các công ty hay cả một quốc gia. Để giải quyết tình hình trên an toàn thông tin được đặt ra cấp thiết. Kỹ thuật mật mã là một trong những giải pháp của an toàn truyền thông. Các nhà khoa học đã phát minh ra những hệ mật ma nhằm che dấu thong tin cũng như là làm rõ chúng để tránh kẻ cố tình phá hoạt các hệ mật: RSA, Elgamal …
Đối tượng và phạm vi nghiên cứu
Đối tượng nghiên cứu của Luận văn:
- Cơ sở toán học hệ mật dựa trên các đường cong Elliptic.
- Các tấn công và độ phức tạp của các tấn công trên hệ mật Elliptic.
- Giao thức bảo mật mạng sử dụng hệ mật Elliptic.
Phạm vi nghiên cứu của Luận văn:
- Luận văn tập trung tìm hiểu về các đánh giá tấn công hệ mật đường cong Elliptic, tìm
hiểu một số hệ mật trên các đường cong Elliptic.
- Dựa trên các cơ sở lý thuyết và tìm hiểu, xây dựng ứng dụng bảo mật mạng riêng ảo
sử dụng hệ mật Elliptic.
Mục đích nghiên cứu
- Làm rõ các phương pháp tấn công trong hệ mật đường cong Elliptic.
- Ứng dụng trong một bài toán bảo mật mạng cụ thể.
Bố cục luận văn:
Luân văn này gồm 03 chương cùng với phần mở đầu, kết luận và các danh mục: Chương 1: Tổng quan về hệ mật đường cong Elliptic Chương 2: Mật mã đường cong Elliptic Chương 3:Ứng dụng trong bài toán bảo mật mạng riêng ảo
CHƯƠNG I – TỔNG QUAN VỀ HỆ MẬT ĐƯỜNG CONG ELLIPTIC
1.1 Cơ sở toán học hệ mật đường cong Elliptic
1.1.1 Các định nghĩa
Định nghĩa 1.
4
Một đường cong Elliptic dạng Weierstrass đầy đủ là tập tất cả các điểm với 3 tọa độ
x, y, z thỏa mãn phương trình:
(1.1) Với
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:
(1.2) với
Định nghĩa 2: Biệt thức của đường cong E được xác định bởi công thức:
(1.3)
Định nghĩa 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 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 được coi là đường cong kì dị. Định nghĩa 5:
(1.4)
Đại lượng j – bất biến của đường cong E khi là:
Định nghĩa 6:
sao cho khi thực hiện đổi biến và
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 thì E hằng số biến thành E’.
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 .
Định nghĩa 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:
(1.5)
Định nghĩa 8:
Một đườ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 bậc p.
5
Định nghĩa 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.
1.1.2 Hệ mật dựa trên đường cong Elliptic
Tập hợp tất cả các điểm với thỏa mãn phương trình của đường cong E
và với một điểm nhóm các điểm trên đường cong Elliptic trong ở 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à , ký hiệu là .
Phép cộng đ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 , đường
thẳng này sẽ cắt tại điểm thứ hai chính là điểm .
Phép nhân đôi một điểm: Cho là một điểm trên . 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 , tiếp
tại điểm thứ hai, ký hiệu là . Kẻ đường thẳng đi qua và vuông
tuyến này cắt góc với trục , đường thẳng này cắt tại điểm thứ hai chính là .
Cho 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 với . Khi đó với
được tính như sau:
(1) (Công thức cộng điểm) Nếu , thì
, . , với
(2) Nếu nhưng , thì .
(3) (Công thức nhân đôi điểm) Nếu , thì và
, với
. (4) Nếu và , thì
. (5)
Phép cộng điểm trên đường cong Elliptic
Tính giao hoán: thỏa mãn các tính chất sau: với mọi trên . (1)
Tồn tại phần tử đơn vị: với mọi trên . (2)
, tồn tại một điểm
. Điểm thường được kí hiệu là cho trước trên .
Tồn tại phần tử nghịch đảo: Với điểm sao cho Tính kết hợp: . (3) trên (4)
1.1.2.1 Các tự đồng cấu
6
Một tự đồng cấu nghĩa là một đồng cấu được cho bởi các hàm hữu
tỉ. Nói cách khác, , và có các hàm hữu tỉ (thương của các đa chức)
, với các hệ số trong sao cho
Một tự đồng cấu được gọi là tự đồng cấu tách được nếu đạo hàm
1.1.2.2 Các điểm n – xoắn
không đồng nhất bằng không.
Các điểm xoắn, chính là các điểm có bậc hữu hạn, đóng một vai trò quan trọng trong là một đường cong Ellip được xác định trên một . Giả sử n là một số nguyên dương. Theo [6] tập các điểm n-xoắn được định nghĩa
nghiên cứu các đường cong Elliptic. Cho trường bởi:
1.1.2.3 Đa thức chia
(1.7)
Đa thức chia thứ - m của đường cong Elliptic , , được xác định bởi
dãy các công thức toán học truy hồi sau đây:
Với
Với .
Cho là một điểm trên đường cong Elliptic (trên một trường
nào đó có đặc số khác 2), và là một số nguyên dương. Khi đó:
(1.8)
1.1.3 Cặp Weil
Cho là một đường cong Elliptic trên một trường và cho là một số nguyên không
chia hết cho đặc số của . Khi đó . Đặt:
(1.9)
. Vì đặc số của
hết cho Là nhóm của các căn bậc , nên phương trình của phần tử đơn vị trong không có nghiệm bội, do đó nó có nghiệm trong không chia . Do
7
vậy, là một nhóm cyclic bậc . Một phần tử sinh của được gọi là một căn nguyên
. Điều này tương đương với việc nói rằng khi và chỉ khi chia hết cho .
thủy bậc Định lý [6 – Theorem 3.9]:
Cho là một đường cong Elliptic xác định trên một trường và cho
không chia hết cho là một số . Khi đó một phép
nguyên dương. Giả sử rằng đặc số của trường ghép cặp:
(1.10)
1.2 Đường cong Elliptic
1.2.1 Đặt vấn đề bài toán
Đường cong elliptic là tập hợp các điểm có toạ độ thoả mãn phương trình có
dạng sau đây:
(1.11) Trên trường F biểu diễn bằng phương trình Weiretrass:
Xét đường cong trên trường nguyên tố hữu hạn ( nguyên tố, >3 ) với công
thức biến đổi như sau:
(1.12)
Hình 1: Một ví dụ về đường cong Elliptic
là một trường có đặc số khác 2 và khác 3 và xét đa thức
Định nghĩa: Giả sử ). Khi đó đường cong elliptic trên trường : (với a, là tập hợp tất cả các
b điểm (x, y) với x, y sao cho (1.12) không có các nghiệm bội tức là
cùng với phần tử O - điểm O này được gọi là điểm vô hạn. Tính chất của đường cong elliptic:
8
Nếu hai điểm và với nằm trên đường cùng một đường
và
cong elliptic , thì đường thẳng qua hai điểm sẽ cắt một điểm duy nhất
và
có thể xác định thông qua nằm trên đường cong .
Tiếp tuyến của đường cong tại điểm bất kỳ trên đường cong cũng cắt đường
tại một điểm duy nhất nằm trên đường , điểm này cũng có thể xác định được
cong elliptic thông qua P.
1.2.2 Đường cong elliptic trên trường hữu hạn
Xét trường hữu hạn của phần tử trên trường hữu hạn . Giả sử E là đường
cong elliptic được định nghĩa trên . Nếu đặc số của trường hoặc thì E được
cho bởi phương trình ở (1.13) và (1.14) .
Định lý: Gọi N là số các điểm trên đường cong elliptic được định nghĩa trên . Khi
đó
1.2.3.1 Phép cộng
1.2.3 Các phép toán trên đường cong Elliptic
Giả sử P = (x1, y1) và Q (x2, y2) là hai điểm của E. Nếu x1 = x2 và y1 = - y2 thì ta định
,
nghĩa P + Q = O. Ngược lại thì P + Q = (x3, y3) E trong đó:
Với:
là hệ số góc đường
Khi P ≠ Q( nếu x1 = x2 th ì thẳng qua P và Q) (1.17)
Khi P = Q ( là đạo hàm của đường cong tại P) (1.18)
9
2
R 1
Q
R P
2P
P+ Q
P -1
-2
Hình 2: Phép cộng trên đường cong Elliptic
Tính chất
Dễ thấy rằng tập E với phép toán cộng đó tạo thành một nhóm Abelian: Tính đóng: Nếu P, Q E thì P + Q E. Tính kết hợp: Nếu P, Q, R E thì P + ( Q + R ) = R + ( Q + P ). Tồn tại phần tử trung hoà O: với mọi P Tồn tại phần tử nghịch đảo: với mỗi E thì P + O = O + P = P (theo định nghĩa). thì luôn tồn tại phần tử
để P + (-P) = O.
1.2.3.2 Phép nhân
Tính chất giao hoán: Nếu P, Q E thì P + Q = Q + P.
được Phép nhân một số nguyên k với một điểm P thuộc đường cong elliptic E là điểm Q nhiên k điểm bằng cách định xác và dĩ P lần
cộng ( k phép cộng điểm P).
10
Hình 3: Ví dụ phép nhân đôi trên đường cong Elliptic
1.2.4.1 Định lý Hasse
1.2.4 Đếm số điểm trên đường cong Elliptic trên trường
N là số điểm của E trên trường Fq (trường hữu hạn q phần tử). Khi đó:
. Từ định lý Hasse suy ra trong đó
1.2.4.2 Định nghĩa
.
Bậc của điểm G thuộc E là số k dương bé nhất sao cho kG = O; khi k = #E(Fq) thì G là
điểm cơ sở của E.
1.2.5.1 Trường
1.2.5 Phương pháp chọn đường cong Elliptic phù hợp và điểm cơ sở
Một đường cong elliptic trên một trường hữu hạn tạo thành nhóm Abelian được sử
dụng trong mật mã học. Một ví dụ là việc chọn trường giúp thực hiện các phép tính nhanh
và dễ dàng triển khai được trên các thiết bị cứng. Tuy nhiên, các đường cong trên trường
có thể bị tấn công bởi MOV, trong khi các đường cong trên trường (p là số nguyên tố lớn)
lại chống lại được kiểu tấn công này. Một chú ý nữa là việc tính số điểm trên # . Tốc
1.2.5.2 Dạng của đường cong elliptic
độ của thuật toán Shoof phụ thuộc vào kích thước và đặc số của trường K.
Trên trường Fq có hai lớp đường cong elliptic được dùng trong các hệ mã hoá là
. Khi đó: supersingular. Xét Fq có đặc số là
11
Tập tất cả các cặp nghiệm (x, y) của phương trình với a, b,
c Fq và a = 0 (mod q) cùng với điểm trung hoà O tạo thành một đường cong elliptic dạng supersin gular.
Tập tất cả các cặp nghiệm (x, y) của phương trình với a, b,
Fq và b = 0 (mod q) cùng với điểm trung hoà O tạo thành một đường cong elliptic
1.2.5.3 Phương pháp lựa chọn
c dạng non-supersingular.
Phương pháp- Phương pháp chọn ngẫu nhiên Kobliz:
(1) .Chọn ngẫu nhiên 3 phần tử từ Fq là x, y, a (2) .Tính b = y2 – (x3 + ax) (3) .Kiểm tra 4a3 + 27b2 ≠ 0 để đảm bảo phương trình x3 + ax + b =0 không có nghiệm
kép.
(4) .Nếu điều kiện trên không thoả mãn quay lại bước 1. (5) .Còn lại, đặt P = (x, y) và đường cong y2 = x3 + ax +b là đường cong cần chọn.
1.2.6.1 Phương pháp Pohlig - Hellman
1.2.6 Đánh giá các tấn công hệ mật đường cong Elliptic
Cho là các phần tử trong nhóm hữu hạn G bậc N. Ta muốn tìm một số nguyên k
với . Giả sử biết phân tích ra thừa số nguyên tố của N là:
1.2.6.2 Tấn công MOV
Phương pháp Pohlig – Hellman thực hiện tốt nếu tất cả các ước nguyên tố của N là nhỏ. Nếu ước nguyên tố lớn nhất xấp xỉ lớn của N thì phương pháp Pohlig – Hellman rất khó áp dụng. Vì lý do này, các hệ mật dựa trên logarith rời rạc, nói chung thường chọn bậc của nhóm có chứa một thừa số nguyên tố lớn.
Thuật toán 1: Tấn công MOV
, , Input: ,
Output:
(1). Chọn một điểm ngẫu nhiên
(2). Tính bậc M của T
12
, đặt . Khi đó có bậc chia hết cho , (3). Đặt
vậy
(4). Tính và . Khi đó cả , đều thuộc vào
(5). Giải bài toán log rời rạc trong . Kết quả cho ta .
1.2.6.3 Phương pháp Xedni
(6). Lặp lại với các điểm ngẫu nhiên T đến khi bội chung nhỏ nhất của các số d khác nhau thu được là N. Khi đó ta xác định được
Thuật toán tính chỉ số ngược đầu tiên là nâng các điểm , sau đó chọn một
đường cong Elliptic chứa các điểm đã nâng và hy vọng rằng chúng phụ thuộc tuyến
tính. Nghĩa là thỏa mãn quan hệ . Tuy nhiên, xác suất để chúng phụ thuộc tuyến
1.2.6.4 Các tấn công dựa trên giả thuyết Diffie – Hellman
tính là nhỏ.
Cho G là một nhóm Abel bậc nguyên tố và là phần tử sinh của G. Bài toán
logarith rời rạc DLP trong G là bài toán tìm số khi biết và trong G. Nhiều hệ
mật được thiết kế dựa trên bài toán DLP, tuy nhiên hầu hết chúng có độ an toàn tương đương với một biến thể yếu hơn của bài toán DLP. Hai biến thể yếu hơn quan trọng nhất là bài toán DH – Tính toán CDH và bài toán DH – Quyết định DDH.
CDH: Cho . Tính ?
1.2.6.5 Các tấn công cài đặt
DDH: Cho . Xác định xem trong hay không?
Kiểu tấn công cài đặt thứ nhất là dựa trên điểm không hợp lệ của đường cong Elliptic. Nếu trong quá trình nhận và xử lý một điểm trên đường cong mà không thực hiện việc kiểm tra xem nó có thực sự nằm trên đường cong đã cho hay không thì lược đồ có thể bị tấn công.
Dạng tấn công thứ hai là kiểu tấn công phân tích năng lượng để khám phá khóa bí mật..
1.2.6.6 Nhận xét
Hiệu quả của các kiểu tấn công này phụ thuộc vào cách cài đặt cụ thể.
Tổng hợp các phương pháp trên ta có bảng như sau:
13
Bảng 1: So sánh các phương pháp tấn công hệ mật Elliptic
STT Phương Ghi chú
Độ phức tạp của thuật toán trong nhóm có bậc là N Yêu cầu bộ nhớ pháp
1 - Nhỏ với K là ước nguyên tố Pohlig Hellman Hiệu quả nếu N chỉ có các ước nguyên tố nhỏ. lớn nhất của N
2 MOV Nhỏ Hiệu quả nếu nhỏ ~
3 Xedni -
Không áp dụng được trong thực tế
4 thuyết với d là ước của
Yêu cầu giả mạnh, cần bộ nhớ lớn
5 Nhỏ
Tấn công dựa vào một số giả thuyết DH Tấn công cài đặt Phụ thuộc vào cách cài đặt cụ thể Thời gian đa thức theo Conron.
Kết luận chương
Các kết quả mà chương 1 đạt được bao gồm:
(1) Đã nghiên cứu tổng quan về hệ mật Elliptic trên trường hữu hạn, nghiên cứu về các
vấn đề như đa thức chia, nhóm con xoắn, các tự đồng cấu, Weil pairing.
(2) Nghiên cứu, xem xét và đánh giá về độ phức tạp tính toán, yêu cầu bộ nhớ và khả năng
áp dụng trong thực tế của các tấn công đối với hệ mật Elliptic.
CHƯƠNG 2 – MẬT MÃ ĐƯỜNG CONG ELLIPTIC
2.1 Mật mã đường cong Elliptic
2.1.1 Thiết lập cơ sở
Alice muốn gửi một văn bản, thường được gọi là bản rõ (Plaintext), tới Bob. Cô ấy mã hóa văn bản để thu được bản mã (Ciphertext). Để mã hóa văn bản, Alice sử dụng một khóa mã hóa (Encryption key). Bob sử dụng một khóa giải mã (Decryption key) để giải mã bản mã nhận được.
Có hai cách mã hóa cơ bản. Trong mật mã đối xứng (Symmetric Encryption), khóa
mã hóa và khóa giải mã là như nhau,
Một dạng khác của mã hóa là mật mã khóa công khai (Public Key Encryption),
hoặc mật mã không đối xứng (Asymmetric Encryption).
14
Hình 4: Mô phỏng mã hóa công khai
2.1.2 Nhúng bản rõ lên đường cong
Nhúng bản rõ lên E là biểu diễn lại bản rõ đó như là các điểm trên E, nhờ đó có thể thực hiện được các tính toán trên E. Có một số phương pháp để thực hiện việc này. Trong đó có 2 phương pháp chính là “nhúng” (Imbeding) và “mặt nạ” (Mask).
2.1.3. Logarith rời rạc trên đường cong Elliptic
Định nghĩa:
E là đường cong Elliptic trên trường Fq và B là một điểm trên E. Khi đó bài toán logarit , tìm số nguyên
rời rạc trên E (theo cơ số B) là một bài toán, cho trước một điểm sao cho xB = P (nếu số x như vậy tồn tại)
2.1.4 Trao đổi khóa Diffie – Hellman
2.1.4.1 Bài toán Diffie – Hellman
Alice và Bob muốn thống nhất một khóa chung mà họ có thể sử dụng cho việc trao đổi dữ liệu thông qua một sơ đồ mã đối xứng. Alice và Bob thống nhất một đường cong elliptic E trên trường hữu hạn Fq sao cho bài toán logarithm rời rạc là khó trong E(Fq). Thông tin duy nhất mà kẻ trộm Eve thấy chỉ là đường cong E, trường hữu hạn Fq, và các điểm P, aP và bP. Do đó cô ta cần phải giải quyết các bài toán sau:
2.1.4.2 Bài toán quyết định Diffie – Hellman
Cho trước P, aP và bP trong E(Fq), tính abP? Nếu Eve có thể giải bài toán log rời rạc trong E(Fq), khi đó cô ta có thể sử dụng P và aP để tìm a. Khi đó cô ta có thể tính a(bP) để nhận được abP. Tuy nhiên, liệu có thể có cách nào để tính abP mà không phải giải bài toán log rời rạc đầu tiên.
Cho trước P, aP và bP trong E(Fq) và cho trước một điểm Q ∈ E(Fq). Khi đấy có xác
định được Q = abP hay không?
15
Cho E là đường cong trên Fq, với q ≡ 2 (mod 3). Theo mệnh đề, E là siêu
kì dị. Cho là một căn nguyên thủy bậc ba của đơn vị. Định nghĩa ánh xạ
.
Bằng tính toán trực tiếp ta chỉ ra được β là một đẳng cấu.
2.1.5 Mã hóa Massey – Omura
Alice muốn gửi một văn bản tới Bob qua một kênh công khai. Họ chưa thiết lập được một khóa riêng. Một cách để thực hiện điều này như sau. Alice đặt văn bản của cô vào một hộp và lắp khóa của cô ta vào đấy. Cô gửi chiếc hộp cho Bob, Bob lắp khóa của anh vào sau đó gửi trả chiếc hộp lại cho Alice. Alice tháo khóa của mình ra và gửi chiếc hộp lại cho Bob. Khi đó Bob bỏ khóa của anh ta ra, mở chiếc hộp và đọc văn bản trong ấy. Ta sẽ chỉ ra M4 chính là văn bản M, một cách hình thức ta có:
mB mAM = M
Nhưng ta cần giải thích thực tế rằng , số nguyên biểu diễn nghịch đảo của mA, và
mA là khử nhau. Ta có mA (mod N), vậy mA = 1 + kN với số nguyên k.
với mọi . Nhóm E(Fq) có cấp N, vậy định lý Lagrange kéo theo
Do đó, mAR = (1+kN)R = R + k ∞ = R.
Áp dụng điều này với R = mBM, ta thấy M3 = mB mAM = mBM.
Tương tự, và mB khử nhau, vậy M4 = mBM = M.
, b = Tên trộm Eve biết E(Fq) và các điểm mAM, mBmAM và mBM. Đặt a =
, P = mAmBM.
2.1.6 Mã hóa công khai Elgamal
Alice muốn gửi một văn bản cho Bob, Anh chọn một đường cong Elliptic E trên một trường hữu hạn Fq sao cho bài toán log rời rạc là khó với E(Fq). Anh cũng chọn một điểm P trên E (thông thường được thỏa thuận để cấp của P là một số nguyên tố lớn). Anh chọn một số nguyên bí mật s và tính B = sP.
Để gửi văn bản cho Bob, Alice thực hiện như sau: Tải về khóa công khai của Bob
Tính M2 = M + kB
(1) (2) Biểu diễn văn bản của cô như một điểm M ∈ E(Fq). (3) Chọn một số bí mật ngẫu nhiên k và tính M1 = kP. (4) (5) Gửi M1, M2 cho Bob.
Bob giải mã bằng việc tính: M = M2 – sM1. Việc giải mã thực hiện được vì M2 – s M1
= (M+kB) – s(kP) = M + k(sP) – skP = M.
16
2.2 Sinh tham số cho hệ mật Elliptic
2.2.1 Tham số miền của đường cong Elliptic
Các tham số cho hệ mật đường cong Elliptic trên là một bộ
, trong đó: p>3 là số nguyên tố, xác định trường hữu hạn cơ sở .
với
Phần tử sinh có bậc nguyên tố là trên , và
.
Đồng thừa số h=1 Một xâu bít SEED dùng để sinh ngẫu nhiên đường cong
2.2.2 Sinh và kiểm tra cặp khóa đường cong Elliptic
Thuật toán 2: Sinh cặp khóa cho hệ mật Elliptic
Input: Bộ tham số miền
Output: (Q – điểm công khai, d – khóa bí mật)
(1) Sinh . Số nguyên d phải được giữ bí mật và phải không dự đoán
được
(2) Tính điểm
(3) Trả về cặp khóa là trong đó là khóa công khai, d là khóa bí mật.
Với một bộ tham số miền và một khóa công khai có thể
được kiểm tra tính hợp lệ theo thuật toán dưới đây.
Thuật toán 3: Kiểm tra tính hợp lệ của khóa công khai
Input: Tham số miền , khóa công khai
Output: “Khóa công khai hợp lệ” hoặc “Khóa công khai không hợp lệ”
(1) Kiểm tra không phải là điểm trên
(2) Kiểm tra
(3) Kiểm tra rằng trong .
(4) Kiếm tra (5) Nếu bất kỳ một trong các phép kiểm tra trên thất bại trả về “khóa công khai không hợp lệ” còn không thì trả về “khóa công khai hợp lệ”.
17
2.2.3 Thuật toán kiểm tra điều kiện MOV
Thuật toán 4: Kiểm tra điều kiện MOV
Input: Giá trị B là cận của MOV theo tiêu chuẩn EC5 Output: 0: Không thỏa mãn điều kiện MOV; 1: Thỏa mãn MOV (1) t = 1, ok= 1; (2) for i = 1 to B do T = t.p (modN) If (t==1){ok=0; return ok;} (3) return ok;
2.2.4 Thuật toán sinh đường cong ngẫu nhiên
Thuật toán 5: Sinh đường cong ngẫu nhiên
Input: Số nguyên tố p Output: Chuỗi SEED và xác định E trên .
Tính trước , ,
(1) Chọn một chuỗi bít SEED có độ dài ít nhất là 256 bít. Gọi g là độ dài theo bít của SEED.
(2) Tính H=SHA256(SEED), gọi là h bít bên phải của H
là h bít nhận được bởi việc thiết lập bít ngoài cùng bên trái của thành 0
(3) (nhằm đảm bảo r < p)
(4) Với i= 1 đến s tính
(5)
(6) Với là các bít của từ trái qua phải. Tính số nguyên .
sao cho (A, B không nhất thiết phải chọn
(7) Chọn ngẫu nhiên). (8) Nếu chuyển sang bước 1.
(9) Đường cong được chọn trên là E: .
(10) Return (SEED, A, B).
2.2.5 Thuật toán kiểm tra đường cong được sinh ngẫu nhiên
Thuật toán 6: Kiểm tra đường cong được sinh ngẫu nhiên
Input: Chuỗi bít SEED có độ dài là g-bít v à .
Output: Chấp nhận hoặc không chấp nhận tham số đầu vào.
18
Tính trước
Tính H = SHA256(SEED), gọi là h bít bên phải của H (1)
là h bít nhận được bởi việc thiêt lập bít ngoài cùng bên trái của thành 0. (2)
(3) Với i= 1 đến s thực hiện:
Tính
(4)
là các bít của từ trái qua phải. Tính số nguyên
(5) Với (6) Nếu thì chấp nhận, ngược lại không chấp nhận tham số đầu
vào.
2.2.6 Thuật toán tính số điểm của đường cong elliptic
Định lý Hasse:
Cho E là một đường cong elliptic trên trường hữu hạn . Khi đó bậc của E ( ) thỏa
mãn:
(2.1)
Đặt t = . Khi đấy mối quan hệ giữa tự đồng cấu Frobenius với số điểm
của đường cong elliptic E trên trường hữu hạn .
Thuật toán 7: Tỉnh số điểm của đường cong _
Input: A , B v à p xác định ( E ) trên .
Output: E ( ) = p + 1 - t .
(1) Chọn tập các sổ nguyên tố sao cho:
(2) Với l= 2 , Nếu gcd thì ta có .
Ngược lại thì .
(3) Với mỗi số nguyên tố lẻ , thực hiện các bước sau đây:
với .
a) Tính b) Tính hoành độ x' của điểm:
19
được thay bởi với công thức truy hồi sau
Chú ý, trong thực tế đa thức chia đây:
(2.7)
Trong đó
c) Với . thực hiện các bước sau:
(i) Tính hoành độ của điểm
(ii) Nếu thì chuyển sang bước iii. Còn không thì tiếp tục
thử với giá trị tiếp theo của j. Nếu mọi giá trị của j trong đoạn
đã được thử thì sang bước d.
(iii) Tính . Nếu thì , còn không
thì
d) Tính w sao cho nếu w không tồn tại thì .
e) Nếu gcd(tử_số_của ) = 1 thì . Còn không thì tính
gcd(tử_số_của ). Nếu gcd này là 1 thì . Còn
không thì .
(4) Sử dụng các giá trị đã tính ở bước 3 với mỗi và Định lý Phần dư
Trung hoa để tính . Chọn giá trị t duy nhất thoả mãn
(5) Trả về .
Đánh giá độ phức tạp của thuật toán Schoof:
Các phép tính phức tạp nhất phải thực hiện trong mỗi bước tính là tính
và .
Như vậy, với mỗi một số nguyên tố l, để tính yêu cầu cỡ
phép toán bít.
Số lượng các số nguyên tố l xuất hiện là cỡ , như vậy độ phức tạp tổng thể
của thuật toán Schoof là cỡ phép toán bít.
20
2.2.7 Thuật toán sinh tham số miền
Hình 5: Lưu đồ thuật toán sinh tham số miền
Thuật toán 8: Sinh tham số miền cho hệ mật đường cong elliptic
Input: Số năm y trong khoảng 2011 -2020 và biến atm (bằng 1 xác định mức an toàn là ATM1, bằng 2 xác định ATM2). Output: Bộ tham số miền
(1) Dựa vào y và biến xác định mức an toàn atm để tính các giá trị cụ thể của độ dài
(2)
khóa N và modulo p theo tiêu chuẩn EC2 và EC3. Sử dụng một thuật toán tất định để sinh số nguyên tố p có thể chứng minh được theo độ dài đã xác định trong bước (1). Lưu lại p. Sử dụng Thuật toán 5 để sinh đường cong ngẫu nhiên có thể kiểm tra được trong (3)
. Lưu lại SEED, A, B.
(4)
Sử dụng Thuật toán 7 để tính số điểm của đường cong được sinh ngẫu nhiên: N=#E( ).
(5) Nếu N là hợp số thì quay lại bước (3). (6)
[1]. Kiểm tra tiêu chuẩn EC6 về ước nguyên tố của N± 1, nếu không thỏa mãn thì
quay về bước (3).
21
[2]. Kiểm tra tiêu chuẩn EC4 về đường cong bất quy tắc: Nếu N = p thì quay về
bước (3).
[3]. Kiểm tra tiêu chuẩn EC5 về điều kiện MOV, nếu không thỏa mãn thì quay về
bước (3).
(7) (8) h = 1 . Sinh ngẫu nhiên một điểm cơ sở .
(9) Kiểm tra điểm cơ sở theo tiêu EC7
( chuẩn . Nếu không thỏa
mãn thì quay về bước (8). (10) Trả về (p, A, B, G, N, h, SEED).
2.2.8 Thuật toán kiểm tra tính hợp lệ của tham số miền
Thuật toán 9: Kiểm tra tính hợp lệ của tham số miền
Input: Bộ tham sô miền (p, A, B, G, N, h, SEED). Output: "tham số miền hợp lệ" hoặc "tham số miền không hợp lệ"
Kiểm tra độ dài theo bít của N theo tiêu chuẩn EC2. (1) Kiểm tra p là nguyên tố (dựa theo các bằng chứng nguyên tố đã được tạo ra trong quá trình sinh p từ Thuật toán 8). Kiểm tra độ dài của p theo tiêu chuẩn EC3.
(2) Kiểm tra (3) Kiểm tra A, B có được dẫn xuất từ SEED không (theo Thuật toán 6 về việc
kiểm tra đường cong được sinh ngẫu nhiên).
(4) Kiểm tra
(5) Kiểm tra tiêu chuẩn EC7 ;
; .
,
(6) Kiểm tra N là nguyên tố và h = 1 theo tiêu chuẩn EC4. (7) Kiểm tra tiêu chuẩn EC6 về ước nguyên tố của N ± 1. (8) Kiểm tra (9) Kiểm tra điều kiện MOV theo tiêu chuẩn EC5.
.
(10) Kiểm tra điều kiện đường cong bất quy tắc theo tiêu chuẩn EC4: (11) Nếu một trong các bước kiểm tra trên cho kết quả sai thì trả về “tham số miền
không hợp lệ” còn không thì trả về “tham số miền hợp lệ”.
Kết luận chương
Các kết quả cụ thể của chương 2:
(1) Đã đưa ra các thuật toán phục vụ cho bài toán sinh tham số.
22
(2) Nghiên cứu bài toán sinh tham số an toàn cho hệ mật Elliptic theo các tiêu chuẩn ISO
và IEEE.
Các kết quả của chương này thu được khẳng định việc xây dựng bài toán tham số an toàn cho hệ mật có tính khả thi áp dụng vào bài toán thực tế được trình bài ở chương 3.
CHƯƠNG 3 - ỨNG DỤNG TRONG BÀI TOÁN BẢO MẬT MẠNG RIÊNG ẢO
3.1. Phần mềm bảo mật mạng riêng ảo OpenVPN
OpenVPN là một bộ chương trình tạo mạng riêng ảo (VPN) mã nguồn mở dựa trên giao thức bảo mật SSL/TLS. OpenVPN bao gồm 03 thành phần: thiết lập khóa, mã hóa/ giải mã bởi một thuật toán đối xứng, đảm bảo tính toàn vẹn dữ liệu bằng HMAC (dựa trên hàm băm mật mã).
3.2. Tích hợp giao thức trao đổi khóa EC-HMQV trong SSL
Hugo Krawczyk đã đề xuất một biến thể đơn giản nhưng mạnh mẽ của MQV (tương ứng EC-MQV), và gọi là giao thức HMQV (tương ứng là EC-HMQV). Cũng giống như MQV, giao thức HMQV dựa trên giao thức Diffie-Hellman cơ bản. Điểm khác nhau giữa HMQV và MQV nằm trong việc tính toán khoá phiên có sử dụng hàm Hash.
Thuật toán 10: Tính khóa chung của giao thức EC-HMQV
p, E, N, h, G) và các thông tin đã nhận được từ là
Input: Tập các tham số hệ thống ( Bước 2 của A là tự của B (tương
)
Output: Khóa bí mật k và k’ cho thực thể A (và B)
Thực thể A Thực thể B
Bước 1: Bước 1:
Bước 2: Bước 2:
Bước 3: Bước 3:
Bước 4: Bước 4:
Bước 5: Bước 5:
Bước 6: Bước 6:
3.3. Tích hợp tham số an toàn hệ mật Elliptic
Để sử dụng tham số do ta tự sinh ra trong bộ phần mềm OpenVPN. Ta phải chuyển đổi sang định dạng PEM và X.509 cho khóa bí mật và công khai. Tham số khóa bí mật sẽ
23
được sử dụng trong lược đồ chữ ký số ECDSA (cho việc kiểm tra chứng chỉ số của đối tác) và trong lược đồ trao đổi khóa EC- HMQV. Để làm được điều này, ta cần chỉnh sửa code của thư viện SSL như sau: (1). Do bộ thư viện SSL sử dụng các tham số hệ mật Elliptic theo các chuẩn của NIST, FIPS và SEClv2-2009 nên các số nguyên tố modulo ở dạng đặc biệt. Các phép tính liên quan đến modulo được cài đặt mặc định để sử dụng cho các số nguyên tố đó. Ta cần phải chỉnh sửa code trong file ec_cvt.c để bộ thư viện có thể tính toán được với các số nguyên tố modulo ngẫu nhiên do ta sinh ra.
(2). Khai báo các tham số hệ mật Elliptic cần sử dụng trong file ec_curve.c. Sử dụng tiện ích ecparam.c để chuyển đổi tham số sang dạng PEM và chứng chỉ sổ X.509 hoặc PKCS12.
3.4 Mô hình thử nghiệm bảo mật VPN
3.4.1 Mô hình mạng
Hình 6: Mô hình bảo mật VPN
3. 4.2. Thiết lập cấu hình cho VPN Server
# VPN Server Port 1194 Proto udp Dev tap0 # RootCA sử dụng tham số hệ mật Elliptic ca /etc/openvpn/key/ec_ca.crt # Khóa công khai/ bí mật sử dụng tham số Elliptic cert /etc/openvpn/key/server1.crt
24
key / etc/openvpn/key/server1.key # Tham số Diffie-Hellman cho trao đổi khóa EC-HMQV ecdh /etc/openvpn/key/ecdh.pem # Mã hóa và xác thực dùng AES và SHA2 cipher AES-256-CBC auth SHA256 …………
3.4.3. Thiết lập cấu hình cho VPN Client # VPN Client: Linux – User02 Client Proto udp Dev tap0 # RootCA sử dụng tham số hệ mật Elliptic ca /etc/openvpn/key/ec_ca.crt # Khóa công khai/ bí mật sử dụng tham số Elliptic cert /etc/openvpn/key/user2.crt key / etc/openvpn/key/user2.key # Kết nối đến địa chỉ thật của VPN Server Remote 192.168.1.18 1194 # Mã hóa và xác thực dùng AES và SHA2 cipher AES-256-CBC auth SHA256 …………
3.4.4. Kết quả và nhận xét
Việc thay thế giao thức trao đổi khóa ECDH bởi EC-HMQV trong bộ thư viện
Quá trình hoạt động của bộ chương trình bảo mật VPN sau khi đã tích hợp giao thức
OpenSSL là công việc phức tạp và khó khăn. trao đổi khóa EC-HMQV và sử dụng tham số hệ mật Elliptic do Luận văn tạo ra.
Kết luận Chương
Các kết quả cụ thể trong Chương 3 bao gồm:
(1). Nghiên cứu và áp dụng các thuật toán phục vụ cho bài toán sinh tham số theo các tiêu chuẩn ISO và IEEE. (2). Nghiên cứu chương trình sinh tham số an toàn hệ mật Elliptic theo các tiêu chuẩn đã đề xuất. (3). Ứng dụng phần mềm bảo mật mạng riêng ảo và áp dụng các tham số an toàn hệ mật Elliptic.
Các kết quả thu được trong chương này khẳng định tham số sinh ra với giá trị p là số nguyên tố ngẫu nhiên có tính bảo mật hơn so với giá trị p là số nguyên tố đặc biệt và khả thi trong thực tế.
25
KẾT LUẬN A.
Các kết quả đạt đưọc của Luận văn
1. Đã nghiên cứu cơ sở toán học hệ mật dựa trên đường cong elliptic và các tấn công đối
với hệ mật Elliptic.
2. Đã nghiên cứu, đánh giá một số chuẩn về tham số. 3. Nghiên cứu được giá trị tham số p là số nguyên tố ngẫu nhiên là an toàn cho các tham
số hệ mật Elliptic.
4. Đã nghiên cứu, đánh giá thuật toán tính số điểm của đường cong elliptic phục vụ cho
bài toán sinh tham số an toàn.
5. Đã nghiên cứu về cấu trúc, nguyên lý hoạt động của một ứng dụng bảo mật mạng
riêng ảo (trao đổi khóa, tham số an toàn ...). Hướng nghiên cứu tiếp theo B.
1. Nghiên cứu phương pháp tính số điểm của đường cong theo phương pháp nhân phức
CM để tăng tính hiệu quả của thuật toán sinh tham số.
