RSA加密算法介绍

首先,找出三个数, 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 >= n的话,就将a表成s进位(s <= n,通常取s = 2^t),则每一位数均小於n,然後分段编码......接下来,计算b == a^m mod n, (0 <= b < n), b就是编码後的资料......解码的过程是,计算c == b^r mod pq (0 <= c < pq),於是乎,解码完毕......等会会证明c和a其实是相等的:)如果第三者进行窃听时,他会得到几个数: m, n(=pq), b......他如果要解码的话,必须想办法得到r......所以,他必须先对n作质因数分解.........要防止他分解,最有效的方法是找两个非常的大质数p, q,使第三者作因数分解时发生困难......... <定理>若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 <= a < n, 0 <= c < n,所以这就是说a等於c,所以这个过程确实能做到编码解码的功能.....