Réduction modulaire d’un nombre de degré 2k par un module de degré k,
par la méthode du "DR modulus" généralisée.
En principe cette méthode est utilisé pour des modules premiers répondant à
certains critères, mais on peut l’étendre à tous les modules. Voir le document
prime_mod.pdf édité par deux auteurs Coréens, Mrs Chea Hoon Lim et Pil Joong Lee
Dans le cas de crypto-systèmes, le module est souvent premier
(RSA par exemple)
Pour fixer les idées, nous allons prendre k = 32, ce qui nous donne :
Un nombre Z de 64 octets à réduire modulo un nombre m de 32 octets.
Prenons comme base b, la longueur du mot utilisé par la machine de traitement :
1 int = 16 bits == 2 octets
Z peut s’écrire sous forme d’un groupement de 32 integers, (ce qui nous ramène k = 16 et 2k = 32)
ou encore:
a31.b31 + a30.b30 + a29.b29 +....+
a2.b2 + a1.b1 + a0.b0
et le modulo de ce développement :
p = (a31.b31 + a30.b30 + a29.b29 + ....
a2.b2 + a1.b1 + a0.b0)mod m
Séparons ce nombre en 2 parties haute et basse :
Z = H.232.8 + L,
avec H, les 32 octets de poids forts, et L, les 32 octets de poids faibles.
La représentation de H sera donc 32 octets significatifs, suivi de 32 octets à 0.
H = a31.b31 + a30.b30 +....
+ a17.b17 + a16.b16
Nous allons réduire ce nombre de degré 2k en un nombre de degré k+1, par DR.
Ensuite, on additionne ce résultat avec la partie basse L définie ci-dessus. Il ne restera plus
qu’à faire une réduction modulaire classique par soustraction.
La réduction modulo de ce H s’écrit alors :
p = (a31.b31)mod m +
(a30.b30)mod m + (a29.b29)mod m + ... +
(a18.b18)mod m + (a17.b17)mod m +
(>a16.b16)mod m
On va substituer le chaque terme par son modulo calculé, qui aura le degré 2k-n (n[1..k-1]
et qui permet de supprimer le terme en 2k-(n+1).
En fait, on incorpore par addition, chaque terme par son modulo de degré réduit d’une unité,
Calculer le modulo d’un nombre de 16 bits, de puissance bx. Soit N ce nombre.
On travaille en hexadecimal, c’est-à-dire que chaque nombre se présente sous forme d’une suite de
chiffres de 0 à F, composés chacun de 4 bits. N peut se présenter sous la forme:
N = (a3.212 + a2.28 +
a1.24 + a0.20 ) bx
Le module m devra toujours avoir un degré inférieur à x.
N mod m = a3.212 mod m + a2.28 mod m +
a1.24 mod m + a0.20 mod m
== a3(28 mod m)24 mod m + (a2.28 mod m)20 mod m +
(a1.20 mod m).24 mod m + a0.20 mod m
Il suffit de calculer les 15 valeurs de
(i.2256.24) mod m == i.0x10.2256
et les 15 valeurs de
(i.2256.20 )mod m == i.0x01.2256
avec i variant de 1 à 0xF, et de les mémoriser sous forme de 2 tables de 15 valeurs de k int.
La première table Tx10[0..15] et la deuxième Tx1[0..15].
Pour calculer le modulo d’un facteur, on aura :
N mod m = Tx10[a3] + Tx1[a2] +
((Tx10[a1] + Tx1[a0])>> 8)
Le calcul se résumera à une suite d’additions et de décalages, jusqu’à ce que
la partie haute soit réduite à un nombre de degré juste plus élevé que le module.
D’après la généralisation proposée dans le document cité plus haut, on a
p’ = bk+r mod p et suivant les recommendations du même document, on prend r = 2, pour le calcul des tables.
Dans le programme proposé ci-dessous, il est plus pratique de travailler avec des octets. Cela donne un
listing plus cours et ramène la boucle à deux additions au lieu de 4 à la suite, mais double la boucle.
Le pointeur de travail évolue de façon à décaler l’addition de la position la plus
élevée vers la position la plus basse.
Cette méthode ne pourra pas être utilisée dans l’application à microprocesseur 8 bits,
si la capacité de la RAM est limitée, et on procédera par décalage du résultat de
l’addition vers les poids forts, sans toucher à la position terme issu des tables.
byte v[128], t[128], bufr[128];
/* les buffers de travail fixés à 128, mais peuvent être plus grands */
/*********************** ModuloK **************************/
/* le nombre à réduire arrive dans l’ensemble de deux */
/* buffers buf1 et buf2 de 32 octets, et le résultat va dans le buf1, et le module est
pointé par *module et k donne la longueur du module, en octets */
void ModuloK(byte *module, byte k)
{
int cpt = 0, num;
int n;
byte octet;
BYTE carry;
byte *p;
memset(v, 0, 2*k);
memcpy(v, buf1, k);
/* copy des k octets MSB en v */
p = v;
/* pointeur sur le degré élevé du nombre à réduire */
cpt = 0;
/* deux compteurs */
octet = k-1;
/* k - 1 */
_L001:
/*isolement du poids fort du caractère de degré
le plus élevé */
if((Acc = p & 0xF0));
{
_L002:
num = (Acc / 0x10) - 1;
/* terme de la table Tx10[] */
p &= 0x0F;
/* suppression du MSQ */
/* addition du terme convertit pour le poids fort de l’octet de degré le plus élevé */
carry = adc(p+2, Tx10[num], p+2, k, 0);
if(carry)
{
*(p+1) += 1;
if(!(*(p+1)))
{
*p += 1;
if(*p & 0x10)
{
Acc = 0x10;
goto _L001;
}
}
}
}
if(*p)
{
num = p - 1;
/* l’index de la table Tx1 */
_L003:
/* addition du terme convertit pour le poids faible de l’octet de degré le plus élevé */
carry = adc(p+2, Tx1[num], p+2, k, 0);
if(carry)
{
*(p+1) += 1;
if(!(*(p+1)))
{
num = 0;
goto _L003;
}
}
}
if(--octet)
/* au suivant */
{
cpt++;
*p = 0;
p++;
goto _L001;
}
/* nous avons réduit la partie haute (H) à
un degré juste supérieur à celui du module.
Il ne reste plus qu’à additionner la partie basse mise en réserve, et
de calculer par soustraction le modulo du résultat */
else
{
memset(t, 0, k+2);
memcpy(&t[1], buf2, k);
/* récupération de la 2ème partie du nombre d’entrée */
carry = adc(&v[31], t, bufr, k+2, 0);
/* addition */
if(carry && !(++v[0]))
{
v[k+2] = 0;
a = b = 0;
Acc = octet = 1;
num = 0;
goto _L003;
}
}
memset(v, 0, 128);
memcpy(v, module k); /* récupération du module */
/***** réduction modulo par soustractions *****/
while(bufr[0])
{
for(n = 0; n < k+2; n++)
if(bufr[n]-v[n])
break;
if(n == k+1 || bufr[n] >= v[n])
{
carry = sbc(bufr, v, bufr, k+1, 0);
}
carry = rorup(v, k+2, 0);
}
memcpy(buf1, &bufr[1], k);
}
/****************************** rorup ****************************/
BYTE rorup(BYTE *p, int nb, BYTE carin)
{
BYTE carry, temp;
int n;
carry = carin;
for(n = 0; n < nb; n++)
{
temp = *(p+n) & 1;
*(p+n) = (*(p+n) >> 1) | (carry ? 0x80 : 0);
carry = temp;
}
return(carry);
}
/** les fonctions adc, sbc et rorup sont respectivement :
addition : carry = adc(*in1, *in2, *out, size, in_carry)
soustraction : carry = sbc(*in1, *in2, *out, size, in_carry)
Ces fonctions sont dans le listing de la multiplication
shift : carry = rorup(*in, size, in_carry);
addition avec carry, soustraction avec carry, et décalage à droite d’un bit **/
Remarque :
/**************/
N = 655.103
m = 15.
N mod m = 10
m = 150
N mod m = 100
m = 1500
N mod n = 1000
m = 15000
N mod m = 10000
Tant que le degré de m est inférieur au degré de n,
N mod (m.bx) = (N mod m).bx
/**************/
Calcul des tables Tx10 et Tx1
La fonction ci-dessous permet de calculer les valeurs à mettre dans les tables. Cette fonction est
appelée deux fois, avec des valeurs de val = 0x10 pour la table Tx10 et 0x01 pour la table Tx1.
On utilise un buffer de travail de la longueur k plus la valeur r, conseillée égale à 2. Dans notre exemple,
k étant de 32, la longueur du buffer sera de 34. La réduction par soustraction nécéssite
alors 16 décalages (2 mots de 8 bits).
/***************************** mod10 ***************************/
byte Tx10[15][K] ;
/* les deux tables de valeurs précalculées */
byte Tx1[15][K] ;
/* calcule les moduli bk+r mod p */
/* val, la valeur à mettre dans le premier octet, 0x10 ou 0x01 */
/* *module, l’adresse du module à utiliser */
/* bufout, le buffer de sortie */
void mod10(byte val, byte *module, byte *bufout, byte k )
{
int x, n, b, i;
byte c;
BYTE carry, *p;
memset(r, 0, 128);
memset(a, 0, 128);
memcpy(a, module, k)
/* copy du module dans le registre de travail */
r[0] = val;
/* initialisation de la valeur à traiter */
/* calcul du modulo par soustraction */
for(n = 0 ; n <= 16; )
/* r = 2 donne 16 décalages */
{
for(x = 0; x <= k+2;x++)
{
carry = (a[x] > r[x]) ? 1 : 0;
if(r[x] - a[x])
break;
}
if(!carry)
sbc(r, a, r, k+2, 0);
else
{
n++;
if(n > c)
break;
rorup(a, k+2, 0);
}
}
for(n = 0; n < k+2; n++)
r[n] = r[n+2];
for(n = 0; n < k+2; n++)
a[n] = a[n+2];
memcpy(bufout, r, k) ;
p = (val == 0x10) ? &Tx10[0] : &Tx1[0];;
/* la table à remplir */
/* stocke le résultat, puis additionne et modulo */
/* à la sortie, on a les 15 valeurs 1, 2, 3, etc.. bk+r mod p */
for(n = 0; n < 0x0F; n++)
{
carry = adc(bufout, r, bufout, k, 0);
if(carry)
{
do {
carry = sbc(bufout, a, bufout, k, 0);
} while(!carry);
}
do {
for(x = 0; x < k; x++)
{
carry = (a[x] > *(bufout + x)) ? 1 : 0;
if(*(bufout + x) - a[x])
break;
}
if(!carry)
sbc(bufout, a, bufout, k, 0);
} while(!carry);
}
}
|
retour index