Let n = a(2)b, where b is square-free. In this paper we present an algorithm based on class groups of binary quadratic forms that finds the square-free decomposition of n,i.e. a and b, in heuristic expected time: (O) ...
详细信息
Let n = a(2)b, where b is square-free. In this paper we present an algorithm based on class groups of binary quadratic forms that finds the square-free decomposition of n,i.e. a and b, in heuristic expected time: (O) over tilde (L-b[1/2,1] ln(n)+L-b[1/2,1/2] ln(n)(2)). If a,b are both primes of roughly the same cryptographic size, then our method is currently the fastest known method to factor n. This has applications in cryptography, since some cryptosystems rely on the hardness of factoring integers of this form
A time lock puzzle (TLP) is an interesting cryptographic primitive used to lock messages for a limited time period. After the desired time interval, the puzzle solver can know the message. Chained time lock puzzle (C-...
详细信息
A time lock puzzle (TLP) is an interesting cryptographic primitive used to lock messages for a limited time period. After the desired time interval, the puzzle solver can know the message. Chained time lock puzzle (C-TLP) is multi instance time lock puzzle where the solution of any instance depends on the previous instance. In this paper, we design a CTLP with security relying on the integer factorization problem (IFP). The size of the output puzzle is smaller than the size in the existing C-TLPs. (c) 2025 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
Polynomial selection is very important in the number field sieve. If the number of relations a pair of polynomials can generate is closely correlated with the coefficients of the polynomials, we can select polynomials...
详细信息
Polynomial selection is very important in the number field sieve. If the number of relations a pair of polynomials can generate is closely correlated with the coefficients of the polynomials, we can select polynomials by checking the coefficients first, which can speed up the selection of good polynomials. In this paper, we aim to study the correlation between polynomial coefficients and the number of relations the polynomials can generate. By analyzing the zero roots, it is found that a polynomial with the ending coefficient containing more small primes usually can generate more relations than the one whose ending coefficient contains less. As a polynomial with more real roots usually can generate more relations, using the complete discrimination system,the requirements on the coefficients of a polynomial to obtain more real roots are analyzed. For instance, a necessary condition for a polynomial of degree d to have d distinct real roots is that the coefficient of degree d- 2should be negative or small enough. The result in the case d = 3 can be used directly in selecting polynomials generated by the nonlinear method, where d = 3 is already enough for practical purpose.
We address the factorization problem in this paper: Given an integer N=pq, find two factors p and q of N such that p and q are of same bit-size. When we say integer multiplication of N, we mean expressing N as a produ...
详细信息
We address the factorization problem in this paper: Given an integer N=pq, find two factors p and q of N such that p and q are of same bit-size. When we say integer multiplication of N, we mean expressing N as a product of two factors p and q such that p and q are of same bit-size. We work on this problem in the light of Binary Decision Diagrams (BDD). A Binary Decision Diagram is an acyclic graph which can be used to represent Boolean functions. We represent integer multiplication of N as product of factors p and q using a BDD. Using various operations on the BDD we present an algorithm for factoring N. All calculations are done over GF(2). We show that the number of nodes in the constructed BDD is O(n3) where n is the number of bits in p or q. We do factoring experiments for the case when p and q are primes as in the case of RSA modulus N, and report on the observed complexity. The multiplication of large RSA numbers (that cannot be factored fast in practice) can still be easily represented as a BDD.
作者：
Wang, BaocangHu, YupuXidian Univ
Key Lab Comp Networks & Informat Secur Xian 710071 Peoples R China Chinese Acad Sci
Inst Software State Key Lab Informat Secur Beijing 100049 Peoples R China
Combinatorial problems serve as an important resource for developing practical public key cryptosystems and several combinatorial cryptosystems have been proposed in the cryptographic community. In this paper, a combi...
详细信息
Combinatorial problems serve as an important resource for developing practical public key cryptosystems and several combinatorial cryptosystems have been proposed in the cryptographic community. In this paper, a combinatorial public key cryptosystem is proposed. The security of the proposed cryptosystem is dependent on a combinatorial problem involving matrices. The system features fast encryption and decryption. However, the system also suffers from some drawbacks. The ciphertext expansion is relatively large and the key sizes are somewhat larger than that of RSA. The security of the system is carefully examined by illustrating the computational infeasibilities of some attacks on the system.
Linear Feedback Shift Registers are a commonly used method of producing pseudo-random sequences with large period. This paper investigated another applications of the third-order linear feedback shift register sequenc...
详细信息
Linear Feedback Shift Registers are a commonly used method of producing pseudo-random sequences with large period. This paper investigated another applications of the third-order linear feedback shift register sequence (3-LFSR). It proposed two methods for directly constructing probabilistic public-key encryption primitives. The proposed probabilistic encryption schemes have properties of one-wayness and semantic security. (c) 2005 Elsevier Inc. All rights reserved.
Proxy signature is a cryptographic primitive used for delegating the signing rights. The security of most existing proxy signature schemes is based on the complexity assumptions of discrete logarithms and the intracta...
详细信息
Proxy signature is a cryptographic primitive used for delegating the signing rights. The security of most existing proxy signature schemes is based on the complexity assumptions of discrete logarithms and the intractable problems of elliptic curves. While several proxy signature schemes from integer factorization were proposed, unfortunately they cannot resist against the attacks lunched by a malicious original signer or a malicious proxy signer. Hence, it is an interesting research problem on how to construct a provably secure proxy signature scheme based on factorization. In this paper, we propose a new construction of proxy signature whose security is reduced to the integer factorization problem in the random oracle model. We demonstrate that our scheme outperforms the other existing schemes in terms of security, computational efficiency and the length of the public key. Our scheme is the first provably secure proxy signature scheme from integer factorization. (C) 2011 Elsevier Ltd. All rights reserved.
Large number factorization is not only the most critical entry point for Rivest-Shamir-Adleman (RSA) security analysis, but also the most direct means of attacking the asymmetric encryption algorithm RSA. In this pape...
详细信息
Large number factorization is not only the most critical entry point for Rivest-Shamir-Adleman (RSA) security analysis, but also the most direct means of attacking the asymmetric encryption algorithm RSA. In this paper, the factorization methods of large numbers are summarized and analysed: classical integer factoring algorithms, Shor's circuit model algorithm, quantum adiabatic methods (integer factorization based on a quantum nuclear magnetic resonance (NMR) platform and D-Wave quantum annealing), and hybrid quantum-classical computing. Finally, the feasibility of integer factorization based on quantum adiabatics is discussed. In this paper, quantum annealing is regarded as a quantum attack method that is completely different from the famous Shor algorithm, and the potential of D-Wave factorization of large numbers to crack RSA cryptography is verified, which provides a new idea for a quantum attack on RSA public key cryptography.
Shor presented a quantum algorithm to factor large integers and compute discrete logarithms in polynomial time. As a result, public key cryptosystems, such as RSA, ElGamal and ECC, which are based on these computation...
详细信息
Shor presented a quantum algorithm to factor large integers and compute discrete logarithms in polynomial time. As a result, public key cryptosystems, such as RSA, ElGamal and ECC, which are based on these computational assumptions will become insecure with the advent of quantum computers. To construct a secure anti-quantum public-key cryptosystem, Wu et al. introduced the notion of data complexity under quantum environment. Based on the hardness of NP-complete problems and data complexity, they presented a new public key cryptosystem and a signature scheme. Using Shor's quantum algorithm, we break their public key cryptosystem and signature scheme by directly solving the private key from the public key. Therefore, their public key cryptosystem and signature scheme are insecure in a quantum computer.
Quantum computing devices are believed to be powerful in solving the prime factorization problem, which is at the heart of widely deployed public-key cryptographic tools. However, the implementation of Shor's quan...
详细信息
Quantum computing devices are believed to be powerful in solving the prime factorization problem, which is at the heart of widely deployed public-key cryptographic tools. However, the implementation of Shor's quantum factorization algorithm requires significant resources scaling linearly with the number size;taking into account an overhead that is required for quantum error correction the estimation is that 20 millions of (noisy) physical qubits are required for factoring 2048-bit RSA key in 8 hours. Recent proposal by Yan et al. claims a possibility of solving the factorization problem with sublinear quantum resources. As we demonstrate in our work, this proposal lacks systematic analysis of the computational complexity of the classical part of the algorithm, which exploits the Schnorr's lattice-based approach. We provide several examples illustrating the need in additional resource analysis for the proposed quantum factorization algorithm.
暂无评论