Partage entre P pour réunion entre R

[Ceubex]

Bonjour,

Il faut que je résolve une petite colle pour mon travail. J'ai une clé de décryptage. Je la partage en M morceaux d'égales longueur et je distribue certains de ces morceaux à P "gardiens de la clé" (ou des morceaux... parce qu'ils n'ont pas tout).

L'idée c'est que pour décrypter le message plus tard, il faudra toute la clé forcément mais au cas où il y ai des absents, on veut quand même pouvoir décrypter s'il y a au moins R gardiens réunis

Question : comment dois-je distribuer à mes P gardiens les M morceaux afin que si R gardiens sont réunis on puisse forcément décrypter.
On a donc P et R qui sont donnés à l'avance, M est à définir.
Et je précise qu'on souhaite éviter autant que possible que si seulement R-1 gardiens sont réunis ils puissent décrypter (mais de ce côté là on essaye de faire au mieux, ça n'est pas une contrainte obligatoire, disons que c'est mieux si on peut la satisfaire aussi bien que possible).


Pour illustrer un exemple simple, j'ai 3 gardiens et je veux que la réunion d'au moins 2 permette de décrypter, je coupe en 3 morceaux et donne au gardien A les morceaux 1 et 2, au B 2 et 3 et au C 3 et 1. Mais il faut résoudre pour P et R quelquonque

[XENSECP]

Salut,

Au final M sera égal à P. C'est plutôt la longueur qui va dépendre de P et R. Probablement R parmi P.

[Ben314]

Salut,
Sauf erreur, on s'en sort systématiquement avec {coeff. binomial} morceaux de clef et on ne peut pas faire avec moins de morceaux si on veut que seuls les groupes d'au moins R gardiens aient tout les morceaux de clef.
En fait, chaque morceau de clef sert à s'assurer qu'un certain groupe de R-1 gardien n'aura pas tout les morceaux de clef : tu donne le morceau de clef en question à tout les gardiens sauf à ceux de ce groupe de R-1 gardiens.

P=4 gardiens A,B,C,D et tu veut que R=3 quelconques d'entre aient tout les morceaux de clef.
Il y a parties à 2 éléments de l'ensemble à 4 éléments {A,B,C,D}.
Ces 6 parties sont :
1) {A,B} => tu donne le morceau de clef 1 à C et D.
2) {A,C} => tu donne le morceau de clef 2 à B et D.
3) {A,D} => tu donne le morceau de clef 3 à B et C.
4) {B,C} => tu donne le morceau de clef 4 à A et D.
5) {B,D} => tu donne le morceau de clef 5 à A et C.
6) {C,D} => tu donne le morceau de clef 6 à A et B.

Bilan : tu fabrique 6 morceaux de clef que tu donne A:4,5,6 ; B:2,3,6 ; C:1,3,5 ; D:1,2,4

[Ceubex]

Ben314 » grand merci, ça semble tout à fait fonctionner.
Par contre pour obtenir M on a la formule. Après quel est le protocole qui permet de distribuer les clés entre les membres ?

[Ben314]

Le seul truc dont tu as besoin, c'est de numéroter les parties à R-1 éléments de ton ensemble de P gardien. La façon dont tu numérote n'a aucune importance donc à la main, il suffit de dresser la liste des différentes parties comme dans l'exemple. (sans en oublier évidement, mais comme on connait le nombre total, y'a pas trop de soucis).

Si tu veut faire un truc informatique, il te faut créer une procédure qui prend en paramètre un entier m entre 1 et (ainsi que P et R) et qui te renvoie une partie à R-1 éléments de l'ensemble {1,2,...,P} (sous forme de tableau par exemple).
Un méthode simple consiste à voir que, parmi les parties à R-1 éléments de {1,2,...,P}, il y en a qui ne contiennent pas le "1" donc :
- Si tu ne prend pas le "1" dans la partie en question, et tu retranche 1 à P (sans modifier ni m, ni R).
- Si alors tu prend le "1" dans la partie en question, tu retranche à m et tu retranche 1 à P et à R.
puis tu passe à "2" et tu recommence, etc... jusqu'à "P".