Английская Википедия:Differential equations of addition

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

In cryptography, differential equations of addition (DEA) are one of the most basic equations related to differential cryptanalysis that mix additions over two different groups (e.g. addition modulo 232 and addition over GF(2)) and where input and output differences are expressed as XORs.

Examples

Differential equations of addition (DEA) are of the following form:

<math>(x+y)\oplus((x\oplus a)+(y\oplus b))=c</math>

where <math>x</math> and <math>y</math> are <math>n</math>-bit unknown variables and <math>a</math>, <math>b</math> and <math>c</math> are known variables. The symbols <math>+</math> and <math>\oplus</math> denote addition modulo <math>2^n</math> and bitwise exclusive-or respectively. The above equation is denoted by <math>(a, b, c)</math>.

Let a set

<math>S=\{(a_i, b_i, c_i)|i < k\}</math>

for integer <math>i</math> denote a system of <math>k(n)</math> DEA where <math>k(n)</math> is a polynomial in <math>n</math>. It has been proved that the satisfiability of an arbitrary set of DEA is in the complexity class P when a brute force search requires an exponential time.

In 2013, some properties of a special form of DEA were reported by Chengqing Li et al., where <math>a=0</math> and <math>y</math> is assumed known. Essentially, the special DEA can be represented as <math>(x \dotplus \alpha) \oplus (x\dotplus \beta)=c</math>. Based on the found properties, an algorithm for deriving <math>x</math> was proposed and analyzed.[1]

Applications

Solution to an arbitrary set of DEA (either in batch and or in adaptive query model) was due to Souradyuti Paul and Bart Preneel. The solution techniques have been used to attack the stream cipher Helix.

Further reading

References

  1. ↑ Шаблон:Cite journal

Шаблон:Cryptography navbox

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Английская_Википедия:Differential_equations_of_addition&oldid=14307379