爲p，q和E，但滿足gcd（E，PHI）給定的值不爲1，那麼如何在RSA求n＆d？或者甚至有可能？

其值爲：p = 19,q = 23和e = 3。計算按照該算法：N = 437 & 披= 396。但是我不認爲RSA在這裏有效，因爲GCD（e，phi）在這種情況下不是1，因爲GCD（3,396）= 3。所以，這意味着RSA算法不滿足，不能進一步計算d，對嗎？爲p，q和E，但滿足gcd（E，PHI）給定的值不爲1，那麼如何在RSA求n＆d？或者甚至有可能？

我想問如果我假設有對P，Q和E的那些給定的值，由於GCD（E，PHI）= 1無解得不到滿足是正確的。

還是我錯在這裏做什麼？這是原來的問題出現於我正在解決以前的試卷：（一字一句）

In RSA, given p=19, q=23 and e=3, find n and d.

我願意承擔其一個棘手的問題，檢查一個人是否知道算法（及其步驟）或不。請讓我知道，如果我的假設是正確與否，提前致謝！ :)

來源

2017-03-31 BlackMambo

你是對的。運行Extended Euclidean Algorithm計算ModInv（3，396），我們得到

ModInverse(3, 396) 
    r=396, newR=3, t=0, newT= 1 
    r= 3, newR=0, t=1, newT=-132 

    newR == 0 && r > 0: Not Invertible.

因此有一個爲d沒有價值。（計算它對lambda(n)而不是phi(n)也產生「不可逆」，因爲lambda只是phi/2和3是打破東西的主要因素。）

來源

2017-03-31 14:10:39 bartonjs

感謝您的確認。後來我做了一些_googling_以查看是否有任何方法使用一些內置的Java函數進行交叉檢查。找出使用BigInteger並嘗試賦值： 'BigInteger d = e.modInverse（phi）'導致ArithmeticException異常，說BigInteger不可逆。這證實了我的設想和你所闡述的內容。再次感謝！ :) – BlackMambo

爲p，q和E，但滿足gcd（E，PHI）給定的值不爲1，那麼如何在RSA求n＆d？或者甚至有可能？

回答

相關問題