離散對數為什麼是難題？

1樓：

When p is small, discrete log can be found by exhaustive search.

The difficulty is on the same order of magnitude as that of factoring primes required for RSA.

DL is an example of one-way function:

A function f isone-wayif

1.Given x, finding f(x) is easy

2.Given y, finding x such that f(x)=y is hard

2樓：玄星

1. 先說明一下「難」的概念。

在計算複雜性理論裡是指，對於乙個（類）問題，設輸入的資料規模為n, 在一般情況下，如果所有的、已知的針對此問題的演算法，其時間複雜度（或空間複雜度，或兩者都）是超過n的多項式級別的話，則這個問題可以視作「困難」的。

也就是說，如果已知的求解問題A的最快速演算法的時間複雜度是,且,使得，注意，c是常數。則A可以被認為是"困難"的。

（ps:以上是本人的大致描述，complexity的嚴謹的定義請參考標準教材。）

常見的」困難「問題往往有指數時間複雜度，比如。

2.密碼學裡，度量輸入規模的單位是bit, 也就是輸入資料的二進位制表達的長度。

比如8這個十進位制數作為輸入的話，對應的輸入規模是4 (因為8的二進位制表示是1000，長度是4個bit)，這裡n=4。

3.離散對數問題 Discrete logarithm

樓上的回答裡，吳斌已經描述了這個問題，相信題主自己也懂這個問題本身。評價乙個問題是否困難，就看解決它的演算法的時間複雜度是怎麼樣的。

3.1. 廣義的DLog目前所知的最佳演算法是 Pollard's rho algorithm for logarithms

時間複雜度是，p可以視為群的大小。（Zp*和EC群有區別，但都可以這麼理解）

乍看起來好像還是低於多項式的複雜度。但是，如果用2進製表示p，(也就是說把p寫成110111....), 設這個二進位制表示的長度為n, 則在密碼學範疇裡，這個複雜度實際上是

3.2. 直接窮舉的情況下，比如逐個計算, 複雜度更驚人,基本上是，n這裡是群的大小的二進位制表示的長度，也可以理解為key的二進位制長度。

如果用1024位的key, 想想是個什麼概念吧，更直觀一點，這個數大概是這個量級，宇宙中原子總數據說才個，世界人口不超過（一百億）

3樓：吳斌

DH 用到的數學: A=g^a (mod p), 離散對數問題是指從已知的A, g, p，很難求得a，這裡的計算很難的關鍵是p是個很大的素數，比如1024-bit, 2048-bit, 3076-bit。

ECC演算法定義在域Fp (或者F2^m)：r=kq(mod p) ，從已知的r, q, p,很難求得k。這裡的p也是大數才安全，但是相對DH位元數可以少很多。

ECC裡192-bit,224-bit,256-bit 的安全性相當於DH1024-bit, 2048-bit, 3076-bit。因為基於ECC的離散對數問題比DH的基於指數模的離散對數問題難度更大。

還有乙個RSA演算法，安全性是基於大數的質因數分解。由於歷史原因，RSA應該仍然是目前使用最廣泛的PK演算法。它Key的長度跟DH類似，現在推薦用2048-bit。

個人建議只要對這些原理性的東西知道個大概就可以了。如果想深入理解需要很強的數學功底，做工程的實在是沒必要。