Bonjour à tous !
Un petit journal pour parler d'un sujet du domaine de la cryptographie qui me tient à coeur mais qui est encore méconnu du public : le chiffrement homomorphe.
Piqûre de rappel
Dans ce journal je parlerai de cryptosystème asymétrique.
Chaque interlocuteur au sein d'un de ces cryptosystème possède deux clés :
- Une clé publique, qu'il peut distribuer librement, sans risque. Les autres interlocuteurs du réseau peuvent, grâce à cette clé :
- Chiffrer des messages à destination de l'interlocuteur original
- Une clé privée, qu'il doit conserver jalousement. Il peut :
- Déchiffrer les messages que les autres interlocuteurs lui ont envoyé avec sa clé publique
Le cryptosystème asymétrique le plus connu est très probablement RSA, même s'il va être amené à disparaître dans les années à venir par des cryptosystèmes basés sur les courbes elliptiques (ECDSA / ECDHE).
Le chiffrement homomorphe, c'est quoi ?
C'est une particularité qui peut s'appliquer à certains cryptosystèmes asymétriques, et qui permet à un tier qui possède votre clé publique de faire des calculs arbitraires (addition et/ou multiplication) sur des messages préalablement chiffrés.
Il obtient en résultat de ces calculs de nouveaux messages, qui sont les résultats chiffrés des opérations.
Puisque je me suis probablement mal exprimé, voici un exemple pour illustrer tout ça :
Mettons Alice, qui possède deux nombres, 5 et 6. Elle aimerait connaître leur produit, mais ne possède pas la puissance de calcul nécessaire.
Elle pourrait donner ces deux nombres à un supercalculateur, mais voilà : ce sont des informations capitales qui peuvent lui coûter beaucoup d'argent si un attaquant met la main dessus.
La solution : le chiffrement homomorphe. Alice chiffre 5 et 6 avec sa clé publique, ce qui donne (par exemple) 48657 et 1248652.
Elle transmet ces deux nombres ainsi que sa clé publique à un datacenter. Ce dernier calcule le produit homomorphe de 48657 et 1248652, ce qui donne 84357.
Il transmet 84357 à Alice, qui le déchiffre avec sa clé privée : 30 !
Dans ce cas, on voit bien que le datacenter a fait une opération sur deux nombres qui n'avaient pour lui aucune signification, a produit un résultat dont il n'a rien pu faire, mais pourtant cela sert bien notre pauvre Alice :) .
Quels usages ?
A part dans l'exemple ci-dessus où j'ai montré que le chiffrement homomorphe pouvait être utile pour déléguer des traitements complexes à des datacenters à qui l'on ne fait pas confiance, le chiffrement homomorphe peut également servir dans le cas du vote électronique.
En effet, chaque vote peut être chiffré séparément, la somme des votes est calculée de façon homomorphe sur les votes chiffrés, et quelques autorités de confiance qui se partagent la clé privée se réunissent une unique fois pour déchiffrer la somme obtenue.
Bien entendu, beaucoup d'autres vérifications sont utilisées pour prouver la validité des votes et le chiffrement homomorphe ne constitue qu'une partie du protocole de vote électronique.
Où en est-on maintenant ?
Le problème avec les cryptosystèmes asymétriques actuels (RSA, ElGamal, etc.), c'est qu'ils ne sont que partiellement homomorphes. En d'autres termes, ils ne supportent qu'une seule opération : addition ou bien multiplication.
Or, il y a ce bon vieux théorème en informatique qui dit que si l'on veut pouvoir faire tout type de calcul, il faut pouvoir faire les deux.
C'est alors qu'intervient en 2009 Craig Gentry, de l'université de Stanford. Sa thèse est la toute première représentation théorique d'un cryptosystème complètement homomorphe, fondé sur la cryptographie à base de réseaux euclidiens (exit donc le problème de factorisation des nombres avec RSA ou encore le logarithme discret avec ElGamal).
En plus, la cryptographie à base de réseaux euclidiens a la particularité d'être résistante aux ordinateurs quantiques. Formidable non ?
Oui mais voilà, dans la pratique, cela donne des clés gigantesques (plusieurs méga-octets, alors qu'une clé RSA ne pèse qu'entre 128 et 512 octets), et les calculs (addition et multiplications) peuvent être jusqu'à 1000x plus lents que les opérations non-homomorphes.
Depuis sa première publication, Gentry et des chercheurs du monde entier cherchent alors à améliorer l'efficacité du cryptosystème, et font de bonnes avancées chaque année => Optimisation des temps de calcul et réduction de la taille des clés.
On reste encore loin d'une solution efficace malgré tout.
Le chiffrement homomorphe est l'un des sujet bouillant de la cryptographie moderne, et on espère qu'il sera possible d'ici quelques années de l'utiliser en pratique.
Quelques liens
- Le chiffrement Homomorphe (Wikipédia EN)
- L'implémentation actuelle du cryptosystème de Gentry (Github)
- La cryptographie à base de réseaux euclidiens (Wikipédia EN)
# contresens
Posté par Philip Marlowe . Évalué à 3.
s/très peu méconnu/très peu connu/
[^] # Re: contresens
Posté par Ely . Évalué à 3.
Merci pour la remarque, mais je ne trouve pas comment éditer mon journal.. Faut-il attendre les pouvoirs d'un modérateur ? :>
[^] # Re: contresens
Posté par Benoît Sibaud (site web personnel) . Évalué à 3.
Corrigé.
[^] # Re: contresens
Posté par ǝpɐןƃu∀ nǝıɥʇʇɐW-ǝɹɹǝıԀ (site web personnel) . Évalué à 2.
s/très peu connu/méconnu/
« IRAFURORBREVISESTANIMUMREGEQUINISIPARETIMPERAT » — Odes — Horace
# Une dépêche!
Posté par ʭ ☯ . Évalué à 10.
Vite, une dépêche pour ce journal simple, ludique et informatif! En plus ça dénonce les chiffrements homophobes du SSH actuel…
⚓ À g'Auch TOUTE! http://afdgauch.online.fr
[^] # Re: Une dépêche!
Posté par claudex . Évalué à 5.
Et voilà !
« Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche
[^] # Re: Une dépêche!
Posté par Ely . Évalué à 3.
Et bien, je ne m'attendais pas à cela ! Merci. Cependant, es-tu sûr que mon journal ne sort pas trop du cadre habituel des dépêches linuxfr ?
Je veux dire, généralement on parle de release de logiciels ou de news dans le monde du libre, pas vraiment de sujets retranchés comme celui-ci..!
[^] # Re: Une dépêche!
Posté par claudex . Évalué à 10.
On n'en parle pas parce que personne ne publie sur le sujet mais c'est tout à fait dans la ligne éditorial. Et en tant que lecteur et modérateur, ça m'intéresse.
« Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche
[^] # Re: Une dépêche!
Posté par ʭ ☯ . Évalué à 4.
Du coup, tu auras compris que tu peux continuer de nous tenir informés ;-)
⚓ À g'Auch TOUTE! http://afdgauch.online.fr
# Ordinateurs quantiques
Posté par erdnaxeli (site web personnel) . Évalué à 2. Dernière modification le 13 janvier 2014 à 14:53.
Je dérive un peu du sujet initial pour rebondir sur cette phrase.
Qu'en est-il de la cryptographie actuelle (AES, RSA, SHA-X, …) face aux ordinateurs quantiques ? D'après cette phrase, j'en déduis que ça ne résiste pas bien.
Il existe deux catégories de gens : ceux qui divisent les gens en deux catégories et les autres.
[^] # Re: Ordinateurs quantiques
Posté par Ely . Évalué à 2.
Salut. Tout n'est pas menacé, heureusement. En fait, seulement les cryptosystèmes asymétriques (même basés sur les courbes elliptiques) le sont : RSA, ElGamal, ECDSA, ECDHE. Ils dépendent de problèmes mathématiques comme la factorisation en nombres premiers ou le logarithme discret qui deviennent faibles face à un ordinateur quantique.
Tout ce qui est cryptographie symétrique (AES..) et fonctions de Hash (SHA-X) ne sont pas menacés car ne dépendent pas de problèmes mathématiques.
[^] # Re: Ordinateurs quantiques
Posté par Renault (site web personnel) . Évalué à 5.
Notons que les ordinateurs quantiques sont très loin d'être capables de déchiffrer sur RSA.
L'algorithme est au point, mais ces bêtes en sont pas assez stables (et on ignore si elles le seront assez pour être économiquement viables même pour de grandes organisations).
[^] # Re: Ordinateurs quantiques
Posté par Ely . Évalué à 5.
Oui, pour le moment on casse du RSA 8 bits, c'est-à-dire qu'un ordinateur quantique a factorisé 15 en 3x5.. wouhou.
RSA a encore de beaux jours devant lui, mais avoir de nouveaux cryptosystèmes d'ici 20 ans serait déjà un premier pas :) .
# électron, piège à ...
Posté par Professeur Méphisto . Évalué à 6.
ce chiffrement ne change rien au problème de la confiance nécessaire en une autorité (qui ? pourquoi celle là ?) et de l'impossibilité du contrôle citoyen de l'élection (Mme Michu peut surveiller/participer au dépouillement)
où me trompe-je ?
[^] # Re: électron, piège à ...
Posté par Ely . Évalué à 2.
Dans le cas du vote électronique, la clé privée est découpée entre plusieurs autorités de confiance. La force de cette méthode, c'est qu'il n'en faut qu'une seule qui soit honnête pour que tout le système soit fiable.
Après si tu tombes sur un cas où toutes les autorités de confiance choisies sont corrompues, c'est que le choix a été mal fait dès le départ. Si un jour le vote électronique arrive, le choix de ces autorités sera l'une des étapes les plus importantes. La façon de choisir aussi..
[^] # Re: électron, piège à ...
Posté par patrick_g (site web personnel) . Évalué à 10.
Cela ne réponds pas à l'objection de la compréhension du système par tous les citoyens.
N'importe qui peut comprendre le vote papier. On met les papiers dans les urnes et à la fin on compte qui en a le plus.
Seule une infime minorité d'électeurs peut comprendre le vote électronique avec toutes les problématiques associées (code source/code compilé, hardware de confiance, clé crypto, etc).
La démocratie doit être compréhensible par tous !
[^] # Re: électron, piège à ...
Posté par Ely . Évalué à 3.
Bien évidemment. La prouesse technique du vote électronique m'intéresse, après socialement il est clair qu'on est très loin d'accepter cela.
Cependant, on a aussi très souvent relevé des cas de triches avec le vote papier. Car on a beau compter et faire une somme juste à un bureau local de vote, rien ne garantit que ça ne sera pas altéré dans les niveaux supérieurs..!
[^] # Re: électron, piège à ...
Posté par lolop (site web personnel) . Évalué à 3.
Tous les résultats sont publics (sauf le vote du bureau du Sénat :-). Les partis font remonter les résultats locaux et font leurs calculs eux aussi en parallèle. Une triche au niveau supérieur serait détectée.
Votez les 30 juin et 7 juillet, en connaissance de cause. http://www.pointal.net/VotesDeputesRN
[^] # Re: électron, piège à ...
Posté par Professeur Méphisto . Évalué à 9.
c'est ça la grandeur de la démocratie : la triche est à la portée de tous les citoyens, indépendamment de leurs compétences techniques.
[^] # Re: électron, piège à ...
Posté par Sygne (site web personnel) . Évalué à 2.
Lapin compris non plus…
D'accord, la machine crache des données chiffrées, et puisque la clé est partagée, il faut être plusieurs pour les déchiffrer. Mais on s'en fout un peu: qui nous dit que la machine reçoit les bonnes données, qui nous dit qu'elle n'ajoute pas des votes (la clé de chiffrement est justement publique), qui nous dit qu'elle calcule bien, qui nous dit que l'algorithme utilisé est effectivement homomorphe…
Amhà, le chiffrement ne fait qu'ajouter une boite noire à une boite noire.
[^] # Re: électron, piège à ...
Posté par Ely . Évalué à 2.
Comme les votes sont chiffrés, tu peux les lier dans une base de données avec des informations nominatives sur leur propriétaire, sans risque de briser l'anonymat du vote bien sûr. Tout ce que ça te permet de savoir, c'est qui a voté et qui n'a pas voté, ce que l'on sait déjà avec les listes..
Ca te permet aussi d'être sûr que seuls des personnes autorisées ont voté.
La seule difficulté, c'est que normalement un vote électronique, c'est un "1" chiffré pour celui pour qui on vote, et des "0" chiffrés pour les autres. Ensuite, on fait la somme homomorphe.
Bien sûr, je te laisse pas imaginer si quelqu'un arrive à voter "99999" chiffré.. Il existe des solutions qui permettent de s'assurer qu'on vote bien 0 ou 1 et pas autre chose, mais là on sort de mes connaissances sur le sujet..!
[^] # ok, mais pas mal d'autres questions…
Posté par bobo38 . Évalué à 3.
Là je comprends mieux l'intérêt de l'homomorphie… du coup pour faire du +1 et du +0 pas besoin de gérer la multiplication.
Mais ça reste bizarre, parce que tous les votes chiffrés le sont avec des clefs différentes, du coup pour faire la somme ça me parait chaud. Ou alors j'ai loupé un truc : c'est peut-être dans le « plusieurs autorités de confiance » que ça se joue.
Sinon une grosse interrogation sur la sécurité. Le format de l'info étant assez simple : un « 1 » parmi n-1 « 0 », et connu, le déchiffrement sauvage peut être facilité, non ?
[^] # Re: électron, piège à ...
Posté par Sygne (site web personnel) . Évalué à 4.
Lier un nom à un vote, c'est tout de même une idée naïve (pour ne pas dire autre chose). Toutes les garanties institutionnelles ou techniques n'atteindront jamais la cheville de la meilleure des garanties qui consiste à ne jamais lier ces informations.
Ça me semble encore plus dangereux s'il s'agit de faire des sommes homomorphes de ces données: on chiffre soit un 0, soit un 1, et comme il n'y a normalement qu'un 1 parmi plusieurs 0 dans la table, on a vite fait, sans même avoir à déchiffrer le vote, de savoir pour qui untel a voté.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.