今天分享一個軟考中經(jīng)常出現(xiàn)的關于RSA私鑰計算的題目。我們試著理解背后的算法邏輯，然后再看看如何解題。
設在RSA的公鑰密碼體制中，公鑰為（e, n）= (13, 35), 則私鑰d= （）。?
A. 17
B. 15
C. 13
D. 11
RSA 算法
Rivest Shamir Adleman（RSA）加密算法是一種非對稱加密算法，廣泛應用于許多產(chǎn)品和服務中。非對稱加密使用一對密鑰（私鑰和公鑰），公鑰是任何人都可以訪問的，而私鑰是密鑰創(chuàng)建者才知道的秘密?？梢允褂盟借€或公鑰進行數(shù)據(jù)加密，然后用另一個密鑰進行數(shù)據(jù)解密。
比如用戶A生成一對密鑰并將公鑰公開。當用戶B需要向用戶A發(fā)送機密信息的時候，用戶B使用A的公鑰對機密信息進行加密再發(fā)送給A，用戶A使用自己的私鑰對加密信息進行解密。另一方面，用戶A可以使用自己的私鑰對機密信息進行簽名然后發(fā)給用戶B，用戶B再使用A的公鑰來驗證簽名。
算法描述
公鑰
1. 任意選取兩個不同的大素數(shù)p和q，計算乘積 n = p*q;?
? ? 質數(shù)是指在大于1的自然數(shù)中，除了1和它本身以外不再有其他因素的自然數(shù)。
?2. 任意選取一個大整數(shù)e，滿足gcd (e, (p-1) (q-1)) = 1;? ?
? ? ?gcd：最大公約數(shù),?e的選取比較容易，比如所有大于p和q的素數(shù)都可用
3. 公鑰為（e, n）
私鑰
1. 使用公式 {d*e} mod? {(p-1) (q-1)} = 1 來計算；
mod，是一個數(shù)學運算符號。指取模運算符，算法和取余運算(REM)相似例如a mod b=c，表明a除以b余數(shù)為c
2. 密鑰為（d, n）
?解題思路
1. 已知?公鑰為（e, n）= (13, 35)，即e = 13，n = 35；
2. n = p*q，得到p=5, q=7 (或者 p=7, q = 5)；
3. 計算得出?(p-1) (q-1) = 24；
4. 將以上參數(shù)代入公式?{d*e} mod? {(p-1) (q-1)} = 1，即 {d*13}?mod? 24 = 1
5. 分別計算4個選項，看看哪一個滿足條件
? ??{17*13}?mod? 24 = 5
? ? {15*13}?mod? 24 = 3
? ??{13*13}?mod? 24 = 1
? ? {11*13}?mod? 24 = 23文章來源：http://www.zghlxwxcb.cn/news/detail-416989.html
? ?所以第三個答案滿足條件，即d = 13，所以答案選C文章來源地址http://www.zghlxwxcb.cn/news/detail-416989.html
到了這里，關于已知RSA的公鑰(e,n)計算對應的私鑰d的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
