在 DLP 情況下以數學方式查找失去的位（完整問題）

在一個預備問題中，我們必須恢復十進制數字@ $ @ $ 的r $ r $ 和s $ s $ 給定

G=51234 $ g=51234 $ ,H=90403 $ h=90403 $ ,ñ=111649 $ N=111649 $ ,r=3@497 $ r=3@497 $ ,s=276@3 $ s=276@3 $ ,

和r $ r $ 和s $ s $ 最小的正解Gr≡H(反對ñ) $ g^r\equiv h\pmod N $ 和Hs≡G(反對ñ) $ h^s\equiv g\pmod N $ .

---

對於大ñ $ N $ 未知因式分解，我們無法計算披(ñ) $ \varphi(N) $ 從ñ $ N $ 正如上面所說的那樣。可以使用哪些技術來解決問題？

---

我嘗試在下面的範例中使用 Index Calculus 但失敗了。這是 2016 年推出的一個非常簡單的問題：

恢復所有數字r $ r $ ,s $ s $ 和因式分解ñ $ N $ .

它被賦予ñ $ N $ ,G $ g $ ,H $ h $ ,r=日誌GH $ r=\log_g h $ 這樣Gr≡H(反對ñ) $ g^r\equiv h\pmod N $ ， 和s=日誌HG $ s=\log_h g $ 這樣Hs≡G(反對ñ) $ h^s\equiv g\pmod N $ ，@計算一個未知的十進制數字：

N = 4770047289861054128673165840475881666985708841069569122247779994575999373990855387188690474135592158102615485877459618836427811081668578893542268141889988869764086285203345206116260923268064851230188829163155218509489708275219402417
g = 1818674628639967921918316591104926407701223436868786162485485191757839034354239408133296195009525639079428182610287045427973123535470060353099447741037582550708917693998695104714221823196243333713913383763090393730760094204741650090
h = 2208658095572997139683467669564020944425802120964728746970717796984260065210935180456703377157524093154996948648279266706057554344748359754567027091354206701512345543745638076145129569549991043944481795915889787265463492997755593901
r =  1@6826295140541573@9405922358@031348321@068314394@23991550@60902965@70229914@6203562@77909154@2484058239@305290554@451041944@77284864589306634379124981555276837338619890402355995522612897221369937487171781010716680@8004465050769716
s =  57@2623169175139588682565993777078629@51369239581656482190187775@98993533114834@931596544472993@0093163506369690@0954113499@984660633390860@46262557530048@277694556546720@7679243674115857@55557012193132332836046587@22597144319762@@

編者註：為了清楚起見，原始問題已更改，不再強調數字範例，並使用此答案中引入的更簡單的符號來回答原始準備問題。

解決方案

ñ $ N $ 是一個沒有瑣碎因素的複合材料，我們的計劃是：

1. 查找缺少的內容r $ r $ （14 位十進制數字）從已知的值ñ $ N $ ,G $ g $ ,H $ h $ , 和關係Gr≡H(反對ñ) $ g^r\equiv h\pmod N $ ，使用嬰兒步巨步離散對數算法的微小變化。
2. 同樣在s $ s $ .
3. 提高Gr≡H(反對ñ) $ g^r\equiv h\pmod N $ 對權力s $ s $ 然後替換Hs≡G(反對ñ) $ h^s\equiv g\pmod N $ 給Gr⋅s≡G(反對ñ) $ g^{r\cdot s}\equiv g\pmod N $ . 因此r⋅s−1 $ r\cdot s-1 $ ，我們現在可以計算，是G $ g $ ，因此有一個公平的機會成為的倍數披(ñ)/2 $ \varphi(N)/2 $ .

注意：這不確定！在預備題G $ g $ 是有序的披(ñ)/2 $ \varphi(N)/2 $ , 並且在完整的問題中希望順序是最好的也是合理的披(ñ)/2 $ \varphi(N)/2 $ 或者披(ñ) $ \varphi(N) $ . 然而，如果G $ g $ 已隨機選擇，其順序可能是的倍數披(ñ)/C $ \varphi(N)/c $ 對於一些小C $ c $ 劃分披(ñ) $ \varphi(N) $ ， 和C $ c $ 可以搜尋到。 4. 因素ñ $ N $ 從它的價值和倍數的披(ñ)/2 $ \varphi(N)/2 $ 剛剛獲得。

---

尋找完整的r $ r $ 與嬰兒步巨步

我們在基地工作b $ b $ 和缺少的數字r $ r $ 在索引一世 $ i $ 在集合中米 $ \Bbb M $ （從右邊的索引 0 開始），並且可以寫r=^r+∑一世∈米X一世b一世 $ \displaystyle r=\hat r+\sum_{i\in\Bbb M}x_i,b^i $ 有未知數X一世∈[0,b) $ x_i\in[0,b) $ . 這裡b=10 $ b=10 $ ,^r $ \hat r $ 是通過以@給0定形式替換為r $ r $ ，@從右邊開始的14個索引是米={16,106,116,126,137,146,154,163,172,181,191,201,212,229} $ \Bbb M={16,106,116,126,137,146,154,163,172,181,191,201,212,229} $ .

我們分手了米 $ \Bbb M $ 大約均勻地分成不相交的子集在 $ \Bbb U $ 和在 $ \Bbb V $ 並重寫Gr≡H(反對ñ) $ g^r\equiv h\pmod N $ 作為

Gr≡H(反對ñ)G(^r+∑一世∈米X一世b一世)≡H(反對ñ)G^r⋅∏一世∈米(G(b一世))X一世≡H(反對ñ)G^r⋅∏一世∈在(G(b一世))X一世≡H⋅∏一世∈在(G(−b一世))X一世(反對ñ)

$$ \begin{array}{llll} g^r&\equiv&h&\pmod N\ g^{\left(\hat r+\displaystyle\sum_{i\in\Bbb M}x_i,b^i\right)}&\equiv&h&\pmod N\\ g^{\hat r}\cdot\displaystyle\prod_{i\in\Bbb M}\left(g^{(b^i)}\right)^{x_i}&\equiv&h&\pmod N\ g^{\hat r}\cdot\displaystyle\prod_{i\in\Bbb U}\left(g^{(b^i)}\right)^{x_i}&\equiv&h\cdot\displaystyle\prod_{i\in\Bbb V}\left(g^{(-b^i)}\right)^{x_i}&\pmod N \end{array} $$ 我們預先計算G−1反對ñ $ g^{-1}\bmod N $ （使案例如半擴展歐幾里得算法），以及(G−1)(b一世)反對ñ $ \left(g^{-1}\right)^{(b^i)}\bmod N $ 為了一世∈在 $ {i\in\Bbb V} $ ，然後可以順序計算並儲存在允許快速搜尋所有的資料結構中b|在| $ b^{|\Bbb V|} $ 的值(H⋅∏一世∈在(G(−b一世))X一世)反對ñ $ \displaystyle\left(h\cdot\prod_{i\in\Bbb V}\left(g^{(-b^i)}\right)^{x_i}\right)\bmod N $ （除了匹配的元組X一世 $ x_i $ 為了一世∈在 $ i\in\Bbb V $ ）。我們從H $ h $ 對所有人X一世=0 $ x_i=0 $ 和一世∈在 $ {i\in\Bbb V} $ 並為彼此執行一次模乘（我們需要|在| $ |\Bbb V| $ 中間變數，包括H $ h $ ).

我們預先計算G^r反對ñ $ g^{\hat r}\bmod N $ 和G(b一世)反對ñ $ g^{(b^i)}\bmod N $ 為了一世∈在 $ {i\in\Bbb U} $ ，並在所述資料結構中依次計算和搜尋G^r⋅(∏一世∈在(G(b一世))X一世)反對ñ $ g^{\hat r}\cdot\displaystyle\left(\prod_{i\in\Bbb U}\left(g^{(b^i)}\right)^{x_i}\right)\bmod N $ . 我們從G^r反對ñ $ g^{\hat r}\bmod N $ 對所有人X一世=0 $ x_i=0 $ 和一世∈在 $ {i\in\Bbb U} $ 並為彼此執行一次模乘（我們需要|在| $ |\Bbb U| $ 中間變數，包括G^r $ g^{\hat r} $ ）。當我們得到一場比賽時，這給了我們所有的X一世∈米 $ x_i\in\Bbb M $ （那些從在 $ \Bbb V $ 來自資料結構，那些來自在 $ \Bbb U $ 是導致比賽的那個），因此完整r $ r $ .

最壞情況的計算工作主要由大約2b|米|/2 $ 2,b^{|\Bbb M|/2} $ （這裡是 20,000,000）模乘模ñ $ N $ （這裡，花費大約2⌈(日誌2ñ)/32+1⌉2<1500 $ 2,\lceil(\log_2N)/32+1\rceil^2<1500 $ 32 位變數的基本乘法和使用教科書算法的 64 位結果的加法）。我們正在談論幾分鐘的執行時間，以及不到 3 MB 的記憶體（並且通過|在| $ |\Bbb V| $ 更小，我們將記憶體需求減少了一個因素b $ b $ ，以執行時間為代價）。

引用自：https://crypto.stackexchange.com/questions/60611