1、代數在網絡平安中的運用20211989運用數學2班童鈔概述 現有的公鑰密碼體制大多是建立在交換代數的根底上, 例如著名的RSA 密碼體制、DiffieHellman 密鑰交換協議和ELGamal 密碼體制都基于整數環, 而概率公鑰算法NTRU那么基于多項式環交換代數構造的優點在于有豐富的實際、容易了解的構造并且易于實現但是, 由于計算才干的繼續加強, 為保證預期平安程度所需求的密鑰長度也不斷增長, 這就使得基于交換代數的公鑰密碼遭遇了計算瓶頸因此有必要尋覓基于更加復雜的代數構造的密碼技術 近年出現的一種具有強大競爭力的橢圓曲線密碼學ECC對RSA 提出了挑戰在關于公鑰密碼學的IEEEP3 中,

2、 曾經思索了ECC在公鑰密碼學中運用橢圓曲線是Neal Koblitz和Victor Miller于1985 年各自獨立地提出的與RSA 相比, ECC 的主要誘人之處在于它可以用比RSA 短得多的密鑰得到一樣的平安性, 因此可以減少處置負荷 近年來, 基于超奇特橢圓曲線上雙線性對的密碼體制的研討非常活潑, 處理了構造三方一輪DiffieHellman 密鑰協議、短簽名方案和基于身份加密算法等長期懸而未決的公開問題但是, 正如BarretoLynnScott所指出, 超奇特橢圓曲線上Weil 對與Tate 對的運算本錢經常使它成為基于雙線性對密碼系統的瓶頸尋覓平安高效的雙線性對已成為基于雙線性

3、對密碼學的首要問題 目前, 曾經出現了一些運用非交換代數的公鑰密碼系統, 尤其是辮子群密碼學吸引了大量的研討1999 年,Anshel-Anshel-Goldfeld基于辮子群中的共軛問題構建了密鑰交換協議2000 年, KoLee 等人利用辮子群的子群間的交換關系構建了基于廣義共軛問題的DiffieHellman 密鑰交換協議, 以及一個類似于ELGamal 體制的加密算法但是, 由于非交換群中沒有像整數環中加法那樣與共軛運算相容的運算, 這使得基于非交換群的簽名方案的設計變得困難直到2002 年, Ko-Choi-Cho-Lee才基于共軛問題的計算方式和斷定方式之間的鴻溝Gap設計了第一個

4、辮子群簽名方案目錄基于橢圓曲線的密碼算法循環矩陣在網絡平安中的運用DES算法基于雙線性對的密碼學基于辮子群的密碼體制AES算法RSA算法SHA-1算法離散對數密碼體制橢圓曲線在網絡平安中的運用橢圓曲線的定義及點的加法運算有限域上的橢圓曲線橢圓曲線的離散對數問題橢圓曲線密碼體制的概念橢圓曲線密碼體制是屬于公鑰密碼體制中的一種，它主要的數學實際根底是源于數論的相關知識，它是經過有限域中橢圓曲線上的點構成的Aebel加法群，在Aebel群中計算橢圓對數 。如今國際上比較流行的密碼體制都是以三種難解的實際為根據而設計的，其中一種是基于大整數因子分解問題設計的比如RSA公鑰密碼體制，還有一種是基于離散對

5、數的難解問題而設計的比如ELGamal公鑰密碼體制，最后一種就是同樣基于離散對數問題設計的橢圓曲線密碼體制。構造橢圓曲線ElGamal算法ElGamal算法，是一種較為常見的加密算法，它是基于1984年提出的公鑰密碼體制和橢圓曲線加密體系。既能用于數據加密也能用于數字簽名，其平安性依賴于計算有限域上離散對數這一難題。在加密過程中，生成的密文長度是明文的兩倍，且每次加密后都會在密文中生成一個隨機數K，在密碼中主要運用離散對數問題的幾個性質：求解離散對數能夠是困難的，而其逆運算指數運算可以運用平方-乘的方法有效地計算。也就是說，在適當的群G中，指數函數是單向函數。橢圓曲面密碼體制的運用背景及優勢我

6、們如今快速的生活節拍和便利的生活方式都是顯而易見的，足不出戶的我們就可以經過計算機完成許多的事情，比如任務、購物等，由于需求的添加導致計算機也不斷的改良提高，尤其是計算機速度的提高，同時也就需求更好更完善的加密方案。由于如今普遍運用的是經典的公鑰密碼體制RSA，但在密鑰長度為512比特的情況下卻逐漸變得不平安，經過加長密鑰長度雖然可以提高密碼的平安性能，但是加密解密的效率也會變得越來越低，所以最好的方式就是設計一種新的密碼體制替代本來運用的4。橢圓曲線密碼體制就是在這樣的背景下開場逐漸遭到注重的，是一種以橢圓曲線相關數學知識為根底的公鑰密碼體制4。在公鑰密碼體制中與其它算法相比較，橢圓曲線密碼

7、體制具有密鑰短和計算效率高等典型優點，而其本身的算法及其數學實際都是非常深奧難懂的。橢圓曲線密碼體制運用在實踐中的主要優勢有：平安性能較高，速度快，計算量小、效率高對于一切的密碼體制而言，它的平安性能毫無疑問的成為了中心的問題，對于橢圓曲線密碼體制來說它的數學原理是對它平安性能最有利的左證。該體制的中心是有限域上的離散對數問題4，而這個問題是不能在多項式時間內運用一切的知算法來求解的，由此可見該體制的抗攻擊性能與其它體制相比是占有絕對優勢的。下面經過一個表格可以更直觀的感受橢圓曲線密碼體制的這點優勢由表格可以看出，將160位的ECC算法和1024位的RSA算法作為比較它們的平安強度相差不多，并

8、且在同等的條件下平安強度要求越高的話ECC算法的短密鑰優勢也就顯現的更為明顯。所以，ECC算法與RSA算法相比較在每一比特都是擁有更高的平安性能的，也正是由于擁有這樣的特點，才干廣泛的運用于挪動的電子商務以及計算機網絡平安和軟件注冊的相關領域。公開密鑰的生成速度主要取決于其中的大數算術運算而它的運算速度自然和它的大小規模息息相關，在一個一樣的計算條件下，橢圓曲線密碼體制ECC的實現可以選擇比基于大合數因子分解困難性的公開密鑰密碼體制RSA小很多的大數，這也就保證了實現的速度和效率。同樣可以經過下面表格中的數據來闡明經過上表就可以明顯的看出ECC在密鑰對的生成速度、簽名速度和認證方面的速度都快得

9、多，計算量小且計算速度快，尤其是在存儲容量不大運算才干比較低的情況下是具有顯著優勢的。所需存儲的空間比較小，帶寬要求較低橢圓曲線密碼體制的密鑰長度與基于大合數因子分解困難性的公開密鑰密碼體制相比就要小很多，這一點也可以從表1中看出來，比如RSA需求512位元元而ECC只需求106位即可，這也就闡明了ECC對存儲空間的需求要較小，在計算上的開銷也很小，所以ECC會廣泛的運用在類似這些存儲空間有限制的設備中。同樣也是由于這樣的優勢決議了ECC可以廣泛的運用在挪動通訊設備和智能卡等存儲空間小計算才干相對較差的設備上。帶寬即頻帶寬度是指可以有效經過某信道的信號最大頻帶寬度。由于橢圓曲線密碼體制和其它加

10、密算法相比具有密鑰短的特點，所以在傳輸中要求的帶寬也更低，當對一個長的數據信息進展加密時ECC和RSA密碼系統有同樣的帶寬要求8，但是運用在較短的數據信息中ECC的帶寬要求卻低很多，這也是ECC可以廣泛的運用于無線網絡中的重要緣由。ECC的運用可以減少一定的帶寬開銷所以使得通訊的效率也大幅提高，并且在Web效力器上運用帶寬的費用是非常高昂的，ECC的出現既處理了需求節省計算時間的要求又節約了因帶寬需求的破費。在3G網絡中針對計算效率低、帶寬資源有限的限制，基于橢圓曲線密碼體制而涉及平安的支付流程是可以實現端對端的平安數據信息傳送。在對系統初始化以及設置系統參數時橢圓曲線密碼體制也有不同于其它密

11、碼體制的優勢，比如與RSA算法相比，RSA需求選取兩個素數才干初始化，而ECC那么需求選擇一個素數并在有限域上選取不同的橢圓曲線，由于選擇橢圓曲線時有很多的選擇所以初始化的選擇空間就很大。基于以上的這些優點，橢圓曲線密碼體制在實踐中的運用非常廣泛，比如虛擬公用網絡VPN平安隧道方面由于要思索到計算機存儲和資源方面對嵌入式運用的局限性，根據ECC加密解密速度較快、節省帶寬和節省所需求的存儲資源的特點可以選擇運用橢圓曲線密碼體制設計運用于身份鑒別中，在網絡的通訊中必需求高效率的對數據信息進展加密，而ECC的快速處置速度可以使通訊不再受限于存儲的容量大小和計算才干的高低。除此之外，橢圓曲線密碼體制在

12、數字簽名等需求高加密速度的方面也能快速實現平安高效的加密、簽名。指紋加密與橢圓曲線隨著近幾年科技的開展，尤其是生物特征識別技術的逐漸成熟，經過利用生物體本身具有獨一穩定不變性的特征將其運用到確保信息平安的領域，指紋加密技術就是生物識別技術與信息平安融洽結合的最好表達。由于生物特征的獨一性就可以保證運用指紋信息進展身份驗證會比其他方案有更高的平安性、準確性。指紋采集端和指紋認證端是分開任務的，它們之間經過網絡傳輸數據信息，這也是指紋識別認證系統中的一個特點。首先是采集指紋信息的過程，用戶經過提取指紋的儀器完成該步驟，然后再將指紋信息的數字圖像傳送給計算機。之后計算機完成指紋特征的采集任務，并將指

13、紋的數字圖像轉換成即將進展加密操作的特征序列。此時就可以將加密后的信息傳送到指紋認證的終端了，在終端完成對應的解密操作、指紋特征的對比操作，最后將對比的結果前往，也就是完成了一次經過網絡對指紋身份的識別認證操作。該方案與上文中引見的EIGamal方案的原理根本一樣，詳細如下方案的優缺陷該方案的優點主要表達在指紋的獨一性決議了較高的平安性，也就是說其他的加密方式也可以到達同樣平安的效果。換言之，這個方案的平安性并不取決于加密算法的復雜程度，而是取決于加密的數據信息的平安強度。但是，與其他的加密方式相比橢圓曲線運用較少、較小的參數完成過程，尤其與RSA算法相比計算過程更不易出錯，所以運用橢圓曲線密

14、碼體制進展加密還是比較高效的。橢圓曲線密碼體制與RSA密碼體制在實踐運用中的比較橢圓曲線密碼算法和RSA算法相比最大的優點就是不需求計算橢圓曲線有理點群的離散對數問題的子指數算法，也就是說當在同等平安的條件下，橢圓曲線密碼算法可以選擇比RSA算法更小的參數進展加密解密操作。同時橢圓曲線密碼算法將實數域中乘法的運算和指數的運算映像成了橢圓曲線上加法的運算。綜上所述，橢圓曲線密碼體制更適用、更容易、更平安，同時本錢也更低。將兩種算法作比較可以發現，RSA算法的過程不僅復雜還必需嚴厲嚴密，對于素數的產生和檢測的計算過程容易產生錯誤；而橢圓曲線密碼算法雖然生成的參數復雜但是不需求嚴密甚至還可以對外公布

15、，不過雖然嚴密的密鑰生成復雜但是計算公鑰很容易。橢圓曲線密碼體制具有橢圓曲線豐富、不易被破解、不需求大量的參數參與計算及不占用大量存儲空間的優勢。比如在數字簽名中完成各部分的效率方面進展比較，RSA算法是幾乎不會遭到密鑰位數變化的影響，不斷都可以堅持著很快的驗證速度，相反地，ECC算法遭到的影響很猛烈，與RSA算法受影響程度相比有很大的差距。在運用超越一定的密鑰位數的范圍中，隨著密鑰位數逐漸地增大ECC算法就會越優于RSA算法。對于一樣運用量的參數，橢圓曲線密碼體制在每一比特的加密解密過程中都擁有更大的強度，并且所需求的參數規模也較小，這在實踐的運用中是具有很大優勢的。橢圓曲線雖然子在一個有限

16、域中只需有限的幾個乘法子群，但是卻有很高的平安性能，所以成為公鑰密碼學中運用廣泛的新體制。二、循環矩陣在網絡平安中的運用多變量密碼學中的循環矩陣等價的多項式定義了一樣密碼體制，因此等價的多項式產生的密碼體制也有一樣的密鑰空間和加/解密映射的集合。一個等價類的勢(cardinality)相當于選取不同的仿射變換對所產生的加密映射的個數.這就引出了找到產生一樣加密映射的仿射變換的個數問題.例如:對于一個給定的多變量公鑰密碼體制，找到其等價密鑰的個數。在一個等價類中的不同多項式方程組的個數代表可以選擇的不同密鑰的個數。等價密鑰的存在可以減少密鑰空間，這對于多變量公鑰密碼學的密碼分析是很有協助的。多項

17、式同構引出多項式方程組的等價關系.因此多項式方程組的集合可以被劃分為不同的等價類。多項式同構的計數問題那么包含以下3個方而: 1)對不同等價類的計數; 2)對每一個等價類的勢進展計數; 3)確定一切的等價類的代表元.基于循環矩陣的ElGamal密碼體制離散對數問題是公鑰密碼學中運用最廣泛的一個密碼原語。其運用之一是最經典的ElGamal密碼系統。眾所周知，ElGamal密碼系統的平安性依賴于有限域上的離散對數問題。為了可以提出更平安的密碼系統，人們開場將有限域上的離散對數問題推行到非交換群上的離散對數問題，并在此上提出了MOR密碼系統，可以說MOR密碼系統是ElGamal密碼系統在非交換群上的

18、推行。而這個非交換群是循環矩陣群的自同構群。，循環矩陣群提供了一個有限域上的同樣大小的平安，且它有一半的計算本錢。循環矩陣的另一個有趣的現實是：其能提供一個平安的域的實現大小。循環矩陣的算法是在有限域上進展運算，這與橢圓曲線的情況極為類似。在循環的情況下，該域的大小甚至可以小于一個用于橢圓曲線的大小。總之，循環矩陣的優點是，它運用較小的域而且運算速度更快。在該文獻中，一切矩陣是非奇特循環矩陣C(d, q)和特殊循環矩陣，即循環矩陣的行列式1，記為SC(d, q)。ElGamal密碼體制在SC(d, q)的實現在SC(d, q)的ElGamal密碼系統中，需求進展十二次的逆操作，這是很容易計算的

19、。自公鑰密碼學概念提出以來，許多優秀的公鑰密碼體制相繼被提出并得到完善。目前，大多數未被攻破的公鑰密碼體制都是基于交換代數構造的困難問題，如大整數分解問題、有限域上的離散對數問題等。然而，由于量子計算的最新研討成果，許多基于交換代數構造的難題假設不再困難。迄今為止，人們曾經提出了許多基于非交換代數構造的公鑰密碼體制，特別是辮群密碼體制吸引了大量的研討。經過本文的探求，我們可以知道，循環矩陣是數學研討中非常重要的一個數學計算手段，它本身具有很多特殊性質。本文針對循環矩陣的特殊性質，研討了其在密碼學中的公鑰密碼加密解密的過程中的運用。隨著電子科技的開展，以及電子通訊的普及，密碼學得到了前所未有的開

20、展機遇。我們從數學工具，數學算法的角度出發，進展發明性思想，使其在密碼學中發揚作用，置信對密碼學的研討會越來越成熟。DES算法DES是一種分組密碼協議，有兩個根本指點思想分散Diffusion和混亂Confusion,以保證密碼算法能滿足要求，所以DES的詳細實現是依賴于多次迭代進展乘積密碼加密變換。這個算法的中心是Feistel密碼，由于其設計的巧妙，加密解密都用一個函數。它的算法是對稱的，既可用于加密又可用于解密。DES 運用一個 56 位的密鑰以及附加的 8 位奇偶校驗位，產生最大 64 位的分組大小。這是一個迭代的分組密碼，運用稱為 Feistel 的技術，其中將加密的文本塊分成兩半。

21、運用子密鑰對其中一半運用循環功能，然后將輸出與另一半進展“異或運算；接著交換這兩半，這一過程會繼續下去，但 最后一個循環不交換。DES 運用 16 個循環，運用異或，置換，代換，移位操作四種根本運算。DES的流程根本是執行16輪下面的運算：1 初始變換Initial Permutation2 右邊32位f函數2.1 E置換2.2 與輪密鑰XOR2.3 S盒交換2.4 P置換2.5 和左邊32位XOR3 左右交換，最終變換final permutation需求特別留意的是，最后一輪是不需求做左右交換這一部的。 從詳細實現看DES有幾個知的方面存在脆弱性：1，加密協議半公開化 2，密鑰太短 3，軟

22、件的實現的性能較低。隨著計算機的處置才干的提高，只需56位密鑰的DES算法不再被以為是平安性的，故如今普通的方案是三重DES，既3DES。AES 算法AESThe Advanced Encryption Standard是一種非Feistel 的對稱分組密碼體制，和DES的根本指點思想一樣都是多次混淆，所不同的是非線性層的由16個S盒進展并置混淆。AES具有平安可靠、效率高等優點。AES加密過程是在一個44的字節矩陣上運作，這個矩陣又稱為“形狀state，其初值就是一個明文區塊矩陣中一個元素大小就是明文區塊中的一個Byte。Rijndael加密法因支持更大的區塊，其矩陣行數可視情況添加加密時，

23、各輪AES加密循環除最后一輪外均包含4個步驟： 1. AddRoundKey 矩陣中的每一個字節都與該次輪秘鑰round key做XOR運算；每個子密鑰由密鑰生成方案產生。 2. SubBytes 經過個非線性的交換函數，用查找表的方式把每個字節交換成對應的字節。 3. ShiftRows 將矩陣中的每個橫列進展循環式移位。 4. MixColumns 為了充分混合矩陣中各個直行的操作。這個步驟運用線性轉換來混合每列的四個字節。AddRoundKey步驟在AddRoundKey步驟中，將每個形狀中的字節與該回合密鑰做異或。AddRoundKey步驟，回合密鑰將會與原矩陣合并。在每次的加密循環中

24、，都會由主密鑰產生一把回合密鑰經過Rijndael密鑰生成方案產生，這把密鑰大小會跟原矩陣一樣，以與原矩陣中每個對應的字節作異或加法。SubBytes步驟在SubBytes步驟中，矩陣中各字節被固定的8位查找表中對應的特定字節所交換,S;bij=Saij.在SubBytes步驟中，矩陣中的各字節經過一個8位的S-box進展轉換。這個步驟提供了加密法非線性的變換才干。S-box與GF28上的乘法反元素有關，知具有良好的非線性特性。為了防止簡單代數性質的攻擊，S-box結合了乘法反元素及一個可逆的仿射變換矩陣建構而成。此外在建構S-box時，刻意避開了固定點與反固定點，即以S-box交換字節的結果

25、會相當于錯排的結果。ShiftRows步驟在ShiftRows步驟中，矩陣中每一行的各個字節循環向左方位移。位移量那么隨著行數遞增而遞增。ShiftRows描畫矩陣的行操作。在此步驟中，每一行都向左循環位移某個偏移量。在AES中區塊大小128位，第一行維持不變，第二行里的每個字節都向左循環挪動一格。同理，第三行及第四行向左循環位移的偏移量就分別是2和3。128位和192比特的區塊在此步驟的循環位移的方式一樣。經過ShiftRows之后，矩陣中每一豎列，都是由輸入矩陣中的每個不同列中的元素組成。Rijndael算法的版本中，偏移量和AES有少許不同；對于長度256比特的區塊，第一行依然維持不變，

26、第二行、第三行、第四行的偏移量分別是1字節、3字節、4位組。除此之外，ShiftRows操作步驟在Rijndael和AES中完全一樣。MixColumns步驟在MixColumns步驟中，每個直行都在modulo之下，和一個固定多項式c(x)作乘法。在MixColumns步驟，每一列的四個字節經過線性變換相互結合。每一列的四個元素分別當作的系數，合并即為GF28中的一個多項式，接著將此多項式和一個固定的多項式在modulo 下相乘。此步驟亦可視為Rijndael有限域之下的矩陣乘法。MixColumns函數接受4個字節的輸入，輸出4個字節，每一個輸入的字節都會對輸出的四個字節呵斥影響。因此Sh

27、iftRows和MixColumns兩步驟為這個密碼系統提供了分散性。大致說來，AES 加密算法的中心有四個操作。AddRoundKey 運用從種子密鑰值中生成的輪密鑰替代 4 組字節。SubBytes 交換用一個替代表 交換單個字節。ShiftRows 經過旋轉 4字節行 的 4 組字節進展序列置換。MixColumns 用域加和域乘的組合來交換字節。正如他所看到的，AES 加密算法運用相當簡單明了的技術來替代和置換，除 MixColumns 例程以外。MixColumns 使 用特殊的加法和乘法。AES 所用的加法和乘法是基于數學的域論。尤其是 AES 基于有限域GF(28)。GF(28)

28、由一組從 0 x00 到 0 xff 的256個值組成，加上加法和乘法，因此是(28)。GF代表伽羅瓦域，以發明這一實際的數學家的名字命名。GF(28) 的一個特性是一個加法或乘法的操作的結果必需是在0 x00 . 0 xff這組數中。雖然域論是相當深奧的，但GF(28)加法的最終結果卻很簡單。GF(28) 加法就是異或XOR操作。在GF(28)中用0 x01的乘法是特殊的；它相當于普通算術中用1做乘法并且結果也同樣任何值乘0 x01等于其本身。如今讓我們看看用0 x02做乘法。和加法的情況一樣，實際是深奧的，但最終結果非常簡單。只需被乘的值小于0 x80，這時乘法的結果就是該值左移1比特位。

29、假設被乘的值大于或等于0 x80，這時乘法的結果就是左移1比特位再用值0 x1b異或。它防止了“域溢出并堅持乘法的乘積在范圍以內。一旦他在GF(28)中用0 x02建立了加法和乘法，他就可以用任何常量去定義乘法。用0 x03做乘法時，他可以將 0 x03 分解為2的冪之和。為了用 0 x03 乘以恣意字節b， 由于 0 x03 = 0 x02 + 0 x01，因此：b * 0 x03 = b * (0 x02 + 0 x01) = (b * 0 x02) + (b * 0 x01)這是可以行得通的，由于他知道如何用 0 x02 和 0 x01 相乘和相加，用0 x0d去乘以恣意字節b可以這樣做

30、：b * 0 x0d = b * (0 x08 + 0 x04 + 0 x01) = (b * 0 x08) + (b * 0 x04) + (b * 0 x01) = (b * 0 x02 * 0 x02 * 0 x02) + (b * 0 x02 * 0 x02) + (b * 0 x01)在加解密算法中，AES MixColumns 例程的其它乘法遵照大體一樣的方式，如下所示：b * 0 x09 = b * (0 x08 + 0 x01) = (b * 0 x02 * 0 x02 * 0 x02) + (b * 0 x01) b * 0 x0b = b * (0 x08 + 0 x02

31、+ 0 x01) = (b * 0 x02 * 0 x02 * 0 x02) + (b * 0 x02) + (b * 0 x01) b * 0 x0e = b * (0 x08 + 0 x04 + 0 x02) = (b * 0 x02 * 0 x02 * 0 x02) + (b * 0 x02 * 0 x02) + (b * 0 x02)總之，在GF(28)中，加法是異或操作。其乘法將分解成加法和用0 x02做的乘法，而用0 x02做的乘法是一個有條件的左移1比特位。AES規范中包括大量 有關GF(28)操作的附加信息。有限域GF(28)的加法和乘法類似DES，AES等算法中雙方都運用一樣

32、的密鑰進展加密解密，我們把這種加解密都運用同一個密鑰的密碼體制稱為對稱密碼體制。運用一樣的密鑰進展加密解密，密鑰的傳輸是一個重要的問題。所以，在公開的計算機網絡上平安地傳送和保管密鑰是一個嚴峻的問題。于是，密碼學家們想象了一個不一樣的的密碼體制來處理這一問題-公鑰加密算法。公鑰加密算法也稱非對稱密鑰算法，用兩對密鑰：一個公共密鑰和一個公用密鑰。用戶要保證公用密鑰的平安；公共密鑰那么可以發布出去。公共密鑰與公用密鑰是有嚴密關系的，用公共密鑰加密的信息只能用公用密鑰解密，反之亦然。由于公鑰算法不需求聯鑰效力器，密鑰分配協議簡單，所以極大簡化了密鑰管理。除加密功能外，公鑰系統還可以提供數字簽名。RS

33、A是其中的一種有效實現。RSA的根本指點思想是設計有效的單向陷門函數，來使得正向加密計算容易、沒有密鑰下的反向計算幾乎不能夠。RSA的平安性是建立在大整數分解的困難性上的。RSA算法假設Alice想要經過一個不可靠的媒體接納Bob的一條私人訊息。她可以用以下的方式來產生一個公鑰和一個私鑰：隨意選擇兩個大的質數p和q，p不等于q，計算N=pq。根據歐拉函數，求得r = (p-1)(q-1)選擇一個小于 r 的整數e，求得 e 關于模 r 的模反元素，命名為d。模反元素存在，當且僅當e與r互質將p和q的記錄銷毀。(N,e)是公鑰，(N,d)是私鑰。Alice將她的公鑰(N,e)傳給Bob，而將她的

34、私鑰(N,d)藏起來。公鑰與密鑰的產生假設Bob想給Alice送一個音訊m，他知道Alice產生的N和e。他運用起先與Alice約好的格式將m轉換為一個小于N的整數n，比如他可以將每一個字轉換為這個字的Unicode碼，然后將這些數字連在一同組成一個數字。假設他的信息非常長的話，他可以將這個信息分為幾段，然后將每一段轉換為n。用下面這個公式他可以將n加密為c：ne c (mod N)計算c并不復雜。Bob算出c后就可以將它傳送給Alice。加密音訊Alice得到Bob的音訊c后就可以利用她的密鑰d來解碼。她可以用以下這個公式來將c轉換為n：cd n (mod N)得到n后，她可以將原來的信息m

35、重新復原。解碼的原理是：cd ned(mod N)以及ed 1 (modp-1)和ed 1 (modq-1)。由費馬小定理可證明由于p和q是質數ned n (mod p)和ned n (mod q)這闡明由于p和q是不同的質數，所以p和q互質ned n (mod pq)解密音訊RSA也可以用來為一個音訊署名。假設甲想給乙傳送一個署名的音訊的話，那么她可以為她的音訊計算一個散列值(Message digest)，然后用她的密鑰(private key)加密這個散列值并將這個“署名加在音訊的后面。這個音訊只需用她的公鑰才干被解密。乙獲得這個音訊后可以用甲的公鑰解密這個散列值，然后將這個數據與他本人為這個音訊計算的散列值相比較。假設兩者相符的話，那么他就可以知道發信人持有甲的密鑰，以及這個音訊在傳播途徑上沒有被篡矯正。簽名音訊當p和q是一個大素數的時候，從它們的積pq去分解因子p和q，這是一個公認的數學難題。然而，雖然RSA的平安性依賴于大數的因子分解，但并沒有從實際上證明破譯RSA的難度與大數分解難度等價。1994年彼得秀爾Peter Shor證明一臺量子計算機可以在多項式時間內進展因數分解。假設量子計算機有朝一日可以成為一種可行的技術的話，那么秀爾的算法可以淘汰RSA和相關的衍生算法。即依賴于分解大整數困難性的加密算法另外，假設N的長度小于或等于256位，那么用一臺個人電