得知公钥，有办法再得出一对公钥一样的密钥吗？

188089942 · 发表于 2021-4-23 15:42:25

比如我现在手上有一个人家的公钥，可以有办法得出一个公钥一样，但私钥不一定要一样的一对密钥吗？

armku · 发表于 2021-4-23 15:46:45

您得长寿

memstone · 发表于 2021-4-23 15:51:05

如果你解决了这个问题，那所有的 SSL 网站，你全可以假冒了，完美实现中间人攻击。

yang855u · 发表于 2021-4-23 15:55:07

技术实现难度很大，市面上没人公开做得到

xjavr · 发表于 2021-4-23 16:06:18

看你公钥多长喽，如果256的rsa,可以嘿嘿，1024就不要想了，4096得量子才行。

188089942 · 发表于 2021-4-23 16:41:08

memstone 发表于 2021-4-23 15:51
如果你解决了这个问题，那所有的 SSL 网站，你全可以假冒了，完美实现中间人攻击。 ...

我就是这么想的，如果能实现，那我就可以做中间人了

brother_yan · 发表于 2021-4-23 17:18:54

那还叫加密了么，那是hash。至少对于rsa，一个公钥唯一对应一个私钥

lusson · 发表于 2021-4-23 17:23:57

找到了的话你就可以伪装了。

lulinchen · 发表于 2021-4-23 17:24:20

如果能做出来，区块链就成了你的提款机了

security · 发表于 2021-4-23 17:32:41

答案就是不行。

saccapanna · 发表于 2021-4-23 17:38:52

目前的算力，标准公钥算法，特别是 ECC 算法，知道公钥求解私钥基本不可能。

哪怕你提出一种快速的算法，都会牛B得不行！

albert_w · 发表于 2021-4-23 18:09:34

嘿嘿，想得美。上来就想降维打击

redroof · 发表于 2021-4-23 21:22:27

如果你做到了，整个SSL体系就完了。所以不用考虑这种不现实的问题。还不如想想哪天买彩票能中个大奖，这样的概率高的多

canspider · 发表于 2021-4-23 22:08:49

根据理论，公钥有且只有一个私钥与之对应
这玩意要能搞出来，所有银行的U盾，芯片卡全部失效

sh0568 · 发表于 2021-4-23 22:16:10

目前肯定不行，如果能做到的话，就破了PKI体系，绝对划时代，比山东大学王小云还牛。

Z11 · 发表于 2021-4-24 00:35:43

想的美。。。如果你实现了，请给坛友每人充30年的VIP++。请相信我，到时候这件事对你财富总额的影响绝对不会比你现在给我充5块钱话费的影响来得大。。。

sinc_mark · 发表于 2021-4-24 09:33:44

看到大家都说不行，我倒是想说一句：楼主，还没有人能够证明非对称加密算法一定是不可逆的，至少在将来还是有可能...

饭牛牛 · 发表于 2021-4-24 10:28:59

lulinchen 发表于 2021-4-23 17:24
如果能做出来，区块链就成了你的提款机了

不只是区块链，所有加与计算机相关的都得崩溃。

pcwhy · 发表于 2021-4-24 10:40:56

非对称加密之所以安全就在于已经有前辈通过数学证明了这么做最快的办法就只有穷举。

redroof · 发表于 2021-4-24 10:41:29

sinc_mark 发表于 2021-4-24 09:33
看到大家都说不行，我倒是想说一句：楼主，还没有人能够证明非对称加密算法一定是不可逆的，至少在将来还是 ...

哈哈，不止RSA，好像所有的加密算法，包括AES什么的，也都没证明过没有密码就一定只能穷举。万一将来发现一个快速破解的算法，理论上也不是不可能的。

redroof · 发表于 2021-4-24 10:42:56

pcwhy 发表于 2021-4-24 10:40
非对称加密之所以安全就在于已经有前辈通过数学证明了这么做最快的办法就只有穷举。 ...

可惜没有精确证明。在我记得的范围内。
如果有人能证明这一点，这个人肯定可以在计算机历史上留下一笔。

security · 发表于 2021-4-24 10:47:59

redroof 发表于 2021-4-24 10:42
可惜没有精确证明。在我记得的范围内。
如果有人能证明这一点，这个人肯定可以在计算机历史上留下一笔。 ...

那就等楼主了。

redroof · 发表于 2021-4-24 11:23:42

工程上就是这样。你发明一个加密算法，公开给全世界，大家都不能找岀破解的方法，那么这个算法就可以用了。但是目前没人能找岀破解，跟从理论上证明不可能有破解，是完全不同的。理论证明不可能有破解是非常非常难的，几乎没有什么实用的算法能做到。如果一个算法必须证明无法破解才能投入使用，那么大家就没得用了。

canspider · 发表于 2021-4-24 12:52:34

sinc_mark 发表于 2021-4-24 09:33
看到大家都说不行，我倒是想说一句：楼主，还没有人能够证明非对称加密算法一定是不可逆的，至少在将来还是 ...

没人说不可逆啊，1024位RSA目前逆向计算成本就很低了
破解只是逆向计算成本问题

redroof · 发表于 2021-4-24 13:22:19

canspider 发表于 2021-4-24 12:52
没人说不可逆啊，1024位RSA目前逆向计算成本就很低了
破解只是逆向计算成本问题 ...

破RSA1024的成本可不低，基本上是目前技术上有可行性的极限了。十年前RSA768花掉了几千CPU年的运算量，RSA1024需要的运算量还要多上千倍，也就是几百万CPU年。考虑到现在的CPU比十年前快很多倍，就算现在的几十万CPU年吧。这叫低吗？

pcwhy · 发表于 2021-4-24 14:41:04

redroof 发表于 2021-4-24 11:23
工程上就是这样。你发明一个加密算法，公开给全世界，大家都不能找岀破解的方法，那么这个算法就可以用了。 ...

好像不是你这么解释的，任何加密算法都需要证明，至少证明解开他的难度等同于解开某个当前无解的数学问题。基本框架现代密码学已经搭建好了，当然，不是易经密码或者达芬奇密码啊。

如果不需要证明，那么你会看到各种江湖骗子声称的宇宙最强加密算法满天乱飞。之前我们论坛还有个号称啥菜农的家伙，声称自己发明了宇宙最强加密算法还吊打AES、RSA，结果被人指出连CPA secure 都达不到。

RSA的Correctness证明其实很简单，知道点群论的基本定理就成，https://www.cse.cuhk.edu.hk/~tao ... notes/rsa-proof.pdf

redroof · 发表于 2021-4-24 18:00:54

本帖最后由 redroof 于 2021-4-24 18:07 编辑

pcwhy 发表于 2021-4-24 14:41
好像不是你这么解释的，任何加密算法都需要证明，至少证明解开他的难度等同于解开某个当前无解的数学问题 ...

我记得其实没有人精确证明过RSA完全等同于分解质因数，只是分解质因数是最直观的破解RSA的办法而已。没有人证明过不能用其它方法破解RSA。
并且分解质因数的快速算法也只是当前无解，同样没有人能证明，分解质因数这个操作保证不会有快速算法。
工程上就这样。证明不可能有快速破解算法，比找一个算法难太多倍了，都不是一个维度的。证明了这个算法不可能有任何快速破解，就永远的断了任何想破解它的人的后路。但这太难了。我记得没有任何一个实用的算法是可以从理论上证明无法破解的，除了一次一密。

pcwhy · 发表于 2021-4-24 23:57:32

redroof 发表于 2021-4-24 18:00
我记得其实没有人精确证明过RSA完全等同于分解质因数，只是分解质因数是最直观的破解RSA的办法而已。没有 ...

One-time pad其实还真就是最保险的，冷战时候好像苏联用的就是这东西，但可惜部分掩码被不小心重用，然后导致CIA破掉密文抓了一堆间谍，但也有很大一部分密文是永远也解不开的。因为苏联解体时候KGB把密码本都毁了。

qq78929709 · 发表于 2021-4-25 10:14:20

redroof 发表于 2021-4-24 18:00
我记得其实没有人精确证明过RSA完全等同于分解质因数，只是分解质因数是最直观的破解RSA的办法而已。没有 ...

因为只能证明某样东西“存在”，而不能证明某样东西“不存在”，正如你不可能证明你的身边不存在一个完全透明，无法感知的第六维幽灵在看着你。

gzhuli · 发表于 2021-4-25 10:27:18

其实可能性是有的，只要找出私钥存在哪里，找一队雇佣兵进去抢就好了。

redroof · 发表于 2021-4-25 10:52:05

qq78929709 发表于 2021-4-25 10:14
因为只能证明某样东西“存在”，而不能证明某样东西“不存在”，正如你不可能证明你的身边不存在一个完全 ...

不是的。某些算法确实可以被证明是绝对不可破解的。比如一次一密。证明方法好像也不难，因为一次一密这个条件太强了。
当然这种证明从原理上就是非常难的。证明某种东西不存在当然比证明存在要难。所以我记得没有其他任何算法能被证明这一点。

gzhuli · 发表于 2021-4-25 11:09:43

redroof 发表于 2021-4-25 10:52
不是的。某些算法确实可以被证明是绝对不可破解的。比如一次一密。证明方法好像也不难，因为一次一密这个 ...

一次一密称不上“算法”，一次一密的生成方式才是真正的算法，如果密码本是伪随机数生成的，则依然是有可能被破的。

qq78929709 · 发表于 2021-4-25 11:13:52

redroof 发表于 2021-4-25 10:52
不是的。某些算法确实可以被证明是绝对不可破解的。比如一次一密。证明方法好像也不难，因为一次一密这个 ...

因为存在不同的密码本，一次一密本质上密文与明文不是唯一的对应关系，无法验证当然就没有破解的说法。但非对称加密，公钥和密钥是存在对应关系的，也就是可以验证的，所以存在快速算法或被破解的可能。

brother_yan · 发表于 2021-4-25 11:17:00

qq78929709 发表于 2021-4-25 10:14
因为只能证明某样东西“存在”，而不能证明某样东西“不存在”，正如你不可能证明你的身边不存在一个完全 ...

奥卡姆剃刀理论了解一下～

qq78929709 · 发表于 2021-4-25 11:19:43

brother_yan 发表于 2021-4-25 11:17
奥卡姆剃刀理论了解一下～

愿闻其详

brother_yan · 发表于 2021-4-25 11:21:19

对rsa感兴趣的可以搜一搜CTF的rsa题，可以作为入门

redroof · 发表于 2021-4-25 11:39:17

gzhuli 发表于 2021-4-25 11:09
一次一密称不上“算法”，一次一密的生成方式才是真正的算法，如果密码本是伪随机数生成的，则依然是有可 ...

是的，那个证明就写在密码学的书里，就是如果一次一密的密码本保证是真随机数无法被预测的话，那么一次一密这种做法就保证是完全不可破的。前面的条件不能丢掉啊，条件就是这个密码本保证无法被预测。
这是唯一一个被证明能保证不可破的算法。带有一个非常强的条件。实际只有理论意义。

redroof · 发表于 2021-4-25 11:45:14

qq78929709 发表于 2021-4-25 11:13
因为存在不同的密码本，一次一密本质上密文与明文不是唯一的对应关系，无法验证当然就没有破解的说法。但 ...

这样强的条件，就是为什么一次一密可以被证明完全不可破解啊。想要完全不可破就得这么强的条件，强到看过书的人一想就知道这样确实是正确的，几乎是正确的废话。呵呵
别的有实际用途的算法，没有一个能被这样证明的。所以原则上总有一天有可能被人找到破解的办法。。。
但是这个世界还得用加密算法啊，RSA看起来很不错，几十年了也没有人能发明岀一个可以破解它的方法，所以就用着呗，不考虑理论上有一天它可能被破解

gzhuli · 发表于 2021-4-25 11:48:48

redroof 发表于 2021-4-25 11:39
是的，那个证明就写在密码学的书里，就是如果一次一密的密码本保证是真随机数无法被预测的话，那么一次一 ...

然而你同样无法证明你所采用的“真随机数”是不是真的无法预测。

redroof · 发表于 2021-4-25 11:54:19

gzhuli 发表于 2021-4-25 11:48
然而你同样无法证明你所采用的“真随机数”是不是真的无法预测。

不用证明啊，这是条件。
那个证明一次一密绝对有效的证明，规定的条件就是这个密码本自身是无法预测的。
这是数学问题，不是工程问题。
给定了密码本自身无法预测的条件，可以得出结论：一次一密保证无法破解。这是数学上无懈可击的。
就好像给定了真空里有一只球形的鸡，可以证明这一只鸡有某某特性。。。。。
至于条件在现实中能不能满足，与这个证明无关。

redroof · 发表于 2021-4-25 11:55:35

楼主去研究数学吧，希望将来有一天，人类的计算机算法书里面可以写上:
1977年，三个数学家R，S和A，发明了RSA算法，这是人类第一个广泛应用的公开密钥算法。
在XXXX年，楼主数学家xxx发明了XXXX快速分解质因数算法，破掉了RSA算法。

gzhuli · 发表于 2021-4-25 12:08:54

本帖最后由 gzhuli 于 2021-4-25 12:32 编辑

redroof 发表于 2021-4-25 11:54
不用证明啊，这是条件。
那个证明一次一密绝对有效的证明，规定的条件就是这个密码本自身是无法预测的。
...

问题就是你无法证明这个世界上存在绝对无法预测的事物，这不是纯数学理论，是物理问题。

就如你前面说将来可能出现质因素分解的快速算法，物理上你也无法排除将来可能出现时空回溯技术的可能性，你现在觉得不可预测的东西可能在下一秒就变成可预测的。

redroof · 发表于 2021-4-25 14:22:40

gzhuli 发表于 2021-4-25 12:08
问题就是你无法证明这个世界上存在绝对无法预测的事物，这不是纯数学理论，是物理问题。

就如你前面说将 ...

所以，数学的归数学，物理的归物理，工程的归工程。
大家一直使用的这些加密算法都只是工程上认为可靠的，不是有数学证明绝对不能破解的。
所以原则上楼主可能发明一个算法破掉RSA，只不过这个可能性比中彩票大奖票低的多而已。低到全世界都忽略这种可能性。

saccapanna · 发表于 2021-4-25 19:30:31

redroof 发表于 2021-4-25 11:54
不用证明啊，这是条件。
那个证明一次一密绝对有效的证明，规定的条件就是这个密码本自身是无法预测的。
...

一次性密码本身是安全，难点在于秘钥的交换上，秘钥的交换又会导入密码的加密问题。
公钥算法可以用于秘钥交换，但是难以避免中间人攻击。
RSA 算法，秘钥太长了，ECC小而强悍，比RSA好用得多。但有没有快速求解的算法，都没有数学上的严格证明。也许有人已经研究出快速求解算法了呢，只是因为特殊原因没有公布。目前还有其他更好的公钥算法吗？

redroof · 发表于 2021-4-25 20:40:39

saccapanna 发表于 2021-4-25 19:30
一次性密码本身是安全，难点在于秘钥的交换上，秘钥的交换又会导入密码的加密问题。
公钥算法可以用于秘 ...

没有更好的了。工程上就是这样，只能是有啥就用啥。现在通行的做法就是现在认为最好的。你认为它是矮子也只能在矮子里拔将军，哈哈。
至于说有人发现了破解算法但不公开，这个概率太低了，可以忽略。这可是名垂青史的事情啊，为什么不公开

188089942 · 发表于 2021-4-27 10:23:24

redroof 发表于 2021-4-25 20:40
没有更好的了。工程上就是这样，只能是有啥就用啥。现在通行的做法就是现在认为最好的。你认为它是矮子也 ...

如果真能破解，区块链就成取款机了

jjj · 发表于 2021-4-27 11:54:32

异想天开

PUPO · 发表于 2021-4-27 20:54:43

你这个问题最终还是等价于已知公钥求解私钥，如果是2048的话那是不可能的

得知公钥，有办法再得出一对公钥一样的密钥吗？

阿莫论坛20周年了！感谢大家的支持与爱护！！

浏览过的版块