DNA 計算能否使用這種方法求解橢圓曲線算法
本文作者：基於 DNA 計算的快速並行分子算法：求解橢圓曲線離散對數問題 $ GF(2^n) $ 提出了一種基於 DNA 計算的新算法，他們聲稱（至少在理論上）可以在多項式時間內解決橢圓曲線算法。
文章摘錄：
“我們已經構造了上面的算法，用於並行計算兩點之和的點。然後，我們可以解決橢圓曲線離散對數問題如下：考慮給定點P和Q，而l是我們想要得到的匹配Q = lP。首先我們把P放大成兩管，把P加到一個管裡。檢查2P是否等於Q；如果不等於Q，記下2P的值，把兩管倒在一起。然後，把管放大成兩管在一根管子裡加2P，檢查是否有點等於Q；如果不是，記下4P的值，把兩管子倒在一起，或者我們得到l的值，然後把管子放大成兩管子，在裡面加4P一根管子，……，當這個循環執行 n 次時，l 的值從 1 到 2n 將被檢查，橢圓曲線密碼系統已被求解的橢圓曲線離散對數問題破壞。"
我剛開始將密碼學作為一種愛好來學習，所以我對它還不太熟悉。有人可以用更簡單的方式向我解釋他們的策略嗎？他們的策略在現實生活中實用嗎？作者聲稱他們可以“在多項式時間內”解決橢圓曲線算法，但我不太確定……
**TL：博士；**該算法是並行工作的，但由於安全曲線的 DNA 鏈數量要求，因此不實用。通用離散對數算法可以輕鬆擊敗這一點，$$ see here $$.
算法
算法在理論上起作用。作者使用 $ Q =lP $ 讓我們改變它 $ Q = [x]P $ .
實際上，他們的方法與任何 DNA 算法一樣**高度並行化。**DNA算法實際上非常擅長並行化。
讓我們呼叫他們的算法
amplify-and-double-and-add；t1 = P / here t is tube while x not found: t1.amplify() t2.amplifyWith(t1) t1.add(t1) if t1 contains Q return matched value t1 = pour(t1,t2)可以看出，該算法實際上也計算了中間值。while 循環需要 $ \lfloor(\log x)\rfloor +1 \in \mathcal{O}(\log n) $ -腳步。加法由
AddTwoNode需要的算法執行 $ O(n^3) $ 提取操作， $ O(n^3) $ 追加操作， $ O(n^3) $ 合併操作，和 $ O(n) $ 橢圓曲線平行加法器的試管。這 $ n $ 是二進制伽羅瓦域的擴展數 $ GF(2^n) $ 在考慮中。因此對於像 Edwards25519 這樣的曲線，我們有 $ n=255 $
- $ \approx 2^{24} $ 提取操作
- $ \approx 2^{24} $ 追加操作
- $ \approx 2^{24} $ 合併操作
- $ \approx 2^8 $ 試管。
私人隨機密鑰 $ x $ 也是255位左右 $ \approx 2^{8} $ . 然後總共
amplify-and-double-and-add需要;
- $ \approx 2^{32} $ 提取操作
- $ \approx 2^{32} $ 追加操作
- $ \approx 2^{32} $ 合併操作
- $ \approx 2^{16} $ 試管 （？）。
文章結尾的註釋
因此在理論上是可行的，並啟發了 DNA 計算的發展。這表明如果 DNA 計算技術足夠熟練以有效地執行本文所討論的算法，那麼橢圓曲線密碼系統可能是不安全的。
注意事項
DNA 計算是從 Adleman 的小說開始的，或者看這裡。自從他們進行了真正的實驗以來，Adleman 幾乎把所有的步驟都寫得很清楚了。在這篇文章中，沒有關於它的實驗或任何計算。我也找過，也沒有找到。
這項工作顯然是一項理論工作，並沒有計算任何有關 DNA 計算的時間或數量的內容。例如;
- 例如，一次PCR可能需要大約 1 小時，不清楚算法需要多少次迭代？
- 該算法的規模尚不清楚。現在在實踐中，試管可以包含 $ 2^{18} $ DNA 鏈
- 未解釋/計算所需 DNA 鏈的數量。最後一步的最後一根管子的要求是什麼？我們可以簡單地說，如果它是好的，它在論文中。
- 沒有計算他們的算法對像 edwars25519 這樣的曲線需要多少。
- 試管操作的時間 - 提取、合併、放大、追加和追加頭部 - 沒有給出。
- 寫於 2008 年，根據Google學術只有 18 次引用。這對於真正的開創性工作來說太低了。
- 他們的 7 種算法的時序至少在撰寫本文時沒有給出技術的目前階段。Adleman 在實驗室中花了 7 天時間繪製了一個包含 7 個城市的圖表，耗時 54 秒。
所需的 DNA 鏈數
讓我們打電話 $ \text{D-SPACE} $ 用於執行任何算法所需的 DNA 鏈。任何步驟中的
amplify-and-double-and-add算法都會計算介於 $ [2^k,2^{k-1}] $ ， 儘管 $ 1<k\leq x $ .讓我們忘記中間步驟，專注於最後一步。我們需要周圍 $ 2^{555}\text{-D-SPACE} $ 以便所有值都可以出現在要匹配的管中 $ x $ . 這個數量太大了，比宇宙中粒子的數量還要少一點；那就是 $ 3.28 \times 10^{80} \approx 2^{266} $ .
結論
不實用，因為 $ 2^{555}\text{-D-SPACE} $ 對於曲線 Edwards25519 甚至 128 位曲線。