ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN QUÝ HÀO
NGHIÊN CỨU PHỐI HỢP HAI PHƯƠNG PHÁP NÉN
và MÃ HOÁ THÔNG TIN
Ngành: Công nghệ thông tin
Chuyên ngành: Truyền dữ liệu và mạng máy tính
Mã số: 60 48 15
LUẬN VĂN THẠC SĨ NGÀNH CNTT Giảng viên hướng dẫn: PGS. TS TRỊNH NHẬT TIẾN
HÀ NỘI, 11-2012
2.1.2 Hệ mã hoá khoá phi đối xứng 16
2.1.3 Hệ mã hoá RSA 17
2.1.3.1 Lịch sử hình thành hệ mã hoá RSA 17
2.1.3.2 Hệ mã hoá RSA đầu tiên 17
2.1.3.3 Định nghĩa hệ mã hoá RSA 18
2.2 CÁC CHUẨN KỸ THUẬT TRONG PKCS 19
2.2.1 Tổng quan về PKCS và PKCS#1 v2.1 19
2.2.1.1 PKCS 19
2.2.1.2 PKCS#1 v2.1 19
2.2.2 Các ký hiệu trong PKCS#1 v2.1 20
2.2.3 Các kiểu khóa 21
2.2.3.1 Khóa công khai RSA 22
2.2.3.2 Khóa bí mật RSA 22
2.2.4 Cơ sở chuyển đổi dữ liệu I2OSP và OS2IP 23
2.2.4.1 Chuyển đổi dữ liệu I2OSP 24
2.2.4.2 Chuyển đổi dữ liệu OS2IP 24
2.2.5 Cơ sở của hệ mật mã 25
2.2.5.1 Cơ sở hệ mã hóa RSAEP 25
2.2.5.2 Cơ sở hệ mã hóa – RSADP 26
2.2.6 Lƣợc đô mã hóa 28
2.2.6.1 Tổng quan về lược đồ mã hóa 28
2.2.6.2 Các kỹ thuật hỗ trợ 28
2.2.6.3 Lược đồ RSAES – OAEP 29
2.2.7 Ý nghĩa của việc áp dụng EME - OAEP trƣớc khi mã hóa RSA 34
2.2.8 Vấn đề sinh khóa RSA 35
2.3 CHUẨN MÃ HÓA DỮ LIỆU TIÊN TIẾN – AES 37
3
3.3.2.2 Các thuật toán nén LZ 66
Chương 4: PHỐI HỢP HAI PHƢƠNG PHÁP NÉN VÀ MÃ HOÁ THÔNG TIN 80
4.1 MÔ HÌNH PHỐI HỢP HAI PHƢƠNG PHÁP NÉN VÀ MÃ HOÁ THÔNG TIN 80
4.1.1 Về không gian lƣu trữ 80
4.1.2 Vấn đề an ninh 81
4.1.3 Vấn đề thời gian xử lý dữ liệu 82
4.2 Mô hình phối hợp hai phƣơng pháp nén và mã hoá dữ liệu 82
4.3 CHƢƠNG TRÌNH THỬ NGHIỆM 86
4.3.1 Mô tả chung 86
4.3.2 Ý tƣởng cài đặt 86
4.3.2.1 Ngôn ngữ lập trình 86
4.3.2.2 Cấu trúc chƣơng trình 87
4.3.3 Thực hiện 92
4.3.4 Đánh giá 94
KẾT LUẬN 98
TÀI LIỆU THAM KHẢO 99
4
DANH MỤC CÁC BẢNG
STT
Tên bảng
Bảng 3.7: Quá trình nén bằng thuật toán LZ78 bản mã
“(0,a)(1,a)(0,b)(3,a)(4,a)(5,a)(4,b)”
73
10.
Bảng 3.8: Quá trình nén xâu “aabababaaababb” bằng thuật toán LZW
79
11.
Bảng 3.9: Quá trình giải nén bản mã “001352411” theo thuật toán
LZW
80
12.
Bảng 4.2: Bảng kết quả thử nghiệm đánh giá về mặt hiệu quả nén
96
13.
Bảng 4.2: Bảng kết quả thử nghiệm đánh giá về mặt thời gian
97
5
DANH MỤC CÁC HÌNH VẼ
STT
Tên bảng
Trang
1.
Hình 2.1: Nguy cơ bị tấn công khi truyền thông tin trên mạng máy tính
16
47
12.
Hình 3.3: Mã tổng
47
13.
Hình 3.4: Mã hoá theo mô hình thống kê động
52
14.
Hình 3.5: Giải mã hoá theo mô hình thống kê động
53
15.
Hình 3.6: Quá trình tạo mã Fanno
5
16.
Hình 3.7: Xây dựng mã Huffman
59
17.
Hình 3.8: Lƣu đồ giải mã Fanon, Shanon, Huffman
61
18.
Hình 3.9: Lƣợng tin
64
19.
Hình 3.10: Quá trình thực hiện nén bằn mã LZ
66
20.
Hình 3.11: Sơ đồ nén LZ78
70
21.
Hình 3.12: Sơ đồ giải nén thuật toán LZ78
6
LỜI MỞ ĐẦU
Quá trình lƣu trữ và truyền tải thông tin luôn luôn có 2 yếu tổ đƣợc quan tâm
hàng đầu là: tính an toàn bảo mật và kích thƣớc của tệp tin.
Đã có rất nhiều các phần mềm, các chƣơng trình đƣợc viết để giải quyết hai vấn
đề đƣợc đặt ra. Tuy nhiên các phần mềm phần lớn chỉ quan tâm tới một trong hai yếu
tố chỉ nén dữ liệu Winzar, Winzip, 7Zip… hoặc chỉ mã hoá nhƣ: Enterprise,
TrueCrypt… tuy nhiên nếu chỉ nén dữ liệu kích thƣớc tệp tin đƣợc giảm nhƣng lại
không bảo đảm tính an toàn thông tin. Ngƣợc lại nếu chỉ mã hoá chỉ đảm bảo tính an
toàn nhƣng không giải quyết đƣợc vấn đề giảm dung lƣợng lƣu trữ hơn thế mã hoá tệp
tin lớn tốn nhiều thời gian và băng thông để truyền tải cũng tăng theo.
Trong khi đó nếu phối hợp cả hai quá trình trên sẽ đem lại rất nhiều lợi ích:
giảm dung lƣợng lƣu trữ, giảm băng thông truyền tải, giảm thời gian mã hoá, tăng tính
bảo mật cho tệp tin so với tệp tin chỉ mã hoá đơn thuần.
Từ ý nghĩa thực tiễn quan trọng nêu trên là động lực để tôi nghiên cứu đề tài:
“Nghiên cứu phối hợp hai phƣơng pháp nén và mã hoá thông tin”.
Trong luận văn sẽ đề xuất mô hình và giải pháp phối hợp hai phƣơng pháp nén
và mã hoá thông tin: sử dụng các thuật toán nén để nén dữ liệu sau đó dùng phƣơng
pháp mã hoá đối xứng để mã hoá tệp tin sau, cuối cùng là dùng mã khoá khoá bất đối
xứng RSA để mã hoá khoá chung của AES.
Luận văn đƣợc trình bày theo cấu trúc sau:
- Chƣơng 1: trình bày cơ sở toán học đƣợc sử dụng trong quá trình nén và mã
hoá thông tin gồm: các khái niệm, các định lý, định nghĩa và một số thuật
toán cơ bản
Học viên: Nguyễn Quý Hào
8
Chương 1: MỘT SỐ KHÁI NIỆM CƠ BẢN
1.1 CÁC ĐỊNH LÝ QUAN TRỌNG
1.1.1 Định lý Euler
Định lý:
Cho a Z, m N, m > 1. Nếu UCLN (a, m) = 1 thì a
(m)
1 (mod m)
1.1.2 Định lý Fermat (hệ quả của định lý Euler)
Định lý:
Cho a Z và k là một số nguyên tố khi đó a
k
a (mod k)
Nếu UCLN(a, k) = 1 thì a
k-1
1 (mod k)
1.1.3 Định lý đồng dƣ Trung Quốc
Định lý:
Cho m
1
, m
2
, … m
r
là x =
r
i
iii
yMa
1
trong đó
M
i
=
i
m
M
và y
i
= M
i
-1
mod m
i
Ví dụ: Tìm nghiệm đồng dƣ của hệ phƣơng trình đồng dƣ:
)7(mod8
)3(mod6
)2(mod3
x
x
x
1.1.4 Định lý Bezout
Định lý:
Cho a, b N, a > b 1; ta có:
+ Tồn tại x, y Z sao cho ax + by = UCLN(a, b)
+ Nếu a, b nguyên tố cùng nhau thì tồn tại x,y Z | ax + by = 1
+ a, b nguyên tố cùng nhau khi và chi khi tồn tại x, y Z | ax + by = 1
1.2 MỘT SỐ THUẬT TOÁN
1.2.1 Thuật toán Euclidean
Cơ sở số học của thuật toán:
Cho a, b, d Z, d ≠ 0 nếu a
d và b
d thì a mod b
d
Nội dung thuật toán:
INPUT: r
0
, r
1
N, r
0
> r
1
0
OUPUT: d = UCLN(r
0
, r
1.2.2 Thuật toán Euclidean mở rộng
Cơ sở số học của thuật toán: trong thuật toán Euclidean tìm UCNL của hai số
nguyên r
0
> r
1
0, ta thấy thuật toán là quá trình thực hiện chuỗi phép chia lấy phần dƣ
dễ dàng ta thấy
UCLN(r
0,
r
1
) = UCLN(r
1,
r
2
) = UCLN(r
2,
r
3
) = … = UCLN(r
m-1,
r
m
)
Với r
2
= r
0
mod r
j-1
t
j-1
) mod r
0
, với j 2
Ta có kết quả quan trọng sau:
Định lý:
Với mọi j, 0 j 2 ta có r
j
t
j
r
1
(mod r
0
)
Nội dung thuật toán:
INPUT: n, b N (n> b 0)
OUTPUT: t = b
-1
mod n
Giả mã thuật toán:
1. n
0
= n
2. b
0
= b
3. t
7.6 n
0
= b
0
7.7 b
0
= r
q = n
0
div b
0
r = n
0
– qb
0
8. if b
0
≠ 1 then b không khả nghịch theo modulo n
9. else b
-1
= t mod n
1.2.3 Thuật toán bình phƣơng và nhân
Giả sử có các số nguyên x, b và n. Ta phải tính x
b
mod n. Thuật toán: “Bình
phƣơng và nhân” sau đây sẽ giúp ta tính lũy thừa này khá đơn giản. Đây là một thuật
toán quan trọng đƣợc sử dụng trong qui trình mã hóa cũng nhƣ giải mã của hệ mã hoá
12
1.2.4 Thuật toán xác suất kiểm tra số nguyên tố
INPUT: một số nguyên dƣơng n
OUPUT: n là hợp số
Sau đây ta sẽ đi xem thuật toán Miller - Rabin giải quyết bài toán này
1/. Thuật toán Miller – Rabin
Kiểm tra Miller:
Giả sử n là một số nguyên dƣơng lẻ, khi đó ta biểu diễn đƣợc n – 1 = 2
s
t với s là
một số nguyên không âm, t là một số nguyên dƣơng lẻ. Ta nói n vƣợt qua đƣợc kiểm
tra Miller cơ sở a (a Z, a > 0) nếu a
t
1 (mod n) hoặc
t
k
a
2
-1 (mod n) với k nào đó
0 k < s.
Mệnh đề:
Nếu n là một số nguyên tố thì n vƣợt qua kiểm tra Miller cơ sở a, 0 < a < n
Định nghĩa:
Nếu n vƣợt qua Miller cơ sở a thì n đƣợc gọi là số nguyên tố giả cơ sở a
Số nguyên dƣơng n > 1 đƣợc gọi là số giả nguyên tố mạnh cơ sở a nếu nó là
hợp số và vƣợt qua đƣợc kiểm tra Miller cơ sở a
Miller – Rabin – Test(n)
Thuật toán Miller – Rabin với t lần thực hiện kiểm tra Miller:
INPUT: n N, lẻ, n > 1, t N, số lần kiểm tra
OUTPUT: “n là nguyên tố” hoặc “n là hợp số”
1. Viết n – 1 = 2
k
m (m lẻ)
2. for i := 1 to t do
2.1 Chọn một số ngẫu nhiên a, 1 a n – 1
2.2 test:= false
2.3 b: = a
m
mod n
2.4 if b = 1 then test: = true
else
for i = 0 to k – 1 do
if b = n – 1 then test:= true
else b = b
2
mod n
2.5 if test = false then return “n là hợp số” và thoát
3. return “n là số nguyên tố”
Xác suất sai khi trả lời n là số nguyên tố không vƣợt quá (1/4)
t
1.3 KHÁI NIỆM ENTROPY
1.3.1 Định nghĩa Entropy
Định nghĩa. Độ bất định :
Xét không gian mẫu = {w
1
,
Định lý:
Có một số δ > 1 mà H( ) =
m
i
ii
pp
1
)(log.
Giả sử chúng ta lấy việc đoán nhận sự kiện nào trong 2 sự kiện đồng xác suất
làm đơn vị đo độ bất định thì khi đó H(2) = 1 vì thế log (2) = 1. Suy ra, = 2. Chúng
ta có công thức H(k) = log
2
(k).
14
Độ bất định xác định không phụ thuộc vào việc chọn đơn vị để đo. Nếu chọn
độ bất định của việc đánh số đề tức là đoán nhận 1 trƣờng hợp trong số 100 trƣờng hợp
đồng khả năng làm đơn vị đo và nếu có một việc có độ bất định là 3, tức là H(k) =
log
100
(k) = 3. Khi dùng đơn vị đo là việc đoán nhận một trƣờng hợp trong số 10 khả
năng làm đơn vị thì chỉ số đo sẽ là 6, vì H(k) = log
10
(k) = 2.log
c) Entropy đạt giá trị cực đại khi xác suất của các sự kiện ngẫu nhiên cơ bản của
không gian mẫu bằng nhau. Lúc đó độ bất định của việc đoán nhận một sự
kiện ngẫu nhiên cơ bản nào đó xảy ra là lớn nhất.
Định lý:
Nếu Ω, Φ là hai không gian mẫu cùng có m phần tử và nếu Φ là đồng xác suất
thì H(Ω) ≤ H(Φ).
Dấu bằng xẩy ra khi và chỉ khi với mỗi sự kiện ngẫu nhiên cơ bản trong Ω có
xác suất p
i
thì trong Ф cũng có một sự kiện ngẫu nhiên cơ bản có xác suất p
i
, tức là Ω
cũng là không gian đồng xác suất.
Nhƣ vậy, định lý khẳng định rằng entropy của không gian đồng xác suất là lớn
nhất trong số các không gian mẫu có cùng số các sự kiện ngẫu nhiên cơ bản.
Ví dụ:
Ví dụ đơn giản để minh hoạ nhƣ sau: giả sử chúng ta tung con xúc sắc mà ở
mặt 1 chúng ta gắn chì vào. Do khối lƣợng chì nặng nên đa số trƣờng hợp mặt 6 xuất
hiện (mặt 6 đối diện với mặt 1). Vì thế việc đoán xem mặt nào xuất hiện trở nên dễ
hơn.
15
Chương 2: PHƢƠNG PHÁP MÃ HOÁ
2.1 CÁC KHÁI NIỆM CƠ BẢN
mãn d
k
(e
k
(x)) = x x P Hình 2.1 Nguy cơ bị tấn công khi truyền thông tin trên mạng máy tính
16
2.1.1 Hệ mã hoá khoá đối xứng
Theo mô hình chung của các hệ mã hoá khoá đối xứng, Alice và Bob bí mật
chọn khóa K, sau đó K đƣợc sử dụng cho quy tắc mã hóa cũng nhƣ giải mã. Theo
phƣơng pháp mã hóa này thì khóa để mã hóa chính là khóa để giải mã hoặc trong một
số hệ mật thì khóa để mã hóa và khóa để giải mã tuy khác nhau nhƣng dễ dàng tính
đƣợc thành phần này khi đã biết thành phần kia. Từ đó mà các hệ mã hoá khoá đối
xứng còn đƣợc gọi với tên khác là hệ mã hoá khóa bị mật, hay hệ mã hoá khóa đối
xứng. Dƣới đây là mô hình truyền thông sử dụng hệ mã hoá khoá đối xứng
Hình 2.2: Mô hình truyền thông sử dụng hệ mã hoá khoá đối xứng [12]
2.1.2 Hệ mã hoá khoá phi đối xứng
Một hạn chế của một hệ mã hoá khoá đối xứng là nó yêu cầu việc truyền đi khóa
K giữa Alice và Bob trên một kênh an toàn trƣớc khi bất kì thông điệp mã hóa nào đƣợc
truyenf đi. Trên thực tế điều này rất khó thực hiện khi mà hai ngƣời ở xa nhau
Từ mặt hạn chế của các hệ mã hoá khoá đối xứng đã phân tích ở trên, ngƣời ta Hình 2.3: Mô hình truyền thông sử dụng hệ mã hoá khoá công khai [12]
2.1.3 Hệ mã hoá RSA
2.1.3.1 Lịch sử hình thành hệ mã hoá RSA
RSA (Ron Rivers, Adi Shamir và Len Adleman) là một hệ mã hoá khoá phi
đối xứng. Nó là thuật toán đầu tiên phù hợp với việc tạo ra chữ kí điện tử và đánh dấu
một sự tiến bộ vƣợt bậc trong mật mã học. RSA đang đƣợc ứng dụng phổ biến trong
giao dịch điện tử, đảm bảo an toàn với điều kiện độ dài đủ lớn. Thuật toán đƣợc mô tả
lần đầu tiên vào năm 1977 tại Học viện công nghệ Massachusettes (MIT).
Trƣớc đó, vào năm 1973, Clifford Cocks, một nhà toán học ngƣời Anh đã 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 cài đặt thực nghiệm. Phát minh này chỉ đƣợc công bố
năm 1977 vì đƣợc xếp vào loại tuyệt mật
2.1.3.2 Hệ mã hoá RSA đầu tiên
1/. Bài toán phân tích một số tự nhiên ra thừa số nguyên tố
Các thuật toán mã hóa công khai hiện đại đƣợc nghiên cứu và đề xuất dựa trên
việc nghiên cứu lý thuyết độ phức tạp của thuật toán và tính khó của các bài toán mà
thuật toán tốt nhất đƣợc tìm ra là để giải quyết bài toán đó cũng không chấp nhận đƣợc
trong thời gian thực với các máy tính hiện đại
Thuật toán RSA là thuật toán mã hóa dựa trên tính khó của bài toán phân tích
một số nguyên tố tự nhiên (đủ lớn) ra thừa số nguyên tố. Giả sử có n là một số tự nhiện
n = p.q trong đó p, q là các số nguyên tố. Với n là số tự nhiên đủ lớn, có độ dài trên
100 chữ số thập phân, thì bài toán phân tích n ra thừa số nguyên tố (tức tìm p, q) chƣa
18
mod n. Từ đó đƣa ra định nghĩa hệ mã hoá RSA.
2.1.3.3 Định nghĩa hệ mã hoá RSA
Định nghĩa:
Cho bộ số RSA (n, p, q, a, b) trong đó p, q là những số nguyên tố cỡ 512 bit
hoặc lớn hơn. Hệ mã hoá RSA với khóa K = (n, p, q, a, b) là hệ mã hoá với P = C = Z
n
,
qui tắc mã hóa và giải mã nhƣ sau:
Qui tắc mã hóa: với mỗi x P = Z
n
e
k
: Z
n
Z
n
x y = x
b
mod n
Qui tắc giải mã:
d
k
: Z
n
Z
n
y x = y
a
Trong RSA – đa nguyên tố thể hiện ở modulo RSA n là tích của nhiều hơn hai số
nguyên tố (trong các phiên bản trƣớc đó n tích của hai số nguyên tố n = p.q)
20
2.2.2 Các ký hiệu trong PKCS#1 v2.1
c Biểu diễn bản mã dạng số nguyên, 0 c n – 1 (là đầu ra của cơ sở mã hóa
RSAEP và là đầu vào của cơ sở giải mã RSADP)
C bản mã, là một chuỗi octet (là đầu ra của mã hóa RSAES – OAEP –
DECRYPT).
d số mũ RSA bí mật, sử dụng cho quá trình giải mã
d
i
số mũ CRT của r
i
, là một số nguyên dƣơng thỏa mã:
e.d
i
1 (mod ( r
i
- 1)), d
i
< r
i
– 1, i = 3, . . u.
MGF hàm sinh mặt nạ
mgfSeed hạt giống từ đó sinh ra mặt lạ mask, là một chuỗi octet
mLen chiều dài tính theo số octet của thông điệp M
n Modulo RSA, n = r
1
r
2
r
3
.r
u
, u 2
(n, e) khóa công khai RSA
p, q hai thừa số nguên tố đầu tiên của modulo RSA n
qInv hệ số CRT của p (hay hệ số CRT đầu tiên), một số nguyên dƣơng nhỏ hơn p và
thỏa mãn: q . qInv 1 (mod p)
r
i
thừa số nguyên tố của modulo RSA n, trong đó bao gồm r
1
= p, r
2
= q, và các
thừa số khác nếu có
t
i
hệ số CRT của thừa số nguyên tố r
i
, một số nguyên dƣơng nhỏ hơn r
i
|| toán tử nối các chuỗi octet
kí hiệu đồng dƣ, a b (mod n) có nghĩa là (a – b)
n
Ghi chú: thuật ngữ octet có ý nghĩa tƣơng đƣơng với byte (8 - bit)
2.2.3 Các kiểu khóa
Có hai kiểu khóa đƣợc sử dụng trong các cơ sở của hệ mật cũng nhƣ trong các
lƣợc đồ, đƣợc định nghĩa trong tài liệu PKCS#1 v2.1 là khóa bí mật RSA và khóa công
khai RSA. Một khóa công khai RSA và một khóa bí mật RSA tƣơng ứng kết hợp với
nhau tạo thành cặp khóa RSA
22
2.2.3.1 Khóa công khai RSA
Một khóa công khai RSA bao gồm hai thành phần:
+ n modulo RSA, một số nguyên dƣơng
+ e số mũ công khai RSA, một số nguyên dƣơng
Trong một khóa công khai RSA hợp lệ thì:
+ Modulo RSA n là tích của u số nguyên tố lẻ phân biệt r
i
, i = 1, 2, 3, ,u; u 2
+ số mũ công khai RSA e là số nguyên thỏa 3 e n – 1, UCLN(e, (n)) = 1
2.2.3.2 Khóa bí mật RSA
Có thể sử dụng một trong hai cách biểu diễn khóa bí mật RSA
Dạng 1: theo cách biểu diễn này thì một khóa bí mật RSA bao gồm hai thành
phần:
23
Một khóa bí mật RSA hợp lệ ở dạng biểu diễn thứ hai thì phải thỏa mãn:
+ p, q là hai thừa số nguyên tố đầu tiên của modulo RSA n. Các số mũ CRT
dP, dQ là những số nguyên dƣơng tƣơng ứng nhỏ hơn p và q thỏa mãn:
e.dP 1 (mod (p – 1))
e.dQ 1 (mod(q – 1))
+ Hệ số CRT đầu tiên qInv là một số nguyên dƣơng nhỏ hơn p, thỏa mãn
q.qInv 1 (mod p)
+ Nếu u > 2 thì trong khóa bí mật RSA dạng hai bao gồm các bộ ba (r
i
, d
i
, t
i
), I
= 3, 4, … u.trong đó r
i
là thừa số nguyên tố thứ I của modulo RSA n. Với số mũ CRT
d
I
(i = 3, 4,…,u) phải thỏa mãn e.d
i
1 (mod(r
i
Các cơ sở chuyển đổi dữ liệu này sẽ đƣợc sử dụng trong lƣợc đồ mã hóa
RSAES – OAEP. Về mặt toán học thực chất I2OSP và OS2IP là hai song ánh ngƣợc
nhau. Việc chuyển đổi này là quan trọng, vì trên thực tế, đầu vào và đầu ra của quy
trình mã hóa và giải mã thực chất là chỉ là những chuỗi octet, trong khi đó thuật toán
RSA chỉ làm việc trên các số nguyên
Trong thực tế để đảm bảo tính an toàn thuật toán RSA yêu cầu việc xử lý trên
số nguyên rất lớn, chúng nằm ngoài phạm vi biểu diễn của một từ máy, vì vậy ngƣời ta
phải biểu diễn số nguyên trong một cấu trúc dữ liệu nào đó. Vì vậy, các cơ sở chuyển
đổi dữ liệu sẽ làm việc trên chuỗi octet và cấu trúc dữ liệu này.
Ghi chú: một chuỗi octet là một dãy tuần tự của các octet, trong đó mỗi octet
là một byte. Dãy tuần tự đó đƣợc đánh dấu chỉ mục từ octet đầu tiên (leftmost) cho đến
octet cuối cùng (rightmost)
24
2.2.4.1 Chuyển đổi dữ liệu I2OSP
I2OSP chuyển đổi một số nguyên không âm về dạng một chuỗi octet với độ
dài đƣợc chỉ định trƣớc
I2OSP (x, xLen)
INPUT: x số nguyên không âm sẽ đƣợc chuyển đổi
xLen biểu diễn chiều dài của chuỗi octet đầu ra
OUTPUT: X chuỗi octet tƣơng ứng với chiều dài xLen
Lỗi: “số nguyên quá lớn”
Các bước chuyển đổi:
1. Nếu x 256
X
2
…X
xLen
2.2.4.2 Chuyển đổi dữ liệu OS2IP
OS2IP chuyển đổi một chuỗi octet về một số nguyên không âm
OS2IP(X)
INPUT: X chuỗi octet sẽ đƣợc chuyển đổi
OUTPUT: x số nguyên không âm tƣơng ứng
Các bước chuyển đổi:
1. Lấ. y X
1
X
2
…X
xLen
là dãy octet của X từ octet đầu tiên cho tới octet cuối
cùng, lấy x
xLen -i
là giá trị nguyên của octet X
i
với mỗi i: 1 i xLen
2. Tính x = x
xLen – 1
. 256
xLen – 1
+ x
xLen – 2
. 256
OUTPUT:
c biểu diễn bản mã, một số nguyên giữa 0 và n – 1
Lỗi: “biểu diễn thông điệp ngoài giớ hạn”
Giả định: khóa công khai RSA(n, e) hợp lệ
Các bước:
1. Nếu biểu diễn thông điệp m không nằm giữa 0 và n – 2, ra “ biểu diễn thông
điệp nằm ngoài giới hạn” và dừng
2. Tính c = m
e
mod n
3. ra c
Copyright: Tài liệu đại học ©