Mô-đun n
φ(n) (p − 1)(q − 1)
Khóa công khai (e, n)
Khóa riêng d e · d mod φ(n) = 1

Các khóa

    Cách tìm d: thuật toán Euclid mở rộng

    Mỗi hàng có được bằng cách chia hai hàng phía trên nó. Ở hàng có số dư 1, cột cuối cùng là d (cộng thêm φ(n) nếu nó âm).

    ThươngSố dưHệ số của e

    Thông điệp

    Ký tự Mã m Kết quả

    Gửi qua mạng

    BitBình phươngNhân với m

    Phá khóa

    Thao tác

    Thêm thông tin về RSA

    Minh họa mã hóa RSA

    RSA cho phép bất kỳ ai khóa một thông điệp bằng khóa công khai của bạn, trong khi chỉ bạn mới mở được nó bằng khóa riêng của mình. Đằng sau nó chỉ là vài dòng số học ở trường: hai số nguyên tố, một phép nhân, một số dư và một phép nghịch đảo khéo léo. Hãy tạo một cặp khóa từ các số nguyên tố bạn chọn, mã hóa và giải mã một thông điệp từng ký tự một, ký nó để ai cũng kiểm tra được rằng nó đến từ bạn, rồi đóng vai kẻ tấn công và phân tích n ra thừa số để thấy vì sao khóa thật cần hàng trăm chữ số. Chọn hai số nguyên tố p và q, hoặc nhấn Số nguyên tố mới. Ứng dụng tạo khóa công khai (e, n) và khóa riêng d, và cho thấy thuật toán Euclid mở rộng tìm ra d thế nào. Gõ một thông điệp: mỗi ký tự được mã hóa bằng khóa công khai và giải mã bằng khóa riêng. Nhấn vào một hàng để xem lũy thừa được tính bằng bình phương liên tiếp. Chuyển sang Ký để ký bằng khóa riêng thay vì mã hóa, và nhấn Phân tích n để xem các khóa nhỏ bị phá nhanh thế nào.

    Cách nó hoạt động

    1. Nhập hai số nguyên tố p và q, hoặc chọn một độ lớn và nhấn Số nguyên tố mới; ứng dụng tính n, φ(n), e và d, và cho thấy d được tìm ra thế nào.
    2. Gõ một thông điệp và chọn Mã hóa hoặc Ký. Mỗi ký tự được chuyển thành một số rồi nâng lên lũy thừa mod n; nhấn vào một hàng để xem phép bình phương liên tiếp.
    3. Nhấn Phân tích n để Eve tách n thành hai số nguyên tố của nó và khôi phục khóa riêng.

    Cách các khóa hoạt động

    Nhân hai số nguyên tố: n = p × q. Với p = 61 và q = 53, n = 3233. Số φ(n) = (p − 1)(q − 1) = 3120 đếm các số nhỏ hơn n không có ước chung nào với n, và chỉ người biết p và q mới tính được nó. Chọn e = 17, không có ước chung với 3120, và tìm d sao cho e × d lớn hơn một bội của φ(n) đúng 1 đơn vị: ở đây d = 2753, vì 17 × 2753 = 46801 = 15 × 3120 + 1. Công bố (e, n) và giữ kín d. Một thông điệp m trở thành c = mᵉ mod n, và định lý Euler bảo đảm rằng cᵈ mod n cho lại m.

    Vì sao khó phá

    Mọi thứ kẻ tấn công cần đều ẩn trong các thừa số của n. Với n = 3233 thì chẳng có gì bảo vệ cả: thử các ước lẻ sẽ tìm ra 53 sau khoảng hai chục lần thử. Nhưng công sức tăng theo căn bậc hai của n. Một mô-đun 2048 bit có khoảng 617 chữ số, và không phương pháp nào đã biết, trên bất kỳ máy tính nào hiện có, có thể phân tích nó ra thừa số trong một khoảng thời gian hữu ích. Ký là chạy RSA theo chiều ngược lại: s = mᵈ mod n chỉ có thể tạo ra bằng khóa riêng, và ai cũng có thể kiểm tra rằng sᵉ mod n cho lại m.

    Câu hỏi thường gặp

    Vì sao không ai tính được d từ khóa công khai?

    Để tìm d bạn cần φ(n) = (p − 1)(q − 1), và để có φ(n) bạn cần p và q. Khôi phục chúng từ n nghĩa là phân tích n ra thừa số, và với những số có hàng trăm chữ số thì chưa có phương pháp nhanh nào được biết đến. Bản minh họa cho phép bạn phân tích các khóa đồ chơi trong chưa đầy một giây, điều này cho thấy chính xác vì sao khóa thật lại lớn đến vậy.

    Vì sao thông điệp được mã hóa từng ký tự một?

    Vì các khóa đồ chơi rất nhỏ: RSA chỉ mã hóa được một số nhỏ hơn n. Với n = 3233, mọi mã ký tự đều vừa, nhưng cả một câu thì không. RSA thật dùng mô-đun từ 2048 bit trở lên, đệm thông điệp bằng các byte ngẫu nhiên để cùng một thông điệp không bao giờ được mã hóa giống nhau hai lần, và trong thực tế chỉ mã hóa một khóa ngắn cho một thuật toán mã hóa nhanh hơn như AES.

    Bình phương liên tiếp dùng để làm gì?

    Nó tính những lũy thừa khổng lồ như m²⁷⁵³ mod n mà không bao giờ phải viết ra con số khổng lồ đó. Viết số mũ ở hệ nhị phân, rồi đi qua từng bit của nó: bình phương kết quả hiện tại với mỗi bit và nhân với m với mỗi bit 1, mỗi lần đều lấy số dư mod n. Một số mũ 2048 bit chỉ cần khoảng 2048 phép bình phương.

    Mã hóa và ký khác nhau thế nào?

    Mã hóa dùng khóa công khai của người nhận, để chỉ khóa riêng của người nhận mới giải được. Ký dùng khóa riêng của người gửi, để ai cũng có thể kiểm tra bằng khóa công khai của người gửi và biết rằng thông điệp đến từ người giữ khóa đó và không bị thay đổi.

    Thông điệp của tôi có bị gửi đi đâu không?

    Không. Mọi thứ được tính trong trình duyệt của bạn, và các số nguyên tố cùng thông điệp của bạn được lưu trong bộ nhớ cục bộ của trình duyệt này.

    Sẵn sàng thử chưa?

    Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

    Tới trình chỉnh sửa