如何证明密码方案不可构造？
我意识到这个问题可能与编程无关，并且由于这个想法的直观逻辑错误，许多人听起来像是一个愚蠢的问题。
我的问题是：是否可以证明不可能构造一个可以在不向解密方暴露解密密钥的情况下解密加密数据的加密方案（可以用图灵完备的编程语言实现）？
当然，我可以看到这种方案的直观逻辑错误，但正如形式逻辑和数学中经常出现的那样，在假设这样的陈述之前必须构建形式证明。这样的证明是否存在，或者可以很容易地构造出来吗？
感谢您对此的建议！
编辑：感谢大家对本次讨论提出的宝贵意见！
I realize this question might not be that programming related, and that it by many will sound like a silly question due to the intuitive logical fault of this idéa.
My question is: is it provable impossible to construct a cryptographic scheme (implementable with a turing-complete programming language) where the encrypted data can be decrypted, without exposing a decryption key to the decrypting party?
Of course, I can see the intuitive logical fault to such a scheme, but as so often with formal logic and math, a formal proof have to be constructed before assuming such a statement. Is such a proof present, or can it easely be constructed?
Thank you for advice on this one!
Edit: Thank you all for valuable input to this discussion!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
是的！！！这已经存在，被称为零知识协议和零知识证明。
请参阅 http://en.wikipedia.org/wiki/Zero-knowledge_proof
但是，你必须有很好的数学和加密背景才能理解它的工作方式和原因。
零知识协议的一个例子是 Schnorr 的 ZK 协议
YES!!! This already exists and are called zero knowledge protocols and zero knowledge proofs.
See http://en.wikipedia.org/wiki/Zero-knowledge_proof
However, you have to have a quite a good background in mathematics and crypto to understand the way it works and why it works.
One example of a zero knowledge protocol is Schnorr's ZK protocol
不;但我不确定你在问你想问什么。
显然，任何解密某些内容（即使用解密密钥）的人都必须拥有该密钥，否则他们就无法解密它。
你是在问RSA，它有不同的解密和加密密钥吗？或者您是否在询问一个系统，根据您使用的密钥，您可能会得到不同的（有效）结果？
No; but I'm not sure you're asking what you want to be asking.
Obviously any person who is decrypting something (i.e. using a decryption key) must, obviously, have the key, otherwise they aren't decrypting it.
Are you asking about RSA, which has different keys for decrypting and encrypting? Or are you asking about a system where you may get a different (valid) result, based on the key you use?
如果“解密”只是指以某种方式获得明文，那么当然可以创建这样的加密方案。事实上它已经存在：
采用非对称加密方案，例如：RSA，您拥有公钥但没有私钥。现在我们收到一条使用公钥加密的消息（因此需要私钥来解密它）。我们可以通过“强力”（是的，在合理的密钥/块大小的情况下，这将花费非常长的时间）来获取原始消息，遍历所有可能的候选者并自己对其进行加密，直到获得相同的加密文本。一旦我们获得相同的加密文本，我们就知道解密的文本是什么，而无需发现私钥。
If by "decrypted" you just mean arrive at the clear text in some way, then it is certainly possible to create such a cryptographic scheme. In fact it already exists:
Take an asymmetric encryption scheme, eg: RSA where you have the public key but not the private key. Now we get a message that's been encrypted with the public key (and therefore needs the private key to decrypt it). We can get the original message by "brute force" (yes, this'll take an enormously long time given a reasonable key/block size) going through all possible candidates and encrypting them ourselves until we get the same encrypted text. Once we get the same encrypted text we know what the decrypted text would be without ever having discovered the private key.
是的。
证明：加密可以被认为是一个黑匣子，因此你得到一个输入和一个输出，并且你不知道黑匣子如何转换输入以获得输出。
要对黑匣子进行逆向工程，您“简单地”需要枚举所有可能的图灵机，直到其中一台确实产生与您寻求的结果相同的结果。
当您想要反转加密时，这同样适用。
诚然，这将花费比宇宙可能存在的时间更多的时间，但算法在时间耗尽之前找到匹配项并非不可能。
在实践中，问题是如何有效地找到解码输出的密钥。这是一个小得多的问题（因为您已经知道算法）。
Yes.
Proof: Encryption can be considered as a black box, so you get an input and an output and you have no idea how the black box transforms the input to get the output.
To reverse engineer the black box, you "simply" need to enumerate all possible Turing machines until one of them does produce the same result as the one you seek.
The same applies when you want to reverse the encryption.
Granted, this will take much more time than the universe will probably live, but it's not impossible that the algorithm will find a match before time runs out.
In practice, the question is how to efficiently find the key that will decode the output. This is a much smaller problem (since you already know the algorithm).
这就是所谓的编码。
但每个拥有编码算法的人都可以“解密”该消息。这是无密钥加密的唯一方法。
It's called encoding.
But everyone with the encoding algorithm can "decrypt" the message. This is the only way of keyless encryption.