用於加密塊的 RSA p 和 q 大小
我有一個大約 18 位大小的明文。我必須使用 RSA 對其進行加密。p 和 q 必須有多大？所以我嘗試使用 Python 編碼的 RSA 算法 M（加密消息）= 2**18 位，p 和 q 的大小不同，我的結果如下：
p=61, q=31 not working p=61, q=127 not working p=997, q=4253 OK working我隨機嘗試了它們，但我認為有一種方法可以確定尺寸。
我有一個大約 18 位大小的明文。我必須使用 RSA 對其進行加密。必須有多大 $ p $ 和 $ q $ ?
為了安全起見，建議是：非常大，比如每個至少 700 位，並且它們的位大小之和至少 2000，這樣他們的乘積就很難分解。但也許這不是答案，因為它不考慮明文大小。此外，還有其他安全條件。
在教科書 RSA 中，公鑰和私鑰是 $ (N,e) $ 和 $ (N,d) $ ， 和 $ N=p,q $ , $ e,d\bmod(p-1);=;1;=;e,d\bmod(q-1) $ ， 在哪裡 $ p $ 和 $ q $ 是素數。明文（整數代表）消息的加密 $ m $ 是每 $ c=m^e\bmod N $ ，並且解密是按 $ e=x^d\bmod N $ .
從後面的方程和定義¹ $ \bmod $ 因此，只有在以下情況下，解密才能返回原始消息 $ 0\le m<N $ . 當素數時，這個條件是充分的 $ p $ 和 $ q $ 是不同的（請參閱this question），我們將假設。
因此 $ p $ 和 $ q $ 應該足夠大，以使最大可能 $ m $ 驗證 $ m<p,q $ . 如果 $ m $ 是 18 位，根據位大小的定義²，只要 $ p,q\ge2^{18} $ .
在位大小方面 $ p,q $ : 至少 19 就足夠了。
就比特大小的總和而言 $ p $ 和 $ q $ : 至少 20 個就足夠了。這是從 $ |p|+|q|-1\le|p,q|\le|p|+|q| $ .
p=61, q=127 not working正確的。證明這一點的一種方法是 $ 2^5=32\le p=61<64=2^6 $ 和 $ 64=2^6\le q=127<128=2^7 $ ， 所以 $ p $ 是 6 位和 $ q $ 是 7 位的，因此 $ p,q $ 不超過 13 位，因此所有 18 位 $ m $ 是這樣的 $ m\not<p,q $ ，因此這樣 $ m $ 不屬於可以加密解密回原件的明文。
p=997, q=4253 OK working正確的。證明這一點的一種方法是 $ 2^9=512\le p=997<1024=2^{10} $ 和 $ 4096=2^{12}\le q=4253<8183=2^{13} $ ， 所以 $ p $ 是 10 位和 $ q $ 是 13 位的，因此 $ p,q $ 不小於 22 位，因此所有 18 位 $ m $ 是這樣的 $ m<p,q $ ，因此這樣 $ m $ 屬於可以加密解密的明文。
通過計算 $ p,q=4240241 $ ，我們可以發現 $ p,q $ 是 23 位（而不是上面建立的最小值 22），因此 $ p=997 $ , $ q=4253 $ 允許解密所有消息，包括 22 位和一些 23 位消息。
¹ 對於整數 $ i $ 和嚴格的正整數 $ k $ ， 數量 $ i\bmod k $ 被唯一地定義為整數 $ j $ 和 $ k $ 劃分 $ i-j $ 和 $ 0\le j<k $ . 這個已經寫完了 $ j=i\bmod k $ 左邊沒有左括號 $ \bmod $ .
對比 $ j\equiv i\pmod k $ ， 意思就是 $ k $ 劃分 $ i-j $ , 但離開範圍 $ j $ 未指定。² 嚴格正整數的位大小 $ a $ 是唯一定義的整數 $ b $ 和 $ 2^{b-1}\le a<2^b $ . 它擁有 $ b=\left\lceil\log_2(a+1)\right\rceil=\left\lfloor\log_2(a)\right\rfloor+1 $ . 在密碼學上下文中，它可以寫成 $ b=|a| $ .