Hệ Mã RSA - .vn

Khái niệm hệ mật mã RSA

Khái niệm hệ mật mã RSA đã được ra đời năm 1976 bởi các tác giả R.Rivets, A.Shamir, và L.Adleman. Hệ mã hoá này dựa trên cơ sở của hai bài toán :

+ Bài toán Logarithm rời rạc (Discrete logarith)

+ Bài toán phân tích thành thừa số.

Trong hệ mã hoá RSA các bản rõ, các bản mã và các khoá (public key và private key) là thuộc tập số nguyên ZN = {1, . . . , N-1}. Trong đó tập ZN với N=p×q là các số nguyên tố khác nhau cùng với phép cộng và phép nhân Modulo N tạo ra modulo số học N.

Khoá mã hoá EKB là cặp số nguyên (N,KB) và khoá giải mã Dkb là cặp số nguyên (N,kB), các số là rất lớn, số N có thể lên tới hàng trăm chữ số.

Các phương pháp mã hoá và giải mã là rất dễ dàng.

Công việc mã hoá là sự biến đổi bản rõ P (Plaintext) thành bản mã C (Ciphertext) dựa trên cặp khoá công khai KB và bản rõ P theo công thức sau đây :

C = EKB(P) = EB(P) = PKB (mod N) . (1)

Công việc giải mã là sự biến đổi ngược lại bản mã C thành bản rõ P dựa trên cặp khoá bí mật kB , modulo N theo công thức sau :

P = DkB(C) = DB(C) = CkB (mod N) . (2)

Dễ thấy rằng, bản rõ ban đầu cần được biến đổi một cách thích hợp thành bản mã, sau đó để có thể tái tạo lại bản rõ ban đầu từ chính bản mã đó :

P = DB(EB(P)) (3)

Thay thế (1) vào (2) ta có :

(PKB)kB = P (mod N ) (4)

Trong toán học đã chứng minh được rằng, nếu N là số nguyên tố thì công thức (4) sẽ có lời giải khi và chỉ khi KB.kB = 1 (mod N-1), áp dụng thuật toán ta thấy N=p×q với p, q là số nguyên tố, do vậy (4) sẽ có lời giải khi và chỉ khi :

KB.kB size 12{ equiv } {} 1 (mod γ size 12{γ} {}(N)) (5)

trong đó γ size 12{γ} {} (N) = {} LCM(p-1,q-1) .

LCM (Lest Common Multiple) là bội số chung nhỏ nhất.

Nói một cách khác, đầu tiên người nhận B lựa chọn một khoá công khai KB một cách ngẫu nhiên. Khi đó khoá bí mật kB được tính ra bằng công thức (5). Điều này hoàn toàn tính được vì khi B biết được cặp số nguyên tố (p,q) thì sẽ tính được (N).