ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC SƯ PHẠM
KHOA TIN HỌC

ĐỒ ÁN MÔN HỌC
ĐỀ TÀI:
GIẢI THUẬT MÃ HÓA RSA VÀ ỨNG DỤNG TRONG MÃ
HÓA DỮ LIỆU VÀ TẠO CHỮ KÝ ĐIỆN TỬ
Sinh viên thực hiện: Huỳnh Ngọc Nam
Lớp: 11CNTT2
Giảng viên hướng dẫn: TS. Nguyễn Trần Quốc Vinh
Đà Nẵng, 2013
MỤC LỤC
MỞ ĐẦU
Trong mật mã học, RSA là một thuật toán mã hóa khóa công khai. Đây là thuật toán đầu tiên phù
hợp với việc tạo ra chữ ký điện tử đồng thời với việc mã hóa. Nó đánh dấu sự tiến bộ vượt bậc của
lĩnh vực mật mã học trong việc sử dụng khóa công cộng. RSA đang được sử dụng phổ biến trong
thương mại điện tử và được cho là đảm bảo an toàn với điều kiện độ dài khóa đủ lớn.
1. Lý do chọn đề tài:
Thuật toán mã hóa công khai đã ra đời từ rất lâu đời. Nhưng trước những nhu cầu về giao
dịch an toàn trên mạng Internet ngày nay, những ứng dụng của nó ngày càng tỏ rõ tầm quan
trọng. Mà trong đó, thuật toán mã hóa RSA là phổ biến nhất. Nó được sử dụng rộng rãi cho
công nghệ VPN.
Khi mà các ứng dụng CNTT đã và đang ngày càng phổ biến rộng rãi đã ảnh hưởng rất lớn
đến diện mạo của đời sống xã hội, kinh tế. Mọi công việc của chúng ta đều có thể thực hiện
được từ xa với sự hỗ trợ của máy tính và mạng Internet (từ học tập, giao dich,… đến việc gửi
thư). Tất cả các thông tin liên quan đều được máy tính quản lý và truyền đi trên hệ thống
mạng. Đối với những thông tin bình thường thì không có ai chú ý tới, thế nhưng đối với
những thông tin mang tính chất sống còn đối với một cá nhân hay tổ chức thì vấn đề bảo mật
và giữ cho đến đúng địa chỉ cần đến. Rất nhiều phương pháp bảo mật ra đời và trong số đó
phương pháp mã hóa khóa công khai được xem là phương pháp có tính an toàn khá cao. Với

Chương 1: CƠ SỞ LÝ THUYẾT
1. Lịch sử.
2. Tổng quan về mã hóa
3. Mật mã hóa khóa công khai
Chương 2: TỔNG QUAN VÀ HOẠT ĐỘNG
1. Mô tả sơ lược
2. Tạo khóa
3. Mã hóa
4. Giải mã
5. Các định lý cơ sở
6. Ví dụ
7. Tạo chữ ký số
8. Các giải thuật có sử dụng
Chương 3: PHÁT BIỂU BÀI TOÁN
1. Phát biểu bài toán
2. Trình bày thuật toán
Chương 4: KẾT QUẢ VÀ ỨNG DỤNG
1. Kết quả
2. Ứng dụng
KẾT LUẬN
PHỤ LỤC
CHƯƠNG 1 CƠ SỞ LÝ THUYẾT
1. Lịch sử phát triển
Trong mật mã học, RSA là thuật toán đầu tiên phù hợp với việc tạo ra chữ ký điện tử đồng thời với
việc mã hóa. Thuật toán được Ron Rivest, Adi Shamir và Len Adleman mô tả lần đầu tiên tại Học
Viện Công Nghệ Massachusetts (MIT) vào năm 1977. Tên của thuật toán được lấy từ 3 chữ cái đầu
tiên của tên 3 tác giả.
Trước đó, vào năm 1973, Clifford Cocks một nhà toán học người Anh làm việc tại GCHQ, đã mô tả
một thuật toán tương tự. Với khả năng tính toán tại thời điểm đó thì thuật toán này không khả thi và
chưa bao giờ được thực nghiệm. Tuy nhiên, phát minh này chỉ được công bố vào năm 1997 vì được

Trong mật mã hóa khóa công khai, khóa cá nhân phải được giữ bí mật trong khi khóa công khai
được phổ biến công khai. Trong 2 khóa, một dùng để mã hóa và khóa còn lại dùng để giải mã. Điều
quan trọng đối với hệ thống là không thể tìm ra khóa bí mật nếu chỉ biết khóa công khai.
Hệ thống mật mã hóa khóa công khai có thể sử dụng với các mục đích:
Mã hóa: giữ bí mật thông tin và chỉ có người có khóa bí mật mới giải mã được.
Tạo chữ ký số: cho phép kiểm tra một văn bản có phải đã được tạo với một khóa bí mật nào đó hay
không.
Thỏa thuận khóa: cho phép thiết lập khóa dùng để trao đổi thông tin mật giữa 2 bên.
Thông thường, các kỹ thuật mật mã hóa khóa công khai đòi hỏi khối lượng tính toán nhiều hơn các
kỹ thuật mã hóa khóa đối xứng nhưng những lợi điểm mà chúng mang lại khiến cho chúng được áp
dụng trong nhiều ứng dụng.
• Các ứng dụng:
- Ứng dụng rõ ràng nhất của mật mã hóa khóa công khai là bảo mật: một văn bản được mã
hóa bằng khóa công khai của một người sử dụng thì chỉ có thể giải mã với khóa bí mật của
người đó.
- Các thuật toán tạo chữ ký số khóa công khai có thể dùng để nhận thực. Một người sử dụng
có thể mã hóa văn bản với khóa bí mật của mình. Nếu một người khác có thể giải mã với
khóa công khai của người gửi thì có thể tin rằng văn bản thực sự xuất phát từ người gắn
với khóa công khai đó.
- Các đặc điểm trên còn có ích cho nhiều ứng dụng khác như: tiền điện tử, thỏa thuận
khóa
CHƯƠNG 2 TỔNG QUAN VÀ HOẠT ĐỘNG
1. Mô tả sơ lược
- Thuật toán RSA có hai khóa: khóa công khai (hay khóa công cộng) và khóa bí mật (hay khóa
cá nhân). Mỗi khóa là những số cố định sử dụng trong quá trình mã hóa và giải mã. Khóa
công khai được công bố rộng rãi cho mọi người và được dùng để mã hóa. Những thông tin
được mã hóa bằng khóa công khai chỉ có thể được giải mã bằng khóa bí mật tương ứng. Nói
cách khác, mọi người đều có thể mã hóa nhưng chỉ có người biết khóa cá nhân (bí mật) mới
có thể giải mã được.
- Ta có thể mô phỏng trực quan một hệ mật mã khoá công khai như sau: Bob muốn gửi cho

- Dạng này cho phép thực hiện giải mã và ký nhanh hơn với việc sử dụng định lý số dư Trung
Quốc (tiếng Anh: Chinese Remainder Theorem - CRT). Ở dạng này, tất cả thành phần của
khóa bí mật phải được giữ bí mật.
- Alice gửi khóa công khai cho Bob, và giữ bí mật khóa cá nhân của mình. Ở đây, p và q giữ
vai trò rất quan trọng. Chúng là các phân tố của n và cho phép tính d khi biết e. Nếu không sử
dụng dạng sau của khóa bí mật (dạng CRT) thì p và q sẽ được xóa ngay sau khi thực hiện
xong quá trình tạo khóa.
3. Mã hóa
- Giả sử Bob muốn gửi đoạn thông tin M cho Alice. Đầu tiên Bob chuyển M thành một số m <
n theo một hàm có thể đảo ngược (từ m có thể xác định lại M) được thỏa thuận trước.
- Lúc này Bob có m và biết n cũng như e do Alice gửi. Bob sẽ tính c là bản mã hóa của m theo
công thức:
- Hàm trên có thể tính dễ dàng sử dụng phương pháp tính hàm mũ (theo môđun) bằng (thuật
toán bình phương và nhân) Cuối cùng Bob gửi c cho Alice.
4. Giải mã
- Alice nhận c từ Bob và biết khóa bí mật d. Alice có thể tìm được m từ c theo công thức sau:
- Biết m, Alice tìm lại M theo phương pháp đã thỏa thuận trước. Quá trình giải mã hoạt động vì
ta có
.
Do e*d ≡ 1 (mod p-1) và e*d ≡ 1 (mod q-1), (Theo Định lý Fermat nhỏ) nên:
và
Do p và q là hai số nguyên tố cùng nhau, áp dụng định lý số dư Trung Quốc, ta có:
hay: .
5. Các định lý cơ sở
5.1 Định lý nhỏ của Fermat
- Định lý nhỏ của Fermat (hay định lý Fermat nhỏ - phân biệt với định lý Fermat lớn) khẳng
định rằng nếu p là một số nguyên tố, thì với số nguyên a bất kỳ, a
p
– a sẽ chia hết cho p.
Nghĩa là:

p = 61 — số nguyên tố thứ nhất (giữ bí mật hoặc hủy sau khi tạo khóa)
q = 53 — số nguyên tố thứ hai (giữ bí mật hoặc hủy sau khi tạo khóa)
n = pq = 3233 — môđun (công bố công khai)
e = 17 — số mũ công khai
d = 2753 — số mũ bí mật
Khóa công khai là cặp (e, n). Khóa bí mật là d. Hàm mã hóa là:
encrypt(m) = mod n = mod 3233
với m là văn bản rõ. Hàm giải mã là:
decrypt(c) = = mod 3233
với c là văn bản mã.
- Để mã hóa văn bản có giá trị 123, ta thực hiện phép tính:
encrypt(123) = mod 3233 = 855
Để giải mã văn bản có giá trị 855, ta thực hiện phép tính:
decrypt(855) = mod 3233 = 123
Cả hai phép tính trên đều có thể được thực hiện hiệu quả nhờ thuật toán bình phương và
nhân.
7. Ứng dụng chữ ký số
- Thuật toán RSA còn được dùng để tạo chữ ký số cho văn bản. Giả sử Alice muốn gửi cho
Bob một văn bản có chữ ký của mình. Để làm việc này, Alice tạo ra một giá trị băm (hash
value) của văn bản cần ký và tính giá trị mũ d mod n của nó (giống như khi Alice thực hiện
giải mã). Giá trị cuối cùng chính là chữ ký điện tử của văn bản đang xét. Khi Bob nhận được
văn bản cùng với chữ ký điện tử, anh ta tính giá trị mũ e mod n của chữ ký đồng thời với việc
tính giá trị băm của văn bản. Nếu 2 giá trị này như nhau thì Bob biết rằng người tạo ra chữ ký
biết khóa bí mật của Alice và văn bản đã không bị thay đổi sau khi ký.
8. Các giải thuật có sử dụng
8.1 Giải thuật Euclid mở rộng
- Giải thuật Euclid mở rộng sử dụng để giải phương trình vô định nguyên (còn được gọi
là phương trình Đi-ô-phăng)
a*x+b*y=c,
trong đó a, b, c là các hệ số nguyên, x, y là các ẩn nhận giá trị nguyên. Điều kiện cần và đủ để

- Thuật toán bình phương và nhân là thuật toán tính nhanh lũy thừa tự nhiên của một số
(thực hoặc nguyên), trong trường hợp cơ số là số nguyên có thể được rút gọn theo
một môđun nào đó.
Phép nâng lên lũy thừa tự nhiên bậc n của số x (x được gọi là cơ số) được định nghĩa từ hệ
thức
Với n lớn số phép nhân là rất lớn.
- Code thuật toán
int binhphuong(int m, int e, int n)
{
int []a = new int[100];
int k = 0;
do
{
a[k] = e % 2;
k++;
e = e / 2;
}
while (e != 0);
int kq = 1;
for (int i = k - 1; i >= 0; i )
{
kq = (kq * kq) % n;
if (a[i] == 1)
kq = (kq * m) % n;
}
return kq;
}
CHƯƠNG 3 PHÁT BIỂU VẤN ĐỀ
1. Phát biểu bài toán
- Một cá nhân (hoặc tổ chức) muốn gửi một thông tin mật cho một cá nhân (hoặc tổ chức) khác

B2. Sau đó ta dùng giải thuật bình phương và nhân để tiến hành tính k = với e và n
đã cho, m chính là giá trị trong bảng mã ACII của ký tự trong chuỗi.
B3. Chuyển k thành chuỗi ký tự kèm công thức cố định c[i] = k+32.
B4. Xuất chuỗi lên TextArea thứ 2. Riêng đối với chữ ký số ta sẽ lấy bảng băm của chuỗi
ký tự, trong eclipse dùng hàm hashcode.
- Đối với cá nhân(hoặc tổ chức) nhận tài liệu, họ sẽ tiến hành giải mã văn bản đã mã hóa
bằng secret key mà họ đã khởi tạo cùng với public key ban đầu theo các bước sau:
B1. Tải văn bản đã mã hóa lên
B2. Tải secret key lên
B3. Tiến hành giải mã
B4. Lưu văn bản sau khi giải mã