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

-]-MỞ ĐẦU Tính cấp thiết của đề tài

Bài toán logarithm rời rac (DLP) là | bài tốn kinh điển của các

hệ mật khóa cơng khai. Cho tới nay sau gần 40 năn ra đời, mặc dù

các nhà mật mã học trên thế giới đã dé nhiều công sức dé giải DLP, <small>DLP van là 1 bài tốn chưa có lời giải đầy đủ và vẫn cịn là 1 bài tốn</small>

khó. Luận văn đi sâu vào bài tốn kinh điển này khơng nhằm mục

tiêu phá giải nó mà xây dựng chúng theo các phương pháp che dấu dữ liệu có thể trên vành số Z,. Việc khảo sát đầy đủ các cách xây dựng này đòi hỏi nhiều công sức hơn 1 luận văn thạc sĩ, bởi vậy đây mới chỉ là những bước đi ban đầu.

Nếu khảo sát đầy đủ hơn ta có thể thấy rằng riêng với hệ mật ElGamal cũng có tới 15 biến thể khác nhau có thể xây dựng. Ngồi

ra, ý tưởng nay cũng có thé được áp dụng cho các vành khác Z „ như

vành đa thức và vành ma trận.

Trong mật mã, hệ mật khóa cơng khai rất thuận tiện vì nó

khơng u cầu người gửi và người nhận phải chia sẻ một bí mật

chung để giao dịch an tồn. Tuy nhiên, chúng thường dựa trên các

tính tốn tốn học phức tạp và do đó thường kém hiệu quả hơn so với

các hệ mật khóa bí mật. Một hệ mật lai là sự kết hợp sự tiện lợi của

<small>một hệ mật khóa cơng khai với hiệu quả của một hệ mật khóa bí mật.</small>

Một hệ mật lai ghép có thể được xây dựng bằng cách sử dụng bất kỳ hai hệ mật riêng biệt. Một sơ đồ đóng gói khóa là một hệ mật

khóa cơng khai, và một sơ đồ đóng gói di liệu là một hệ mật khóa bi

mật. Các hệ mật lai chính là một hệ thống khóa cơng khai, mà các

khóa cơng khai và bí mật giống như trong các sơ đồ đóng gói dữ liệu

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

<small>Đối tượng nghiên cứu của đề tài là bài toán Logarith rời rạc vàcác hệ mật có liên quan.</small>

<small>Phạm vi nghiên cứu là xây dựng hệ mật lai trên bài toán</small>

<small>Logarith rời rạc</small>

Mục tiêu nghiên cứu của luận an:

— Tìm hiểu về các hệ mật và các biến thé xây dựng trên bài toán

logarithm roi rac.

<small>— Xây dựng các hệ mật lai ghép trên bài toán logarithm rời rac.</small>

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

-2-Phương pháp nghiên cứu: Thu thập thông tin từ các nghiên cứu, tải liệu liên quan (sách giáo khoa, Internet, ...) và các công trình nghiên cứu có liên quan.

Nội dung luận án này bao gồm: lời mở đầu, 3 chương và phần kết

> Chương I. Bài toán Logarithm rời rac

> Chương II. Các hệ mật xây dựng trên bài toán Logarithm rời

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

-3-— CHUONGI _

BÀI TOÁN LOGARITHM RỜI RẠC

Chương này giới thiệu về bài toán logarithm rời rạc, bài toán

<small>logarithm roi rac trên trường số thực, trường hữu han, các thuậttoán giải.</small>

<small>1.1. Bài toán logarithm rời rac</small>

<small>Định nghĩa bài toán Logarithm rời rạc:</small>

Giả sử G là một nhóm cyclic hữu hạn có cấp n. Gọi @ là phần

tử sinh của G và /là một phan tử khác thuộc G. Khi đó logarithm

rời rac của theo cơ sở a, được ký hiệu là log, 8. là một SỐ nguyên duy nhất x với 0< x<n—1 sao cho đ = đ”.

Trên mọi cấu trúc nhóm cyclic nếu biết trước @ và x mà cần

tính 2 =a thì đây là một việc dé và được thực hiện trong thời gian

đa thức. Ngược lại biết Z, Ø8 mà tinh x thi đây là một việc khó va

được thực hiện trong thời gian hàm mũ. ;

1.2. Bai tốn logarithm roi rac trên trường sơ thực

Bài tốn thuận: y=a",x ER, việc tính tốn hàm mũ này có thé được thực hiện dễ dàng bằng thuật tốn nhân và bình phương.

Bai tốn ngược: y=log x,x>0, việc tính tốn hàm ngược

logarit này sẽ khó khăn hon nhiều so với hàm thuận. Tuy nhiên, cả

hai phép hàm mũ và logarit đêu là các hàm đơng biên cho nên có thê xác định giá trị tương đôi của hàm logarit được.

1.3. Bài toán logarithm rời rac trên trường hữu hạn

Bài toán thuận: y= #” mod p,x € GF(p) =

_p

Bài toán ngược: y=log, xmod

p,xeŒF(p)/{0}=-1.4. Thuật toán giải

1.4.1. Thuật toán vét cạn

Đây là thuật toán tự nhiên nhất và kém hiệu quả nhất dé tính Logarithm rời rạc. Người ta sẽ thử tất cả các khả năng xem khả năng nào là nghiệm đúng của bài toán cần giải nhất.

Ưu điểm: Tìm ra nghiệm một cách chắc chắn, có thể áp dụng

<small>cho moi loại bài toán.</small>

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

-4-Nhược điểm: Số bước tính tốn lớn do vậy sẽ tốn thời gian để

<small>tìm nghiệm bài tốn.</small>

1.4.2. Thuật tốn bước đi lớn bước di nhé

Giả sử m =| Vn | với n là cẤp của a.

Thuật toán bước đi lớn bước đi nhỏ là sự thoả hiệp giữa thời gian và bộ nhớ của phương pháp vét cạn và dựa trên quan sát sau là

nếu /đ=ø* thì chúng có thê viết x =im+j với Ư<¡ï, j<m. Từ

đó a =a'"a! hay B(a”)' =a7! . Vậy nên người ta có thể lập

bảng (j,a’) với 0 <j<m.

Sau đó lần lượt tính (a)! với i lần lượt chạy từ 0 đến m—1 và tra trong bảng (j,a’) chừng nào có được dang thức Bia")! =a

<small>thì dừng lại.</small>

Thuật tốn này địi hỏi khơng gian lưu trữ là Own ) phan tử

nhóm và địi hỏi OWn) phép nhân dé xây dựng và Own logn)

phép so sánh dé sắp xếp. Ngồi ra nó cũng can Own) phép toan

nhan va Own ) phép toán tra bang. Tựu chung là nó có thời gian

chạy Own ) phép tốn nhóm.

<small>1.4.3. Thuật toán p của Pollard</small>

<small>Đây là thuật toán ngẫu nhiên với cùng thời gian chạy như trong thuậttoán bước đi lớn bước đi nhỏ nhưng không cần đến không gian lưu trữ</small>

Nó chia nhóm G thành ba tập Si, S›, S3 như nhau dựa trên tính <small>chat dé kiêm nghiệm. Định nghĩa day các phân tử của nhóm xo, x1, x2,</small>

.. VỚI Xo= 1 như sau:

<small>`. Nếu x; € S;</small>

Xia *= f(x) # {| xỉ Nếu x; € Sp.

<small>a.X; Nếu x; € S3</small>

đối với ¡>0.

Day các phần tử của nhóm sẽ xác định hai dãy số nguyên ao, đi,

da, ... va bọ, bị, bạ, ... thoả mãn x, = ø" Ø8” với i >0 và với ao= 0, bo

<small>= 0thì:</small>

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

Người ta áp dụng thuật tốn tìm chu trình cua Floyd dé tìm hai

phan tử của nhóm x,,x,,sao cho x,=x,,. Từ đó œ“/” =œ“:”

và do đó B" =a, Lay logarithm cả hai về theo cơ số @

<small>chúng ta thu được:</small>

(b, —b,,).log,, B = (4, — a,)(modn)

Với điều kiện là b #b,,(modn) thì chúng ta có thể dé dàng giải phương trình đồng dư này để tính ra log„/. Trên thực tế thì xác

xuất dé cho b, #b, (modn) là rất nhỏ và có thé bỏ qua.

Thuật tốn này được thực hiện giống như hình chữ / với điểm xuất phát là chân chữ này và vịng trịn phía trên chính là khi thuật

tốn rơi vào chu trình. Chính vì vậy mà nó được gọi là thuật tốn Ø do Pollard nghĩ ra.

1.4.4. Thuật toán Pohlig-Hellman

Thuật toán này tận dụng lợi thế của phân rã của cấp n của nhóm G. Giả sử phân rã của n= p,^ p,°”...p,” là phân rã nguyên tố của n.

Nếu x=log, thi cách tiếp cận này xác định x,=xmod p,“ với

1<¡<r và sau đó sử dụng thuật tốn Gauss làm việc với định lý

phan dư Trung Hoa dé tìm ra xmodn.

Mỗi số x; được tính theo các chữ số /„„/,.../ „ trong biểu

_e-l

diễn p, phân rã của x, =/,+/,p, +. +, pe với 0<ƒ,<p,—1. Gia

</div><span class="text_page_counter">Trang 6</span><div class="page_container" data-page="6">

-6-Khi biết trước phân rã của ø thì thời gian chạy của thuật tốn

Pohlig-Hellman sẽ là 0 e,(log n+p, ) các phép tốn nhóm. Thuật

tốn này chỉ thực sự hiệu quả khi ước lượng nguyên tố p¡ của n tương đối nhỏ hay n là số ngun mịn.

1.4.5. Thuật tốn tính chỉ số

Thuật tốn tính chỉ số là thuật toán mạnh nhất được biết đến khi

đem tấn cơng bài tốn logarithm rời rạc. Khơng phải nhóm nào cũng có thể áp dụng thuật tốn tính chỉ số nhưng nêu áp dụng được thì nó <small>cho chúng ta thời gian chạy là hàm tiêu mũ.</small>

Thuật toán tính logarithm rời rạc đối với nhóm cyclic:

<small>Pau vào: Phan tử sinh ø của nhóm cyclic G có cấp n và phan</small>

tử BEG.

Đầu ra: Logarithm rời rạc y = log,

B-1. Chọn co sở phân tích S: Chon tap con $ = {P1, P2, ..., Pr } cua G

sao cho “một ty lệ đáng kê” cua tat ca các phan tử của G có thé được biểu diễn hiệu quả như là tích của các phan tử của S.

2. Chọn các quan hệ tuyến tính liên quan đến logarithm của các phần

Nếu thành công thi lay logarithm ca hai về của dang thức trên dé đạt

được quan hệ tuyên tính :

k= » log„p,(modn)

2.3.Lặp lại các bước 2.1 va 2.2 chừng nao f +c các quan hệ như trên

đạt được ( c là số tự nhiên nhỏ chang han c = 10 sao cho hé phuong

trình đã cho với f+c phương trình sẽ có nghiệm duy nhất với xác xuất cao ).

3. Tìm các logarithm của các phương trình trong S: Tính theo mod n

giải hệ phương trình có f+c phương trình với ân số giống như

trên tại bước 2 dé đạt được log, p,, với 1<i<t.

<small>4. Tính y:</small>

<small>i?</small>

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

Nếu cố gắng khơng đạt kết quả thì lặp lại bước 4.1. Ngược lại, lấy

logarithm cả hai về của đăng thức thu được để đạt được :

log, B Z=|[l.4 log, P; ~k) mod n

Va do đó chúng ta có được kết quả của thuật toán là:

-|>.4 log, D; -k)modn

1.4.6. Thuật tốn sàng trường số

<small>Thuật tốn sàng trường sơ tính logarithm rời rac trên GF(p) mởrộng trên cơ sở thuật tốn tinh chỉ sơ từ trường hữu han GF(p) sang</small> trường mở rộng Ø(z)với a là nghiệm cua một đa thức bat khả <small>quy f(x) trên Z[x] và có nghiệm m trên GF(p) hay f(m)=Omod p.</small>

Từ đây chúng ta có một đồng cấu vành tự nhiên từ

Z[œ]vào GF(p) được cảm sinh bởi g(a@)=m. Trong tính tốn

chúng ta sẽ mở rộng vào trường @(z) mà bỏ qua những vấn đề

tiềm tàng của phép chia. Trường số Q(q) là trường của các số đại số

và do đó cũng có một vành các số nguyên đại số trong trường này.

Lý do của việc mở rộng này là tạo ra cho giai đoạn sàng một <small>mơi trường tính tốn rộng hơn và do đó có khả năng cao hơn đê tìm</small> được các phân tử mịn trên cơ sở phân tích.

Vanh sơ ngun đại sơ Z[ œ ] có thê khơng có tính chat phân rã

duy nhất như vành số nguyên Z nhưng vành các ideal thì ln có

<small>phân rã duy nhât. Do đó mà chúng ta xây dựng thêm một cơ sở phần</small> tích các ideal B bên cạnh cơ sở phân tích S chỉ bao gơm các ideal có

chuẩn min. Ideal J của @(#) là mịn nếu nó phân rã hồn tồn trên cơ

sở phân tích các ideal 8 và số đại số x là mịn nếu ideal (x) là mịn.

Trong giai đoạn sàng phương pháp sàng trường số tìm ra mộtkhối lượng lớn các cặp (a,,b,) của các số nguyên nhỏ sao cho a,—bacũng là min. Do đó mà phân ra cua (a, —b,a) là đã biết.

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

-8-Chúng ta có thể sinh được nhiều vectơ (e,)sao cho ideal

II —b,a)' là lũy thừa đúng bậc (p—1). Điều này được thực

hiện nhờ phép biến đổi đại số tuyến tính theo modulo(p—1). Tuy

vậy, điều này khơng nhất thiết có nghĩa là số đại số IG — ba)” cũng là lũy thừa đúng bậc (p —1) trong (2z). Trên thực tế tích này mới trở thành đơn vị trong vành nguyên của Q(q). Sự tinh tế là ở

chỗ phan tử đơn vị trong vành ngun của @(z) cịn chưa có nghĩa là 1 như trong vành nguyên Z thông thường. Chúng ta còn cần đến một lần biến đổi nữa để cuối cùng chúng ta có tích II —ba)' =|

và như vậy chúng ta có:

ø({{ (4, —b,z)”) =1ámod p)

tức là: |

[|(4-2,)' =1(mod p)

Lấy logarithm đồng dư thức này chúng ta được:

Ye, log, (a, —b;m) =0(mod p—])

Nhưng mỗi số a; —b,m là mịn vì ideal đ;—# là mịn. Bởi vậy đồng

dư thức trên có thể được viết lại thành:

die, log ,g =0(mod p —1)

với B là tập tất cả các số nguyên tố nhỏ và mỗi €; là các số nguyên đã biết.

Khi các đơng dư thức như vậy tìm được đủ nhiêu người ta sẽ <small>giải hệ phương trình tuyên tinh đê tim ra được các log, q đô với</small>

những qạcB. Các số nguyên tố g như vậy được gọi là các số nguyên

tố tốt và trong giai đoạn này chúng ta đã tìm được logarithm của tất

cả các số nguyên tố tốt để sử dụng trong giai đoạn tìm logarithm của

thuật tốn tính chỉ số đặt ra. Giai đoạn này đồng nhất với những gì được thực hiện trong thuật tốn tính chỉ sơ thơng thường trên GF(p).

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

-0-Ưu điểm của logarithm rời rạc

Một lượng lớn các giao thức mà mật mã khóa cơng khai mang

lại, chăng hạn như chữ ký số và trao đổi khóa có thé được thực hiện

với RSA và các biến thể của nó. Các hệ mật dựa trên cặp là một

ngoại lệ nổi bật với quy tắc chung này. Tuy nhiên, ngay cả đối với các giao thức cô điển, sử dụng logarithm rời rac thay vì RSA như là

nguyên thủy cơ bản mang lại một sơ lợi ích nơi bật.

1.5.1. Kích thước khóa nhỏ

Ưu điểm chính của logarithm rời rạc đến từ thực tế rằng sự

phức tạp của việc giải quyết các bài toán logarithm rời rạc đường cong elliptic trên một đường cong elliptic tổng quát là, như ta đã biết,

cao hơn nhiều so với việc phân tích một sơ ngun có kích thước

tương đương. Như một hệ quả trực tiếp, các hệ mật đường cong

elliptic cung cấp các tùy chọn của việc sử dụng các kích thước khóa nhỏ hơn nhiều so với các yêu cầu của RSA của logarithm rời rạc trên các trường hữu hạn để có được một mức độ bảo mật tương đương.

Trên thực tế, việc giảm kích thước khóa là rất quan trọng mà nó hơn hiệu số mức độ phức tạp của số học đường cong elliptic. Vì vậy, với cùng mức độ bảo mật tổng thể, hệ thống đường cong elliptic hiện

tại tốt hơn hệ thống cơ điền.

1.5.2. Sự an tồn phía trước hoàn hảo

Khi sử dung RSA dé thiết lập một trao đổi khóa, phương pháp

thơng thường là cho một bên tạo ra một khóa bí mật ngẫu nhiên và

gửi nó đến bên khác được mã hóa với khóa cơng khai RSA của mình. Việc gửi này, đề một kẻ thù ghi lại tất cả lưu lượng truy cập, có khả

<small>năng giải mã tất cả thông tin liên lạc đã qua, nếu anh ta được giữ</small> khóa riêng tương ứng.

Ngược lại, một thiết kế chính xác giao thức trao đổi khóa dựa trên bài tốn logarithm rời rạc có thể tránh cái bẫy này và đạt được sự

an tồn phía trước hồn hảo, do đó ngăn ngừa được kẻ thù giải mã thơng tin đã qua.

1.5.3. Thuật tốn đa dạng

Các nhà mật mã học học đã học được từ lịch sử rằng việc dựa vào bảo mật trên một giả định duy nhất là _ khơng khơn ngoan, vì nếu

giải quyết được giả định này thì có thé dẫn đến đồng thời sự đồ vỡ

<small>của tất cả các hệ thống xây dựng trên nó. Vì lý do này, điều quan</small>

trọng là phải có một sự đa dạng của các hệ mật và có các hệ thống

thay thé. Các lược đồ dựa trên logarithm rời rac cung cấp một sự thay

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

-10-thế cho bài tốn phân tích có nguồn gốc từ RSA và các thuật toán bảo

mật khác mà phụ thuộc vào độ khó của bài tốn phân tích thừa SỐ.

<small>Tuy nhiên, ta nên lưu ý rang cả nhân tử số nguyên và logarithm</small> rời rac sẽ dé dang dé có được từ các máy tinh lượng tử. Do đó điều quan trọng là phải nghiên cứu ngay cả các hệ mật kỳ lạ hơn, như trên

lưới và mã chỉnh lỗi (Bài toán SVP — Shortest vector problem và bài

<small>toán LWE — Learning with errors).</small>

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

-|1-; l CHƯƠNGIH |

CÁC HỆ MẬT XÂY DỰNG TRÊN BÀI TOÁN LOGARITHM

RỜI RẠC

Chương này trình bày một số hệ mật xây dựng trên bài toán logarithm rời rạc và các biến thể của nó.

2.1. Hệ mật Pohlig-Hellman

<small>Thuật tốn mã hóa Pohlig-Hellman sử dụng lũy thừa modulo.</small>

Đối với thuật tốn mã hóa giá trị modulo p được chọn là một nguyên

tố lớn. Bản tin m được mã hóa c =m‘ mod p.Trong khi giải mã được

thực hiện bằng cách tăng bản mã c lên mũ d ( khóa giải mã)

m=c‘ mod p.

Số mũ mã hóa (hay khóa) được chọn là một số nguyên tố cùng

nhau với ø(p)= p—1 - hàm Phi-Euler.

Vip là số nguyên tố nên @(p) = p—l.

Khóa giải mã tương ứng d được tính bằng nghịch đảo của

emod ø(p).

d=e mod p—1=et?!mod p—l=e””' mod p-1

2.2. Trao đối khóa Diffie-Hellman

2.2.1. Trao đổi khóa trước Diffie-Hellman

Phương pháp trao đơi khóa trước Diffie-Hellman dùng dé thiết

lập một khóa bí mật giữa người gửi và người nhận mà khơng cần

dùng đến mã hóa cơng khai. Phương pháp này dùng hàm một chiều làm hàm logarithm rời rac. Diffie-Hellman khơng có ý nghĩa về mặt

mã hóa giống như RSA.

I) Số nguyên tố p và phan tử nguyên thủy € 2, công

<small>2) Atinh:</small>

K,,=@° mod p =b;` mod p

nho dung gia tri b, công khai nhận từ dau xác nhận của B va

<small>giá trị x mật riêng của anh ta.</small>

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

-12-3) Btinh:

<small>Ky;=ø” mod p =b„” mod p</small>

nhờ dùng giá trỊ b, công khai nhận từ dau xác nhận cua A và

<small>giá trị y mật riêng của anh ta.</small>

2.2.2. Trao doi khóa phiên Diffie-Hellman - Tham sé chung công khai của hệ thống:

p - số nguyên tô lớn, ø Vi phan tử nguyên thủy

- Đề nhận được khóa phiên chung cho mỗi phiên liên lạc A và B

thực hiện như sau:

<small>+ Atinh: K = £,* =a” mod p + Btinh: x = Ø8 =a” mod p</small>

2.2.3. Trao đổi khóa phiên có xác thực bên nhận

<small>- Bên nhận A chọn | sô nguyên tô lớn p, va 1 phân tử nguyên</small>

- B gửi thong tin về khóa này cho A

- Khóa chung được tính như sau:

+ Atính: 7“ =a,"

+ Btinh: £.* =a,

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

Giả thiết thành phần mạng Bob có khố w=r Và x =í, trong khi thành phần mạng Sue có khố w, =u và x,=v. Khi Bob gửi một ban

tin đên Sue, các g1ao thức sau được quan sát: <small>1.</small>

Bob tạo bản tin m sử dụng bộ ký tự A, không vượt quá độ dài tôi đa N.

Bob chuyên đôi bản tin m sang giá trị sô tương ứng

M L sử dung sơ đồ S.

Bob mã hố M bằng tính tốn "(mod p) và gửi kết qua đến Sue.

Sue tiếp tục mã hoá sự truyền dan bang cách tính tốn (M'(mod p))“(mod p)=MTM(mod p) và gửi kết

quả trả lại Bob.

Bob giải mã từng phần sự truyền bằng cách tính:

(MTM (mod p)} (mod p) =(M”)” (mod p)

-Do /=r'(modp-l), nên ;=l(modp-lI) bởi vậy

rt =l+s(p—T) với số ngun s nào đó.

Vì vậy:

</div>