Comment prouver un schéma cryptographique inconstructible?

Je me rends compte que cette question n'est peut-être pas liée à la programmation, et que cela paraîtra beaucoup comme une question idiote à cause de la faute logique intuitive de cette idéa. Ma question est: est-il prouvé impossible de construire un schéma cryptographique (implémentable avec un langage de programmation complet) où les données cryptées peuvent être décryptées, sans exposer une clé de décryptage à la partie de décryptage?Comment prouver un schéma cryptographique inconstructible?

Bien sûr, je peux voir la faute logique intuitive à un tel schéma, mais comme souvent avec la logique formelle et les mathématiques, une preuve formelle doit être construite avant d'assumer une telle déclaration. Une telle preuve est-elle présente ou peut-elle être facilement construite?

Merci pour votre avis sur celui-ci!

Éditer: Merci à tous pour votre contribution à cette discussion!

Source

2009-10-14 Tomas Vinter

Demandez-vous "comment une partie peut-elle déchiffrer un message sans toutes les pièces nécessaires pour le faire"? Si quelqu'un n'a pas la clé, il ne devrait pas être en mesure de décrypter le texte chiffré [pendant un certain temps, où "un peu de temps" est de préférence "plus long que l'espérance de vie de l'univers"]. – Piskvor

Je ne parle pas d'un schéma cryptographique existant comme RSA asymétrique ou AES symétrique. Comme vous le dites, pour déchiffrer des données, une clé doit évidemment être présente. Mais est-il prouvé qu'il est impossible de construire un nouveau schéma cryptographique où une clé n'aurait pas besoin d'être présente pour le décryptage? Je suis sûr que c'est le cas, mais je n'ai pas trouvé une telle preuve. –

Propre: Un tel cas serait un schéma de "chiffrement" qui aboutit à ce que le "texte chiffré" soit égal au "texte en clair". Bien que je ne vois pas vraiment comment vous pourriez envisager ce cryptage. En ce qui me concerne, votre réponse ne réside pas dans les preuves, mais dans la définition des termes. –

OUI !!! Cela existe déjà et sont appelés des protocoles de connaissance zéro et des preuves de connaissance zéro.

Voir http://en.wikipedia.org/wiki/Zero-knowledge_proof

Cependant, vous devez avoir une assez bonne base en mathématiques et Crypto pour comprendre la façon dont il fonctionne et pourquoi cela fonctionne.

Un exemple d'un zéro protocole de connaissance est le protocole ZK de Schnorr

Source

2009-10-14 08:51:01 Henri

caveat: "Les preuves de connaissance zéro ne sont pas des preuves dans le sens mathématique du terme, car il est une petite probabilité, l'erreur de validité, qu'un prouveur trompeur puisse convaincre le vérificateur d'une fausse déclaration, en d'autres termes, ils sont probabilistes plutôt que déterministes, mais il existe des techniques pour réduire l'erreur d'acceptabilité à des valeurs négligeables. " – Piskvor

IMHO c'est autre chose; mais si ça aide l'OP, tant mieux :) –

@siliy, ouais ... on obtient un peu trop de backfeed du côté downvote. Je suis sûr que vous avez aidé op, nous pourrions également mentionner les keystores, mais il n'y a pas de solution globale pour l'op. Ce n'est pas ce que demande l'op. (Remarquez les gens, j'ai dit légèrement) Si ce n'est pas ce que vous avez demandé (quelque chose d'autre), puis-je suggérer la seule chose que je peux penser est qu'il n'y a pas de solution finale à la gestion des clés? confiance. –

Non; mais je ne suis pas sûr que vous demandiez ce que vous voulez demander. Il est évident que toute personne qui déchiffre quelque chose (c'est-à-dire en utilisant une clé de déchiffrement) doit évidemment avoir la clé, sinon elle ne la décrypte pas.

Demandez-vous à propos de RSA, qui a différentes clés pour le décryptage et le cryptage? Ou demandez-vous un système où vous obtiendrez un résultat différent (valide), basé sur la clé que vous utilisez?

Source

2009-10-14 08:38:49

"résultat différent (valide), basé sur la clé que vous utilisez" Je suis sûr que j'ai vu quelque chose comme ça avec des pads uniques; ceux-ci ont cependant leur propre série de problèmes (notamment qu'ils sont des blocs de temps, ainsi que la longueur et la distribution des clés). – Piskvor

Piskvor: Exactement, OTP est incassable, car essentiellement la clé * est * le texte en résultant: P –

Oui. Preuve: Le chiffrement peut être considéré comme une boîte noire, donc vous obtenez une entrée et une sortie et vous n'avez aucune idée de comment la boîte noire transforme l'entrée pour obtenir la sortie. Pour effectuer une rétro-ingénierie de la boîte noire, vous devez "simplement" énumérer toutes les machines de Turing possibles jusqu'à ce que l'une d'entre elles produise le même résultat que celui que vous recherchez.

La même chose s'applique lorsque vous voulez inverser le cryptage. Accordé, cela prendra beaucoup plus de temps que l'univers vivra probablement, mais il n'est pas impossible que l'algorithme trouve une correspondance avant la fin du temps imparti. En pratique, la question est de savoir comment trouver efficacement la clé qui va décoder la sortie. C'est un problème beaucoup plus petit (puisque vous connaissez déjà l'algorithme).

Source

2009-10-14 08:40:42

Non, vous avez tort, car sans la clé (ou le texte en clair) vous ne pouvez pas déterminer si le résultat obtenu est valide. –

Qu'elle produise le 'même résultat' pour une sortie donnée ne signifie pas que c'est la même machine. Je suis à peu près sûr qu'il est en général indécidable que 2 machines de Turing fassent la même chose. – Greg

@silky: cela est laissé comme un exercice au lecteur;) – Piskvor

Si par « déchiffré » que vous venez de dire arriver au clair d'une certaine manière, il est certainement possible de créer un tel système cryptographique. En fait, il existe déjà:

Prendre un schéma de chiffrement asymétrique, par exemple: RSA où vous avez la clé publique mais pas la clé privée.Nous obtenons maintenant un message crypté avec la clé publique (et donc besoin de la clé privée pour le déchiffrer). Nous pouvons obtenir le message original par «force brute» (oui, cela prendra énormément de temps étant donné une taille de clé/bloc raisonnable) en passant par tous les candidats possibles et en les chiffrant nous-mêmes jusqu'à obtenir le même texte crypté. Une fois que nous obtenons le même texte crypté, nous savons ce que serait le texte déchiffré sans jamais avoir découvert la clé privée.

Source

2009-10-14 09:00:31

C'est ce qu'on appelle l'encodage. Mais tout le monde avec l'algorithme de codage peut "déchiffrer" le message. C'est le seul moyen de cryptage sans clé.

Source

2011-09-15 07:38:04 Yigit

Comment prouver un schéma cryptographique inconstructible?

Répondre

Questions connexes