Mã Hóa RSA - W3seo Tìm Hiểu Kiến Thức Của Mã Hóa Công Khai RSA

Skip to content

Cryptography

Mã hóa RSA Posted on 3 Tháng mười một, 20215 Tháng hai, 2024 by Dục Đoàn Trình Rate this post

Mật mã RSA do ba nhà toán học người Mỹ Ron Rivest, Adi Shamir and Leonard Adleman đưa ra lần đầu vào năm 1977. RSA là thuật toán mật mã khóa công khai nổi tiếng và được phổ biến rộng rãi cho đến tận ngày nay. Cơ sở của nó là phép lũy thừa trên trường Galoa của các số nguyên theo modulo của số nguyên tố lớn. Phép tính lũy thừa có độ phức tạp O((log n)3) là khá dễ so với độ phức tạp của bài toán ngược lại là bài toán logarit rời rạc. Sự an toàn của RSA dựa trên mức độ khó của bài toán phân tích một số lớn ra thừa số và bài toán logarit rời rạc. Bài toán phân tích n ra thừa số có độ phức tạp là: O(elog n log log n). Còn bài toán logarit rời rạc với modulo p là số nguyên tố có độ phức tạp cỡ:

Các bài viết liên quan:

• Lý thuyết số học trong mã hóa
• Meta robots tag: tìm hiểu & kiến thức
• Mã hóa Stream Cipher
• Bài toán rút gọn lũy thừa Module
• Bài toán tính nghịch đảo theo Modulo
• Biểu diễn cho các Relations

Nội dung thuật toán RSA

Để cài đặt thuật toán RSA, người ta chia thành ba giai đoạn riêng biệt là: tạo khoá, mã hoá và giải mã.

Tạo khóa

Người dùng tạo cặp khóa công khai/cá nhân:

Chọn 2 số nguyên tố lớn ngẫu nhiên p ≠ q (>120 chữ số thập phân) Tính số N = p × q, số φ(N) = (p – 1) × (q – 1)

Chọn số e ngẫu nhiên 0 < e < φ(N) sao cho: (e, φ(N)) = 1 Tính số d = e-1 mod φ(N) với 0 < d < φ(N)

Để tính số nghịch đảo d ta có thể sử dụng thuật toán Euclid mở rộng

Khóa công khai là cặp: ku = {e,N} Khóa cá nhân là cặp: kr = {d,N}

Các giá trị d, p, q và φ(N) cần được giữ bí mật

Trong khi đó các giá trị e, N được công bố công khai.

Số e thường nhỏ, có thể dùng chung một giá trị e cho nhiều người. Trước kia người ta thường hay chọn e = 3, bây giờ người ta hay chọn e = 65535. Tuy nhiên, số d tính được thì thường là rất lớn.

Xem thêm Xác thực thông điệp(message authentication) là gì?

Mã hóa

Sử dụng khoá công khai đã tạo ra ở trên để mã hoá thông điệp.

Thông điệp cần mã hoá: M ( 0 < M < N );

Người gửi sử dụng khóa công khai của người nhận ku = {e, N} để mã hoá M;

Tính: C = Me mod N, với 0 < C < N.

Để tính giá trị C ta có thể sử dụng thuật toán bình phương và nhân

C chính là bản mã sẽ được gửi đi cho người nhận

Giải mã

Sử dụng khoá cá nhân để giải mã thông điệp.

Thông điệp cần giải mã là C

Người nhận sử dụng khóa cá nhân của mình kr = {d, N} để giải mã C

Tính: M‟ = Cd mod N, với 0 < M‟ < N

Để tính giá trị M’ ta cũng có thể sử dụng thuật toán bình phương và nhân. Nếu quá trình giải mã thành công thì M’chính là bản nguồn M. Thật vậy:

Theo quá trình tạo khoá của thuật toán RSA thì các số d và e là nghịch đảo của nhau theo mod φ(N), tức là: d = e-1 mod φ(N), khi đó tồn tại số nguyên s sao cho: e × d = 1 + s × φ(N), do đó từ điều kiện mã hoá C = Me ta suy ra Cd = (Me)d = Me×d = M1+s×φ(N) = M × (Mφ(N))s ?= M × (1)s mod N = M.

Nếu ta chứng minh được Mφ(N) = 1 mod N thì chuỗi đẳng thức trên sẽ đúng và ta sẽ có điều phải chứng minh. Xét hai trường hợp có thể xảy ra:

Nếu (M, N) = 1 thì theo định lý Euler ta có: Mφ(N) = 1 mod N (đpcm).

Nếu (M, N) ≠ 1 thì vì N = p × q và p, q là hai số nguyên tố và 0 < M < N nên (M, N) = p hoặc (M, N) = q.

Không mất tính tổng quát giả sử (M, N)= p ? p|M ? M = t × p (với t là số nguyên nào đó) và khi đó: (q, M)=1 ? Mφ(q) = mod q (theo định lý Euler) ? Mφ(q) = 1 + c × q với c là số nguyên ? M × Mφ(q) = M × (1 + c × q) = M + t × p × c × q = M + t × c × N = M mod N

? Mφ(q) = 1 mod N.

Từ đây ta có: Mφ(N) = M(q-1)(p-1) = Mφ(q)×(p-1) = 1(p-1) mod N = 1 mod N (đpcm).

Xem thêm Mã hóa ELGAMAL

Cài đặt thuật toán RSA

Sau đây ta xét ví dụ thuật toán RSA với: p = 7, q =17, e = 11. Chúng ta thực hiện các phép tính sau đây:

• Tính cặp khóa cá nhân và công khai.
• Mã hóa thông điệp M = 20 và sau đó giải mã.
• TẠO KHOÁ: N = p × q = 7 × 17 = 119 φ(N) = (7 – 1) × (17 – 1) = 96

Dùng thuật toán Euclid kiểm tra hai số có nguyên tố cùng nhau hay không: (φ(N), e) = (96, 11) = (11, 8) = (8, 3) = (3, 2) = (2, 1) = 1 OK!

Tính d = e-1 mod φ(N) = 11-1 mod 96

y	q	v
–	96	0
–	11	1
8	8	-8
1	3	9
2	2	-26
1	1	35

Khóa công khai: (e, N) = (11,119) Khóa cá nhân: (d, N) = (35,119)

MÃ HÓA : C = Me mod N = 2011 mod 119

1011	20	1
1	202 = 400 = 43	20 × 1 = 20
1	432 = 1849=64	20 × 43 = 860=27
0	642 = 4096= 50	–
1	–	27 × 50 = 1350 = 41

Xem thêm Birthday attack là gì?

Như vậy giá trị M = 20 đã được mã hoá thành C = 41

GIẢI MÃ: Cd = 4135

100011	41	1
1	412 = 1681 = 15	1 × 41 = 41
1	152 = 225 = -13	41 × 15 = 615 = 20
0	(-13)2=169= 50	–
0	502 = 2500 = 1	–
0	12 = 1	–
1	–	20 × 1= 20

Kết quả giải mã C = 41 nhận được giá trị ban đầu M = 20

Triển khai RSA trên thực tế

An toàn của thuật toán RSA phụ thuộc vào độ khó khăn trong việc tính φ(N) hoặc tính các giá trị p, q – đây là bài toán phân tích N ra thành tích của các thừa số nguyên tố.

Bài toán phân tích N thành các thừa số nguyên tố thực sự là một bài toán khó khăn vì N là một số rất lớn (1024 hoặc 2048 bit) và hơn nữa N có rất ít ước số nguyên tố (hai). Ví dụ khi N là số có 120 chữ số thập phân (400 bit) thì số lượng phép toán cần thiết để phân tích N thành thừa số nguyên tố theo thuật toán Brent – Pollard là 7,7 × 1013, tức là mất khoảng hơn 2 năm thực hiện với một máy tính với tốc độ 1 triệu phép toán trong một giây.

Xem thêm:

• Định tuyến Link state vector
• Mã hóa công khai( public key)
• Mật mã đường cong Ecliptic
• Kiểm tra lỗ hổng bảo mật Weak Encryption
• Lý thuyết số học trong mã hóa
• PGP (Pretty Good Privacy) là gì ?
• SSL ( secure socket layer) là gì
• Bài toán tính nghịch đảo theo Modulo
• Phân phối khóa (Key) trong IP SEC
• Mã hóa ELGAMAL

Khi N có độ dài 200 chữ số thập phân (670 bit), thời gian tính toán sẽ tăng theo cấp số nhân tới gần 1 triệu năm. Trong thực tế, chúng ta sử dụng N có ít nhất 300 chữ số thập phân (1024 bit). Do đó có thể nói, việc thám mã theo cách này là không tưởng.

Trên thực tế, để tính toán với các số lớn, người ta sử dụng các thư viện hàm có sẵn được xây dựng và tích hợp trong các bộ dịch của các ngôn ngữ lập trình. Tuy nhiên, có thể sử dụng vài kỹ thuật tăng tốc cho các tính toán của thuật toán RSA. Ví dụ, thông thường phép nhân sử dụng O(n2) phép tính bit.

Tuy nhiên, thuật toán Schonhage – Strassen rút gọn số phép tính xuống còn O(n × log n). Khi mã hóa, ta tính C = Me với e nhỏ nên thường nhanh, tuy nhiên khi giải mã, cần tính M = Cd với d lớn nên có thể rất lâu. Ở đây, ta có thể dùng định lý số dư Trung Hoa (Chinese Remainder Theorem) để làm nhanh quá trình. Chẳng hạn, với N = p × q nếu tính trực tiếp theo mod N thì sẽ rất lâu, do đó, ta có thể thay nó bởi các phép tính theo mod p và mod q sẽ nhanh hơn nhiều.

Ví dụ. Cần tính: M = Cd mod N, trong đó N = p × q Ta tính như sau (dễ):

Vp = Cd mod p = Cd mod (p-1) mod p (theo định lý Fermat: Cp-1 =1 mod p) Vq = Cd mod q = Cd mod (p-1) mod q

Tiếp theo ta tính:

Xp = q × (q-1 mod p), Xq = p × (p-1 mod q) (Dùng thuật toán Euclid mở rộng)

Theo định lý số dư Trung Hoa: M = (Vp Xp + Vq Xq) mod N Ví dụ: C = 41, d = 35, N = 119, p = 7 và q = 17 ta có:

V7 = 4135 mod 7 = 4135 mod 6 mod 7 = (-1)5 mod 7 = 6

V17 = 4135 mod 17 = 4135 mod 16 mod 7 = 73 mod 17 = 3

X7 = 17 × (17-1 mod 7) = 17 × 5 = 85

X17 = 7 × (7-1 mod 17) = 7 × 5 = 35

M = (V7 X7 + V17 X17) mod 119 = (6 × 85 + 3 × 35) mod 119 = 20.

Ngoài ra, người ta còn có thể kết hợp định lý số dư Trung Hoa với thuật toán Ganner để tăng tốc tính toán.

Khi sử dụng thuật toán RSA trên thực tế, chúng ta còn phải tìm và kiểm tra các số nguyên tố lớn cho các giá trị p và q. Để tăng tốc tính toán, chúng ta có thể sử dụng bộ lọc Fermat hoặc bộ lọc Miller–Rabin để chọn ra các số nguyên tố với độ chính xác từ 75% đến 95%.

Xem thêm 50 + câu hỏi trắc nghiệm về testing software

Một số kiểu tấn công RSA phổ biến:

• Tính khoá d bằng vét cạn: Biết C = Me mod N. Thử lần lượt các giá trị d: 0 < d < φ(N), sao cho: M = Cd mod N; Số lần thử sẽ là φ(N) ≈ N

> 21000 (quá lớn !!!)

• Tìm φ(N): Biết N, e, C = Me. Muốn tính φ(N) phải tính p và q – đây là bài toán phân tích thừa số có độ phức tạp lớn.

• Tìm d: Biết n, e, C = Me và cả M. Tìm trực tiếp d từ công thức: M = Cd mod N – đây là bài toán logarit rời rạc – độ phức tạp cao.

Xem thêm Mã hóa công khai( public key)

Ví dụ code RSA bằng java và python

Đây là ví dụ mã hóa và giải mã thông điệp sử dụng thuật toán RSA bằng Java và Python:

Mã hóa và giải mã RSA bằng Java:

javaCopy codeimport java.math.BigInteger; import java.security.KeyPair; import java.security.KeyPairGenerator; import java.security.NoSuchAlgorithmException; import java.security.PrivateKey; import java.security.PublicKey; import javax.crypto.Cipher; public class RSAExample { public static void main(String[] args) throws Exception { // Generate public and private key pair KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("RSA"); keyPairGenerator.initialize(2048); KeyPair keyPair = keyPairGenerator.generateKeyPair(); PublicKey publicKey = keyPair.getPublic(); PrivateKey privateKey = keyPair.getPrivate(); // The message to be encrypted String message = "Hello World!"; // Encrypt the message using the public key Cipher cipher = Cipher.getInstance("RSA"); cipher.init(Cipher.ENCRYPT_MODE, publicKey); byte[] encrypted = cipher.doFinal(message.getBytes()); System.out.println("Encrypted message: " + new BigInteger(1, encrypted).toString(16)); // Decrypt the message using the private key cipher.init(Cipher.DECRYPT_MODE, privateKey); byte[] decrypted = cipher.doFinal(encrypted); System.out.println("Decrypted message: " + new String(decrypted)); } }

Mã hóa và giải mã RSA bằng Python:

pythonCopy codefrom Crypto.PublicKey import RSA from Crypto.Cipher import PKCS1_OAEP # Generate public and private key pair key = RSA.generate(2048) private_key = key.export_key() public_key = key.publickey().export_key() # The message to be encrypted message = b'Hello World!' # Encrypt the message using the public key cipher = PKCS1_OAEP.new(RSA.import_key(public_key)) encrypted = cipher.encrypt(message) print("Encrypted message:", encrypted.hex()) # Decrypt the message using the private key cipher = PKCS1_OAEP.new(RSA.import_key(private_key)) decrypted = cipher.decrypt(encrypted) print("Decrypted message:", decrypted.decode())

Lưu ý: Để chạy các ví dụ trên, bạn cần phải cài đặt các thư viện liên quan. Trong Java, bạn cần phải cài đặt Java Cryptography Extension (JCE) Unlimited Strength Jurisdiction Policy Files để hỗ trợ khóa có độ dài 2048-bit. Trong Python, bạn cần phải cài đặt pycrypto hoặc pycryptodome để sử dụng các thư viện mã hóa và giải mã RSA.

Xem thêm Các nguyên tắc đếm cơ bản

Một số câu hỏi phổ biến về mã hóa RSA

1. RSA là gì? RSA là một thuật toán mã hóa khóa công khai được phát triển vào năm 1977 bởi Ronald Rivest, Adi Shamir và Leonard Adleman. RSA là viết tắt của tên ba nhà khoa học này.
2. Nguyên lý hoạt động của RSA? RSA dựa trên sự khó giải các bài toán toán học phức tạp như phân tích nhân tích số nguyên tố để mã hóa và giải mã thông điệp. Nguyên tắc hoạt động của RSA như sau:

• Một cặp khóa (public key, private key) được tạo ra bằng cách chọn hai số nguyên tố lớn và tính toán.
• Public key được công bố và private key được giữ bí mật.
• Để mã hóa thông điệp, người gửi sử dụng public key để mã hóa thông điệp.
• Để giải mã thông điệp, người nhận sử dụng private key để giải mã.

3. RSA có những ứng dụng gì? RSA có rất nhiều ứng dụng trong việc bảo mật thông tin truyền tải trên internet. Các ứng dụng của RSA bao gồm:

• Mã hóa dữ liệu truyền tải trên mạng.
• Xác thực người dùng và đảm bảo tính toàn vẹn của dữ liệu.
• Tạo chữ ký số để xác minh tính xác thực và độ tin cậy của tài liệu.

4. Cách tăng độ an toàn của RSA là gì? Cách tăng độ an toàn của RSA bao gồm:

• Tăng độ dài khóa: sử dụng các số nguyên tố lớn hơn để tăng độ an toàn.
• Sử dụng khóa động thay vì khóa tĩnh: tạo ra khóa mới sau mỗi lần sử dụng để giảm khả năng bị tấn công.
• Sử dụng thuật toán mã hóa khác kết hợp với RSA: sử dụng các thuật toán mã hóa khác để tăng độ an toàn.

5. RSA có những hạn chế gì? RSA có những hạn chế sau:

• Độ phức tạp tính toán lớn: do sử dụng các phép tính số học phức tạp, việc mã hóa và giải mã thông điệp trong RSA có độ phức tạp tính toán lớn.
• Sử dụng không gian lưu trữ lớn: việc lưu trữ các khóa công khai và riêng tư trong RSA có thể chiếm nhiều không gian lưu trữ.
• Nguy cơ bị tấn công bằng phương pháp tấn công trung gian (Man-in-the-Middle attack): Kẻ tấn công có thể thay đổi thông điệp truyền tải giữa người gửi và người nhận thông qua việc giả mạo khóa công khai hoặc sử dụng khóa giả mạo để mã hóa thông điệp.
• RSA không thể sử dụng trực tiếp cho việc mã hóa các thông điệp dài.

6. RSA và SSL/TLS SSL/TLS là giao thức bảo mật được sử dụng rộng rãi trong việc bảo mật truyền tải dữ liệu trên internet. RSA được sử dụng trong SSL/TLS để tạo ra các khóa bí mật cho phiên truyền tải. Trong quá trình thiết lập phiên truyền tải SSL/TLS, máy chủ sẽ gửi khóa công khai của mình cho máy khách. Sau đó, máy khách sẽ sử dụng khóa công khai này để mã hóa thông điệp và gửi lại cho máy chủ. Máy chủ sử dụng khóa riêng tư của mình để giải mã thông điệp này. Các khóa bí mật này sẽ được sử dụng để bảo vệ dữ liệu truyền tải trong phiên truyền tải SSL/TLS.

Xem thêm Chữ ký số (digital signatures) là gì?

Hướng dẫn khác:

1. Chữ ký số (Digital Signatures): Khái niệm và Ứng dụng
2. Mã hóa Stream Cipher
3. Bài Toán Tính Nghịch Đảo Theo Modulo
4. Thám mã Mod-n
5. Lý thuyết số Nhóm, vành, trường
6. Lý thuyết số học trong mã hóa
7. Tìm hiểu về mã hóa cổ điển
8. Mã hóa ELGAMAL
9. Thuật toán mã hóa khối(block cipher)- AES
10. Mật mã đường cong Elliptic

Mã hóa công khai( public key) Mã hóa ELGAMAL

Để lại một bình luận Hủy

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Bình luận *

Tên *

Email *

Trang web

Lưu tên của tôi, email, và trang web trong trình duyệt này cho lần bình luận kế tiếp của tôi.

Δ

Có thể bạn quan tâm

• Tối ưu Crawl budget ? những điều cần biết
• Mật mã đường cong Elliptic
• Tập hợp có thứ tự - Ordered Sets
• Cấu trúc Directory trong hệ điều hành
• Bài Toán Tính Nghịch Đảo Theo Modulo
• Test Plan là gì? tìm hiểu test plan trong kiểm thử
• PGP (Pretty Good Privacy) là gì ?
• Logger trong Java: Hướng dẫn chi tiết
• System Testing - kiểm thử hệ thống
• Mã hóa mật mã: các khái niệm cơ bản

Các bài viết cùng chủ đềRing-LWE (Learning With Errors on Rings)Thuật toán BKZ (Block Korkin-Zolotarev)Thuật toán LLL (Lenstra-Lenstra-Lovász)Thuật Toán Kannan: Giới Thiệu và Ứng DụngShortest vector problem (SVP)Cơ sở toán học của lattice trong cryptographyLattice-based key exchangeLattice-based signature schemesLattice-based EncryptionLattice-based cryptography

• Trang chủ
• Dịch vụ
  • Dịch vụ seo chuyên nghiệp
  • Dịch vụ thiết kế website
  • Dịch vụ content marketing
  • Dịch Vụ Bảo Trì Website: Đảm Bảo Sự Ổn Định và An Toàn
  • Dịch vụ hosting giá rẻ
  • Dịch Vụ Làm Video Marketing: Chiến Lược Hiệu Quả Cho Doanh Nghiệp
  • Mobile App
• Marketing
• Lập trình
• Liên Hệ

Call now