已知某一RSA公鑰密碼體制中公鑰為（23，1073），求密文c=19對應的明文m？

01-25

「筆試題目只能手算，用什麼方法？」

好像沒啥辦法，先強行分解 1073

$sqrt{1073} = 32.7....$

目測可以直接排除 2 3 5 7 11 13，所以還剩下 17 19 23 29 ，一個個試試過來，竟然最後剩下29 。當然，不妨假設天才的你，一眼看出 1073 + 37 = 1110 。

$p = 29 \ q = 37 \ n = p imes q = 1073 \ t = (p-1) imes (q-1) = 1073 - 29 - 37 + 1 = 1008 \ e = 23$

求 d 使得

$d imes 23 equiv 1 pmod{1008}$

extended euclidean

23 1008 1 0 (1008/23 = 43 ... 19) ( 0 - 43 * 1 = -43) 19 23 -43 1 ( 23/19 = 1 ... 4) ( 1 - 1 * -43 = 44) 4 19 44 -43 ( 19/ 4 = 4 ... 3) (-43 - 4 * 44 = -219) 3 4 -219 44 ( 4/3 = 1 ... 1) ( 44 - 1 *-219 = 263) 1 3 263 -219

於是 $d = 263$ 現在要計算 $c^d pmod n = 19^{263} pmod{1073}$

Fermat little theorem

$c^{p-1} equiv 1 pmod p \ c^{q-1} equiv 1 pmod q \ c^d equiv c^{d pmod {p-1}} pmod p \ c^d equiv c^{d pmod {q-1}} pmod q$

$d_p = d pmod {p-1} = 263 pmod{28} = 11 \ d_q = d pmod {q-1} = 263 pmod{36} = 11 \ m_p = c^{d_p} pmod p = 19^{11} pmod{29} = 27 \ m_q = c^{d_q} pmod q = 19^{11} pmod{37} = 20$

$19^2 equiv (-10)^2 equiv 13 pmod {29} \ 19^4 equiv 13^2 equiv 5 pmod{29} \ 19^8 equiv 5^2 equiv -4 pmod{29} \ 19^{11} equiv -10 imes 13 imes -4 equiv 11 imes 13 equiv 27 pmod{29}$

$19^2 equiv -9 pmod{37} \ 19^4 equiv (-9)^2 equiv 7 pmod{37} \ 19^8 equiv 7^2 equiv 12 pmod{37} \ 19^{11} equiv 19 imes -9 imes 12 equiv 6 imes -9 equiv 20 pmod{37}$

CRT

類似求d的過程求出

$p_{inv} = p^{-1} pmod q = 29^{-1} pmod{37} = 23 \ q_{inv} = q^{-1} pmod p = 37^{-1} pmod {29} = 11 \ m = q_{inv} imes q imes m_p + p_{inv} imes p imes m_q pmod n \ = 11 imes 37 imes 27 + 20 imes 23 imes 29 pmod {1073} \ = 723$

謝邀

關於RSA定義方面的問題，前面的答主都回答的很詳細了，我就不在贅述了。

也可以參考我這篇答案：RSA非對稱可以通過私鑰獲取公鑰嗎？ - 知乎用戶的回答

對 @之幽的回答表示不贊同，這道題目的目的就是考RSA加解密的過程，那麼根據公鑰推導私鑰的過程也是考察的範圍。

具體的解題思路如下：

公鑰為(23,1073)，由於23是質數，所以1073為 $n$
將1073進行質因數分解，得到 $29 imes 37 = 1073$

這一步是這道題最費時間的地方，同時也是RSA演算法安全性的根本所在，直接代碼解決：

public class RSATest{ public static void main(String[] args){ int n = 1073; for(int i = 3; i &< Math.sqrt(n); i++){ if(isPrime(i) n % i == 0){ System.out.printf("1073 = %d * %d", i, n / i); } } } static boolean isPrime(int n){ if(n &<= 3){ return true; } for(int i = 2; i &< Math.sqrt(n); i++){ if(n % i == 0){ return false; } } return true; } }
從因數分解的結果，得到 $p=29,q=37$

從公鑰中，可以得到 $e_{1}=23$

根據 $(e_{1} imes e_{2}) mod [(p-1)(q-1)] =1$ 計算 $e_{2}$

這一步也很蛋疼，首先要變成這樣一個式子： $(23 imes e_{2} ) - 1 = n1008$ ，直接代碼解決：
public static void main(String[] args){ int data = 1008; for(int n = 1; ; n++){ if((n * data + 1) % 23 == 0){ System.out.printf("n = %d, e2 = %d ", n, (data * n + 1) / 23); break; } } }
得到 $e_{2} = 263$
所以，私鑰為(263,1073)

根據 $P=C^{e_{2}} mod n$ 解密密文

$P=19^{263} mod1073 =723$

話說這麼大的計算量手算真的大丈夫？

不謝邀。兄弟啊，本科課本上列出來的密碼學演算法總共沒有幾個，做分析的應該只有對稱的DES和非對稱的RSA了吧，稍微看看書推導一下唄，也就20分鐘的事情。

我不認為回答有錯誤，通過公鑰求私鑰和破解沒有區別，而且通過公鑰求私鑰屬於公式簡單但數字難求，這對於演算法本身的考察沒有什麼意義。

而且你的問題描述是錯誤的呀。給出的是公鑰，只能加密，沒辦法解密啊，解密是私鑰的事情。我姑且把問題重新改正列出如下：

已知RSA的私鑰為（23，1073），密文為c = 19，求對應的明文m。

我把RSA演算法簡單寫一下，全部取自課本。要是不耐煩，那就直接拉到最下面找答案。

一. 產生公、私鑰對

假設Alice想要通過一個不可靠的媒體接收信息，那麼她可以用以下的方式來產生一個公鑰和相應的私鑰私鑰，組成密鑰對：

1.隨意選擇兩個大的質數p和q，p不等於q，計算N=pq。

2.根據歐拉函數，求得r = (p-1)(q-1)

3.選擇一個小於 r 的整數 e，求得 e 關於模 r 的模反元素，命名為d。（模反元素存在，當且僅當e與r互質）將 p 和 q 的記錄銷毀。

其中：(N,e)是公鑰；(N,d)是私鑰。

Alice將她的公鑰(N,e)公開，而將她的私鑰(N,d)藏起來。

二. 加密

某位用戶Bob希望通過RSA同Alice進行通信，那麼他將明文m以如下形式加密即可：

$m^e = c (mod N)$

其中，(N, e)為Alice的公鑰。c即為Bob傳輸給Alice的密文。

三.解密

Alice在收到密文c之後，用自己的私鑰(N,d)對密文進行解密，方法如下：

$c^d = m (mod N)$

m即為解密出的明文。

值得一提的是，RSA的解密過程和加密過程的形式完全相同，只不過參數有所變化。正因為如此，將公私鑰的身份對調，就可以實現相應的RSA簽名方案。

==演算法和具體計算的分割線==

懶得手算密文了，心算了一下並沒有溢出，寫了個簡單的測試代碼。

public class RSA { /** * 加解密演算法形式相同, 所以一個演算法就能夠描述加密和解密過程了. * @param key 加密時候為公鑰, 解密時候為私鑰 * @param data 數據 * @return 相應的密文 / 明文 */ public static long rsa_crypt(int key, long data, long baseNum){ if(baseNum &< 1 || key &< 1){ return 0L; } return Math.round(Math.pow(data, key)) % baseNum; } public static void main(String[] args) { //基數 int baseNum = 1073; //私鑰 int secretKey = 23; //加密後的數據 long cipherText = 19; //解密後的數據 long message = rsa_crypt(secretKey, cipherText, baseNum); System.out.println("解密前：" + cipherText); System.out.println("解密後：" + message); } }

得到結果：

注1：文中只列出了演算法，用於了解RSA的基本步驟，並未介紹費馬小定理、大整數分解問題等理論基礎。

注2：文中的代碼僅僅是針對這種測試題目。事實上，由於RSA演算法多用於1024bit以上，計算過程中至少要用BigInteger來做才是對的。其次，RSA的工業實現，其重心放在素數生成器（即開始時候的p和q）和演算法加速（採用流水線進行冪運算並用ASIC實現）上，而文中的代碼並未給出，有興趣的同學可以自行查找相應實現。

手算的方法是先分解n=1073=29*37

然後按照RSA的方法對m=19進行加密。對密文再加密，若干輪之後得出c=19.這個時候看m的值就行了。現場沒有環境，要不然我也要試試。

首先公鑰的話（23，1073）應該是寫反了，23是質數不可能作為n，在這個前提上，公鑰如果是（1073，23）的話：

e=23，n=1073=29*37（這個手算有點噁心啊，我百度的），d未知

由p=29，q=37，φ(n) =（p-1）*（q-1）=1008，

23d-1 = 1008k，求得有d=263，k=6

c=19，有

m^23≡19(mod 1073)

19^263≡m(mod 1073)

19^263≡(19^ 7)*(19^256) (mod 1073)

手算硬算出19^7≡505 (mod 1073)

19^263≡505*(19^256) (mod 1073)

19^256≡(19^2)^128≡361^128≡(361^2)^64≡488^64≡1011^32≡625^16≡53^8≡663^4≡712^2≡488 (mod 1073)

19^263≡505*488≡723 (mod 1073)

反向驗算723^23≡19 (mod 1073)無誤

所以我猜m=723？

不過這題真的是筆試純手算題么？我手算用了近2個小時。。。。其實寫代碼的話應該很快出答案