Fast Parallel Molecular Algorithms for DNA-Based Computation: Solving the Elliptic Curve Discrete Logarithm Problem over GF(2{sup}n)

摘要

The analogs based on elliptic curve over finite fields of public-key cryptosystems are algorithms that converts input data to an unrecognizable encryption and converts the unrecognizable data back into its original decryption form. The security of the Elliptic Curve public-key cryptosystem is based on the difficulty of the discrete logarithm problem on elliptic curve, especially over GF(2{sup}n), n∈Z{sup}+. This paper demonstrates to find the discrete logarithm on elliptic curve, and is a breakthrough in basic biological operations using a molecular computer. In order to achieve this, we propose three DNA-based algorithms for parallel adder, parallel multiplier, and parallel getting inverse over GF(2{sup}n). The biological operation time of these algorithms are all polynomial with respect to n. This work indicates that the cryptosystems using public-key are perhaps insecure and also presents clear evidence of the ability of molecular computing to perform complicated mathematical operations.