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

HỌC VIỆN CƠNG NGHỆ BƯU CHÍNH VIỄN THƠNG

NGUN QC KHÁNH

LOGARITHM RỜI RẠC TRONG CÁC TRƯỜNG HỮU HAN VÀ Ý NGHĨA MAT MA CUA CHUNG

CHUYEN NGANH: KY THUAT VIỄN THONG

MA SO: 60.52.02.08

TOM TAT LUẬN VAN THẠC SĨ

<small>HÀ NỘI - 2015</small>

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

<small>Luận văn được hoàn thành tại:</small>

<small>HỌC VIEN CƠNG NGHỆ BƯU CHÍNH VIÊN THONG</small>

<small>Phản biện l: ... eens ee ene tena SH.</small>

<small>Phản biện 2: ...--- Q22 Q22 2n n2 Hy</small>

<small>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</small>

<small>Cơng nghệ Bưu chính Viễn thơng</small>

<small>Vào lúc: ... giờ</small>

<small>Có thé tìm hiểu luận văn tai:</small>

<small>- Thư viện của Học viện Cơng nghệ Bưu chính Viễn thơng</small>

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

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

Ké từ khi có sự trao đổi thông tin giữa các đối tượng trong xã hội lồi người thì van dé bảo mật thơng tin được đặt ra như một nhu cầu tất yếu. Tuy nhiên, trong suốt nhiều thế kỷ, các kết quả nghiên cứu của lĩnh vực này hầu như không được ứng dụng trong các lĩnh vực dân sự thông thường của đời sống — xã hội mà chủ yếu được sử dụng trong lĩnh vực an ninh quốc phịng, chính trị, ngoại giao...Ngày nay các ứng

dụng bao mật thông tin đang được sử dụng ngày càng phổ biến trong các lĩnh vực dân

<small>sự như thương mại điện tử, ngân hàng.</small>

Đề đảm bảo các dịch vụ an toản này các nhà tốn học đã phát triển các thuật tốn mã hóa khác nhau. Từ những thuật tốn được cơng khai để mọi người cùng sử dụng

và áp dụng như một chuẩn chung cho việc mã hóa dữ liệu; đến thuật tốn mã hóa khơng được cơng bố. Có thé phân loại các thuật tốn mã hóa như sau: bao gồm mật

<small>mã khóa bi mật ( như DES, 3DES, RC4, AES...), mật mã khóa cơng khai (RSA,DIFIE —- HELLMAN...). Mật mã khóa bí mật: q trình mã hóa và giải mã thơng</small>

điệp sử dụng cùng một mã khóa gọi là khóa bí mật (secret key) hay khóa đối xứng (symmetric key). Do đó, van đề bảo mật thơng tin đã mã hóa hồn tồn phụ thuộc vào việc g1ữ bí mật nội dung của mã khóa đã được sử dụng. Với tốc độ và khả năng xử lý ngày càng được nâng cao của các bộ vi xử lý hiện nay, phương pháp mã hóa chuẩn

<small>(Data Encryption Standard — DES) đã trở nên khơng an tồn trong bảo mật thơng tin.</small>

Nếu như vấn đề khó khăn đặt ra đối với các phương pháp mã hóa bí mật là bài tốn trao đổi mã khóa thì ngược lại, các phương pháp mã hóa khóa cơng khai giúp cho việc trao đổi mã khóa trở nên dé dàng hơn. Nội dung của khóa cơng khai (public key) khơng cần phải giữ bí mật như đối với khóa bí mật trong các phương pháp mã

hóa bí mật. Vấn đề đặt ra đối với mật mã khóa cơng khai chính là phải tìm hàm

ngược (giải mã) phải là rất khó khăn (đối với bat kỳ ai không được trao quyền giải mã). Ta nhận thấy bài tốn logarithm rời rạc là một bài tốn khó (chưa có một thuật tốn nào hiệu qua dé tinh logarithm rời rac một cách tổng quát) trong khi bài toán lũy

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

thừa rời rạc lại khơng khó (có thể sử dụng thuật tốn bình phương và nhân). Với mục

đích là nghiên cứu tìm hiểu các hệ mật mã khóa cơng khai được sinh ra dựa trên bài toán logarithm rời rạc trên trường hữu hạn đồng thời nghiên cứu thêm các thuật giải

<small>của bài tốn đó.</small>

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

<small>Luận văn tập trung vào nghiên cứu, phân tích các thuật giải của bài tốn logarithm</small>

rời rạc như phương pháp số mũ con hay thuật toán tính chỉ số. Đồng thời đưa ra các tính tốn chỉ tiết cho các phương pháp này cùng với việc phân tích, tính tốn một vài

cải tiến cho các thuật toán dé giúp các thuật toán hoạt động hiệu quả hơn về nhiều

<small>phương diện.</small>

<small>Mục tiêu nghiên cứu của luận án:</small>

<small>Nghiên cứu, phân tích, tính tốn các thuật giải của bài toán logarith rời rạc trongtrường hữu hạn và các phương pháp giải của chúng.</small>

Đưa ra các cải tiến về một vài mặt làm cho thuật toán hiệu quả hơn trong thực té tính tốn va so sánh chúng với các thuật tốn, cải tiễn đã biết trước đó.

<small>Phương pháp nghiên cứu:</small>

Tìm hiểu chung về bài tốn logarithm rời rạc và các hệ mật có liên quan, đưa ra

các khái niệm, tính tốn chung về bài tốn này. Đi sâu vào tìm hiểu các thuật giải cụ thé cùng các phương thức tính tốn trong đó, bảng số liệu v.v...Cudi cùng là việc

triển khai các ý tưởng và những van đề còn tồn tại dành cho các nghiên cứu về sau.

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

<small>> Chương I. Bài toán Logarithm rời rac và các hệ mật có liên quan</small>

> Chương II. Một số thuật giải của bài toán Logarithm rời rac

> Chương . Ý nghĩa mật mã và phân tích hệ số của bài tốn Logarithm rời

<small>Phân ci cùng bao gôm các két luận về kêt quả dat được của luận van.</small>

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

<small>CHƯƠNG I</small>

BÀI TOÁN LOGARITHM ROI RAC VÀ CÁC HE MAT CĨ LIÊN QUAN

Chương này mơ tả khái quát về mật mã học và các bài toán quan trọng của mật mã gom: Bài toán logarithm rời rac và các hệ mật có liên quan; bài tốn phân tích thừa số (RSA); bài tốn đường cong Elliptic, dong thời phân tích sơ lược một số

<small>thuật tốn cùng một vài ví dụ mình họa.</small>

1.1 Tổng quan về mật mã học

Mật mã học là ngành khoa học ứng dụng tốn học vào việc biến đơi thơng tin thành một dạng khác với mục đích che dấu nội dung, ý nghĩa thơng tin cần mã hóa.

Day là một ngành quan trọng và có nhiều ứng dung trong đời sống xã hội. Ngày nay, các ứng dụng mã hóa và bảo mật thông tin đang được sử dụng ngày càng phố biến hơn trong các lĩnh vực khác nhau trên thế giới, từ lĩnh vực an ninh, quân sự, quốc phòng..., cho đến các lĩnh vực dân sự như thương mại điện tử, ngân hang....

<small>1.1.1 Bài toán logarithm rời rạc</small>

Nhiều hệ mật khóa cơng khai phổ biến dựa trên lũy thừa rời rac. Nếu G là một nhóm nhân, như nhóm các phần tử khả nghịch trong một trường hữu hạn hoặc nhóm

các điểm trên một đường cong Elliptic, và g là một phan tử của G, ø" là lũy thừa rời rac cua g VỚI số mũ x. Hoạt động này chia sẻ các tính chất cơ bản với lũy thừa thơng

<small>thường, ví dụ g*”</small>

= ø@`. g’. Các hoạt động nghịch đảo, cho h trong G, dé xác định

một giá trỊ của x, nếu nó tơn tại, sao cho h = ø'”. Như một số x được gọi là logarithm rời rac của h với cơ sở ø, vì nó chia sẻ nhiều tính chất với logarithm thơng thường.

Nếu, bên cạnh đó, ta yêu cầu một vài chuẩn hóa của x để hạn chế các câu trả lời có

thé cho giá trị hợp lệ duy nhất thì ta có thé nói về logarithm rời rac của h. Thật vậy, nếu khơng có chuẩn hóa như vậy, x khơng phải là duy nhất và chỉ được xác định theo

modul thứ tự của phan tử g.

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

1.1.1.1 Bài toán Logarithm trên trường số thực

Bài toán thuận: y =a", xe R, 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 toán nhân và bình phương.

<small>Bài tốn ngược: y=log,x, x>0, việc tính tốn hàm ngược logarit này sẽ khó</small>

khăn hơn 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.

<small>1.1.1.2 Bài toán Logarithm trên trường hữu hạn GF(p)Bài toán thuận: y=a* modp, xeGF(p)=Z„</small>

<small>Bài toán ngược: y=log, xmod p,xeGF(p)/{0)=Z,</small>

1.1.1.3 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.

1) Số nguyên tổ p và phan tử ngun thủy @ €Z* cơng khai

<small>2) A tính :</small>

<small>K,, =a” mod p =b;` mod p</small>

nhờ dùng giá trị 5, công khai nhận từ dau xác nhận của B và giá tri x mật

<small>riêng của anh ta.3) Btinh:</small>

<small>K,, =a” mod p=b,” mod p</small>

nhờ dùng giá trị b, công khai nhận từ dấu xác nhận của A và giá tri y mật riêng

<small>của anh ta.</small>

1.1.1.4 Sơ đồ phân phối khóa trước Diffie-Hellman

1. Số nguyên tố p và phan tử nguyên thủy a e 2, cơng khai

<small>2. A tính :</small>

<small>K,, =a” mod p =b,” mod p</small>

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

nhờ dùng giá trị b, công khai nhận từ dau xác nhận của B và giá trị x mật riêng

<small>của anh ta.</small>

<small>3. B tinh:</small>

<small>K,, =a” mod p=b,” mod p</small>

nhờ dùng giá tri b, công khai nhận từ dau xác nhận của A và giá trị y mật riêng

<small>của anh ta.</small>

<small>1.1.1.5 Ví dụ 1.1</small>

<small>Gia Sử p=25307,œxz =2 khóa cơng khai.</small>

Giả thiết A chọn x=3578 và tính:

<small>b, =a mod p =2" mod25307 =6113</small> đặt trên dấu xác nhận của A.

1.1.1.6 Trao đối khóa phiên Diffie-Hellman - Tham số chung công khai của hệ thống:

p - số nguyên tô lớn, we Z;- phần tử nguyên thủy

- Dé 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ư

<small>A B</small>

<small>+ Achonx ngau nhiên (l<x<p-l) va + Bchony ngau nhiên (1< y< p-l)</small>

tính: ø, =ø' mod p rồi gửi cho B. và tính: ø,=zø'modp rồi gửi cho

<small>+ A tinh: =ø,'=z*modp A.</small>

<small>+ B tinh: «=2,) =a" modp</small>

<small>1.1.2 Hé mat Omura-Massey</small>

Hé mat Omura-Massey truyén thong la mot hé thong dựa trên ham mũ su dung

một modulo cơ ban. Do đó một người giải mã có thể có được khóa mã hóa và modulo có thé dé dàng tính tốn các khóa giải mã tương ứng và giải mã bản tin bị chặn.

1.1.2.1 Thiết lập hệ thống thông tin

<small>1. Một bộ ký tự A được chọn</small>

2. Một độ dài bản tin tối da N được xác định. Vậy N là số ký tự tối đa của bản tin.

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

. Sơ đồ S được xác định dé chuyền đổi ban tin dang ký tự sang dang số và ngược

Số nguyên L lớn nhất có thé biểu diễn bản tin được xác định dựa trên ký tự A,

độ dài tối đa N và sơ đồ S.

. Một số nguyên tố p>L được chọn là modul mạng.

Đối với mỗi thành phần của mạng, một số nguyên w, được lựa chọn như là <small>một khóa mã hóa dạng gcd{w,,p—I} =1.</small>

Với mỗi số nguyên w,, x =w;'(modp-1) được tính như khóa giải mã. Sự tồn tại của x, được đảm bao do w, là một thành phần của nhóm các đơn vị theo

<small>modul p-1, việc tính toán của x, đạt được nhờ sử dụng thuật toán Euclide.</small>

Mỗi thành phần mạng được cung cấp khóa mã hóa riêng với khóa giải mã

<small>riêng w,,x, tương Ứng.</small>

. Các tham số A,N,S,L và p được công khai. Mặt khác w, và x, là các khóa riêng, do đó nó được biết đến như là khóa trung tâm và các thành phan mạng

riêng biệt có thé gan chúng từ đó.

<small>1.1.2.2 Giao thức tương ứng</small>

Giả thiết thành phần mang Bob có khố w,=r va x =:, trong khi thành phan mang

<small>Sue có khoá w,=„ và x,=v. Khi Bob gửi một bản tin dén Sue, các giao thức sau được</small>

<small>quan sát:</small>

FY NP

^{Bob tạo bản tin m sử dụng bộ ký tu A, không vượt qua độ dai tôi đa N.}

Bob chuyền đổi bản tin m sang giá trị số tương ứng M < L sử dụng sơ đồ S.

Bob mã hoá M băng tính tốn 1'(modp) và gửi kết quả đến Sue.

Sue tiếp tục mã hố sự truyền dẫn bằng cách tính toán

(M” (mod p))“(mod p) = M “(mod p) Và gui kết quả trả lại Bob.

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

<small>(M “(mod p)) (mod p) =(M")" (mod p) </small>

<small>-Do ¡=z'(modp—I), nên rr=1(modp—1) bởi Vay rt =1+s(p—1) VỚI SƠ ngun s nào đó.</small>

<small>Vi vậy:</small>

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

(M")" (mod p) = ("mod p) =M"(M?")"(modp) Tuy nhiên do <L<p và p là số

nguyên t6, gcd{M,p}=1. Vì vay w”ˆ =1(mod p) theo định ly Fermat. Do đó ÉM'-(M?ˆ”)°(mod p) = M"(mod p). Bob gửi két qua nay dén Sue.

6. Sue kết thúc q trình giải mã bang cách tính:

<small>(M“(mod p))’ (mod p)=M" (mod p)=M (mod p) bởi một vài lý do như bước 5</small>

<small>v=z'(mod p—1). Hơn nữa (mod p)= dO M<L<p.</small>

7. Sau đó Sue chuyên M lại với ký tự tương ứng sử dung sơ đồ S và đọc bản tin

<small>của Bob.</small>

<small>1.1.3 Hệ mật ElGamal dạng hàm mũ</small>

<small>Mỗi bên liên lac A và B tạo cho mình 1 cặp khóa cơng khai — bí mật theo các</small>

<small>bước sau:</small>

- Bước 1: A chọn 1 số nguyên tố lớn p, và một phần tử nguyên thủy zø, eZ/,

- Bước 2: A chon I số nguyên tố ngẫu nhiên a (2 <a < p—2) và tính: a,’ = 8,

<small>- Bước 3: Khóa cơng khai cua A: (p,,z,,Ø,). Khóa bí mật của A: a</small>

<small>Tương tự: Khóa cơng khai cua B: (p,,a,,8,). Khóa bi mật của B: b</small>

Giả sử B cần gửi bản tin meZ; cho A. B cần thực hiện các bước sau:

<small>- Bước |: B nhận khóa cơng khai của A: (p,,z,,/,)</small>

<small>- Bước 2: B chon x ngẫu nhiên (2< x< p—2) và tính:</small>

<small>- Bước 5: B tinh: 5=m' mod p</small>

<small>- Bước 6: B gửi ban mã c= (y,5) cho A.</small>

<small>A nhận e = (z, ở) và giải mã m băng cách thực hiện các bước sau:</small>

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

Hệ mật này sử dụng các tính tốn trong Z,, trong đó n là tích của 2 số nguyên

tố phân biệt p và ạ. Ta nhận thấy rằng ý(n)=(p—1)(a-1).

Ta kiểm tra xem các phép mã và giải mã có phải là các phép tốn nghịch đảo

<small>của nhau hay khơng. Vì</small>

ab = 1(mod ¢(n))

<small>nên ta có ab =tĨ(n)+l</small>

<small>1.1.5 Bài tốn đường cong Elliptic</small>

Cho p>3 là một số nguyên tố. Đường cong elliptic y? =x°+ax +b trên Z,, là

một tập các cặp (x,y)eZ,xZ, thỏa mãn đồng dư thức yŸ =x°+ ax + b(mod p)

trong đó a,beZ, là các hằng số sao cho 4z`+27? #0(mod p) cùng với một điểm đặc biệt O gọi là điểm vơ cực.

Đường cong elliptic E có thé tạo thành một nhóm Aben bằng cách xác định một phép

tốn thích hợp trên các điểm của nó. Phép tồn này là phép cộng và được xác định như sau (ở đây mọi phép toán số học được thực hiện trên Z,)

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

<small>CHƯƠNG II</small>

MỘT SÓ THUẬT GIẢI CỦA BÀI TỐN LOGARITHM

RỜI RẠC

Trong chương này ta trình bày thuật tốn đa năng mà được biết đến ngày nay là thuật tốn tính chỉ số dong thời phân tích biểu diễn gan đúng của thuật toán. Một

sự cải tiễn đáng kề gan day trong trường GF (2") duoc lam boi Coppersmith sé duoc phán tích tương đối cụ thể, cùng với đó là một số vấn đề kỹ thuật mà quan trọng của

thuật tốn tính chỉ số như là các phương thức nhanh để giải hệ các phương trình tuyến tính.

<small>2.1 Giới thiệu</small>

Cho mỗi phan tử nguyên thủy s của một trường hữu hạn GF(q), logarithm rời rac của một phan tử khác 0 weGF(q) là số nguyên k, 1<k<q-1, thỏa mãn w=". Việc nhân các nhóm con của trường hữu hạn GF(q), q là số nguyên tố, là vành, và

các phần tử g eGF(4) sinh ra nhóm con nay được coi như các phan tử nguyên thủy. Một phan tử nguyên thủy g và một vai we GF (q) =GF(4)—{0}, logarithm rời rac của

u đối với g là số nguyên k,0<k<q—1,sao cho

Chúng ta viết k =log,u . Logarithm rời rac của u thì đơi khi xem như chi số

<small>của u.</small>

2.2 Một số thuật giải đặc biệt

Trong phần này ta trình bày vắn tắt một vài thuật tốn mà khơng làm việc thật

tốt và sau đó ta thảo luận một thuật toán hữu hiệu mà làm việc tốt chỉ khi hầu hết g-1 các số chia nguyên là có độ lớn thích hợp.

Giải pháp khác dé tính tốn logarithm rời rac trong các trường GF (2") được

làm bởi Arazi ông chú thích rang nếu một ai đó có thé nhanh chóng tự xác định

logarithm rời rac của u, sau đó ai đó có thé nhanh chóng logarithm rời rac của chính

<small>nó. Arazi chi ra rang một ai đó có thê xác định chăn lẻ cua logarithm rời rac đê dựa</small>

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

nhanh vào g nếu ø thỏa mãn thêm một vài điều kiện phức tạp. Từ khi có thể tính tốn

logarithm rời rạc tới việc cho phép ai đó tính tốn chúng tới bất kỳ cái khác dựa trên

tốc độ nhanh như nhau, nó sẽ đủ tìm một số ø mà thỏa mãn điều kiện của Arazi.

Ta thảo luận một thuật tốn rất quan trọng mà được cơng bố bởi Pohlig và

<small>Hellman. Thuật tốn này tính tốn logarithm rời rac trên GF(z) sử dụng trên bậc của</small>

toán tử /p và một lượng tương thích lớn, ở đây p là nhân tố nguyên thủy lớn nhất

<small>của q-l.</small>

Thuật toán Silver-Pohlig-Hellman hiệu quả bất kỳ khi nào tất cả các hệ số ngun của q—1 là nhỏ một cách thích hợp (nó hiệu quả nhất trong các trường mà q là một số ngun tơ Fermat, ạ=2”+1, là phương thức thuật tốn đa thức thời gian logarithm rời rạc). Vì thế việc lựa chọn các trường GF(q) là mỗi quan tâm lớn cho

<small>việc sử dụng trong mật mã.</small>

2.3 Phương thức logarithm rời rạc số mũ con

2.3.1 Thuật tốn tính chỉ số

<small>Thuật tốn đã được phát minh độc lập bởi Adleman, Merkle, và Pollard. Việc</small>

tính tốn độ phức tạp của nó được thực hiện một phần bởi Adleman và đó xem là

thuật tốn tính chỉ SỐ. Một phân tích tiệm cận mở rộng của thuật toán trong trường

hợp này và liên quan các trường hợp GF(p") với p có định va „->œ được cho gần đây bởi Hellman và Reyneri. Vì thế sẽ được chỉ ra bên dưới, thời gian chạy của thuật toán là ước lượng thực tế của chúng .

2.3.1.1 Giai đoạn đầu của phương thức tính chỉ số logarithm rời rạc

Giai đoạn bao gồm tính tốn logarithm rời rạc (đối với g(x)) của các phần tử

được chọn của GF(2) là một tập s. Tập S thường bao gồm tat cả các đa thức bat kha quy trên GF(2) bac <m. Ở đây m được chọn thích hợp. Khi trạng thái tiền xử lý được hồn thành, thuật tốn có thể được tính tốn tương đối nhanh chóng.

2.3.1.2 Giai đoạn thứ hai của phương thức tính chỉ số logarithm rời rạc

Giai đoạn thứ hai của thuật tốn tính chỉ số u cau thời gian dé tính logarithm

<small>rời rạc đơn là</small>

</div>