Trouver la clé secrète de RSA

$val6 Bob a donné à Alice la clé publique RSA suivante :

, .

Les facteurs premiers de ont même taille (le même nombre de bits en binaire).

Mais le choix de la clé privée n'a peut-être pas été bien fait, car elle est peut-être inférieure à .

Vous allez peut-être pouvoir casser la clé en faisant tourner l'algorithme d'Euclide sur

et sur .

En utilisant le tableau ci-dessus, quel candidat avez-vous pour la clé privée :

$val25
Le candidat pour la clé privée est $val31. La ligne suivante est extraite du tableau précédent :
$val30
Si , que vaudrait la somme ?

Si ce n'est pas un entier, donnez sa partie entière
L'entier $val31 est-il la clé privée


Logarithme discret, baby-giant I

Soit un nombre premier. L'élément $val10 est un générateur de d'ordre $val11. On désire calculer le logarithme fini d'un élément dans la base $val10 ( sera donné plus tard).

Soit le plus petit entier supérieur à la racine carrée de $val7. La table des premières puissances de dans est $val20
$val10$m_j
$m_j
Réordonnée, elle devient $val15 $val17
Enfin, on a

$m_equiv modulo $val7

Analyse de l'algorithme : Combien d'éléments de a-t-on stockés ? . On prend .


Logarithme discret, pas de bébé-géant II

Soit un nombre premier. L'élément $val10 est un générateur de d'ordre $val11. On désire calculer le logarithme discret d'un élément dans la base $val10 ( sera donné plus tard).

Soit le plus petit entier supérieur à la racine carrée de $val7.

Construire le vecteur dont la -ième composante est mod $val7 pour :

On obtient la table dans ($m_ZZ/$val7$m_ZZ): $val19
$val10$m_j
$m_j
Construire la table obtenue en arrangeant la deuxième ligne de la table par ordre croissant et en faisant les mêmes opérations sur la première ligne (on la rentrera comme une matrice : les éléments d'une ligne sont séparés par une virgule).
En effet, on obtient la matrice :
Calculer , puis modulo $val7 :
modulo $val7
modulo $val7

Analyse de l'algorithme : Combien d'éléments de a-t-on stockés? . Retenons que

$val20 modulo $val7
$val21 modulo $val7
On prend .

Quel est le plus petit entier tel que soit dans la deuxième ligne de la table :

Calculez .

Donnez le nombre de multiplications que vous venez de faire.

Comparez vous-même le coût des opérations avec les $val11 ou $val11/2 calculs d'éléments de que vous auriez pu avoir à faire sans la méthode précédente.


Message et lemme chinois

$val28 Vous venez de recevoir un message inférieur à $val13 : plus précisément, vous ont été transmis les réductions de modulo certains entiers . Malheureusement, certaines des réductions de sont peut-être fausses. Il y a au plus une erreur. deux erreurs. Vous devez retrouvez le nombre . Les classes résiduelles transmises sont
$(val18[2*$m_i - 1]) modulo $(val8[2*$m_i - 1])   $(val18[2*$m_i]) mod $(val8[2*$m_i])  
Quelle est la valeur du message effectivement transmis (il doit être inférieur au produit des ) :

Vous voulez appliquer l'algorithme de Bezout : sur quels nombres ?

,

L'algorithme d'Euclide appliqué à et donne les équations suivantes $val26
Quel est le message ?


Autour de l'algorithme d'Euclide I

Trouver un entier compris entre $val6 et $val7 $val12 et tel que l'algorithme d'Euclide de par $val6 nécessite exactement $val10 étape étapes .

Elévation à la puissance

Voici les résultats partiels des calculs d'élévation à la puissance par l'algorithme binaire de droite à gauche. $val11 $val14 $val15 $val13

Elévation à une puissance

Calculer le nombre de multiplications et d'élévations au carré que vous devez faire en utilisant l'algorithme binaire d'exponentiation par $val6.

Approximant de Padé

$val6 On désire calculer le - de .
Pour cela, on va appliquer l'algorithme d'Euclide à

et à

En appliquant l'algorithme d'Euclide à et à , on obtient $val17 Calculer le -approximant de Padé.

Ecrire 0 s'il n'existe pas


Développement de Laurent en 1/x

On fait un développement de la fraction rationnelle en dans

.

Calculer le coefficient de de ce développement.