建構增強橢圓曲線離散對數計算Chor-Rivest 迷袋生物資訊密碼系統

Constructing the Chor-Rivest Knapsack Bioinformatics Cryptosystem Enhanced with Elliptic Curve Discrete Logarithms

陳翔靖(Hsiang-Ching Chen)

指導教授 ： 何善輝 ； 洪昆裕

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

摘要

公鑰密碼系統(Public Key Cryptosystem) 於1976 由W.Diffie 和M.Hellman 首先提出概念，應用在公鑰密碼系統有兩類，一種為函數，另一種是非函數。
質因數分解為非函數的一種，質因數分解就是給出兩個大質數，很容易就能將它們兩個相乘。但是，給出它們的乘積，找出它們的因子就顯得不是那麼容易了。這就是許多現代密碼系統的關鍵所在。如果能夠找到解決整數分解問題的快速方法，幾個重要的密碼系統將會被攻破。
橢圓曲線離散對數問題是被公認為非常困難的，因為它也是一個非常困難的單向函數，有不可逆的特性，並且在相同安全強下以至於他是NP-complete問題。並且在計算時主要是找橢圓曲線離散對數的橢圓曲線的點來帶入公式，因為橢圓曲線的點讓人很難去猜測點的順序。可以利用這特性來混淆私鑰跟公鑰的多項式順序來增加安全性。雖然在1994 Peter Williston Shor提出在量子電腦應用上的Shor's algorithm，來解決，但缺點在運算時間上也需要多項式時間花費O((logN)3)的時間，顯得非常沒有效率。
迷袋問題是一個集合問題也是非函數問題，利用集合來求出子集合的組合，當集合很少時，非常的好解決，但當集合很大時，就變成一個NP-complete問題，因此我們把它應用在公鑰密碼系統上。不過雖然迷袋是NP-complete問題，近幾年來還是被破解了。Chor-Rivest迷袋公鑰系統有快速加密跟解密的優點，並且解密時需要使用模乘積(mod)增加安全性，但近幾年也陸續被破解。因此在本研究中，我們加入橢圓離散對數來增加計算的困難性。
在本研究中我們結合函數和非函數問題，建構以Chor-Rivest迷袋問題為基礎來加強橢圓曲線離散對數的迷袋生物資訊密碼系統。首先利用迷袋的集合問題，來產生有限集合，再利用離散對數計算來產生公鑰和私鑰。在計算的過程，我們在多項式的裡加入平移，混淆公鑰和私鑰之間的關係，來加強預防公鑰被破解後，能保護私鑰的安全性。因為不論是迷袋的組合問題還是離散對數都是NP-complete問題.所以非常的困難被破解，因為架構離散對數的Chor-Rivest迷袋密碼系統，時間複雜度是需要O(2*nh)。所以我們利用生物資訊邏輯閘來架設離散對數的Chor-Rivest迷袋密碼系統，來改善離散數學Chor-Rivest迷袋密碼系統建構的效率。其時間複雜度減為O(2*n3).。但是離散數學Chor-Rivest迷袋生物資訊密碼系統的本質不會變，因此仍然是不可逆而且是幾乎不可能被破解。

關鍵字

生物資訊計算 ； NP-Complete ； 橢圓離散對數 ； Chor-Rivest密碼系統 ； 迷袋問題

並列摘要

Prime factorization of a non-function, the prime factorization of two large prime numbers is given , they can easily be multiplied by two. However, given their product, it becomes a factor to identify them is not so easy. This is why many modern cryptography key. If we can find a solution to the problem of fast integer factorization method, several important cryptographic systems will be broken.
Elliptic curve discrete logarithm problem is acknowledged to be very difficult, because it is also a very difficult one-way function, there is an irreversible characteristic, and under the same Anquan Jiang that he is NP-complete problems. And in the calculation is mainly looking into the elliptic curve point formulas, because elliptic curve points make it difficult to guess the point of order, because the linear curve that people can easily guess, thus increasing the complexity of the formula. This feature can be used to confuse the private key with the public key polynomial order to increase security.
The problem is a collection of Knapsack issue is non-functional, the use of a combination of a subset of the collection to determine when a collection of rare, the very good solution, but the collection is large, it becomes an NP-complete problem, so we put it is used in public key cryptography system. But while Knapsack are NP-complete problem, in recent years or are cracked. Chor-Rivest knapsack encrypted with the public key to decrypt the system has the advantages of knapsack. Decryption requires the use of mold product to increase security, but in recent years is starting to crack. Therefore, we add the discrete logarithm to increase the difficulty of computing. Elliptic Curve Discrete logarithm problem is acknowledged to be very difficult, because it is also a very difficult one-way function, there is irreversible characteristics, that he is NP-complete problems. Although raised in the 1994 Peter Williston Shor quantum computer applications in the Shor's algorithm, to solve, but the disadvantage is also needed in the computing time spent in polynomial time O ((logN3) of the time, it is very inefficient.
In this study, we constructed the Chor-Rivest Knapsack to enhance problem-based Discrete Logarithm Knapsack cryptography. Firstly, Knapsack collection problems, to generate a finite set, then use the discrete logarithm calculations to generate public and private keys. In the calculation process, we have added in polynomial translation, confusion between public and private key to the public key to be cracked strengthen prevention, can protect the private key security.
Because of both Knapsack and discrete logarithms problems are NP-complete; it is very difficult to crack. The structure of the discrete logarithm Chor-Rivest knapsack cryptosystem system takes O (2 * nh) time complexity. So we proposed a Chor-Rivest knapsack bioinformatics cryptosystem enhanced with discrete logarithm for its construction to be more effectively. Hence, the construction time complexity is reduced to O (2 * n3). It’s worth mentioning that the nature of Chor-Rivest knapsack bioinformatics cryptosystem enhanced with discrete logarithm is not changed. It is still irreversible and almost impossible to breakthrough.

並列關鍵字

Optimization ； Bioinformatics Computing ； NP-Complete ； Elliptic Curve Discrete Logarithm ； Chor-Rivest Cryptosystem ； Knapsack problem ； Cryptosystem

參考文獻

1. Diffie, W. and Hellman, M.E. (1976). New Directions in Cryptography. IEEE Transactions

2. L. M. Adleman, "On breaking generalized knapsack public key cryptosystems," in Proc. 15th ACM Symposium on Theory of Computing, pp. 402-412, 1983.

4. B. Chor, R.L. Rivest. A knapsack-type public key cryptosystem based on arithmetic in nite elds. In Advances in Cryptology CRYPTO'84, Santa Barbara, California, 1985.

5. L.M.Adleman, A subexponential algorithm for the discrete logarithm problem with application to cryptography , Proc. Of the 20th Annual IEEE Symposium on Foundations of Computer Science(1979), 55-60.

7. Adleman, L. M. (1994). “Molecular computation of solutions to combinatorial problems.” Science, 266(5187), 1021-1024.