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