使用已知填充方案和公鑰對 RSA 進行有效攻擊
我在分配問題上遇到了一些麻煩。我希望我能在這裡得到一些指導。這個問題為我們提供了一個公鑰， $ N $ 和填充方案。
這是填充方案“假設 PIN 是一個小於 $ 2^{16} $ . 她沒有直接加密 PIN，而是先以二進制格式寫入 PIN，然後在 PIN 的二進製表示的最右側附加 2048 個 1 位。例如，整數 $ abcd $ 十六進制變成整數 $ x $ "
$ c = (m^e) \bmod N $
兩者的長度 $ N $ 和 $ C $ 是 923 位的十六進制數。
根據這些知識，我們應該對密文進行有效的攻擊，通過它我們可以恢復明文。
我和我的團隊嘗試實施多種 cca 和 cpa 技術，但是我們幾乎找不到任何可行的方法。當然，我知道解決這個問題的訣竅在於填充，但我們還沒有發現如何做到這一點。
我將不勝感激在這方面的任何幫助。
編輯：價值 $ N $ 是
0xa05bb3783769b832a2d022646c48344948282cdcd42bff414ec90f23b7e3b1b817137664f4016319586395741996245f9c2c66dee453352dc329fe54228beaa559a610114dbe902c32572e954660adbd06f8da8c770c33bb5ad15f506073ea0c50ff4e9906e16ee70d1311e0ad81896f4807282361f5b2116488de06966b571cdb15da536226378bc1fba8a3476c5809b5a274a0117b5de3e52278d39fdfa62de29f338b0453ac3af61a30dcb2975949a3d0ec2d2b7f0d2c4d2e3ef6ddefa8caad21bc16972dcecfcd5f9332373a759632f7f02c52dd424b83985eaa673ce67023366e85899729fc1d1fede02fa9c53aa01328c9108a3c5145f47ef988688f3076d49821314210d1f4db88fa836d41f3dc3960499eb46b28261aaa1515e0fb6d7481ae051b607683cbfdc18d6b692f93d6facf4002d6fa835aac4d61911b66859a81043763e1d0ef6e47f1a7a4c8d57993b0fb67b5758ed3aca9540d39e150935cdd0c320d166da65612ae78322f96853885e6a44add306a899fab2f87cf2a1d和價值 $ C $ 是
0x90fdea0c662ed2cef739c491c2f391d8cf636b80144c412580c02e3262e4fa10c6e101f4c53d09619c7cb6fc9d8edfe2a676c1c128bd8e32528aff243101b9daf655bcd5460a9bf020ff4bef0f61b94304b142b6b18830b8b4d5574e8b54903de67df71f39234fdf9f66723ab1bf426d1c0a95fabae8485e9edf7f4c868ca2816398b1f46ffda2a84b5d52ff36bad829ddc2e123f86cb266256824f047fb6f6a1c7593eaf4ae5c47c6f5e633370d832345fde53324d02687a9b21e60fcefb5e2e2eb1ace969fe72afca67847acad093dec8976336ace5f135257f740f625851a3258854775a3f4f123eae1a6253b2740de37d112bca596f36e4c0d4cfc50b05643b8ec0b52619ae7d0ae990e041ba01bc149ac4a510c81e3aef3f4f2843a50f15c637e274e714c6a768e0c7d96e28a5365b64aee0315623794724573648516ebc9b0f5135a180ac3141a98f2ef0f005f6980781036c9b1c7975774708d1929d1935ae782de80722124220a9dd3fadc457d8bdb8be762b0158187ee619142637d
由於填充是確定性的並且輸入值的數量很少，您可以嘗試使用公鑰加密每個可能的值。如果結果 - 密文 - 與您所擁有的相同，那麼您已經找到了輸入值，因此找到了 PIN。保證你成功 $ 2^{16} $ 畢竟嘗試了 65536 次。
用算術方法描述填充可能會有所幫助：first shift $ p $ （大頭針） $ 2048 $ 左邊的位，所以計算 $ 2^{2048}\cdot p $ . 替換尾隨 $ 0 $ 由 $ 1 $ 我們添加 $ 2^{2048}-1 $ . 所以給定 $ p $ 要由 RSA 函式加密的消息是
$$ m=2^k \cdot p + (2^k-1) = (p+1)\cdot 2^k - 1 $$
和 $ k=2048 $ 並在擂台上工作 $ \mathbb{Z}_n $ .
所以發現 $ p $ 給定 $ C $ 歸結為找到多項式的一個小根 $ (Kx - 1)^e $ 模組 $ n $ （環境 $ K=2^k \pmod{n} $ )，並且您可以使用Coppersmith 的方法來執行此操作，例如在 Sage 或某些此類程序中。我不抱太大希望，但也許有幫助。