Cryptanalysis of block ciphers with overdefined systems of equations

Several recently proposed ciphers, for example Rijndael and Serpent, are built with layers of small S-boxes interconnected by linear key-dependent layers. Their security relies on the fact, that the classical methods of cryptanalysis (e.g. linear or differential attacks) are based on probabilistic characteristics, which makes their security grow exponentially with the number of rounds N r r. In this paper we study the security of such ciphers under an additional hypothesis: the S-box can be described by an overdefined system of algebraic equations (true with probability 1). We show that this is true for both Serpent (due to a small size of S-boxes) and Rijndael (due to unexpected algebraic properties). We study general methods known for solving overdefined systems of equations, such as XL from Eurocrypt’00, and show their inefficiency. Then we introduce a new method called XSL that uses the sparsity of the equations and their specific structure. The XSL attack uses only relations true with probability 1, and thus the security does not have to grow exponentially in the number of rounds. XSL has a parameter P, and from our estimations is seems that P should be a constant or grow very slowly with the number of rounds. The XSL attack would then be polynomial (or subexponential) in N r> , with a huge constant that is double-exponential in the size of the S-box. The exact complexity of such attacks is not known due to the redundant equations. Though the presented version of the XSL attack always gives always more than the exhaustive search for Rijndael, it seems to (marginally) break 256-bit Serpent. We suggest a new criterion for design of S-boxes in block ciphers: they should not be describable by a system of polynomial equations that is too small or too overdefined.

On the direct parallel solution of systems of linear equations: New algorithms and systolic structures

The paper presents two new algorithms for the direct parallel solution of systems of linear equations. The algorithms employ a novel recursive doubling technique to obtain solutions to an nth-order system in n steps with no more than 2n(n −1) processors. Comparing their performance with the Gaussian elimination algorithm (GE), we show that they are almost 100% faster than the latter. This speedup is achieved by dispensing with all the computation involved in the back-substitution phase of GE. It is also shown that the new algorithms exhibit error characteristics which are superior to GE. An n(n + 1) systolic array structure is proposed for the implementation of the new algorithms. We show that complete solutions can be obtained, through these single-phase solution methods, in 5n−log2n−4 computational steps, without the need for intermediate I/O operations.

Iterative solution of a class of linear equations with application to reconstruction of three-dimensional object arrays

An iterative algorithm baaed on probabilistic estimation is described for obtaining the minimum-norm solution of a very large, consistent, linear system of equations AX = g where A is an (m times n) matrix with non-negative elements, x and g are respectively (n times 1) and (m times 1) vectors with positive components.

A bicharacteristic formulation of the ideal MHD equations

On a characteristic surface Omega of a hyperbolic system of first-order equations in multi-dimensions (x, t), there exits a compatibility condition which is in the form of a transport equation along a bicharacteristic on Omega. This result can be interpreted also as a transport equation along rays of the wavefront Omega(t) in x-space associated with Omega. For a system of quasi-linear equations, the ray equations (which has two distinct parts) and the transport equation form a coupled system of underdetermined equations. As an example of this bicharacteristic formulation, we consider two-dimensional unsteady flow of an ideal magnetohydrodynamics gas with a plane aligned magnetic field. For any mode of propagation in this two-dimensional flow, there are three ray equations: two for the spatial coordinates x and y and one for the ray diffraction. In spite of little longer calculations, the final four equations (three ray equations and one transport equation) for the fast magneto-acoustic wave are simple and elegant and cannot be derived in these simple forms by use of a computer program like REDUCE.

Solutions of cubic equations in quadratic fields

Let K be any quadratic field with O-K its ring of integers. We study the solutions of cubic equations, which represent elliptic curves defined over Q, in quadratic fields and prove some interesting results regarding the solutions by using elementary tools. As an application we consider the Diophantine equation r + s + t = rst = 1 in O-K. This Diophantine equation gives an elliptic curve defined over Q with finite Mordell-Weil group. Using our study of the solutions of cubic equations in quadratic fields we present a simple proof of the fact that except for the ring of integers of Q(i) and Q(root 2), this Diophantine equation is not solvable in the ring of integers of any other quadratic fields, which is already proved in [4].

Solutions of a system of forced Burgers equation

In this article, we obtain explicit solutions of a system of forced Burgers equation subject to some classes of bounded and compactly supported initial data and also subject to certain unbounded initial data. In a series of papers, Rao and Yadav (2010) 1-3] obtained explicit solutions of a nonhomogeneous Burgers equation in one dimension subject to certain classes of bounded and unbounded initial data. Earlier Kloosterziel (1990) 4] represented the solution of an initial value problem for the heat equation, with initial data in L-2 (R-n, e(vertical bar x vertical bar 2/2)), as a series of self-similar solutions of the heat equation in R-n. Here we express the solutions of certain classes of Cauchy problems for a system of forced Burgers equation in terms of self-similar solutions of some linear partial differential equations. (C) 2013 Elsevier Inc. All rights reserved.

Mechanics of a grip system of three-key-board hydraulic tongs developed for offshore oil pipe lines

This paper carries out the analysis of mechanics of a grip system of three-key-board hydraulic tongs developed for offshore oil pipe lines which has been successfully used in oil fields in China. The main improvement of this system is that a lever frame structure is used in the structural design, which reduces greatly the stresses of the major components of the oil pipe tongs. Theoretical analysis and numerical calculation based on thirteen basic equations developed Show that the teeth board of the tongs is not easy to slip as frequently happens to other systems and is of higher reliability.

Effects of Baffle Design on Fluid Flow and Heat Transfer in Ammonothermal Growth System of Nitrides

Efforts have been made in growing bulk single crystals of GaN front supercritical fluids using the ammonothermal method, which utilizes ammonia as fluid rather than water as in the hydrothermal process. Different mineralizers such as amide or azide and temperatures in the range of 200-600degreesC have been used to increase the solubility. The pressure is from 1 to 4 kbar. Modeling of the ammonothermal growth process has been used to identify factors which may affect the temperature distribution, fluid flow and nutrient transport. The GaN charge is considered as a porous media bed and the flow in the charge is simulated using the Darcy-Brinkman-Forchheimer model. The resulting governing equations are solved using the finite volume method. The effects of baffle design and opening on flow pattern and temperature distribution in an autoclave are analyzed. Two cases are considered with baffle openings of 15% and 20% in cross-sectional area, respectively.

New variational principles for systems of partial differential equations

The question of finding variational principles for coupled systems of first order partial differential equations is considered. Using a potential representation for solutions of the first order system a higher order system is obtained. Existence of a variational principle follows if the original system can be transformed to a self-adjoint higher order system. Existence of variational principles for all linear wave equations with constant coefficients having real dispersion relations is established. The method of adjoining some of the equations of the original system to a suitable Lagrangian function by the method of Lagrange multipliers is used to construct new variational principles for a class of linear systems. The equations used as side conditions must satisfy highly-restrictive integrability conditions. In the more difficult nonlinear case the system of two equations in two independent variables can be analyzed completely. For systems determined by two conservation laws the side condition must be a conservation law in addition to satisfying the integrability conditions.

Numerical solution of parabolic equations by the box scheme

The box scheme proposed by H. B. Keller is a numerical method for solving parabolic partial differential equations. We give a convergence proof of this scheme for the heat equation, for a linear parabolic system, and for a class of nonlinear parabolic equations. Von Neumann stability is shown to hold for the box scheme combined with the method of fractional steps to solve the two-dimensional heat equation. Computations were performed on Burgers' equation with three different initial conditions, and Richardson extrapolation is shown to be effective.

Choice of calibration equations in calibrating microwave test fixtures

The error theory of linear equation system has been applied to the calibration procedure of microwave network analyser in this article. A new explanation for the choice of the linear calibration equations is proposed and a general principle for choosing calibration equations is presented. The method can also be used to predict the occurrence of the problem of frequency limitation at some periodic frequencies. This principle is employed to the thru-short-delay (TSD) method and the solution using the chosen equations gives the most accurate results. A good agreement between the theory and the experiment has been obtained.

Sequentially continuous non-linear fundamental systems of solutions of affine equations in locally convex spaces

According to the Mickael's selection theorem any surjective continuous linear operator from one Fr\'echet space onto another has a continuous (not necessarily linear) right inverse. Using this theorem Herzog and Lemmert proved that if $E$ is a Fr\'echet space and $T:E\to E$ is a continuous linear operator such that the Cauchy problem $\dot x=Tx$, $x(0)=x_0$ is solvable in $[0,1]$ for any $x_0\in E$, then for any $f\in C([0,1],E)$, there exists a continuos map $S:[0,1]\times E\to E$, $(t,x)\mapsto S_tx$ such that for any $x_0\in E$, the function $x(t)=S_tx_0$ is a solution of the Cauchy problem $\dot x(t)=Tx(t)+f(t)$, $x(0)=x_0$ (they call $S$ a fundamental system of solutions of the equation $\dot x=Tx+f$). We prove the same theorem, replacing "continuous" by "sequentially continuous" for locally convex spaces from a class which contains strict inductive limits of Fr\'echet spaces and strong duals of Fr\'echet--Schwarz spaces and is closed with respect to finite products and sequentially closed subspaces. The key-point of the proof is an extension of the theorem on existence of a sequentially continuous right inverse of any surjective sequentially continuous linear operator to some class of non-metrizable locally convex spaces.

Multiple Roots of Systems of Equations by Repulsion Merit Functions

In this paper we address the problem of computing multiple roots of a system of nonlinear equations through the global optimization of an appropriate merit function. The search procedure for a global minimizer of the merit function is carried out by a metaheuristic, known as harmony search, which does not require any derivative information. The multiple roots of the system are sequentially determined along several iterations of a single run, where the merit function is accordingly modified by penalty terms that aim to create repulsion areas around previously computed minimizers. A repulsion algorithm based on a multiplicative kind penalty function is proposed. Preliminary numerical experiments with a benchmark set of problems show the effectiveness of the proposed method.

On Vessiot's Theory of Partial Differential Equations

The object of research presented here is Vessiot's theory of partial differential equations: for a given differential equation one constructs a distribution both tangential to the differential equation and contained within the contact distribution of the jet bundle. Then within it, one seeks n-dimensional subdistributions which are transversal to the base manifold, the integral distributions. These consist of integral elements, and these again shall be adapted so that they make a subdistribution which closes under the Lie-bracket. This then is called a flat Vessiot connection. Solutions to the differential equation may be regarded as integral manifolds of these distributions. In the first part of the thesis, I give a survey of the present state of the formal theory of partial differential equations: one regards differential equations as fibred submanifolds in a suitable jet bundle and considers formal integrability and the stronger notion of involutivity of differential equations for analyzing their solvability. An arbitrary system may (locally) be represented in reduced Cartan normal form. This leads to a natural description of its geometric symbol. The Vessiot distribution now can be split into the direct sum of the symbol and a horizontal complement (which is not unique). The n-dimensional subdistributions which close under the Lie bracket and are transversal to the base manifold are the sought tangential approximations for the solutions of the differential equation. It is now possible to show their existence by analyzing the structure equations. Vessiot's theory is now based on a rigorous foundation. Furthermore, the relation between Vessiot's approach and the crucial notions of the formal theory (like formal integrability and involutivity of differential equations) is clarified. The possible obstructions to involution of a differential equation are deduced explicitly. In the second part of the thesis it is shown that Vessiot's approach for the construction of the wanted distributions step by step succeeds if, and only if, the given system is involutive. Firstly, an existence theorem for integral distributions is proven. Then an existence theorem for flat Vessiot connections is shown. The differential-geometric structure of the basic systems is analyzed and simplified, as compared to those of other approaches, in particular the structure equations which are considered for the proofs of the existence theorems: here, they are a set of linear equations and an involutive system of differential equations. The definition of integral elements given here links Vessiot theory and the dual Cartan-Kähler theory of exterior systems. The analysis of the structure equations not only yields theoretical insight but also produces an algorithm which can be used to derive the coefficients of the vector fields, which span the integral distributions, explicitly. Therefore implementing the algorithm in the computer algebra system MuPAD now is possible.

A comparative study of some computer algebra packages which determine the lie point symmetries of differential equations

The study seeks to determine which of five computer algebra packages is best at finding the Lie point symmetries of systems of partial differential equations with minimal user intervention. The chosen packages are LIEPDE and DIMSYM for REDUCE, LIE and BIGLIE for MUMATH, DESOLV for MAPLE, and MATHLIE for MATHEMATICA. A series of systems of partial differential equations are used in the study. The paper concludes that while all of the computer packages are useful, DESOLV appears to be the most successful system at determining the complete set of Lie point symmetries of systems of partial differential equations.