DHAES: Sơ đồ mã hóa dựa trên thuật toán DIFFIE-HELLMAN

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 (2.79 MB, 16 trang )

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

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

NGUYEN TRUNG DUNG

DHAES: SƠ DO MA HOA DUA TREN THUẬT TOÁN

TOM TAT LUẬN VĂN THẠC SĨ

HÀ NỘI - 2014

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

Người hướng dẫn khoa học: GS. TS. NGUYÊN BÌNH

Phản biện 1: PGS. TS. BACH NHẬT HONG

Phản biện 2: PGS. TS. LÊ MỸ TÚ

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: 08h giờ, ngày 08 tháng 02 năm 2015.

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

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

MỞ ĐẦU

1. Tính cấp thiết của đề tài:

Thế kỷ XXI, thế kỷ công nghệ thông tin, thông tin đã và đang tác động trực tiếp đến mọi mặt hoạt động kinh tế xã hội của hầu hết các quốc gia trên thế giới. Thơng tin có một vai trị hết sức quan trọng, bởi vậy chúng ta phải

làm sao đảm bảo được tính trong suốt của thông tin, nghĩa là thông tin không

bị sai lệch, thay đơi, bị lộ trong q trình truyền từ nơi gui đến nơi nhận.

Với sự phát triển rất nhanh của cơng nghệ mạng máy tính, đặc biệt là mạng INTERNET thì khối lượng thơng tin ngày càng truyền tải nhiều hơn. Những tập đồn cơng nghiệp, những cơng ty đa quốc gia, thị trường chứng khóa, tiễn hành xử lý và truyền nhận thông tin đắt giá, những phiên giao dịch hay mua

bán cổ phiếu, trái phiếu đều được tiến hành qua mạng. Giờ đây với sự tăng

trưởng nhanh của các siêu thị điện tử, thương mại điện tử thì hàng ngày có

một khối lượng tiền rất lớn được lưu chuyền trên mạng toàn cầu INTERNET, vấn đề khó khăn đặt ra là làm sao giữ được thơng tin bí mật và giữ cho tiền

đên đúng được dia chỉ cân đền.

Hậu quả sẽ như thế nào nếu như những thông tin đặc biệt quan trọng bị

lộ ra bên ngồi, như vậy thơng tin đó sẽ khơng cịn tính ngun vẹn. Mã hóa

thơng tin là một trong các phương pháp đảm bảo tính bảo mật của thơng tin,

và nghiên cứu sơ đồ mã hóa DHAES dựa trên thuật toán Diffie-Hellman là

một trong những phương thức dé làm điều đó. Lam thé nào dé một bản tin sẽ

được “đóng gói” theo thứ tự dé khai thác tốt nhất các hoạt động nhóm (ví dụ,

phép lũy thừa mơ-đun) là lõi của mã hóa dựa trên thuật tốn Diffie-Hellman DHAES, và sơ đồ mã hóa này sẽ giúp chúng ta trả lời câu hỏi đó. DHAES sử dụng mã hóa đối xứng, bản tin xác thực, và hàm băm mã hóa. Nó cho phép

thiết lập một khóa bí mật chung để mã hóa dữ liệu sử dụng trên kênh truyền

thơng khơng an tồn mà khơng cần có sự thỏa thuận trước về khóa bí mật giữa hai bên. Khóa bí mật tạo ra sẽ được sử dụng đê mã hóa dữ liệu với

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

phương pháp mã hóa khóa đối xứng. Thêm nữa, DAHES: sơ đồ mã hóa dựa trên thuật tốn Diffie-Hellman có tính hiệu quả như sơ đồ mã hóa ElGamal nhưng lại có những tính năng bảo mật mãnh mẽ hơn. DHAES khơng chỉ có các tính năng cơ bản của một mã hóa an tồn (như là bảo mật dưới tấn cơng

bản rõ chọn sẵn) mà còn đạt được bảo mật dưới tấn cơng bản mã chọn sẵn

tương thích và khơng tương thích. Sơ đồ này có tính linh hoạt cao hơn hắn, nó có thé được sử dụng trong bất kỳ van đề Diffie-Hellman phức tap nao, khơng chỉ nhóm các số ngun tố mà cịn cho nhóm các đường elip. Đưa ra một sơ đồ mới như DHAES, là dé cung cấp thêm một lý do đầy “hap dan” dé chúng ta đi vào phát triển các tiêu chuân mã hóa khóa cơng khai dựa trên giả thuyết Diffie-Hellman đã có.

2. Tổng quan về vấn đề nghiên cứu:

DHAES (the Diffie-Hellman based encryption scheme) chính là sơ đồ mã hóa dựa trên thuật tốn Diffie-Hellman. Sơ đồ này có tính hiệu quả như sơ đồ mã hóa ElGamal nhưng lại có những tính năng bảo mật mãnh mẽ hơn.

DHAES khơng chỉ có các tính năng cơ bản của một mã hóa an tồn (như là

bảo mật dưới tấn cơng bản rõ chọn sẵn) mà còn đạt được bảo mật dưới tấn cơng bản mã chọn sẵn tương thích và khơng tương thích. Sơ đồ này có tính

linh hoạt cao hơn han, nó có thé được sử dụng trong bat kỳ van dé Diffie-Hellman phức tạp nào, khơng chỉ nhóm các số ngun tổ mà cịn cho nhóm

các đường elip.

3. Mục đích nghiên cứu:

Nội dung luận văn được thực hiện nhằm nghiên cứu tổng quan về sơ đồ mã hóa dựa trên thuật tốn Diffie-Hellman, dé có thé sử dụng loại mật mã này đảm bảo cho tính an tồn trong thông tin liên lạc, với cách sử dụng linh hoạthơn các loại mã hóa đã cũ khác, nhưng lại có tính bảo mật mạnh mẽ, hơn nữa

lại cịn tương thích với các giả thuyết trên các nguyên lý cơ bản

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

. Đối tượng và phạm vi nghiên cứu: Bài tốn logarit rời rac

Thuật tốn Diffie-HellmanMã hóa ElGamal

Sơ đồ hệ mật hỗn hợp

. Phương pháp nghiên cứu và tiếp cận:

Nghiên cứu, thu thập các tài liệu đã xuât bản, các bài báo trên các tạpchí khoa học và các tài liệu trên mạng Internet liên quan đên vân đêđang nghiên cứu của các tác gia trong va ngoai nước. Từ đó chọn lọc va

sắp xếp lại theo ý tưởng của mình

Tìm hiêu, vận dung và kê thừa một sơ các hàm mat mã đã có trên

Internet

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

CHUONG I

TONG QUAN VE SO DO DHAES

1.1 Tong quan về so đồ DHAES

DHAES (the Diffie-Hellman based encryption scheme) chính là sơ đồ mã hóadựa trên thuật tốn Diffie-Hellman. Sơ đồ này có tính hiệu quả như sơ đồ mã hóa

ElGamal nhưng lại có những tính năng bảo mật mãnh mẽ hơn. DHAES khơng chỉ

có các tính năng cơ bản của một mã hóa an tồn (như là bảo mật dưới tấn cơng bảnrõ chọn sẵn) mà cịn đạt được bảo mật dưới tấn công bản mã chọn sẵn tương thíchvà khơng tương thích. Sơ đồ này có tính linh hoạt cao hơn han, nó có thé được sửdụng trong bat kỳ van dé Diffie-Hellman phức tạp nào, không chỉ nhóm các sốngun tố mà cịn cho nhóm các đường elip.

DHAES được xây dựng bằng một cách chung từ các nguyên thủy mức thấp: sơ

đồ mã hóa đối xứng, xác thực bản tin, các hoạt động nhóm trong một nhóm bat ky,

va hàm băm mật mã. Điều này dường như có vẻ khá giống với nhiều các mật mã

khác trừ hoạt động nhóm, nhưng nó chính là mật mã đã được bố sung với tính bảomật, chắc chắn hơn nhiều.

1.2 Bài tốn Diffie-Hellman

Bài tốn: / = (p,ø, Ø,y), trong đó p là số nguyên tố, a € 2s là phần tử

nguyên thủy, và ,ÿ € Zÿ

Mục tiêu: Tinh được B!°8¢’ mod p(= yÌ9%s 8 mod p)

Chọn số nguyên tố p sao cho bài tốn logarit rời rac Zy là khó giải. Chon a là phan tử nguyên thủy của Zp”. Giá trị a và p là công khai (người

dùng hoặc TT chọn).

Người dùng U chọn số mũ bí mat a„ (0 < a, <p— 2) và tính giá trị công khai tương ứng bY“ = a% mod p. Trong sơ đồ này, ID(U) là thông tin

định danh cho mỗi người sử dụng, ví dụ như thơng tin cá nhân như tên tuổi, nghề nghiệp,... TA (Trusted Authority) sẽ có sơ đồ chữ ký với thuật toán xác

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

minh (cơng khai) 0erzx và thuật tốn ký mật sigr„. Giả thiết thêm rằng tat cả các thông tin đều được chia nhỏ ra nhờ dùng hàm hash công khai trước khi

nó được kí. Đề đơn giản, ta sẽ không đưa hàm hash trong phần mô tả thủ tục.

Thông tin chắc chắn về người sử dụng U sẽ được xác thực bằng cách dùng dấu xác nhận (certificate) của TA và được TA kí. Mỗi người sử dụng U sẽ có một dấu xác nhận:

C(U) = UD(U), by, sigralD(U), bụ))

và TA không cần biết giá trị của ay. Dau xác nhận của người sử dung U sẽ được đóng vào khi U nối vào mạng. Có thể lưu các dấu xác nhận trong cơ sở

dữ liệu công khai hoặc mỗi người sử dụng có thể tự lưu dấu xác nhận của chính họ. Chữ ký của TA trên dấu xác nhận cho phép bất kỳ ai trên mạng đều có thê xác minh được thơng tin trên nó.

Khi đó U, V rất dé dàng tinh ra được khóa chung Kyy = œmodp

1.3 Dinh nghĩa so đồ DHAES

1.3.1 Sơ bộ

NHĨM ĐẠI DIỆN. DHAES sử dụng một nhóm hữu hạn tuần hoàn G =(g) (Ký hiệu này biểu thị rằng G được tạo bởi các phan tử g). Chúng ta

sẽ sử dụng cấp số nhân cho các hoạt động nhóm. Vì vậy, nếu cho u € N, thì g* biểu thị nhóm các phan tử của G mà kết quả có được từ việc nhân với g

trong u lần. Đương nhiên g° biểu thị cho phan tử đơn vị của G. Chú ý rang,

nếu # € N, sau đó, băng định lý Lagrange, thì ta có g“ = g1 mod|6l.

MÃ XÁC THỰC THÔNG BÁO: Một sơ đồ xác thực bản tin cho phépngười dùng chia sẻ một khóa bí mật dé gan dữ liệu cho mục đích xác thực vatính toàn vẹn. Sơ DHAES sẽ được sử dụng như là một sơ đồ. Bất kỳ yêu cầu

vê an ninh của sơ do đêu sẽ được đáp ứng đây đủ.

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

MÃ HÓA ĐÓI XỨNG. Sơ đồ mã hóa đối xứng cho phép người dùng

chia sẻ khóa dé mã hóa dữ liệu dé đạt được bảo mật. DHAES có thé sử dung bất kỳ sơ đồ nào đáp ứng được các yêu cầu bảo mật thích hợp được thảo luận

ở phan sau.

MÃ HOA BAT DOI XUNG. DHAES là sơ đồ với mã hóa bat đối

xứng. Cho Coins, Message, Ciphertext như trước va cho PK 3 {0,1}” va SK

> {0,1}* là tập hợp các chuỗi.

1.3.2 Sơ đồ DHAES

Đặt GROUP = (6, g,1) là nhóm đại diện, trong đó các phan tử nhóm được biểu diễn bởi các chuỗi có chiều dài gLen bit

Cho SYM=(SYM.enc, SYM.dec) là một sơ đồ mã hóa đối xứng với chiều dai

khóa eLen.

Cho MAC = (MAC.gen, MAC.ver) là một mã xác thực bản tin với chiều dài

khóa mLen và chiều dai thẻ là tLen.

Cho ham số H {0,1)291⁄" — {0,1}TMLenteLen

Từ những điều kiện ban đầu chúng ta xác định được sơ đồ mã hóa bất đối

DHAES = (DHAES.enc, DHAES.dec, DHAES. key)1.3.3 Chú ý

Công ước [23] kết hợp từng sơ đồ thành một “gia đình mã hóa” chính xác mà ba gia đình mã hóa dang được mơ tả: Bai tốn logarit rời rac trên cáctrường hữu hạn (DL- discrete logarithm); bài toán logarit rời rac trên nhóm

đường elip (EC- Eliptic curve); và thừa số nguyên (IF- integer factorization).

Bởi vì DHAES làm việc trên nhóm đại điện tuần hồn bat kỳ nên có thé định nghĩa môt cách tự nhiên hai sơ đồ DHAES theo định nghĩa [23]: DLES và

ECES.

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

1.4 Kết luận chương

Chương I đã giới thiệu tổng quan về một mơ hình sơ đồ mã hóa mới DHAES. Nhận thấy rằng đây là một sơ đồ có tính linh hoạt cao hơn, Song vẫn

đảm bảo được hiệu quả so với các sơ đồ mã hóa khác. Trong chương này, chúng ta đã quan tâm đến các chỉ tiết của mã hóa dựa trên thuật tốn

Diffie-Hellman - làm thé nào dé một bản tin sẽ được “đóng gói” theo thứ tự dé khai

thác tốt nhất các hoạt động nhóm (ví dụ, phép lũy thừa mơ-đun) là lõi của mã

hóa dựa trên thuật tốn Diffie-Hellman. DHAES sử dung mã hóa đối xứng, bản tin xác thực, và hàm băm mã hóa. Nó cho phép thiết lập một khóa bí mật

chung dé mã hóa dit liệu sử dụng trên kênh truyền thơng khơng an toan mà khơng cần có sự thỏa thuận trước về khóa bí mật giữa hai bên. Khóa bí mật

tạo ra sẽ được sử dụng dé mã hóa đữ liệu với phương pháp mã hóa khóa đối

xứng.

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

CHUONG II

CAC THUOC TINH UU VIET CUA SO DO

2.1 Mã hóa với Diffie-Hellman: sơ đồ ElGamal

Cho G là nhóm hữu hạn tuần hồn, G = Z _ nhóm lũy thừa mô-đun

phần nguyên của các số nguyên tô p. Chúng ta sẽ chỉ ra hoạt động nhóm của nhóm lũy thừa G, với mục dich để biểu diễn phép nhân lặp lại bang phép lũy thừa. Dat g là một phan tử sinh của G, do đó các phần tử của G bao gồm {g1, g2,..., gi“. Có định nhóm G và các phan tử sinh g của nó. Tất cả phép

nhân (hay phép lũy thừa được tính nhanh thay cho phép nhân lặp lại) sẽ được

đều được thực hiện trong G.

2.2 Những nhược điểm của mã hóa ElGamal

- Khơng gian bản tin hạn ché

- Có thể khơng cung cấp bảo mật tốt

- Muon có nhiễu hon bảo mật cơ bản.

2.3 Cách khắc phục những nhược điểm trong mã hóa ElGamal 2.3.1 Các tan cơng trên sơ đồ ElGamal

Một trong những lý do chính dé xây dung DHAES đó là không chỉ muốn sơđồ bảo vệ được thông tin về bản rõ trước sự hiện diện của một tấn cơng thụ động,mà cịn đạt được các mục đích mạnh mẽ hơn như là tính khơng dễ uốn dẻo (non-maleability) và an toàn bản rõ chọn san. Một van đề chính đối với sơ đồ ElGamal

đó là nó thất bại trong việc đạt được an toàn mạnh mẽ hơn trong bat ky nhom dai

dién nao. Trong thuc tế, sơ đồ ElGamal thậm chí khơng đạt được an tồn ngữ nghĩatrong một vai nhóm vi dụ như Z5 Dé làm rõ van dé này, chúng tôi sẽ cung cấp thêm

một sô các mẫu tán công trên sơ đô ElGamal.

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

2.3.2 Cách khắc phục những nhược điểm trong mã hóa ElGamal

Sơ đồ DHAES dựa trên thuật tốn Diffie-Hellman như đã được giới thiệu làmột cách dé khắc phục những hạn chế của mã hóa ElGamal, được trình bày ở trên,nhưng khơng có sự gia tăng đáng ké về chi phí nào. Các đặc tính khóa và lợi thé của

DHAES bao gồm những điều sau đây:

+ Bao mật cơ bản — đã được chứng minh có tính an tồn

+ Bên ngồi bao mật cơ bản: Tinh khơng mêm đẻo va an toàn bản mã chọn

sẵn — được chứng minh có tinh an tồn

+ Khơng oracle ngẫu nhiên.

+ Hiệu năng.

+ Da năng — Nhóm.

+ Da năng — các primitive phụ thuộc.

+ Không gian bản tin bat kỳ.

2.4 Thêm về bảo mật có thé chứng minh 2.5 Bảo mật cụ thể

2.6 Kết luận chương

Nội dung của chương đã đưa ra những vấn đề mà DHAES giải quyết được, và cácphương hướng đề giải quyết các vẫn đề này, cùng với đó là cung cấp thêm một chútnên tảng, so sánh với một sơ đồ mã hóa khác là ElGamal. Từ đó, có những cáchkhắc phục những nhược điểm của sơ đồ mã hóa ElGamal ở trong sơ đồ DHAES

này.

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

CHUONG III

MUC ĐỘ BAO MAT CUA SƠ DO

3.1 Cac bién thé

- BIEN THE LOI CUA DHAES.

- MOT VAI BIEN THE DUNG CUA DHAES

3.2 Giả thuyết bảo mật về các nguyên thủy DHAES

DHAES sử dụng ba nguyên thủy như đã thảo luận trong phan 1.1. Chúng ta yêu cầu các bộ tạo lý thuyết-nhóm (1) đúng với giả thuyết Diffie-Hellman; về sơ đồ mã hóa đối xứng; và mã xác thực bản tin.

3.2.1 Vấn đề Diffie-Hellman

GIA THUYET DIFFIE-HELLMAN. Chúng ta đề cập đến giả thuyết Diffie-Hellman tiêu chuẩn như một giả (huyết Diffie-Diffie-Hellman dùng tinh toán,

GIA THUYÉT DIFFIE-HELLMAN TINH QUYET ĐỊNH, DDH-A, một giả

thuyết mạnh hon đã được sử dụng phổ biến ngày nay.

GIẢ THUYET DIFFIE-HELLMAN BAM. Như đã nêu ở trên, bảo mật ngữ nghĩa của một sơ đồ dựa vào thuật tốn Diffie-Hellman địi hỏi chúng ta có

thé nhận được một số các bit “lõi phức tạp” từ khóa Diffie-Hellman, cụ thé khóa dẫn ra các bit mà không thê phân biệt được với các bit ngẫu nhiên.

GIA THUYET ĐỘC LẬP HDH: Bây giờ chúng ta sẽ củng cô giả thuyết HDH-A dé khăng định là nó cũng được sử dụng trong đại diện của các oracle mà có gửi thơng tin về các khóa DH, miễn là các khóa đó đủ “tính độc lập” với ví dụ mục tiêu.

GIẢ THUT ĐỘC LẬP HDH KHƠNG TƯƠNG THÍCH.LỰA CHỌN HÀM BĂM

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

3.2.2 Mã hóa đối xứng

An tồn của một sơ đồ mã hóa đối xứng được định nghĩa như trong [4], lần

lượt các khái niệm về an toàn đa thức được đưa ra trong [21, 26]. Chúng ta tưởng tượng một kẻ tan công mà chạy trong hai giai đoạn. Trong hai giai đoạn kẻ tấn cơng có thể truy vấn oracle mã hoa SYM mà trên đầu vao x, thu lai

được SYM.enc(K,z,r) với r lựa chọn ngẫu nhiên.

3.2.3 Mã xác thực thông báo

Bảo mật MAC được định nghĩa băng thử nghiệm mà đầu tiên chúng ta

chọn khóa ngẫu nhiên K € mKey và sau đó gửi cho tan cơng F một oracle

MAC.genx(-), chúng ta nói rằng đầu ra (x,t) của F khơng được yêu cầu

nếu như t* không phải đáp ứng của oracle MAC.gen,(-), đến truy van trước đó x”

3.2.4 Mã hóa bat đối xứng

- BAO MAT CHONG LAI TAN CONG BAN RO CHON SAN

- BAO MAT CHONG LAI TAN CONG BAN MA CHON SAN KHONG TUONG THICH.

- BAO MAT CHONG LAI TAN CONG BAN MA CHON SAN TƯƠNG

3.3 Bảo mật chống lại tan công ban rõ chọn sẵn

Tôi sẽ chỉ ra rằng DHAES||GROUP,SYM,MAC,H|| chịu khái niệm

không thể phân biệt được dưới tấn công bản rõ chọn sẵn, được định nghĩa

trong định nghĩa 6

Định lý 1 Cho GROUP là nhóm đại diện, SYM là sơ đồ mã hóa đối xứng và cho MAC là sơ đồ xác thực bản tin, và H là hàm. Cho DHAES là sơ

đồ mã hóa khóa bất đối xứng kèm theo các nguyên thủy như được định nghĩa

trong phan 1.2. Sau đó cho các số bat kỳ t, m, và mm

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

InSec2SY"(DHAES; t,m)

< 2-InSecP(GROUP,H; t,) + InSec®”TM (SYM; t;,0,1n, 1n),

Trong đó t, € O(t + TIME; + TIMEmac.gen(m')) và

tz € O(t + TIMEsywene(m) + TIME yac.gencm'y):

Thời gian ở phía trên là nhỏ; với tất cả các kết quả thực tế, t, va ty... có thé được xem đều là t

3.4 Bảo mật chống lại tan cơng bản mã chọn sẵn khơng tương thích

Chúng tôi chỉ ra rằng DHES||GROUP, SYM, MAC, H|| thỏa mãn các khái niệm về không phân biệt trong một tấn cơng bản mã chọn sẵn khơng

tương thích, như trong Định nghĩa 7

Định lý2 Cho GROUP là nhóm đại diện, SYM là so đồ mã hóa đối xứng, MAC là sơ đồ xác thực bản tin, và H là hàm. Cho DHAES là sơ đồ mã

hóa khóa bất đơi xứng được kết hợp với các nguyên thủy, như trong phan 1.2.

Do đó với bất kỳ các số t, q, u,1m vam’ ta có

InSecf*€^1(DHAES; t, q,u,1n) < InSec®”TM (SYM; t,,0,m,m’) +

InSec?""(H, GROUP; tz) + q.2~(912n+hien)31,

Trong do

t, EO (t + TIME; + TIMEwacgen (m))

tz € O( + TIMEsywene(m) + TIME yac.gencm’)

3.5 Bảo mật chống lại tan cơng bản mã chọn sẵn tương thích

Tơi sẽ chỉ ra rằng DHAES|[GROUP,SYM,MAC,H] thỏa mãn khái

niệm “không thể phân biệt được” dưới tấn công bản mã chọn sẵn tương thích như trong định nghĩa 8.

</div>