首先,找出三个数, p, q, r,
其中p, q是两个相异的质数, r是与(p-1)(q-1)互质的数。
p, q, r这三个数便是private key。接著,找出m,使得rm == 1 mod (p-1)(q-1).....这个m一定存在,因为r与(p-1)(q-1)互质,用辗转相除法就可以得到了.....再来,计算n = pq....... m, n这两个数便是public key。
编码过程是,若资料为a,将其看成是一个大整数,假设a = n的话,就将a表成s进位(s 若p, q是相异质数, rm == 1 mod (p-1)(q-1), a是任意一个正整数, b == a^m mod pq, c == b^r mod pq,则c == a mod pq证明的过程,会用到费马小定理,叙述如下: m是任一质数, n是任一整数,则n^m == n mod m (换另一句话说,如果n和m互质,则n^(m-1) == 1 mod m)运用一些基本的群论的知识,就可以很容易地证出费马小定理的........ 因为rm == 1 mod (p-1)(q-1),所以rm = k(p-1)(q-1) + 1,其中k是整数因为在modulo中是preserve乘法的(x == y mod z and u == v mod z = xu == yv mod z),所以, c == b^r == (a^m)^r == a^(rm) == a^(k(p-1)(q-1)+1) mod pq 1.如果a不是p的倍数,也不是q的倍数时,则a^(p-1) == 1 mod p (费马小定理) = a^(k(p-1)(q-1)) == 1 mod p a^(q-1) == 1 mod q (费马小定理) = a^(k(p-1)(q-1)) == 1 mod q所以p, q均能整除a^(k(p-1)(q-1)) - 1 = pq | a^(k(p-1)(q-1)) - 1即a^(k(p-1)(q-1)) == 1 mod pq = c == a^(k(p-1)(q-1)+1) == a mod pq 2.如果a是p的倍数,但不是q的倍数时,则a^(q-1) == 1 mod q (费马小定理) = a^(k(p-1)(q-1)) == 1 mod q = c == a^(k(p-1)(q-1)+1) == a mod q = q | c - a因p | a = c == a^(k(p-1)(q-1)+1) == 0 mod p = p | c - a所以, pq | c - a = c == a mod pq 3.如果a是q的倍数,但不是p的倍数时,证明同上4.如果a同时是p和q的倍数时,则pq | a = c == a^(k(p-1)(q-1)+1) == 0 mod pq = pq | c - a = c == a mod pq Q.E.D.这个定理说明a经过编码为b再经过解码为c时, a == c mod n (n = pq)....但我们在做编码解码时,限制0
