Overblog Suivre ce blog
Editer l'article Administration Créer mon blog

Pourquoi ce blog ?

CouvPocheIndispensables
J'ai créé ce blog lors de la sortie de mon livre "Les Indispensables mathématiques et physiques pour tous", Odile Jacob, avril 2006 ; livre republié en poche en octobre 2011 (achat en ligne) (sommaire du livre).
Je développe dans ce blog des notions de mathématiques et de physique à destination du plus large public possible, en essayant de susciter questions et discussion: n'hésitez pas à laisser vos commentaires!

Rechercher

Indispensables astronomiques

Nouveauté octobre 2013, mon livre "Les Indispensables astronomiques et astrophysiques pour tous" est sorti en poche, 9,5€ (éditions Odile Jacob, éidtion originale 2009). Comme mon premier livre (Les Indispensables mathématiques et physiques), c'est un livre de notions de base illustrées avec des exemples concrets, s'appuyant sur les mathématiques (géométrie notamment) pour l'astronomie, et sur la physique pour l'astrophysique. Je recommande vivement sa lecture.

Communauté de blogs

22 novembre 2006 3 22 /11 /novembre /2006 14:54
Un de mes premiers posts concernait le petit théorème de Fermat (pas le grand) : "Pour tout nombre entier a , pour tout nombre premier p, ap et a ont le même reste dans la division par p ".On notera ap ≡ a (mod. p), ce qui se lit ap est congru à a modulo p.
Voyons comment le petit théorème de Fermat (1640) est utile à la cryptographie sur Internet (et est sans doute plus utile que le grand théorème de Fermat !).
Tout d’abord Euler le généralise en introduisant la fonction indicatrice d’Euler φ(n) égale au nombre d’entiers inférieurs à n et premiers avec n ; il démontre le théorème d’Euler, pour tout nombre a premier avec n :
a φ(n) ≡ 1 (mod. n)
On retrouve, pour n premier (on a alors φ(n) = n-1) , a premier avec n, le petit théorème de Fermat ci-dessus.
Un petit bout de cryptographie simple maintenant. Alice (A) et Bob (B) veulent communiquer de manière secrète, par exemple Alice veut envoyer à B (banque) un message M correspondant à son numéro de carte de paiement. Le système de cryptographie affecte à B les nombres suivants :

  • p un grand nombre premier, q un grand nombre premier, n = p × q

  • c un nombre premier avec φ(n) = φ(p) φ(q)= (p-1)× (q-1)

  • d l’inverse de c par rapport à φ(n), c'est-à-dire un nombre tel que le produit cd a comme reste 1 dans la division par φ(n) ; il est possible de trouver un tel nombre unique car c est premier avec φ(n).
Arrêtons-nous un instant sur ce dernier point pour donner un exemple avec des petits nombres : p = 7, q = 11, φ(pq) = 10 × 6 = 60, c = 7 par exemple, on trouve d tel que cd = 60k +1, soit d = 43, on vérifie 7 × 43 = 5 × 60 + 1.

Le couple de nombres (n, c) est connu de tous, c’est la clef de chiffrement publique de Bob; le couple (n,d) n’est connu que de lui, c’est la clef de chiffrement privée de Bob. Pourquoi d n’est-il connu que de Bob ? C’est là toute l’astuce du cryptage Internet (dit cryptage RSA). On ne connaît les nombres premiers que jusqu’à un certain rang : si l’on prend deux grands nombres premiers et qu’on les multiplie n = p × q, alors quelqu’un qui ne connaît que n (clef publique) ne peut pas reconstituer p et q à partir de n avec les moyens de calcul actuels ; donc il ne peut connaître φ(n), ni d même s’il connaît c. Seul Bob peut connaître d à partir des trois nombres (p,q,c).
En revanche on peut affecter à Bob un nombre d connu de lui seul ; partant de c premier avec φ(n) on trouve d par ordinateur, il s’agit d’un " problème d’ordre p ", tandis que trouver d sans connaître p et q est un " problème d’ordre n = pq " insoluble avec les ordinateurs actuels.

Terminons le chiffrement du message, Alice envoie à Bob le message ainsi chiffré à partir du message initial M :
M’ ≡ Mc (mod. n)
soit le reste de la division de Mc (M puissance c) par n
Bob fait le déchiffrement avec sa clef privée qu’il est seul à connaître (donc personne ne peut faire ce déchiffrement autre que Bob) comme suit, en élevant M’ qu’il reçoit à la puissance d et en faisant un calcul de reste de division par n :
M’d ≡ Mcd (mod. n)

Or par construction c × d = r × φ(n) + 1, donc :
M’d ≡ Mcd (mod. n)= Mrφ(n)×M (mod. n).
Or le théorème d’Euler ci-dessus donne Mrφ(n)≡ 1 (mod. n) (c’est vrai si M est premier avec n, mais on peut démontrer que c’est aussi vrai si M n’est pas premier avec n), donc :
M’d ≡ Mcd (mod. n)= Mrφ(n)×M ≡ M (mod. n)
Bob retrouve le message M initial.

En résumé, Alice élève M à la puissance c de la clef publique de Bob, puis Bob élève ce résultat à la puissance d de sa clef privée, et en faisant le reste de la division par n retombe sur le message M originel.
 
Et tout cela grâce à deux faits principaux :

  1. 1. du point de vue mathématique, le théorème d’Euler et le petit théorème de Fermat (1642)

  2. 2. du point de vue informatique (puissance des ordinateurs), l’impossibilité de décomposer n = pq en ses facteurs p et q quand ce sont de grands nombres premiers.

Partager cet article

Repost 0

commentaires

renato 07/01/2007 20:45

Reste plus qu'a développer ce blog

Alexandre Moatti 08/01/2007 09:31

Oui, merci de vos encouragements, mais n'hésitez pas chacun de vous à laisser des commentaires, çà aide...

Articles Récents

Alterscience (janvier 2013)

Mon livre Alterscience. Postures, dogmes, idéologies (janvier 2013) détails.


CouvertureDéf


Récréations mathéphysiques

RécréationsMathéphysiques

Mon dernier ouvrage est sorti le 14 octobre 2010 : Récréations mathéphysiques (éditions Le Pommier) (détails sur ce blog)

Einstein, un siècle contre lui

J'ai aussi un thème de recherche, l'alterscience, faisant l'objet d'un cours que j'ai professé à l'EHESS en 2008-2009 et 2009-2010. Il était en partie fondé sur mon second livre, "Einstein, un siècle contre lui", Odile Jacob, octobre 2007, livre d'histoire des sciences (voir billet sur ce blog, et notamment ses savoureux commentaires).

Einstein, un siècle contre lui