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.

## Contents

* 1 Examples
* 2 Applications
* 3 Further reading
* 4 References

## Examples

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

(x+y)⊕((x⊕a)+(y⊕b))=c

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

Let a set

S={(ai,bi,ci)|i<k}

for integer i denote a system of k(n) DEA where k(n) is a polynomial in n. 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 a=0 and y is assumed known. Essentially, the special DEA can be represented as (x∔α)⊕(x∔β)=c. Based on the found properties, an algorithm for deriving x 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

* Souradyuti Paul and Bart Preneel, Solving Systems of Differential Equations of Addition, ACISP 2005. Full version (PDF)
* Souradyuti Paul and Bart Preneel, Near Optimal Algorithms for Solving Differential Equations of Addition With Batch Queries, Indocrypt 2005. Full version (PDF)
* Helger Lipmaa, Johan Wallén, Philippe Dumas: On the Additive Differential Probability of Exclusive-Or. FSE 2004: 317-331.

## References

1. ↑ Li, Chengqing; Liu, Yuansheng; Zhang, Leo Yu; Chen, Michael Z. Q. (2013-04-01). "Breaking a chaotic image encryption algorithm based on modulo addition and xor operation". International Journal of Bifurcation and Chaos 23 (4): 1350075. doi:10.1142/S0218127413500752. ISSN 0218-1274. Bibcode: 2013IJBC...2350075L.

* v
* t
* e

Block ciphers (security summary)

Common
algorithms|

* AES
* Blowfish
* DES (internal mechanics, Triple DES)
* Serpent
* Twofish

Less common
algorithms|

* Camellia
* CAST-128
* GOST
* IDEA
* RC2
* RC5
* RC6
* SEED
* ARIA
* Skipjack
* TEA
* XTEA

Other
algorithms|

* 3-Way
* Akelarre
* Anubis
* BaseKing
* BassOmatic
* BATON
* BEAR and LION
* CAST-256
* Chiasmus
* CIKS-1
* CIPHERUNICORN-A
* CIPHERUNICORN-E
* CLEFIA
* CMEA
* Cobra
* COCONUT98
* Crab
* Cryptomeria/C2
* CRYPTON
* CS-Cipher
* DEAL
* DES-X
* DFC
* E2
* FEAL
* FEA-M
* FROG
* G-DES
* Grand Cru
* Hasty Pudding cipher
* Hierocrypt
* ICE
* IDEA NXT
* Intel Cascade Cipher
* Iraqi
* Kalyna
* KASUMI
* KeeLoq
* KHAZAD
* Khufu and Khafre
* KN-Cipher
* Kuznyechik
* Ladder-DES
* Libelle
* LOKI (97, 89/91)
* Lucifer
* M6
* M8
* MacGuffin
* Madryga
* MAGENTA
* MARS
* Mercy
* MESH
* MISTY1
* MMB
* MULTI2
* MultiSwap
* New Data Seal
* NewDES
* Nimbus
* NOEKEON
* NUSH
* PRESENT
* Prince
* Q
* RC6
* REDOC
* Red Pike
* S-1
* SAFER
* SAVILLE
* SC2000
* SHACAL
* SHARK
* Simon
* SM4
* Speck
* Spectr-H64
* Square
* SXAL/MBAL
* Threefish
* Treyfer
* UES
* xmx
* XXTEA
* Zodiac

Design|

* Feistel network
* Key schedule
* Lai–Massey scheme
* Product cipher
* S-box
* P-box
* SPN
* Confusion and diffusion
* Avalanche effect
* Block size
* Key size
* Key whitening (Whitening transformation)

Attack
(cryptanalysis)|

* Brute-force (EFF DES cracker)
* MITM
* Biclique attack
* 3-subset MITM attack
* Linear (Piling-up lemma)
* Differential
* Impossible
* Truncated
* Higher-order
* Differential-linear
* Distinguishing (Known-key)
* Integral/Square
* Boomerang
* Mod n
* Related-key
* Slide
* Rotational
* Side-channel
* Timing
* Power-monitoring
* Electromagnetic
* Acoustic
* Differential-fault
* XSL
* Interpolation
* Partitioning
* Rubber-hose
* Black-bag
* Davies
* Rebound
* Weak key
* Tau
* Chi-square
* Time/memory/data tradeoff

Standardization|

* AES process
* CRYPTREC
* NESSIE

Utilization|

* Initialization vector
* Mode of operation
* Padding

* v
* t
* e

Cryptography

* History of cryptography
* Cryptanalysis
* Outline of cryptography

* Symmetric-key algorithm
* Block cipher
* Stream cipher
* Public-key cryptography
* Cryptographic hash function
* Message authentication code
* Random numbers
* Steganography

* Category

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Differential equations of addition. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Differential_equations_of_addition&oldid=175591"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template