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, Ý nghĩa viết tắt

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

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

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

Trường số thực

Trường nhị phân

Tập hợp khóa mã

Thuật toán mã hóa

Thuật toán giải mã

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

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

Hàm Phi_Ơle

Cặp số nguyên tố và

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

Văn bản rõ thuộc

Bản mã thuộc

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

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

Số nguyên tố Mersenne

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ố 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ố (modul của RSA). Trường hợp đối với số lớn, từ 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ố đố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].

2

Xuất phát từ thực tế đó, luận văn “Nghiên cứu xây dựng thuật toán tấn

công hệ mật RSA” mang tính cấp thiết, thực sự có ý nghĩa khoa học và thực

tiễn.

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

- Nghiên cứu về các phương pháp tấn công hệ mật RSA hiện nay và đề

xuất một phương pháp tấn công RSA mới.

- Sử dụng ngôn ngữ lập trình C để xây dựng chương trình phần mềm

được đề xuất.

3. Hướng nghiên cứu của luận văn

Nghiên cứu tổng quan về vấn đề an toàn hệ mật RSA, các phương pháp

tấn công RSA phổ biến hiện nay. Từ đó đi sâu nghiên cứu đề xuất một phương

pháp tấn công RSA mới, không dựa trên bài toán phân tích nhân tử. Nghiên

cứu xây dựng phần mềm giải pháp và thực nghiệm, đánh giá.

4. Những nội dung nghiên cứu chính

Chương 1: Tổng quan về hệ mật RSA

Nghiên cứu mô tả, thực thi hệ mật RSA, vấn đề an toàn và các kiểu,

phương pháp tấn công hệ mật RSA phổ biến.

Chương 2: Nghiên cứu một số thuật toán tấn công RSA

Tập trung nghiên cứu, phân tích một số thuật toán tấn công RSA phổ

biến sử dụng chung phương pháp phân tích nhân tử. Nội dung chính của chương

trình bày kết quả nghiên cứu các thuật toán kiểm tra số nguyên tố và thuật toán

phân tích số nguyên thành tích các thừa số nguyên tố.

Chương 3: Nghiên cứu đề xuất thuật toán tấn công RSA

Dựa trên cơ sở lý thuyết toán học, nội dung Chương 3 nghiên cứu, tìm

hiểu và xây dựng chương trình thuật toán tấn công hệ mật RSA không cần phân

tích nhân tử. Việc tính toán, phân tích số nguyên để xác định các số nguyên

tố được thực hiện thông qua tính toán hàm . Đồng thời đã phân tích,

tính toán thực nghiệm để đưa ra một số kết luận.

3

5. Phương pháp nghiên cứu

- Nghiên cứu các bài báo khoa học, công trình nghiên cứu trong nước và

quốc tế.

- Nghiên cứu, phân tích các phương pháp tấn công RSA hiện nay. Từ đó

xây dựng thuật toán tấn công RSA mới.

- Xây dựng phần mềm ứng dụng và đánh giá.

6. Ý nghĩa khoa học của luận văn

Nghiên cứu vấn đề tấn công hệ mật RSA có ý nghĩa và vai trò to lớn

trong việc vệ an ninh thông tin. Đây là vấn đề đang được quan tâm, thu hút

nhiều quốc gia, tổ chức, cá nhân đầu tư nghiên cứu. Học viên đã nghiên cứu

tìm hiểu và xây dựng phần mềm giải pháp tấn công RSA, không cần phân tích

nhân tử. Do vậy, luận văn có tính khoa học và ứng dụng thực tiễn.

4

CHƯƠNG 1: TỔNG QUAN VỀ HỆ MẬT RSA

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

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

Adleman và được Scientific American công bố lần đầu tiên vào năm 1977 [17].

Hệ mật RSA được sử dụng để bảo mật và đảm bảo tính xác thực của dữ

liệu số. Hiện nay RSA được sử dụng trong hệ thống thương mại điện tử, các

dịch vụ Web Server và Web Browser. RSA còn được sử dụng để đảm bảo tính

xác thực vào bảo mật của Email, đảm bảo an toàn cho các phiên truy cập từ xa

và là bộ phận quan trọng của hệ thống thanh toán thẻ tín dụng. Như vậy ta có

thể thấy rằng RSA thường được sử dụng trong các ứng dụng cần đảm bảo sự

an toàn và bảo mật dữ liệu số cao.

1.1.1 Mô tả hệ mật RSA

Định nghĩa hệ mật RSA

Hệ mật RSA bao gồm bộ . Trong đó [1]:

là tập các bản rõ. 1.

là tập các bản ký tự mã. 2.

3. là tập các khóa , mỗi khóa gồm hai phần: là khóa công khai

dành cho việc lập mã, còn là khóa bí mật dành cho việc giải mã.

4. Với mỗi bản rõ , thuật toán lập mã cho ta ký tự mã tương ứng

5. Với mỗi ký tự mã thuật toán giải mã cho ta lại ký tự bản rõ :

Hệ mật RSA sử dụng các tính toán trong trong đó là tích của hai số

nguyên tố lớn phân biệt nhau và . Mô tả hình thức của hệ

mật như sau:

Cho trong đó là các số nguyên tố lớn phân biệt nhau sao cho

độ dài của hai số này là gần nhau nhất có thể được.

5

Đặt: và định nghĩa

- Mã hóa:

- Giải mã:

Trong đó ,

Các giá trị công khai còn các giá trị được giữ bí mật.

Ta sẽ kiểm xem các phép mã hóa và giải mã có phải là các phép toán

nghịch đảo của nhau hay không?

Vì nên ta có với một số nguyên bất kỳ .

Giả sử có khi đó ta sẽ xét hai trường hợp.

a.Trường hợp . Khi đó ta có:

b. Trường hợp hoặc

Giả sử , khi đó với và

Suy ra: . Do nên

. Bên cạnh đó ta lại có:

. Vậy

Ví dụ:

Giả sử Bob chọn và . Khi đó và

.

Vì nên có thể dùng một số nguyên b khóa công khai có giá

trị không chia hết cho . Anh ta kiểm tra điều kiện bằng thuật

toán Euclidean.

Giả sử Bob chọn , khi đó theo thuật toán Euclidean mở rộng ta

có:

6

Do vậy số mũ mật (khóa bí mật) để giải mã của Bob sẽ là . Bob

sẽ công bố và .

Giả sử Alice muốn gửi bản rõ đến Bob. Cô ta sẽ tính:

Rồi gửi bản mã trên kênh truyền. Khi Bob nhận được bản mã

, anh ta sẽ sử dụng khóa bí mật để tính:

1.1.2 Thực thi hệ mật RSA

Để thiết lập hệ thống, Bob sẽ tuân theo các bước sau:

1. Bob tạo ra hai số nguyên lớn và sao cho độ dài của hai số gần bằng nhau nhất có thể được.

2. Bob tính và

3. Bob chọn một số ngẫu nhiên sao cho:

bằng cách sử dụng thuật toán

4. Bob tính Euclidean.

5. Bob công bố n và b trong một danh bạ và dùng chúng làn Hình 1.1: Thực thi hệ mật RSA khóa công khai. 1.1.3 Vấn đề an toàn của hệ mật RSA

Hệ mật RSA chỉ được an toàn khi giữ bí mật khóa giải mã và thừa số

nguyên tố (hay giữ bí mật ).

Trường hợp biết được thì Marvin dễ dàng tính được

. Khi đó Marvin sẽ sử dụng thuật toán Euclidean mở rộng để tính .

Khi biết thì toàn bộ hệ thống sẽ bị phá vỡ ngay lập tức. Vì khi biết ,

toàn bộ khóa đều được biết và Marvin sẽ giải mã được và sẽ đọc được nội

dung của bản rõ, Ngoài ra Marvin có thể lập mã trên văn bản khác là cực kỳ

7

nguy hiểm. Nhất là những thông tin liên quan đến an ninh quốc gia, quân đội,

ngân hàng.

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

Tính an toàn của một hệ thống mật mã phụ thuộc vào độ khó của bài toán

thám mã khi sử dụng hệ mật đó. Người ta đã đề xuất một số cách hiểu cho khai

niệm an toàn của hệ thống mật mã, để trên cơ sở các ccách hiểu đó nghiên cứu

tính an toàn của nhiều hệ mật khác nhau, sau đây là một vài cách hiểu thông

dụng nhất:

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

Giả thiết người thám mã có được thông tin về bản mã. Theo quan niệm

lý thuyết thông tin, nếu những hiểu biết về bản mã không thu hẹp được độ bất

định về bản rõ đối với người thám mã, thì hệ mật mã là an toàn vô điều kiện,

hay theo thuật ngữ của C.Shannon, hệ mật là bí mật hoàn toàn. Như vậy, hệ là

an toàn vô điều kiện, nếu độ bất định về bản rõ sau khi người thám mã có được

cả thông tin (về bản mã) bằng độ bất định về bản rõ trước đó. Tính an toàn vô

điều kiện thường được sử dụng cho các hệ mật mã khó đối xứng.

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

Một hệ thống mật mã được xem là có độ an toàn được chứng minh nếu

ta có thể chứng minh được bài toán thám mã đối với hệ thống đó “khó tương

đương” với một bài toán khó đã biết, thí dụ bài toán phân tích một số nguyên

thành tích các thừa số nguyên tố, bài toán tìm lôgarit theo một modul nguyên

tố,…(“khó tương đương” có nghĩa là nếu bài toán này giải được thì bài toán kia

cũng giải được cùng một độ phức tạp như nhau).

1.2.3 An toàn tính toán

Hệ mật mã được xem là an toàn về mặt tính toán, nếu mọi phương pháp

thám mã đã biết đều đòi hỏi một nguồn năng lực tính toán vượt quá mọi khả

năng (kể cả phương tiện thiết bị máy móc) tính toán của một kẻ thám mã. An

8

toàn theo nghĩa này, nói theo ngôn ngữ của lý thuyết về độ phức tạp tính toán

là bao hàm cả khái niệm an toàn theo nghĩa “được chứng minh” nói trên.

Tính an toàn theo nghĩa được chứng minh hay tính toán được sử dụng

nhiều trong công việc nghiên cứu các hệ thống mật mã hiện đại, đặc biệt là các

hệ thống mật mã khóa công khai. Các bài toán đó đều có hạt nhân là tính an

toàn của các hệ mật mã, góp phần giải quyết các vấn đề an toàn thông tin kể

trên.

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

Mật mã được sử dụng trước hết là để đảm bảo tính bí mật cho các thông

tin được trao đổi trên các kênh truyền thông công cộng. Do đó bài toán quan

trọng nhất của thám mã cũng chính là bài toán phá bỏ tính bí mật đó, tức là: với

những bản mã có thể dễ dàng thu được trên các kênh truyền thông công cộng,

người thám mã phải tìm ra được nội dung thông tin che dấu bên trong bản mã

[8],[17],[18].

Giả thiết chung: Ta luôn coi đối phương biết hệ mã đang dùng. Giả thiết

này được gọi là nguyên lý KoreKhoff. Dĩ nhiên nếu đối phương không biết hệ

mật được dùng thì nhiệm vụ của anh ta sẽ khó khăn hơn nhiều. Tuy nhiên, ta

không muốn độ mật của một hệ thống dựa trên một giả thiết không chắc chắn:

đối phương không biết hệ mật đang sử dụng. Vì vậy, mục tiêu trong việc thiết

kế một hệ mật là phải đạt được độ mật của giả thiết KoreKhoff.

Việc thám mã có thể quy về việc tìm được bản rõ hoặc phát hiện khóa

giải mã, khi biết trước hệ mật mã sử dụng. Ngoài việc biết hệ mật mã, người

thám mã cần có thông tin về bản rõ và một số phát hiện khác. Tuỳ theo thông

tin đó là gì mà ta phân các bài toán thám mã thành 4 loại [2]:

- Bài toán thám mã chỉ biết bản mã: Đây là bài toán phổ biến nhất

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

- Bài toán thám mã khi có bản rõ được chọn.

- Bài toán thám mã khi có bản mã được chọn.

9

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

Đây là bài toán phổ biến nhất. Người thám mã chỉ biết các bản mã

mà không biết bản rõ tương ứng với những bản mã đó cũng

như khóa giải mã. Anh ta cố gắng tìm khóa giải mã, nếu không cần tìm các bản

rõ .

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

Người thám mã biết các bản mã

Như trên, nhưng cũng biết các bản rõ tương ứng . Anh ta cố gắng

tìm khóa giải mã , nếu không thì cố gắng phỏng đoán bản rõ từ bản mã

mới đã được mã hóa cùng với khóa .

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

Người thám mã được quyền truy nhập tạm thời cơ chế mã hóa, nên có

thể chọn các bản rõ và có được các bản mã tương ứng ,

,.., , từ đó anh ta sẽ phỏng đoán khóa giải mã và có thể

tìm được bản rõ từ một vài bản mã mới cũng được mã hóa bởi

khóa lập mã .

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

Người thám mã được quyền truy cập tạm thời vào cơ chế giải mã, nên từ

các bản mã anh ta nhận được các bản rõ tương ứng . Từ đó anh

ta phỏng đoán khóa giải mã và có thể tìm được bản rõ từ một vài bản mã

mới cũng được mã hóa bởi cùng khóa lập mã .

Trong mỗi trường hợp đối tượng cần phải xác định chính là khóa đã sử

dụng: Rõ ràng bốn mức tấn công (thám mã) trên đã được liệt kê theo độ tăng

dần của sức mạnh tấn công và cách tấn công các bản mã được lựa chọn là thích

hợp đối với hệ mật mã hóa công khai.

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

10

Tính bảo mật của RSA chủ yếu dựa vào việc giữ bí mật số mũ giải mã

và các thừa số của . Tuy nhiên, điều kiện an toàn trên của hệ mật chỉ là

điều kiện chung. Trong thực tế khi thiết kế một giao thức hay một kênh bí mật

có sử dụng hệ mật RSA vẫn tồn tại nhiều sơ hở, những sơ hở đó đã được thám

mã lợi dụng nhằm phá huỷ giao thức, kênh bí mật, phá vỡ tính an toàn của hệ

mật. Trong phần này, sẽ giới thiệu một số sơ hở người thám mã có thể lợi dụng

vào đó để phá vỡ hệ mật RSA [5, 8, 13].

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

Người ta có thể xác định được và ngược lại. Biết được người ta

có thể dễ dàng tính được .

Nếu biết được ta có thể tìm được bằng cách giải hệ phương trình:

Do đó là nghiệm của phương trình bậc 2:

Bởi vậy nếu người thám mã biết được anh ta có thể phân tích được

và phá được hệ mật.

Ngược lại cho trước rõ ràng việc tính được thực hiện dễ dàng:

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

Nếu như biết số mũ giải mã a thì coi như đã làm xong việc thám mã, vì

vậy việc tìm kiếm là không còn ý nghĩa đối với Marvin (người thám mã)

nữa. Tuy nhiên điều này còn có một ý nghĩa quan trọng hơn đó là nếu đối

phương biết thì ta không chỉ phải thay đổi số mũ giải mã mà còn phải chọn

modul khác. Vì khi Marvin biết được d, anh ta cũng có thể tính được . Do

đó Marvin sẽ biết cách tìm một khóa bí mật bất kỳ, néu hệ thống vẫn giữ nguyên

modul .

11

Bây giờ chúng ta sẽ chứng minh rằng: nếu biết số mũ giải sẽ tìm được

các thừa số của .

Thật vậy:

Do nên

Do là một số chẵn nên ta có thể viết dưới dạng.

với là số lẻ và .

Theo định lý ơle: với a thì . Do đó ta có:

(do là bội của và do đó là căn bậc hai của 1

theo module .

Theo định lý phần dư Trung Hoa, 1 có 4 căn bậc hai module . Hai

căn bậc 2 là , hai căn bậc hai là . Sử dụng

một trong hai căn bậc hai không tầm thường này sẽ tìm được trong thời

gian đa thức bằng cách tính

(1)

Đặt và

nên: Vì và

và

và

Suy ra hoặc phải khác và do nên một trong hai giá trị

chính là hoặc .

Ví dụ: Giả sử . Bốn căn bậc hai của 1 theo modul là:

. Căn bậc hai 92 nhận được bằng cách giải hệ

theo định lý phần dư China. Nếu tìm được nghiệm

không tầm thường này, thì nghiệm không tầm thường kia phải là 403-92=311.

Đó là nghiệm của hệ và .

12

Giả sử là căn bậc hai không tầm thường của 1 module . Khi đó ta có:

Nhưng không là ước của một nhân tử nào ở vế phải. Điều đó kéo theo

hoặc (và tương tự hoặc ). Tất nhiên có thể tính

ước chung lớn nhất bằng thuật toán Euclidean mà không cần phải phân tích nhâ

tử n. Bởi vậy hiểu biết về căn bậc hai không tầm thường 1 module n sẽ làm cho

việc phân tích n chỉ cần thực hiện trong thời gian đa thức. Yếu tố quan trọng

này là cơ sở của nhiều kết quả trong mật mã.

Trong ví dụ trên, và

Sau đây là thuật toán phân tích thừa số khi đã biết số mũ giải mã .

1. Cho ngẫu nhiên sao cho

2. Tính

3. If then quit (thanh công: hoặc )

4. Tính

, với là số lẻ 5. Viết

6. Tính

then quit (không thành công) 7. If

8. While do

9.

10.

11. If then quit (không thành công)

Else

Tính

(thành công: hoặc )

Thuật toán có xác suất thành công tối thiểu là .

1.4.3 Giao thức công chứng

13

Giao thức công chứng là giao thức được thiết kế cho một văn bản sau khi

A ký lên đó, người khác có thể xác thực được rằng văn bản này thực sự được

ký bởi A (nó cùng giống như như việc công chứng của công chứng viên ký chữ

ký của mình lên bản công chứng).

Để thiết lập giao thức công chứng, Bob phải chọn các tham số RSA: các

số nguyên tố và các số mũ hóa và khóa giải mã thỏa mãn

trong đó . Các giá trị là công khai, còn được Bob giữ bí mất.

Để ký một văn bản M, Bob sử dụng số mũ bí mật d để tính chữ ký

. Bất cứ ai cũng có thể sử dụng những thông tin công khai của Bob

để kiểm tra xem S có thật sựu là chữ ký của Bob trên hay không bằng cách

tính và so sánh với . Vì chỉ có Bob biết giá trị , giá trị dùng để tạo

ra . Giao thức công chứng khẳng định rằng chỉ có một mình Bob mới có thể

tạo ra .

Tuy nhiên Davida và Denning [6] đã chỉ ra rằng: Có thể tạo ra chữ ký

giả mạo của giao thức này. Sau đây là một phương pháp để thực hiện điều đó.

Bob có khóa bí mật d và khóa công khai e. Giả sử marvin muốn có được

chữ ký của Bob trên văn bản . Khi đó Marvin có thể thực hiện theo cách

sau đây:

Lấy một số ngẫu nhiên , tính , và đề nghị Bob ký

trên . Nếu Bob ký trên thì Marvin có thể dễ dàng tính được chữ ký

của Bob trên :

Vì

tìm được chính là chữ ký của Bob trên .

Thật vậy:

14

Kỹ thuật trên được gọi là kỹ thuật che khuất (blinding), kỹ thuật này cho

phép Marvin lấy được một chữ ký hợp pháp trên một văn bản anh ta muốn,

bằng cách yêu cầu Bob ký trên một văn bản "được che khuất" (blinding) ngẫu

nhiên. Bob không có thông tin về văn bản anh ta đang thực sự ký.

Kết quả của kỹ thuật này dựa trên một thực tế: RSA sử dụng một hàm

toán học (hàm mũ) bảo toàn phép nhân các giá trị đầu vào. Điểm mấu chốt của

cách tấn công này là nếu chọn và bất kỳ:

tức

Vậy để ngăn cản việc tấn công vào giao thức công chứng bằng kỹ thuật

che khuất ta phải huỷ bỏ khả năng sử dụng tính bảo toàn của phép nhân của kẻ

định giả mạo chữ ký. Một trong nhiều cách đó là sử dụng hàm “hash một chiều”

trên văn bản trước khi ký và kỹ thuật này được áp dụng trong nhiều ứng

dụng thực tế của RSA (ví dụ như thanh toán điện tử ẩn danh).

1.4.4 Giao thức module n chung

Tình huống dẫn đến việc sử dụng RSA có số module chung xảy ra như

sau: khi trong hệ thống có k người đăng ký sử dụng RSA. Để quản lý, phân

phối khóa được đơn giản, trung tâm sẽ tạo ta hai số nguyên tố và tính số

modul ; sinh ra các cặp khóa mã hóa và giải mã , sau đó cấp cho

người đăng ký thứ trong hệ thống, bí mật tương ứng, cùng các thông tin công

khai bao gồm số và một danh sách đầy đủ các khóa công khai ;

các cặp khóa mã hóa nguyên tố cùng nhau từng đôi một.

Bất kỳ người nào có thông tin công khai này dều có thể mã hóa văn bản

M và gửi cho người đăng ký thứ bằng cách sử dụng thuật toán mã hóa RSA

với khóa mã : , sau đó gửi cho người thứ hoặc người đăng

ký thứ có thể ký một văn bản bằng cách tính chữ ký . Bất kỳ

15

ai cũng có thể xác thực rằng được ký bởi người đăng ký thứ bằng cách

tính và so sánh với .

Tuy nhiên việc sử dụng modul chung dẫn đến một số điểm yếu của giao

thức dẫn đến các hình thức tấn công:

Kiểu tấn công thứ nhất

Như Simmón [6] chỉ ra, nếu một văn bản được gửi tới một người đăng

ký có các số mũ mã hóa nguyên tố cùng nhau thì đối phương có thể giải mã

được văn bản mà không cần biết khóa giải mã. Để chứng minh điều này ta hãy

xem kết quả văn bản gửi cho 2 người có khóa công khai tương ứng là và

:

Thuật toán sau đây chỉ ra rằng Marvin có thể lấy được bản rõ chỉ với

những giá trị anh ta biết như: , khóa lập mã và của người thứ và

người thứ .

Input:

Output: Văn bản

Algorithm:

Step 1: Tính

Step 2: Tính

Step 3: Tính

Rõ ràng

Thật vậy:

16

Như vậy ta đã có được điều cần chứng minh

Chúng ta sẽ xét một ví dụ để hiểu rõ hơn về thuật toán này

Ví dụ: , ,

,

Ta có

Vậy

Việc sử dụng chung cũng làm cho giao thức này dễ bị tấn công

theo những cách khác nữa mà trong đó một người đăng ký trong hệ thống có

thể bẻ gãy được hệ mật. Hệ mật bị sập, và điều tất nhiên kênh bí mật sẽ bị lộ vì

người đăng ký này có thể giải mã các văn bản của những người khác. Kênh chữ

ký cũng hỏng vì anh ta có thể giả mạo chữ ký của người dùng mà không bị phát

hiện. Đó là cách sử dụng phương pháp xác suất để phân tích ra thừa số modul

, hoặc sử dụng thuật toán tất định để tính số mũ giải mà không cần số

module.

Kiểu tấn công thứ hai

Ý tưởng cơ bản của kiểu tấn công thứ hai là phân tích số modul bằng

cách tìm căn bậc hai không tầm thường của . Nghĩa là tìm một số thỏa

mãn:

Với

Nếu tìm được số như thế thì số modul có thể phân tích được theo

cách sau đây:

Vì nên

17

Suy ra: với là số nguyên tuỳ ý.

Hay nói cách khác chia hết cho cả và .

Tuy nhiên, do nên (4)

Bất đẳng thức (4) cho ta thấy rằng nếu thì không chia hết

cho . Tương tự với , suy ra phải là hoặc .

Áp dụng thuật toán Euclidean ta sẽ phân tích được thừa số của . Vì vậy,

cách tấn công vào hệ thống này tập trung vào cách để tìm căn bậc hai không

tầm thường của .

Đặt và là số mũ của khóa mã hóa và giải mã của người dùng hệ

thống, thỏa mãn điều kiện . Do đó , với là

số lẻ.

Thủ tục sau đây sẽ giúp chúng ta tìm căn bậc hai không tầm thường của

:

1. Chọn số nguyên sao cho và

2. Tìm số nguyên dương nhỏ nhất thỏa mãn: (vì theo định lý ơle nếu

thì và là bội của nên chắc chắn tồn tại số

này.

3. Đặt:

4. Nếu , thì nó là căn bậc hai không tầm thường của .

5. Nếu thì quay lại bước 1.

Delaurentí [6] đã chứng minh rằng với a ngẫu nhiên,

Xác suất xảy ra:

Hay:

18

Do đó nếu ta xác định một thuật toán xác suất và thử lần lượt với m giá

trị ngẫu nhiên a theo tính chất:

Thuật toán này sẽ dừng nếu tính chất đó được nghiệm đúng ở một lúc

nào đó và cho ta kết quả . Trong trường hợp ngược lại thuật toán

sẽ dừng và không có kết quả.

Như vậy, một người trong cuộc có thể bẻ hệ mật trong giao thức này với

xác suất cao cùng với những thông tin mà anh ta có. Cách tấn công này là rất

quan trọng vì nó chỉ ra rằng những thông tin về cặp số mũ mã hóa và giải mã

có thể cho phép tìm ra thừa số của số modul n.

Kiểu tấn công thứ ba:

Một thành viên có thể sử dụng khóa công khai và khóa bí mật của anh ta

để sinh khóa bí mật của người dùng khác. Nghĩa là căn cứ vào số mũ hoá công

khai , người giữ cặp số mũ hóa/giải mã có thể tìm được số nguyên

mà không cần biết .

Để tìm được số này, cần phải tìm một số nguyên nguyên tố cùng

nhau với và là bội của . Điều này thực hiện được bởi . Khi đó,

do và nguyên tố cùng nhau nên tồn tại hai số và sao cho

(theo thuật toán Euclidean mở rộng). Vì là bội của nên và

khi đó .

Thủ tục tìm một số như sau(trong đó chỉ cần đến các giá trị và

)

1. Đặt

2. Sử dụng thuật toán Euclidean mở rộng để tính . Đồng thời

cũng tìm được 2 số và thỏa mãn

3. Nếu thì đặt và kết thúc.

19

4. Nếu thì đặt rồi quay lại bước 2.

Ta có thể chứng minh thuật toán trên như sau:

Theo thuật toán Euclidean mở rộng, tồn tại hai số và sao cho

, chính là ước chung lớn nhất của và .

, khi đó ta sẽ có: Nếu

Suy ra . Điều này có nghĩa chia hết cho hay

. Vậy chính là phần tử nghịch đảo của , hay chính là .

Thủ tục trên đưa ra được số mũ giải của . Độ phức tạp của hệ thống

này là . Đây chính là một mối đe doạ đối với hệ thống.

Một lần nữa ta khẳng định rằng, với những thông tin có sẵn cho mỗi

người dùng hợp pháp trong hệ thống, họ có thể bẻ được hệ thống mật mã, khi

đó hệ mật sẽ bị sập. Tất nhiên, người dùng này không thể thực hiện nguyên xi

theo yêu cầu của nhà thiết kế giao thức dành cho người dùng, nhưng với những

thông tin cần thiết vẫn có thể lấy được mà họ không hề vi phạm quy định của

giao thức.

Qua 3 kiểu tấn công trên cho thấy giao thức modul chung sẽ gặp thất bại

trong việc đảm bảo bảo mật các văn bản hoặc cung cấp sự xác thực cho chữ ký

của người dùng trong hệ thống. Vì vậy, trong việc thiết kế giao thức với hệ mật

RSA cần tránh việc sử dụng modul chung. Cụ thể, người thiết kế giao thức phải

xem xét xem đối thủ sẽ có thể làm được gì với những bản mã mà những bản rõ

của chúng có liên quan(giống nhau), hoặc khóa của họ có liên quan với nhau(ở

đây ta xét là nguyên tố cùng nhau).

Vì vậy để chống lại sự tấn công trong giao thức module chung, khi sử

dụng RSA để xây dựng hệ thống mật cần đảm bảo:

- Thông tin của một số cặp mã hóa, giải mã với số modul đã cho có khả

năng đối phó với thuật toán xác suất phân tích số module.

20

- Thông tin của một số mũ hóa/giải mã với modul đã cho có khả năng

đối phó với thuật toán tất định để tính các cặp mã hóa/giải mã khác nhau mà

không cần xác định trước .

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

Nhằm giảm tải thời gian mã hóa hoặc kiểm tra chữ ký người ta đưa ra

một biện pháp đó là sử dụng số mũ mã hóa nhỏ. Cách này thường được sử dụng

trên mạng có yêu cầu truyền dữ liệu thông tin lớn.

Trong giao thức này mỗi người dùng chọn và công bố khóa công

khai của mình. ở đây chúng ta quan tâm đến trường hợp số mũ mã hóa

là giống nhau và là một số nguyên nhỏ. Với một vài ứng dụng thì điều này rất

hấp dẫn vì ứng dụng với số mũ nhỏ có thể thực hiện đơn giản và nhanh hơn.

Tuy nhiên tính chất này sẽ làm cho giao thức thất bại nếu một người mã hóa

cùng một văn bản bằng số mũ và gửi cho nhiều người.

Ví dụ người dùng thứ nhất với khóa mã và văn bản được mã

hóa để gửi cho 3 người khác nhau. Khi đó ta sẽ có các bản mã tương ứng là:

Nếu là nguyên tố cùng nhau, thì áp dụng định lý phần dư Trung

Hoa sẽ tính được duy nhất thỏa mãn hệ phương trình trên. Tính

Ngược lại, không nguyên tố cùng nhau, thì sẽ là hoặc

chung của hai người. Khi đó người này hoàn toàn có thể phá vỡ được hệ mật

của người kia.

Để khắc phục nhược điểm này, văn bản cần được gán thêm một thông

tin ngẫu nhiên trước khi mã hóa để gửo cho mỗi người (ví dụ gắn thêm tem thời

gian). Trong ví dụ của chúng ta ở trên, các bản mã mới trong giao thức sẽ là:

21

Tuy nhiên, Hastad [14] đã chứng minh cách này có thể không cho đủ các

bản rõ khác nhau, để khắc phục nhược điểm vốn có của giao thức số mũ nhỏ.

Trong tài liệu của ông, đã chỉ ra rằng một hệ phương trình đồng dư:

Có bậc không lớn hơn có thể giải được trong thời gian đa thức nếu số

phương trình lớn hơn . Vì trong trường hợp này số mũ là 3, nếu văn

bản được điều chỉnh bằng tem thời gian được gửi ít nhất cho 7 thành viên trong

mạng, văn bản sẽ không còn là bí mật đối với người tấn công sau một khoảng

thời gian dài. Tuy nhiên, tem thời gian chỉ gồm một số bít nhỏ so với kích thước

của văn bản vì vậy nó có thể được ước lượng trước khi áp dụng thuật toán của

Hastad. Rõ ràng tính bảo mật của hệ thống không thể tuỳ thuộc vào tính bí mật

của tem thời gian.

Thất bại của giao thức được đề cập đến trong phần này đã nhấn mạnh

một điều, đó là người thiết kế giao thức phải quan tâm đến việc tăng thêm các

thông tin cho các bản mã mà bản rõ của nó có quan hệ (trong ví dụ là bằng nhau

hoặc sai khác tem thời gian) hoặc khóa của chúng có liên quan với nhau(như

cùng số mũ với module nguyên tố cùng nhau).

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

Để rút ngắn thời gian giải mã(hoặc thời gian sinh chữ ký), người ta muốn

sử dụng một giá trị nhỏ hơn là giá trị ngẫu nhiên. Vì việc mã hóa theo modul

mất một khoảng thời gian tuyến tính là , nên số mũ nhỏ có thể nâng

hiệu quả thực thi nhanh hơn ít nhất 10 lần(đối với module 1024 bít). Tuy nhiên

22

theo tác giả M. Wiener[10] nếu giá trị số mũ giải nhỏ sẽ dẫn đến sập toàn bộ

hệ thống mật mã.

Để chứng minh điều này chúng ta xét định lý sau:

Định lý M. Wiener: Cho . Giả sử . Biết

(n,e) với nên tồn tại một số nguyên . Do đó, nếu

chia hai vế cho ta sẽ có:

Do đó:

Mặc dù Marvin không biết , nhưng có thể sử dụng để xấp xỉ nó.

Thật vậy, do nên . Mặt khác:  nên:

. . Ta có: nên

Thay vào :

và nên:

Như vậy, số các phân số với xấp xỉ bằng

Thực tế, tất cả các phân số này có được là do sự hội tụ của khai triển

phân số liên tục của . Tất cả mọi việc phải làm là tính logn hội tụ của phân

số liên tục . Một trong những phân số đó sẽ bằng . Vì thế ,

chúng ta có và do đó là phân số tối giản. Đây là thuật toán tuyến

tính để khôi phục khóa bí mật .

Vì phổ biến là 1024 bít nên độ dài của ít nhất là 256 bít nhằm tránh

việc bị tấn công theo kiểu này. Nhưng thật không may, đối với những thiết bị

23

có dung lượng bộ nhớ nhỏ như Smartcard thì sẽ nhỏ hơn nhiều. Chính vì vậy

kiểu tấn công này vẫn có thể xảy ra.

Để khắc phục điều này, Wiener[10] đã đưa ra một số kỹ thuật cho phép

giải mã nhanh nhưng vẫn tránh được sự tấn công ở trên. Đó là:

+ Số lớn

Giả sử thay vì giảm , một người sử dụng làm khóa công

khai, trong đó với lớn. Rõ ràng có thể được sử dụng vào vị trí

của đối với văn bản mã hóa. Tuy nhiên, khi một giá trị của lớn được dùng

thì giá trị trong chứng minh ở trên không nhỏ nữa. Một phép tính đơn giản

chỉ ra rằng nếu thì sẽ không có vấn đề: “liệu với nhỏ nhất là bao

nhiêu?” thì cách tấn công ở trên không thể thực hiện được. Tuy nhiên giá trị

lớn sẽ dẫn đến tăng thời gian mã hóa.

+ Sử dụng CRT(Chinese Remainder Theorem): Sử dụng định lý phần dư

Trung Hoa [11, 13].

Giả sử chọn sao cho cả và nhỏ (khoảng

128 bít). Việc giải mã nhanh bản mã thực hiện như sau: tính

và . Sau đó sử dụng định lý phần dư Trung Hoa để tính giá trị

thỏa mãn yêu cầu. Vấn đề là mặc dù và nhỏ, giá trị có

thể lớn. Như vậy, cách tấn công theo định lý trên không thực hiện được.

Chú ý rằng với đã biết, sẽ tồn tại cách tấn công cho phép phân tích

ra thừa số nguyên tố trong thời gian . Vì vậy và không

thể chọn số quá nhỏ.

Chúng ta không biết chắc phương pháp nào kể trên là an toàn. Nhưng

điều mà chúng ta biết là cách tấn công của Wiener là không hiệu quả đối với

chúng. Một định lý do Boneh và Durfee[4] cải tiến chỉ ra rằng thì có

thể khôi phục từ . Kết quả này chỉ ra rằng giới hạn của Wiener là chưa

24

chặt chẽ khi cho rằng giới hạn là . Đây vẫn còn là một vấn đề mở cho

đến thời điểm hiện nay.

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

Trong khi xây dựng hệ mật RSA, nếu ta bất cẩn trong việc chọn các tham

số và để hoặc có ước nguyên tố nhỏ thì hệ mật mã trở nên mất

an toàn. Khi hoặc có ước nguyên tố nhỏ thì ta có thể dùng thuật toán

Pollar đưa ra vào năm 1974 phân tích một cách hiệu quả.

Thuật toán được mô tả như sau:

Input: và một cận

Output: Trả lời:

- Thành công và đưa ra thừa số của

- Không thành công

Algirithm:

1.

2. For to do

3.

4. If then

Printf (“Thành công và các thừa số của là:”, ;

Else

Printf (“Không thành công”);

Giả sử là một ước nguyên tố của và có phân tích ra các số mũ

nguyên tố sau:

Đặt: , với

Nếu , khi đó

25

Ở cuối bước 2 ta có: nên ta cũng có vì .

Theo định lý Fermat ta có:

Vì nên . Tại bước 4 ta có và , do đó

. Số nguyên tố sẽ là ước không tầm thường của trừ khi

ở bước 3.

Ví dụ:

Giả sử . Nếu áp dụng với , thì sẽ thấy rằng

ở bước 3, còn và

Trên thực tế . Trong trường hợp này, phép

phân tích sẽ thành công do

Nếu lấy thì chắc chắn rằng

Trong thuật toán có luỹ thừa theo module, mỗi luỹ thừa cần nhiều

nhất là phép nhân module dùng cho thuật toán bình phương và nhân.

Việc tính ước chung lớn nhất có thể thực hiện trong thời gian bằng

thuật toán Euclidean. Bởi vậy độ phức tạp của bài toán sẽ là:

. Nếu B là , với số nguyên xác định nào đó thì

thuật toán thật sự là thuật toán thời gian đa thức. Tuy nhiên chọn như vậy, xác

suất thành công sẽ rất nhỏ. Mặt khác nếu tăng kích thước của lên thật lớn,

chẳng hạn tới thì thuật toán sẽ thành công nhưng khi đó nó sẽ không thực

hiện nhanh hơn phép chia thử. Như vậy, điểm bất lợi của thuật toán này là yêu

cầu phải có ước nguyên tố sao cho chỉ có các thừa số nguyên tố bé.

Giải pháp khắc phục:

Ta có thể dễ dàng xây dựng hệ mật RSA với module hạn chế được

việc phân tích theo phương pháp này.Trước tiên tìm một số nguyên tố sao

cho cũng là một số nguyên tố và một số nguyên tố sao cho

26

cũng là một số nguyên tố(chúng ta có thể kiểm tra điều này bằng các

thuật toán kiểm tra tính nguyên tố). Khi đó module RSA sẽ chống được

cách phân tích theo phương pháp .

Kết luận Chương 1

Hệ mật công khai RSA đã và đang được sử dụng, ứng dụng rộng rãi, giải

quyết bài toán bảo mật và xác thực, đảm bảo an ninh an toàn thông tin trong tất

cả các lĩnh vực của đời sống xã hội. Tuy nhiên trong quá trình nghiên cứu, sử

dụng cho thấy, hệ mật mã RSA cũng tồn tại những điểm yếu, là lỗ hổng cho

phép thám mã lợi dụng để phân tích, tấn công.

Nội dung chính của Chương 1 đã trình bày tổng quan 4 phương pháp

thám mã chung nhất đối với các hệ mật mã nói chung và RSA nói riêng. Trên

cơ sở đó, đã nghiên cứu, phân tích 7 hình thức tấn công dựa vào những điểm

yếu trong quá trình lựa chọn tham số hệ mật và quá trình sử dụng. Đồng thời

27

đưa ra biện pháp, cách thức và khuyến cáo đối với cả người lập mã và người sử

dụng để hạn chế, chống lại những tấn công đó.

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

MẬT RSA

Bài toán phân tích một số nguyên thành tích của các thừa số nguyên

tố là một bài toán khó. Biết một số là một hợp số thì việc phân tích thành

thừa số mới có ý nghĩa, do đó trước khi giải quyết bài toán phân tích thừa số ta

sẽ phải kiểm tra xem có phải là hợp số không. Nội dung chương 2 sẽ trình

bày tổng quan kết quả nghiên cứuthuật toán kiểm tra số nguyên tố và phân tích

số nguyên thành tích các thừa số nguyên tố.

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

2.1.1 Đặt bài toán

28

Cho một số nguyên dương bất kỳ, kiểm tra xem có phải là số nguyên

tố không? Bài toán này được đặt ra từ những buổi đầu của số học và trải qua

hơn 200 năm đến nay vẫn là một bài toán chưa có được lời giải tối ưu nhất.

Bằng những phương pháp đơn giản như phương pháp sàng Euratosthene, từ rất

sớm người ta đã xây dựng được các bảng số nguyên tố đầu tiên, rồi tiếp tục

bằng nhiều phương pháp khác tìm được những số nguyên tố lớn. Tuy nhiên

hiện nay nhu cầu sử dụng các số nguyên tố và kiểm tra tính nguyên tố của các

số mới trở thành nhu cầu lớn và phổ biến, đòi hỏi nhiều phương pháp mới hiệu

quả hơn. Trong phần này học viên giới thiệu một số thuật toán kiểm tra tính

nguyên tố của một số nguyên .

Định nghĩa 1: Một số nguyên dương được gọi là số nguyên tố nếu nó

chỉ có ước là 1 và chính nó.

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

Theo định nghĩa trên ta thấy rằng để kiểm tra xem một số nguyên dương

bất kỳ có phải là số nguyên tố không, có một cách đơn giản đó là ta thực hiện

phép chia thử một số cho các số nằm trong khoảng từ đến . Nhưng điều

đó là khó khả thi nếu là một số lớn. Hiện nay các phương pháp kiểm tra gần

đúng số nguyên tố hầu như xuất phát từ giả thiết: Giả sử là một số tự nhiên,

từ các tính chất của số nguyên tố . Để là số nguyên tố thì phải thỏa

mãn điều kiện của số nguyên và phải có các tính chất . Nếu là một số

nguyên gần đúng cũng thỏa mãn các điều kiện trên thì ta có thể coi như là

một số nguyên tố. Các giải pháp cho các phương pháp kiểm tra tính gần đúng

này thường có những tính chất sau:

1. Với ta có thể kiểm tra hay không bằng một thuật toán có

độ phức tạp cỡ đa thức.

2. Nếu là số nguyên tố thì (rỗng)

3. Ngược lại nếu là hợp số thì .

29

2.1.2.1 Thuật toán Fermat

Định lý Fermat khẳng định rằng: nếu n là một số nguyên tố và là một

số nguyên bất kỳ, sao cho thì . Vì vậy, với một số

nguyên bất kỳ ta cần để trả lời xem có phải là số nguyên tố hay không, ta

phải tìm một số bất kỳ trong khoảng thỏa mãn điều kiện trên. Điều

này cũng tương đương: nếu ta không tìm được một số nguyên nào thỏa mãn

thì là hợp số.

Định nghĩa 2: Cho là một số nguyên lẻ và là một số nguyên thỏa

mãn . Ta nói là số nguyên tố với cơ sở (base) nếu

.

Thuật toán Fermat kiểm tra tính nguyên tố của một số nguyên lẻ :

Input: Số nguyên lẻ và là số lần kiểm tra

Output: Trả lời “ là số nguyên tố” hay “ là hợp số”

Algorithm:

1. For to

1.1. Chọn một số nguyên ngẫu nhiên

1.2. Tính

1.3. If return “ là hợp số”

2. Return “ là số nguyên tố”.

2.1.2.2 Thuật toán Solovay-Strassen

Solovay-Strassen là thuật toán kiểm tra tính nguyên tố theo xác suất. đây

là thuật toán được sử dụng phổ biến đầu tiên trong hệ mã hóa công khai, đặc

biệt là trong hệ mật RSA.

Nếu là số nguyên tố thì trong ký hiệu Jacobi và Legendre là tương

đương. Thuật toán Solovay-Strassen dựa trên định lý:

30

Định lý 1 (Tiêu chuẩn Euler): Nếu là số nguyên tố thì

với thỏa mãn .

Thuật toán Solovay-Strassen:

Input: Một số nguyên lẻ và số nguyên (là số vòng lặp)

Output: Trả lời “ là số nguyên tố” hay “ là hợp số”

Algorithm:

1. For to

1.1. Chọn số nguyên ngẫu nhiên (thỏa mãn )

1.2. Tính

1.3. If và then “ là hợp số”

1.4. Tính Jacobi symbol

1.5. If then “ là hợp số”

2. Return “ là số nguyên tố”.

Xác suất sai lầm là

2.1.2.3 Thuật toán Miller-Rabin

Thuật toán Miller-Rabin là thuật toán kiểm tra tính nguyên tố theo xác

suất mạnh nhất hiện nay. Thuật toán Miller-Rabin được dựa trên định lý sau:

Định lý Miller: Cho là số nguyên tố lẻ và ; là số lẻ. Với

một số bất kỳ thỏa mãn điều kiện thì:

hoặc với

Nếu số nguyên thỏa mãn điều kiện này thì được gọi là số nguyên tố

mạnh trên cơ sở(base) , tức là khi đó sẽ thỏa mãn mọi tính chất của số

nguyên tố trên cơ sở .

Thuật toán Miller-Rabin:

Input: Số nguyên lẻ và số nguyên (là số vòng lặp)

31

Output: Trả lời: “ là số nguyên tố” hay “ là hợp số”

Algorithm:

1. Phân tích với là số nguyên lẻ.

2. For to

2.1. Chọn ngẫu nhiên số nguyên thỏa mãn

2.2. Tính

2.3. If then

2.3.1. While và do

2.3.1.1. Tính

2.3.1.2. If then return (“ là hợp số”)

2.3.1.3. ;

2.3.2. If then return (“ là hợp số”)

3. Return “ là số nguyên tố”;

Xác suất sai lầm của thuật toán này và độ phức tạp tính toán là

.

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

So sánh giữa hai thuật toán Fermat và Miller-Rabin ta thấy rằng: nếu với

số nguyên tố cần tìm lớn thì giải thuật Miller-Rabin tốt hơn Fermat nhưng

Miller chạy chậm hơn. Đối với những chữ ký điện tử áp dụng không nhiều các

định lý và tính chất của số nguyên tố thì thuật toán Fermat là lựa chọn tối ưu.

Mọi cơ sở a của n trong Fermat cũng là cơ sở của n trong Miller-Rabin. Do đó

thuật toán Miller-Rabin có độ an toàn cao hơn. Đối với những ứng dụng chữ

ký điện tử hiện nay, hầu như sử dụng thuật toán Miller-Rabin.

So sánh giữa hai thuật toán Solovay-Strassen và Miller_Rabin ta thấy

rằng: Thuật toán Solovay-Strassen và Miller_Rabin gần tương tự như nhau

32

nhưng thuật toán Miller-Rabin thực hiện tốt hơn. Xác suất sai của Miller-Rabin

là trong khi đó xác suất sai của Solovay-Strassen là .

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

Định nghĩa số Mersenne: Cho số nguyên .

Số Mersenne là một số nguyên có dạng .Nếu là số nguyên tố

thì ta có số nguyên tố Mersenne.

Định lý 2: Cho số nguyên . Một số Mersenne là số nguyên

tố khi và chỉ khi nó thỏa mãn hai điều kiện sau:

(i) là số nguyên tố.

(ii) Và chuỗi các số nguyên được định nghĩa:

; với , thỏa mãn

Thuật toán kiểm tra tính nguyên tố của số Mersenne(Lucas-Lehmer)

Input: Một số Mersenne , với

Output: Trả lời “ là số nguyên tố” hay “ là hợp số”

Algorithm:

1. Trong khoảng từ 2 đến

1.1. Nếu s có nhân tử (ta sẽ dùng phép chia để kiểm tra (use

trial division)).

1.2. Return “ là hợp số”

2.

3. For to

Tính

4. Nếu thì “ là số nguyên tố”

Else “ là hợp số”.

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

Thuật toán 1

33

Input: Số nguyên lẻ cần kiểm tra

Output: Trả lời

- “ là số nguyên tố”

- “ là hợp số”

Algorithm:

1. Step 1: Cho ;

2. Step 2: ;

3. Step 3:

3.1. If then là hợp số

3.2. Else then test:

3.2.1. If dừng, Trả lời “ là số nguyên tố”

3.2.2. If then

, go to step 2

Thuật toán 2 (Thuật toán Packington)

Input: với là số nguyên tố

Output: Trả lời

- “ là số nguyên tố”

- “ là hợp số”

Algorithm:

1. Lấy ngẫu nhiên số

2. Tính

3. If then “ là hợp số”

4. Tính

5. If then “ là hợp số”

6. Tính

7. If then “ là số nguyên tố”

34

8. If then “ là hợp số”

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

Trong toàn bộ các thuật toán được nêu ra ở dưới đây, chúng ta sẽ coi rằng

số nguyên cần phân tích ra thừa số là số lẻ. Bài toán phân tích thành thừa

số có thể dẫn việc tìm một ước của , vì khi biết một ước của thì tiến trình

phân tích được tiếp tục thực hiện bằng cách phân tích và .

Bài toán phân tích thành thừa số, hay bài toán tìm ước số của một số

nguyên cho trước, đã được nghiên cứu nhiều, nhưng cũng chưa có một thuật

toán nào hiệu quả để giải quyết nó trong trường hợp tổng quát [2, 3]. Do đó

người ta có khuynh hướng tìm thuật toán giả nó trong những trường hợp đặc

biệt, chẳng hạn khi có một ước nguyên tố với:

là B-mịn với một cần B>0 nào đó, hoặc khi là số Blum, tức là

số có dạng tích của hai số nguyên tố lớn nào đó.

Có rất nhiều thuật toán phân tích một số nguyên lẻ thành tích các số

nguyên tố như: thuật toán sàng bậc hai, thuật toán đường cong Elliptic, thuật

toán sàng trường số, hay phương pháp và thuật toán của Pollard, thuật

toán của Wiliams, thuật toán liên phân số và dĩ nhiên là các phép chia thử.

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

Bài toán đặt ra: Cho trước số nguyên lẻ , với là các số nguyên

tố lớn. Giả thiết

Với giả thiết trên ta có thể dễ dàng chứng minh được

Thật vậy, ta có mà nên

Thuật toán thứ nhất này xác định số nguyên tố lớn nhất

Thuật toán như sau:

Input: Một số nguyên lớn lẻ (odds)

Output: hai nhân tử của

35

Algorithm:

Step 1: Set , , , ( là phần nguyên của

)

Step 2: If goto step 4

Step 3: Set , y=y+2 goto step2

Step 4: If then thuật toán dừng.

Khi đó chúng ta sẽ có:

(đây chính là hai nhân tử của )

Và là phân số có giá trị lớn nhất

Step 5: Set ;

Goto step 3

Tiến hành phân tích thuật toán thứ nhất, thuật toán này được xây dựng

dựa trên định lý Fermat. Nội dung của định lý Fermat như sau:

Định lý Fermat: Giả sử là một số nguyên dương lẻ có dạng

Trong đó và là các số nguyên tố. Khi đó biểu thức có thể

viết dưới dạng: với là các số nguyên dương. Các số nguyên

có mối quan hệ và

Chứng minh:

Thật vậy, giả sử khi đó ta có:

Ngược lại, nếu ta có: (1)

Với dương, ta có thể viết vế phải của (1) là

Áp dụng thuật toán Fermat, để phân tích thuật toán 1 xác định các thừa

số nguyên tố của .

36

Tại bước 4 ta thấy rằng:

Theo định lý Fermat ta sẽ có:

Nên: Suy ra: (do )

Và giá trị của phân số chính là giá trị lớn nhất của số nguyên tố

Ví dụ: Hãy tìm một nhân tử của với

Step 1: ; ,

Quá trình được tính toán như sau:

y R X

1 185 193

1 8 195

3 7 195

5 4 195

7 -1 195

7 194 197

9 187 197

11 178 197

13 167 197

15 154 197

17 139 197

19 122 197

21 103 197

37

23 197 82

25 197 59

27 197 34

29 197 7

31 197 -22

31 199 175

33 199 144

35 199 111

37 199 76

39 199 39

41 199 0

Khi đó ta sẽ có: . Vậy

Thuật toán 1 yêu cầu vòng lặp. Do vậy ưu điểm là đơn giản,

tuy nhiên đòi hỏi nhiều vòng lặp.

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

Ta biết độ an toàn của hệ mật RSA phụ thuộc vào độ khó của phép phân

tích thành các thừa số nguyên tố . Nếu hai số nguyên tố : thì

khả năng phân tích được là cao. Vì thế các nhà khoa học khuyến cáo: nên chọn

giá trị : và độ dài của xấp xỉ bằng một nửa độ dài . Khi đó

xác suất nằm trong khoảng là lớn.

Bài toán đặt ra: Cho là số nguyên dương lẻ, . Nội dung bài

toán này là tìm nhân tử lẻ nhỏ nhất của sao cho hoặc khẳng

định rằng không tồn tại nhân tử như vậy. Nội dung các bước tiến hành như sau:

Thuật toán được thực hiện như sau:

Input: Số nguyên dương

38

Output:

- Tìm ra nhân tử

- Trả lời “không tìm ra nhân tử nào như vậy”

Algorithm:

1. Step 1: Set ;

;

;

;

2. Step 2: If thuật toán kết thúc và ta không tìm được nhân

tử hay thừa số nào thỏa mãn điều kiện:

, 3. Step 3: Set

;

, goto step 5

5. Step 4: If , set

, goto step 5(quay lại bước này một lần nữa)

6. Step 5: If then là một thừa số của

Và thuật toán kết thúc, ta sẽ thu được

Else goto step 2

Như vậy ta thấy rằng thuật toán sẽ quét tất cả các giá trị lẻ nằm trong

khoảng

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

Bài toán đặt ra: (giống như thuật toán thứ nhất) cho trước một số lẻ,

hãy xác định nhân tử lớn nhất của n mà không vượt qua

Thủ tục này giải bài toán này được tiến hành như sau:

39

Lấy số nguyên

Ta lập ma trận (bảng) Sieve với ; như sau:

có nghiệm nếu nếu trái lại

Sau khi có bảng ta tiến hành xây dựng thuật giải như sau:

Input: Một số nguyên lẻ

Output: các thừa số nguyên tố của

Algorithm:

Step1: Đặt và , với

Step 2: If

For to goto Step4

Step 3: đặt ;

For i=1 to r goto Step 2

Step 4: đặt hoặc

4.1. If then là một nhân tử cần tìm của

và thuật toán kết thúc.

4.2. Else goto Step 3

Trong đó:

- là số nguyên bé nhất mà lớn hơn hoặc bằng .

- là số nguyên lớn nhất mà nhỏ hơn hoặc bằng

.

Thuật toán Pollard

Nguyên tố của nó đều . ý chính của thuật toán này là:

Giả sử là B-mịn. Ta ký hiệu là bội chung nhỏ nhất của tất cả các luỹ

thừa của số nguyên tố mà bản thân chúng .

40

Nếu thì , tức với là số nguyên bé nhất lớn

hơn .

Khi đó ta có:

Trong đó tích lấy theo tất cả các số nguyên tố khác nhau . Nếu là

một thừa số nguyên tố của sao cho là B-mịn, thì và do đó với

mọi bất kỳ thỏa mãn , theo định lý Fermat ta có: . Vì

vậy, nếu lấy thì . Nếu , coi như thuật toán không cho

ta kết quả mong muốn.

Tuy nhiên điều đó chắc không xảy ra nếu có ít nhất hai thừa số nguyên

tố khác nhau. Bây giờ chúng ta sẽ xét thuật toán để khẳng định thêm những lập

luận ở trên.

_Thuật toán Pollard phân tích thành thừa số:

Input: Một hợp số không phải là luỹ thừa của một số nguyên tố

Output: Một thừa số nguyên tố không tầm thường của

Algorithm:

1. Chọn một lần cho độ mịn

2. Chọn ngẫu nhiên một số nguyên

Tính

If then là kết quả cần tìm.

3. Với mỗi số nguyên tố thực hiện:

3.1. Tính

3.2. Tính

4. Tính

5. If then cho kết quả

41

6. Else không tìm thấy kết quả nào thỏa mãn.

Xét ví dụ sau để hiểu rõ hơn về thuật toán này. Dùng thuật toán cho

, chọn và .

Ta sẽ tính được . Chuyển sang thực hiện bước 3 ta được bảng

sau đây(mỗi hàng ứng với giá trị của ).

Q L A

2 24 2293244

3 15 13555889

5 10 16937233

7 8 15214586

11 6 9685355

13 6 13271154

17 5 11406961

19 5 554506

Sau đây là cách tính (bước 4)

Vậy ta tìm được một thừa số , do đó thừa số . Cả hai

đều là thừa số nguyên tố.

Ta thấy , có tất cả các ước nguyên tố đều , do đó

chắc chắn thuật toán kết thúc sẽ có kết quả. Thuật toán sẽ kết thúc không có kết

quả khi độ mịn được chọn quá bé để không một thừa số nguyên tố nào của

mà chỉ chứa các ước số nguyên tố . Như vậy, có thể xem _thuật

toán Pollard phân tích thành thừa số nguyên tố có hiệu quả đối với những số

nguyên là mịn, người ta tính được thời gian cần để thực hiện thuật toán là

cỡ vào khoảng phép nhân theo module.

42

Kết luận Chương 2

Tấn công hệ mật RSA, bản chất là việc phân tích để tìm ra khóa bí mật,

hay chính là việc tìm ra cặp số nguyên tố . Nội dung Chương 2 trình bày

kết quả tìm hiểu, nghiên cứu các thuật toán kiểm tra tính nguyên tố đối với một

số nguyên. Theo đó, đã nghiên cứu tìm hiểu 3 thuật toán phổ dụng nhất là

Farmat, Solovay-Strassen và Miller- Rabin, so sánh ưu điểm của 3 thuật toán

này để đưa ra một số khuyến cáo trong việc ứng dụng. Đồng thời trình bày kết

quả kiểm tra tính nguyên tố đối với số nguyên tố Mersenne, được sử dụng nhiều

trong lĩnh vực mật mã hiện nay.

Dựa trên các kết quả nghiên cứu về toán học, cùng với một số giả thiết,

Chương 2 trình bày tổng quan 3 thuật toán phân tích số nguyên bằng phương

43

pháp phân tích nhân tử được sử dụng phổ biến hiện nay. Các phương pháp phân

tích dựa trên phương pháp nhân tử này chỉ khả dụng trong trường hợp không

quá lớn. Do vậy với trường hợp số nguyên lớn cần có một thuật toán phân tích

đủ mạnh để giải quyết yêu cầu bài toán đặt ra.

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Ử

3.1 Mở đầu

Trong chương này, tác giả nghiên cứu và xây dựng phần mềm mô tả

thuật toán tấn công hệ mật RSA mà không cần phân tích nhân tử của

tham số RSA. Như chúng ta đã biết, các thuật toán phân tích nhân tử của tham

số RSA đã được trình bày ở chương 2 chỉ có hiệu quả khi tham số không quá

lớn, tức là số và với công cụ tính toán hiện đại nhất có thể có hiện tại.

Trong khi theo tiêu chuẩn X509 thì tham số phải lớn, cụ thể là mới

đảm bảo cho hệ mật RSA đủ an toàn. Một ưu điểm của thuật toán sắp được đề

xuất là tham số càng lớn càng tốt.

44

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

3.2.1 Một số mệnh đề

Cho là một số nguyên dương, chúng ta cần trả lời câu hỏi “ có phải

là tích của 2 số nguyên tố hay không?”Ta có các mệnh đề sau đây:

Mệnh đề 1. Giả sử, là một số nguyên dương lẻ, không chính phương

(square - free number). Điều kiện cần và đủ để là tích của 2 số nguyên tố là

bất đẳng thức kép sau đây được duy trì:

(3.1) . Trong đó là hàm Phi- Euler

Chứng minh

1/ Điều kiện đủ: Trước hết ta thấy rằng không phải là số nguyên tố vì

nếu là số nguyên tố thì . Điều này trái với giả thiết đã cho. Bây giờ,

giả sử là tích của 3 số nguyên tố trở lên. Ta ký hiệu là một số nguyên tố

nhỏ nhất và là một nhân tử của . Khi đó, rõ ràng rằng: và do đó, ta có

: trái với giả thiết, vậy điều kiện đủ được

chứng minh.

2/ Điều kiện cần:Giả sử với là hai số nguyên tố phân biệt,

theo tính chất của hàm Phi- Euler ta có:

Mặt khác

Vậy ta có: . Mệnh đề 1 được chứng minh.

Mệnh đề 2. Giả sử là tích của 2 số nguyên tố lẻ phân biệt

Khi đó:

(3.2)

Chứng minh. Đây là hệ quả của chứng minh Mệnh đề 1

Mệnh đề 3. Giả sử trong đó, là 2 số nguyên tố lẻ phân biệt

Khi đó giới hạn

45

(3.3)

Việc chứng minh Mệnh đề 3 được suy ra từ Mệnh đề 2

Mệnh đề 4. Cho với là 2 số nguyên tố lẻ phân biệt. Khi đó

việc biết được và tương đương việc biết được hàm . Nói chính xác

hơn, chúng ta có thể tính được hàm từ và với phép toán bít và

có thể tính được và từ hàm với phép toán bít.

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

Để xác định hàm , ta thiết lập bài toán như sau:

Cho trước 2 số nguyên tố lẻ khác nhau . Đặt n = pq.. Ta biết rằng

. Lúc đó

(3.4)

Hay:

, từ đó có (3.5)

Phương trình bậc 2 ẩn cho ở (3.5) có dạng

, trong đó (3.6)

Do là chẵn và là số tự nhiên chẵn nên ta có thể biến đổi (3.6)

như sau:

Với , và

Từ đó, phương trình cho ở (3.5) được viết thành

(3.7)

Xét biệt số

(3.8)

46

là nghiệm nguyên dương nên căn bậc hai phải là giá trị nguyên

dương, tức phải là số chính phương (perfect square), nghĩa là là bình

phương đúng của một số nguyên dương. Như vậy, bài toán đặt ra hãy xác định

sao cho là số chính phương. Theo mệnh đề 3 ta chỉ cần xác định giá trị

:

(3.9)

3.3 Nghiên cứu thuật toán

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

Input: Cho , trong đó là hai số nguyên tố lẻ khác nhau

Output: Xác định hoặc :

Algorithm:

Step 1. Tính

Step 2. Đặt

Step 3. Đặt , nếu lẻ

nếu chẵn

Step 4. Với tính

Step 5. Nếu là số nguyên thì dừng:

; là

đáp số bài toán

Step 6. Trái lại, đặt , quay lại Step 4

Lưu đồ thuật toán như sau:

47

Hình 3.2: Lưu đồ thuật toán

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

Chương trình được viết bằng ngôn ngữ C, sử dụng thư viện số lớn

(BigNumber) kiểm tra và phân tích số nguyên thành số nguyên tố . Đây

là phương pháp tấn công hệ mật RSA mà không cần phân tích nhân tử.

3.2.2.1 Giao diện chương trình

48

Chương trình phân tích số nguyên tố được thiết kế giao diện như sau:

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

Tại giao diện chính, thao tác nhập số cần phân tích và lựa chọn “phân

tích”. Trong quá trình muốn dừng việc phân tích thì clik “dừng”.

3.2.2.2 Một số chức năng chính

+ Kiểm tra số nhập vào là chẵn hoặc nguyên tố: Sau khi nhập số cần

phân tích và thao tác click “Phân tích”. Khi đó, đầu tiên chương trình sẽ tiến

hành kiểm tra tính chẵn và tính nguyên tố của số nhập vào. Nếu không thỏa

mãn, chương trình sẽ hiển thị thông báo “Số nhập vào là số chẵn, không hợp

lệ”và dừng việc phân tích.

49

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

Trường hợp là số nguyên tố, hiển thị “số nhập vào là số nguyên tố, không

phân tích được” và dừng việc phân tích.

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

+ Chức năng phân tích:Nếu thỏa mãn tính chẵn và tính nguyên tố,

chương trình sẽ tiến hành phân tích theo thuật toán đề xuất.

50

Hình 3.6: Chức năng phân tích

+ Chức năng dừng trong quá trình phân tích: Khi muốn dừng việc phân

tích, tính toán ta sẽ click “Dừng”, chương trình sẽ dừng toàn bộ việc tính toán

tại thời điểm yêu cầu.

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

51

+ Hiển thị, thông báo kết quả: Hoàn tất quá trình phân tích, chương trình

hiển thị thông báo “xong” và kết quả tìm được của cùng toàn bộ các kết

quả tính .

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

3.3.3 Một số ví dụ

Ví dụ 1: Cho , tìm hàm

Ta có và . Vậy cận trên của là

. Vì là một số chẵn nên ta chọn và tính

.

Vậy là số chính phương. Do đó là nghiệm cần tìm. Từ

đó và . Thử lại do đó

trùng với kết quả đã tìm được ở trên.

Ví dụ 2: Cho , xác định

do đó ;

Chọn

Tính không phải

là số chính phương;

52

không phải là số chính phương; Tính tiếp

là số chính phương; Tính tiếp

và , số nguyên tố Do đó

là

Ví dụ 3: Cho , xác định

; Ta có

Chọn

Tính không phải là số

chính phương;

Tính không phải là số chính phương;

Tiếp tục tính là số chính phương.

do đó

Từ đó tìm ra được hai số nguyên tố và

Ví dụ 4: Cho , xác định

Ta có và

Chọn

Tính không phải là

số chính phương.

Tính không phải số chính phương…

Tiếp tục tính là số chính phương

Do đó, và

Ví dụ 5: Cho , xác định

Tính

Chọn

53

Tính không phải số

chính phương

Tính không phải số chính phương…

Tính là số chính phương

Do đó

Kết luận Chương 3

54

Dựa trên một số kết quả nghiên cứu chứng minh về mặt toán học, thuật

toán phân tích số nguyên lớn có những ưu điểm nhất định, bởi khi càng lớn

thì càng tiệm cấn đến , nên việc xác định trở nên thuận lợi.

Kết quả thực nghiệm cho thấy việc tính toán trong các vòng lặp đơn giản, mỗi

vòng lặp chỉ thực hiện 4 phép tính cộng (+), trừ (-) và bình phương, do vậy việc

xây dựng chương trình thuật toán đơn giản. Ví dụ, đối với trường hợp n gồm

19 chữ số thập phân, thuật toán chỉ thực hiện 143217727 vòng lặp, số các phép

tính để xác định được giá trị là 536870908.

Chương trình phân tích có giao diện trực quan và các chức năng, thao tác

thân thiện người dùng. Một số thực nghiệm thực tế cho kết quả nhanh hơn đối

với các thuật toán sử dụng phương pháp nhân tử. Tuy nhiên để có kết luận một

cách chính xác hơn, cần có những thực nghiệm so sánh với các thuật toán phân

tích hiện có, dựa trên các phân tích, thống kê số liệu khảo sát, tổng hợp làm sở

cứ khoa học và thực tiễn chắc chắn, từ đó đưa ra những kết luận, đánh giá chính

xác và khuyến cáo phù hợp.

Mặt khác, để có thể áp dụng trong thực tế, chúng ta cần xác định cận

dưới của hàm một cách tối ưu hơn sao cho khoảng cách giữa cận trên và

cận dưới là gần nhau có thể được sao cho xác suất để nằm trong khoảng

đó là trên 99% .

KẾT LUẬN

55

Luận văn đã tiến hành nghiên cứu tổng quan về hệ mật RSA, phân tích

vấn đề an toàn của hệ mật, để làm rõ những điểm yếu, nguy cơ khai thác để tấn

công hệ mật hiện nay. Đồng thời đã nghiên cứu những phương pháp, biện pháp

phổ biến được sử dụng để tấn công RSA.

Trên cơ sở đó, luận văn tìm hiểu nghiên cứu một số thuật toán kiểm tra

tính nguyên tố và phân tích số nguyên lớn bằng phương pháp nhân tử, để đưa

ra những kết luận, so sánh giữa chúng. Theo đó đã chứng minh được các

phương pháp này đều không khả dụng trong trường hợp phân tích các số

nguyên lớn.

Kế thừa một số kết quả nghiên cứu, chứng minh mới về mặt toán học,

luận văn đã đi sâu nghiên cứu thuật toán phân tích số nguyên mới không sử

dụng phương pháp nhân tử. Đồng thời đã tiến hành xây dựng Chương trình

phân tích một cách trực quan, thân thiện và tổ chức thực nghiệm, đánh giá để

rút ra một số kết luận và khuyến cáo trong việc tấn công RSA.

Kết quả thực nghiệm ban đầu cho phép khẳng định phương pháp sử dụng

có nhiều ưu điểm. Tuy nhiên cần tiếp tục được nghiên cứu, phát triển, tối ưu

hóa cận dưới của hàm .

Mặt khác, để đạt hiệu quả phân tích thám mã cao, cần có sự đầu tư nghiên

cứu xây dựng hệ thống tính toán lớn, hiệu năng cao sử dụng các công nghệ mới

nhất để tăng tốc độ xử lý và tính toán.

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

56

Tiếng Việt

[1] Hồ Văn Canh, Nguyễn Viết Thế, “Phân tích thông tin có bảo mật”

NXB Hà Nội T&T, 2010.

[2] Lê Công Tuấn Anh, Trịnh Nhật Tiến, “Các phương pháp tấn công

chữ ký số: rsa, elgamal, dss”, Đại học Công nghệ, Đại học Quốc gia Hà Nội,

2016.

[3] Mai Thị Thúy Hà, Hồ Văn Canh, “Nghiên cứu tấn công hệ mật khóa

công khai RSA”, Đại học Công nghệ, Đại học Quốc gia Hà Nội, 2013.

[4] Nguyễn Anh Tuấn, Hồ Văn Canh, “Xây dựng thuật toán tấn công

RSA không cần phân tích nhân tử”, Đại học Công nghệ, Đại học Quốc gia Hà

Nội, 2007.

[5] Phan Đình Diệu, “Lý thuyết mật mã và an toàn thông tin”, Đại học

Quốc gia Hà Nội, 2002.

Tiếng Anh

[6] Alfred J. Menezes, Scott A Vanstone, “Handbook of Applied

Cryptography”, CRC Press,1996.

[7] Abdelhak Azhari1, Samir Bouftass, “On a new fast public key

cryptosystem”, 2015.

[8] ANSIX9. 44, “Public Key Cryptography Using Reversible

Algorithms for the Financial Services Industry: Transport of Symmetric

Algorithm Keys Using RSA”, draft, 2004.

[9] Caxton Foster, “Cryptanalysis for Microcomputers”, Rochelle

Park,1982.

[10] D. Boneh, “Twenty Years of Attacks on the RSA Cryptosystems”,

Notices of the AMS, 1999.

[11] Donal Knut, “The Art of Progamming Computer”, Tom, 2004.

[12] I. Anshel, M. Anshel, and D. Goldfeld, “An algebraic method for

public-key cryptography”, Methematical Research Letters, 2006.

57

[13] Mark Stamp, Richard, M. Low, “Applied Cryptanalysis”, Wiley -

InterScience A. John wiley & Sons, INC Publication, 2007.

[14] W. Alext, B. Chor, O. Goldreich, and C.P. Schnor, “RSA and

Rabin functions: Certain parts are as hard as the whole”, SIAM Journal

on Computing, 2009.

Website

[15]http://vi.wikipedia.org/wiki/Số-nguyên-tố

[16] http://primes.utm.edu/largest.html

[17] http://www.rsa.com

[18] http://www.rsasercurity.com

PHỤ LỤC

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

58

using System.Collections.Generic;

using System.Linq;

using System.Threading.Tasks;

using System.Windows.Forms;

namespace Phan_Tich_So_Nguyen_To

{

static class Program

{

///

/// The main entry point for the application.

///

[STAThread]

static void Main()

{

Application.EnableVisualStyles();

Application.SetCompatibleTextRenderingDefault(false);

Application.Run(new Form1());

}

}

}

--------

namespace Phan_Tich_So_Nguyen_To

{

partial class Form1

{

///

/// Required designer variable.

///

private System.ComponentModel.IContainer components = null;

///

/// Clean up any resources being used.

using System;

59

/// true if managed resources should be disposed;

otherwise, false.

protected override void Dispose(bool disposing)

{

if (disposing && (components != null))

{

components.Dispose();

}

base.Dispose(disposing);

}

#region Windows Form Designer generated code

///

/// Required method for Designer support - do not modify

/// the contents of this method with the code editor.

///

private void InitializeComponent()

{

System.ComponentModel.ComponentResourceManager resources = new

System.ComponentModel.ComponentResourceManager(typeof(Form1));

this.richTextBox1 = new System.Windows.Forms.RichTextBox();

this.textBox1 = new System.Windows.Forms.TextBox();

this.btnAnalysis = new System.Windows.Forms.Button();

this.label1 = new System.Windows.Forms.Label();

this.backgroundWorker1 = new System.ComponentModel.BackgroundWorker();

this.progressBar1 = new System.Windows.Forms.ProgressBar();

this.label2 = new System.Windows.Forms.Label();

this.button1 = new System.Windows.Forms.Button();

this.SuspendLayout();

//

// richTextBox1

//

///

60

((System.Windows.Forms.AnchorStyles)((((System.Windows.Forms.AnchorStyles.Top |

System.Windows.Forms.AnchorStyles.Bottom)

| System.Windows.Forms.AnchorStyles.Left)

| System.Windows.Forms.AnchorStyles.Right)));

this.richTextBox1.Font = new System.Drawing.Font("Microsoft Sans Serif",

15.75F, System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point,

((byte)(0)));

this.richTextBox1.ForeColor = System.Drawing.Color.ForestGreen;

this.richTextBox1.Location = new System.Drawing.Point(0, 58);

this.richTextBox1.Name = "richTextBox1";

this.richTextBox1.ReadOnly = true;

this.richTextBox1.Size = new System.Drawing.Size(925, 477);

this.richTextBox1.TabIndex = 0;

this.richTextBox1.Text = "";

//

// textBox1

//

this.textBox1.AcceptsReturn = true;

this.textBox1.Anchor =

((System.Windows.Forms.AnchorStyles)(((System.Windows.Forms.AnchorStyles.Top |

System.Windows.Forms.AnchorStyles.Left)

| System.Windows.Forms.AnchorStyles.Right)));

this.textBox1.Font = new System.Drawing.Font("Microsoft Sans Serif", 14.25F,

System.Drawing.FontStyle.Italic, System.Drawing.GraphicsUnit.Point, ((byte)(0)));

this.textBox1.ForeColor = System.Drawing.Color.FromArgb(((int)(((byte)(0)))),

((int)(((byte)(0)))), ((int)(((byte)(192)))));

this.textBox1.Location = new System.Drawing.Point(185, 17);

this.textBox1.Name = "textBox1";

this.textBox1.ShortcutsEnabled = false;

this.textBox1.Size = new System.Drawing.Size(280, 29);

this.textBox1.TabIndex = 1;

this.richTextBox1.Anchor =

61

System.Windows.Forms.KeyPressEventHandler(this.textBox1_KeyPress);

//

// btnAnalysis

//

this.btnAnalysis.Anchor =

((System.Windows.Forms.AnchorStyles)((System.Windows.Forms.AnchorStyles.Top |

System.Windows.Forms.AnchorStyles.Right)));

this.btnAnalysis.Font = new System.Drawing.Font("Microsoft Sans Serif", 12F,

System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(0)));

this.btnAnalysis.ForeColor = System.Drawing.Color.DarkGreen;

this.btnAnalysis.Location = new System.Drawing.Point(471, 14);

this.btnAnalysis.Name = "btnAnalysis";

this.btnAnalysis.Size = new System.Drawing.Size(116, 30);

this.btnAnalysis.TabIndex = 2;

this.btnAnalysis.Text = "Phân tích";

this.btnAnalysis.UseVisualStyleBackColor = true;

this.btnAnalysis.Click += new System.EventHandler(this.btnAnalysis_Click);

//

// label1

//

this.label1.AutoSize = true;

this.label1.Font = new System.Drawing.Font("Microsoft Sans Serif", 14.25F,

System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(0)));

this.label1.ForeColor = System.Drawing.Color.Green;

this.label1.Location = new System.Drawing.Point(12, 20);

this.label1.Name = "label1";

this.label1.Size = new System.Drawing.Size(167, 24);

this.label1.TabIndex = 3;

this.label1.Text = "Số cần phân tích";

//

// backgroundWorker1

this.textBox1.KeyPress += new

62

this.backgroundWorker1.WorkerReportsProgress = true;

this.backgroundWorker1.WorkerSupportsCancellation = true;

this.backgroundWorker1.DoWork += new

System.ComponentModel.DoWorkEventHandler(this.backgroundWorker1_DoWork);

this.backgroundWorker1.ProgressChanged += new

System.ComponentModel.ProgressChangedEventHandler(this.backgroundWorker1_Progr

essChanged);

this.backgroundWorker1.RunWorkerCompleted += new

System.ComponentModel.RunWorkerCompletedEventHandler(this.backgroundWorker1_

RunWorkerCompleted);

//

// progressBar1

//

this.progressBar1.Dock = System.Windows.Forms.DockStyle.Bottom;

this.progressBar1.Location = new System.Drawing.Point(0, 535);

this.progressBar1.Name = "progressBar1";

this.progressBar1.Size = new System.Drawing.Size(925, 23);

this.progressBar1.Step = 1;

this.progressBar1.TabIndex = 5;

//

// label2

//

this.label2.Anchor =

((System.Windows.Forms.AnchorStyles)((System.Windows.Forms.AnchorStyles.Top |

System.Windows.Forms.AnchorStyles.Right)));

this.label2.Font = new System.Drawing.Font("Microsoft Sans Serif", 12F,

System.Drawing.FontStyle.Italic, System.Drawing.GraphicsUnit.Point, ((byte)(0)));

this.label2.Location = new System.Drawing.Point(697, 4);

this.label2.Name = "label2";

this.label2.Size = new System.Drawing.Size(228, 51);

this.label2.TabIndex = 6;

//

63

this.label2.TextAlign = System.Drawing.ContentAlignment.MiddleCenter;

//

// button1

//

this.button1.Anchor =

((System.Windows.Forms.AnchorStyles)((System.Windows.Forms.AnchorStyles.Top |

System.Windows.Forms.AnchorStyles.Right)));

this.button1.Font = new System.Drawing.Font("Microsoft Sans Serif", 12F,

System.Drawing.FontStyle.Bold, System.Drawing.GraphicsUnit.Point, ((byte)(0)));

this.button1.ForeColor = System.Drawing.Color.DarkGreen;

this.button1.Location = new System.Drawing.Point(593, 14);

this.button1.Name = "button1";

this.button1.Size = new System.Drawing.Size(82, 30);

this.button1.TabIndex = 2;

this.button1.Text = "Dừng";

this.button1.UseVisualStyleBackColor = true;

this.button1.Click += new System.EventHandler(this.button1_Click);

//

// Form1

//

this.AcceptButton = this.btnAnalysis;

this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);

this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;

this.ClientSize = new System.Drawing.Size(925, 558);

this.Controls.Add(this.label2);

this.Controls.Add(this.label1);

this.Controls.Add(this.button1);

this.Controls.Add(this.btnAnalysis);

this.Controls.Add(this.textBox1);

this.Controls.Add(this.richTextBox1);

this.Controls.Add(this.progressBar1);

this.label2.Text = "© All rights reserved by \r\nMr. Hoàng";

64

this.Icon = ((System.Drawing.Icon)(resources.GetObject("$this.Icon")));

this.MaximizeBox = false;

this.Name = "Form1";

this.SizeGripStyle = System.Windows.Forms.SizeGripStyle.Hide;

this.Text = "Phân tích số nguyên tố";

this.Load += new System.EventHandler(this.Form1_Load);

this.ResumeLayout(false);

this.PerformLayout();

}

#endregion

private System.Windows.Forms.RichTextBox richTextBox1;

private System.Windows.Forms.TextBox textBox1;

private System.Windows.Forms.Button btnAnalysis;

private System.Windows.Forms.Label label1;

private System.ComponentModel.BackgroundWorker backgroundWorker1;

private System.Windows.Forms.ProgressBar progressBar1;

private System.Windows.Forms.Label label2;

private System.Windows.Forms.Button button1;

}

}

------------------------------------------

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Threading;

using System.Threading.Tasks;

using System.Windows.Forms;

this.ForeColor = System.Drawing.Color.DarkGreen;

65

namespace Phan_Tich_So_Nguyen_To

{

public partial class Form1 : Form

{

public Form1()

{

InitializeComponent();

}

Int64 tinhN(Int64 thamso)

{

return (thamso + 1) / 2;

}

Int64 tinhB(Int64 n, Int64 canN)

{

if ((n - canN) % 2 == 0)

return n - canN;

else return n - canN - 1;

}

Int64 tinhCanN(Int64 thamso)

{

return (Int64)Math.Sqrt(thamso);

}

Int64 tinhF(Int64 nPhay, Int64 B, Int64 N)

{

return (nPhay - B) * (nPhay - B) - N;

}

bool kiemTraSoChinhPhuong(Int64 N)

{

try

{

66

{

return true;

}

else

{

for (double i = 0; i < (Int64)Math.Sqrt(N)+1 ; i++)

{

if (i * i == N) return true;

}

}

return false;

}

catch (Exception)

{

MessageBox.Show("Error here");

return false;

}

}

private void backgroundWorker1_ProgressChanged(object sender,

ProgressChangedEventArgs e)

{

progressBar1.Value = e.ProgressPercentage;

//richTextBox1.ScrollToCaret();

}

private void backgroundWorker1_RunWorkerCompleted(object sender,

RunWorkerCompletedEventArgs e)

{

//progressBar1.Hide();

MessageBox.Show("Xong!");

btnAnalysis.Enabled = true;

if (N == 0 || N == 1)

67

int validate(string input)

{

long res=0;

if (!Int64.TryParse(input,out res) )

{

return 1;//số nhập không hợp lệ

}

res = Int64.Parse(input);

if (res % 2 == 0)

{

return 2;// số là số chẵn

}

else if (checkPrime(res) == 2)

{

return 3;// số nguyên tố

}

else return 0;// số hợp lệ

}

int checkPrime(Int64 number)

{

int count = 0;

for (int i = 1; i <= number; i++)

{

if(number%i==0) count++;

if (count > 2) break;

}

return count;

}

void AppendTextBox(string Value)

{

if (InvokeRequired)

}

68

this.Invoke(new Action(AppendTextBox), new object[] { Value });

return;

}

richTextBox1.AppendText(Value);

//richTextBox1.ScrollToCaret();

}

private void backgroundWorker1_DoWork(object sender, DoWorkEventArgs e)

{

try

{

if (validate(textBox1.Text)==1)

{

AppendTextBox("Số nhập vào không hợp lệ \n");

}

else if (validate(textBox1.Text)==2)

{

AppendTextBox("Số nhập vào là số chẵn, không hợp lệ \n");

}

else if (validate(textBox1.Text) == 3)

{

AppendTextBox("Số nhập vào là số nguyên tố, không phân tích được \n");

}

else

{

Int64 N=Int64.Parse(textBox1.Text);

Int64 nPhay = tinhN(N);

//In ra N'

AppendTextBox("Bước 1: Tính n'=(n+1)/2: "+nPhay.ToString()+"\n");

Int64 B = tinhB(nPhay,tinhCanN(N));

AppendTextBox("Bước 2: Tính b'=n'-[sqrt(n)]: " + B.ToString() + "\n");

AppendTextBox("Bước 3: Tính toán tiếp theo: \n");

{

69

{

if (this.backgroundWorker1.CancellationPending)

{

e.Cancel = true;

return;

}

long percentage = (B - i) * 100 / (B - 1);

if (percentage>100)

{

percentage = 100;

}

backgroundWorker1.ReportProgress((int.Parse(percentage.ToString())));

Int64 deltaPhay = (nPhay - i) * (nPhay - i) - N;

if (kiemTraSoChinhPhuong(deltaPhay))

{

Int64 deltaCP = (Int64)Math.Sqrt(deltaPhay);

Int64 p = nPhay - i - deltaCP;

Int64 q = nPhay - i + deltaCP;

String tmp = String.Format("Bước 3.{3} Delta' = ({4}-{5})^2-{6}={0} là

số chính phương;\n \t\t\t\t KẾT QUẢ: p={1} và q={2} \n", deltaPhay, p, q,(B-

i)/2+1,nPhay,i,N);

AppendTextBox(tmp);

return;

}

else {

String tmp = String.Format("Bước 3.{1} Delta' = ({2}-{3})^2-{4}={0}

không là số chính phương, tiếp tục tính \n", deltaPhay, (B - i)/2 +1, nPhay, i, N);

AppendTextBox(tmp);

}

//Thread.Sleep(100);

}

for (long i = B; i >= 0; i=i-2)

70

}

catch (Exception e1)

{

MessageBox.Show(e1.Message);

}

}

private void btnAnalysis_Click(object sender, EventArgs e)

{

btnAnalysis.Enabled = false;

button1.Enabled = true;

richTextBox1.Clear();

//backgroundWorker1.CancelAsync();

//progressBar1.Show();

backgroundWorker1.RunWorkerAsync();

}

private void Form1_Load(object sender, EventArgs e)

{

}

private void textBox1_KeyPress(object sender, KeyPressEventArgs e)

{

e.Handled = !char.IsDigit(e.KeyChar) && !char.IsControl(e.KeyChar);

}

private void button1_Click(object sender, EventArgs e)

{

backgroundWorker1.CancelAsync();

//backgroundWorker1.Dispose();

//backgroundWorker1 = null;

//GC.Collect();

btnAnalysis.Enabled = true;

MessageBox.Show("Dừng tính toán");

button1.Enabled = false;

}

71

}

}

}

Phụ lụcThư viện tính toán số lớn

72

Trước khi xây dựng giải pháp tấn công RSA, chúng ta nghiên cứu cách

biểu diễn số nguyên lớn cũng như các thuật toán số học làm việc với các số lớn

đó trong máy tính.

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

Có nhiều cách để biểu diễn và lưu trữ số lớn. Cách thông thường nhất là

biểu diễn bằng xâu ký tự. Cho một số lớn có chữ số thập phân được biểu

diễn trong hệ cơ số , có dạng ta sử dụng một xâu ký tự có

độ dài là ký tự để biểu diễn theo cách:

Chữ số được lưu vào phần tử

Chữ số được lưu vào phần tử

…………………………………….

Chữ số được lưu vào phần tử

Dấu của số lớn được đặt trong biến trạng thái “dau”

+ Nếu dau = 1 thì là số dương;

+ Nếu dau =-1 thì là số âm;

Ta quy ước khi nói đến số lớn thì là xâu ký tự, các phần tử của xâu

chính là các phần tử của số lớn được biểu diễn ở hệ cơ số một cách tương

ứng. Giả sử ta đang biểu diễn số lớn ở hệ cơ số nào đó và ta muốn chuyển số

lớn sang biểu diễn ở hệ cơ số thông qua thuật toán sau:

Input: số nguyên dương , số nguyên dương

Output: biểu diễn ở hệ cơ số của , ,

Thuật toán:

(1) ; ;

(2) while

; ;

73

(3) return

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

Ta quy ước số lớn biểu diễn trong hệ cơ số

2.1. So sánh hai số

Input: Số hai số lớn , có độ dài

Output:

- Nếu thì retum l.

- Nếu thì retum 0

- Nếu thì return 2.

Algorithm:

1. If ( dương, âm) return 1;

2. If ( âm, dương) return 0;

&&( âm) return 0; // 3: If

&& ( âm) return 1;// 4. if

&& ( dương) return 1; // 5. If

&& ( dương) return 0; // 6. If

7. If

7. l If ( dương)

For

return 1; // If

Else return 0;

7.2 Else if ( âm)

For

If return 0; //

Else if return 1; //

8. return 2;

74

2.2 Cộng hai số lớn dương

Cho là hai số lớn có độ dài lần lượt là và . Nếu số nào nhỏ hơn

sẽ được chèn thêm vào bên trái số đó sao cho độ dài của hai số là bằng

nhau.Cộng từng phần từ một của hai xâu lưu trữ hai số.

Input: Số hai số lớn , có độ dài

Output:

Algorithm:

; // nho: biến lưu giá trị nhớ của phép cộng , 1.

; 2. If

; Else

3. For

;

If

;

;

; Else

4. Return ;

2.3. Trừ hai số lớn dương

Cho là hai số lớn có độ dài lần lượt là và . Nếu số nào nhỏ hơn

sẽ được chèn thêm vào sao cho độ dài của hai số bằng nhau khi ta tiến hành

trừ. Ta tiến trừ từng phần tử một của hai xâu lưu trữ hai số lớn.

Input: Số hai số lớn , có độ dài

Output:

Algorithm:

1. ; // nho: biến lưu giá trị nhớ của phép trừ

2. For

75

;//chèn 0 vào nếu có độ dải nhỏ hơn 3. If

4. If

;

;

; Else

5. ;

6. Xét dấu cho ;

2.4 Phép nhân hai số lớn

2.4.1 Nhân số lớn với một số nguyên

Input: Số lớn và số nguyên

Output: , có độ dải tối thiểu bằng

Algorithm:

l. ; ;

p 2. for

; 3.

; 4.

; 5.

6. Độ dài của 1à ;

7. if

8. while

9. ; //Tăng độ dài của ,

; 10.

; 11.

12. ;

13.retum ;

76

2.4.2 Nhân hai số lớn

Cho hai số lớn , có cần tính có độ dài là

.

Để nhân hai số lớn ta tiến hành như sau:

- Lấy phần tử của số thứ hai nhân với tất cả các phần tử của số thứ nhất

hay nóicách khác lấy từng phần tử của nhân với toàn bộ cộng thêm một

phần tử nhớ, được kết quả đem chia cho hệ cơ số, lấy số dư làm kết quả của

hàng tương ứng, thương số là số nhớ của số mới.

- Dịch trái một số bước phù hợp.

- Cộng tất cả các kết quả nhân lại

Cụ thể thuật toán nhân hai số lớn như sau:

Input: Hai số lớn , có độ dài là và

Output:

Algorithm:

; 1.

2. BigNum ;

3. for

; 4. ; // Nhân một số lớn với một số nguyên

5. Dichtrai ; // dịch trái vị trí;

6. ;

7. Retum ;

2.5 Phép chia hai số lớn dương

Hai số lớn , có độ dài là và

Xét trường hợp phép chia hai số lớn có thương nhỏ hơn hoặc bằng 9

Input: Hai số lớn , có độ dài là và

Output: ; có độ dài là ;

77

Algorithm:

1.For to do

2. BigNum ;

3. ; // Nhân một số lớn với một số nguyên

4. If (Sosanh ==1) return

5. Else If (Sosanh ==2) retum

Thuật toán chia hai số lớn dựa trên ý tưởng của phép chia thông thường

Input: Hai số lớn có độ dài

Output:

Algorithm:

1. BigNum ;

2. If ( )

cout << “ Loi Chia Cho 0”;

return ;

3. If

3.1. ;

3.2. Độ dài của là 1;

3.3 dau = l;// dương

3.4 return ;

4.

5. for down to // đảo ngược

5.1. Độ dài của số lớn là;

; 5.2.

5.3. if then ;

else Dich ;// Dịch sang trái vị trí

;

78

Chuan ; // loại bỏ các số 0: dạng thành

5.5 if( Sosanh != 0){

Chia ;// chia hai số lớn có thương

;

; ;

;

Chuan ;

5.6 If then ;

6. Độ dài của là ;

7. Giá trị dấu của = (giá tri dấu của ).(giá trị dấu của y)

8. z = dao( ); // đảo ngược lại số ;

9. return ;

2.6 Lũy thừa

Input:

Output:

Algorithm:

1. Đưa về dạng biểu diễn nhị phân

2. Xét và nếu thì là kết quả

3. Xét

4. Nếu thì

5. For

5.1.

5.2. Nếu thì

6. Return ;

2.7 Ước chung lớn nhất

Sử dụng thuật toán Euclidean mở rộng tìm ước chung lớn nhất của 2 số.

79

Input: Hai số lớn

Output: và 2 số nguyên thỏa mãn

Algorithm:

1. if then

2.

; 3.

4. While

4.1. ;

4.2. ;

4.3.

5. If then

6.

7. return ;

2.8. Phép nhân theo module p

Để tính , ta biểu diễn dưới dạng nhị phân trong đó

Áp dụng thuật toán Horner

Input: Ba số lớn

Output:

Algorithm:

; 1.

2. ;

3. For

80

;

If then ;

4. return ;

2.9 Tính căn của số nguyên lớn

Ta thực hiện tính căn của số nguyên có số phần tử chẵn. Để

ta thực hiện:

1. Chia thành cặp

2. Tìm một số nguyên dương // là số nguyên dương gần

nhất có thể được.

3. Tính

4. Ghép

5. Tính

6. Tìm một số nguyên dương sao cho

7. Tính

8. Đặt và lặp lại bước 5 // tức

9. Nếu thì dừng và số nguyên là số phải tìm.

2.10 Tìm phần từ nghịch đảo theo module p

Để tính nghịch đảo, chúng ta sẽ sử dụng thuật toán Euclidean mở rộng.

Algorithm:

Input: với

Output:

1. Sử dụng giải thuật Euclidean mở rộng tìm thỏa mãn điều kiện

và .

2. Nếu thì không tồn tại,

Ngược lại thì là giá trị cần tìm

2.11 Phép cộng có dấu

81

Phép cộng hai số có dấu được thực hiện dựa trên phép so sánh, phép cộng

và phép trừ hai số không âm đã trình bày; dấu của số lớn được lưu bít cao nhất

của số lớn.

Thuật toán cộng hai số lớn có dấu được thực hiện như sau:

Input: Hai số lớn

Output:

Algorithm:

1. If ( cùng dấu)

1.1. ;

1.2. Đặt cùng dấu với ;

1.3.Return ;

2. if ( dương) // âm

2.1. If(s = Sosanh !=0)

Retum ;

2.2. If(s==0)

;

Đặt cùng dấu với ;

return ;

3. if ( âm) // dương

3.1.if((s = Sosanh )==0)

Retum ;

3.2 if(sl==0)

;

Đặt cùng dấu với ;

Retum

2.12 Phép trừ có dấu

Phép trừ hai số có dấu được thực hiện dựa trên phép cộng hai số có dấu

82

Input: Hai số lớn

Output:

Algorithm:

1. Đổi dấu của ;

2. Cộng có dấu ;

3. Return ;

2.13 Phép nhân có dấu

Phép nhân hai số có dấu được thực hiện dựa trên phép nhân hai số không

âm đã được trình bày ở trên.

Input: Hai số lớn

Output: ;

Algorithm:

1. If ( cùng dấu) return ;

2. If( khác dấu)

;

Đổi dấu ;

3. Return ;