Security analysis of public-key cryptosystems is of fundamental significance for both theoretical research and applications in cryptography. In particular, the security of widely used public-key cryptosystems merits d...Security analysis of public-key cryptosystems is of fundamental significance for both theoretical research and applications in cryptography. In particular, the security of widely used public-key cryptosystems merits deep research to protect against new types of attacks. It is therefore highly meaningful to research cryptanalysis in the quantum computing environment. Shor proposed a wellknown factoring algorithm by finding the prime factors of a number n =pq, which is exponentially faster than the best known classical algorithm. The idea behind Shor's quantum factoring algorithm is a straightforward programming consequence of the following proposition: to factor n, it suffices to find the order r; once such an r is found, one can compute gcd( a^(r/2) ±1, n)=p or q. For odd values of r it is assumed that the factors of n cannot be found(since a^(r/2) is not generally an integer). That is, the order r must be even. This restriction can be removed, however, by working from another angle. Based on the quantum inverse Fourier transform and phase estimation, this paper presents a new polynomial-time quantum algorithm for breaking RSA, without explicitly factoring the modulus n. The probability of success of the new algorithm is greater than 4φ( r)/π~2 r, exceeding that of the existing quantum algorithm forattacking RSA based on factorization. In constrast to the existing quantum algorithm for attacking RSA, the order r of the fixed point C for RSA does not need to be even. It changed the practices that cryptanalysts try to recover the private-key, directly from recovering the plaintext M to start, a ciphertext-only attack attacking RSA is proposed.展开更多
Time efficiency of key establishment and update is one of the major problems contributory key managements strive to address.To achieve better time efficiency in key establishment,we propose a Location-based Huffman(L-...Time efficiency of key establishment and update is one of the major problems contributory key managements strive to address.To achieve better time efficiency in key establishment,we propose a Location-based Huffman(L-Huffman) scheme.First,users are separated into several small groups to minimize communication cost when they are distributed over large networks.Second,both user's computation difference and message transmission delay are taken into consideration when Huffman coding is employed to forming the optimal key tree.Third,the combined weights in Huffman tree are located in a higher place of the key tree to reduce the variance of the average key generation time and minimize the longest key generation time.Simulations demonstrate that L-Huffman has much better performance in wide area networks and is a little better in local area network than Huffman scheme.展开更多
基金partially supported by he State Key Program of National Natural Science of China No. 61332019Major State Basic Research Development Program of China (973 Program) No. 2014CB340601+1 种基金the National Science Foundation of China No. 61202386, 61402339the National Cryptography Development Fund No. MMJJ201701304
文摘Security analysis of public-key cryptosystems is of fundamental significance for both theoretical research and applications in cryptography. In particular, the security of widely used public-key cryptosystems merits deep research to protect against new types of attacks. It is therefore highly meaningful to research cryptanalysis in the quantum computing environment. Shor proposed a wellknown factoring algorithm by finding the prime factors of a number n =pq, which is exponentially faster than the best known classical algorithm. The idea behind Shor's quantum factoring algorithm is a straightforward programming consequence of the following proposition: to factor n, it suffices to find the order r; once such an r is found, one can compute gcd( a^(r/2) ±1, n)=p or q. For odd values of r it is assumed that the factors of n cannot be found(since a^(r/2) is not generally an integer). That is, the order r must be even. This restriction can be removed, however, by working from another angle. Based on the quantum inverse Fourier transform and phase estimation, this paper presents a new polynomial-time quantum algorithm for breaking RSA, without explicitly factoring the modulus n. The probability of success of the new algorithm is greater than 4φ( r)/π~2 r, exceeding that of the existing quantum algorithm forattacking RSA based on factorization. In constrast to the existing quantum algorithm for attacking RSA, the order r of the fixed point C for RSA does not need to be even. It changed the practices that cryptanalysts try to recover the private-key, directly from recovering the plaintext M to start, a ciphertext-only attack attacking RSA is proposed.
基金Supported by National Basic Research and Development Program of China (2007CB307102)
文摘Time efficiency of key establishment and update is one of the major problems contributory key managements strive to address.To achieve better time efficiency in key establishment,we propose a Location-based Huffman(L-Huffman) scheme.First,users are separated into several small groups to minimize communication cost when they are distributed over large networks.Second,both user's computation difference and message transmission delay are taken into consideration when Huffman coding is employed to forming the optimal key tree.Third,the combined weights in Huffman tree are located in a higher place of the key tree to reduce the variance of the average key generation time and minimize the longest key generation time.Simulations demonstrate that L-Huffman has much better performance in wide area networks and is a little better in local area network than Huffman scheme.
