Bài lưu trữ về giải thuật RSA 1.0.1 Rongchaua





Trang 1 của 13
Giải thuật RSA
www.reaonline.net


1 Giới thiệu. ____________________________________________________________________ 2
2 Phân phối khóa. _____________________________________________________________ 4
3 Phương pháp truyền dữ liệu „lai“. _________________________________________ 5
4 Giải thuật RSA._______________________________________________________________ 5
4.1 Giải thuật._______________________________________________________________________ 5
4.1.1 Hàm một chiều. _____________________________________________________________________ 5
4.1.2 Public Key. __________________________________________________________________________ 5
4.1.3 Private Key. _________________________________________________________________________ 5
4.1.4 Ví dụ với sự giúp đỡ của RSA Tool :__________________________________________________ 5
4.2 Mã hóa tin tức.__________________________________________________________________ 7
4.2.1 Công thức. __________________________________________________________________________ 7
4.2.2 Ví dụ với mã nguồn C#. _____________________________________________________________ 7
4.3 Giải mã tin tức. _________________________________________________________________ 7
4.3.1 Công thức ___________________________________________________________________________ 7
5 Ví dụ. _________________________________________________________________________ 8
5.1 Chuẩn bị. ________________________________________________________________________ 8
5.2 Tạo khóa. _______________________________________________________________________ 8
5.3 Mã hóa.__________________________________________________________________________ 9
5.4 Giải mã. _________________________________________________________________________ 9
5.5 Kết luận. _______________________________________________________________________ 10

5.6 Độ phức tạp của giải thuật RSA. ______________________________________________ 10
6 Chữ ký kỹ thuật số__________________________________________________________ 11
7 Ứng dụng. ___________________________________________________________________ 12
8 Tài liệu tham khảo. _________________________________________________________ 12











Bài lưu trữ về giải thuật RSA 1.0.1 Rongchaua





Trang 2 của 13

1 Giới thiệu.
• Với sự phát triển như vũ bão của nền công nghệ thông tin trong các thập kỷ
qua thì các hệ thống bảo mật cũng như các phương pháp bảo mật mới hàng
lọat ra đời nhằm đáp ứng nhu cầu bảo mật dữ liệu trong quá trình truyền tải.
Nói đến các giải thuật mã hóa dữ liệu nổi tiếng và được sử dụng rộng rãi hiện
nay có thể kể đến như MD5, CRC32,… và RSA.
• Như quy luật tự nhiên, „vỏ quít dày, móng tay nhọn“, bảo mật cao cách mấy

thì cũng có thể bẻ gãy. Những MD5-Hash, CRC32-Hash… với một máy tính
mạnh và một chương trình bruteforce tốt thì trong vòng 21 ngày một mật mã
chuẩn (gồm ký tự hoa, thường, ký tự đặc biệt, số và có chiều dài lớn hơn 8 ký
tự) được mã hóa bằng MD5 có thể bị bẻ gãy „dễ dàng“. Như vậy, việc bảo mật
dữ liệu trên đường truyền ngày càng đòi hỏi những giải thuật „mạnh hơn, khó
bẻ gãy hơn“. Và hiện nay dẫn đầu về tính bảo mật trong các giải thuật thông
dụng có thể nhắc đến RSA.
• Vậy RSA là gì? RSA là một giải thuật (phương pháp) để mã hóa dữ liệu điện
tử, được lấy theo tên của ba nhà phát minh Ronald L. Rivest, Adi Shamir,
Leonard Adleman. RSA được phát triển vào năm 1977 dựa trên:
o Lý thuyết về khóa mở (Public Key) của Whitfield Diffie và Martin
Hellman. Cho nên RSA được xếp vào nhóm giải thuật sử dụng phương
pháp bất đối xứng hoặc phương pháp Public Key.
o Phép tóan mã hóa một chiều với kiến thức tóan học cơ bản „Việc tách
một số ra thành 2 số nguyên tố thông qua một phép tóan chia thì
rất khó. Trong khi đó việc tạo ra một số từ phép nhân của 2 số
nguyên tố thì lại rất đơn giản“.
• Dựa trên ý tưởng trên, RSA được áp dụng vào quá trình truyền tải dữ liệu như
sau.
o Một khóa riêng sẽ được tạo ra dựa trên các số nguyên tố.
o Một khóa chung sẽ được tạo ra dựa trên khóa riêng này theo một hàm
một chiều. Tức là việc tìm lại „khóa riêng“ từ khóa chung này là một
điều gần như là không thể. Do đó, khóa chung có thể gởi đi trên
mạng.
o Khóa chung sẽ được truyền đi trên mạng trong quá trình truyền tải dữ
liệu.
o Dữ liệu nhận được sẽ được mã hóa dựa theo khóa chung này, và sẽ
được giải mã bằng khóa riêng.
• Để dễ hiểu chúng ta có thể xem ví dụ sau:
Bài lưu trữ về giải thuật RSA 1.0.1 Rongchaua







Server
Client 1 Client 2 Client 3 Client 4
(3)
(3)
(2)
(2)
(1)
(1)
• (1) : Client 1 muốn tải dữ liệu từ Server/Client 2
o Tạo ra một khóa riêng
o Từ khóa riêng này tạo ra một khóa chung.
o Gởi yêu cầu đến Server/Client khác đồng thời gởi khóa chung này theo.
• (2) : Server/Client 2 nhận được yêu cầu
o Mã hóa dữ liệu dựa trên khóa chung mà Client đã gởi đến.
• (3) : Server/Client hòan tất quá trình mã hóa
o Gởi dữ liệu đã mã hóa lại cho Client 1.
o Client nhận được dữ liệu và bắt đầu tiến hành giải mã.
o Như vậy, trên nguyên tắc bảo mật, chỉ có Client 1 là có thể giải mã được
dữ liệu nhận được. Vì “duy nhất”chỉ có Client 1 mới biết được khóa riêng
và với khóa riêng này quá trình giải mã sẽ có thể tiến hành.
• Qua ví dụ trên, chúng ta thấy được rằng, với RSA có rất nhiều khóa riêng
(tương ứng với mỗi Client) và vì thế có rất nhiều khóa chung để phục vụ quá
trình mã hóa và giải mã.
















Trang 3 của 13
Bài lưu trữ về giải thuật RSA 1.0.1 Rongchaua





Trang 4 của 13
2 Phân phối khóa.
• Ở trên, chúng ta đã có nhắc tới phương pháp truyền dữ liệu bất đối xứng. Để
hiểu rõ thêm ta có thể tạo một bảng so sánh giữa 2 phương pháp truyền dữ
liệu:
o Đối xứng.
o Bất đối xứng.

Phương pháp truyền dữ liệu đối xứng Phương pháp truyền dữ liệu bất đối xứng


• Người gởi và người nhận sử dụng
cùng chung một khóa bí mật. Tức
là, khi Client yêu cầu dữ liệu thì
Client phải gởi khóa bí mật này
theo để Server/Client khác có thể
mã hóa dữ liệu theo khóa bí mật
này. Như vậy, yêu cầu quá trình
truyền tải dữ liệu phải tuyệt đối
bảo mật. Nếu đường truyền bị
„nghe lén“ thì dĩ nhiên dữ liệu sẽ
bị mất do khóa bảo mật cũng bị
nghe lén.
• Việc kiểm tra xem khóa nhận được
có phải từ người mà dữ liệu cần
được truyền đến cần phải được
thực hiện
• Nếu đường truyền bị nghe lén thì
khóa bị mất là khóa chung. Vẫn
không thể giải mã được dữ liệu vi vẫn
cần một khóa riêng. Và việc giải mã
ngược từ khóa chung ra khóa riêng là
một điều gần như là không thể.






• Tương tự như ở phương pháp truyền

dữ liệu đối xứng, việc nhận dạng
cũng phải được thực hiện.

• Với hàm Hash SHA-1, khóa chung có
thể được chia thành nhiều phần. Mỗi
phần là một khóa con và có thể được
gởi vào các thời điểm khác nhau cũng
như với các phương pháp trao đổi
khác nhau hòan tòan.













Bài lưu trữ về giải thuật RSA 1.0.1 Rongchaua





Trang 5 của 13
3 Phương pháp truyền dữ liệu „lai“.

• So sánh với 3DES, AES và SHA-1 mã hóa bằng RSA chậm hơn khỏang 1000
lần. Vì vậy để mã hóa một số lượng lớn dữ liệu thì RSA sẽ không được sử
dụng. Thay vào đó phương pháp mã hóa đối xứng sẽ được sử dụng. Nhược
điểm của phương pháp mã hóa đối xứng chính là khóa sẽ được truyền đi, cho
nên để khắc phục nhược điểm này, khóa của phương pháp mã hóa đối xứng
sẽ được mã hóa bằng RSA và gởi đi. Phần nội dung sẽ được gởi theo phương
pháp đối xứng.
• Sử dụng phương pháp truyền dữ liệu như trên gọi là phương pháp lai.
4 Giải thuật RSA.
• Như vậy chúng ta đã có một cái nhìn sơ lược về giải thuật RSA cũng như
những lợi điểm và yếu điểm của giải thuật này. Bây giờ, chúng ta sẽ tìm hiểu
sâu hơn về giải thuật RSA về phương diện cấu trúc.
• Ta đã biết, với giải thuật RSA chúng ta cần 2 khóa : Khóa riêng và khóa chung
và một hàm một chiều để tạo ra khóa chung này từ khóa riêng tùy ý. Chúng
ta sẽ tìm hiểu xem các thành phần này được tạo ra như thế nào.
4.1 Giải thuật.
4.1.1 Hàm một chiều.
• Chọn 2 số nguyên tố bất kỳ p ≠ q.
• Tính tích N = p * q.
• Tính hàm Euler φ(N) = (p -1)*(q -1).
4.1.2 Public Key.
• Chọn 1 số e bất kỳ sao cho 1<e< φ(N) và φ(N) không chia hết cho e.
• Một khóa public key bao gồm:
o N, tích của 2 số nguyên tố.
o e, mũ public
4.1.3 Private Key.
• Tìm k sao cho ((φ(N)*k) + 1 mod e) = 0
• Tính d = (φ(N)*k + 1) / e.
• Một khóa private key bao gồm:
o d, mũ private.

o N, đã biết trước có trong khóa public key.
4.1.4 Ví dụ với sự giúp đỡ của RSA Tool :
• Chọn 2 số nguyên tố: p = 11 và q = 13.
• Chọn e = 17.
4.1.4.1 Dùng RSA Tool
• Ta dùng RSA Tool để tính N và khóa riêng d.

Bài lưu trữ về giải thuật RSA 1.0.1 Rongchaua






• Bước 1 : Nhập vào 2 số nguyên tố P = 11 và Q = 13 ( tại 2 Textbox viền đỏ).
• Bước 2 : Nhập vào mũ e = 0x11 (tại Textbox viền xanh lá cây), tức bằng 17 ở
hệ thập phân.
• Bước 3 : Chọn NumberBase là 10, tức là ta dùng hệ thập phân để tính.
• Nhấn nút “Calc. D” để tính ra D (nút viền xanh dương). Ta tính được N = 143
và D = 47
• Vậy, private key (143,47) và public key (143,17).
• Lưu ý: Ở đây ta thấy có một Textbox thể hiện Keysize (Bits) của khóa.
Tức là nếu chúng ta chọn 256 thì Public Key e cũng như Private key d
sẽ có chiều dài là 256 bits trong hệ nhị phân. Tức là sẽ có dạng một
chuỗi 1000101110001…010101010 Å Dài 256 ký tự.
4.1.4.2 Tự lập trình.
• Dưới đây là source code tham khảo trong C#
• Do khả năng lập trình hạn chế nên source code bên dưới chỉ họat động với các
số nguyên tố nhỏ hơn 100.



Trang 6 của 13
Bài lưu trữ về giải thuật RSA 1.0.1 Rongchaua
















int p = 11,q = 13;
int N = p * q;
int phi = (p - 1) * (q - 1);
int k=1;
while (((phi * k + 1) % exp
!= 0))
{
k++;
}
int exp= 17;
int d = (phi * k + 1) / exp;

4.2 Mã hóa tin tức.
• Như vậy, ta đã xác định được private key và public key. Bây giờ ta sẽ sử dụng
các khóa này vào quá trình mã hóa dữ liệu.
4.2.1 Công thức.
• Để mã hóa tin tức K, người gởi sử dụng công thức :
C ≡

K
e
mod N
o C: tin đã mã hóa
o K: tin chưa mã hóa.
4.2.2 Ví dụ với mã nguồn C#.
• Chúng ta muốn mã hóa số 7 để gởi về người nhận, và chúng ta có khóa chung
là (143,17)
• Vậy số gởi đi là C ≡ 7
17
mod 143 = 50.

int C = (int) (Math.Pow(7, exp) % N
)
;


4.3 Giải mã tin tức.
4.3.1 Công thức
• Tin tức mã hóa có thể phục hồi trở lại tin tức chưa mã hóa theo công thức




K ≡ C
d

mod N

• Lưu ý : Ta thấy qua công thức trên có một điều kiện cần phải thỏa cho
N đó là N phải lớn hơn K. Do ta chia lấy phần dư nên phần dư phải bắt
buộc nhỏ hơn số chia. Như vậy điều kiện là : N > K (Cảm ơn lão Dump
đã gợi ý cho điều kiện này).
• Ví dụ:
• Theo ví dụ trên ta sẽ có
• K ≡ 50
113
mod 143 = 7.

int K = (int) (Math.Pow(
C
,

d
)
% N
)
;

Trang 7 của 13
Bài lưu trữ về giải thuật RSA 1.0.1 Rongchaua





5 Ví dụ.
5.1 Chuẩn bị.
• Như vậy, chúng ta vừa hòan thành mã hóa và giải mã một số đơn giản bằng
giải thuật RSA. Dĩ nhiên trong thực tế giải thuật RSA được sử dụng và biến tấu
phức tạp hơn gấp nhiều lần. Vì vậy chúng ta lại tiếp tục với một ví dụ khác
phức tạp hơn một chút để gắn liền với thực tiễn hơn.
• Trong thực tế người ta sử dụng bảng mã ASCII để chuyển Text sang dạng số.
Sau đó, người ta sẽ dùng giải thuật RSA để mã hóa dữ liệu Text ở dạng số này
rồi truyền trên mạng .Ở đây để đơn giản, thay vì sử dụng ký tự ASCII chúng
ta sử dụng thứ tự của các chữ cái trong bảng chữ cái.
• A = 01, B = 02, C = 03 … và 00 = ký tự trống.



for (i = 0; i < strName.Length; i++)
{
strTmp = Convert.ToString((strAlphabet.IndexOf(strName[i]) + 1));
if (strTmp.Length == 2)
{
strNameIndex += strTmp;
}
else
{
strNameIndex += "0" + strTmp;
}
}













• Ta giả sử ở đây cứ hai ký tự sẽ tạo thành một nhóm tin tức K. Ví dụ chuỗi TI
sẽ được chuyển thành 2009. Như vậy số mã hóa nhỏ nhất sẽ là 0000 ( 2 ký tự
trống liên tục) và 2626( 2 chữ ZZ).
• Bây giờ là chúng ta sẽ mã hóa một Text : RONGCHAUA bằng giải thuật RSA.
• Chuỗi chưa mã hóa : R O N G C H A U A
• Chuỗi mã hóa bằng vị trí của ký tự trong bảng chữ cái là : 18 15 14 07
03 08 01 21 01
5.2 Tạo khóa.
• Trước tiên ta chọn 2 số nguyên tố p & q. Chọn p = 53 và q = 51. Lưu ý điều
kiện là N = 51*53 phải lớn hơn 2626
• Chọn ra e = 0xB (tức 11 ở hệ thập phân).


Trang 8 của 13
Bài lưu trữ về giải thuật RSA 1.0.1 Rongchaua







• Như vậy ta có khóa riêng là (2703,1891) và khóa chung là (2703,11).
5.3 Mã hóa.
• C
n
= K
n
e
mod N ( với n = 1,2,3 …).
• C
1
= 1815
11
mod 2703 = 1500.
• C
2
= 1407
11
mod 2703 = 939.
• C
3
= 0308
11
mod 2703 = 1344.
• …
5.4 Giải mã.
• K
n
= C
n
d

mod N
• K
1
= 1500
1891
mod 2703 = 1815 √
• K
2
= 939
1891
mod 2703 = 1407 √
• K
3
= 1344
1891
mod 2703 = 308 √
• …

Trang 9 của 13
Bài lưu trữ về giải thuật RSA 1.0.1 Rongchaua




5.5 Kết luận.
• Như vậy ta đã hòan thành phần mã hóa, giải mã của giải thuật RSA với một
Text.
5.6 Độ phức tạp của giải thuật RSA.
• Giải thuật RSA cho phép chúng ta mã hóa với các mức độ phức tạp khác nhau
bằng cách thiết lập độ lớn của Keysize (Bits).

• Chúng ta có thể làm một ví dụ để hiểu rõ hơn về mức độ phức tạp của giải
thuật RSA.
• Đầu tiên chúng ta thiết lập các thông số như sau.



• Chúng ta click vào nút Factor N để chương trình tính ra 2 số nguyên tố P và Q.
Rất nhanh chúng ta được kết quả P = 91M và Q = 4AM (nhìn hình).
• Bây giờ chúng ta hãy làm tương tự như trên nhưng với cách thiết lập thông số
như sau:



Trang 10 của 13
Bài lưu trữ về giải thuật RSA 1.0.1 Rongchaua






• Nhấn nút Calc. D và chờ… Chúng ta dĩ nhiên không thể chờ được vì theo lý
thuyết thì để giải được khóa này chúng ta cần khỏang 8 giờ để máy chạy liên
tục. Như vậy, chúng ta đã xong với phần test độ an tòan của khóa được tạo
ra bằng giải thuật RSA. Trong việc bảo mật dữ liệu thông qua RSA người ta
thông thường dùng Keysize là 1024 để an tòan tuyệt đối.

6 Chữ ký kỹ thuật số
• Một trong những ứng dụng to lớn của RSA đó chính là việc tạo chữ ký kỹ
thuật số cho các tài liệu. Vì sao chúng ta lại cần chữ ký kỹ thuật số? Đó là vì

trong quá trình truyền tải dữ liệu chúng ta cần phải chắc chắn rằng tài liệu
mà chúng ta nhận được có phải từ nguồn mà chúng ta mong muốn hay
không.
• Chúng ta sẽ làm một ví dụ đơn giản cho rõ ràng hơn.
• Giả sử Ti muốn gởi cho Mi một tài liệu. Thì Ti sẽ làm các bước sau.
o Trước tiên Ti tạo một khóa riêng (d,N) và một khóa chung (e,N).

Trang 11 của 13
Bài lưu trữ về giải thuật RSA 1.0.1 Rongchaua




o Sau đó Ti sẽ tạo ra Hash của tài liệu (có thể là checksum MD5 hay CRC
của tài liệu).
o Tiếp theo Ti sẽ mã hóa giá trị Hash này bằng khóa riêng (d,N).
o Sau đó Ti sẽ chuyển tài liệu + giá trị mã hóa của giá trị Hash + khóa
chung này cho Mi.
• Mi nhận được tài liệu, muốn biết chắc là nó có phải là của Ti không. Mi cần
làm các bước sau.
o Dùng khóa chung nhận được từ Ti. Giải mã giá trị mã hóa giá trị Hash
sẽ một giá trị Hash.
o Tính giá trị Hash của tài liệu với cùng cách với các tính giá trị Hash của
tài liệu như Ti đã tính.
o So sánh 2 giá trị Hash này nếu bằng nhau thì tài liệu đó chính là của Ti
gởi.
• Toàn bộ quá trình được biễu diễn theo hình dưới.


7 Ứng dụng.

• Hệ thống Internet và điện thọai : X.509 – Certifikate.
• Giao thức truyền tải : IPSec, TLS, SSH, WASTE.
• Mã hóa Email : PGP, S/MIME.
• Thanh tóan bằng thẻ : EMV.
8 Tài liệu tham khảo.
• Wikipedia. www.wikipedia.org.
• Xin cảm ơn dump về gợi ý điều kiện N > K.


Trang 12 của 13
Bài lưu trữ về giải thuật RSA 1.0.1 Rongchaua






Rongchaua chấp bút
My Email :
My Website : www.rongchaua.nth12a1.com
“46a42a575a3115eff2d2a37e9cf33626”ÅÝ nghĩa của đọan MD5 này là gì?
Nếu tôi có gì sai sót, vui lòng liên hệ email trên để “mắng vốn”.
16.04.2006-16.12.2006

Trang 13 của 13