為高效率密碼工程設計之特定領域語言

A Domain-Specific Language for Efficient Cryptographic Engineering

郝柏翔(Po-Hsiang Hao)

指導教授 ： 鄭振牟

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2014年)

https://doi.org/10.6342/NTU.2014.00553

摘要

實作密碼學系統時,常見許多多維代數結構間的運算。若要在較低階的組合語言上實作,必須轉換成基本元素的運算。運算數量龐大時,必須有自動化工具來輔助。此外,在低階語言上無法高階地描述系統或演算法,增加程式設計者的困難,以及出錯的可能性。
我們提出一個嵌於Haskell中的特定領域語言,讓程式設計者能以方便的語法和多維的代數結構,描述密碼演算法和系統。程式會被表示成樹狀的表示式,並且由編譯器自動展開代數結構的運算,轉成中間語言,再進行優化並產生目標語言。
編譯器結合了兩個優化器,並且實作了兩種目標語言,分別是Hydra處理器上的組合語言,以及C++,支援的代數結構有擴張體和矩陣。程式設計者也能加入自己所需的代數結構、優化或是目標語言。我們在此特定領域語言上實作了兩個應用:最佳配對和一個基於LWE的密鑰交換系統。
使用此特定領域語言實作密碼系統,可將數學演算法、優化和輸出語言各自獨立,節省重複的工作,並且程式設計者在實作時可把重點放在密碼系統高階的描述。

關鍵字

密碼工程 ； 特定領域語言 ； Haskell ； Hydra處理器 ； 編譯器優化

並列摘要

Multidimensional algebraic structures are common in the description of cryptographic systems. They have to be translated to computations between basic elements by automation before being implemented on low-level assembly languages. Besides, the programmer cannot write programs in a high-level way, which makes them more error-prone.
In this thesis, we propose a domain-specific language embedded in Haskell, so that the programmer can implement cryptographic systems in convenient syntax. The computations of algebraic structures will be expanded, supporting extension fields and matrices.
Our compiler is combined with two optimizers, and supports two target languages: Hydra assembly and C++. The programmer can add his own algebraic structures, optimizations, and target language as needed. We also implement two applications in this DSL: optimal pairing and a key exchange with LWE.
The algorithm description, optimizations and code generations is separated and independent. The programmer can focus on the high-level descriptions of the cryptographic systems.

並列關鍵字

cryptographic engineering ； domain-specific language ； Haskell ； Hydra coprocessor ； compiler optimizations

參考文獻

[Axe12] Emil Axelsson. A generic abstract syntax model for embedded languages. In ACM SIGPLAN Notices, volume 47, pages 323–334. ACM, 2012.

[CHH+] Y.-A. Chang, W.-C. Hong, M.-C. Hsiao, B.-Y. Yang, A.-Y. Wu, and C.-M. Cheng. Hydra: An energy-efficient programmable cryptographic coprocessor supporting elliptic-curve pairing over fields of large char- acteristics. To appear in the 9th International Workshop on Security (IWSEC 2014), Hirosaki, Japan, Aug. 2014.

[EFDM03] Conal Elliott, Sigbjorn Finne, and Oege De Moor. Compiling embedded languages. Journal of Functional Programming, 13(3):455–481, 2003.

[Hug95] John Hughes. The design of a pretty-printing library. In Advanced Functional Programming, pages 53–96. Springer, 1995.

[Hut92] Graham Hutton. Higher-order functions for parsing. J. Funct. Program., 2(3):323–343, 1992.