Thắc mắc về Hệ mã RSA

Cái “bẻ bit” này thực ra không phải dùng như vậy đâu bạn. Tìm hiểu OAEP nhé.

Ba câu này thuộc về toán học, chỉ cần bạn học Số học nhập môn khoảng 6-7 tuần thì có thể tự trả lời.

1. Nếu p, q không nguyên tố thì không thể tính m như vậy được, vì m (hàm totient) này dựa trên phân tích TSNT. Số bit phải ngang bằng để không thể chia thử được, và đó là một lí do nữa để p, q phải nguyên tố.
2. m sinh ra từ n mà.
3. Bạn phải chọn một số rồi lấy nghịch đảo mod, rồi giữ bí mật một trong hai số.

Thực ra nên dùng hàm Carmichael BCNN(p-1, q-1) thì đúng hơn.

1. p q phải lớn ngang nhau, ngang ở đây là cùng số bit, vd p cần 1024 bit để biểu diễn thì q cũng phải là số có độ lớn 1024 bit. Nếu khác số bit thì bởi vì n = pq công khai mêm chỉ cần tìm p là có thể tìm ra q = n / p. Nếu p 512 bit, q 1536 bit thì tuy n 2048 bit, độ khó để phân tích n thành p q chỉ là 512 bit thay vì 1024 bit. Càng lớn thì phân tích p q càng khó, nhưng lớn quá thì mã hóa chậm đi rất nhiều.
2. Hình như có nhầm lẫn ở đây? (n, e) mới là khóa công khai.
3. Bạn tạo ra được e, d, bạn công khai cả hai thì lấy cái gì để mã hóa… 1 số dùng để mã hóa thì số còn lại để giải mã. Bạn công khai cả hai thì khác gì công khai password email cho mọi người biết…
4. Vì RSA giải mã thông điệp ra thành 1 số nhỏ hơn n = pq, nếu thông điệp mã hóa X đc chuyển sang số lớn hơn n thì Y giải mã ra là (X mod n) < n nên Y < X, hay Y!= X. Vì vậy nên X phải < n.

Định lí Bezout: Hai số nguyên dương có ước chung lớn nhất chia hết m khi và chỉ khi phương trình ax + by = m có nghiệm. Nghĩa là khi tồn tại x, y nguyên sao cho ax + by = 1 thì gcd(a, b) = 1 và ngược lại. Áp dụng well-ordering và tính chất đóng của + trên tập {d \ d = ax + by > 0; x, y ∈ Z} để c/m.

Tại sao RSA cơ bản là như vậy

Tất cả nằm ở phương trình M^(ed) = M (mod n). Vậy tích ed phải bằng 1 với modulo nào đó, mà ai học sơ sơ đại số cũng biết 1 là phần tử trung hòa của nhóm nhân, nhưng nhóm nào?

Đặt S = {x ∈ N \ x < n && gcd(x, n) = 1}. Ta nói rằng phép nhân * mod n là đóng trên tập S, vì theo Bezout, với mỗi hai số a, b ∈ S ta có ngay ax + ny = 1 và bx’ + ny’ = 1. Nhân lại: ab(xx’) + nybx’ + ny’ax + n^2yy’ = 1
<=> ab(xx’) + n(ybx’ + y’ax + nyy’) = 1. Vậy là đủ
Cũng do Bezout nên mỗi phần tử trong S đều có phần tử nghịch đảo (ax + ny = 1, nếu m | x và m | n thì m | 1, vậy m phải bằng 1, huề vốn). Vậy (S, *) đầy đủ các tính chất của một nhóm nhân.

Tính duy nhất. Không mất tính tổng quát chọn m bất kì thuộc S, dễ thấy rằng các tích mr với r ∈ S đều đôi một khác nhau, vì m*r = m*r' (mod n) <=> m(r - r') = 0 (mod n) <=> r = r' (do tính chất của S). Vậy m^|S| * pi(r ∈ S) (r) = pi(r ∈ S) (r) (mod n) (do tính chất đóng), hay m^|S| = 1 (mod n).

Thay |S| = phi(n) = (p-1)(q-1), vậy M^[(p-1)(q-1)] = 1, hay M^[k(p-1)(q-1)+1] = M. Vậy là giải thích xong một tính chất của nhóm nhân mod n.

Đừng nhầm với 1, g, g^2, g^3, … là thuật toán khác

Vậy có thể trả lời:

1. n có thể là bất cứ số tự nhiên nào miễn là đi theo những bước như vậy. Nếu n nguyên tố thì phương trình ed = 1 (mod n-1) quá dễ và thuật toán vứt đi. Nhưng nếu n là hợp số thì phương trình này không có modulo, vậy thì làm sao giải Khi phân tích TSNT thì thừa số càng lớn càng khó tìm, nghĩa là tích hai số nguyên tố là khóa mạnh nhất.
2. đã giải thích ở trên (tức là |S|).
3. d là nghiệm phương trình trên nên phải giấu (chọn một trong hai số để giữ bí mật, số còn lại để công khai)

Để theo dõi thì phải đi từ ước cho tới phần số nguyên tố, mấy bài đầu thôi.

Tính chất đóng có thể chứng minh ntn: Ta có m*gcd(u, v) = gcd(mu, mv) (sử dụng đnghĩa), nên có thể viết: gcd(ab, n) = gcd(ab, n*gcd(a, 1)) = gcd(ab, gcd(an, n)) = gcd(ab, an, n) = gcd(a*gcd(b, n), n) = gcd(a, n) = 1. (SO: https://math.stackexchange.com/a/20904)

Tại sao cần 2 số nguyên tố ?
Vì một số là tích của 2 số nguyên tố thì chỉ được tạo ra bởi đúng 2 số đó: ví dụ : 35 = 7.5 và không có cặp số nào khác thỏa mãn(nguyên). Nhưng 40 thì sao ?? 40 = 10.4 = 5.8 = 20 . 2, bản chất của mã hóa RSA là tạo một cặp private key duy nhất, và dùng nó để sinh pubic key. Dữ liệu sau khi mã hóa CHỈ CÓ THỂ giải mã bằng private key, nên cặp số đó cần duy nhất để đảm bảo an toàn.
Thứ 2, tại sao cần một cặp số nguyên tố đủ lớn ?

image.png721x263 19.5 KB

image.png1366x768 260 KB