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)
上面这个结论必须牢记,因为下一步的密钥生成就是要根据上面的这个结论来做的。
实际上目前基本简化成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的乘积。
下一步就是加密和解密过程了。
在先前计算出的私钥是:模倒数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的加密就讲完了,下次讲一下椭圆曲线的加密过程,东西会比这个更多一点。