RSA加密算法
cc 首先,?找出三個數(shù),?p,?q,?r,
其中?p,?q?是兩個相異的質(zhì)數(shù),?r?是與?(p-1)(q-1)?互質(zhì)的數(shù)......
p,?q,?r?這三個數(shù)便是?private?key
接著,?找出?m,?使得?rm?==?1?mod?(p-1)(q-1).....
這個?m?一定存在,?因為?r?與?(p-1)(q-1)?互質(zhì),?用輾轉(zhuǎn)相除法就可以得到了.....
再來,?計算?n?=?pq.......
m,?n?這兩個數(shù)便是?public?key
編碼過程是,?若資料為?a,?將其看成是一個大整數(shù),?假設(shè)?a?<?n....
如果?a?>=?n?的話,?就將?a?表成?s?進(jìn)位?(s?<=?n,?通常取?s?=?2^t),
則每一位數(shù)均小於?n,?然後分段編碼......
接下來,?計算?b?==?a^m?mod?n,?(0?<=?b?<?n),
b?就是編碼後的資料......
解碼的過程是,?計算?c?==?b^r?mod?pq?(0?<=?c?<?pq),
於是乎,?解碼完畢......?等會會證明?c?和?a?其實是相等的??:)
如果第三者進(jìn)行竊聽時,?他會得到幾個數(shù):?m,?n(=pq),?b......
他如果要解碼的話,?必須想辦法得到?r......
所以,?他必須先對?n?作質(zhì)因數(shù)分解.........
要防止他分解,?最有效的方法是找兩個非常的大質(zhì)數(shù)?p,?q,
使第三者作因數(shù)分解時發(fā)生困難.........
<定理>
若?p,?q?是相異質(zhì)數(shù),?rm?==?1?mod?(p-1)(q-1),
a?是任意一個正整數(shù),?b?==?a^m?mod?pq,?c?==?b^r?mod?pq,
則?c?==?a?mod?pq
證明的過程,?會用到費馬小定理,?敘述如下:
m?是任一質(zhì)數(shù),?n?是任一整數(shù),?則?n^m?==?n?mod?m
(換另一句話說,?如果?n?和?m?互質(zhì),?則?n^(m-1)?==?1?mod?m)
運用一些基本的群論的知識,?就可以很容易地證出費馬小定理的........
<證明>
因為?rm?==?1?mod?(p-1)(q-1),?所以?rm?=?k(p-1)(q-1)?+?1,?其中?k?是整數(shù)
因為在?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
- 如果?a?不是?p?的倍數(shù),?也不是?q?的倍數(shù)時,
則?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
- 如果?a?是?p?的倍數(shù),?但不是?q?的倍數(shù)時,
則?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
- 如果?a?是?q?的倍數(shù),?但不是?p?的倍數(shù)時,?證明同上
- 如果?a?同時是?p?和?q?的倍數(shù)時,
則?pq?|?a
=>??c?==?a^(k(p-1)(q-1)+1)?==?0?mod?pq
=>??pq?|?c?-?a
=>??c?==?a?mod?pq
Q.E.D.
