Advances in quantum computers threaten to break public key cryptosystems such as RSA, ECC, and EIGamal on the hardness of factoring or taking a discrete logarithm, while no quantum algorithms are found to solve certai...Advances in quantum computers threaten to break public key cryptosystems such as RSA, ECC, and EIGamal on the hardness of factoring or taking a discrete logarithm, while no quantum algorithms are found to solve certain mathematical problems on non-commutative algebraic structures until now. In this background, Majid Khan et al.proposed two novel public-key encryption schemes based on large abelian subgroup of general linear group over a residue ring. In this paper we show that the two schemes are not secure. We present that they are vulnerable to a structural attack and that, it only requires polynomial time complexity to retrieve the message from associated public keys respectively. Then we conduct a detailed analysis on attack methods and show corresponding algorithmic description and efficiency analysis respectively. After that, we propose an improvement assisted to enhance Majid Khan's scheme. In addition, we discuss possible lines of future work.展开更多
A new attack on block ciphers is introduced, which is termed linear-differential cryptanalysis. It bases the combining of linear cryptanalysis and differential cryptanalysis, and works by using linear-differential pro...A new attack on block ciphers is introduced, which is termed linear-differential cryptanalysis. It bases the combining of linear cryptanalysis and differential cryptanalysis, and works by using linear-differential probability （LDP）. Moreover, we present a new method for upper bounding the maximum linear-differential probability （MLDP） for 2 rounds of substitution permutation network （SPN） cipher structure. When our result applies to 2-round advanced encryption standard（AES）, It is shown that the upper bound of MLDP is up to 1.68×2^-19, which extends the known results for the 2-round SPN. Furthermore, when using a recursive technique, we obtain that the MLDP for 4 rounds of AES is bounded by 2^-73.展开更多
4-bit linear relations play an important role in cryptanalysis of 4-bit crypto S-boxes. 4-bit finite differences have also been a major part of cryptanalysis of 4-bit S-boxes. Existence of all 4-bit linear relations h...4-bit linear relations play an important role in cryptanalysis of 4-bit crypto S-boxes. 4-bit finite differences have also been a major part of cryptanalysis of 4-bit S-boxes. Existence of all 4-bit linear relations have been counted for all of 16 input and 16 output 4-bit bit patterns of 4-bit Crypto S-boxes said as S-boxes has been reported in Linear Cryptanalysis of 4-bit S-boxes. Count of existing finite differences from each element of output S-boxes to distant output S-boxes have been noted in Differential Cryptanalysis of S-boxes. In this paper a brief review of these two cryptanalytic methods for 4-bit S-boxes has been introduced in a very lucid and conceptual manner. Two new analysis techniques, one to search for the existing linear approximations among the input vectors (IPVs) and output Boolean functions (BFs) of a particular S-box has also been introduced in this paper. The search is limited to find the existing linear relations or approximations in the contrary to count the number of existent linear relations among all 16, 4-bit input and output bit patterns within all possible linear approximations. Another is to find number of balanced BFs in difference output S-boxes. Better the number of Balanced BFs, Better the security.展开更多
This paper observes approaches to algebraic analysis of GOST 28147-89 encryption algorithm (also known as simply GOST), which is the basis of most secure information systems in Russia. The general idea of algebraic an...This paper observes approaches to algebraic analysis of GOST 28147-89 encryption algorithm (also known as simply GOST), which is the basis of most secure information systems in Russia. The general idea of algebraic analysis is based on the representation of initial encryption algorithm as a system of multivariate quadratic equations, which define relations between a secret key and a cipher text. Extended linearization method is evaluated as a method for solving the nonlinear sys- tem of equations.展开更多
This letter proposes algebraic attacks on two kinds of nonlinear filter generators with symmetric Boolean functions as the filter fimctions. Different fxom the classical algebraic attacks, the proposed attacks take th...This letter proposes algebraic attacks on two kinds of nonlinear filter generators with symmetric Boolean functions as the filter fimctions. Different fxom the classical algebraic attacks, the proposed attacks take the advantage of the combinational property of a linear feedback shift register （LFSR） and the symmetric Boolean function to obtain a tow-degree algebraic relation, and hence the complexities of the proposed attacks are independent of the algebraic immunity （AI） of the filter functions. It is shown that improper combining of the LFSR with the filter function can make the filter generator suffer from algebraic attacks. As a result, the bits of the LFSR must be selected properly to input the filter function with large AI in order to withstand the proposed algebraic attacks.展开更多
In June 2013, the U.S. National Security Agency proposed two families of lightweight block ciphers, called SIMON and SPECK respectively. These ciphers are designed to perform excellently on both hardware and software ...In June 2013, the U.S. National Security Agency proposed two families of lightweight block ciphers, called SIMON and SPECK respectively. These ciphers are designed to perform excellently on both hardware and software platforms. In this paper, we mainly present zero-correlation linear cryptanalysis on various versions of SIMON. Firstly, by using miss- in-the-middle approach, we construct zero-correlation linear distinguishers of SIMON, and zero-correlation linear attacks are presented based oi1 careful analysis of key recovery phase. Secondly, multidimensional zero-correlation linear attacks are used to reduce the data complexity. Our zero-correlation linear attacks perform better than impossible differential attacks proposed by Abed et al. in ePrint Report 2013/568. Finally, we also use the divide-and-conquer technique to improve the results of linear cryptanalysis proposed by Javad et al. in ePrint Report 2013/663.展开更多
Data Encryption Standard(DES)is a symmetric key cryptosystem that is applied in different cryptosystems of recent times.However,researchers found defects in the main assembling of the DES and declared it insecure agai...Data Encryption Standard(DES)is a symmetric key cryptosystem that is applied in different cryptosystems of recent times.However,researchers found defects in the main assembling of the DES and declared it insecure against linear and differential cryptanalysis.In this paper,we have studied the faults and made improvements in their internal structure and get the new algorithm for Improved DES.The improvement is being made in the substitution step,which is the only nonlinear component of the algorithm.This alteration provided us with great outcomes and increase the strength of DES.Accordingly,a novel 6×6 good quality S-box construction scheme has been hired in the substitution phase of the DES.The construction involves the Galois field method and generates robust S-boxes that are used to secure the scheme against linear and differential attacks.Then again,the key space of the improved DES has been enhanced against the brute force attack.The out-comes of different performance analyses depict the strength of our proposed substitution boxes which also guarantees the strength of the overall DES.展开更多
NUSH is a block cipher as a candidate for NESSIE. NUSH is analyzed by linear crypt-analysis . The complexity δ = (ε , η) of the attack consists of data complexity ε and time complexity η. Three linear approximati...NUSH is a block cipher as a candidate for NESSIE. NUSH is analyzed by linear crypt-analysis . The complexity δ = (ε , η) of the attack consists of data complexity ε and time complexity η. Three linear approximations are used to analyze NUSH with 64-bit block. When |K| = 128 bits, the complexities of three attacks are (258, 2124), (260, 278) and (262, 255) respectively. When |K| = 192 bits, the complexities of three attacks are (258, 2157) (260, 2%) and (262, 258) respectively. When |K| = 256 bits, the complexities of three attacks are (258, 2125), (260, 278) and (262, 253) respectively. Three linear approximations are used to analyze NUSH with 128-bit block. When |K|= 128 bits, the complexities of three attacks are (2122, 295), (2124, 257) and (2126, 252) respectively. When |K| = 192 bits, the complexities of three attacks are (2122, 2142), (2124, 275) and (2126, 258) respectively. When |K|= 256 bits, the complexities of three attacks are (2122, 2168), (2124, 281) and (2126, 264) respectively. Two linear approximations are used to analyze NUSH with 256-bit block. When |K|= 128 bits, the complexities of two attacks are (2252, 2122) and (2254, 2119) respectively. When |K|= 192 bits, the complexities of two attacks are (2252, 2181) and (2254, 2177) respectively. When |K|=256 bits, the complexities of two attacks are (2252, 2240) and (2254, 2219) respectively. These results show that NUSH is not immune to linear cryptanalysis, and longer key cannot enhance the security of NUSH.展开更多
Finding the solution to a general multivariate modular linear equation plays an important role in cryptanalysis field. Earlier results show that obtaining a relatively short solution is possible in polynomial time. Ho...Finding the solution to a general multivariate modular linear equation plays an important role in cryptanalysis field. Earlier results show that obtaining a relatively short solution is possible in polynomial time. However, one problem arises here that if the equation has a short solution in given bounded range, the results outputted by earlier algorithms are often not the ones we are interested in. In this paper, we present a probability method based on lattice basis reduction to solve the problem. For a general multivariate modular linear equation with short solution in the given bounded range, the new method outputs this short solution in polynomial time, with a high probability. When the number of unknowns is not too large （smaller than 68）, the probability is approximating 1. Experimental results show that Knapsack systems and Lu-Lee type systems are easily broken in polynomial time with this new method.展开更多
基金supported in part by the National Natural Science Foundation of China(Grant Nos.61303212,61170080,61202386)the State Key Program of National Natural Science of China(Grant Nos.61332019,U1135004)+2 种基金the Major Research Plan of the National Natural Science Foundation of China(Grant No.91018008)Major State Basic Research Development Program of China(973 Program)(No.2014CB340600)the Hubei Natural Science Foundation of China(Grant Nos.2011CDB453,2014CFB440)
文摘Advances in quantum computers threaten to break public key cryptosystems such as RSA, ECC, and EIGamal on the hardness of factoring or taking a discrete logarithm, while no quantum algorithms are found to solve certain mathematical problems on non-commutative algebraic structures until now. In this background, Majid Khan et al.proposed two novel public-key encryption schemes based on large abelian subgroup of general linear group over a residue ring. In this paper we show that the two schemes are not secure. We present that they are vulnerable to a structural attack and that, it only requires polynomial time complexity to retrieve the message from associated public keys respectively. Then we conduct a detailed analysis on attack methods and show corresponding algorithmic description and efficiency analysis respectively. After that, we propose an improvement assisted to enhance Majid Khan's scheme. In addition, we discuss possible lines of future work.
基金Supported by the National Natural Science Foun-dation of China(60503010) and the Foundation of National Laboratory for Modern communications(51436030105DZ0105)
文摘A new attack on block ciphers is introduced, which is termed linear-differential cryptanalysis. It bases the combining of linear cryptanalysis and differential cryptanalysis, and works by using linear-differential probability （LDP）. Moreover, we present a new method for upper bounding the maximum linear-differential probability （MLDP） for 2 rounds of substitution permutation network （SPN） cipher structure. When our result applies to 2-round advanced encryption standard（AES）, It is shown that the upper bound of MLDP is up to 1.68×2^-19, which extends the known results for the 2-round SPN. Furthermore, when using a recursive technique, we obtain that the MLDP for 4 rounds of AES is bounded by 2^-73.
文摘4-bit linear relations play an important role in cryptanalysis of 4-bit crypto S-boxes. 4-bit finite differences have also been a major part of cryptanalysis of 4-bit S-boxes. Existence of all 4-bit linear relations have been counted for all of 16 input and 16 output 4-bit bit patterns of 4-bit Crypto S-boxes said as S-boxes has been reported in Linear Cryptanalysis of 4-bit S-boxes. Count of existing finite differences from each element of output S-boxes to distant output S-boxes have been noted in Differential Cryptanalysis of S-boxes. In this paper a brief review of these two cryptanalytic methods for 4-bit S-boxes has been introduced in a very lucid and conceptual manner. Two new analysis techniques, one to search for the existing linear approximations among the input vectors (IPVs) and output Boolean functions (BFs) of a particular S-box has also been introduced in this paper. The search is limited to find the existing linear relations or approximations in the contrary to count the number of existent linear relations among all 16, 4-bit input and output bit patterns within all possible linear approximations. Another is to find number of balanced BFs in difference output S-boxes. Better the number of Balanced BFs, Better the security.
文摘This paper observes approaches to algebraic analysis of GOST 28147-89 encryption algorithm (also known as simply GOST), which is the basis of most secure information systems in Russia. The general idea of algebraic analysis is based on the representation of initial encryption algorithm as a system of multivariate quadratic equations, which define relations between a secret key and a cipher text. Extended linearization method is evaluated as a method for solving the nonlinear sys- tem of equations.
基金Supported by the National Basic Research Program of China （No. 2007CB311201）, the National Natural Science Foundation of China （No.60833008 No.60803149）, and the Foundation of Guangxi Key Laboratory of Information and Communication （No.20902）.
文摘This letter proposes algebraic attacks on two kinds of nonlinear filter generators with symmetric Boolean functions as the filter fimctions. Different fxom the classical algebraic attacks, the proposed attacks take the advantage of the combinational property of a linear feedback shift register （LFSR） and the symmetric Boolean function to obtain a tow-degree algebraic relation, and hence the complexities of the proposed attacks are independent of the algebraic immunity （AI） of the filter functions. It is shown that improper combining of the LFSR with the filter function can make the filter generator suffer from algebraic attacks. As a result, the bits of the LFSR must be selected properly to input the filter function with large AI in order to withstand the proposed algebraic attacks.
基金This work was supported by the National Basic Research 973 Program of China under Grant No. 2013CB338002 and the National Natural Science Foundation of China under Grant Nos. 61272476, 61202420, and 61232009.
文摘In June 2013, the U.S. National Security Agency proposed two families of lightweight block ciphers, called SIMON and SPECK respectively. These ciphers are designed to perform excellently on both hardware and software platforms. In this paper, we mainly present zero-correlation linear cryptanalysis on various versions of SIMON. Firstly, by using miss- in-the-middle approach, we construct zero-correlation linear distinguishers of SIMON, and zero-correlation linear attacks are presented based oi1 careful analysis of key recovery phase. Secondly, multidimensional zero-correlation linear attacks are used to reduce the data complexity. Our zero-correlation linear attacks perform better than impossible differential attacks proposed by Abed et al. in ePrint Report 2013/568. Finally, we also use the divide-and-conquer technique to improve the results of linear cryptanalysis proposed by Javad et al. in ePrint Report 2013/663.
文摘Data Encryption Standard(DES)is a symmetric key cryptosystem that is applied in different cryptosystems of recent times.However,researchers found defects in the main assembling of the DES and declared it insecure against linear and differential cryptanalysis.In this paper,we have studied the faults and made improvements in their internal structure and get the new algorithm for Improved DES.The improvement is being made in the substitution step,which is the only nonlinear component of the algorithm.This alteration provided us with great outcomes and increase the strength of DES.Accordingly,a novel 6×6 good quality S-box construction scheme has been hired in the substitution phase of the DES.The construction involves the Galois field method and generates robust S-boxes that are used to secure the scheme against linear and differential attacks.Then again,the key space of the improved DES has been enhanced against the brute force attack.The out-comes of different performance analyses depict the strength of our proposed substitution boxes which also guarantees the strength of the overall DES.
基金This work was supported by 973 Project (Grant No. G1999035802) and the National Natural Science Foundation of China (Grant No. 19931010) .
文摘NUSH is a block cipher as a candidate for NESSIE. NUSH is analyzed by linear crypt-analysis . The complexity δ = (ε , η) of the attack consists of data complexity ε and time complexity η. Three linear approximations are used to analyze NUSH with 64-bit block. When |K| = 128 bits, the complexities of three attacks are (258, 2124), (260, 278) and (262, 255) respectively. When |K| = 192 bits, the complexities of three attacks are (258, 2157) (260, 2%) and (262, 258) respectively. When |K| = 256 bits, the complexities of three attacks are (258, 2125), (260, 278) and (262, 253) respectively. Three linear approximations are used to analyze NUSH with 128-bit block. When |K|= 128 bits, the complexities of three attacks are (2122, 295), (2124, 257) and (2126, 252) respectively. When |K| = 192 bits, the complexities of three attacks are (2122, 2142), (2124, 275) and (2126, 258) respectively. When |K|= 256 bits, the complexities of three attacks are (2122, 2168), (2124, 281) and (2126, 264) respectively. Two linear approximations are used to analyze NUSH with 256-bit block. When |K|= 128 bits, the complexities of two attacks are (2252, 2122) and (2254, 2119) respectively. When |K|= 192 bits, the complexities of two attacks are (2252, 2181) and (2254, 2177) respectively. When |K|=256 bits, the complexities of two attacks are (2252, 2240) and (2254, 2219) respectively. These results show that NUSH is not immune to linear cryptanalysis, and longer key cannot enhance the security of NUSH.
基金Supported by the National Natural Science Foundation of China (Grant Nos. 60873249, 60973142)the National High-Tech Research & Development Program of China (Grant Nos. 2008AA10Z419, 2009AA011906)the Project Funded by Basic Research Foundation of School of Information Science and Technology of Tsinghua University
文摘Finding the solution to a general multivariate modular linear equation plays an important role in cryptanalysis field. Earlier results show that obtaining a relatively short solution is possible in polynomial time. However, one problem arises here that if the equation has a short solution in given bounded range, the results outputted by earlier algorithms are often not the ones we are interested in. In this paper, we present a probability method based on lattice basis reduction to solve the problem. For a general multivariate modular linear equation with short solution in the given bounded range, the new method outputs this short solution in polynomial time, with a high probability. When the number of unknowns is not too large （smaller than 68）, the probability is approximating 1. Experimental results show that Knapsack systems and Lu-Lee type systems are easily broken in polynomial time with this new method.
