Category Archives: Maths difficiles

Modéliser le trafic routier : introduction aux lois de conservation hyperboliques (1)

Posted on by
3

Il est assez facile de créer des modèles qui simulent le trafic routier. Bien que trop simpliste, et donc irréaliste, ces modèles constituent une bonne introduction à la théorie des lois de conservations hyperboliques.

L’équation de base

On va supposer que la route est une ligne droite sans début ni fin (pas très réaliste donc). Il n’y a qu’une seule voie : les voitures ne peuvent pas se doubler; si une voiture est bloquée elle bloque les voitures derrière elle. On modélise donc la route par la droite des réels \mathbf R.

On note v(t,x) la vitesse des voitures à l’instant t au point x et \rho(t,x) la densité de voitures.

Le principe physique utilisé ici est simple : la variation du nombre de véhicule entre deux points x_1 et x_2  en un instant t est égale à la différence des flux de voitures en x_1 (ce qui rentre) et x_2 (ce qui sort).

Le nombre de véhicule entre x_1 et x_2 à l’instant t est égal à

\displaystyle \int_{x_1}^{x_2} \rho(t,x) \mathrm dx

donc sa variation est

\displaystyle\partial_t \int_{x_1}^{x_2} \rho(t,x) \mathrm dx.

Le flux étant par définition v(t,x)\times \rho(t,x) on obtient d’après le principe physique

\displaystyle\partial_t \int_{x_1}^{x_2} \rho(t,x) \mathrm dx = v(t,x_1)\rho(t,x_1)-v(t,x_2)\rho(t,x_2).

Or par une formule d’intégration par parties on a

\displaystyle v(t,x_1)\rho(t,x_1)-v(t,x_2)\rho(t,x_2) =-\int_{x_1}^{x_2} \partial_x [ v(t,x)\rho(t,x)] \mathrm dx

d’où

\displaystyle \partial_t \int_{x_1}^{x_2} \rho(t,x) \mathrm dx=-\int_{x_1}^{x_2} \partial_x [ v(t,x)\rho(t,x)] \mathrm dx.

Comme x_1 et x_2 ne dépendent pas du temps on a par les régles de dérivation des intégrales

\displaystyle \partial_t \int_{x_1}^{x_2} \rho(t,x) \mathrm dx = \int_{x_1}^{x_2} \partial_t \rho(t,x) \mathrm dx.

Finalement on obtient

\displaystyle \int_{x_1}^{x_2} [\partial_t \rho(t,x)+\partial_x(v(t,x)\rho(t,x))]\mathrm dx=0.

Comme le choix des points  x_1 et x_2 est arbitraire on en déduit que ce qu’il y a sous l’intégrale est nul. On obtient donc l’équation

\boxed{\partial_t \rho(t,x)+\partial_x(v(t,x)\rho(t,x)) =0}.

Choix du flux

L’équation ci-dessus a deux inconnues. Il faut donc rajouter une autre équation si on veut arriver à la résoudre. Le plus simple est de considérer que la vitesse est une fonction décroissante de la densité (plus il y a de voitures moins on peut rouler vite).

Par exemple, on peut considérer que lorsque la densité est presque nulle les voitures roulent à une vitesse maximale v_{max} (typiquement 130 à l’heure) et que pour une certaine densité \rho_{max} les voitures sont à l’arrêt (embouteillage).

Un candidat serait donc la fonction affine

v(t,x)=v_{max}\left(1-\frac{\rho(t,x)}{\rho_{max}}\right)

et on obtient l’équation aux dérivées partielles suivante :

\boxed{\partial_t\rho(t,x)+\partial_x\left[v_{max}\left(1-\frac{\rho(t,x)}{\rho_{max}}\right)\rho(t,x)\right]=0}.

On a donc ici un modèle, extrêment simpliste certes, du traffic routier. Pour résoudre correctement ce problème, il faudra spécifier une condition initiale pour \rho en t=0.

Dans le prochain article nous verrons pourquoi le cadre classique des fonctions dérivables ne convient pas ici et comment y remédier.

Le théorème de Wilson

Posted on by
7

Le théorème de Wilson est un résultat très connu d’artihmétique élémentaire, qui donne une caractérisation anecdotique des nombres premiers.

Dans cet article, je rappellerai les démonstrations connues et vous présenterai une démonstration un peu plus étonnante (et très anecdotique) basée sur le théorème de Sylow en théorie des groupes.

Historique

Le théorème de Wilson a été découvert par Ibn al-Haytham (aussi connu comme Alhazen) vers les années 1000, mais est attribué à John Wilson (un étudiant de Edward Waring) qui l’a conjecturé au dix-huitième sicècle. C’est Waring qui publia la conjecture 1770, mais sans démonstration. La première preuve est dûe à Lagrange, et a été publiée en 1773. Il semblerait que Leibniz connaissait le résultat un siècle plus tôt, mais ne l’a jamais publié.

Théorème de Wilson

Un entier naturel p>1 est premier si et seulement si

(p-1)!+1 \equiv 0 \pmod p

Cette caractérisation des nombres premiers est un peu anecdotique et ne constitue pas un test de primalité utile (calculer la factorielle de p-1 n’est pas envisageable). Son principal intérêt réside dans son histoire et la simplicité de son énoncé et de ses preuves (exceptée bien entendu celle dont je vais parler en dernier et qui justifie l’existence de cet article).

Démonstration du sens réciproque

Commençons par démontrer que si (p-1)!+1\equiv 0\pmod p, alors p est premier. Supposons que cette équation est vraie, cela signifie qu’il existe k\in\mathbf Z tel que

kp-(p-1)!=1

Ainsi, on a une relation de Bezout entre p et 1<\ell <p, donc p est premier.

Démonstration du sens direct

par Lagrange

Notons \mathbf F_p=\mathbf Z/p\mathbf Z. C’est un corps et le groupe \mathbf F_p^\times de ses inversibles est d’ordre p-1. Ainsi, le petit théorème de Fermat implique que ses p-1 éléments sont racines du polynôme X^{p-1}-1\in\mathbf F_p[X] de degré p-1. Comme \mathbf F_p est un corps, et que les éléments 1\leq \ell < p sont racines de ce polynôme, on a

X^{p-1}-1=(X-1)(X-2)\cdots(X-(p-1)).

En évaluant cette expression en p, on trouve le résultat voulu.

par Gauss

Si p=2, le résultat est clair. On suppose donc p impair.

Le principe de cette jolie démonstration est de grouper deux par deux les éléments de \mathbf F_p^\times. Pour tout k\in\mathbf F_p^\times, k\neq 1, -1, il existe \ell\in \mathbf F_p^\times, \ell\neq k (sinon k^2=1, i.e., k\in\left\{-1,1\right\} ce qu’on a justement exclu) tel que k\ell =1. Ainsi, lorsqu’on élimine, dans le produit \prod_{1\leq k\leq p-1}k\in\mathbf F_p, les paires d’inverses mutuels dont le produit vaut 1, il ne reste que

\prod_{1\leq k\leq p-1}k = 1\times (p-1) = -1 \in \mathbf F_p,

ce qui prouve le résultat.

… par le théorème de Sylow

Commençons par dénombrer le nombre de p-Sylow du groupe symétrique \mathfrak S_p

Dans \mathfrak S_p, il y a (p-1)! éléments d’ordre p. En effet, un élément d’ordre p est un p-cycle car p est premier, et un p-cycle peut s’écrire avec n’importe quel élément en premier, et c’est l’ordre des p-1 éléments restants qui importe.

Maintenant, un p-Sylow est de cardinal p^\alpha maximal avec p^\alpha qui divise le cardinal de \mathfrak S_p. Ainsi, \alpha=1 et les p-Sylow sont d’ordre p, et contiennent l’identité et p-1 p-cycles. Réciproquement, chaque p-cycle est contenu dans un p-Sylow. Il y a donc

\frac{(p-1)!}{p-1}=(p-2)! p-Sylow.

Avec le théorème de Sylow…

on sait que le nombre de p-Sylow est congru à 1 modulo p. Ainsi

(p-2)!\equiv 1\pmod p,

et en multipliant par p-1, on a

(p-1)!\equiv p-1\equiv -1\pmod p.

Petit mot de la fin

J’aime bien cette dernière démonstration pour deux raisons. La première, c’est qu’elle relie les sous-groupes de Sylow avec un théorème d’arithmétique élémentaire, ce qui prouve (si besoin est encore) qu’en mathématiques il n’y a jamais qu’un seul moyen de prouver les choses. La seconde est que les étudiants, face au dénombrement des p-Sylow de \mathfrak S_p, utilisent immédiatement le théorème de Sylow et restent bloqué avec

n_p\equiv 1\pmod p,

où n_p est le nombre de p-Sylow. Là, il faut remettre les mains dans le cambouis pour s’en sortir. De plus, ce n’est pas un exercice difficile.

L’historique et les premières démonstrations sont tirées de la page sur le théorème de Wilson de la wikipédia.

Simuler l’équation des ondes en dimension 2

Posted on by
1

On peut modéliser la propagation d’une onde dans un milieu homogène, linéaire et isotrope en dimension 2 par l’équation aux dérivées partielles suivante :

\dfrac{1}{c^2} \dfrac{\partial^2}{\partial t^2} u(t,x,y)=\dfrac{\partial^2}{\partial x^2} u(t,x,y)+\dfrac{\partial^2}{\partial y^2} u(t,x,y)

où u(t,x,y) représente l’amplitude de l’onde au temps t et au point de coordonnées (x,y) et c la vitesse de propagation de l’onde dans le milieu considéré. Nous allons voir comment simuler une telle équation en utilisant la méthode des différences finies. Dans la suite, on considère c=1, on se donne la condition initiale u^0(x,y)=u(0,x,y) et on suppose que l’onde n’a pas de vitesse initiale :

\dfrac{\partial }{\partial t} u(0,x,y)=0.

On fait ces hypothèses pour simplifier l’article, mais la méthode reste valable sans.

Regardons déjà ce qui se passe en dimension 1. Pour une fonction f régulière, la formule de Taylor nous assure que pour un réel \Delta x>0 petit on a

f(x+\Delta x)=f(x)+\Delta x f^\prime (x)+\dfrac{ \Delta x^2}{2} f^{\prime\prime }(x)+\mathcal O(\Delta x^3)

et

f(x-\Delta x)=f(x)-\Delta xf^\prime(x)+\dfrac{\Delta x^2}{2}f^{\prime\prime }(x)+\mathcal{O}(\Delta x^3).

En additionnant les deux lignes, on a donc

f(x+\Delta x)+f(x-\Delta x)=2f(x)+\Delta x^2f^{\prime\prime }(x)+\mathcal{O}(\Delta x^3).

On note f_i la valeur de f au point i\Delta x : f_i=f(i\Delta x). En négligeant le terme en \mathcal O(\Delta x^3) on a donc

f^{\prime\prime }_i =\dfrac{f_{i+1}+f_{i-1}-2f_i}{\Delta x^2}.

On peut faire le même raisonnement avec des fonctions de plusieurs variables. L’équation des ondes s’écrit alors

\dfrac{u_{i,j}^{n+1}+u_{i,j}^{n-1}-2u_{i,j}^n}{\Delta t^2}=\dfrac{u_{i+1,j}^n+u_{i-1,j}^{n}-2u_{i,j}^n}{\Delta x^2}+\dfrac{u_{i,j+1}^n+u_{i,j-1}^n-2u_{i,j}^n}{\Delta y^2}

où \Delta t, \Delta x et \Delta y sont des réels positifs petits et où u_{i,j}^n=u(n\Delta t,i\Delta x,j \Delta y). On peut écrire cette formule de manière différente :

u_{i,j}^{n+1}=2u_{i,j}^{n}-u_{i,j}^{n-1}+\dfrac{\Delta t^2}{\Delta x^2}(u_{i+1,j}^n+u_{i-1,j}^{n}-2u_{i,j}^n)+\dfrac{\Delta t^2}{\Delta y^2}(u_{i,j+1}^n+u_{i,j-1}^n-2u_{i,j}^n)

ce qui permet ainsi de calculer les valeurs approchées de u^{n+1} en fonction des valeurs de u^n et u^{n-1}. Il suffit donc d’écrire une boucle dans votre logiciel de calcul numérique favori (pour moi Matlab, sinon en gratuit il y a Scilab) pour calculer les solutions approchées. Il reste cependant deux problèmes. On se donne la condition de départ u^0. On ne peut calculer u^1 par la formule précédente, car il nous faut les expressions des deux termes u^0 et u^{-1} que l’on a pas! Heureusement Taylor nous vient encore une fois en aide, on a

u^1_{i,j}=u^0_{i,j}+\Delta t \dfrac{\partial}{\partial t} u^0_{i,j}+\dfrac{\Delta t^2}{2}\dfrac{\partial^2}{\partial t^2} u^0_{i,j}+\mathcal{O}(\Delta t^3).

La vitesse initiale est nulle, donc le terme d’ordre 1 est nul. De plus, on a

\dfrac{\partial^2}{\partial t^2} u^0_{i,j}=\dfrac{\partial^2}{\partial x^2} u^0_{i,j}+\dfrac{\partial^2}{\partial y^2} u^0_{i,j}

par l’équation des ondes. En refaisant encore une fois les approximations par Taylor, on trouve que

u_{i,j}^1=u_{i,j}^0+\dfrac{\Delta t^2}{2\Delta x^2}(u_{i+1,j}^0+u_{i-1,j}^{0}-2u_{i,j}^0)+\dfrac{\Delta t^2}{2\Delta y^2}(u_{i,j+1}^0+u_{i,j-1}^0-2u_{i,j}^0).

Le second problème est que l’ordinateur ne peut effectuer les calculs que sur un nombre fini de données. Il faut donc borner i et j. Cela pose un problème pour calculer la valeur de u aux bords du domaine. Si on prend -N \leq j \leq N, pour calculer u^n_{N,j} il faudrait connaitre u^{n-1}_{N+1,j}, ce que l’on ne connait pas. On se donne alors les valeurs sur le bord du domaine de calcul. On peut par exemple donner une valeur nulle aux bords, ce qui donnera une onde réfléchie sur les bords. On peut également développer des méthodes pour que les bords soient absorbants, bien qu’il subsiste toujours des réflexions parasites. Ici, j’ai évité le problème en arrêtant la simulation quand la première onde touche les bords.

Voilà ce que donne cette méthode implémentée sous Matlab. Ca ressemble pas si mal que ça à une mare dans laquelle on aurait jeté une pierre, non?

Vidéo de l’équation des ondes en dimension 2

Remarque : la vidéo chez moi est en rouge sous Windows Media Player et en bleu sous VLC, je n’ai aucune idée de la raison… Avez-vous une idée?

L’équation de transport unidimensionnelle

Posted on by
Reply

On appelle équation aux dérivées partielles une équation qui lie les dérivées partielles d’une ou plusieurs fonctions. Elles sont énormément utilisées en physique, dans des domaines aussi variées que la mécanique des fluides (équation de Navier-Stokes), l’électromagnétisme (équations de Maxwell), la thermodynamique (équation de la chaleur), la mécanique quantique (équation de Schrödinger), etc… On les trouve également dans des domaines comme la météorologie, la synthèse d’image ou l’économie  (équation de Black-Scholes).

On va étudier l’exemple le plus simple d’équation aux dérivées partielles : l’équation de transport unidimensionnelle. Elle s’écrit sous la forme

\displaystyle \frac{\partial}{\partial x} u(x,y)+c \frac{\partial}{\partial y} u(x,y)=0

où u(x,y) est la fonction inconnue des deux variables x et y et où c \neq 0 est une constante. Comme pour les équations différentielles ordinaires, il faut ajouter une condition initiale :

u(0,y)=u_0(y)

où u_0 est une fonction donnée de la variable y que l’on suppose assez régulière, par exemple dérivable à dérivée continue.

Résolution

On suppose que u est une solution régulière de notre problème, c’est-à-dire que u admet des dérivées partielles selon x et selon y et que ses dérivées partielles sont continues.

On va montrer que u est constante le long de certaines droites, appelées caractéristiques. Pour y_0 un réel, posons D(x)=cx+y_0 la droite de pente c qui passe par y_0.

On a par les règles de dérivation des fonctions composées :

\displaystyle\frac{\mathrm d}{\mathrm d x} u(x,D(x))=\frac{\partial}{\partial x} u(x,D(x))+D'(x) \frac{\partial}{\partial y}u(x,D(x)).

Or D'(x)=c, on a donc

\displaystyle\frac{\mathrm d}{\mathrm d x} u(x,D(x))=\frac{\partial}{\partial x} u(x,D(x))+c \frac{\partial}{\partial y}u(x,D(x))

et comme u est solution de l’équation de transport, on a

\displaystyle\frac{\mathrm d}{\mathrm d x} u(x,D(x))=0

ce qui montre que u est constante le long de toutes les caractéristiques. On a donc pour tout réel x

u(x,D(x))=u(0,D(0))=u(0,y_0)

ce qui s’écrit

u(x,cx+y_0)=u_0(y_0).

Soient x et y deux réels. Pour connaître la valeur de u(x,y), il suffit de connaitre la valeur de u_0 au point où la caractéristique passant par (x,y) coupe l’axe des ordonnées car u est constante le long de cette caractéristique. On cherche donc le réel y_0 tel que la caractéristique passant par (0,y_0) de pente c passe aussi par le point (x,y). Il faut donc que D(x)=cx+y_0, c’est-à-dire y_0=y-cx. Finalement, on obtient

\boxed{u(x,y)=u_0(y-cx).}

C’est la formule de Duhamel. Réciproquement, il est facile de vérifier que si on définit u par la formule de Duhamel, alors u admet des dérivées partielles continues et que

\begin{cases} \displaystyle\frac{\partial}{\partial x} u(x,y)+c \frac{\partial}{\partial y} u(x,y)=0 \\u(0,y)=u_0(y).\end{cases}.

On a donc montré que u définie par la formule de Duhamel est l’unique solution de l’équation de transport.

Partage de secret

Posted on by
5

Supposons que le PDG d’une grande compagnie de soda veuille garder secrète la recette qui a fait la fortune de l’entreprise. Il l’enferme donc dans un coffre fort blindé, qui s’ouvre à l’aide d’une certaine clé (qu’il garde secrète). Cette solution est très sécuritaire dans le sens où seul le PDG peut accéder au secret. Mais elle revêt un gros défaut : si le PDG perd cette clé, ou vient à décéder dans un accident, la clé est perdue et personne ne peut jamais accéder à la recette, entraînant inévitablement la déroute de la multinationale.

Une des solutions est de donner des copies de cette clé secrète à des collaborateurs au travail. Mais répliquer la clé augmente les chances des espions de l’obtenir et de rapporter la recette à l’entreprise concurrente. Le PDG est bien conscient qu’il ne peut pas faire entièrement confiance à un de ses 5 subordonnés. Il veut donc mettre en place un schéma où tout groupe contenant au moins 3 de ses subordonnés puisse ouvrir le coffre alors que tout groupe contenant strictement moins de 3 subordonnés ne puisse rien savoir sur la clé.
Une solution qui consisterait à donner des bouts du secret aux subordonnés de manière à ce qu’ensemble ils puissent le reconstruire ne convient pas parce qu’ils connaîtraient alors partiellement la clé secrète.

Ce problème peut-être résolu par la mise en place d’un schéma de partage de secret.

Le partage de secret avec seuil

Notons 2\leq t<n des entiers. Notre but est de partager une clé secrète K entre un ensemble de n personnes \mathcal P = \{P_1, \ldots, P_n\} de telle manière que toute coalition de t ou plus de ces personnes puisse calculer K facilement, et que toute coalition de t-1 ou moins de ces personnes ne puisse rien déterminer sur la valeur de K, autrement dit que toutes les valeurs de K possibles soient équiprobables. Un tel schéma est appelé un schéma au seuil (t,n). Dans l’exemple introductif, le PDG cherche un schéma au seuil (3,5).

La valeur du secret est choisie par un participant spécial D (le dealer) (que l’on suppose bien évidemment ne pas faire partie de \mathcal P). Le dealer va donner à chaque participant une clé de partage. Cette distribution sera secrète bien entendu, pour qu’aucun des participants ne connaissent les clés de partage des autres participants.

Le problème de construire un tel schéma a été résolu indépendamment par Sharmir [1] et Blakley [2] en 1979.

Schéma de Shamir

Commençons par présenter le schéma de Shamir, qui repose sur l’interpolation polynômiale.

Le dealer veut partager la clé secrète K\in \mathbf F_q où q\geq n+1 est la puissance d’un nombre premier (on peut prendre q=p premier et raisonner dans \mathbf F_p bien évidemment). Il choisit de manière aléatoire n éléments distincts de \mathbf F_q que l’on note x_1, \ldots, x_n. Ces éléemnts ne sont pas les clés de partages secrètes, ce sont des clés publiques : chaque P_i reçoit la clé x_i. Dans l’exemple du PDG, on pourrait dire par exemple que x_i représente l’ordre d’arrivée de l’employé dans l’entreprise. Ensuite, il réalise les étapes suivantes :

  1. Il choisit secrètement et aléatoirement t-1 éléments de \mathbf F_q notés a_1, \ldots, a_{t-1}.
  2. Pour tout 1\leq i\leq n, le dealer calcule y_i=a(x_i) où

    a(X) = K+\sum_{i=1}^{t-1}a_jX^j.

  3. Pour tout 1\leq i\leq n, le dealer donne secrètement la clé de partage y_i à P_i

Regardons comment un groupe B=\left\{P_{i_1}, \ldots, P_{i_t}\right\} de t personnes (avec leur clé publique x_i) peut retrouver les coefficients secrets du polynôme a(X) par interpolation, et ainsi retrouver K=a(0). Comme y_{i_k} = a(x_{i_k}) pour tout 0\leq k\leq t, le groupe B obtient t équations linéaires en les t inconnues K, a_1, \ldots, a_{t-1}. Ainsi, le système obtenu par B peut-être écrit sous la forme

\begin{pmatrix}1& x_{i_1}& x_{i_1}^2& \cdots& x_{i_1}^{t-1}\\1& x_{i_2}& x_{i_2}^2& \cdots& x_{i_2}^{t-1}\\\vdots& \vdots & \vdots & & \vdots\\1& x_{i_t}& x_{i_t}^2& \cdots& x_{i_t}^{t-1}\\\end{pmatrix}\begin{pmatrix}K\\a_1\\\vdots\\a_{t-1}\end{pmatrix} = \begin{pmatrix}y_{i_1}\\y_{i_2}\\\vdots\\y_{i_t}\end{pmatrix}.

Or, la matrice A des coefficients x_i est appelée matrice de Vandermonde et son déterminant vaut \det(A) = \prod_{1\leq k<j\leq t}\left(x_{i_j}-x_{i_k}\right)\neq 0. Comme il est non nul (par choix des x_i), le système admet une unique solution sur \mathbf F_q, et K peut-être retrouvé.

Supposons maintenant que t-1 des n clés de partages secrètes sont révélées à un ennemi. Pour chaque candidat K'\in \mathbf F_q pour le secret, l'ennemi peut construire un et un unique polynôme a'(X) de degré t-1 tel que a'(0)=K' et a'(x_i)=y_i pour les t-1 clés connues. Par construction, ces q possibles polynômes sont équiprobables, en conséquence de quoi l'espion ne peut rien déduire sur la valeur de la clé secrète K.

Bien entendu, il y a une méthode alternative basée sur la formule de l'interpolation de Lagrange. La formule est la suivante :

a(X) = \sum_{j=1}^t y_{i_j} \prod_{\substack{1\leq k\leq t\\k\neq j}}\frac{X-x_{i_k}}{x_{i_j}-x_{i_k}}.

Étant donné qu’un groupe recherche la valeur du secret K=a(0), ils peuvent calculer

K = \sum_{j=1}^{t}y_{i_j}b_j, \qquad \text{avec} \quad b_j = \prod_{\substack{1\leq k\leq t\\k\neq j}}\frac{x_{i_k}}{x_{i_k}-x_{i_j}}.

Remarquons que les valeurs b_j ne dépendent que des x_i et peuvent-être pré-calculées.

Un exemple concret

Donnons un petit exemple concret pour soulager notre PDG qui a vraiment peur de faire un infarctus qui perdrait à tout jamais la recette ! Supposons que q=17 et que les coordonnées publiques sont x_i = i pour tout 1\leq i\leq 5. Supposons maintenant que les collaborateurs P_1, P_3 et P_5 veuillent retrouver le secret. Ils mettent en commun leurs clés de partages secrètes qui sont respectivement 8, 10 et 11. Comme a(X) = K+a_1X+a_2X^2, ils obtiennent le système d’équation suivant :

\left\{\begin{array}{lll}K+a_1+a_2 &=&8\\K+3a_1+9a_2&=&10\\K+5a_1+8a_2&=&11\end{array}\right.

Ce système admet une unique solution dans \mathbf F_{17}=\mathbf Z/17\mathbf Z : K=13, a_1=10 et a_2=2. Le secret est donc K=13 !

Schéma de Blakley

Donnons un autre exemple : le schéma de Blakley basé sur la géométrie des hyperplans sur les corps finis. Le secret est un point d’un espace t-dimensionnel, et les n clés de partages secrètes sont des hyperplans affines passant par ce point. Un hyperplan dans un espace t-dimensionnel à coordonnées dans un corps \mathbf F peut être décrit par une équation de la forme suivante :

a_1x_1 + a_2x_2 + \cdots + a_tx_t = y.

Le point d’intersection est obtenu en trouvant l’intersection d’un ensemble quelconque de t de ces hyperplans. Par exemple, le secret peut être la première coordonnée du point d’intersection.

Disons que \mathbf F = \mathbf F_q est le corps sur lequel on travaille. Le dealer génère un point x dans \mathbf F_q^t, où la première coordonnée x_1 est la clé secrète et les autres coordonnées sont choisies aléatoirement dans \mathbf F_q. Le ième participant recevra comme clé de partage secrète l’hyperplan sur \mathbf F_q d’équation

a_{i,1}x_1+a_{i,2}x_2+\cdots+a_{i,t}x_t=y_i.

Pour obtenir un schéma au seuil (t, n), il y aura n équations d’hyperplan, et on obtient alors un système linéaire n\times t: Ax=y.

Le dealer donne en pratique la clé de partage secrète y_i ainsi que les coordonnées (qui peuvent être publiques) a_{i,1}, \ldots, a_{i,t} au participant P_i. un choix judicieux pour la matrice A est de faire en sorte que ses lignes soient les lignes d’une matrice de Vandermonde pour se ramener à une situation similaire à celle du schéma de Shamir.

Pour aller plus loin…

Bien entendu, ceci n’est qu’une introduction sommaire à un domaine toujours en pleine expansion en cryptologie. On pourra trouver d’autres schémas basés sur la géométrie, sur les graphes, sur le théorème des restes chinois… Une excellente introduction au sujet est l’article [3].

Pour les plus intrépides d’entre vous, remarquez que jusquà présent nous avons travaillé sur des corps, s’autorisant allégrement la possibilité d’inverser pour retrouver le secret si nécessaire. Un sujet intéressant est de vouloir construire des schémas valables sur n’importe quel groupe abélien (sans connaître le groupe, c’est-à-dire un schéma en boîte noire), qui ont fait l’objet de deux articles récents [4] et [5].

Références
  • [1] A. Shamir – « How to share a secret », Communications of the ACM 22 (1979), no. 11, p. 612 – 613.
  • [2] G. R. Blakley – « Safeguarding cryptographic keys », AFIPS Conference Proceedings 48 (1979), p. 313 – 317.
  • [3] D. R. Stinson – « An explication of secret sharing schemes », Designs, Codes and Cryptography 2 (1992), no. 4, p. 357 – 390.
  • [4] R. Cramer & S. Fehr – « Optimal black-box secret sharing over arbitrary Abelian groups », Advances in Cryptology – CRYPTO’02 (2002), p. 272 – 287.
  • [5] R. Cramer, S. Fehr & M. Stam – « Black-box secret sharing from primitive sets in algebraic number fields », Advances in Cryptology – CRYPTO 2005, Springer, 2005, p. 344-360.