Khoá luận tốt nghiệp
Mục lục
Ngành: Công nghệ thông tin...................................................................................................1
Lời nói đầu...............................................................................................................................3
..................................................................................................................................................5
Chơng I......................................................................................................................................5
Một số khái niệm cơ sở.............................................................................................................5
1. 1. Kí hiệu và khái niệm......................................................................................................5
d là số nguyên dơng nhỏ nhất sao cho d = e trong , tức là d 1 (mod n). ......................7
1. 2. Logarit rời rạc.....................................................................................................................8
1. 3. Thặng d bậc hai và ký hiệu Legendre..........................................................................8
1. 4. Hàm một phía và hàm cửa sập một phía......................................................................8
1. 5. Thuật toán tính nghịch đảo...........................................................................................9
1. 6. Thuật toán phân tích ra thừa số....................................................................................10
Chơng II..................................................................................................................................11
Vấn đề mã hoá.......................................................................................................................11
2. 1. Đặt vấn đề......................................................................................................................11
2. 2. Khái niệm hệ Mật mã.....................................................................................................11
2. 3. Hệ mật mã RSA...............................................................................................................13
2. 3. 1. Định nghĩa sơ đồ hệ mật mã RSA ...........................................................................................13
2. 3. 2. Xét độ an toàn trong hệ mật mã RSA.......................................................................................14
Chơng III.................................................................................................................................15
Vấn đề ký điện tử................................................................................................................15
3. 1. Khái niệm ký điện tử.....................................................................................................15
3. 2. Sơ đồ chữ ký RSA............................................................................................................17
3. 2. 1. Sơ đồ chữ ký RSA.......................................................................................................................17
3. 2. 2. Chống giả mạo chữ ký .................................................................................................................18
3. 3. Sơ đồ chữ ký điện tử ELGamal.....................................................................................19
3. 3. 1. Sơ đồ chữ ký ELGamal...............................................................................................................19
3. 3. 2. Vấn đề giả mạo chữ ký..............................................................................................................20
3. 3. 3. Vấn đề Phá khóa theo sơ đồ ELGamal.....................................................................................24


Hà Nội 6-2001
Khoá luận tốt nghiệp
4. 1. Chơng trình mã hoá RSA................................................................................................39
4. 2. Chơng trình ký điện tử theo sơ đồ chữ ký RSA.........................................................43
Tài liệu tham khảo...............................................................................................................46
Hoàng Thị Thanh Liễu - K42 C
2
Khoá luận tốt nghiệp
Lời nói đầu
Truyền thông trên mạng đã, đang và sẽ phổ biến trong các hoạt động kinh tế
xã hội. Thông tin đợc truyền đi nhanh chóng, tiện lợi. Ngời ta có thể nói chuyện
với nhau, giải trí cùng nhau, mua bán trao đổi với nhau trên mạng,. . . khi cách xa
nhau hàng trăm ngàn cây số.
Việc mua bán trên mạng đợc thực hiện nh thế nào? Với một giao dịch mua
bán bình thờng, ngời mua và ngời bán xác nhận sự đồng ý mua bán bằng cách ký
tay vào cuối hợp đồng mua bán. Vì bằng cách nào đó ngời ta phải thể hiện đó là chữ
ký của họ và kẻ khác không thể giả mạo. Mọi cách sao chép trên văn bản thờng đều
bị phát hiện vì bản sao dễ bị phân biệt đợc với bản gốc. Mua bán trên mạng cũng đ-
ợc thực hiện theo cách thức tơng tự nh vậy. Nghĩa là ngời gửi và ngời nhận cũng
phải ký vào hợp đồng mua bán. Một số văn bản khác cũng cần phải xác nhận
trách nhiệm của ngời gửi đối với văn bản gửi đi tức là họ phải ký vào văn bản trớc
khi gửi. Nhng ký trên văn bản truyền qua mạng nh thế nào, khi tất cả nội dung
văn bản đều đợc biểu diễn dới dạng số hoá (chỉ dùng hai số 0 và 1 ta gọi văn bản
loại này là văn bản số). Việc giả mạo và sao chép lại đối với văn bản số là hoàn toàn
dễ dàng và không thể phân biệt đợc bản gốc với bản sao. Hơn nữa, một văn bản số
có thể bị cắt dán, lắp ghép là hoàn toàn có thể và ta không thể phân biệt đợc bản gốc
với bản sao. Vậy một chữ ký ở cuối văn bản loại này không thể chịu trách nhiệm
đối với toàn nội dung văn bản. Chữ ký nh thế nào thì mới thể hiện đợc trách nhiệm
đối với toàn bộ văn bản? Chắc chắn chữ ký đó phải đợc ký trên từng bít của văn bản.

Chơng I
Một số khái niệm cơ sở
1. 1. Kí hiệu và khái niệm
* Kí hiệu chia hết:
Cho a và b là hai số nguyên dơng.
- Số a chia hết cho số b ký hiệu là a b Tồn tại n N sao cho a = b*n,
- Khi đó ngời ta nói b là ớc của a và ký hiệu: b | a.
* ớc số chung lớn nhất:
Cho a và b là hai số nguyên dơng.
- Ước số chung lớn nhất của a và b là số tự nhiên m lớn nhất sao cho m | a và m | b.
Khi đó ký hiệu là ƯCLN(a, b) = m.
* Hai số nguyên tố cùng nhau:
Cho a và b là hai số nguyên dơng.
- Số a và số b đợc gọi là 2 nguyên tố cùng nhau ƯCLN (a, b) = 1.
*Đồng d modulo:
Cho n N, n 0 và a, b
*
n
Z
.
Kí hiệu a b (mod n) nghĩa là a đồng d với b theo mod n
tồn tại số nguyên k
*
n
Z
sao cho a = b+k*n
Tức là (a-b) = k*n, nh vậy n | (a-b).
* Một số tính chất của đồng d modulo:
(ab) (mod n) [(a mod n) (b mod n)] (mod n)
(a*b) (mod n) [(a mod n) *(b mod n)] (mod n)

2,
g
3,
.. . , g
n-1
. Khi đó G đợc gọi là nhóm Cyclic hữu
hạn cấp n.
- Phần tử G đợc gọi là có cấp d nếu d là số nguyên dơng nhỏ nhất sao
cho
d
= e. Nó có cấp 1 nếu = e.
Hoàng Thị Thanh Liễu - K42 C
6
Khoá luận tốt nghiệp
Chính vì lẽ trên, nhóm Cyclic còn đợc định nghĩa nh sau:
- Nhóm G đợc gọi là nhóm Cyclic nếu tồn tại số g sao cho mọi phần tử trong
G đều là một luỹ thừa nguyên nào đó của g.
* Nhóm con: Cho G là một nhóm, cho S G và S .
- S đợc gọi là nhóm con của G nếu
1. Phần tử trung lập e của G nằm trong S.
2. S khép kín đối với luật hợp thành trong G (tức là x*y S với mọi x, y S).
3. S khép kín đối với phép lấy nghịch đảo trong G (tức x
-1
S với mọi xS).
* Kí hiệu: Z
n
= {0, 1, 2, .. . , n-1}. Tức Z
n
là tập các số nguyên không âm < n.
Tập này cùng với phép cộng lập thành nhóm Cyclic có phần tử sinh là 1. Đó

thì b

(n)
1 (mod n).
Nếu p là số nguyên tố thì (p) = p-1.
Do đó với mọi b
*
p
Z
(tức b nguyên tố với p)
thì b

(p)
1 (mod n) hay b
p -1
1 (mod n).
- Định lý: Nếu p là số nguyên tố thì
*
p
Z
là nhóm Cyclic.
Chú ý Theo các định nghĩa trên ta có: phần tử
*
n
Z
có cấp d nếu
d là số nguyên dơng nhỏ nhất sao cho
d
= e trong
*


(n)
mod n = 1
- Hệ quả: Với p là một số nguyên tố và (a, p) = 1 thì a
p-1
(mod p) = 1
1. 3. Thặng d bậc hai và ký hiệu Legendre
* Thặng d bậc hai:
Cho p là số nguyên tố lẻ, x là một số nguyên dơng p-1.
x đợc gọi là thặng d bậc hai mod p, nếu phơng trình
y
2
x mod p có lời giải.
* Kí hiệu Legendre:
Cho p là số nguyên tố lẻ, và a là một số nguyên dơng bất kỳ.
ký hiệu Legendre nh sau:
a 0 nếu a 0 mod p
= 1, nếu a là thặng d bậc hai mod p
b 1, trong các trờng hợp còn lại.
1. 4. Hàm một phía và hàm cửa sập một phía.
1. Hàm f(x) đợc gọi là hàm một phía nếu tính y = f(x) thì dễ,
nhng tính x = f
-1
(y) lại rất khó.
Ví dụ: 1. Hàm f(x) =
x
(mod p), với p là số nguyên tố lớn, ( là phần tử nguyên
thuỷ mod p) là hàm một phía.
- Hàm f(x) đợc gọi là hàm cửa sập một phía nếu tính y = f(x) thì dễ,
tính x = f

-1
(mod n) = 1.
2. Nếu biết (n) thì chỉ cần tính: a
-1
a

(n)-1
(mod n)
3. Dùng thuật toán Euclidean mở rộng nh sau:
Đầu vào: b và n.
Đầu ra: - nghịch đảo của b theo mod n nếu tồn tại,
- 0 nếu không tồn tại
Đặt n
0
= n;
b
0
= b;
t
0
= 1;
t
1
= 1;
q = n
0
/b
0
;
r = n

t
1
= t
2
;
n
0
= b
0
;
b
0
= r;
q = n
0
/b
0
;
r = n
0
- q *b
0
;
}
if(b
0
= = 1) return t mod n;
else return 0;
Hoàng Thị Thanh Liễu - K42 C
9

chỉ lệnh trong 1 giây thì thời gian thực
hiện là:
T = n
1/ 2
/2 2
1/2*512
/2 = 2
256
/2 = 2
255
(giây)
2
238
(ngày) 2
230
năm.
(1 ngày = 60*60*24 = 86400 giây 2
17
giây.
1 năm = 30*12*86400 giây = 31104000 giây 2
25
giây.)
Nếu kẻ giả mạo muốn tìm p, q theo cách này thì đây là điều không tởng.
Hoàng Thị Thanh Liễu - K42 C
10
Khoá luận tốt nghiệp
Chơng II
Vấn đề mã hoá
2. 1. Đặt vấn đề
Ta biết rằng tin truyền trên mạng rất dễ bị lấy cắp. Để đảm bảo việc truyền

e
k
: P

C, và một hàm giải mã d
k

D, d
k
: C

P sao cho d
k
(e
k
(x)) = x

x

P.
Hoàng Thị Thanh Liễu - K42 C
11
Khoá luận tốt nghiệp
Đờng đi của thông tin trong sơ đồ mã hoá nh sau:
Ngời gửi G Ngời nhận N

Kẻ tấn công H
Ngời gửi G muốn gửi một văn bản cho ngời nhận N, thay vì gửi văn bản bình
thờng, G mã hoá văn bản đó rồi mới gửi (tất nhiên phải cho ngời nhận biết khoá để
giải mã). Khi ngời N nhận đợc bản mã, họ dùng khoá do G gửi để giải mã thì mới

Hàm giải mã:
d
k
(x) = y
a
mod n
Hình 1: Sơ đồ hệ mật mã RSA
Chú ý: Theo sơ đồ trên, ngời thờng ta chọn b trớc sau đó tính a = b
-1
.

Ví dụ 1
- Chọn p = 109, q = 409 khi đó
n = p*q = 109*409 = 44581,
(n) = (p-1)*(q-1) = 108*408 = 32*27*51 = 44064.
- Chọn b sao cho b nguyên tố với (n) tức là chọn b sao cho b không chia hết cho 2,
3 và 51.
Lấy b = 43*929 = 39947 khi đó a = b
-1
trong (n) a = 13475.
Khi đó phép lập mã và giải mã đợc tính:
e
k
(x) = x
b
mod n = x
39947
mod 44581
d
k

1. P là một tập hữu hạn các văn bản có thể.
2. A là một tập hữu hạn các chữ ký có thể.
3. K là một tập hữu hạn các khoá có thể.
4. S là tập các thuật toán ký.
5. V là tập các thuật toán kiểm thử.
6. Với mỗi K

K, có một thuật toán ký sig
K


S, sig
K
: P

A, và một thuật toán
kiểm thử ver
K


V, ver
K
: P
ì
A


{
đúng, sai
}

K
(x) sao cho ver
K
(x, y) = true.
Khi trộm đợc x, H kiểm tra với mọi y có thể trên x cho đến khi ver
K
(x, y) = true.
Hiện nay có nhiều loại sơ đồ chữ ký, sau đây em xin trình bày một số sơ đồ
chữ ký.
Hoàng Thị Thanh Liễu - K42 C
16
Ngời gửi G
Kẻ tấn công H Kiểm thử
Ngời nhận N
Khoá luận tốt nghiệp
3. 2. Sơ đồ chữ ký RSA
Thuật toán ký phải dựa vào hệ mã hoá bởi vì các thông tin cần đợc ký chắc là
các thông tin phải đợc giữ bí mật hoặc là phải tránh bị tấn công, do đó bản ký và cả
chữ ký đều cần đợc bảo mật. Trên cơ sở một số hệ mật mã, ngời ta đã xây dựng nên
các sơ đồ chữ ký tơng ứng. Sơ đồ chữ ký RSA đợc xây dựng dựa trên hệ mật mã
RSA.
3. 2. 1. Sơ đồ chữ ký RSA
Cho n = p*q với p, q là số nguyên tố lớn. Đặt P = A = Z
n
K= {(n, p, q, a, b): n = p*q, p, q là các số nguyên tố, a*b 1 (mod
(n))}.
Giá trị n và b là công khai, và các giá trị a, p, q là bí mật.
Với mỗi K = (n, p, q, a, b), x P ta định nghĩa:
y = sig
K

N
(x, y) rồi gửi bản mã đến N. Khi N nhận đợc, đầu tiên dùng
hàm giải mã d
N
để đợc x, y sau đó kiểm tra ver
K
(x, y) = true?
b. Trờng hợp G mã hoá x trớc bằng z = e
N
(x) sau đó ký:
y = sig
G
(z) = sig
G
(e
N
(x)).
Tiếp theo gửi cặp (z, y) đến N. N giải mã z đợc x và dùng thuật toán kiểm thử
ver
G
với y để đợc x.
* Giả sử H lấy cắp đợc thông tin trên đờng truyền từ G đến N.
Trong trờng hợp a, H lấy đợc z.
Trong trờng hợp b, H lấy đợc (z, y).
- Nếu muốn tấn công văn bản x thì trong cả hai trờng hợp, H đều phải giải
mã thông tin lấy đợc. Nhng nếu muốn tấn công vào bản ký (để giả mạo) thì sao?
- Trong trờng hợp a, H phải giải mã z thì mới có thể tấn công vào chữ ký.
- Trong trờng hợp b, H sẽ thay chữ ký y của G bởi y = sig
H
(e