Traitement de données cryptées

[invited37a86e7]

Bonjour,

Ma question concerne la cryptographie: imaginons que je dispose de données privées et d'un programme informatique qui traite ces données. Je souhaite confier l'exécution de ce programme à quelqu'un d'autre, sans que quiconque puisse voir mes données privées en clair. Je les crypte donc. Suis-je capable de transformer mon programme informatique pour qu'il traite mes données cryptées (sans jamais avoir besoin de les décrypter bien sur) ? Est-ce mathématiquement possible ?

Merci par avance.
-----

[invitebe0cd90e]

Ta question est trop vague, mais en general non... Et en particulier, je t'avoue ne pas reussir a trouver d'exemple ou ca marcherais.

Le but du chiffrement est de transformer un ensemble de donner cohérent, qui fait "sens", en quelque chose qui a l'apparence et les propriétés d'une suite aléatoires. En particulier, un bon algorithme doit etre tel qu'une tout petite modification des données "en clair", induit une modification importante et "imprevisible" des données cryptées. Donc a priori impossible d'appliquer une modif sur les données cryptées pour induire une modif voulu sur les données en clair.

[invited37a86e7]

Ta question est trop vague, mais en general non... Et en particulier, je t'avoue ne pas reussir a trouver d'exemple ou ca marcherais.

Je vais essayer d'être plus précis: je dispose de 2 entiers a et b (codés sur 32bits pour faire simple) et d'un algo f(x,y) qui réalise l'addition de deux entiers (sur 32 bits aussi). J'encrypte a et b en a' et b', et je "transforme" f(x,y) en f'(x,y). f'(a',b') donne un résultat c' que je sais transformer en un résultat c qui n'est autre que a+b.

En gros, la question ici est de savoir si il est possible de trouver le triplet suivant:
1. algo d'encryptage des données a et b
2. algo de transformation de mon algo d'addition f
3. algo de transformation du résultat retourné par f'

Le fait que cela débouche sur des données volumineuses et des fonctions f' couteuses (en nombre d'instructions et donc en temps de calcul comparé à celui de l'addition) est un problème secondaire.
Ce que je souhaite savoir, c'est si c'est possible et si ce n'est pas le cas: quelle est l'objection mathématique (en priant pour que je la comprenne ) ?

Merci.

[invitebe0cd90e]

En gros, ce que tu aimerais c'est un algorithme de cryptage qui "commute" à l'addition.

L'objection est celle que je donne dans mon precedent message, elle est simple et non mathématique : un des criteres pour qu'un algorithme de cryptage soit considéré comme bon, est justement que ce genre de choses ne soit pas possible.

Uatrement dit il est certainement possible de trouver des algos elementaires qui repondent a ton probleme, mais ils ne seront alors absolument pas sur.

Un algorithme de cryptage decoupe, melange et brasse dans tous les sens pour faire disparaitre au maximum toute regularité, pour s'approcher le plus possible d'un message aleatoire. Avoir un algo de cryptage tel que f(a+b)=g(f(a),f(b)) avec g une fonction "simple" est tout simplement contraire a cet objectif.

[A voir en vidéo sur Futura]

[invited37a86e7]

Un algorithme de cryptage decoupe, melange et brasse dans tous les sens pour faire disparaitre au maximum toute regularité, pour s'approcher le plus possible d'un message aleatoire. Avoir un algo de cryptage tel que f(a+b)=g(f(a),f(b)) avec g une fonction "simple" est tout simplement contraire a cet objectif.

En l'occurence, ce que je recherche c'est f, g et h tels que:
a+b = h(g(f(a), f(b))
ou f est mon algo d'encryptage des données, g mon addition et h l'algo qui me restitue le résultat.
Que f, g et h ne soient pas "simples" ce n'est pas un problème. J'aimerai savoir si, mathématiquement, je peux en trouver (une démonstration d'existence non constructive me satisferait).

Merci en tout cas pour ta réponse.

[invitebe0cd90e]

En l'occurence, ce que je recherche c'est f, g et h tels que:
a+b = h(g(f(a), f(b))
ou f est mon algo d'encryptage des données, g mon addition et h l'algo qui me restitue le résultat.
Que f, g et h ne soient pas "simples" ce n'est pas un problème. J'aimerai savoir si, mathématiquement, je peux en trouver (une démonstration d'existence non constructive me satisferait).

Merci en tout cas pour ta réponse.

Mouais, ca ne change rien, on etait sensé supposer que h etait la fonction qui decrypte....

Ca n'a pas de sens de demander s'il existe une fonction, n'importe laquelle qui marche... Il suffit de definir : "soit g la fonction qui a tout couple (f(a),f(b)) d'entier crypté associe f(a+b)"...(ou f est la fonction de chiffrement)

Cette fonction existe, ne serait ce que parce qu'il y a un nombre fini de cas, elle peut meme d'un point de vue theorique etre donnée explicitement... Mais ca n'avance pas beaucoup de dire ca !

J'ai pris soin de mettre le mot "simple" entre guillemets, donne lui le sens que tu veux, mais tu ne peux pas d'un coté parler de crypto et de l'autre dire que tu t'en fiches que les fonctions qui entrent en jeu soient simple ou constructible. La base meme de la crypto c'est qu'il existe des operations simples et d'autre compliquées ! Sinon ca ne sert a rien, si on va par la, il existe une fonction mathematique theorique mais constructible capable de decrypter n'importe quel message codé avec l'algo le plus performant sans connaitre la clé !

[Médiat]

Si la qualité de la cryptographie n'est pas un critère impératif, tu peux faire un truc très simple (je crois que cela remplit tous tes critères) :
Tu choisis deux nombres premiers (m et n proches l'un de l'autre) plus grands que les plus grands nombres que tu vas manipuler
tu poses f(a) = a*n [m] (c'est bien une bijection, il me semble)
f(a+b) = (a+b)*n [m] = a*n[m] + b*n[m]

Mais comme le dis jobhertz, c'est nul en qualité de cryptographie, donc si la question est théorique (est-ce que cela existe ?), la réponse est oui, si la question est pratique (il faut que le cryptage soit efficace), la réponse est celle de jobhetz.

[invite986312212]

s'il ne s'agit que de faire la somme de nombres, il y a une façon triviale de procéder: permuter les chiffres dans chaque nombre, à l'aide de la même permutation bien sûr.
La somme est invariante et on ne peut pas reconstruire les nombres sans connaître la permutation. Mais bon, ça ne marche que pour les sommes, je suppose que le problème est un peu plus sophistiqué quand-même.

[invite173dee73]

une démonstration d'existence toute bête dans R :
g = X (multiplication)
f = exp (fonction exponentielle népérien)
h = ln (logarithme népérien)

on a bien : a+b = h(g(f(a), f(b)))

[invitebe0cd90e]

une démonstration d'existence toute bête dans R :
g = X (multiplication)
f = exp (fonction exponentielle népérien)
h = ln (logarithme népérien)

on a bien : a+b = h(g(f(a), f(b)))

Je rappelle qu'on parle de cryptage, quand meme

[invite173dee73]

aujourd'hui en cryptage, l'analyse contribue autant que l'arithmetique ou la cuisine ! (ex : compression reversible, ..etc) .. ces fonction analytiques peuvent etre aprochée "suffisament" par des series entières presque finis(donc algorithmes)

[invite173dee73]

Je rappelle qu'on parle de cryptage, quand meme

jobhetz, j'ai mieux compris tes explications ! je réagissait surtout par rapport à la demande d’un exemple de construction, sachant évidemment que les contraintes imposées sortent du cadre général de la cryptographie.

[invitebe0cd90e]

Histoire de temperer quand meme : il existe un algorithme tres sur (en fait c'est meme le seul qui soit absolument inviolable) et tres simple en meme temps, qui justement ne recquiers pas de "melange" compliqué, et donc qui peut eventuellement commuter avec des operations elementaires au niveau du bit. Cet algorithme consiste simplement a representer les données a crypter en binaire, a choisir une clé aussi longue que le message en binaire egalement, et a faire une operation XOR entre les 2...

Reste qu'a mon avis ca ne "commute" pas avec grand chose non plus....