当前位置:网站首页>RSA及其證明 [原創]

RSA及其證明 [原創]

2021-09-15 07:42:44 helesheng

描述RSA的實現步驟介紹文章非常多,但說明並證明其原理,並進而討論為什麼這樣設計的文章不多。本人才疏學淺,不敢說理解了R.S.A.三比特泰鬥的設計初衷,簡單就自己的理解寫一寫,博大家一笑。

以下原創內容歡迎網友轉載,但請注明出處: https://www.cnblogs.com/helesheng

一、用到的數論基礎定理

R.S.A.三比特一定是數學大神歐拉的粉絲,因為所有用到的基本原理和定理都是以歐拉命名的。

1、歐拉函數

小於m的書中,所有與m互質的數的個數定義為“歐拉函數”,寫為:Φ(m)。若m的質因數分解為: (其中Pi為素數,ei為正整數),Φ(m) 的計算公式為:

 

 2、歐拉定理

若gcd(a,m)=1(a和m互質),則有:

啟示:

1)歐拉定理是“環”到“域”的重要過渡,只要把左邊的乘方運算拆為兩個乘方運算的乘積,拆成的兩個部分就可以理解為“域”中的“元”及其乘法“逆元”,這樣環上的模逆元就存在了,“環”就可以變成“域”了。但需要注意的是歐拉定理存在的條件是gcd(a,m)=1這個條件。為滿足這個條件,密碼學(cryptology)如果工作在有限域上,經常會進行選擇m為素數,或者非常接近素數的情况;而a則之需要是小於m的任意數,作為明文或密文。但嚴格說,RSA不是工作在伽羅瓦域上的,因為RSA的模數n是兩個素數p、q的乘積。n很接近一個素數,在證明RSA時,需要專門證明gcd(a,n)不為1的情况。

2)費馬小定理是歐拉定理的“特例中的特例”,其描述為:當p是一個素數時, 或 。證明:若p為素數gcd(a,p)=1;而歐拉函數Φ(m)=p-1。代入歐拉定理,即可得到費馬小定理。

二、RSA過程

Step 1.選擇兩個大素數p和q,當n為7680比特(960字節)的數時,p和q約為3072比特,在這樣長度的奇數中尋找一個素數的可能性約為:

 即約1065個奇數中有一個素數。

計算n=p*q。

Step 2.計算n的歐拉函數Φ(n)。

因為n的兩個質因數已知為p和q,代入公式(1)有Φ(n)=(p-1)(q-1)。

Step 3.選擇一個與Φ(n)互質的數e。

a)要求e與Φ(n)互質的原因是要保證e的模n乘法逆的存在。而這個乘法逆就是私鑰d。

 

 

b)e將作為公鑰,e取值不大,一般有3、17、65537幾種選擇。因為公鑰e遠小於私鑰d,持有公鑰的一方,在不論是進行加密(用RSA做密鑰交換)還是進行解密(用RSA作數字簽名)的速度都遠遠快於持有私鑰d的一方

e之所以選擇這幾個數,除了是素數之外,還因為這幾個數3(b101)、17(b1_0001)、65537(b1_0000_0001)的二進制錶達中1的個數特別少,這樣在計算xe時將會特別簡便。

c)在整個RSA運算中,計算d是唯一一次使用Φ(n)作為模的地方,其他地方都是使用n作為模。

Step 4.使用公鑰e和私鑰d進行加解密

a)上面的公式中並沒有指定x和y誰是明文誰是密文,也就是說兩者都可以作為明文和密文。

b)RSA找到了一種“一一對應”的映射關系f:因為e較小,且公開,所以x映射到y很容易;y映射到x很困難,d較大,且不知道p、q時很難得到。這樣的映射f被稱為單向映射

三、RSA的證明

證明RSA過程,等價於證明:其中

n=p×q,n只有p、q兩個質因數。

根據n和x的情况分兩種情况討論:

情况一:當x不含有p和q兩個質因數時,n和x互質,gcd(n,x)=1。根據歐拉定理有:

 

根據d的定義,d和e對模Φ(n)互逆,有:

 

 

 將上式寫成另一種形式:

 

 將其代入欲證明的(2),有:

 

 情况二:當n和x不互質時,由於n=p×q,x可以寫成:x=r×p或s×q(但不能寫成x=r×p×q,因為這會使得x > n)。不失一般性,假設x=r×p。由於,根據歐拉定理和歐拉函數有:

 

 

根據d的定義,同樣有(5)式,而(6)式則變為: 

 

 

其中使用了歐拉函數計算公式

將(7)代入上式有: 

 

 

 至此,證明了不論在那種情况下都有 ,證畢!

四、RSA的設計思路

不自量力的揣測一下R.S.A.三比特的設計思路,是利用歐拉定理構造了以n作為模的環上互逆的一對數x和y作為明文和密文,x和y各自是對方的e次方和d次方。如果知道n的質因數分解(p×q)的,可以通過歐拉函數方便的計算出e和d,否則只能靠對方告知其中之一,從而形成了單向映射,構成了所謂“非對稱加密”。

另外,在e和d的複雜度的分割上,並不是相等的。設計者讓知道質因數分解的一方的密鑰d遠遠複雜於e,原因有二:其一,知道質因數分解的一方可以通過中國餘數定理CRT加速計算;其二,不知道質因數分解的諸多“非對稱”通信者,可以使用較低的算力執行加、解密。

較簡單密鑰e稱為公鑰,較複雜密鑰d稱為私鑰。

 

版权声明
本文为[helesheng]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/09/20210915073956247P.html

随机推荐