MDS matrix

MDS matrix

An MDS matrix (Maximum Distance Separable) is a matrix representing a function with certain diffusion properties that have useful applications in cryptography. Technically, an m×n matrix A over a finite field K is an MDS matrix if it is the transformation matrix of a linear transformation f(x)=Ax from Kn to Km such that no two different (m+n)-tuples of the form (x,f(x)) coincide in n or more components.Equivalently, the set of all (m+n)-tuples (x,f(x)) is an MDS code, i.e. a linear code that reaches the Singleton bound.

Let ilde A = left(egin{array}{c}{ m Id}_n\ hline{ m A}end{array} ight) be the matrix obtained by joining the identity matrix Idn to A.Then a necessary and sufficient condition for a matrix A to be MDS is that every possible n×n submatrix obtained by removing m rows from ilde Ais non-singular.

Reed-Solomon codes have the MDS property and are frequently used to obtain the MDS matrices used in cryptographic algorithms.

Serge Vaudenay suggested using MDS matrices in cryptographic primitives to produce what he called "multipermutations", not-necessarily linear functions with this same property. These functions have what he called "perfect diffusion": changing t of the inputs changes at least m-t+1 of the outputs. He showed how to exploit imperfect diffusion to cryptanalyze functions that are not multipermutations.

MDS matrices are used for diffusion in such block ciphers as AES, SHARK, Square, Twofish, Manta, Hierocrypt, and Camellia, and in the stream cipher MUGI and the cryptographic hash function WHIRLPOOL.

References

* cite conference
author = Serge Vaudenay
title = On the Need for Multipermutations: Cryptanalysis of MD4 and SAFER
booktitle = 2nd International Workshop on Fast Software Encryption (FSE '94)
pages = pp.286–297
publisher = Springer-Verlag
date = November 16 1994
location = Leuven
url = http://citeseer.ist.psu.edu/vaudenay94need.html
format = PDF/PostScript
accessdate = 2007-03-05

* cite conference
author = Vincent Rijmen, Joan Daemen, Bart Preneel, Anton Bosselaers, Erik De Win
title = The Cipher SHARK
booktitle = 3rd International Workshop on Fast Software Encryption (FSE '96)
pages = pp.99–111
publisher = Springer-Verlag
date = February 1996
location = Cambridge
url = http://citeseer.ist.psu.edu/rijmen96cipher.html
format = PDF/PostScript
accessdate = 2007-03-06

* cite paper
author = Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, Niels Ferguson
title = The Twofish Encryption Algorithm
date = June 15 1998
url = http://www.schneier.com/paper-twofish-paper.html
format = PDF/PostScript
accessdate = 2007-03-04


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Whirlpool (криптография) — У этого термина существуют и другие значения, см. Whirlpool (значения). Криптографическая хеш функция …   Википедия

  • Blom's scheme — is a cryptographical symmetric threshold key exchange protocol.A trusted party gives each of the n participants a secret key and a public identifier, which enables any two participants to independently create a shared key for securely… …   Wikipedia

  • Рэймен, Винсент — Винсент Рэймен Vincent Rijmen …   Википедия

  • JH — Криптографическая хеш функция Название JH Разработчик У Хунцзюнь (англ Wu Hongjun) Опубликован 16 января 2011 года Размер хеша 224, 256, 384, 512 Число раундов 42 JH семейство из четырех криптографических хеш функций: JH 224, JH 256, JH 384 и JH …   Википедия

  • Rijndael MixColumns — Der MixColumns Schritt stellt gemeinsam mit dem ShiftRows Schritt den primären Verschleierungsakt im Rijndael Algorithmus (AES) dar. Dieser Artikel soll verdeutlichen, wie dieser Schritt funktioniert Im MixColumns Schritt, wird jede Spalte des… …   Deutsch Wikipedia

  • Advanced Encryption Standard — Infobox block cipher name = AES caption = The SubBytes step, one of four stages in a round of AES designers = Vincent Rijmen, Joan Daemen publish date = 1998 derived from = Square derived to = Anubis, Grand Cru related to = certification = AES… …   Wikipedia

  • Camellia (cipher) — Infobox block cipher name = Camellia caption = designers = Mitsubishi, NTT publish date = 2000 derived from = E2, MISTY1 derived to = related to = certification = CRYPTREC, NESSIE key size = 128, 192 or 256 bits block size = 128 bits structure =… …   Wikipedia

  • SHARK — Infobox block cipher name = SHARK designers = Vincent Rijmen, Joan Daemen, Bart Preneel, Antoon Bosselaers, Erik De Win publish date = 1996 derived from = derived to = KHAZAD, Rijndael related to = key size = 128 bits block size = 64 bits… …   Wikipedia

  • MUGI — In cryptography, MUGI is a pseudorandom number generator (PRNG) designed for use as a stream cipher. It has been recommended for Japanese government use by the CRYPTREC project.MUGI takes a 128 bit secret key and a 128 bit initial vector (IV).… …   Wikipedia

  • Rijndael mix columns — The MixColumns operation performed by the Rijndael cipher, along with the shift rows step, is the primary source of diffusion in Rijndael. Each column is treated as a polynomial over GF( 28 ) and is then multiplied modulo x^4+1 with a fixed… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”