RSA là một bài toán trong lý thuyết số, được sử dụng trong mã hóa thông tin. Nó được đặt tên theo tên của ba nhà toán học Rivest, Shamir và Adleman, người đã phát minh ra thuật toán RSA vào năm 1977.
Bài toán RSA dựa trên sự phân tích thành thừa số nguyên tố của một số nguyên lớn. Thuật toán này sử dụng hai số nguyên tố lớn p và q để tạo ra một số nguyên tố khác n = p * q, sau đó sử dụng các phép tính số học để tạo ra hai khóa, khóa công khai và khóa bí mật. Khóa công khai được sử dụng để mã hóa thông điệp và chỉ có thể được giải mã bằng khóa bí mật tương ứng. Thuật toán RSA được sử dụng rộng rãi trong các ứng dụng mã hóa, như mật khẩu email, giao dịch tài chính trực tuyến và bảo vệ dữ liệu cá nhân.
Để tóm tắt, bài toán RSA là một bài toán trong lý thuyết số, được sử dụng để mã hóa thông tin bằng cách sử dụng hai số nguyên tố lớn và các phép tính số học để tạo ra các khóa công khai và bí mật. Thuật toán này là một phương pháp mã hóa an toàn và được sử dụng rộng rãi trong các ứng dụng bảo mật thông tin.
Để giải bài toán RSA trong Python, chúng ta cần các bước sau:
- Chọn hai số nguyên tố lớn p và q, tính n = p * q và φ(n) = (p-1) * (q-1).
- Chọn số nguyên e, sao cho 1 < e < φ(n) và e là số nguyên tố cùng nhau với φ(n).
- Tìm số nguyên d, sao cho (d * e) mod φ(n) = 1.
- Khóa công khai là cặp (e, n), khóa bí mật là cặp (d, n).
- Để mã hóa thông điệp, chuyển đổi các ký tự trong thông điệp thành số nguyên tương ứng và tính toán ciphertext bằng cách sử dụng công thức c = m^e mod n.
- Để giải mã ciphertext, tính toán plaintext bằng cách sử dụng công thức m = c^d mod n.
Dưới đây là đoạn mã Python để mã hóa và giải mã thông điệp bằng RSA:
import math
# Hàm tính ước chung lớn nhất
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
# Hàm tính số d
def find_d(e, phi_n):
d = 0
while True:
if (e * d) % phi_n == 1:
return d
d += 1
# Hàm mã hóa thông điệp
def encrypt(m, e, n):
c = pow(m, e, n)
return c
# Hàm giải mã thông điệp
def decrypt(c, d, n):
m = pow(c, d, n)
return m
# Chọn hai số nguyên tố lớn
p = 17
q = 19
# Tính n và phi(n)
n = p * q
phi_n = (p - 1) * (q - 1)
# Chọn số nguyên e
e = 7
# Tính số d
d = find_d(e, phi_n)
# Khóa công khai và khóa bí mật
public_key = (e, n)
private_key = (d, n)
# Mã hóa và giải mã thông điệp
message = "Hello world"
message_ascii = [ord(c) for c in message] # chuyển đổi các ký tự thành mã ASCII
encrypted_message = [encrypt(m, e, n) for m in message_ascii] # mã hóa thông điệp
decrypted_message_ascii = [decrypt(c, d, n) for c in encrypted_message] # giải mã thông điệp
decrypted_message = ''.join([chr(c) for c in decrypted_message_ascii]) # chuyển đổi mã ASCII thành ký tự
# In kết quả
print("Message:", message)
print("Encrypted message:", encrypted_message)
print("Decrypted message:", decrypted_message)
Kết quả sẽ được hiển thị như sau:
Message: Hello world