Inverse modulaire

Résumé

En mathématiques et plus précisément en arithmétique modulaire, l'inverse modulaire d'un entier relatif a pour la multiplication modulo n est un entier u satisfaisant l'équation : :au\equiv1\pmod n. En d'autres termes, il s'agit de l'inverse dans l'anneau des entiers modulo n, noté ℤ/nℤ ou ℤ. Une fois ainsi défini, u peut être noté a^{-1}, étant entendu implicitement que l'inversion est modulaire et se fait modulo n. La définition est donc équivalente à : :u\equiv a^{-1}\pmod n. L'inverse de a modulo n existe si et seulement si a et n sont premiers entre eux, (c.-à-d. si PGCD(a, n) = 1). Si cet inverse existe, l'opération de division par a modulo n équivaut à la multiplication par son inverse. Définition équivalente D'après la définition ci-dessus, u est un inverse de a modulo

Source officielle

https://fr.wikipedia.org/wiki/Inverse_modulaire

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (16)

Publications associées

Chargement

Personnes associées (1)

Personnes associées

Chargement

Unités associées (1)

Unités associées

Chargement

Concepts associés (22)

Concepts associés

Chargement

Cours associés (8)

Cours associés

Chargement

Séances de cours associées (11)

Afficher plus

Séances de cours associées

Chargement

The block cipher MMB was designed by Daemen, Govaerts and Vandewalle, in 1993, as an alternative to the IDEA block cipher. We exploit and describe unusual properties of the modular multiplication in

Z_{2^{32} - 1}

, which lead to a differential attack on the full 6-round MMB cipher (both versions 1.0 and 2.0). Further contributions of this paper include detailed square and linear cryptanalysis of MMB. Concerning differential cryptanalysis (DC), we can break the full MMB with 2^118 chosen plaintexts, 2^95.91 6-round MMB encryptions and 2^64 counters, effectively bypassing the cipher's countermeasures against DC. For the square attack, we can recover the 128-bit user key for 4-round MMB with 2^34 chosen plaintexts, 2^126.32 4-round encryptions and 2^64 memory blocks. Concerning linear cryptanalysis, we present a key-recovery attack on 3-round MMB requiring 2^114.56 known-plaintexts and 2^126 encryptions. Moreover, we detail a ciphertext-only attack on 2-round MMB using 2^93.6 ciphertexts and 2^93.6 parity computations. These attacks do not depend on weak-key or weak-subkey assumptions, and are thus independent of the key schedule algorithm.

2009

Chargement

Cryptanalysis of the full MMB Block Cipher

Jorge Nakahara, Yue Sun

The block cipher MMB was designed by Daemen, Govaerts and Vandewalle, in 1993, as an alternative to the IDEA block cipher. We exploit and describe unusual properties of the modular multiplication in ZZ232 −1 , which lead to a diﬀerential attack on the full 6-round MMB cipher (both versions 1.0 and 2.0). Further contributions of this paper include detailed square and linear cryptanalysis of MMB. Concerning diﬀerential cryptanalysis (DC), we can break the full MMB with 2118 chosen plaintexts, 295.91 6-round MMB encryptions and 264 counters, eﬀectively bypassing the cipher’s countermeasures against DC. For the square attack, we can recover the 128-bit user key for 4-round MMB with 234 chosen plaintexts, 2126.32 4-round encryptions and 264 mem- ory blocks. Concerning linear cryptanalysis, we present a key-recovery attack on 3-round MMB requiring 2114.56 known-plaintexts and 2126 en- cryptions. Moreover, we detail a ciphertext-only attack on 2-round MMB using 293.6 ciphertexts and 293.6 parity computations. These attacks do not depend on weak-key or weak-subkey assumptions, and are thus in- dependent of the key schedule algorithm.

Springer2009

Chargement

Bipartite modular multiplication method

Marcelo Kaihara

This paper proposes a new modular multiplication method that uses Montgomery residues defined by a modulus M and a Montgomery radix R whose value is less than the modulus M. This condition enables the operand multiplier to be split into two parts that can be processed separately in parallel-increasing the calculation speed. The upper part of the split multiplier can be processed by calculating a product modulo M of the multiplicand and this part of the split multiplier. The lower part of the split multiplier can be processed by calculating a product modulo M of the multiplicand, this part of the split multiplier, and the inverse of a constant R. Two different implementations based on this method are proposed: One uses a classical modular multiplier and a Montgomery multiplier and the other generates partial products for each part of the split multiplier separately, which are added and accumulated in a single pipelined unit. A radix-4 version of a multiplier based on a radix-4 classical modular multiplier and a radix-4 Montgomery multiplier has been designed and simulated. The proposed method is also suitable for software implementation in a multiprocessor environment.

2008

Chargement

The block cipher MMB was designed by Daemen, Govaerts and Vandewalle, in 1993, as an alternative to the IDEA block cipher. We exploit and describe unusual properties of the modular multiplication in

Z_{2^{32} - 1}

2009