Điểm:1

RSA key generation: why use lcm(p-1, q-1) instead of the totient ϕ(n)?

lá cờ jm

As far as I can see, generating a private key from two prime numbers p and q, having calculated n = pq, starts with calculating λ(n) = lcm(p-1, q-1). This is the detailed explanation given in the wikipedia article for RSA, it's also the implementation I've found in most Python cryptography libraries, and, searching through the openssl source code, it's also how they seem to do it, so I'd say this looks like the standard.

So my question is, why do some implementations appear to use ϕ(n) instead, which is simply (p-1)(q-1)? I understand that you can calculate λ(n) = ϕ(n) / gcd(p-1, q-1), so I suppose these two can be equal if p-1 and q-1 are coprime, but what's with the two different implementations?

This way to generate the "private modulo" is used for example in the somewhat popular python program rsatool, it's also mentioned in this popular article detailing how RSA keys are generated, but my problem is, taking the two same prime numbers p and q, these two methods will not generate the same private key, so assuming the former is the proper, standard way, where did this other one come from?

kelalaka avatar
lá cờ in
Bạn có thể có [nhiều hơn một khóa riêng cho RSA](https://crypto.stackexchange.com/q/87583/18298) và $\lambda$ luôn cung cấp $d$ nhỏ nhất kể từ $\lambda(n)| \phi(n)$ theo định nghĩa. Nhỏ nhất = tính toán ít hơn.
fgrieu avatar
lá cờ ng
@kelalaka: e rằng "bớt tính toán" mới là lý do thật sự. Khi hiệu suất quan trọng, $d$ hoàn toàn không được sử dụng. Và khi $d$ được sử dụng, tôi nghĩ sự khác biệt trung bình là
kelalaka avatar
lá cờ in
Vâng, rất nhỏ, và vẫn có thể tạo ra ít lợi thế về thời gian. Đặt cược của bạn là một tốt.
dave_thompson_085 avatar
lá cờ cn
Lừa đảo https://crypto.stackexchange.com/questions/1789 https://crypto.stackexchange.com/questions/12710 https://crypto.stackexchange.com/questions/29591 https://crypto.stackexchange.com/ câu hỏi/33676/ https://crypto.stackexchange.com/questions/54280/ https://crypto.stackexchange.com/questions/68873/ https://crypto.stackexchange.com/questions/70624/ và một vấn đề phụ hoặc bình luận trong nhiều hơn nữa. Lưu ý đối với RSA p và q đều phải là số lẻ nên p-1, q-1 không thể nguyên tố cùng nhau và lambda không thể bằng phi.
Điểm:3
lá cờ jm

Vì vậy, sau khi tìm kiếm, hóa ra phiên bản thứ 2 là phiên bản được đưa ra trong bài báo RSA gốc, "Phương pháp lấy chữ ký số và hệ thống mật mã khóa công khai".

Tôi cho rằng phương pháp đầu tiên đơn giản là tiêu chuẩn kể từ đó. Như đã chỉ ra bởi một bình luận $\lambda(n)$ luôn nhỏ hơn hoặc bằng $\phi(n)$. Trong RSA, như được chỉ ra bởi Dave Thompsons, $\lambda(n) \neq \phi(n)$. $\lambda(n)$ có thể dẫn đến tính toán nhanh hơn (?) nhưng điều khiến tôi quan tâm là phiên bản thứ 2 đó đến từ đâu và hóa ra nó đến từ bài báo RSA gốc.

fgrieu avatar
lá cờ ng
Có, phiên bản thứ hai của bạn (với $\varphi$ hoặc $\Phi$ hoặc $\phi$) là phiên bản được xuất bản đầu tiên theo trình tự thời gian. Lưu ý cái khác (với $\lambda$) chia nhỏ thành $e\,d\equiv1\pmod{\lambda(n)}$ với $0

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.