×

Loading...
Ad by
  • 最优利率和cashback可以申请特批,好信用好收入offer更好。请点链接扫码加微信咨询,Scotiabank -- Nick Zhang 6478812600。
Ad by
  • 最优利率和cashback可以申请特批,好信用好收入offer更好。请点链接扫码加微信咨询,Scotiabank -- Nick Zhang 6478812600。

Carmichael函数在计算机密码学上的应用,各个大学cryptography课程必教

Carmichael函数是这样一个定义的函数 phi(n)=所有小于n且和n互质的数的数量,举个糖炒栗子: phi(6)=2 因为只有1,5 <6且和6互质。明眼人就可以看出来了,如果phi(p) p是个质数,那么显然phi(p)=p-1,因为肯定是从1数到p-1都是和p互质的。

好了,那么现在一个关键的问题,phi(pq) ,在 p,q都是质数是怎么样的形式?

肯定也是要数出所有和pq互质的数,那么怎么数?

我们假设 x是一个和pq互质的,那么显然 gcd(x,pq)=1, 因为p,q都是质数,那么显然根据中国剩余定理在循环群Z/q 和Z/p上可以形成群积同构,并且同构于循环群Z/pq。 则显然,根据中国剩余定理,必然存在一个且仅有一个l=x mod p,和仅有一个m =x mod q, 而l, m则显然是属于在phi(p) phi (q)里被数过的数字,这个是根据中国剩余定理的1-1对应可以确定。那么显然,所有像 x这样的数字的数量,必然会是phi(p)的倍数,也会是phi(q)的倍数,且是最小倍数值(否则越界到 1=mod p ,1=mod q里去了)

则显然 phi(pq)=lcm (phi(p),phi (q)) 又因为p, q都是质数,则显然

phi(pq)=lcm (p-1,q-1)

上面这个结论必须牢记,因为下一步的密钥生成就是要根据上面的这个结论来做的。

Sign in and Reply Report

Replies, comments and Discussions:

  • 工作学习 / 学科技术 / Carmichael函数在计算机密码学上的应用,各个大学cryptography课程必教 +6

    Carmichael函数是这样一个定义的函数 phi(n)=所有小于n且和n互质的数的数量,举个糖炒栗子: phi(6)=2 因为只有1,5 <6且和6互质。明眼人就可以看出来了,如果phi(p) p是个质数,那么显然phi(p)=p-1,因为肯定是从1数到p-1都是和p互质的。

    好了,那么现在一个关键的问题,phi(pq) ,在 p,q都是质数是怎么样的形式?

    肯定也是要数出所有和pq互质的数,那么怎么数?

    我们假设 x是一个和pq互质的,那么显然 gcd(x,pq)=1, 因为p,q都是质数,那么显然根据中国剩余定理在循环群Z/q 和Z/p上可以形成群积同构,并且同构于循环群Z/pq。 则显然,根据中国剩余定理,必然存在一个且仅有一个l=x mod p,和仅有一个m =x mod q, 而l, m则显然是属于在phi(p) phi (q)里被数过的数字,这个是根据中国剩余定理的1-1对应可以确定。那么显然,所有像 x这样的数字的数量,必然会是phi(p)的倍数,也会是phi(q)的倍数,且是最小倍数值(否则越界到 1=mod p ,1=mod q里去了)

    则显然 phi(pq)=lcm (phi(p),phi (q)) 又因为p, q都是质数,则显然

    phi(pq)=lcm (p-1,q-1)

    上面这个结论必须牢记,因为下一步的密钥生成就是要根据上面的这个结论来做的。

    • 根据carmichael 函数生成私钥和公钥的过程 +4

      实际上目前基本简化成lcm (p-1,q-1)而不再考虑carmichael函数,我们再取一个质数,随便选一个,比如8171,因为生成私钥过程的p,q非常大所以我们可以非常的确定 8171 < lcm (p-1,q-1).

      这个时候找出8171在 lcm(p-1,q-1)上的模倒数,即 a*8171=1 mod lcm(p-1,q-1) 不知道什么是模倒数的同学可以这样理解, 也可以说存在这样一个k整数, such that k* lcm(p-1,q-1)+1 = a*8171.

      这个时候 这个算出来的a,连带 lcm(p-1,q-1)的值就是私钥。

      而8171 和pq的乘积就是公钥。当然现在RSA公钥可能连8171这种质数都不保存而是使用一个统一的大质数,也就是说公钥只保存pq的乘积。

      下一步就是加密和解密过程了。

      • 干货👏 +1
      • 能不能把数字放进去,比较直观的讲讲,比如p,q 是5,7.
        • 对!可以自己替代一下,选2个小的质数做一遍就理解了。主要打字数学符号很乱,特别是模,指数啥的,写出来要清晰不少。当然RSA密钥的质数都是非常大的,通常在4096bits. +2
          • p,q 13, 17, lcm (p-1,q-1) = lcm(12,16) = 48, k* lcm(p-1,q-1)+1 = a*8171 => 3*48 + 1 = 5 * 29, a=5. 公钥is 29, 13*17 = 221 私钥 is 5, 48
    • 👍👍👍 +1
    • RSA加密解密过程 +2

      在先前计算出的私钥是:模倒数a, lcm(p-1,q-1)

      公钥是8171, pq

      讲要加密的信息数字化即可(比如最丑陋的可以按照ascii编码成一个二进制数字)叫数字t.

      加密过程就是把t^8171=x mod pq, x这个值就是加密后的值。解密过程则就是 x^a=y mod pq, y其实是等于t的。

      如何证明 x^a=y mod pq的 y 必然等于t?

      我们来看 t^(8171*a)这个东西,也就是说某种程度t^8171是加密,而t^(8171*a)是解密。

      还记不记得 8171*a= 1 mod lcm(p-1,q-1), 对!这个就是关键,8171*a-1 = k* lcm (p-1, q-1) 某个常数k

      所以 t^(8171*a) = t^(8171*a-1) *t

      那么显然8171*a-1是等于p-1,或者q-1的倍数,我们单独的来看其中的一个p-1

      则显然 t^(8171*a-1)*t= t^(k(p-1))*t 某个整数k符合。

      交换一下冥 就得到 t^[(p-1)*k] *t

      我蛮看一下在模上面的情况; t^[(p-1)*k] *t = ? mod p

      这个时候要动用一个著名的定理,费马小定理: i^(p-1)=1 mod p 当p为质数的时候

      所以t^[(p-1)*k]*t = ? mod p 得出( t^(p-1))^k * t =? mod p 得出 1^k *t = ? mod p 得出 t=? mod p,所以 ? 必然等t.

      所以 t^(8171*a)=t mod p

      然后运用中国剩余定理在质数p,q上即可以得出 t^(8171*a) =t mod (pq)

      所以在模的角度,用公钥加密,私钥解密,还是用私钥加密,公钥解密,从费马小定理的角度来看是完全等价的,即公钥,私钥顺序无关且等价。另外可以看到中国剩余定理在代数数论上的频繁使用,无论是carmichael函数的推导还是加密解密的过程都动用了n次中国剩余定理,这个古老的定理是天朝为数不多的,给数学和计算机出的重大科学贡献的定理。

      私钥强度的证明比较简单,用可计算理论即得得出:

      因为密钥a是通过charmichael 函数lcm (p-1,q-1)取模反得出的,而carmichael lcm(p-1,q-1)的计算必须要分别知道p和q,而质数分解是个np问题,则显然密钥是无法通过分解pq这个公钥快速得出的。

      好了,rsa的加密就讲完了,下次讲一下椭圆曲线的加密过程,东西会比这个更多一点。

      • 14^29=209 mod 221, 209^5=14 mod 221 +1
        • 所以取2个小质数算一下,高中生都都能立刻理解加密到解密的过程。
    • 有人看懂了吗? +1
      • 其实可以把p,q选2个小的质数自己算一下整个过程,比如选17 , 19, 那个特定的公钥质数可以不选8171这种大的质数,选个5即可,高中学生算一遍就理解了,模其实高中生也可以理解,就是一个余数而已,费马小定理高中生其实也可以理解的。 +2
    • 好👍郑景润👍 +5
      • “陈景润”这个词和“专家”一样目前不是一个煲议词。许多年前,我女儿跟我说:班上有位男生数学很好,大家说他是nerd,我听了很心寒。 +1
        • 是啊,数学与体育,就不能共存吗?
          • 感觉数学和性格有很大的关系。它们之间相互影响。
    • 公钥,私钥以前把我搞混了,其实就是要一对钥匙,一把钥匙锁了,只有另一把能开。
      • 主要还是费马小定理,你公钥私钥前后换一下顺序一点问题都没有的,因为模倒数的次方不管顺序必然等于1 mod pq, 所以公钥,私钥过程后,必然在Z/pq群上等价于乘以1,也就是啥也没做。 +1
    • 还有,这加密和破解login password无关吧?
      • login pass一般用sha2哈希后只保存hash值,不保存密码和加密的一般,当然也有用AES加密保存的,但要保证aes密钥在系统上特别特别可靠。所以login pass更多的是要考虑是否有恶意碰撞的问题。 +1
        • “密码学家王小云,十年破解MD5和SHA-1两大国际密码”,这种真的厉害,还是夸大其词?
          • 是真厉害,因为她发现的杂凑函数的碰撞率,md5和sha1已经退出了hash商业使用的价值了,恶意碰撞在sha1上几台电脑算上1个月就能找出一个碰撞了,所以sha1安全性就废了。。 +2
    • word 天 - 普通从业者只需要纠结 openssl 后面参数到底跟 rsa 还是 ec 怎么一个周末整个 rolia 都开始谈两个大质数了。很像谢耳朵和佩尼讲 “这事儿得从两千六百年前古希腊温暖夏夜讲起” 既视感。🤣🤣🤣 +2
      • 这个坛子开始充满了乐趣,好玩。 +1
    • Let p=3,q=7, phi (pq)=phi(21)=12; lcm(p-1,q-1) = lcm(2, 6) = 6, so the statement phi(pq) = lcm(p-1, q-1) is false.
      • phi(21)=6 打字时候太晚了,脑子糊涂了,把toitient函数和phi函数搞混淆了,这个数-1是满足coprime 的最小的模倒数。比如 2* 2^(6-1)=1 mod 21 , 5*5^(6-1)=1 mod 21 其实可以不用管toitient函数,直接用lcm(p-1,q-1)即可。