Nghiên cứu xây dựng thuật toán tấn công hệ mật RSA

i

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN&TRUYỀN THÔNG

VÕ TÁ HOÀNG

NGHIÊN CỨU XÂY DỰNG

THUẬT TOÁN TẤN CÔNG HỆ MẬT RSA

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

Thái Nguyên – 2020

ii

LỜI CAM ĐOAN

Học viên xin cam đoan luận văn này là công trình nghiên cứu thực sự của

bản thân, dưới sự hướng dẫn khoa học của TS. Hồ Văn Canh.

Các số liệu, kết quả trong luận văn là trung thực và chưa từng được công

bố dưới bất cứ hình thức nào. Tất cả các nội dung tham khảo, kế thừa của các tác

giả khác đều được trích dẫn đầy đủ.

Em xin chịu trách nhiệm về nghiên cứu của mình.

Người cam đoan

Võ Tá Hoàng

iii

LỜI CẢM ƠN

Học viên trân trọng cảm ơn sự quan tâm, tạo điều kiện và động viên của

Lãnh đạo Trường Đại học Thái Nguyên, các thầy cô Khoa Đào tạo sau đại học,

các khoa đào tạo và các quý phòng ban Học viện trong suốt thời gian qua.

Học viên xin bày tỏ sự biết ơn sâu sắc tới TS. Hồ Văn Canhđã nhiệt tình định

hướng, bồi dưỡng, hướng dẫn học viên thực hiện các nội dung khoa học trong

suốt quá trình nghiên cứu, thực hiện luận văn.

Xin chân thành cảm ơn sự động viên, giúp đỡ to lớn từ phía Cơ quan đơn

vị, đồng nghiệp và gia đình đã hỗ trợ học viên trong suốt quá trình triển khai các

nội dung nghiên cứu.

Mặc dù học viên đã rất cố gắng, tuy nhiên, luận văn không tránh khỏi những

thiếu sót. Học viên kính mong nhận được sự đóng góp từ phía Cơ sở đào tạo, quý

thầy cô, các nhà khoa học để tiếp tục hoàn thiện và tạo cơ sở cho những nghiên

cứu tiếp theo.

Xin trân trọng cảm ơn!

Hà Nội, tháng năm 2020

Học viên

Võ Tá Hoàng

iv

MỤC LỤC

LỜI CAM ĐOAN...................................................................................................i

LỜI CẢM ƠN ......................................................................................................iii

MỤC LỤC............................................................................................................iv

DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT...............................................vii

DANH MỤC HÌNH VẼ, BẢNG BIỂU .............................................................viii

MỞ ĐẦU............................................................................................................... 1

CHƯƠNG 1: TÌM HIỂU VỀ HỆ MẬT RSA....................................................... 4

1.1 Hệ mật mã hóa RSA........................................................................................ 4

1.1.1 Mô tả hệ mật RSA.................................................................................... 4

1.1.2 Thực thi hệ mật RSA................................................................................ 6

1.1.3 Vấn đề an toàn của hệ mật RSA............................................................... 6

1.2 Tính an toàn của hệ mật mã RSA.................................................................... 7

1.2.1 An toàn vô điều kiện ................................................................................ 7

1.2.2 An toàn được chứng minh........................................................................ 7

1.2.3 An toàn tính toán ...................................................................................... 7

1.3 Các kiểu thám mã ............................................................................................ 8

1.3.1 Bài toán thám mã chỉ biết bản mã............................................................ 9

1.3.2 Bài toán thám mã khi các cặp rõ/ mã đã biết ........................................... 9

1.3.3 Bài toán thám mã với bản rõ lựa chọn ..................................................... 9

1.3.4 Bài toán thám mã với bản mã lựa chọn.................................................... 9

1.4 Tấn công hệ mật RSA lợi dụng những lỗ hổng của chúng ............................. 9

1.4.1 Biết (n) tìm được p, q ........................................................................... 10

1.4.2 Biết số mũ bí mật của RSA.................................................................... 10

1.4.3 Giao thức công chứng ............................................................................ 12

1.4.4 Giao thức module n chung ..................................................................... 14

1.4.5 Giao thức số mũ công khai nhỏ.............................................................. 20

1.4.6 Giao thức số mũ bí mật nhỏ ................................................................... 21

v

1.4.7 Trường hợp các tham số p-1 và q-1 có các ước nguyên tố nhỏ............. 24

Kết luận Chương 1 .............................................................................................. 26

CHƯƠNG 2: NGHIÊN CỨU MỘT SỐ THUẬT TOÁN TẤN CÔNG HỆ MẬT

RSA ..................................................................................................................... 27

2.1 Kiểm tra tính nguyên tố của một số .............................................................. 27

2.1.1 Đặt bài toán ............................................................................................ 27

2.1.2 Các thuật toán kiểm tra tính nguyên tố theo xác suất ............................ 28

2.1.2.1 Thuật toán Fermat ............................................................................... 29

2.1.2.2 Thuật toán Solovay-Strassen............................................................... 29

2.1.2.3 Thuật toán Miller-Rabin...................................................................... 30

2.1.2.4 So sánh thuật toán Fermat, Solovay-Strassen và Miller - Rabin ........ 31

2.1.2.5 Kiểm tra tính nguyên tố của số nguyên tố Mersenne.......................... 32

2.1.2.6 Một số thuật toán kiểm tra tính nguyên tố khác.................................. 32

2.2 Các thuật toán phân tích thừa số ................................................................... 34

2.2.1 Thuật toán tìm nhân tử lớn nhất thứ nhất............................................... 34

2.2.2 Thuật toán phân tích thứ hai................................................................... 37

2.2.3 Thuật toán phân tích thứ ba.................................................................... 38

Kết luận Chương 2 .............................................................................................. 42

CHƯƠNG 3: ĐỀ XUẤT THUẬT TOÁN TẤN CÔNG RSA KHÔNG CẦN

PHÂN TÍCH NHÂN TỬ..................................................................................... 43

3.1 Mở đầu........................................................................................................... 43

3.2 Cơ sở toán học của thuật toán ....................................................................... 44

3.2.1 Một số mệnh đề ...................................................................................... 44

3.2.2 Xác định hàm ф(n)................................................................................. 45

3.3 Đề xuất thuật toán ......................................................................................... 46

3.3.1 Lưu đồ giải thuật .................................................................................... 46

3.3.2 Xây dựng chương trình .......................................................................... 47

3.3.3 Một số ví dụ............................................................................................ 51

Kết luận Chương 3 .............................................................................................. 53

vi

KẾT LUẬN ......................................................................................................... 54

DANH MỤC TÀI LIỆU THAM KHẢO............................................................ 55

PHỤ LỤC............................................................................................................ 57

Phụ lục Mã nguồn Chương trình......................................................................... 57

Phụ lục Thư viện tính toán số lớn ....................................................................... 71

1 Biểu diễn số lớn................................................................................................ 72

2 Các phép toán với số lớn.................................................................................. 73

vii

DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT

Ký hiệu,

viết tắt

Ý nghĩa

RSA Rivest - Shamir - Adlemal Hệ mật mã RSA

RCT Chinese Remainder Theorem Định lý đồng dư Trung Hoa

GCD Greatest Common Divisor Ước chung lớn nhất

GF(P)

Trường số thực

GF(2)

Trường nhị phân

K

Tập hợp khóa mã

E

Thuật toán mã hóa

D

Thuật toán giải mã

P

Tập hợp các bản rõ

C

Tập hợp các bản mã

n

Hàm Phi_Ơle

p, q

Cặp số nguyên tố

p

và

q

n

Số nguyên dương bất kỳ

x

Văn bản rõ thuộc

P

y

Bản mã thuộc

C

'

k

Thành phần khóa công khai

''

k

Thành phần khóa bí mật

s

Số nguyên tố Mersenne

r

Số nguyên lẻ

viii

DANH MỤC HÌNH VẼ, BẢNG BIỂU

Hình 3.1: Lưu đồ thuật toán................................................................................ 47

Hình 3.2: Giao diện chính của chương trình...................................................... 48

Hình 3.3: Kiểm tra tính chẵn của số cần phân tích ............................................ 49

Hình 3.4: Kiểm tra tính nguyên tố của số cần phân tích .................................... 49

Hình 3.5: Chức năng phân tích........................................................................... 50

Hình 3.6: Chức năng dừng trong quá trình phân tích ........................................ 50

Hình 3.7: Chức năng hiển thị kết quả................................................................. 51

1

MỞ ĐẦU

1. Đặt vấn đề

Hệ mật RSA được phát minh bởi Ron Rivest, Adi Shamir, và Len

Adleman, công bố lần đầu vào tháng 8 năm 1977 trên tạp chí khoa học Mỹ,

được sử dụng trong lĩnh vựcbảo mật và cung cấp cơ chế xác thực của dữ liệu

số [3],[17]. Ngày nay, RSA đã được phát triển và ứng dụng rộng rãi trong tất

cả các lĩnh vực đời sống, kinh tế xã hội, an ninh quốc phòng, đặc biệt là trong

thương mại điện tử. Theo [4],[6] RSA được sử dụng nhiều nhất để trao đổi khóa

bí mật và xác thực đối với hệ mật mã đối xứng; sử dụng trên web servers và

trên các browsers nhằm đảm bảo an ninh đường truyền, đặc biệt RSA được coi

là hạt nhân của hệ thống thanh toán điện tử... Bởi vậy, nghiên cứu phân tích hệ

mật RSA luôn thu hút sự quan tâm của nhiều quốc gia, tổ chức, các tập đoàn,

công ty và các nhà khoa học đầu tư nghiên cứu [7],[9].

Ở nước ta hiện nay, hầu hết các cơ quan, tổ chức hoạt động trong lĩnh

vực bảo mật và các trung tâm nghiên cứu, trường đại học khối kỹ thuật đều có

những kết quả nghiên cứu, phân tích hệ số an toàn đối với các tham số hệ mật,

từ đó chỉ rõ những mối nguy hiểm tiềm ẩn cần cải thiện hệ mật RSA khi sử

dụng [5],[10]. Vấn đề thám mã đối với hệ mật RSA hiện nay đang được các

nhà nghiên cứu tập trung khai thác dựa trên các sơ hở của RSA như: tấn công

vào số mũ công khai hoặc số mũ bí mật thấp, tấn công vào các tham số nguyên

tố

p,q

bé hoặc cách xa nhau lớn, hoặc họ tập trung vào việc phân tích nhân tử

số

n

(modul của RSA). Trường hợp đối với số lớn, từ

24

n 10

trở lên thì các

phương pháp hiện tại không phát huy được hiệu quả hoặc chạy chậm và không

cho quả như mong muốn [3]. Mặt khác về mặt toán học đã chứng minh hiệu

quả của việc tấn công hệ mật RSA phụ thuộc vào cách thu hẹp khoảng cách dò

tìm số nguyên tố

p

đối với hệ mật RSA. Do vậy cần có những nghiên cứu tấn

công RSA mới mà không cần phân tích nhân tử [4].