常數時間模冪運算的虛擬碼
我希望在恆定時間內實現模冪運算（對於 RSA），但我發現的大多數範例都是對操作的更多數學描述。是否有任何帶有虛擬碼描述的參考資料，這些參考資料對於沒有太多數學背景的人來說是可以理解的（並且可以實現的！）？
不。如果您沒有強大的數學背景，那麼自己實施 RSA 是一個壞主意（也許即使您這樣做了）。出錯的方法有很多，這可能會導致微妙的安全漏洞。
相反，您應該使用標準加密庫中經過嚴格審查的 RSA 實現和經過嚴格審查的協議——或者如果您認為自己不能信任任何現有的實現或需要幫助，請聘請理解數學的密碼學家選擇一個合適的。
一瞥 RSA 的工作原理
密鑰生成算法
- 選擇兩個非常大的隨機素數：p 和 q
- 計算 n 和 φ(n)：n = pq 和 φ(n) = (p-1)(q-1)
- 選擇一個整數 e, 1 < e < φ(n) 使得： gcd(e, φ(n)) = 1
（其中 gcd 表示最大公分母） 4. 計算 d, 1 < d < φ(n) 使得： ed ≡ 1 (mod φ(n))
在哪裡…
- 公鑰是（n，e），私鑰是（n，d）
- p、q 和 φ(n) 的值是私有的
- e 是公共或加密指數
- d 是私有或解密指數
加密
密文 C 由等式“C = Me mod n”找到，其中 M 是原始消息。
解密
消息 M 可以通過等式“M = Cd mod n”從密文 C 中找到。
一個例子
這是一個非常簡單的例子，使用如此小的素數是不安全的，通常素數 p 和 q 會大得多。
Select the prime integers q=11, q=3. n=pq=33; φ(n)=(p-1)(q-1)=20 Choose e=3 Check gcd(3,20)=1 Compute d=7 (3)d ≡ 1 (mod 20)因此公鑰是 (n, e) = (33, 3)，私鑰是 (n, d) = (33, 7)。
現在假設我們要加密消息 M=7
C=米和反對n $ C = M^e \mod n $
C=73反對33 $ C = 7^3 \mod 33 $
C=343反對33 $ C = 343 \mod 33 $
C=13 $ C = 13 $
所以現在已經找到了密文C。C的解密如下進行。
米′=Cd反對n $ M’ = C^d \mod n $
米′=137反對33 $ M’ = 13^7 \mod 33 $
米′=62,748,517反對33 $ M’ = 62,748,517 \mod 33 $
米′=7 $ M’ = 7 $
如您所見，在消息被加密和解密後，最終消息 M’ 與原始消息 M 相同。使用該算法的更實用的方法是將消息轉換為十六進制並對每個消息執行加密和解密步驟單獨的八位字節。
安全通知
現在，請注意，提供的範例遠非安全。在這個相當粗略的介紹性解釋中，很多重要的細節都被遺漏了。此外（有充分理由）與範例中使用的素數相比，RSA 使用了巨大的素數。
最後，在跳過數學（如您所要求的那樣）時很難提供“虛擬碼”，因為算法取決於數學！但是按照上面的描述來初步了解事情是如何工作的應該不難……並在此基礎上建立/擴展你的知識。
有一件事是肯定的：如果你不掌握它背後的數學原理，你將很難確保你不會弄亂你自己的實現。如有疑問，請像其他使用者已經建議的那樣使用經過嚴格審查的實現/庫之一。這些是由確實了解所涉及的數學並且知道自己在做什麼（至少在大多數情況下）的人建構的。
“恆定時間”和公司……
根據您實現它的方式，RSA 可能會為幾個安全問題提供空間。其中之一是對側通道攻擊的缺失防禦。然而，要建立適當的防禦，需要對它背後的數學有很好的理解。您可以查看 Wikipedia 上的“平方求冪”文章。除此之外，它還提到了蒙哥馬利的梯子技術……
x 1 = x; x 2 = x 2 對於 i=k-2 到 0 做 如果 n i =0 那麼 x 2 = x 1 * x 2 ; x 1 = x 1 2 別的 x 1 =x 1 *x 2 ; x 2 =x 2 2 返回 x 1但這不會削減它！（“如果”是個問題……所以你需要修改這個虛擬碼。）
在我看來，虛擬碼和維基百科的此類文章都無法涵蓋實際實施 RSA 時可能出現的*所有潛在安全問題。*事實上，涵蓋每一個潛在問題對於答案來說過於寬泛，並且不知道您目前的知識水平（以及您所做的研究，以及您從該研究中學到了什麼），幾乎不可能判斷什麼可能會幫助你，什麼可能不會。然而，據我所知，虛擬碼肯定無法滿足您的需求。
請不要誤會我的意思，但由於您表示您很難掌握這一切背後的數學，我想重複一遍：如有疑問，您應該考慮使用經過良好審查（測試）的一種實施。由於缺乏一些知識和/或經驗，您肯定不想冒險搞砸一些重要的事情。畢竟，在加密貨幣方面犯錯不是一種選擇……如果有的話，錯誤會破壞加密貨幣——最終——你的脖子。