密码学入门的一个小白问题
我们又在搞事了。 最近和几位老师吹牛讨论密码学小白研究生入门的培养问题。如何准备1000道小白问题帮助学生入门(别期待哈,我们计划退休的时候才弄好,而且没有答案)。 今天,我们发现一个看似简单的入门问题,收到的答案却是五花八门。放在这里,让大家围观下,感受下密码学的入门门槛。——小白劝退文呐。 各位道友,不可取笑以下的每一个答案哦。不然,我咒你每天出门忘记拉裤链,和卧报主编一样。每一个答案的背后都是一位道友的成长史,有人还在炼气期,而有人已筑基……
问题
:
如何从“对用户好,对敌人狠”解释: 敌人破解公钥对应的私钥时,我们要求其时间复杂度和公钥的长度呈指数级关系,而不是线性级或 多项式级的关系?
答案
:对用户好:计算的方式简单(相比多项式),从私钥得到公钥只需要很小的简单的输入(私钥),经过指数计算,就可以得到很大的复杂的结果(公钥)。用户在持有保存时开销少。 对敌人狠:计算困难(逆运算),从公钥破解获取私钥,是指数的逆运算,需要大量的运算尝试,计算很大的复杂的数,然后才能获得结果。敌人在持有保存时开销多。
答案
:在用户的角度,为了用户方便,产生私钥的过程应该是容易的,所花费的时间不多,是线性或者多项式级别的,即对用户好,而在敌人的角度,为了保护私钥不会被轻易泄露,破解公钥对应的私钥的过程是困难的,所花费的时间要超过敌人所能承受的极限,是指数级别的,即对敌人狠。
答案
:呈指数级关系,意味着敌人破解私钥的难度大,即“对敌人狠”,这样才能保证方案的安全性
答案
: 敌人破解公钥对应私钥是没有简单解法或者不存在,但对于用户获得私钥是简单的,具有单向性。
答案
:“对用户好,对敌人狠”就是用户可以方便地使用公钥和私钥进行加解密,而敌人则需要花费大量的时间和计算资源去攻破私钥。因此,敌人破解公钥对应的私钥时要求时间复杂度和公钥的长度呈指数级关系,而不是线性级或多项式级的关系。这样的话,随着公钥长度的增加,敌人所需的计算量就会呈现爆炸性地增长,攻破私钥的难度也就大幅增加。
答案
: 首先一个用户是否恶意的判别是,这个用户是否遵守算法规则,不遵守规则的用户就应定义为恶意用户,也可直接定义为敌手,那么我们去构造一个算法的时候就应该考虑到恶意敌手的存在,那么此算法就应该能抵御敌手的任何形式的攻击。 以敌手根据正常用户的公钥计算对应私钥这类攻击为例: 首先我们要清楚,我们避免不了任何一个用户都成为敌手的可能,因此,应该可以说是,对任何不怀好意的人来说,仅仅由公钥计算私钥必须是困难的,这样才能保证算法的安全性。 然后,对于敌手由公钥计算私钥的困难程度来说,指数级时间复杂度是最耗时的,而除此之外的时间复杂度对敌手来说,可以在相比较之下较短的时间内算出私钥。 因此,对于由公钥推出私钥来说,这对用户是友好的,因为用户有自己私钥,对敌手是提防的,提防的手段就是使敌手由公钥计算私钥的时间复杂度为指数级。
答案
: 对用户好,对敌人狠,直白的理解就是,敌人很难从公钥计算出私钥。它的要求是:随着公钥长度的增加,从公钥求解出私钥的时间复杂度是指数级的,其难度高于线性或者多项式。
答案
:”对用户好“是指方案在计算、通信、存储等方面的开销较小 ”对敌人狠“是指敌人攻破方案的难度较大,即方案的安全性较高。通常认为敌人攻破方案的时间复杂度与公钥的长度呈指数级关系时,难度较大,而呈线性级或多项式级的关系时,难度较小。因此,为了保证”对敌人狠“,要求其攻破方案的时间复杂度和公钥的长度呈指数级关系
答案
:离散对数不就是这样吗?已知g^x,求x, 没有办法,只能穷举。复杂度就是与群元素长度的指数?
答案
: 没有Google,直觉上我是这么理解的。因为理论上公钥长度越长越安全,但是同时带来的问题是,公钥越长,通信代价越高。所以我们需要增加公钥长度时,敌人破解的难度指数增加。这样一样,“对用户好,对敌人狠”。
答案
:因为如果敌人破解私钥所需要的时间复杂度和公钥的长度成线性级或 多项式级的关系的话,那么为了保证私钥的安全,公钥长度就要设置的特别长,这样显然对用户不友好。而且,我们也很难利用敌人破解私钥来解决数学困难问题,这也方便了敌人,对敌人“不够狠”。 站在实际应用的角度,公钥的长度是有限的,如果攻破私钥的时间复杂度与公钥长度的线性或多项式关系,那么为了为了保证私钥的安全,公钥长度可能就得呈指数级增长,这样显然对用户不友好。 站在安全归约的角度,我们将一个密码学方案归约到某个问题上,通常是为了证明破解该方案不比解决该问题简单。而在实际的方案设计中,大多数方案都会将都会将底层困难假设嵌入在由公钥计算私钥中。 在归约时,simulator希望能够利用敌手对方案的攻击来获取困难问题的解,也就是说,simulator希望利用一个拥有无限计算力的敌手来破解一个自己无法解决的问题。如果破解公钥对应的私钥仅仅呈线性级或多项式级的关系的话,那么就意味着,该方案所依赖的底层困难问题可以通过增加有限计算资源的方式让simulator自己解决,从而浪费了利用敌手的机会,对敌手来说不够狠。