RSA計算d

不知道這是否是要求密碼問題的正確位置，但這裏有。RSA計算d

我想在RSA中找出「d」，我已經計算出p，q，e，n和øn;

p = 79, q = 113, e = 2621 

n = pq     øn = (p-1)(q-1) 
n = 79 x 113 = 8927  øn = 78 x 112 = 8736 

e = 2621 
d =

我似乎無法找到d，我知道d意味着是一個值，該值.. ED MOD O（N）= 1。任何幫助將理解

編輯：一個例子將是E = 17，d = 2753，ON = 3120

17 * 2753 3120 MOD = 1

來源

2014-04-24 user3423572

這個問題似乎是題外話因爲它是關於[加密]（http://crypto.stackexchange.com） –

您正在尋找ë（MOD Ñ）的模逆，這可以使用擴展歐幾里得算法來計算：

function inverse(x, m) 
    a, b, u := 0, m, 1 
    while x > 0 
     q := b // x # integer division 
     x, a, b, u := b % x, u, x, a - q * u 
    if b == 1 return a % m 
    error "must be coprime"

因此，在實施例中，inverse(17, 3120) = 2753和inverse(2621, 8736) = 4373.如果你不想實現該算法，你可以詢問Wolfram|Alpha的答案。

來源

2014-04-24 22:52:29 user448810

乾杯，我聽說沃爾夫林阿爾法我認爲這是一個程序，你必須安裝，所以我從來沒有打擾到現在。我得到的答案是4373，通過使用命令 - 2621模8736的逆。但是，如果我重新檢查答案，我得到0，是不是它應該是1？「ed modø（n）= 1」。此外，我相信你的意思是在RSA中有2個數字是小數和大數。一個即時通訊設法解決我有一個大的「E」，但在例子中，「E」是小的，「D」是大的 – user3423572

我犯了一個錯誤，我得到的答案是7936，而不是0. – user3423572

我原來的解決方案誤讀數字;答案現在已經修復。對困惑感到抱歉。在RSA中，通常_e_在其二進制表示中只有少量的1位，因爲對於0位不存在計算。因此，e = 3 = 11b或e = 65537 = 10000000000000001b是常見的。 – user448810

你需要的算法是Extended Euclidean Algorithm。這使您可以計算貝祖等式，其中規定，對於任何兩個非零整數a和b，存在整數x和y使得係數：

ax + by = gcd(a,b)

這可能不會立即有用的，但是我們知道即e和φ(n)是互質，gcd(e,φ(n)) = 1。因此，算法爲我們提供了x和y這樣的：

ex + φ(n)y = gcd(e,φ(n)) 
      = 1 
Re-arrange: 
ex = -φ(n)y + 1

這相當於說ex mod φ(n) = 1，所以x = d。

來源

2014-04-24 21:44:12 Iridium

感謝您的答覆。我有點失去了你的解釋，我正努力應用你提供給我的問題的公式。我過去遇到了Euclid的算法，但它只是計算一個最大公約數 - gcd – user3423572

@ user3423572我的答案實際上是爲什麼算法能夠工作的描述 - 「擴展歐幾里德算法」的第一行中的鏈接應該指出你在正確的方向。你是對的，通常的歐幾里得算法給你的GCD，但是「擴展」版本爲你提供了Bézout身份的係數 - 其中之一就是你需要的'd'。 – Iridium

例如，你需要得到d在下一：
3 * d = 1（MOD 9167368）

這同樣是：
3 * d = 1 + K * 9167368，其中，k = 1，2，3，...

重寫它：
d =（1 + K * 9167368）/ 3

您的d必須是整數最低 k。
讓我們寫出下式：
d =（1 + K * FI）/ E

public static int MultiplicativeInverse(int e, int fi) 
     { 
      double result; 
      int k = 1; 
      while (true) 
      { 
       result = (1 + (k * fi))/(double) e; 
       if ((Math.Round(result, 5) % 1) == 0) //integer 
       { 
        return (int)result; 
       } 
       else 
       { 
        k++; 
       } 
      } 
     }

讓我們來測試此代碼：

Assert.AreEqual(Helper.MultiplicativeInverse(3, 9167368), 6111579); // passed

來源

2015-03-08 21:28:20

回答

相關問題