Tôi đang cố gắng tạo một mô-đun RSA trong VHDL, mô-đun này sẽ được triển khai thành một FPGA. Tôi đang cố gắng thực hiện một thuật toán Montgomery đầy đủ, điều đó có nghĩa là tôi đang làm việc với thuật toán Lũy thừa Montgomery và thuật toán Phép nhân Montgomery. Hầu hết các thử nghiệm của tôi bao gồm tạo các số ngẫu nhiên (khóa, mô-đun, r, thông báo) mà tôi sử dụng để thực hiện mã hóa/giải mã. Nếu tin nhắn ban đầu bằng với tin nhắn được giải mã, thì bài kiểm tra đã vượt qua.
Trước tiên, tôi đã tạo một số mã cấp cao của phiên bản cấp độ bit của Phép nhân Montgomery trong Python. Trong khi cố gắng loại bỏ phép trừ cuối cùng, tôi đã tìm thấy cái này bài đăng của Brett trên Stack Overflow. Ông cũng đã thực hiện một bài viết đây về cùng một điều. Điều này đã giúp tôi làm cho thuật toán cấp độ bit hoạt động trong Python mà không cần phép trừ cuối cùng. Hơn nữa, nó dường như hoạt động trong VHDL khi thực hiện mô phỏng.
Tiếp theo là làm cho thuật toán cấp độ từ hoạt động. Đọc tài liệu c03gfp của Ãetin Kaya Koç tìm thấy đây, tôi đã xoay sở để mã Python cấp cao của thuật toán cấp từ hoạt động, nhưng không như tôi mong đợi vì tôi phải giữ lại phép trừ cuối cùng.Sử dụng cùng một R đã được sử dụng trong mã cấp độ bit không hoạt động đối với mã cấp độ từ. Thành thật mà nói, tôi không chắc liệu Brett có hỏi về điều tương tự hay không. đây, nhưng anh ấy có thể là.
Tôi đã cố gắng tìm các tài liệu mô tả cách thực hiện điều này chủ yếu bằng cách googling, nhưng tôi không có may mắn tìm thấy bất kỳ tài liệu nào. Nếu tôi tìm thấy bất kỳ thứ gì thực sự có thể giúp tôi thoát khỏi phép trừ cuối cùng trong thuật toán cấp độ từ, thì tôi đã không hiểu nội dung của tài liệu trong trường hợp đó.
Tôi có một ý tưởng rằng tôi có thể thử tăng R nhiều hơn so với những gì đã làm khi sử dụng tối ưu hóa Walter cho thuật toán mức bit. Xét rằng tôi đang làm việc với cấp độ từ thuật toán, tại sao không có R rộng hơn một từ so với mô đun?
Đối với thuật toán cấp bit tôi đặt R = 2^(2 * NUM_BITS) mod n theo đề xuất của Renaud Pacalet, ở đâu NUM_BITS = 256 + 2 trong trường hợp của tôi khi tôi đang làm việc với các số 256 bit.
Mặt khác, đối với thuật toán cấp độ từ, tôi đã thử đặt R = 2^(2 * (NUM_BITS + WORD_WIDTH)) mod n. Trong trường hợp của tôi NUM_BITS = 256 và WORD_WIDTH = 32, nhưng WORD_WIDTH cũng có thể là 8, 16, 64 hoặc 128 chẳng hạn (lưu ý rằng WORD_WIDTH $\leq$ NUM_BITS). Điều này đã hoạt động và đã hoạt động cho tất cả các thử nghiệm mà tôi đã thực hiện bằng Python với các số ngẫu nhiên. Tôi vẫn chưa triển khai điều này trong VHDL vì tôi muốn xác minh xem điều này có đúng không trước khi thực hiện hoặc ít nhất là có thêm cơ sở để thực hiện việc này.
Vì vậy, câu hỏi của tôi là nếu đặt đúng R = 2^(2 * (NUM_BITS + WORD_WIDTH)) mod n cho Phép nhân Montgomery cấp độ từ như tôi đã làm bây giờ.
Ngoài ra, có tài liệu nào mô tả điều này không?
CHỈNH SỬA 1
Có vẻ như sau khi định dạng lại câu hỏi của mình khi tôi đang tìm kiếm xung quanh, tôi tình cờ thấy cái này bài viết của Saf. Câu trả lời được cung cấp bởi Thomas Pornin dường như gần như trả lời câu hỏi của tôi, vì câu hỏi của tôi về cơ bản là cùng một câu hỏi với câu hỏi mà Saf đã hỏi.
Thomas Pornin đã viết rằng nếu mô đun $n$ có kích thước NUM_BITS, thì lẽ ra tôi nên tìm bội số tiếp theo của WORD_WIDTH.
Lặp lại ví dụ của Thomas Pornins ở đâu WORD_WIDTH = w = 32:
Đối với mô đun 1024 bit, đã là bội số của 32, bạn sử dụng $R=2^{1024}$. Đối với mô-đun 1025 bit, bạn sẽ sử dụng $R=2^{1056}$.
Điều này dường như không đúng với tôi trừ khi tôi đã hiểu lầm điều gì đó. Thông qua thử nghiệm của tôi với NUM_BITS = 256 và WORD_WIDTH = 32 Tôi đã tìm thấy cài đặt đó $R=2^{256}$ có thể thất bại mặc dù $n$ là một số 256 bit và ngay cả khi $n$ là một số 255-bit. Mặt khác, các thử nghiệm luôn thành công khi $R=2^{256 + 32\cdot c}$, ở đâu $c$ là một số nguyên dương. Tôi chỉ thử nghiệm với $c = [1,2,3]$, vì vậy tôi không thể đảm bảo rằng tất cả các số dương sẽ hoạt động. Người ta cũng nên xem xét chất lượng các bài kiểm tra của tôi và số lượng bài kiểm tra tôi đã thực hiện ($+1000000$).
Phần tiếp theo cũng là câu trả lời của Thomas Pornins cho câu hỏi của Saf:
Trường hợp là phép nhân Montgomery chỉ có ý nghĩa với kích thước từ. Với $w$ như kích thước từ, sau đó $R=2^{kw}$ đối với một số nguyên k, nên được chọn càng nhỏ càng tốt với điều kiện là $R\geN$.
Đối với tôi nó có vẻ như $R > N$ nên là trường hợp. Bất kỳ ý kiến về điều này?
