Chủ đề này có 1 trả lời

[ngocson52]

Ứng dụng toán học trong mật mã hoá RSA
Copy từ diễn đàn cũ
Tác giả: eiffel

Chào mọi người, chắc hẳn rất nhiều người đã từng nghe qua việc dùng toán học trong mật mã hóa, tuy vậy có thể đã quên, chủ đề này được tạo với mục đích giới thiệu về ứng dụng của toán học trong mật mã hóa, vì trình độ có hạn (hi hi...), nếu có điều gì chưa chính xác, mong mọi người sửa giúp, em xin cảm ơn trước!
Đầu tiên em xin giới thiệu về những khái niệm toán học cần thiết.
- Hàm số Eurler (kí hiệu là φ ): cho n tự nhiên, khi đó φ(n) = số các số tự nhiên nhỏ hơn n và nguyên tố cùng nhau với n. Viết dưới dạng tập hợp:
A = { u| 0 <u < n && (u, n) = 1}
φ(n) = card(A).
- Căn nguyên thủy: cho n tự nhiên, khi đó a được gọi là căn nguyên thủy của n nếu:
(i) 1<a<n
(ii) (a,n)=1
(iii) a^d != 1 (mod n) với mọi 0 <d < φ(n)
- Định lý: cho p nguyên tố, a là một căn nguyên thủy của p, khi đó hàm số f:
f : Z/pZ --> Z/pZ
x --> a^x là 1 song ánh.

Ở đây ta có: Z/pZ là tập hợp p lớp tương đương xây dựng bởi quan hệ đồng dư mod p. Nói nôm na, đó là tập hợp của p tập hợp, trong đó tập hợp thứ i = {n| n = i (mod p)}. Một hàm số f xây dựng như vậy được gọi là hàm mũ đồng dư. Trong trường hợp tổng quát, f được định nghĩa như sau:
f : Z/nZ --> Z/nZ
x --> a^x (mod n)
Cho trước x, a, việc xác định số dư của a^x mod n, tức là tính f(x) là đơn giản và có khả năng. Tuy vậy, việc xác định hàm số ngược của f, nghĩa là cho trước a, n và số dư của a^x khi chia cho n, xác định số dư của x khi chia cho n không phải bao giờ cũng làm được. Điều này chỉ có thể làm được nếu f là 1 song ánh, đó cũng chính là ý nghĩa của định lý này.
Như vậy, việc tìm tất cả các căn nguyên thủy của 1 số cho trước sẽ rất có ý nghĩa. Định lý sau đây giúp chúng ta.
- Định lý : Nếu p nguyên tố, a là một căn nguyên thủy của p, khi đó với mọi b thuộc Z/pZ có thể viết được dưới dạng b = a^i trong đó 0 < i < p-2
Từ định lý này suy ra:
* b là 1 căn nguyên thủy khi và chỉ khi (p-1,i)= 1, hay nói cách khác, tập hợp các căn nguyên thủy của p = {a^i (mod p), (p-1,i)=1}
* Số căn nguyên thủy của p = φ(p-1)
* Nếu ta biết 1 căn nguyên thủy của p, khi đó chúng ta sẽ biết tất cả các căn nguyên thủy của p.

Như vậy, dưới một số điều kiện, hàm số mũ đồng dư x --> a^x (mod n) trong Z/nZ là một song ánh. Cần nhấn mạnh rằng việc tính hàm số ngược của nó thì phức tạp hơn rất nhiều, ngay cả khi chúng ta biết giá trị của a.
Hàm số này là một ví dụ tốt cho một lớp các hàm số mà chúng ta gọi là hàm số "hướng duy nhất":
- đơn giản để tính
- phức tạp để tính ngược lại.
Tuy vậy, hàm số mũ đồng dư có một lợi thế khác, đó là: Chúng ta có thể tính hàm số ngược của nó một cách dễ dàng nếu chúng ta biết một số thông tin dễ dàng trong việc giữ bí mật. Và chính những hàm số này có một ý nghĩa quan trọng trong việc mật mã hóa.

[ngocson52]

Bây giờ chúng ta sẽ cùng tìm hiểu một số phương pháp mã hóa:
I. Chia sẻ chìa khóa:
A và B muốn có chung 1 chìa khóa, họ sẽ chọn:
- p nguyên tố và công khai.
- a căn nguyên thủy của p, a công khai
- Mỗi nguời một số bí mật Xa và Xb với 1 < Xa, Xb < p-1
A sẽ gửi cho B a^Xa (mod p)
B sẽ gửi cho A a^Xb (mod p)
Khi đó, A và B sẽ cùng có chung 1 chìa khóa K = a^(Xa.Xb) (mod p)

II. Mã hóa "không chìa khóa":
Cho 1 thông tin (dưới dạng số) M < p, A cần gửi M cho B
1. A chọn a < p, (a,p-1)=1 (a bí mật)
B chọn b < p, (b,p-1)=1 (b bí mật)
2. A gửi cho B số C = M^a(mod p)
3. B gửi lại cho A số D = C^b (mod p)
4. A tính a' sao cho 0 < a' < p và a.a' = 1 (mod p-1) (a' được gọi là nghịch đảo (mod p-1) của a), sau đó gửi cho B số E = D^a' = C^(b.a') = M^(a.b.a')
5. B tính nghịch đảo b' của b, sau đó tính E^b' = M^(aba'b') = M (mod p) vì aa' = bb' = 1 (mod p-1) và theo định lý nhỏ Fermat, M^(p-1) = 1 (mod p)

III. Mã hóa với chìa khóa công khai
p nguyên tố, p công khai
N người muốn chia sẻ thông tin một cách bí mật, họ sẽ chọn:
a căn nguyên thủy của p (như thế hàm số mũ đông dư của a sẽ là song ánh)
mồi người 1 số bí mật Xn, với 1 < Xn < p-1
Họ công khai Yn = a^Xn (mod p)

Bây giờ giả sử rằng A, B là 2 trong N người, A muốn gửi cho B 1 thông tin M.
1. A chọn k bất kì với 1 < k < p-1
2. A tính K = Yb^k (không có mod p ở đây)
3. A chuyển cho B (a^k, KM) = (C1, C2) (chú ý không có mod p ở đây)
Khi B nhận được cặp số (C1, C2), muốn có M, B sẽ:
1. Tính C1^Xb = a^(k.Xb)= (a^Xb)^k = Yb^k = K
2. Chia C2 cho K nhận được sẽ thu được M.

IV. Hệ thống RSA
Đây là hệ thống mã hóa khá thông dụng hiện nay, lấy tên từ thuật toán RSA, do Rivest, Shamir, Adelman tìm ra vào năm 1977.
Người sử dụng muốn trao đổi thông tin:
- Chọn 2 số nguyên tố p và q
- Tính n = pq
- Chọn d (lớn) và nguyên tố cùng nhau với φ(n) = (p-1)(q-1)
- Tính e nghịch đảo của d mod (p-1)(q-1)
Công khai e và n.
A muốn gửi thông tin M cho B, A sẽ gửi C = M^e (mod n)
B muốn tìm lại M sẽ tính C^d = M^(ed) = M (mod n)

Chú ý rằng thông tin bị che giấu ở đây là hai số p và q, như chúng ta đều biết, cho trước 1 số tự nhiên, việc phân tích thành thừa số nguyên tố đòi hỏi 1 khoảng thời gian rất lớn (với những thuật toán hiện tại). Em không có ví dụ ở đây nên không thể viết bừa, ai có thì post lên hộ em với! Từ đó việc giữ bí mật được đảm bảo.
Em chắc chắn rằng có rất nhiều điều chưa được rõ ràng, mọi người có thể tham khảo ơ đây ạ http://www.muppetlab...ox/txt/rsa.html
Ngoài mật mã RSA còn có rất nhiều các loại mật mã hoá khác như MD5, hy vọng là mọi người có thể viết tiếp. Chúc mọi người vui vẻ!
(eiffel)