給定因子的高位分解 RSA 模數
我有 {e,N,C} 和 p 的一部分；我可以從這個例子中得到 q 嗎：
N: 009cff15eb53f29b343be4d363b892f5e11fd642ad77146dc856fc9a5c8f96dd3ceb5aa4fc05829e77d49855dbcc9af74023785d2cbc6278de83ad0603bf424697868ddba2f2a6d4bce559934cf2a960e8d35bb99c20fae7155bc8b6ef7ba1e843738e41964d8cc843f65273847a5c6a9548118d63b25b8f0e7090990f2379f16e9edbc8c17fe440198acc654c5aa9173cc2e86d1d442d521e5c80eb84722de103aed5269636cd0280be08bd422c03d03a409bbeb8a390a1a382b06cdd2610ce21ad23c74c834df0ee4dd845d54c766fa9c9295b3a8531edacf187d0fc16a82b8a1eb4f8adef7e4888cef91be81ace3e4fb6db643847f4a7ab489bfeaf42e317a9 e: 3 p: 00cb7b290d0527d2408809087e280aabb9544138efb5e3e283870936411484a587¡s^,ú:§Ç¹cÚO
這是 M^e 小於 N 的解：
http://asecuritysite.com/encryption/crackrsa2
另一種方法是在這裡作為一篇有趣的文章：
http://asecuritysite.com/encryption/crackrsa5
你有密碼值嗎？
考慮這個問題的一個簡單方法是：我們能否分解給定的 2048 位 RSA 模數？ $ N $ ，假設是兩個 1024 位素數的乘積 $ p $ 和 $ q $ ，如果還給定 256 個高位 $ p $ ?
Don Coppersmith 研究了這類問題：多項式方程的小解和低指數 RSA 漏洞，在密碼學雜誌 (1997) 10: 233–260 中（或者可能是盲目的 Google 搜尋？）。他展示瞭如何分解 $ N $ 給定 $ {1\over4}\log_2(N) $ 的高階位 $ p $ . 我不知道平衡兩個素數情況下的更好結果，這將是個大新聞。
我們這裡只有 $ \approx{1\over8}\log_2(N) $ 位，所以該方法行不通。也許這個問題的作者試圖提出一個可以解決的問題，但是搞砸了。或者也許有一些陷阱；喜歡 $ N $ 可能是兩個以上因素的產物；或嚴重不平衡；或者可能有資訊可以從右側明顯的胡言亂語中提取 $ p $ ; 或者生成器中可能存在可檢測到的缺陷 $ p $ ; 或者..
最後，現在的答案確實與從中提取問題的原始RSA Fun問題無關。提示：在 RSA 加密中，通常， $ \log_2(C)\lesssim\log_2(N) $ （在哪裡 $ C $ 是密文）；但在這裡我們有 $ \log_2(C)\ll\log_2(N) $ ; 結合低 $ e $ , 我們可以猜到..