A la recherche de Phi

Toute recherche jusqu’à présent s’est montrée vaine : Nous avons bien trouvé quelques petits trucs ici et là mais rien qui ne soit une avancé significative vers le déchiffrement du « Green Code ».

Nous avons pour l’instant concentré nos efforts sur la caractéristique singulière de e. Nous avons bien trouvé 7 facteurs premiers. Mais cela semble avec le recul sans intérêt.

Si nous n’avons pas été capables de trouver d, peut être serons nous plus chanceux (… ou pas) si nous nous lançons à la recherche de \phi(N).

Par définition, \phi(N) = (p-1)\times(q-1) = pq + 1 - (p+q) < N+1-2\sqrt N

Assez facilement, nous pouvons démontrer que pour tout N produit de 2 grands nombres premiers, \phi(N) est divisible par 4.

Mais il est possible d’aller plus loin. En effet, nous pouvons en fonction des restes de dans certaines divisions euclidiennes déterminer des facteurs de \phi(N). Notamment :

  • Si N = 2 mod 3, alors 3 divise \phi(N)
  • Si N = 1 mod 4 ou N = 3 mod 4, alors 4 divise \phi(N)
  • Si N = 5 mod 6, alors 6 divise \phi(N)
  • Si N = 3 mod 8 ou N = 7 mod 8, alors 8 divise \phi(N)
  • Si N = 5 mod 12 ou N = 11 mod 12, alors 12 divise \phi(N)
  • Si N = 11 mod 24 ou N = 23 mod 24, alors 24 divise \phi(N)

Dans notre cas particulier, pouvons-nous trouver d’autres facteurs de \phi(N) ?

Nous avons N = 3 mod 8, donc \phi(N) est divisible par 8. En soit cela n’a rien d’extraordinaire, sauf si nous sommes partisans d’une tentative de recherche « brute force » de \phi(N) Dans ce cas, nous pouvons diviser le nombre de recherche par un facteur 8.

Mais nous pouvons tout de même conclure que p (ou q)  est de la forme 4k+1.

p-1 (où p désigne un des facteurs de N) serait-il friable ?

Publicités

A propos JoMendes

Amateur de mathématiques et d'hexadécimal. Je m'intéresse de près ou de loin suivant mon niveau à tous les sujets de sécurité de l'information.
Cet article, publié dans Challenge ANSSI, Cryptographie Asymétrique, est tagué . Ajoutez ce permalien à vos favoris.

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s