The key operation in Elliptic Curve Cryptosystems(ECC) is point scalar multiplication. Making use of Frobenius endomorphism, Muller and Smart proposed two efficient algorithms for point scalar multiplications over eve...The key operation in Elliptic Curve Cryptosystems(ECC) is point scalar multiplication. Making use of Frobenius endomorphism, Muller and Smart proposed two efficient algorithms for point scalar multiplications over even or odd finite fields respectively. This paper reduces the corresponding multiplier by modulo Υk-1 +…+Υ+ 1 and improves the above algorithms. Implementation of our Algorithm 1 in Maple for a given elliptic curve shows that it is at least as twice fast as binary method. By setting up a precomputation table, Algorithm 2, an improved version of Algorithm 1, is proposed. Since the time for the precomputation table can be considered free, Algorithm 2 is about (3/2) log2 q - 1 times faster than binary method for an elliptic curve over展开更多
Let q be a power of a prime and φ be the Frobenius endomorphism on E(Fqk), then q = tφ - φ^2. Applying this equation, a new algorithm to compute rational point scalar multiplications on elliptic curves by finding...Let q be a power of a prime and φ be the Frobenius endomorphism on E(Fqk), then q = tφ - φ^2. Applying this equation, a new algorithm to compute rational point scalar multiplications on elliptic curves by finding a suitable small positive integer s such that q^s can be represented as some very sparse φ-polynomial is proposed. If a Normal Basis (NB) or Optimal Normal Basis (ONB) is applied and the precomputations are considered free, our algorithm will cost, on average, about 55% to 80% less than binary method, and about 42% to 74% less than φ-ary method. For some elliptic curves, our algorithm is also taster than Mǖller's algorithm. In addition, an effective algorithm is provided for finding such integer s.展开更多
In this paper,the integer N = pkq is called a <k,1>-integer,if p and q are odd primes with almost the same size and k is a positive integer. Such integers were previously proposed for various cryptographic appli...In this paper,the integer N = pkq is called a <k,1>-integer,if p and q are odd primes with almost the same size and k is a positive integer. Such integers were previously proposed for various cryptographic applications. The conditional factorization based on lattice theory for n-bit <k,1>-integersis considered,and there is an algorithm in time polynomial in n to factor these integers if the least significant 「((2k-1)n)/((3k-1)(k+1))」bits of p are given.展开更多
Wireless Sensor Networks (WSNs) are being deployed for a wide variety of applications and the security problems of them have received considerable attention. Considering the limitations of power, computation capabilit...Wireless Sensor Networks (WSNs) are being deployed for a wide variety of applications and the security problems of them have received considerable attention. Considering the limitations of power, computation capability and storage resources, this paper proposed an efficient defense against collusion scheme based on elliptic curve cryptography for wireless sensor networks in order to solve the problems that sensor node-key leaking and adversaries make compromised nodes as their collusions to launch new attack. In the proposed scheme, the group-key distribution strategy is employed to compute the private key of each sensor node, and the encryption and decryption algorithms are constructed based on Elliptic Curve Cryptography (ECC). The command center (node) only needs to broadcast a controlling header with three group elements, and the authorized sensor node can correctly recover the session key and use it to decrypt the broadcasting message. Analysis and proof of the proposed scheme's efficiency and security show that the proposed scheme can resist the k-collusion attack efficiently.展开更多
We define the notion of special automorphisms on Shimura curves. Using this notion, for a wild class of elliptic curves defined over Q, we get rank one quadratic twists by discriminants having any prescribed number of...We define the notion of special automorphisms on Shimura curves. Using this notion, for a wild class of elliptic curves defined over Q, we get rank one quadratic twists by discriminants having any prescribed number of prime factors. Finally, as an application, we obtain some new results on Birch and Swinnerton-Dyer(BSD) conjecture for the rank one quadratic twists of the elliptic curve X_0(49).展开更多
基金Supported by the National Natural Science Foundation of China(No.90104004) the National 973 High Technology Projects(No.G1998030420)
文摘The key operation in Elliptic Curve Cryptosystems(ECC) is point scalar multiplication. Making use of Frobenius endomorphism, Muller and Smart proposed two efficient algorithms for point scalar multiplications over even or odd finite fields respectively. This paper reduces the corresponding multiplier by modulo Υk-1 +…+Υ+ 1 and improves the above algorithms. Implementation of our Algorithm 1 in Maple for a given elliptic curve shows that it is at least as twice fast as binary method. By setting up a precomputation table, Algorithm 2, an improved version of Algorithm 1, is proposed. Since the time for the precomputation table can be considered free, Algorithm 2 is about (3/2) log2 q - 1 times faster than binary method for an elliptic curve over
基金Supported by the National 973 High Technology Projects (No. G1998030420)
文摘Let q be a power of a prime and φ be the Frobenius endomorphism on E(Fqk), then q = tφ - φ^2. Applying this equation, a new algorithm to compute rational point scalar multiplications on elliptic curves by finding a suitable small positive integer s such that q^s can be represented as some very sparse φ-polynomial is proposed. If a Normal Basis (NB) or Optimal Normal Basis (ONB) is applied and the precomputations are considered free, our algorithm will cost, on average, about 55% to 80% less than binary method, and about 42% to 74% less than φ-ary method. For some elliptic curves, our algorithm is also taster than Mǖller's algorithm. In addition, an effective algorithm is provided for finding such integer s.
基金the National Natural Science Foundation of China (No.60473021).
文摘In this paper,the integer N = pkq is called a <k,1>-integer,if p and q are odd primes with almost the same size and k is a positive integer. Such integers were previously proposed for various cryptographic applications. The conditional factorization based on lattice theory for n-bit <k,1>-integersis considered,and there is an algorithm in time polynomial in n to factor these integers if the least significant 「((2k-1)n)/((3k-1)(k+1))」bits of p are given.
基金Supported by the Six Great Talent Peak Plan of Jiangsu Province (No.06-E-044)the "Qinlan Project" Plan of Jiangsu Province 2006
文摘Wireless Sensor Networks (WSNs) are being deployed for a wide variety of applications and the security problems of them have received considerable attention. Considering the limitations of power, computation capability and storage resources, this paper proposed an efficient defense against collusion scheme based on elliptic curve cryptography for wireless sensor networks in order to solve the problems that sensor node-key leaking and adversaries make compromised nodes as their collusions to launch new attack. In the proposed scheme, the group-key distribution strategy is employed to compute the private key of each sensor node, and the encryption and decryption algorithms are constructed based on Elliptic Curve Cryptography (ECC). The command center (node) only needs to broadcast a controlling header with three group elements, and the authorized sensor node can correctly recover the session key and use it to decrypt the broadcasting message. Analysis and proof of the proposed scheme's efficiency and security show that the proposed scheme can resist the k-collusion attack efficiently.
文摘We define the notion of special automorphisms on Shimura curves. Using this notion, for a wild class of elliptic curves defined over Q, we get rank one quadratic twists by discriminants having any prescribed number of prime factors. Finally, as an application, we obtain some new results on Birch and Swinnerton-Dyer(BSD) conjecture for the rank one quadratic twists of the elliptic curve X_0(49).