Hệ mật mã và sơ đồ chữ ký RSA

Hệ mật mã RSA

Giải thuật RSA là một giải thuật mật mã công khai được phát triển bởi Ron Rivest, Adi Shamir và Leonard Adleman có thể được sử dụng trong công tác mã hoá và công nghệ chữ ký điện tử. Trước hết chúng ta sẽ xem xét cách làm việc của giải thuật này khi áp dụng trong mã hoá. Giả sử rằng Bob muốn nhận được các bản tin được mã hoá như trong hình sau :

Mô hình hệ mật mã khóa công khai

Có hai thành phần liên đới trong RSA:

• Việc lựa chọn khoá công khai và khoá bí mật
• Giải thuật mã hoá và giải mã

Để lựa chọn các khoá công khai và khoá bí mật, Bob phải thực hiện các bước sau đây:

1. Chọn hai số nguyên tố đủ lớn, p và q. Chọn p và q thế nào là đủ lớn? Nếu p, q càng lớn thì càng khó phá vỡ RSA, tuy nhiên thời gian để mã hoá và giải mã sẽ tăng lên đáng kể. Phòng nghiên cứu RSA đề xuất rằng tích của p và q nên là 1024 bit, ngoài ra, tích có thể là 768bit đối với các thông tin ít có giá trị hơn.
2. Tính toán n=pq và z=(p-1)(q-1)
3. Chọn một số, e, nhỏ hơn n sao cho gcd(e, z)=1. e sẽ được sử dụng trong mã hoá.
4. Tìm một số d sao cho ed-1 chia hết cho z. d sẽ được sử dụng để giải mã.
5. Bob công khai khoá K⁺_B, khoá này là cặp số (n,e) và giữ bí mật khoá K^-_B, khoá này là cặp số (n,d)

Việc mã hoá thực hiện bởi Alice và giải mã bởi Bob được hoàn thiện như sau:

Giả sử Alice muốn gửi cho Bob một mẫu bit, hoặc một số m sao cho m<n. Để mã hoá, Alice thực hiện việc luỹ thừa, m^e, sau đó tính toán số dư khi đem chia modulo m^e cho n. Vì vậy, giá trị được mã hoá (c), của bản tin m là:

c=m^e mod n

Để giải mã đoạn tin mã hoá nhận được (c), Bob tính toán:

m=c^d mod n

Việc này đòi hỏi việc sử dụng khoá bí mật (n, d)

Ví dụ:

p=5, q=7 => n=pq=35, z=24.

Bob chọn e=5 vì gcd(5, 24)=1; cuối cùng Bob chọn d=29 vì ed-1 =29.5-1 chia hết cho 24.

Chọn m = 0, 1, 2 ... sinh viên thực hiện quá trình mã hóa và giải mã.

Tại sao giải thuật RSA khả thi?

Để hiểu công việc của giải thuật RSA chúng ta cần thực hiện phép chia modulo n, kết quả của mỗi phép toán được thay thế bởi số dư khi chia cho n. Chúng ta lấy n=pq, trong đó p và q là các số nguyên tố lớn được sử dụng trong giải thuật RSA [2].

Nhắc lại rằng trong mã hoá RSA, một đoạn thông tin (được biểu diễn bởi một số nguyên), m, được luỹ thừa e sử dụng phép toán modulo-n để mã hoá. Giải mã được thực hiện bởi tăng thêm giá trị này lên luỹ thừa d, một lần nữa sử dụng phép toán modulo-n. Kết quả của một bước mã hoá theo sau bởi một bước giải mã là: (m^e)^d. Trong đó:

(m^e)^d mod n = m^ed mod n

Theo giả thiết z=(p-1)(q-1), z|(ed-1), nghĩa là ed = tz+1 (với t size 12{ >= {}} {}1). Do đó:

(m^e)^d size 12{ equiv } {} m^{t(p-1)(q-1)+1} mod n

size 12{ equiv } {} (m^t(p-1)(q-1))m mod n

size 12{ equiv } {} (m^(p-1)(q-1))^tm mod n

size 12{ equiv } {} (m^{φ(n) size 12{φ ( n ) } {}})^tm mod n

size 12{ equiv } {} (1)^tm mod n {Theo định lý Euler}

size 12{ equiv } {} m mod n

size 12{ equiv } {} m.

Bảo mật trong giải thuật RSA

Bảo mật của RSA dựa trên việc chưa tồn tại các giải thuật đủ nhanh để khai triển luỹ thừa một số, trong trường hợp này là khai triển số công khai n thành các số nguyên tố p và q. Nếu ta biết p và q sau đó cộng với việc hiểu biết giá trị e thì chúng ta có thể dễ dàng tính ra d. Do đó bảo mật của RSA tương đương với việc tìm ra giải thuật đủ nhanh để triển khai luỹ thừa một số [2].

Sơ đồ chữ ký RSA

Tương tự như mô hình RSA chúng ta đã xem xét trong phần trên, tuy nhiên Bob sẽ ký vào tài liệu sử dụng khoá bí mật và người nhận sẽ sử dụng khoá công khai để kiểm chứng chữ ký. Nếu tài liệu quá dài chúng ta có thể áp dụng phương pháp chia nhỏ tài liệu, sau đó ký từng đoạn