Tìm hiểu RSA nguyên thủy

Mục Lục
Mục Lục.........................................................................................................................................................1
Mở đầu..........................................................................................................................................................2
CHƯƠNG 1: CẤU TẠO VÀ HOẠT ĐỘNG CỦA RSA.........................................................................................3
1.1 : Sơ lược về RSA..........................................................................................................................................3
1.2 : Các thuật toán hệ mật mã khóa công khai..............................................................................................3
1.3 : Đánh giá hệ mật mã khóa công khai RSA.................................................................................................6
1.4 : Ứng dụng của RSA vào chữ ký điện tử.....................................................................................................7
CHƯƠNG 2: MÃ HÓA RSA NGUYÊN THỦY...................................................................................................7
2.1 : Phép mã hóa RSA nguyên thủy................................................................................................................7
2.2 : Phép giải mã RSA nguyên thủy.................................................................................................................8
2.3 : Phép ký số RSA nguyên thủy....................................................................................................................9
2.4 : Phép kiểm tra chữ ký RSA nguyên thủy RSAVP........................................................................................9
Chương 3:Xây dựng chương trình.............................................................................................................10
3.1 : Xây dựng chương trình...........................................................................................................................10
3.2 : Một số giao diện của chương trình........................................................................................................11

1


Tìm hiểu RSA nguyên thủy

Mở đầu
Thuật toán mã hóa công khai đã ra đời từ lâu. 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 ngày càng quan
trọng. Một trong những thuật toán mã hóa khóa công khai phổ biến đó là RSA.
Trong quá trình học nhóm em đã chọn đề tài “ tìm hiểu RSA nguyên thủy ”.
Với khoảng thời gian không nhiều nhưng với sự nỗ lực của bản thân và sự hướng
dẫn tận tình của thầy giáo, nhóm em đã hoàn thành đề tài. Tuy nhiên do thời gian

còn hạn chế nên phạm vi nghiên cứu và chương trình còn nhiều vấn đề chưa giải
quyết được triệt để. Nhóm em mong nhận được sự đóng góp của thầy giáo và các
bạn.Nhóm em xin chân thành cảm ơn thầy giáo!

2


Tìm hiểu RSA nguyên thủy

CHƯƠNG 1: CẤU TẠO VÀ HOẠT ĐỘNG CỦA RSA
1.1 : Sơ lược về RSA
RSA là hệ thống bảo mật khóa công khai cho cả mã hóa và việc xác
nhận, được phát minh vào năm 1977 bởi Ron Rivest và Leonard Adleman.
Được xây dựng trên cơ sở mã mũ trong đó khóa là cặp (e,n), gồm mũ e và
modulo n. Số n là tích hai số nguyên tố lớn nhất nào đó, n=pq, sao cho ( e,
ϕ(n)) = 1, trong đó ϕ(n) là hàm Euler.
Những kỹ thuật đặc trưng sử dụng thao tác toán học thành một văn
bản mã. Những thao này gọi là chức năng một chiều, chức năng tương đối
dễ thực hiện theo một hướng nhưng chuyển đổi theo hướng ngược lại thì khó
hơn nhiều.
Chế độ bảo mật của RSA dựa vào việc phân tích những số rất lớn ra thừa
số nguyên tố.
Bảng tóm tắt quá trình mã hóa RSA.
Khóa chung Khóa riêng
Mã hóa
Giải mã
e
n tích hai số e, nguyên tố cùng c = m mod (p-1)(q- m = cd mod
nguyên tố p,q nhau với (p-1)(q-1) 1)


n

1.2 : Các thuật toán hệ mật mã khóa công khai
1.2.1: thuật toán sinh khóa
Để sử dụng được hệ mật mã khóa công khai RSA, trước tiên mỗi người phải
tạo riêng cho mình một cặp khóa gồm khóa công khai và khóa bí mật. Việc tạo ra
khóa công khai và khóa bí mật thực hiện theo các bước sau:
- Sinh ra 2 số nguyên tố lớn p và q ngẫu nhiên sao cho: (p,q) =1
- Tính n = p*q.
- Ф(n) = (p-1) * (q-1).
3


Tìm hiểu RSA nguyên thủy
- Chọn một số tự nhiên e sao cho 1< e< Ф(n) và là số nguyên tố cùng nhau
với Ф(n).
- Tính d sao cho d*e ≡ 1 ( mod Ф(n)) với 1< d< Ф(n).
Khóa công khai (e,n).
Khóa bí mật ( d).

Hình 1: mô hình hoạt động của RSA
1.2.2 : Thuật toán mã hóa
Hệ RSA là một hệ mật mã điển hình về kiểu mã hóa khối. Nghĩa là, thông
điệp được chia thành nhiều khối (hoặc chuỗi) có chiều dài cố định, và mỗi khối sẽ
được mã hóa riêng. Giả sử để gửi thông điệp bí mật M cho người nhận B trong
nhóm gửi thông tin an toàn, người gửi A phải thực hiện các bước như sau:
- Thu nhận khóa công khai (e,n) của người nhận B.
-

Biểu diễn bản tin dưới dạng một số nguyên m trong khoảng [0,n-1]


- Tính: C = me mod n
- Gửi bản mã C cho A
4


Tìm hiểu RSA nguyên thủy

1.2.3 : Thuật toán 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:
m = cd mod n
Biết m, Alice tìm lại m theo phương pháp đã thảo thuận trước.
cd ≡ (me)d ≡ med ( mod n)
Do ed ≡ 1 ( mod p-1) và ed ≡ 1 ( mod q-1) nên:
med ≡ m ( mod p) và med ≡ m (mod q)
Do p và q là hai số nguyên tố cùng nhau, ta có:
med ≡ m ( mod pq) hay cd ≡ m (mod n)
1.2.4 : Chuyển đổi văn bản rõ
Trước khi thực hiện mã hóa, ta phải thực hiện việc chuyển đổi văn bản rõ
(chuyển đổi từ M sang m) sao cho không có giá trị nào của M tạo ra văn bản mã
không an toàn. Nếu không có quá trình này, RSA sẽ gặp phải một số vấn đề sau:
- Nếu m = 0 hoặc m = 1 sẽ tạo ra các bản mã có giá trị là 0 và 1 tương ứng
- Khi mã hóa với số mũ nhỏ (chẳng hạn e = 3) và m cũng có giá trị nhỏ,
giá trị me cũng nhận giá trị nhỏ (so với n). Như vậy phép môđun không có
tác dụng và có thể dễ dàng tìm được m bằng cách khai căn
bậc e của c (bỏ qua môđun).
- RSA là phương pháp mã hóa xác định (không có thành phần ngẫu nhiên)
nên kẻ tấn công có thể thực hiện tấn công lựa chọn bản rõ bằng cách tạo
ra một bảng tra giữa bản rõ và bản mã. Khi gặp một bản mã, kẻ tấn công

sử dụng bảng tra để tìm ra bản rõ tương ứng.
5


Tìm hiểu RSA nguyên thủy
- Trước khi thực hiện mã hóa, ta phải thực hiện việc chuyển đổi bản rõ
(chuyển từ
M sang mi (i, 0 < i < n) sao cho không có giá trị nào của M tạo ra bản mã
không an toàn.
1.3 : Đánh giá hệ mật mã khóa công khai RSA
1.3.1 : Độ an toàn của RSA
Độ an toàn của RSA được thiết kế dựa trên độ khó giải bài toán phân tích
ra thừa số nguyên tố n = p*q với 2 số nguyên tố bí mật lớn p, q. Nếu ta chọn
các số p, q khoảng 100 chữ số thập phân thì nó sẽ có khoảng 200 chữ số thập
phân. Để phân tích một số nguyên cỡ lớn như thế với các thuật toán nhanh
nhất hiện nay cùng với những máy tính hiện đại nhất cũng mất hàng triệu
năm. Như vậy việc phân tích số nguyên n thành các thừa số nguyên tố p, q
nhằm mục đích bẻ gãy hệ mật mã RSA là điều khó có thể tính toán nổi nếu
như trong quá trình thiết kế hệ RSA ta chọn số nguyên N lớn.
1.3.2 : Hiệu suất thực hiện của thuật toán RSA
Chi phí: Để thực hiện thuật toán RSA phần lớn phải tốn chi phí thực hiện
các phép tính cơ bản như: tạo khoá, mã hoá, giải mã. Quá trình mã hoá và giải mã
tương đương với chi phí thực hiện các phép tính luỹ thừa module n. Để đảm bảo
cho khoá bí mật được an toàn thì thường chọn số mũ công khai e nhỏ hơn nhiều so
với số mũ bí mật d, do đó chi phí thời gian để thực hiện mã hoá dữ liệu nhỏ hơn
nhiều so với thời gian giải mã.
Tốc độ của hệ RSA: Tốc độ của RSA là một trong những điểm yếu của RSA
so với các hệ mã đối xứng, so với hệ mã DES thì RSA chậm hơn từ 100 đến

6



Tìm hiểu RSA nguyên thủy
1000 lần, vì vậy RSA không được dùng để mã hoá khối lượng dữ liệu lớn mà
thường dùng để mã hoá những dữ liệu nhỏ.

1.4 : Ứng dụng của RSA vào chữ ký điện tử
Hệ mã RSA có tính an toàn rất cao. Nhưng nhược điểm lớn là tốc độ mã hóa
chậm. bởi vậy nó chỉ được sử dụng với các văn bản ngắn và thường dùng trong
giao thức xác nhận chủ thể.
Chữ ký điện tử đảm bảo khi người nhận có được mật thư thì biết chắc chắn
ai là tác giả bức thư đó. Và cũng đảm bảo việc không ai có thể mạo danh người
khác để gửi thư.
Chữ kí điện tử và chữ ký tay có chung đặc điểm là rất khó xảy ra trường hợp
trùng.

CHƯƠNG 2: MÃ HÓA RSA NGUYÊN THỦY
2.1 : Phép mã hóa RSA nguyên thủy
RSAEP((n ,e ), m)
Đầu vào : ( n, e) khóa công khai RSA.
m thông báo được biểu diễn là một số nguyên trong khoảng từ 0 đến n −1.
7


Tìm hiểu RSA nguyên thủy
Đầu ra: c bản mã được biểu diễn là một số nguyên trong khoảng từ 0 đến n-1 hoặc
thông báo” biểu diễn thông báo vượt khung”.
Giả thiết: khóa công khai ( n,e) là hợp lệ.
Các bước:
1. Nếu thông báo m không nằm trong khoảng từ 0 đến n-1 thì đưa ra thông báo

“ biểu diễn thông báo vượt khung” và dừng.
2. Đặt c = me mod n.
3. Trả về c.
2.2 : Phép giải mã RSA nguyên thủy
RSADP(K,c)
Đầu vào: K khóa bí mật RSA, trong đó K là một trong các dạng sau:
- Cặp (n,d)
- Bộ tham số (p, q, dP, dQ, qInv)
c bản mã là một số nguyên trong khoảng từ 0 đến n-1.
Đầu ra: m thông báo là một số nguyên trong khoảng 0 đến n-1 hoặc
thông báo “ biểu diễn bản mã vượt khung”.
Giả thiết: khóa bí mật K là hợp lệ.
Các bước:
1. Nếu bản mã c không trong khoảng từ 0 đến n-1, đưa ra thông báo “
biểu diễn bản mã vượt khung” và dừng.
2. Nếu sử dụng dạng thứ nhất (n, d) của K thì:
a. Đặt m = cd mode n.
Ngược lại, nếu dạng thứ hai ( p, q, dP, dQ, qInv) của K được sử
dụng:
b. Đặt m1 = cdP mod p.
c. Đặt m2 = cdQ mode d.
d. Đặt h = qInv ( m1 –m2) mod p.
e. Đặt m = m2 + hq.
3. Trả về m.
8


Tìm hiểu RSA nguyên thủy

2.3 : Phép ký số RSA nguyên thủy

RSASP(K,m)
Đầu vào: K khóa bí mật RSA, trong đó K là một trong các dạng sau: Cặp
(n, d)Bộ tham số ( p, q, dP, dQ,qInv)m biểu diễn của thông điệp dưới dạng
số nguyên trong từ 0 đến n-1.
Đầu ra: s biểu diễn của chữ ký, là số nguyên trong khoảng từ 0 đến n-1.
Thông báo lỗi “ biểu diễn thông điệp ở ngoài miền hợp lệ”.
Giả thiết: khóa bí mật K là hợp lệ.
Các bước:
1. Nếu biểu diễn của thông điệp m không nằm trong khoảng từ 0 đến n-1,
đưa ra thông báo “ biểu diễn thông điệp ở ngoài miền hợp lệ” và dừng.
2. Biểu diễn của chữ ký được tính như sau:
a. Nếu dạng thứ nhất ( n, d) của K được sử dụng thì s = md mod n.
b. Nếu dạng thứ hai ( p, q, dP, dQ, dInv) của K được sử dụng thì tiến
hành như sau:
i.
Đặt s = mdQ mod p, s = mdQ mod q.
ii.
Đặt h = (s1 –s2 ) qInv mod p.
iii. Đặt s = s2 + q.h.
3. Xuất ra s.

2.4 : Phép kiểm tra chữ ký RSA nguyên thủy RSAVP
RSAVP ( ( n, e), s)
Đầu vào: ( n, e) khóa công khai RSA s biểu diễn của chữ ký, là số nguyên giữa 0
và n -1.
Đầu ra: m biểu diễn của thông điệp, là số nguyên giữa 0 và n-1. Thông báo lỗi “
biểu diễn chữ ký ở ngoài miền hợp lệ”
Giả thiết: khóa công khai RSA ( n, e) là hợp lệ.
Các bước:
1. Nếu biểu diễn của chữ ký s không nằm giữa 0 và n-1 cho ra “ biểu diễn chữ

ký ở ngoài miền hợp lệ” và dừng lại.
9


Tìm hiểu RSA nguyên thủy
2. Đặt m = se mod n.
3. Xuất ra m.

Chương 3:Xây dựng chương trình
3.1 : Xây dựng chương trình
3.2.1: Cấu tạo chương trình
Texbox: P , Q, E , N, Message,RSA
Button : Random, Encrypt, Decrypt
3.2.2: Phân tích chức năng
Chương trình gồm có 2 textbox đầu tiên dùng để hiển thị 2 số nguyên tố lớn
P và Q , textbox thứ 3 dùng để hiển thị số mũ E,textbox thứ 4 để hiển thị biến N ,
textbox thứ 5 dùng để nhập bản rõ M ,textbox thứ 6 để hiển thị bản mã hóa C
.Chương trình có button Random giúp sinh nhanh ra các số nguyên tố lớn P, Q ,Số
mũ E và tính toán N một cách nhanh chóng và bất kì. Button Encrypt để thực hiện
thuật toán mã hóa,button Decrypt để thực hiện thuật toán giải mã.
3.2.3: Nhận xét kết quả chương trình
Đạt được : Đã mã hóa và giải mã được , tạo được các số nguyên tố P , Q , số
mũ E , Tính toán được N
Hạn chế : Chỉ mã hóa được bản mã là số nguyên , giao diện còn sơ sài.

10


Tìm hiểu RSA nguyên thủy


3.2 : Một số giao diện của chương trình
Chương trình được xây dựng trên NetBeans 8.0.2 giao diện được kéo thả
đơn giản với các button và các textbox

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

11


Tìm hiểu RSA nguyên thủy

Hình 3:Giao diện khi click button Random

Hình 4: Giao diện khi click button Encrypt

12


Tìm hiểu RSA nguyên thủy

Hinh 5 : Giao diện khi click button Decrypt

13