意味着: 如果小B用自己的 私钥 加密数据,那么 小A 可以用 小B的公钥进行解密, 得到原始数据。 暂时这个功能好像还看不出来什么作用, 我们稍后再提。
RSA的大素数选择这同样是一个难点. 如果不感兴趣可以跳过.
参考:
RSA周边——大素数是怎样生成的?
数论部分第一节:素数与素性测试
RSA算法的核心正在于 找到两个大素数 p q 并且这个数值越大越好, 破解的难度就越高。
我们要将两个数相乘 很简单, 但是因式分解, 确定它是素数 又是一件很难的事情了。
惯用 也是最简单的方法, 正是采用试除法进行处理, 即从 2 开始逐个测试, 但目前而言, 我们需要的数值有数百位, 仅仅64位的long型 9223372036854775807 已经是这样大的一个数值, 更何况数百位?
素性测试
费马小定理:
如果p是一个质数,而整数a不是p的倍数,则有a^(p-1)≡1(mod p)
即: a的(p-1)次方除以p的余数恒等于1。
费马小定理是判定一个数是否为素数的必要条件,并非充分条件,因为存在着一些伪素数满足费马小定理却不是素数.
也就是说, 如果一个数是素数, 那么必然满足费马小定理. 换句话说, 如果存在一个数, 不满足费马小定理, 此时可以断定这个数必然不是素数.
Fermat 素性检验
则考虑a=2, 我们可以将选定的数用 a=2做检验, 如果判断不满足 费马小定理. 此时必然不是素数, 比起试除法要快很多。
但遗憾的是,仅能通过不满足来检验不是素数, 如果满足我们也没办法确定他是素数.
因此继续考虑a=3的情况,一个合数可能在a=2时通过了测试,但a=3时的计算结果却排除了素数的可能。于是,人们扩展了伪素数的定义,称满足 a^(n-1) mod n = 1 的合数n叫做以a为底的伪素数(pseudoprime to base a)。
前10亿个自然数中同时以2和3为底的伪素数只有1272个,这个数目不到刚才的1/4。
这告诉我们如果同时验证a=2和a=3两种情况,算法出错的概率降到了0.000025。
容易想到,选择用来测试的a越多,算法越准确。通常我们的做法是,随机选择若干个小于待测数的正整数作为底数a进行若干次测试,只要有一次没有通过测试就可以判定这个数为合数。这就是Fermat素性测试。
人们自然会想,如果考虑了所有小于n的底数a,出错的概率是否就可以降到0呢?遗憾的是,居然就有这样的合数,它可以通过所有a(前提是n与a互素)的测试。Carmichael第一个发现这样极端的伪素数,他把它们称作Carmichael数。前10亿个自然数中Carmichael数也有600个之多。这样高的出错率, 说明费马素性检验 依然不能够帮我们准确找到一个大素数. 依然需要加强算法.
Miller-Rabin素性测试
基于下面的定理:
如果p是素数,x是小于p的正整数,且x^2 mod p = 1,那么要么x=1,要么x=p-1。这是显然的,因为x^2 mod p = 1相当于p能整除x^2-1,也即p能整除(x+1)(x-1)。由于p是素数,那么只可能是x-1能被p整除(此时x=1)或x+1能被p整除(此时 x=p-1)。
以 a==2,n==341为例,演示一下该测试是如何进行的。(2^340%341==1,但是341并不是一个质数)
根据模运算的规则: a^b mod n = (a mod n)^b mod n
2 ^ 340 mod 341 = (2^170 mod 341)^2 mod 341 == 1
此时必然有: 2^170 mod 341 == 1 或 2^170 mod 341 = 340 而 2^170 mod 341 结果是等于 1的
继续: 要求满足: 2^85 mod 341==1 或者 2^85 mod 341 == 340 但此时 两者都不满足, 所以341不是素数。
所以测试的要点则是: 尽可能提取因子2, 把n-1表示成 d * 2 ^ r, 如果n是一个素数,那么或者a ^ d mod n=1,或者存在某个i使得a ^ (d * 2 ^ i) mod n = n - 1.
但需要注意的是: Miller-Rabin 素性测试同样是不确定算法,我们把可以通过以a为底的Miller-Rabin测试的合数称作以a为底的强伪素数(strong pseudoprime)。第一个以2为底的强伪素数为2047。第一个以2和3为底的强伪素数则大到1373653。
对 于大数的素性判断,目前Miller-Rabin算法应用最广泛。一般底数仍然是随机选取,但当待测数不太大时,选择测试底数就有一些技巧了。比如,如果 被测数小于4 759 123 141,那么只需要测试三个底数2, 7和61就足够了。当然,你测试的越多,正确的范围肯定也越大。如果你每次都用前7个素数(2, 3, 5, 7, 11, 13和17)进行测试,所有不超过341 550 071 728 320的数都是正确的。如果选用2, 3, 7, 61和24251作为底数,那么10^16内唯一的强伪素数为46 856 248 255 981。这样的一些结论使得Miller-Rabin算法在OI中非常实用。通常认为,Miller-Rabin素性测试的正确率可以令人接受,随机选取 k个底数进行测试算法的失误率大概为4^(-k)。
而 Miller-Rabin素性测试 也就是我们的终极法宝。
那么大素数是怎么生成的?