Nghiên cứu hệ mật NTRU

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (4.01 MB, 22 trang )

Trang 1<div class="page_container" data-page="1">

LỜI MỞ ĐẦU

Ngày này, xu hướng tồn cầu hóa là xu thế tất u của sự phát triển. Việc trao đôi thông tin trong nước, quốc tế ngày càng nhiều địi hỏi sự nhanh gọn, chính xác và an tồn. Những cơng việc xác minh, chứng thực theo cách truyền thống sẽ làm giảm tốc độ đáng kể.

Từ đó, mạng máy tính với tốc độ nhanh đóng vai trị quan trọng trong nhiều lĩnh vực và nhu

cầu bảo mật thông tin được đặt lên hàng đầu. Tiêu biéu là việc mã hóa bảo mật các thơng tin số của doanh nghiệp, dùng chữ ky số xác thực email trao đồi thông tin, các don hàng, ngân hàng điện tử, mua sắm trực tuyến.... Từ đó ta thay rằng, việc xây dựng các hệ mật dé dam bảo an tồn thơng tin là một vấn đề bắt buộc và cấp thiết.

Hệ mật NTRU được đề xuất bởi 3 nhà toán học J.Hoffstein, J .Pipher và J.H.Silverman vào năm 1996. NTRU là hệ mật khóa cơng khai đầu tiên khơng dựa trên việc

tìm thừa số và các vấn đề về logarit rời rac. Nó là một thay thé dựa trên dan (lattice) cho

RSA, ECC va dựa trên van dé vector ngắn nhất trong dan.

Nam 2009, hé mat NTRU da duoc phé duyét cho chuẩn hóa bởi IEEE trong tiêu chuẩn P.1363.1. Từ khi ra đời, NTRU đã thu hút được nhiều sự quan tâm, nghiên cứu bang nhiều kiểu tan công khác nhau dé phá hệ mat mã nay. Cho đến nay nó là một trong những hệ mật khóa cơng khai nhanh nhất.

Trong luận văn này sẽ nghiên cứu hệ mật NTRU với 3 chương như sau:

Chương I: giới thiệu hệ mật khóa cơng khai và các bài toán một chiều liên quan với

các hệ mật.

Chương II: di sâu vào hệ mật NTRU với các cách thực hiện hệ mật, cùng với phân

tích tân cơng vào hệ mật.

Chương III: tập trung vào tối ưu hóa hệ mật NTRU.

</div>Trang 2<div class="page_container" data-page="2">

CHƯƠNG I: TONG QUAN VE HỆ MAT KHOA CƠNG KHAI

Trong chương này, ta sé đi tìm hiệu về hệ mật khóa cơng khai va đưa ra các bài toán

liên quan đên các hệ mật. Ta sẽ nghiên cứu vê các bài toán 1 chiêu như: logarit, phân tích thừa số,... Nghiên cứu một số hệ mật khóa cơng khai như RSA, ECC.

1.1. Tổng quan

Năm 1976, Diffie và Hellman đã đưa ra ý tưởng về hệ mật khóa cơng khai. Năm 1977, Rivesrt, Shamir và Adleman đã hiện thực hóa nó và tạo ra một hệ mật khóa cơng khai được dùng rộng rãi nhất đó là RSA. Ké từ đó, một số hệ mật được cơng bố, độ mật của chúng thì dựa trên những bài tốn một chiều khác nhau. Trong đó, các hệ mật sau đây là quan trọng nhất, sẽ được giới thiệu trong mục 1.2:

- Cac hệ mật liên quan đến bai toán logarithm.

- Hé mật RSA: độ bảo mật liên quan đến việc phân tích ra thừa SỐ nguyên lớn.

- Hệ mật Merkle - Hellman: bài toán xếp balo. Liên quan đến độ khó của việc giải

bài tốn tổng các tập con.

- Hé mật McEliece: dựa trên lý thuyết mã đại số.

- Hé mật trên các đường cong Elliptic: chúng làm việc trên các đường cong Elliptic

chứ không phải trên các trường hữu hạn. Nó đảm bảo độ mật với số khóa nhỏ hơn

các hệ mật khóa cơng khai khác.

1.2. Các bài toán một chiều và các hệ mật liên quan

1.2.1. Bài toán logarithm rời rac và các hệ mật liên quan

1.2.1.1. Bài toán logarithm trên trường số thực R

Bài toán thuận: y= a*, x ER

Bài toán ngược: y= log, x, x >0

1.2.1.2. Bai toán logarithm trên trường hữu han Z, (p nguyên tố)

Bài toán thuận: y= œŠ mod p, x € 2p={0, 1,2,..„p-1}

Bài toán ngược: y= log, xX mod p, x€ Z;= Z,/{0}

1.2.1.3. Trao đổi va phân phối khóa Diffie — Hellman

</div>Trang 3<div class="page_container" data-page="3">

Bên A (p, œ) Bên B

p: số nguyên tô lớn ơ: phần tử sinh € Zp 1.2.1.4. Hệ mật Omura - Massey

Y tưởng: bên A gui ban tin cho B với khóa cua A. Bên B nhận được lại khóa tiếp bản tin với khóa của B rồi gửi lại cho A. Lúc này bản tin có 2 khóa, A nhận được và mở bản tin bang khóa cua mình, ban tin cịn lai 1 khóa cua B va được gửi lại cho B. Khi đó B nhận

được và dé dàng mở được bản tin vì chỉ cịn khóa của B.

1.2.1.5. Hệ mật El.Gamal

Đây là một hệ mật xác suât với hiệu quả R = 1. Trong hệ mật này có ân vào trao đơikhóa Diffie — Hellman.

1.2.2. Bài tốn phân tích thừa số và hệ mật RSA 1.2.2.1. Bài tốn phân tích thừa số

Cho n - số nguyên: n= p;'p,”...p,*. Với p¡ số nguyên tố phân biệt, e¡ nguyên dương.

Trường hợp n = pq với p và q có độ lớn tương đương.

1.2.2.2. Hệ mật RSA

Thám mã phải phân tích được n = pq. Thế nên hiệu quả R ~ 1.

1.2.3. Bài toán xếp balo và hệ mật Merkle — Hellman 1.2.3.1. Bài toán xếp balo

Cho tập các giá trị M,, Mạ, ..., Mạ và một tổng S. Hãy tính các giá trị b; đề:

S= b;M¡+ bạM¿+ bạMạ

với bị € {0, 1}

bị = 1: có nghĩa là gói M; được xếp vào balo.

b, = 0: có nghĩa là gói M; khơng được xếp vào balo.

</div>Trang 4<div class="page_container" data-page="4">

Trong trường hợp M={M¡, M;,.., Mạ} là một dãy siêu tăng thì việc tim b= (bj, bạ,... bạ) trong đương như bai tốn tìm biểu diễn nhị phân của một số S. Ta sẽ

tìm được biêu diễn này sau tôi đa n bước.

Nếu M không phải dãy siêu tăng thi lời giải của bài toán là một trong 2" phương án có thé. Vậy nên đây là một bài tốn khó nếu n lớn.

1.2.3.2. Hệ mật Merkle — Hellman

1.2.4. Bài toán mã sửa sai và hệ mật McEliece

1.2.4.1. Bài toán mã sửa sai1.2.4.2. Hệ mật McEliece

Dinh lý: Giả sử C là một mã [n, k] có ma trận sinh G và ma trận kiểm tra tính chin lẻ

H. Khi đó x € (Z)" là một từ mã khi và chỉ khi Hx? = [00...0]7.

Hơn nữa nếu x € C, e € (Z¿)" var =x + e thi Hx’ = He’.

Ta xem e là vetor sai xuất hiện trong quá trình truyền từ mã x. Khi đó r biểu diễn

vector thu được. Định lý trên phát biểu rằng syndrom chỉ phụ thuộc vào các sai số mà không

phụ thuộc vào từ mã cụ thể nào được truyền đi.

1.2.5. Bài toán xây dựng hệ mật trên đường cong elliptic

Đường cong Elliptic là một phương trình bậc 3 có dạng:

Điều kiện tồn tai: A = 4a3+ 27b? #0 mod p.

1.2.5.1. Các phép tốn trên nhóm E, (a, b)1.2.5.2. Mật mã trên đường cong Elliptic

</div>Trang 5<div class="page_container" data-page="5">

Trong hệ mật này, bản rõ M mã hóa thành điểm Py trong tập hữu hạn các điểm của

nhómE, (a, b).

1.2.5.3. Độ an toàn của hệ mật trên đường cong Elliptic

Sức mạnh của hệ mật trên đường cong Elliptic (ECC) nằm ở sự khó khăn đối với

thám mã khi phải xác định số ngẫu nhiên bi mật k từ kP và P. Dé pha ECC độ phức tạp tính

tốn khi dùng phương pháp S — Pollard là 3,8.10°° MIPS — năm với kích thước khóa 150

bit. Nếu độ dài khóa của RSA tăng lên tới 2048 bit thì cần 3. 102° MIPS — năm, trong khi đó với ECC chi cần độ dài khóa là 234 bit đã phải yêu cầu tới 1,6. 1028 MIPS - năm.

1.3. Ưu và nhược điểm của hệ mật khóa cơng khai

Ưu điểm:

+ Khơng cần kênh an tồn dé truyền khóa.

+ Đơn giản trong việc tạo, lưu trữ và giữ bí mật khóa va dé dàng qui trách

+ Khó thực hiện cho các dịch vụ nhạy cảm với độ trễ.

1.4. Một số ứng dụng phố biến của hệ mật khóa cơng khai

</div>Trang 7<div class="page_container" data-page="7">

Trong chương I, ta đã tìm hiểu được các bài tốn một chiều và các hệ mật liên quan.

Từ đó, thấy được được ưu và nhược điểm của hệ mật khóa công khai. Cuối cùng, ta rút ra

được hệ mật RSA là hệ mật phổ biến được sử dụng khá nhiều hiện nay, cùng với các ứng

dụng của nó.

Như vậy, sang chương tiếp theo, ta sẽ đi sâu vào phần chính của luận văn là hệ mật

khóa mới NTRU.

</div>Trang 8<div class="page_container" data-page="8">

CHƯƠNG II: KỸ THUẬT TRONG HỆ MẬT NTRU

Trong chương II, ta sẽ di sâu tìm hiểu về hệ mật mới NTRU cùng với cách thực hiện hệ mật (mã hóa, giải mã), tìm hiểu về mức độ an ninh của NTRU cùng với cách thám mã tấn công hệ mật.

2.1. Hệ mật mới NTRU

NTRU lần đầu tiên được giới thiệu bởi Jeffrey Hoffstein trong hội nghị con ở

CRYPTO'96 và được xuất bản năm 1998. Hệ mật NTRU được cấp bằng sáng chế vào

2.2. Mơ tả thuật tốn NTRU2.2.1. Ký hiệu

Một hệ mật NTRU phụ thuộc vào 3 số nguyên (N, p, q) và 4 tập Tự, Đụ, Ủạ, Em của

các đa thức bậc N — 1 với các hệ số nguyên.

2.2.2. Tao khóa

h =F¿ @ g (mod q) (2.2)

Khóa cơng khai của Bình là đa thức h.

Khóa bí mật của Binh là đa thức f.

Rồi Bình chọn các hệ số của a trong khoảng từ -q/2 đến q/2. Bây giờ xem a như là một đa thức với các hệ số ngun, Bình sẽ khơi phục lại bản rõ m băng cách tính:

m=F, @ a (mod p) (2.5)

</div>Trang 9<div class="page_container" data-page="9">

2.3. Lựa chọn tham số 2.3.1. Quy tắc

Mệnh đề: Với bat kỳ e > 0, có các hằng số yj, Y2 > 0, phụ thuộc vào e và N, với các đa thức lựa chọn ngẫu nhiên F, G € R, xác suất rất lớn so với 1 - e mà thỏa mãn:

YilFl2IGl2 SIF © Glo <y›;|F|z|G|›

2.3.2. Khéng gian mau

Không gian của các bản tin £„ bao gồm tat cả các đa thức modulo p. Gia sử p là lẻ,

nó rât thuận tiện đê lây:

an 1 1

Lm = {m € R: m có các hệ sơ nam giữa - 2 Íp - 1)và 2œ -1)} Dé mơ tả các không gian mẫu khác, ta sẽ dùng các tập hợp có dang:

£(d:, dạ) = {F €R: F có các hệ số dị bằng 1, các hệ số dạ bằng — 1, còn lại bằng 0}.

Với ký hiệu nay, ta chọn 3 số nguyên dương dy, d,, d và tap:

Ly = L(dp dị— 1), Ly = L(dg, dg), Ly = £(d, d)

2.3.3. Tiêu chuẩn giải mã

Dé có thé giải mã thành công, điều kiện cần thiết là:

If Om+ph @g|„<q (2.6)

2.4. Phan tich an ninh trong NTRU

2.4.1. Tan công vét cạn

Bên tấn cơng có thé khơi phục lại khóa riêng bằng cách thử tat cả các f € Ly có thể và kiểm tra nếu f © h (mod q) có các giá trị nhỏ, hoặc băng cách thử tất cả g € Ly và kiêm tra nêu g ® h7! (mod q) có các giá trị nhỏ. Tương tự, bên tan cơng có thể khơi phục lại bản

tin bang cách thử tat cả trường hợp @ € Ly và kiểm tra nếu e - @ h (mod q) có các giá

trị nhỏ.

</div>Trang 10<div class="page_container" data-page="10">

2.4.2. Tan công “gặp nhau ở giữa” (meet-in-the-middle)

Nhắc lại rằng bản tin đã được mã hóa có dạng e = @ @ h +m (mod q). Nói một cách ngắn gon, chia f làm đơi, với f = f¡ + f, và sau đó thay f¡ © e vào - f, @ e, rồi tim (f¡,f;) vậy nên các hệ số tương ứng có giá trị xấp xỉ giống nhau.

2.4.3. Tan công khi phát lại nhiều lan

Nếu An gửi một bản tin m nhiều lần dùng cùng một khóa cơng khai nhưng ngẫu nhiên khác nhau ở, khi đó bên tấn cơng — gọi là Cơng — có thé khơi phục phan lớn bản tin.

2.4.4. Tấn công dựa trên dàn (lattice)

Đối tượng của ta trong mục này là nhằm đưa ra một phân tích tom tắt những hiểu biết

về tấn cơng lattice trên cả khóa công khai h và bản tin m. Ta sẽ bắt đầu với khái niệm liên

quan đến việc giảm lattice. Mục đích của việc rút gon lattice là để tìm một hoặc nhiều

vector “nhỏ” trong một lattice đã được cho. Về mặt lý thuyết, vector nhỏ nhất có thể được

tìm thấy bằng tìm kiếm vét cạn, nhưng trong thực tế điều này là khơng thể nếu kích thước

2.4.4.1. Tan cơng lattice trên một khóa bí mật NTRU

Xem xét ma trận 2N x 2N tạo bởi 4 khối N xN:

a 0 OP Ag hị ch hàng

Ở đây, a là một tham số được lựa chọn ngắn gọn. Đề L trở thành lattice được tạo bởi

các hàng của ma trận. Định thức của L là: qŸœŸ,

Khi khóa cơng khai h = g @ fT†, lattice L sẽ chứa vector 7 = (af, g), nghĩa là 2N

vector bao gôm N hệ sô của af, theo sau bởi N hệ sô của g

2.4.4.2. Tan công lattice trên một bản tin NTRU

</div>Trang 11<div class="page_container" data-page="11">

Một tan cơng lattice cũng có thé trực tiếp chống lại một ban tin cá nhân m. Ở đây,

van dé lattice liên kết gần giống như với h, và vector mục tiêu sẽ có dạng (am, ở). Như

trước đây, bên tan công nên cân bang lattice dùng a = |@|;/|m|a, dẫn đến giá trị:

Đê thực hiện tân công vào h và m với độ khó ngang nhau, chúng ta mn lây

Cm * Ch, hoặc tương đương là |fl;|g|lz ~ |m|;|d|a.

2.4.4.3. Tan cơng Lattice trên một khóa giả

Thay vì cố gắng tìm khóa bí mật f, bên tan cơng có thé dùng lattice được mơ ta ở trên

mục 2.4.4.1 và thử tìm một vài vector ngăn khác trên lattice, có dạng: r' = (af’,g’). Nếu

vector này đủ ngắn, khi đó f sẽ hoạt động như một khóa giải mã. Chính xác hơn, nó có thể

giải mã với xác suất cao:

2.5. Thực hiện NTRU trong thực tế 2.5.1. Lựa chọn tham số cụ thể

Bây giờ ta sẽ tìm hiểu về 3 tập tham số riêng biệt mang lại 3 mức độ an ninh khác nhau [5]. Các định chuẩn của f và g mà được chọn thì việc giải mã thất bại Xảy ra VỚI Xác

suất ít hơn 5.10° (dựa vào những thử nghiệm rộng rãi trên máy tính).

2.5.1.1. Trường hợp A: mức an ninh trung bình [5]

Các tham sơ của mức an ninh trung bình phù hợp với các tình hng mà trong đó giá

trị nội tại của bât cứ bản tin cá nhân nào là nhỏ, và trong đó các khóa sẽ được thay đơi với

tân st hợp lý. Các ví dụ có thê bao gơm như mã hóa trun hình, máy nhăn tin và truyén

tín hiệu điện thoại di động.

2.5.1.2. Trường hợp B: mức an ninh cao [5]

2.5.1.3. Trường hợp C: mức an ninh cao nhất [5]

</div>Trang 12<div class="page_container" data-page="12">

2.5.2. Vi dụ thực tế về tắn công dan (lattice)

Sử dụng thuật tốn LLL có một vài tham số có thé thay đổi dé đưa ra các kết qua khác nhau. Nói chung thuật tốn LLL có thé điều chỉnh dé hoặc tìm một điểm ngắn trong một khoảng thời gian nhỏ hoặc một điểm rắt ngắn trong khoảng thời gian dài hơn. Số lượng

khóa là hăng sơ cụ (hoặc c,,) đã được nêu ra trong các mục trên.

Bảng 2.1 cung cấp thời gian cần thiết dé LLL tìm hoặc vector mục tiêu (af, g) hoặc 1 vector có liên quan gần nhất trong lattice L được nói đến ở mục 2.4.4.1 cho nhiều sự lựa chọn khác nhau của q, cụ va kích thước N [5].

Vậy nên chúng ta chọn các tham số c,, cụ. Thời gian cần thiết dé phá vỡ một ban tin riêng cũng giống như thời gian cần thiết dé phá vỡ một khóa cơng khai. Trong mọi trường hợp, chúng ta thấy răng khi N càng lớn thì thuật tốn sẽ bị lỗi trong việc dừng lại, ngun nhân bởi vì vịng tích lũy sinh ra các lỗi. Bảng 1 sẽ kết thúc ở thời điểm lúc này.

Bảng 2. 1 Thời gian cần thiết dé LLL tìm được vector trong dàn L

</div>Trang 13<div class="page_container" data-page="13">

2.6. So sánh với các hệ mật khóa cơng khai khác

Hiện nay, có một sé những hệ mật khóa công khai như hệ mat RSA (Rivest — Shamir

— Adleman) dựa trên độ khó của việc phân tích thừa số, hệ mật McEliece dựa trên mã sửa

sai, và gần đây là hệ mật GGH (Goldreich, Goldwasser và Halevi) dựa trên độ khó của việc tìm phép trực giao hóa ngắn dựa trên một dàn (lattice) [5].

</div>Trang 14<div class="page_container" data-page="14">

Hệ mật NTRU có một vai đặc điểm chung với hệ mật McEliece, trong đó @ - phép

nhân trên vành R có thé được xây dựng như phép nhân của các ma trận (một loại đặc biệt),

và khi đó mã hóa trong cả 2 hệ mật có thể được viết như là một phép nhân ma trận E = AX

+ Y, với A là khóa cơng khai. Một khác biệt nhỏ giữa hai hệ mật là mã hóa NTRU, Y là bản

tin và X là vector ngẫu nhiên, trong khi hệ mật McEliece nghịch đảo các phép gan này.

Hệ mật NTRU có ít điểm chung với hệ mật RSA. Tương tự, mặc dù hệ mat NTRU

phải được thiết lập để ngăn ngừa tấn công rút gọn lattice, phương pháp giải mã cơ bản của nó rất khác so với hệ mật GGH, trong đó giải mã được dựa trên những hiểu biết về các cơ sở

lattice ngắn.

Bảng 2.3 dưới đây [5] so sánh các đặc điểm hoạt động trên lý thuyết của các hệ mật

RSA, McEliece, GGH và NTRU. Trong mỗi trường hợp số N đại diện cho một tham số mức

an ninh tự nhiên/độ dài bản tin.

Bảng 2. 3 Đặc điểm hoạt động trên lý thuyết của các hệ mật

NTRU RSA McEliece GGH

Qua chương II, ta đã có được cái nhìn tương đối tồn vẹn về hệ mật NTRU: các kỹ

thuật trong hệ mật NTRU, cách chọn các tham số cho hệ mật, phân tích một vài kiểu tấn

cơng hệ mật cũng như đưa ra được ví dụ. Cuối cùng, ta có một so sánh giữa hệ mật NTRU

và các hệ mật khóa cơng khai khác.

Sang chương tiếp theo, sau khi đã hiểu về hệ mật NTRU, ta sẽ đi vào tối ưu hóa hệ

mật này.

</div>Trang 15<div class="page_container" data-page="15">

CHUONG III: TOI UU HOA NTRU

Trong chương cuối này, ta sẽ xây dựng cách tối ưu hệ mat NTRU, tức là sẽ tìm cách

để cải thiện tốc độ và hiệu quả của hệ mật. Và phương pháp tối ưu được sử dụng trong

chương này là thông qua phương pháp đại sé, tính tốn. Ta sẽ xem xét, thay đổi các u tố như f, p hay các trọng số Hamming.

3.1. Bảo vệ chống lại tắn công bản mã được chọn 3.1.1. Tấn công bản mã được chọn

Đâu tiên, ta xem xét hiệu quả của giải mã một bản mã có dạng ch + c, với c là một sô

nguyên và h là khóa cơng khai. Đầu tiên thuật tốn giải mã sẽ nhân với f modulo q: a= f@ch+cf(mod q)

cg + cf (mod q)

Nếu bây giờ ta giả sử rằng một hệ số đơn trong a là + 2c, tức a; = + 2c, khi đó giá trị

của a mod q là cg + ef - qx'. Đầu ra của quá trình giải mã là:

cg @ F, +c - qx' @F, (mod p)

Nếu c được chọn là một bội số của p, thì đầu ra sẽ là: - qx! @F, (mod p).

3.1.2. Bảo vệ chống lại tắn công bản mã được chọn

Có rất nhiều cách để xây dựng khả năng thích nghỉ các cuộc tấn công bản mã được chọn chống lại hệ mật NTRU [8], [9]. Các kỹ thuật đệm của Fujisaki và Okamoto có thé được dùng dé ngăn chặn các cuộc tấn công này [3], [4]. Hơn nữa, nếu bản rõ NTRU không

bị xáo trộn theo cách nao đó, sau đó có thé có các cuộc tấn cơng như lý thuyết chống lại một

phần hoặc toàn bộ bản mã. Khả năng thích nghi cho NTRU theo phương pháp Fujisaki Okamoto với việc thêm vào tin nhắn xáo trộn sẽ làm việc theo như các cơng việc được trình bày tiếp theo đây.

Trong phan này, ta sẽ chọn ký hiệu r € £„, dé thay cho @ € Ly. Thay vào trong cơng thức (3), ta có cơng thức mã hóa tương ứng mới là e =r © h + m (mod 9).

Gọi M là bản rõ của bên gửi An. An chọn một tập ngẫu nhiên các bit R và dùng biến

đổi tat cả hoặc khơng gì cả (all-or-nothing transformation) trên phép ghép nối MỊIR. Ví dụ,

</div>