Tôi là một học sinh trung học viết một bài báo về RSA, và tôi đang làm một ví dụ với một số số nguyên tố rất nhỏ. Tôi hiểu làm thế nào hệ thống hoạt động, nhưng tôi không thể cho cuộc sống của tôi tính toán khóa riêng bằng cách sử dụng thuật toán euclide mở rộng.RSA: Tính toán khóa riêng với thuật toán Euclide mở rộng
Dưới đây là những gì tôi đã làm cho đến nay:
- tôi đã lựa chọn các số nguyên tố p = 37 và q = 89 và tính toán N = 3293
- tôi đã tính toán (p-1) (q -1) = 3168
- Tôi đã chọn số e để e và 3168 tương đối chính. Tôi đang kiểm tra điều này với thuật toán euclide chuẩn, và nó hoạt động rất tốt. e My = 25
Bây giờ tôi chỉ cần phải tính toán chính d tin, vừa đáp ứng ed = 1 (mod 3168)
Sử dụng Giải thuật Euclid mở rộng để tìm d sao cho de + tN = 1 Tôi nhận được -887 • 25 + 7 • 3168 = 1. Tôi ném 7 đi và nhận d = -887. Tuy nhiên, cố gắng giải mã một tin nhắn, điều này không hiệu quả.
Tôi biết từ cuốn sách của tôi rằng d nên là 2281, và nó hoạt động, nhưng tôi không thể tìm ra cách họ đến con số đó.
Có ai giúp được không? Tôi đã cố gắng giải quyết vấn đề này trong 4 giờ qua, và đã tìm kiếm câu trả lời ở khắp mọi nơi. Tôi đang thực hiện thuật toán Euclide mở rộng bằng tay, nhưng vì kết quả hoạt động của tôi nên được tính toán đúng.
Cảm ơn trước,
Mads
Như các nhân viên đã lưu ý, chỉ cần sử dụng số dư còn lại. Tương tự, để nâng thứ gì đó lên một điện âm 'x' đầu tiên tính toán nghịch đảo của nó và sau đó nâng cao lên công suất (' -x') ('-x' là tích cực vì' x' là âm). –
Tôi nhầm lẫn về cách bạn nhận được "de + tN = 1" -887 • 25 + 7 • 3168 = 1. Tôi hiểu e = 25 nhưng d, t, và N không có ý nghĩa. D, t, và N là gì? Và tại sao bạn được phép vứt bỏ 7? Casey –