Tìm hiểu và mô phỏng thuật giải rsa trên matlab

Tìm hiểu và mô phỏng thuật giải RSA trên matlab Trang i BỘ GIÁO DỤC VÀ ĐÀO TẠO CỘNG HÒA XÃ HỘI CHỦ NGHĨA TRƯỜNG ĐẠI HỌC SƯ PHAM KY VIỆT NAM THUẬT THÀNH PHÓ HÒ CHÍ MINH Độc lập — Tự d

BO GIAO DUC VA DAO TAO

TRUONG DAI HOC SU’ PHAM KY THUAT

THÀNH PHÓ HÒ CHÍ MINH

HGMUIIE

ĐỎ ÁN TÓT NGHIỆP NGÀNH KỸ THUẬT ĐIỆN - ĐIỆN TỬ

TIM HIEU VA MO PHONG

THUAT GIAI RSA TREN MATLAB

GVHD: LE MINH THANH SVTH: NGUYEN DUC HUY

ae

BỘ GIÁO DỤC & ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUAT TP HO CHi MINH

KHOA DIEN - DIEN TU

BQ MON DIEN TU CONG NGHIEP

DO AN TOT NGHIEP

NGÀNH KỸ THUẬT ĐIỆN - ĐIỆN TỬ

TIM HIEU VA MO PHONG

THUAT GIAI RSA TREN MATLAB

GVHD: THS.LÊ MINH THÀNH SVTH: NGUYEN DUC HUY MSSV: 10301021 5

oe VIÊN TRƯỜNG ĐiiSPXT

ISKL 902324 l

Tp.Hồ Chí Minh, tháng 02/2012

PHAN A

GIOI THIEU

Tìm hiểu và mô phỏng thuật giải RSA trên matlab Trang i

LOT CAM ON

Cuốn đồ án tốt nghiệp đã hoàn thành đúng thời gian

quy định và đạt được kết quả như mong đợi Để đạt

được kết quá đó, trước hết nhóm thực hiện muốn gửi

lời biết ơn đến các bậc cha mẹ đã khổ công sinh thành đường dục để lạo nến những thành viên của nhóm

ngày hôm này Bên cạnh đá, kiiáng thế không kể đến

sự tận tình giúp đỡ của các đáy cô trong bộ môn

Điện tử -Viễn thông cũng như các tháy cô trong khoa

Điện- Điện tử, các thầy cô đã hết mực giúp đỡ nhóm

trong suốt quá trình học tập tại trướng, không chỉ giáo dục nhóm về kiến thức mà còn chí bảo những kỹ

năng sống cần thiết để nhóm có thể đứng vững trong

cuộc sống tự lập sau khi ra trường Đặc biệt, nhóm

thực hiện đề tài xin chân thánh cảm ơn thầẩy Lê Minh Thành giảng viên đã trực tiếp hướng dẫn nhóm

trong quá trình thực hiện dé tai Các thẩy đã tận tình

giúp đỡ nhóm trong quá trình học tập tại trường và thể hiện sự quan tâm với việc đảm nhận hướng dẫn nhóm

thực hiện đề tài tốt nghiệp

Một lần nữa nhóm thực hiện xin chân thành biết ơn

các bậc cha mẹ và chân thành cảm ơn quý thây cô đã

tận tình giúp đỡ nhóm trong quá trình học tập tại trường

Tìm hiểu và mô phỏng thuật giải RSA trên matlab Trang i

BỘ GIÁO DỤC VÀ ĐÀO TẠO CỘNG HÒA XÃ HỘI CHỦ NGHĨA

TRƯỜNG ĐẠI HỌC SƯ PHAM KY VIỆT NAM

THUẬT THÀNH PHÓ HÒ CHÍ MINH Độc lập — Tự do ~ Hạnh phúc

saElca

QUYÉT ĐỊNH GIAO ĐÈ TÀI

Họ và tên sinh viên: Nguyễn Đức Huy MSSV: 10301021

Ten dé tai: Phân Tích Cơ Chế Báo Mật RSA Và Thực Hiện

Mô Phòng Trên Matlab

1) Cơ sở bán dầu

Eù thục tiễn của việc thông tin đi động vá viễn thông ngày càng bùng nỗ,

si0g với sự: đan mê trong lĩnh vực điện tử và viễn thống, nhóm thực hiện đề tài

đà quyết định chọn nội dung đồ án tốt nghiệp lä mó tả một thuật giải mã và mã hòa dựa trên thuật toán RSA Đây có thể xem là một sự kết hợp tốt giữa kiến thức

viễn thông và chuyên ngành điện tử

2) Nội dung các phần thuyết minh và tính toán:

© Téng quan về mật mã và mã hóa

© Thuật giải RSA

© Mô phỏng thuật toán RSA trên Matlab

3) Các bản vẽ:

4) Giáo viên hướng dẫn: Th§ Lê Minh Thành

5) Ngày giao nhiệm vụ: / /2011

6) Ngày hoàn thành nhiệm vụ: seven 2012

Tìm hiểu và mô phỏng thuật giải ÑSA trên matlab Trang ii

NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN

Tìm hiểu và mô phỏng thuật giải RSA trén matlab Trang iii

NHAN XET CUA GIAO VIEN PHAN BIEN

Tìm hiểu và mô phỏng thuật giải RSA trên matlab Trang iv

LOI NOI DAU

Thé ky XXI thé kỷ công nghệ thông tin, thông tin đã và đang tác động trực

tiếp đến mọi mặt hoạt động kinh tế xã hội của hầu hết các quốc gia trên thế giới

Thông tin có một vai trò hết sức quan trọng, bởi vậy chúng ta phải làm sao đảm bảo được tính trong suốt của thông tin nghĩa là thông tin không bị sai lệch, bị thay

đối, bị lộ trong quá trình truyền từ nơi gửi đến nơi nhận

Với sự phát triển rất nhanh của công nghệ mạng máy tính đặc biệt là mạng

INTERNET thi Khoi lượng thông tin ngày càng chuyển tải nhiều hơn Những tập đoàn công nghiệp, những công ty đa quốc gia, thị trường chứng khoán tiến hành

xử lý và truyền nhận những thông tỉn đất giá, những phiền giao dịch hay mua bán

cỗ phiểu, trải phiêu đều được tiến hành qua mạng (Giờ đây với sự tăng trưởng nhanh của các siêu (hị điện tử, thương mai dién wr thi hang ngày có một khối lượng

Mã hoá thông tin là một trong các phương pháp đán bảo được tính trong suốt

của thông tin Nó có thể giải quyết các vấn rắc rồi ở trến giúp bạn, một khi thông, tin đã được mã hoá và gửi đi thì kẻ xấu rất khó hoặc không thẻ giải mã được

Với mong muốn phục vụ những thông tin được truyền đi trên mạng được nguyên vẹn, trong cuốn luận văn này em nghiên cứu một số khái niệm cơ bản về

mã hoá thông tin, phương pháp mã hoá thông tin RSA Trong bài viết này nhóm

chọn hệ mã hóa rsa để tìm hiểu và mô phỏng hệ mã hóa trên Matlab

Tìm hiểu và mô phỏng thuật giải RSA trên matlab Trang v

Quyết định giao đề tài

Nhận xét của giáo viên hướng dẫn

Nhận xét của giáo viên phản biện

Lời nói đầu

1.2.1 Mô hình mã hóa khối

1.2.1.1 Mô hình dây chuyên khối mã hóa

1.2.1.2 Thể hiện các bước trong đây truyền khối mã hoá

1.2.1.3 Mô hình mã hóa với thông tin phản hồi 1.2.2 Mô hình mã hóa dòng

1.3 Phương pháp mã hóa đối xứng

1.3.3 Nhược điểm của mã hóa đối xứng

1.4 Mã hóa công khai

1.4.1 Phân biệt mã hóa bí mật và mã hóa công khai

1.4.2 Cơ sở lý thuyết cho mã hóa công khai

Chương 2 : Thuật giải RSA

2.1.Giới thiệu về hệ mật mã khóa công khai

Tìm hiểu và mô phỏng thuật giải RSA trên matlab Trang vi

2.4.Lý thuyết số học

2.4.1.Số học đồng đư

2.4.1.1.Khái niệm modulo

2.4.1.2.Phần tử nghịch đảo theo modulo n

3.3.4.1.Phân phối khóa

3.3.4.2.Tấn công dựa vào thời gian

3.3.4.3 Bẻ khóa dựa trên các tấn công lặp lại

Chương 4: Mô phỏng thuật toán RSA dùng Matlab

4.1.Giới thiệu

4.2.Các lệnh thông dụng trong matlab

4.2.1.Một vài kiểu dữ liệu

4.2.2.Các lệnh điều khiển cơ bản

Tìm hiểu và mô phỏng thuật giải ÑSA trên matlab Trang vii

4.2.4.3.Tóan tử logic .46 4.2.4.4.Kí tự đặc biệt 47

Tìm hiểu và mô phỏng thuật giải RSA trên matlab Trang viii

LIỆT KÊ HÌNH

Hình 1.1 Mô hình trao đổi thông tin qua mạng theo cách thông thường

Hình 1.2 Mô hình trao đổi thông tin theo phương pháp mã hóa

Hình 1.3 Sơ đồ mô hình dây chuyển khối mã hoá

Hình 1.4 Mã hoá dòng

Hình 1.5 Mô hình mã hóa đối xứng,

Hình 1,6 Mã hóa bí mật

Hình 1.7 Mô hình mã hóa công khaí

Hình 2.1 Mô hình sử dụng của các hệ mã khóa công khái

Hình 2.2, Ño để của quá trình

Hình 11 Mà hình chữ kí điện tử

Hinh 4.1 Luu đồ giải thật

Ninh 4.3 Lưu đỗ tạo khóa

Ninh 4.3 Lưu đồ mã hóa

Hình 4.4 Lưu đồ giải mã

Hình 4.5 Giao diện khởi đầu chương trình mô phỏng

Hình 4.6 Giao điện chương trình mô phỏng khi mã hóa

Hình 4.7 Giao diện chương trình mô phỏng khi giải mã

Phan A : Giới thiệu

Tìm hiểu và mô phỏng thuật giải RSA trên matlab Trang II

Chương 1

TONG QUAN VE MAT MA VA MA HOA

1.1.Giới thiệu

Trong mọi lĩnh vực kinh tế, chính trị, xã hội, quân sự luôn có nhu cầu trao đổi

thông tin giữa các cá nhân, các công ty, tổ chức, hoặc giữa các quốc gia với nhau

Ngày nay, với sự phát triển của công nghệ thông tin đặt biệt là mạng internet thì

việc truyền tải thông tin dã dễ dàng và nhanh chóng hơn

Hình 1.1 Mô hình trao đổi thong tin qua mang theo cdch thong thuéng

Và vấn đề đặt ra là tính bảo mật trong quá trình truyển tải thông tin, đặt biệt

quan trọng đối với những thông tỉn liên quan đến chính trị, quân sự, hợp đồng kinh

tế Vì vậy nghành khoa học nghiên cứu về mã hóa thong tin được phát triển Việc

mã hóa là làm cho thông tin biến sang một dạng khác khi đó chỉ có bên gửi và bên

nhận mới đọc được, còn người ngoài dù nhận được thông tin nhưng cũng không thể

hiểu được nôi dung

Người A tạo Người B nhận thông

| sathôngtn tin từ người A | ”

aa Mã hóa thông Nhân va giải CÀ

tin của người mã thông tin

‘Ava gti di của người A

Tìm hiểu và mô phỏng thuật giải RSA trên matlab Trang 12

Như chúng ta thấy ở mô hình 1.1: Việc trao déi thông tin được thực hiện qua

các bước sau:

- _ Tạo ra thông tin cần gửi đi

-_ Gửi thông tin này cho đối tác

Ở mô hình 1.2: Việc trao đổi thông tin được thực hiện:

+ Tao thong tin cần gửi

+ M8 hỏa và gửi thông tin đã được mã hóa đi

-_ ĐI tác nhận và giải mã thông tín

Đi tác có được thông tin ban đâu của người gửi,

Vài 3 thao tác mã hóa và giải mã ta đã đảm báo thóng tín được gửi an toàn và vhnh xác,

Chúng ta có nhiều phương pháp để mã hóa thông tín: Ở đáy ta tim hiểu về hệ mã

hóa công khai RSA

1.1.1 Mã hóa là gì ?

Mã hóa là phương thức biến đổi thông tin từ định dạng thông thường thành một

dạng khác (mã hóa) không giống như ban đầu nhưng có thẻ khôi phục lại được (giải

mầ)

1.1.2 Mục đích

+ Đảm bảo tính bảo mật của thông tin khi chúng được truyền trong những môi

trường có độ an toàn không cao

* Trong quá trình mã hóa thông tin có sử dụng một giá trị đặc biệt gọi là khóa

Tìm hiểu và mô phỏng thuật giải RSA trên matlab Trang 13

Mã hoá sử dụng các thuật toán khối gọi đó là mã hoá khối, thông thường kích thước của khối là 64 bits Một số thuật t oán mã hoá khối sẽ được trình bày sau

đây

1.2.1.1 Mô hình dây truyền khối mã hoá

Dây truyền sử dụng kỹ thuật thông tin phản hồi, bởi vì kết quả của khối mã hoá

trước lại đưa vào khối mã hoá hiện thời Nói một cách khác khối trước đó sử dụng

để sửa đổi sự mã hoá của khối tiếp theo, Mỗi khối mã hoá không phụ thuộc hoàn toàn vào khối của bản rô

Trong đây nuyền khoi ma hod (Cipher Block Chaining Mode), ban rõ đã được

XOI với khải mã hoá kế uước đó trước khí nó được mã hoá

1.3.1.2 Thể hiện các bước trong đây truyền khối mã hoá

Sau khi khối bản rõ được mã hoá, kết quả của sự mã hoá được lưu trữ trong thanh ghi thông tin pảhn hồi Trước khi khối tiếp theo của b án rõ đ ược mã hoá, nó

sẽ XOR với thanh ghi thông tin phản hồi để trở t hành đšu vảo cho tuyến mã hoá

tiếp theo Kết quả của sự mã hoá tiếp tục được lưu trữ trong thanh ghi thông tin

phản hồi, và tiếp tục XOR với khối bản rõ tiếp theo, tiếp tục như vậy cho tới kết

thúc thông báo Sự mã hoá của mỗi khối phụ thuộc vào tất cả các khối trước đó

Chương 1: Tông quan vê mật mã và mã hóa

Tìm hiểu và mô phỏng thuật giải RSA trên matlab Trang _ 14

Hình 1.3 Sơ đồ mô hình dây chuyển ki mã huá „

Sự giải mã là cân đối rõ ràng Một khối mã hoá giải mã bình thường và mặt

khác được cất giữ trong thanh ghi thông tin phản hồi Sau khi khối tiếp theo được

giải mã nó XOR với kết quả của thanh ghi phản hồi Như vậy khối mã hoá tiếp

theo được lưa trữ trong thanh ghi thông tin phản hồi, tiếp tục như vậy cho tới khi

kết thúc thông báo

Công thức toán học của quá trình trên như sau :

Ci = EK(Pi XOR Ci-1)

Pi=Ci-l XOR DK(Ci)

1.2.1.3 Mô hình mã hoá với thông tin phản hồi

Chương 1: Tổng quan về mật mã và mã hóa

Tìm hiểu và mô phỏng thuật giải RS4 trên matlab Trang lỗ

Trong mô hình dây truyền khối mã hoá(CBC Cipher Block Chaining

Mode), sự mã hóa không thẻ bắt đầu cho tới khi hoàn thành nhận được một khối dữ liệu Đây thực sự là vấn đề trong một vài mạng ứng dụng Ví dụ, trong môi trường mạng an toàn, một thiết bị đầu cuối phải truyền mỗi ký tự tới máy trạm như nó đã

được đưa vào Khi dữ liệu phải xử lý như một khúc kích thước byte, thì mô hình

dây truyền khối mã hoá là không thoả đáng

Tại mô hình CFB dữ liệu là được mã hóa trong một đơn vị nhỏ hơn là kích

thước của khối Ví dụ sẽ mã hoá một ký tự ASCII tại một thời điểm (còn gọi là mô

hình 8 bits CER) nhưng không có gì là bất khả kháng về số 8 Bạn có thể mã hoá 1

bịt dữ liệu tại mệt thời điểm, sử dụng thuật toán Í bít CEB

1.3123 Mô hình mã hoá dòng

Ma hoa dong là thuật toán, chuyển đổi bản rõ szzz bản mã là 1 bít tại mỗi thời

điểm Sự thực hiện đơn giản nhất của mã hoá dòng được thế hiện trong hình 4.2

Tìm hiểu và mô phỏng thuật giải RSA trén matlab Trang _ lố

dòng đã được XOR với một dòng bits của bản rõ, p 1, p2, p3, pi, để đưa ra dòng bits mã hoá

ci = pi XOR ki

Tại điểm kết thúc của sự giải mã, các bits mã hoá được XOR với khoá dòng để

trả lại các bits bản rõ

pi=ci XOR ki

Từ lúc pi XOR ki XOR kị = pi là một công việc ti mi

Độ an toàn của hệ thống phụ thuộc hoàn toàn vào bên trong bộ sinh khoá dong

Nếu đầu ra bộ sinh kho á dòng vO §t n bang 0, thì khí đó bản rõ bằng bản mã và cả

quả trình hoạt động sé là vô dụng, Nếu bộ sinh khoá dong sinh ra sự lặp lai 16 bits

thần, thì thuật toàn sẽ là đơn giản với độ an toàn không đáng kể

Nếu bộ sinh khoá dòng là vô tận của dòng ngẫu nhiên các bits, bạn sẽ có một

vũng đệm (one tỉme -pad) và độ an toàn tuyệt đối

Thực tế mã hoá dòng nó nằm đâu đó giữa XOR đơn giản và một vùng đệm Bộ

sinh khoá dòng sinh ra một dòng bits ngẫu nhiên, thực tế điều nảy quyết định thuật

toán có thể hoàn thiện tại thời điểm giải mã Đẫu ra của 5ó sinh khoá dòng là ngẫu

nhiên, như vậy người phân tích mã sẽ khó khăn hơn khí

bẻ gãy khoá Như bạn đã đoán ra được rằng, tạo một bộ sinh khoá dòng mà sản

phẩm đầu ra ngẫu nhiên là một vấn đề không dễ dàng

1.3 Phương pháp mã hóa đối xứng

1.3.1 Khái niệm

Phương pháp mã hóa đối xứng là phương pháp mã hóa mà bên gửi và bên nhận

tin cùng sử dụng chung 1 khóa ,hệ thống tạo ra một khóa chung mã hóa và giải

mã đều dùng một khóa chung đó

* Đây là kỹ thuật mã hóa duy nhất trước 1970 và hiện rất phổ biến

+ Còn gọi là mã hóa khóa riêng, khóa bí mật

“Thuật toán đối xứng hay còn gọi thuật toán mã hoá cổ điển là thuật toán mà tại

đó khoá mã hoá có thể tính toán ra được từ khoá giải mã Trong rất nhiều trường

Chương 1: Tổng quan về mật mã và mã hóa

Tìm hiểu và mô phỏng thuật giải RSA trên matlab Trang l7

hợp, khoá mã hoá và khoá giải mã là giống nhau Thuật toán này còn có nhiều tên

gọi khác như thuật toán khoá bí mật, thuật toán khoá đơn giản, thuật toán một khoá Thuật toán này yêu cầu người gửi và người nhận phải thoả thuận một khoá trước khi thông báo được gửi đi, và khoá này phải được cắt giữ bí mật Độ an toàn

của thuật toán này vẫn phụ thuộc và khoá, nếu để lộ ra khoá này nghĩa là bất kỳ

người nào cũng có thể mã hoá và giải mã thông báo trong hệ thống mã hoá

Có 3 hệ mâ hóa đổi xứng hiện nay được dùng phổ biến đó là:

* DES (Data Encryption Standard)

DES (Data Encryption Standard 3)

* ALS (Advanced Encryption Standard)

1.5 Mô hình mã hóa đối xứng

1.3.2 Ưu điểm của mã hóa đối xứng

+ Mô hình khá đơn giản

* Dễ đàng tạo ra thuật toán mã hóa đối xứng cho cá nhân,

Tìm hiểu và mô phỏng thudt gidi RSA trén matlab Trang 18

+ Dé cai dat va hoat dong hiệu quả

* Hoạt động nhanh và hiệu quả do tốc độ mã hoá và giải mã cao

+ => Được sử dụng khá phổ biến nhiều hiện nay

1.3.3 Nhược điểm của mã hóa đối xứng

* Cae phương mã hoá cỏ điển đòi hỏi người mã hoá và người giải mã phải cùng

chung một khoá Khi đó khoá phải được giữ bí mật tuyệt đối, do vậy ta dễ dàng xác

định một khoá nêu biết khoá kia

« - Hệ mã hoá đối xứng không bảo vệ được sự an toàn nếu có xác suất cao khoá

người gửi bị lệ Trong hệ khoá phái được gửi đi trên kênh an toàn nếu kẻ địch tắn

công trên kênh này có thể phát hiện ra khoá

* VẤn để quản ý và phân phối khoá là khó khán vá phức tạp khi sử dụng hệ mã

hoa cả điện Người gửi và người nhận luôn luôn thống nhất với nhau về vấn đề khoa, Việc thay đổi k hoá là rất khó và để bị lộ

+ khuynh hướng cung cấp khoá dài mà nó phải được thay đổi thường xuyên cho

mọi nạ ười trong khí vẫn duy trì cả tính an to àn lẫn h iéu quả chỉ phí sẽ cản trở rất

nhiều tới việc phát triển hệ mật mã cổ điền

1.4 Hệ mã hóa công khai

1.4.1 Phân biệt mã hóa bí mật và mã hóa công khai

Mã hóa bí mật: thông tin sẻ được mã hóa theo một phương pháp ứng với một

key, key này dùng để lập mã và đồng thời cũng để giải mã Vì vậy key phải được giữ bí mật, chỉ có người lập mã và người nhận biết được, nếu key bị lộ thì người

ngoài sẽ dễ dàng giải mã và đọc được thông tin

Tìm hiển và mô phỏng thuật giải RSA trên matlab Ũ Trang _ 19

Public key: Được sử dụng để mã hoá những thông tin mà ta muốn chia sẻ với

bắt cứ ai Chính vì vậy ta có thể tự do phân phát nó cho bắt cứ ai mà ta cần chia sẻ

thông tin ở dạng mã hoá

Privite key: Đúng như cái tên, Key này thuộc sở hữu riêng tư của bạn(ứng

với public key) và nó được sử dụng đề giải mã thông tin Chỉ mình bạn sở hữu nó,

Key nay không được phép và không lên phân phát cho bắt cứ ai

Nghĩa là mỗi người sẽ giữ 2 key 1 dùng để mã hóa, key này được công bố rộng

rãi, | ding đẻ giải mã, key này giữ kín

Khí ai đó có nhụ cầu trao đối thông tin với bạn, sé ding public key mà bạn công,

hố để mã hóa thông tín và gửi chớ bạn, khí nhận được bạn dùng private key để giải

mã, Những người khác dù có nhận được thông tin nhưng không biết được private

key thị cũng kháng the giải mã và đọc được thóng tín

Public-key người nhận

Bantin rd —— Bản tín mật ~~

1.7.Mô hình mã hóa công khai

1.4.2.Cơ sờ lý thuyết cho hình thức mã hóa công khai

Hàm một phía

Một hàm một phía là hàm mà dễ dàng tính toán ra quan hệ một chiều nhưng rất

khó để tính ngược lại Ví như : biết giả thiết x thì có thể dé dàng tính ra f(x), nhưng nếu biết f{x) thì rắt khó tính ra được x Trong trường hợp này “khó” có nghĩa là

để tính ra được kết quả thì phải mắt hàng triệu năm dé tinh toán, thậm chí tất cả máy

tính trên thế giới này đều tính toán công việc đó

Vậy thì hàm một phía tốt ở những gì ? Chúng ta không thể sử dụng chúng cho

sự mã hoá Một thông báo mã hoá với hàm một phía là không hữu ích, bất kỳ ai

Chương I: Tông quan về mật mã và mã hóa

Tìm hiểu và mô phông thuật giải RSA trên mailab Trang — 20

cũng không giải mã được Đối với mã hoá chúng ta cần một vài điều gọi là cửa

sập hàm một phía.(khóa)

Hộp thư là một ví dụ rất tuyệt về hàm một phía cũng như hình thức mã hóa này Bat kỳ ai cũng có thể bỏ thư vào thùng Bỏ thư vào thùng là một hành động công cộng Mở thùng thư không phải là hành động công cộng Nó là việc khó

khăn, khi bạn không có chìa khóa ứng với thùng thư Hơn nữa nếu bạn có điều bí

mật (chìa khoá), nó thật dễ dàng mở hộp thư Hệ mã hoá công khai có rất nhiều

điều giống như vậy

Chương 1: Tổng quan về mật mã và mã hóa

PHAN B

NOI DUNG

Tìm hiểu và mô phỏng thuật giải RSA trên matlab Trang 21

Chuong 2

THUAT GIAI RSA

2,1 Giới thiệu hệ mật mã khóa công khai

Vào năm 1976 Whitefile Deffie và Martin Hellman đưa ra ý tưởng xây dựng

một hệ mật mã mới trên cơ sở hoàn toàn khác các hệ mật mã trước đây Hệ mật mã

này dùng thuật toán mã hóa khác biệt so với thuật toán đối xứng, thỏa các yêu cầu

sau:

Khóa mã hỏa không đối xứng với khóa giải mã nghĩa là dùng một khóa để mã

hóa, dùng khóa khác để giải mã Hai khóa này độc lập và khác biệt nhau

3,3, Mô tả tổng quát các thuật toán không đối xứng

Nguyên tắc hoạt động của các hệ mã lá mỗi bén tham gia truyền tin sẽ có 2

khóa, irệt khaa gọi là khóa bí mật và một khóa cứng khai Khóa bí mật là khóa

hệ thã (e¿) ngày nay chúng ta có thể thấy rõ nguyn tác náy trong việc gửi email,

mọi người đều có thể gửi email tới một địa chỉ email náo đó, nhưng chỉ có người sở

hữu của địa chỉ email đó mới có thể đọc được nội đụng của bức thư, còn những

người khác thì không Với các hệ mã khóa công khai việc phán phôi khóa sẽ trở nên

dễ dàng hơn qua các kênh cung cấp khóa công cộng, số lượng khóa hệ thống quản

lý cũng sẽ ít hơn Các dịch vụ mới như chữ ký điện tử, thỏa thuận khóa cũng được xây dựng dựa trên các hệ mã này

Các yêu cầu của loại hệ mã này:

e _ Việc sinh cặp khóa công khai e„ và bí mật dự, phải được thực hiện một

cách dễ dàng

Người gửi A có khóa công khai của người nhận B khi muốn gửi thông điệp M

thì cần dùng khóa công khai ey của B để mã hóa bản rõ P thành bản mã C

« _ Tiến trình mã hóa thực hiện trong thời gian đa thức

ø„(P) =€

Người nhận B khi nhận được thông điệp đã được mã hóa C, dùng khóa bi mat dy

cảu mình để giải mã thông điệp C thu được thông điệp ban đầu P

« Tiến trình giải mã được thực hiện trong thời gian đa thức

Chương 2: Thuật giải RSA

Tìm hiểu và mô phỏng thuật gidi RSA trén matlab Trang 22

d,(c) = d,(e,(P)) =P

© Néu biétn khóa công khai e, thi viée tinh ton dé dò tìm khóa bí mật

d, không thể thực hiện trong thời gian đa thức, không khả thi về thời

gian

œ Nếu biết được cặp (ey, C) thì không tìm được lời giải để khôi phục

bản rõ P, bài toán khó với số phép thử là vô cùng lớn, không khả thi

® Lượt đồ chữ ký số: tạo chữ ký số có tính chất như chữ ký tay và khó

giả mạo hơn chữa ký tay,

Khóa công [Khoa bi

Hình 2.1: mô hình sử dụng của các hệ mã ÈÈ4a cúng khai

2.3 Nguyên tắc cấu tạo của hệ mã khóa công khai

Các hệ mã khóa công khai được xây dựng dựa trên các hàm được gọi là các hàm

1 phía hay hàm 1 chiều (one — way functions)

Hàm một chiều ƒ:# - Y là một hàm nếu biết x e X ta có thể dễ dàng tính được

y = f (x) Nhung voi y bắt kỳ e Y việc tìm x eX sao cho x = y"!(y) là khó Có nghĩa là tìm hàm ngược ƒ "` là rất khó

“pe” nghĩa là tính được trong thời gian đa thức, “khó” là không tính được trong

thời gian đa thức

Ví dụ nếu có các số nguyên tố P, P; , F„ thì việc tính rt = Pạ x P„» .* P„ là

dễ nhưng nếu có N thì việc tính ngược lại là một bài toán khó với N lớn

Để thuận tiện các hàm một phía được sử dụng trong các hệ mã khóa công khai thường được trang bị các cửa bẫy (trapdoor) hàm ƒ[%) được gọi là hàm cửa sập một

Chương 2: Thuật giải RS4

Tìm hiểu và mô phỏng thuật giải RSA trên matlab _—_- Trang 23

chiều, nếu tính y=f() là dễ, tính x = ƒ ~ˆ(v) là rất khó, nhưng có cửa sập z để tính x=£ 1Q) là dễ

Ngày nay, việc dùng các hệ mật mã để mã hóa thông tin đảm bảo an toàn thông,

tin trong quá trình trao đổi thông tin khá phổ biến Đặc biệt là hệ mã RSA

2.4 Lý thuyết số

2.4.1 Số học đồng dư

Với mỗi cặp sổ œ b €Z cho trước, b % 0, tồn tại cặp số nguyên q, r thỏa

6 & cm khi đỏ q là phẩn nguyên, r là phần dư Nếu z = 0, thì phép chia là

phép: chía hết

DALAL Khai nig

Dink nghia: cho a, b,n € Z, n> 0, a goi la dong du vdi b theo modulo n nếu

phần dư của a chia m bằng phần dư của b chia n

Ky hiệu: a = b mod mn nếu n chia hết cho b-a

Mệnh đề a = b mod n được gọi là a đồng dư với b theo modulo n,

Ví dụ: 9 = 5 mod 2

Các tính chất của modulo

ia =amodn

ii, Néu a = bmod nvab =c mod nthia=cmodn

iii Néu a = bmod n,c =d mod nthiat+c b+dmodn

Vaa.c=b.dmod n

2.4.1.2 Phần tử nghịch đảo theo modulo n

Định nghĩa: giả sử a 6 Z„ Phần từ nghịch đảo của a mod n là a“ € Z, sao

1=a"la = 1modn

cho aa~

Dinh Ij: nghịch đảo œ~1 của a theo modulo n tồn tại và duy nhất nếu và chỉ nếu

a nguyên tố cùng nhau với n

Chứng mình:

Chương 2: Thuật giải RSA

Tìm hiểu và mô phỏng thuật giải RSA trên matlab Trang 24 Nếu øø *= 1modm, thì azđ1=1+km ©aa 1—km=1=>a và m

nguyên tố cùng nhau,

aa” + km = 1 => øa"! = 1—km, do đó aa"! = 1mod m

Ñồ nguyên tô có vai trò và ý nghĩa to lớn trong số học và mật mã học

NỔ ngà ên tô củng nhau: cho a,b € NW, a, b 14 hái số nguyên tố cùng nhau nếu

chúng cô dạy nhất một ước chung là 1

2.4.3 Ham Euler

Định nghia: cho n € N, số lượng các số tự nhiền bé hơn n và nguyên tố cùng

nhau với n được ký hiệu là (Œn) ø được gọi là hàm Euler,

Ví dụ: ø(5) =4= {1,2, 3,4), ø(6)=2= {1,5}, gŒ) =6= {1,2,3, 4, 5,6) Nhận xét: khi p là số nguyên tố thì Y x € N đều là nguyên tố cùng nhau với p,

Chứng minh: tập tắt cả cdc thang du mod n là {0, 1, 2, 3, 4, 5, pq-1}chỉ có

duy nhất những thặng dư không có nguyên tố cùng nhau với n là: p, 2p, 3p, Áp, .,

Tìm hiểu và mô phỏng thuật giải RSA trén matlab Trang 25

=(@-1)(—1)

= 0Œ) ø(q) (đem)

2.4.4.Ước số chung lớn nhất

Hai số gọi là cặp số nguyên tố khi mà chúng khôn g có thừa số chung

nàokhác 1, hay nói một cách khác, nếu ước số chung lớn nhất của a và n là bằng1

Chúng ta có thể viết như sau:

gcd(a,n)=L

SỐ 15 và 2 là một vập số nguyên tố, nhưng 15 và 27 thì không phải cặp

sốnguyên tỐ đo cô ước số chúng là | và 3, Ế dáng thấy 13 và 500 cũng là một cặp

sổ nguyên i Mot sd nguyên tố là một cập số nguyên tố với tắt cả những số khác loại tù những số là bội số

Một cách dễ nhất để tính toán ra ước số chung lớn nhất của hai số là nhờ vào

thuật toán Euclid, Knuth mô tả thuật toán và một vàí mô hình của thuật toán đã được sửa đổi

Dưới đây là đoạn mã nguồn trong ngôn ngữ C

/* Thuật toán tìm ước số chung lớn nhất của x và y, giả sử x.y>0 */

int ged(int x, int y)

với điều kiện là cả x và k đều là số nguyên

Van dé chung dat ra tai day 1a tim x sao cho

1=(a*x) modn

có thể viết lại như sau :

a’! =x(modn)

Sự thu nhỏ vấn đề Modulo là rất khó giải quyết Đôi khi nó là một vấn đề,

nhưng đôi khi hi không phải vay

Ví dụ : nghịch đảo của 5 modulo 14 là 3 bởi

5x3 = 151 (mod 14)

“Trong trường hợp chung a! =x (mod n) chỉ có duy nhất một giải pháp nếu a

và n là một cặp số nguyên tố Nếu a và n không phải là cặp số nguyên tố, thì

Chương 2: Thuật giải RSA

Tìm hiểu và mô phỏng thuật giải RSA trén matlab Trang 27

a’ = x (mod n) không có giải pháp nào Thuật toán Euclid có thể tính ra

được số nghịch đảo của số Modulo n, đôi khi thuật toán này còn gọi là thuật toán

Euclid mở rộng

2.4.6 Định lý phần dư trung hoa

Nếu bạn biết cách tìm thừa số nguyên tố của một số n, thì bạn có thể đã sử dụng,

một số điều gọi là dịnh lý phần dư trung hoa để giải quyết trong suốt hệ ph ương trình Bản dịch cơ b ản của định lý này được khám phá b di to án học Trung Hoa

vào thế kỷ thử nhất

GIÁ sử, sự phân tích thừa số của n=pJzp2⁄, “pL thì hệ phương trình

(X map) <= Ai, với l2,

vỏ duy nhất một cách giải, tại đó x nhỏ hơn n

Bởi vậy, với a,b tuỳ ý sao cho a < p và b <q (p,q la số nguyên tố) thì tồn tại duy

nhất a,x ,khi x nhỏ hơn pxq thì

2.4.7 Các phép kiểm tra số nguyên tố

Hàm một phía là một khái niệm cơ bản của mã hoá công khai, việc nhân hai

số nguyên tố được phỏng đoán như là hàm một phía, nó rất dễ dàng nhân các số để tạo ra một số lớn, nhưng rất khó khăn để phân tích số lớn đó ra thành các thừa số là hai số nguyên tố lớn

Chương 2: Thuật giải RSA

Tìm hiểu và mô phỏng thuật giải RSA trên matlab Trang 28

Thuật toán mã hoá công khai cần thiết tới những số nguyên tố Bất kỳ mạng kích

thước thế nào cũng cần một số lượng lớn số nguyên tố Có một vài phương pháp để

sinh ra số nguyên tố Tuy nhiên có một số vấn để được đặt ra đối với số nguyên tố

như sau :

+ _ Nếu mọi người cần đến những số nguyên tố khác nhau, chúng ta sẽ không đạt

được điều đó đúng không Không đúng, bởi vì trong thực tế có tới 10!'' số nguyên

tố có độ dài 512 bits hoặc nhỏ hơn

+ Điều gì sẽ xảy ra nếu có hai người ngẫu nhiên chọn cùng một số nguyên tố? Với

sự chọn lựa từ sẽ lượng 10”” số nguyên tố, điều kỳ quặc này xảy ra là xác xuất nhỏ hơn so với sự tự bắc cháy của máy tính, Vậy n ó không có gì là đáng lo ngại cho

bạn hết 'Erong bài này chúng tạ chỉ tìm hiểu phép kiếm tra số nguyên tố của Rabin-

miller

> Rabina-Miller

thuật toán nay duge phat trién boi Rabin, dua wén mot phan ý tưởng của

Miller, Thực tế những phiên bản của thuật toán đã được giới thiệu tại NIST

(National Institute of Standards and Technology)

Đầu tiên là chọn ngẫu nhiên một số p để kiểm tra Tính b, với b lả số mũ của

2 chia cho p-1 Tiếp theo tính m tương tự như n = 1+2°m

Sau đây là thuật toán :

1 Chọn một sô ngẫu nhiên a, và giả sử a nhỏ hơn p

2 Dat j=0 va z=a™ mod p

3 Nếu z=1, hoặc z=p-l thi pda qua hước kiểm tra và có thể là số

nguyên 6

4 Néuj> 0 va z=1 thi p kh6ng phai la số nguyên tố

5 Đặtj = j+1 Nếu j < b và z # p-l thì đặt z=z? mod p và trở lại bước 4

6 Nếu j =b và z # p-1, thì p không phải là số nguyên tố

2.5 Hệ mật mã khóa công khai RSA

Chương 2: Thuật giải RSA

Tìm hiểu và mô phỏng thuật giải RSA trên mallab Trang 20

2.5.1 Giới thiệu

RSA là hệ mật mã khóa công khai được phát minh bởi Ron Rivest, Adi Shamir

va Len Adleman, được

công bố năm 1977, RSA được dùng bởi các web server và browser để bảo mật

đữ liệu trên đường truyền, đảm bảo tính riêng tư và xác thực của email, đảm bảo

phiên đăng nhập truy cập từ xa

RSA dap ứng đầy đủ nhu cầu bảo mật thông tin nên được triển khai nhiều trong,

hệ thống thương mại, thanh toáo bằng thẻ điện tử

Trude do, nam 1973, Clifford Cock nha to4n học người Anh làm việc tại

GCHO, đã mô tả một thuật toán tương tự, Tuy nhiên, tại thời điểm đó thì thuật toán khong kha thi và chưa được thực nghiệm Phát mình nay chỉ được công bố vào năm

1997 vị được Xếp vào loại tuyệt mật

Thuát toàn RSA được MIT đăng ký sáng chế tại H124 Ký nám 1983 (số đăng ky

4,408,829) Bang sang chế này hết hạn vào ngày 21 thang 9 năm 2000 Tuy nhiên

do thuật toán đã được công bố trước khi có đăng ký b42 hộ nén sự bảo hộ hầu như không có giá trị bên ngoài Hoa Kỳ Ngoài ra, nếu cózø trinh của Clifford Cock

được công bố trước đó thì bằng sáng chế RSA không được đáng kí

Hiện tại, RSA là trái tim của hệ thống thương mại điện tử vả thanh toán điện tử

đảm bảo tính riêng tư và xác thực dữ liệu số Để đảm bảo an toàn thông tỉn trong

quá trình trao đổi thông tin trên mạng thì sử dụng hệ mật mã RSA là giải pháp tốt

và an toàn nhất hiện nay

2.5.2 Mô tả thuật toán

Để cài đặt RSA ban đầu mỗi người sinh khóa công khai và khóa bí mật của

mình bằng cách:

e_ Chọn hai số nguyên tố lớn ngẫu nhiên (cỡ gần 100 chữ số) khác nhau

p và q kiểm tra p và q có phải là số nguyên tố hay không bằng định lý

miller-rabin test

'Với p là số nguyên tố, a là một số nguyên thì:

aŒ~® = 1 (mod p) (định lý fermat nhỏ)

Tìm hiểu và mô phỏng thuật giải RSA trén matlab Trang 30

ø(Œ) =(p—1)(q@— 1) Chọn ngẫu nhiên khóa mã hóa e bé hơn ø(), với điều kiện

gcd(e,ø) = 1

Có nghĩa là e và ø(n) có ước chung lớn nhất là 1

Tìm khóa bí mật d theo công thức

'Thể lần lượt ¡ từ 0 đến n-1 đến khi nào phép chía cho kết quả là số

nguyên thì kết quả là số nguyên đầu tiến đó chính là khóa bí mật

(khóa giải mã đ) cần tìm Kết quả khóa cóng khaí là (e, n), khóa bí

mật là (d, n)

Việc thiết lập khóa này được thực hiện 1 lẫn khi một người dùng thiết lập (thay thế) khóa công khai của họ Mũ e thường là khá nhỏ (để tính nhanh), và phải

là số nguyên tố cùng nhau với y(n) Các giá trị thường được chọn cho e là 3 hoặc

216 _ 4 = 65535 Tuy nhiên khi e càng, nhỏ thì d sẽ tương đối lớn khóa bí mật là

(d, n) Các số p và q thường có giá trị xấp xỉ nhau nhưng không được bằng nhau

Chú ý là việc để lộ một trong các thành phần trên sẽ làm cho hệ thống trở nên

Tìm hiểu và mô phỏng thuật giải RSA trên matlab Trang 3]

Chuyển P về dạng ký tự để được thông điệp ban đầu

® - Thuật toán RSA làm việc được bởi vì nó dựa trên cơ sở toán học là sự

tổng quát định lý Fermat nhé a®- = 1 (mod p) trong thuật toán

RSA ta chọn e và d nghịch đảo nhau trên vành Z„¿„y với e được chọn

trước

Đo đó chúng ta sẽ có e.d = 1 (mod @(r)), suy ra:

P=Ct = Pet = PhO = p.(p?())* = P (mod n)

Vie.d = 1 (mod ø(n))

bày 6d ~ 1< kợŒn) => e.d =kp(n) +1 => PROM =1