Trong mật mã học, RSA là một thuật toán mật mã
hóa khóa công khai. Đây là thuật
toán đầu tiên phù hợp với việc tạo ra chữ ký điện
tử đồng thời với việc mã hóa. Nó
đánh dấu một sự tiến bộ vượt bậc của lĩnh vực mật
mã học trong việc sử dụng khóa
công cộng. RSA đang được sử dụng phổ biến trong
thương mại điện tử và được
cho là đảm bảo an toàn với điều kiện độ dài khóa
đủ lớn.
Thuật toán được Ron Rivest, Adi Shamir và Len
Adleman mô tả lần đầu tiên vào
năm 1977 tại Học viện Công nghệ Massachusetts
(MIT). Tên của thuật toán lấy từ
3 chữ cái đầu của tên 3 tác giả.
Trước đó, vào năm 1973, Clifford Cocks, một nhà
toán học người Anh làm việc tại
GCHQ, đã mô tả 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 thực nghiệm. Tuy nhiên,
phát minh này chỉ được công bố vào năm 1997 vì
được xếp vào loại tuyệt mật.
Thuật toán RSA được MIT đăng ký bằng sáng chế tại
Hoa Kỳ vào năm 1983 (Số
đăng ký 4,405,829). Bằng sáng chế này hết hạn
vào ngày 21 tháng 9 năm 2000.
Tuy nhiên, do thuật toán đã được công bố trước
khi có đăng ký bảo hộ nên sự bảo
hộ hầu như không có giá trị bên ngoài Hoa Kỳ.
Ngoài ra, nếu như công trình của
Clifford Cocks đã được công bố trước đó thì bằng
sáng chế RSA đã không thể
được đăng ký.
1. Thuật
toán RSA
1.1 Thuật toán
1.1 Thuật toán
Giả sử Alice và Bob
cần trao đổi thông tin bí mật thông qua một kênh không an toàn (ví dụ như Internet). Với thuật toán RSA, Alice đầu tiên cần tạo
ra cho mình cặp khóa gồm khóa công khai và khóa bí mật theo các bước sau:
1. Chọn 2 số nguyên tố lớn p và q với p != q, lựa chọn ngẫu
nhiên và độc lập
2. Tính: n = pq
3. Tính: giá trị hàm số Ơle:
4. Chọn một số tự nhiên e sao cho
và
là số nguyên tố cùng nhau với
5. Tính: d sao cho
Một số lưu ý:
·
Các số nguyên tố
thường được chọn bằng phương pháp thử xác suất.
·
Các bước 4 và 5 có thể
được thực hiện bằng giải thuật Euclid mở rộng (xem thêm: số học môđun).
·
Bước 5 có thể viết
cách khác: Tìm số tự nhiên x sao cho
cũng
là số tự nhiên. Khi đó sử dụng giá trị
.
·
Từ bước 3, PKCS#1 v2.1
sử dụng thay
cho
.
Khóa công khai bao gồm:
• n, môđun, và
• e, số mũ công khai (cũng gọi là số mũ mã hóa).
Khóa bí mật bao gồm:
• n, môđun, xuất hiện cả trong khóa công khai và khóa bí mật, và
• d, số mũ bí mật (cũng gọi là số mũ giải mã).
Một dạng khác của khóa bí mật bao gồm: p and q, hai số nguyên tố chọn ban đầu,
d mod (p-1) và d mod (q-1) (thường được gọi là dmp1 và dmq1), (1/q) mod p (thường được gọi là iqmp).
Dạng này cho phép thực hiện giải mã và ký nhanh hơn với việc sử dụng định lý số
dư Trung Quốc. Ở dạng này, tất cả thành phần của khóa bí mật phải được giữ bí
mật.
A gửi khóa công khai cho B và giữ bí mật khóa cá nhân của mình. Ở đây, p và q
giữ vai trò rất quan trọng. Chúng là các phân tố của n và cho phép tính d khi biết e.
Nếu không sử dụng dạng sau của khóa bí mật (dạng CRT) thì p và q sẽ được xóa
ngay sau khi thực hiện xong quá trình tạo khóa.
• n, môđun, và
• e, số mũ công khai (cũng gọi là số mũ mã hóa).
Khóa bí mật bao gồm:
• n, môđun, xuất hiện cả trong khóa công khai và khóa bí mật, và
• d, số mũ bí mật (cũng gọi là số mũ giải mã).
Một dạng khác của khóa bí mật bao gồm: p and q, hai số nguyên tố chọn ban đầu,
d mod (p-1) và d mod (q-1) (thường được gọi là dmp1 và dmq1), (1/q) mod p (thường được gọi là iqmp).
Dạng này cho phép thực hiện giải mã và ký nhanh hơn với việc sử dụng định lý số
dư Trung Quốc. Ở dạng này, tất cả thành phần của khóa bí mật phải được giữ bí
mật.
A gửi khóa công khai cho B và giữ bí mật khóa cá nhân của mình. Ở đây, p và q
giữ vai trò rất quan trọng. Chúng là các phân tố của n và cho phép tính d khi biết e.
Nếu không sử dụng dạng sau của khóa bí mật (dạng CRT) thì p và q sẽ được xóa
ngay sau khi thực hiện xong quá trình tạo khóa.
Mã hóa và giải mã
Mã hóa
Giả sử B muốn gửi đoạn thông tin M cho A. Đầu tiên B chuyển M thành một số m < n theo một hàm có thể đảo ngược (từ m có thể xác định lại M) được thỏa thuận trước. Lúc này B có m và biết n cũng như e do A gửi, B sẽ tính c là bản mã hóa của m theo công thức:
Hàm trên có thể tính dễ dàng sử dụng phương pháp tính hàm mũ (theo môđun) bằng
thuật toán bình phương và nhân. Cuối cùng B gửi c cho A.Giả sử B muốn gửi đoạn thông tin M cho A. Đầu tiên B chuyển M thành một số m < n theo một hàm có thể đảo ngược (từ m có thể xác định lại M) được thỏa thuận trước. Lúc này B có m và biết n cũng như e do A gửi, B sẽ tính c là bản mã hóa của m theo công thức:
Giải
mã
A nhận c từ B và biết khóa bí mật d. A có thể tìm được m từ c
theo công thức sau:
Biết m, A tìm lại M theo phương pháp đã thỏa thuận trước.
Quá trình giải mã hoạt động như sau
Ta có:
Do ed ≡ 1 (mod p-1) và ed ≡ 1 (mod q-1), (theo định lý Fermat nhỏ) nên:
và
Do p và q là hai số nguyên tố cùng nhau, áp dụng
định lý Thặng dư Trung Hoa, ta có:
hay:
1.2
Các định lý cơ sở
a) Định
lý nhỏ của Fermat:
Với
p là một số nguyên tố khác 2 thì chia một số a lũy thừa p cho p sẽ có số dư chính
bằng a:
Mở
rộng ta có:
Với Φ(m) là số nguyên tố cùng nhau với m và nhỏ hơn m
b)
Định lý Thặng dư Trung Hoa:
Cho hệ phương trình đồng
dư bậc nhất
trong đó m1, m2,... đôi
một nguyên tố cùng nhau
Định lý
Hệ
phương trình đồng dư nói trên có nghiệm duy nhất theo mođun
Là:
trong đó
Áp dụng
trường hợp đặc biệt:
Cho p và q là 2 số nguyên tố cùng nhau.
Nếu a= b (mod p)
và a = b (mod q)
thì a= b (mod pq)
Cho p và q là 2 số nguyên tố cùng nhau.
Nếu a= b (mod p)
và a = b (mod q)
thì a= b (mod pq)
Ví dụ:
Lấy 2 số nguyên tố khác nhau p, q:
Lấy 2 số nguyên tố khác nhau p, q:
p = 11
q = 13
Ta tính được số module N là:
N= pq = 11 * 13 = 143
Giá trị hàm số Ơ le là:
Φ(n)= (p-1) * (q-1) = 10 * 12 = 120
e là số nguyên tố cùng nhau với Φ(n)
e = 17
Tìm d sao cho
ed = 1 (mod Φ(n))
<=> 17 * d = 1 (mod 120)
=> d = 113
vì
7 * 113 = 1921 = 16 * 120 + 1 = 1 (mod 120)
Khóa công khai là cặp (e, n). Khóa bí mật là d. Hàm mã hóa là:
c = encrypt(m) =
với m là văn bản rõ. Hàm giải mã là:q = 13
Ta tính được số module N là:
N= pq = 11 * 13 = 143
Giá trị hàm số Ơ le là:
Φ(n)= (p-1) * (q-1) = 10 * 12 = 120
e là số nguyên tố cùng nhau với Φ(n)
e = 17
Tìm d sao cho
ed = 1 (mod Φ(n))
<=> 17 * d = 1 (mod 120)
=> d = 113
vì
7 * 113 = 1921 = 16 * 120 + 1 = 1 (mod 120)
Khóa công khai là cặp (e, n). Khóa bí mật là d. Hàm mã hóa là:
c = encrypt(m) =
m = decrypt(c) = với c là văn bản mã.
Để mã hóa văn bản có giá trị m = 50 và có cặp khóa công khai (e,n) là (17,143) ta tính:
encrypt(50) = Để giải mã văn bản có giá trị c=545 và cặp khóa bí mật (d,n) là (113,1435) ta tính:
decrypt(85) = Cả hai phép tính trên đều có thể được thực hiện hiệu quả nhờ giải thuật bình phương và nhân.
Trao đổi khóa bất đối xứng
2. Tạo chữ ký số
2.1 Giới thiệu chung
2.1 Giới thiệu chung
Ngày nay, có ba hệ mã hóa thông dụng được sử dụng
để xây dựng các lược đồ ký điện tử,
đó là hệ mã hóa RSA, hệ mã hóa dựa trên bài toán logarit rời rạc và hệ mã hóa dựa trên đường cong elliptic. Các
hàm một chiều sử dụng trong các hệ mã này hiện
đang được xem là an toàn theo thừa nhận (tức là không có thuật toán nào hữu hiệu để tính hàm ngược của chúng). Tuy
nhiên, một vấn đề cơ bản của tính an toàn đối
với một lược đồ ký điện tử lại là tính không thể giả mạo được chữ ký và điều này không suy ra được trực tiếp từ
tính an toàn của hệ mã mà nó dựa vào. Trong khoảng
mười năm gần đây, vấn đề này đang thu hút rất nhiều sự quan tâm của cộng đồng mật mã trên thế giới. Người ta
đang cố gắng đưa ra những lược đồ ký sao cho tính
không thể giả mạo được của nó có thể được đánh giá thông qua độ an toàn của các hàm một chiều mà nó sử dụng. Trong
bài này mình xem xét một số lược đồ ký
sử dụng hàm một chiều của hệ mã RSA (đang được xem là phổ biến nhất hiện nay).
Giả sử A muốn gửi cho B một văn bản có chữ ký của
mình. Để làm việc này, A tạo ra một
giá trị băm (hash value) của văn bản cần ký và tính giá trị mũ d mod n của nó (giống như khi A thực hiện giải
mã). Giá trị cuối cùng chính là chữ ký điện tử của văn bản đang xét. Khi B nhận được
văn bản cùng với chữ ký điện tử, anh ta tính
giá trị mũ e mod n của chữ ký đồng thời với việc tính giá trị băm của văn bản. Nếu 2 giá trị này như nhau thì B biết
rằngngười tạo ra chữ ký biết khóa bí mật của A
và văn bản đã không bị thay đổi sau khi ký.Ký điện tử và những mô hình nguyên
thủy.
2.2 Hàm băm mật mã
Người ta thường sử dụng sự hỗ trợ của các hàm băm
mật mã trong quá trình Encoding của
các lược đồ ký. Một hàm băm với đầu vào là văn bản (có độ dài bất
kỳ), sinh ra cho ta xâu H có độ dài xác định, được gọi là mã băm của . Hàm băm mật mã h phải thỏa mãn các điều kiện sau:
• Là hàm một chiều: Tức là nếu cho ta sẽ dễ dàng tính ra H=h(M) . Nhưng nếu chỉ có mã băm H thì rất khó có thể tìm được văn bản M sao cho H=h(M) (rất khó có nghĩa là hiện nay không có thuật toán hữu hiệu nào làm được).
• Không tìm được xung đột: Tức là rất khó để tìm ra hai văn bản M và M’ có cùng mã băm.
• Không tìm được xung đột của văn bản cho trước: Tức là cho trước văn bản M thì rất khó để tìm được văn bản M’có cùng mã băm với văn bản M đó. Trong thực tế rất khó có thể tìm ra được một hàm băm thỏa mãn nghiêm ngặt các tính chất trên. Hiện nay, ngày càng có những kết quả thám mã mạnh tấn công vào tính chất thứ hai. Cho nên, các lược đồ ký gần đây thường cố gắng tránh việc dựa trực tiếp vào tính chất này.
kỳ), sinh ra cho ta xâu H có độ dài xác định, được gọi là mã băm của . Hàm băm mật mã h phải thỏa mãn các điều kiện sau:
• Là hàm một chiều: Tức là nếu cho ta sẽ dễ dàng tính ra H=h(M) . Nhưng nếu chỉ có mã băm H thì rất khó có thể tìm được văn bản M sao cho H=h(M) (rất khó có nghĩa là hiện nay không có thuật toán hữu hiệu nào làm được).
• Không tìm được xung đột: Tức là rất khó để tìm ra hai văn bản M và M’ có cùng mã băm.
• Không tìm được xung đột của văn bản cho trước: Tức là cho trước văn bản M thì rất khó để tìm được văn bản M’có cùng mã băm với văn bản M đó. Trong thực tế rất khó có thể tìm ra được một hàm băm thỏa mãn nghiêm ngặt các tính chất trên. Hiện nay, ngày càng có những kết quả thám mã mạnh tấn công vào tính chất thứ hai. Cho nên, các lược đồ ký gần đây thường cố gắng tránh việc dựa trực tiếp vào tính chất này.
2.3 Tạo chữ ký số:
Quá trình tạo CKS
2.4 Thẩm định chữ
ký số:
Quá trình
thẩm định CKS
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).
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ã hoá 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.
Trên
thực tế, ta thường gặp 2 vấn đề đầu khi gửi các bản tin ASCII ngắn với m là nhóm
vài ký tự ASCII. Một đoạn tin chỉ có 1 ký tự NUL sẽ được gán giá trị m = 0 và
cho ra bản mã là 0 bất kể giá trị của e và N. Tương tự, một ký tự ASCII khác, SOH,
có giá trị 1 sẽ luôn cho ra bản mã là 1. Với các hệ thống dùng giá trị e nhỏ
thì tất cả ký tự ASCII đều cho kết quả mã hóa không an toàn vì giá trị lớn nhất
của m chỉ là 255 và 2553 nhỏ hơn giá trị n chấp nhận được. Những bản mã này sẽ
dễ dàng bị phá mã.
Để tránh gặp phải những vấn đề trên, RSA trên thực tế thường bao gồm một hình thức chuyển đổi ngẫu nhiên hóa m trước khi mã hóa. Quá trình chuyển đổi này phải đảm bảo rằng m không rơi vào các giá trị không an toàn. Sau khi chuyển đổi, mỗi bản rõ khi mã hóa sẽ cho ra một trong số khả năng trong tập hợp bản mã. Điều này làm giảm tính khả thi của phương pháp tấn công lựa chọn bản rõ (một bản rõ sẽ có thể tương ứng với nhiều bản mã tuỳ thuộc vào cách chuyển đổi).
Một
số tiêu chuẩn, chẳng hạn như PKCS, đã được thiết kế để chuyển đổi bản rõ trước
khi mã hóa bằng RSA. Các phương pháp chuyển đổi này bổ sung thêm bít vào M. Các
phương pháp chuyển đổi cần được thiết kế cẩn thận để tránh những dạng tấn công
phức tạp tận dụng khả năng biết trước được cấu trúc của bản rõ.
Phiên bản ban đầu của
PKCS dùng một phương pháp đặc ứng (ad-hoc) mà về sau được biết là không an toàn
trước tấn công lựa chọn bản rõ thích ứng (adaptive chosen ciphertext attack).
Các phương pháp chuyển đổi hiện đại sử dụng các kỹ thuật như chuyển đổi mã hóa
bất đối xứng tối ưu (Optimal Asymmetric Encryption Padding - OAEP) để chống lại
tấn công dạng này. Tiêu chuẩn PKCS còn được bổ sung các tính năng khác để đảm bảo
an toàn cho chữ ký RSA (Probabilistic Signature Scheme for RSA – RSA - PSS).
Comments
Post a Comment