用无理数加密，如何破解？
未邀自答。 竟然在知乎上刷出这么有意思的一个问题，很欣慰啊！但让我比较失落的是，已有的回答似乎都有些问题。出于讨论，也出于对这个问题的兴趣，我尝试回答一下，如有问题或者错误，还请各位大牛们指正~ 密码学是一个比较新的学科，但这个学科的奇妙之处在于它既符合计算机领域“脑洞大开”的特点，又符合数学领域“推理严谨”的特点。所以，下定结论之前还是要想明白，解释清楚。所以在回答问题之前，我想把已有答案中的一些问题指出来。我希望能多普及一些相关的知识，尽可能有理有据又比较直白的说明问题。如我指出的问题并不正确或者不严谨，还请讨论并指正。 ================================ 1 已有答案的一些问题 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @Xylitogum的答案： 这个地方有两个问题： 密码学中有两个主要领域：对称密码学（Symmetric Cryptography）和非对称密码学（Asymmetric Cryptography）。对称密码学中，加密/解密双方使用一个相同的密钥进行操作。非对称密码学中，加密/解密双方使用不同的密钥进行操作。题主所提出的加密算法属于对称密码学中的对称加密算法范畴。为什么？请看算法描述中的其中一句话： 对称加密算法中，密钥不能被公开，所以通信双方如何共享密钥是对称加密算法从根本上就无法解决的问题。但这并不意味着对称加密算法没有用途。对称加密算法加解密速度要比非对称加密算法快几个数量级。同时，对称加密算法中，明文空间可以看做{0, 1}^*（对于分组对称加密算法，是人为把明文空间分组，如果加上加密模式的话，也可以人为是{0, 1}^*，参见： ）。而非对称加密算法都有一个明文空间的限制。在实际中，双方可以使用速度较慢、明文空间有限制的非对称密码学进行密钥协商或者密钥传输，再利用速度较快、明文空间没有限制的对称密码学进行加密等操作。 此外，无论何种加解密算法，解密方都需要秘密地存储私钥。并且在解密时，解密方需要将私钥作为参数传入解密算法中。所以，如果我们认为程序的加密/解密运算在本地执行，可能获取整个程序的代码从而得到无理数（私钥），那么我们也可以认为对于所有加/解密算法，攻击者都可以获取整个程序的代码从而得到私钥。当然，这里要指出的是，题主的描述有一点瑕疵，使得我们可能会对题主提出的加解密有理解偏差，认为无理数、或者计算无理数的方法是加解密算法，而不是私钥。这一点我会在下面的答案中论述。 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 匿名用户的答案： 这个地方也有两个问题： 在题主的描述中，有这么一句话： 因此，题主的意思是，f(k)整个函数都作为私钥。 另外，即使密钥空间是k的空间大小，我们来看一下k的取值范围。从题主的描述： 因此，k的取值范围可以理解为实数。当然了，由于绝大多数无理数很难用多项式长度的公式来描述，这些无理数如果用做密钥的话，会导致密钥长度无法使用计算机描述，而导致算法的复杂度超过多项式级。因此，我们可以把k的取值范围限制为有理数比较科学。然而，这个范围依然很大，达到可以超过除了one time pad以外的所有加密算法的密钥空间长度。 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 的答案： 注意，题主的算法所涉及到的私钥长度可能会远远小于传递加密本的长度。题主算法的私钥是一个公式。这个公式的长度是多项式级的，甚至可能是常数级的。而如果使用one time pad的话，密码本长度要等于明文长度。如果明文长度较长，那么题主的算法就有意义了。 ================================ 2. 精确定义题主的算法 很多答案之所以有问题，根源在于题主对于算法的描述并不是很严谨，会导致理解上的歧义。所以在给出问题答案前，需要先精确定义题主的算法。 对于一个对称加密算法，只需要定义两个算法：加密算法和解密算法。还需要定义一个密钥空间。在此我不打算用数学语言描述，还是使用陈述的方法。 ================================ 3. 题主算法的安全性 这其实是一个安全的算法，而且算法的安全性达到了one time pad。为什么？首先要明确，很多答案中提到： 谈到一个算法的安全性，就必须要谈到这个算法的安全模型。也就是说，攻击者在具有什么能力的条件下，认为这个算法是安全的。举例来说，如果攻击者具有指数级复杂度的计算能力，那么现有算法都不是安全的。这个例子有些特殊，我想表明的是我们要限制攻击者的能力。 所谓理论上安全的one time pad算法，所有的pad只能使用一次，这样才能保证理论上安全。如果说用了两次以上就不安全，而断言题主的算法不安全，是不严谨的。因为我们可以要求题主的算法中，对于每一个明文，密钥对应的数学公式都是不同的。如果在这个条件下，题主的算法可以达到理论上安全。因为无理数本身是无限不循环小数，从概率上说我们可以认为无理数每一位的取值满足等概率分布，对于攻击者来说完全随机。这样一来，pad所用可以认为是随机数，这就保证了安全性。 ================================ 4. 题主算法的问题 既然题主提出的算法是安全的，那么这个算法有什么问题呢？题主算法根本的问题是：算法加解密速度是指数级的，这使得算法无法使用多项式计算能力的计算机实现。 为什么？我们考虑算法中这样的过程： 那么，计算这个无理数的复杂度是多少？这引出了一个本质问题：计算机如何计算一个无理数？现有计算机计算无理数的通用算法是牛顿迭代法等类似算法。这个算法不是一个确定算法，无法完全计算无理数，而是有近似范围。而且，计算的越精确，所需要的迭代次数越多。如果要求计算精确度达到完全精确，那么迭代次数是指数级的。我们计算根号2的前多少多少位很简单，再往后算呢？越来越复杂，计算时间指数级增加，最终会导致算法永远无法结束运行。 其实，这个问题在题主的描述中已经显露了： 如果已知密钥，算法计算结果与正确结果不同的概率是不可忽略的，那么会认为这个加解密算法是错误的。类似地，如果这个算法的时间复杂度是指数级，那么这个算法无法使用，也是错误的。而题主设计这个算法的根本问题就在这里。 这其实让我想起了有关格（Lattice）密码学上的一个梗。格密码学的一个大牛在一个分享报告中曾经提到： 为何格密码学，以及现在新提出来的全同态加密（Fully Homomorphic Encryption）等密码学算法没法用？根本上也是这个原因。 ================================ 那么，讨论到此为止。知乎密码学讨论群的各位，求点评啊！如有任何问题，欢迎留言讨论，我会随时修正答案，让答案更严谨。