A Knapsack Public-Key Cryptosystem Based on Elliptic Curve Discrete Logarithm

隨著電腦網路與通訊系統蓬勃發展，資料保密儼然已成為基本且重要的問題。密碼系統的設計可以基於各種理論，如數論、線性代數或編碼理論等。好的密碼系統除考慮其安全性外，尚須考慮其執行加、解密之速度，以免造成通訊瓶頸或時間浪費。RSA 公開金鑰加密系統是於1978 年所提出。從那時開始，RSA 系統已是被接受的公開金鑰加密系統，其安全性建構在因式分解(Factoringproblem)之問題上。現今最快的因式分解方法是利用General NumberFieldSieve(GNFS)。到目前為止，由於電腦技術及因式分解演算法的發展，標準512 位元的RSA 模數已不再被認為是安全，且有其他模式加以解決。橢圓曲線密碼系統（Elliptic Curve Cryptosystem, ECC）最近被討論。自從80年代中期被引進以來，橢圓曲線密碼系統已成為一個十分令人感到興趣的密碼學分支，1997 年以來更形成一個研究重點。這種密碼系統的誘人之處在於安全性相同的前提下，可使用較短的私密金鑰。給定Q=kP，Q 與P 都屬於ECC的範圍，則從Q與kP中決定k 是很困難。再加上其他密碼技術，則安全度更應該提高。一般認?，q 位元域上的橢圓曲線密碼系統，當q 的長度約?160bit時，其安全性相當於RSA使用約1024bit模數。故本計畫擬從被包理論(Knapsack problem)的基礎起，依單純(Simplest)與複雜(Complexity)被包理論轉換再加上ECC 具有的特性，將從整體研究與分析，以研究橢圓曲線快速指數運算為基礎，提出不同於以往學者所提的應用方法，並結合背包理論，設計一套植基於Knapsack 及ECDLP難題的公開金匙密碼機制，期許能對浩瀚的密碼學研究研究裡，掀起一波小小的漣漪。

Project ID:PB9508-4003
External Project ID:NSC95-2221-E182-031