Small Characteristic DLP (Discrete Log Problem) 被解決

最近幾天在密碼學領域還蠻紅的話題 (雖然預印本在去年就發了),EUROCRYPT 2014 上發表對 DLP (Discrete Log Problem) 的重大進展。

論文在 arXiv 上可以取得:「A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic」。

針對使用小特徵值的有限域 (finite field) 的 DLP 問題 (也就是 Zqk 上) 直接從 sub-exponential 降到 nO(logn) (quasi-polynomial)。最常見到的應該是 Z2n

雖然現有被廣泛使用的密碼系統在使用 DLP 建構時都是用 Zp,但這次的成果絕對寫下了 DLP cryptoanalysis 上的里程碑...

Linux kernel 內的資料結構與演算法...

Theoretical Computer Science Stack Exchange 上,有人問到有沒有哪些軟硬體的 source code 是可以跟學生說明某些經典演算法的重要性:「Core algorithms deployed」。

下面就有人列了 Linux kernel 內的演算法,以及對應的程式碼。相當長的一份列表...

除了 Linux kernel 外,也還有其他大型 open source 專案用到的資料結構與演算法...

不過看到 Bubble sort 是怎樣呢... XD

微軟將在 2016 年會拒絕 SHA-1 的 SSL 安全憑證...

微軟公告將在 2016 年拒絕只有 SHA-1 的 SSL Certificate:「Security Advisory 2880823: Recommendation to discontinue use of SHA-1」。微軟的力量主要是對 IE 瀏覽器的控制。

可以看到文章裡把 MD5 的歷史也拿出來比較,然後對照到 SHA-1,所以宣佈 2016 年後就不吃只有 SHA-1 的 SSL Certificate

比較新的簽章都包含了比較強的 cryptographic hash algorithm,像是 SHA-256 的:

現在差不多 2013 年年底,所以大約還有兩年的時間...

SHA-3 的歷史由來...

Bruce Schneier 的 blog 上看到 SHA-3 的由來:「SHA-3 Status」,而投影片在「Keccak and the SHA-3 Standardization」這裡,裡面有不少資料可以用...

像是 crypto hash function 速度的比較:

後半段看到蠻多有趣的東西,等有空回頭來看...

Fast Inverse Square Root 演算法...

中文稱為「平方根倒數速演算法」,英文則是「Fast Inverse Square Root」。

好像是在 Twitter 還是 Facebook 上看到的 (還是是在其他管道?),仔細看中文版維基百科條目,發現中文版的資料相當完整了 (看了一下歷史記錄,是去年 2012 年 6 月的時候從英文版翻出來的)。

當時很有名的 magic hack,比查表法快:

在1990年代初(也即該演算法發明的大概時間),軟體開發時通用的平方根計算方法多是從尋找表中取得近似值,而這段代碼取近似值耗時比之更短,達到精確度要求的速度也比通常使用的浮點除法計演算法快四倍,

然後還比 CPU 指令集快 XD

由於演算法所生成的用於輸入牛頓法的首次近似值已經相當精確,此演算法所得近似值的精度已可接受,而若使用與《雷神之鎚III競技場》同為1999年發行的Pentium III中的SSE指令rsqrtss計算,則計算平方根倒數的收斂速度更慢,精度也更低。

Update:請參考 comment,看起來中文版有誤譯...

我本來以為我之前寫過,找了找沒翻到... 補記錄下來 :p