Lập trình C/C++, Lập trình Python

Thuật toán mã hóa khóa công khai RSA

Posted on by Đỗ Thành
04
Th4
View: 65

Giới thiệu thuật toán RSA

Thuật toán RSA là một thuật toán mã hóa khóa công khai (Public Key Cryptography) được phát triển bởi Ronald Rivest, Adi Shamir và Leonard Adleman vào năm 1977. Thuật toán RSA dựa trên việc tính toán trên số nguyên tố lớn (RSA là viết tắt của tên ba nhà toán học Ron Rivest, Adi Shamir và Leonard Adleman).

Thuật toán RSA được sử dụng để mã hóa và giải mã thông tin trên mạng. Nó sử dụng hai khóa khác nhau để mã hóa và giải mã dữ liệu, bao gồm khóa công khai và khóa bí mật.

Khóa công khai được sử dụng để mã hóa dữ liệu, trong khi khóa bí mật được sử dụng để giải mã dữ liệu đã được mã hóa. Khóa công khai được công khai cho tất cả mọi người, trong khi khóa bí mật được giữ bí mật chỉ cho người sở hữu.

Thuật toán RSA hoạt động dựa trên tính năng của việc tìm kiếm hai số nguyên tố lớn và tính toán trên chúng. Sự an toàn của thuật toán RSA phụ thuộc vào khả năng tìm kiếm các số nguyên tố lớn, vì việc phá mã RSA đòi hỏi phải tìm được các số nguyên tố lớn này.

Thuật toán RSA đã được sử dụng rộng rãi trong các ứng dụng bảo mật, bao gồm mã hóa email và truyền thông an toàn trên mạng.

Các bước thực hiện Thuật toán RSA

Các bước thực hiện thuật toán RSA như sau:

  1. Chọn hai số nguyên tố lớn khác nhau p và q. Tính n = p*q.

  2. Tính Euler totient của n: φ(n) = (p-1)*(q-1).

  3. Chọn số nguyên e sao cho 1 < e < φ(n) và e là số nguyên tố cùng nhau với φ(n).

  4. Tính d sao cho d*e ≡ 1 (mod φ(n)). Đây là quá trình tìm nghịch đảo modular của e.

  5. Khóa công khai sẽ là cặp (e, n), và khóa bí mật sẽ là cặp (d, n).

  6. Để mã hóa một tin nhắn M, sử dụng khóa công khai (e, n) để tính M^e mod n.

  7. Để giải mã một tin nhắn đã được mã hóa C, sử dụng khóa bí mật (d, n) để tính C^d mod n.

Trong quá trình mã hóa và giải mã, các phép tính modulo n sẽ được sử dụng để đảm bảo rằng kết quả cuối cùng sẽ nằm trong khoảng từ 0 đến n-1.

Với các giá trị khóa công khai và khóa bí mật được chọn đúng cách, thuật toán RSA đảm bảo tính bảo mật của thông tin được mã hóa và giải mã trên mạng.

Cài đặt Thuật toán RSA với Python

import random

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def is_prime(num):
    if num < 2:
        return False
    elif num == 2:
        return True
    elif num % 2 == 0:
        return False
    else:
        for i in range(3, int(num**0.5)+1, 2):
            if num % i == 0:
                return False
        return True

def generate_keypair(p, q):
    if not (is_prime(p) and is_prime(q)):
        raise ValueError("Both numbers must be prime.")
    elif p == q:
        raise ValueError("p and q cannot be equal")

    n = p * q
    phi = (p - 1) * (q - 1)

    e = random.randrange(1, phi)

    g = gcd(e, phi)
    while g != 1:
        e = random.randrange(1, phi)
        g = gcd(e, phi)

    d = multiplicative_inverse(e, phi)

    return ((e, n), (d, n))

def multiplicative_inverse(e, phi):
    d = 0
    x1 = 0
    x2 = 1
    y1 = 1
    temp_phi = phi

    while e > 0:
        temp1 = temp_phi // e
        temp2 = temp_phi - temp1 * e
        temp_phi = e
        e = temp2

        x = x2 - temp1 * x1
        y = d - temp1 * y1

        x2 = x1
        x1 = x
        d = y1
        y1 = y

    if temp_phi == 1:
        return d + phi

def encrypt(pk, plaintext):
    key, n = pk
    cipher = [(ord(char) ** key) % n for char in plaintext]
    return cipher

def decrypt(pk, ciphertext):
    key, n = pk
    plain = [chr((char ** key) % n) for char in ciphertext]
    return ''.join(plain)

if __name__ == '__main__':
    p = int(input("Nhập số nguyên tố (17, 19, 23, etc): "))
    q = int(input("Nhập một số nguyên tố khác (Không phải số bạn đã nhập ở trên): "))
    public, private = generate_keypair(p, q)
    print("Khóa chung của bạn là ", public, " và private của bạn là ", private)

    message = input("Nhập tin nhắn để mã hóa bằng khóa riêng của bạn: ")
    encrypted_msg = encrypt(private, message)
    print("Tin nhắn được mã hóa của bạn là: ")
    print(''.join(map(lambda x: str(x), encrypted_msg)))
    print("Giải mã tin nhắn bằng khóa công khai ", public, " . . .")
    print("Tin nhắn của bạn là:")
    print(decrypt(public, encrypted_msg))

Chú thích cho từng hàm:

  • gcd(a, b): Tính ước chung lớn nhất của hai số a và b.
  • is_prime(num): Kiểm tra xem một số num có phải là số nguyên tố hay không.
  • generate_keypair(p, q): Tạo cặp khóa công khai và khóa bí mật dựa trên hai số nguyên tốt là hai số nguyên tố p và q. Hàm này sẽ trả về một tuple gồm hai tuple, mỗi tuple chứa hai giá trị: khóa công khai và khóa bí mật.
  • multiplicative_inverse(e, phi): Tính nghịch đảo nhân modulo của hai số e và phi.
  • encrypt(pk, plaintext): Mã hóa một chuỗi văn bản đơn giản plaintext bằng cách sử dụng khóa bí mật pk. Kết quả trả về là một danh sách các giá trị số nguyên, mỗi giá trị là kết quả mã hóa cho một ký tự trong chuỗi plaintext.
  • decrypt(pk, ciphertext): Giải mã một danh sách các giá trị số nguyên ciphertext bằng cách sử dụng khóa công khai pk. Kết quả trả về là một chuỗi văn bản đơn giản.

Trong hàm main, người dùng sẽ được yêu cầu nhập hai số nguyên tố p và q, sau đó thuật toán sẽ tạo cặp khóa bằng cách sử dụng hàm generate_keypair. Sau đó, người dùng sẽ được yêu cầu nhập một chuỗi văn bản đơn giản và thuật toán sẽ mã hóa và giải mã chuỗi này sử dụng các hàm encrypt và decrypt.

Lưu ý rằng đây chỉ là một ví dụ đơn giản, không hoàn toàn phù hợp với mục đích thực tế. Nếu muốn sử dụng thuật toán RSA để bảo vệ dữ liệu của mình, bạn nên tìm hiểu thêm về cách triển khai thuật toán này một cách an toàn và chính xác.

Cài đặt Thuật toán RSA với C++

#include <iostream>
#include <cstdlib>
#include <cmath>

using namespace std;

// Hàm kiểm tra tính nguyên tố của một số
bool is_prime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

// Hàm tìm ước số chung lớn nhất của hai số
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

// Hàm tính nghịch đảo modulo
int multiplicative_inverse(int e, int phi) {
    int d = 0;
    int x1 = 0;
    int x2 = 1;
    int y1 = 1;
    int temp_phi = phi;
    while (e > 0) {
        int temp1 = temp_phi / e;
        int temp2 = temp_phi - temp1 * e;
        temp_phi = e;
        e = temp2;
        int x = x2 - temp1 * x1;
        int y = d - temp1 * y1;
        x2 = x1;
        x1 = x;
        d = y1;
        y1 = y;
    }
    if (temp_phi == 1) {
        return d + phi;
    }
    return 0;
}

// Hàm tạo khóa
void generate_keypair(int p, int q, int &n, int &e, int &d) {
    if (!is_prime(p) || !is_prime(q)) {
        cerr << "p hoặc q không phải số nguyên tố" << endl;
        exit(1);
    }
    if (p == q) {
        cerr << "p và q phải khác nhau" << endl;
        exit(1);
    }
    n = p * q;
    int phi = (p - 1) * (q - 1);
    e = 0;
    for (int i = 2; i < phi; i++) {
        if (gcd(i, phi) == 1) {
            e = i;
            break;
        }
    }
    if (e == 0) {
        cerr << "Không tìm thấy e phù hợp" << endl;
        exit(1);
    }
    d = multiplicative_inverse(e, phi);
}

// Hàm mã hóa
int encrypt(int m, int e, int n) {
    int c = 1;
    for (int i = 0; i < e; i++) {
        c = (c * m) % n;
    }
    return c;
}

// Hàm giải mã
int decrypt(int c, int d, int n) {
    int m = 1;
    for (int i = 0; i < d; i++) {
        m = (m * c) % n;
    }
    return m;
}

int main() {
    int p, q;
    cout << "Nhập số nguyên tố p: ";
    cin >> p;
    cout << "Nhập số nguyên tố q: ";
    cin >> q;

   int e, d;
   generate_keypair(p, q, n, e, d);

   cout << "Khóa công khai: (" << e << ", " << n << ")" << endl;
   cout << "Khóa bí mật: (" << d << ", " << n << ")" << endl;

   int m;
   cout << "Nhập thông điệp cần mã hóa: ";
   cin >> m;

   int c = encrypt(m, e, n);
   cout << "Thông điệp đã mã hóa: " << c << endl;

   int plaintext = decrypt(c, d, n);
   cout << "Thông điệp đã giải mã: " << plaintext << endl;

return 0;

}

Trong đó:

  • is_prime(n) là hàm kiểm tra tính nguyên tố của một số n.
  • gcd(a, b) là hàm tìm ước số chung lớn nhất của hai số a và b.
  • multiplicative_inverse(e, phi) là hàm tính nghịch đảo modulo của số e và phi.
  • generate_keypair(p, q, n, e, d) là hàm tạo khóa công khai và khóa bí mật dựa trên hai số nguyên tố p và q.
  • encrypt(m, e, n) là hàm mã hóa một thông điệp m bằng khóa công khai (e, n).
  • decrypt(c, d, n) là hàm giải mã một thông điệp đã được mã hóa c bằng khóa bí mật (d, n).

Sau khi chạy chương trình, bạn sẽ nhập vào hai số nguyên tố p và q, sau đó chương trình sẽ tạo khóa và cho phép bạn nhập vào một thông điệp cần mã hóa. Sau đó, chương trình sẽ mã hóa thông điệp và giải mã lại để hiển thị kết quả trên màn hình.

Đánh giá độ phức tạp của Thuật toán RSA

Thuật toán RSA có độ phức tạp tính toán khá cao. Độ phức tạp của thuật toán RSA phụ thuộc vào kích thước của các số nguyên tố được sử dụng để tạo khóa. Kích thước của các số nguyên tố này thường lớn, vì vậy thuật toán RSA thường rất chậm khi thực hiện trên các số lớn.

Về cơ bản, thuật toán RSA có các bước sau đây:

  1. Tạo hai số nguyên tố lớn và ngẫu nhiên p và q.
  2. Tính n = p * q.
  3. Tính φ(n) = (p – 1) * (q – 1).
  4. Chọn một số nguyên tố e sao cho 1 < e < φ(n) và e là số nguyên tố cùng nhau với φ(n).
  5. Tính d = e^(-1) mod φ(n).
  6. Khóa công khai là (e, n), khóa bí mật là (d, n).
  7. Mã hóa thông điệp m thành c bằng cách tính c = m^e mod n.
  8. Giải mã thông điệp c thành m bằng cách tính m = c^d mod n.

Độ phức tạp của các bước trong thuật toán RSA khác nhau. Bước tạo số nguyên tố là bước tốn nhiều thời gian nhất trong thuật toán RSA. Việc tính toán mũ có độ phức tạp khá cao, nhưng được tối ưu hóa bằng cách sử dụng phép tính modulo. Trong tổng thể, độ phức tạp của thuật toán RSA là O(k^3), trong đó k là độ dài của số nguyên tố được sử dụng. Vì vậy, khi sử dụng các số nguyên tố lớn, độ phức tạp của thuật toán RSA là rất lớn.

Kết luận

Thuật toán RSA là một trong những thuật toán mã hóa đối xứng phổ biến nhất hiện nay. Thuật toán RSA được sử dụng trong rất nhiều ứng dụng như mã hóa và giải mã dữ liệu, xác thực người dùng và ký số điện tử.

Mặc dù độ phức tạp của thuật toán RSA khá cao, nó vẫn được sử dụng rộng rãi vì tính bảo mật của nó. Thuật toán RSA sử dụng một cặp khóa công khai và khóa bí mật để mã hóa và giải mã dữ liệu. Do đó, nếu khóa bí mật được bảo vệ tốt, thì dữ liệu sẽ được bảo vệ an toàn.

Tuy nhiên, một số phương pháp tấn công đã được phát triển để đánh bại thuật toán RSA, chẳng hạn như tấn công brute-force và tấn công số liệu phụ. Do đó, các chuyên gia bảo mật cần phải cẩn trọng khi sử dụng thuật toán này và luôn cập nhật các biện pháp bảo mật mới để bảo vệ dữ liệu của họ.

One thought on “Thuật toán mã hóa khóa công khai RSA”

Trả lời

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 *