資訊專欄INFORMATION COLUMN
摘要：本文首發(fā)于深入淺出區(qū)塊鏈社區(qū)原文鏈接非對稱加密技術算法數(shù)學原理分析原文已更新，請讀者前往原文閱讀非對稱加密技術，在現(xiàn)在網(wǎng)絡中，有非常廣泛應用。加密技術更是數(shù)字貨幣的基礎。
本文首發(fā)于深入淺出區(qū)塊鏈社區(qū)
原文鏈接:非對稱加密技術 - RSA算法數(shù)學原理分析原文已更新，請讀者前往原文閱讀非對稱加密技術，在現(xiàn)在網(wǎng)絡中，有非常廣泛應用。加密技術更是數(shù)字貨幣的基礎。
所謂非對稱，就是指該算法需要一對密鑰，使用其中一個（公鑰）加密，則需要用另一個（私鑰）才能解密。
但是對于其原理大部分同學應該都是一知半解，今天就來分析下經(jīng)典的非對稱加密算法 - RSA算法。
通過本文的分析，可以更好的理解非對稱加密原理，可以讓我們更好的使用非對稱加密技術。
題外話:
本博客一直有打算寫一系列文章通俗的密碼學，昨天給站點上https, 因其中使用了RSA算法，就查了一下，發(fā)現(xiàn)現(xiàn)在網(wǎng)上介紹RSA算法的文章都寫的太難理解了，反正也準備寫密碼學，就先寫RSA算法吧，下面開始正文。
RSA算法的基于這樣的數(shù)學事實：兩個大質(zhì)數(shù)相乘得到的大數(shù)難以被因式分解。
如：有很大質(zhì)數(shù)p跟q，很容易算出N，使得 N = p * q，
但給出N, 比較難找p q（沒有很好的方式， 只有不停的嘗試）
這其實也是單向函數(shù)的概念
下面來看看數(shù)學演算過程：
1、 選取兩個大質(zhì)數(shù)p，q，計算N = p q 及 φ ( N ) = φ (p) φ (q) = (p-1) * (q-1)
三個數(shù)學概念：
質(zhì)數(shù)(prime numbe)：又稱素數(shù)，為在大于1的自然數(shù)中，除了1和它本身以外不再有其他因數(shù)。
互質(zhì)關系：如果兩個正整數(shù)，除了1以外，沒有其他公因子，我們就稱這兩個數(shù)是互質(zhì)關系（coprime）。
φ(N)：叫做歐拉函數(shù)，是指任意給定正整數(shù)N，在小于等于N的正整數(shù)之中，有多少個與N構成互質(zhì)關系。如果n是質(zhì)數(shù)，則 φ(n)=n-1。
如果n可以分解成兩個互質(zhì)的整數(shù)之積， φ(n) = φ(p1p2) = φ(p1)φ(p2)。即積的歐拉函數(shù)等于各個因子的歐拉函數(shù)之積。
2、選擇一個大于1 小于φ(N)的數(shù)e，使得 e 和 φ(N)互質(zhì)
e其實是1和φ(N)之前的一個質(zhì)數(shù)
3、 計算d，使得de=1 mod φ(N) 等價于方程式 ed-1 = k φ(N) 求一組解。
d 稱為e的模反元素，e 和 φ(N)互質(zhì)就肯定存在d。
模反元素是指如果兩個正整數(shù)a和n互質(zhì)，那么一定可以找到整數(shù)b，使得ab被n除的余數(shù)是1，則b稱為a的模反元素。
可根據(jù)歐拉定理證明模反元素存在，歐拉定理是指若n,a互質(zhì)，則：
a^φ(n) ≡ 1(mod n) 及 a^φ(n) = a * a^（φ(n) - 1）， 可得a的 φ(n)-1 次方，就是a的模反元素。
4、 (N, e)封裝成公鑰，(N, d)封裝成私鑰。
假設m為明文，加密就是算出密文c:
m^e mod N = c (明文m用公鑰e加密并和隨機數(shù)N取余得到密文c)
解密則是：
c^d mod N = m (密文c用密鑰解密并和隨機數(shù)N取余得到明文m) > 私鑰解密這個是可以證明的，這里不展開了。加解密步驟
具體還是來看看步驟，舉個例子，假設Alice和Bob又要相互通信。
Alice 隨機取大質(zhì)數(shù)P1=53，P2=59，那N=53*59=3127，φ(N)=3016
取一個e=3，計算出d=2011。
只將N=3127，e=3 作為公鑰傳給Bob（公鑰公開）
假設Bob需要加密的明文m=89，c = 89^3 mod 3127=1394，于是Bob傳回c=1394。 （公鑰加密過程）
Alice使用c^d mod N = 1394^2011 mod 3127，就能得到明文m=89。 （私鑰解密過程）
假如攻擊者能截取到公鑰n=3127，e=3及密文c=1394，是仍然無法不通過d來進行密文解密的。
安全性分析那么，有無可能在已知n和e的情況下，推導出d？
1. ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。 2. φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。 3. n=pq。只有將n因數(shù)分解，才能算出p和q。
如果n可以被因數(shù)分解，d就可以算出，因此RSA安全性建立在N的因式分解上。大整數(shù)的因數(shù)分解，是一件非常困難的事情。
只要密鑰長度足夠長，用RSA加密的信息實際上是不能被解破的。
模運算加減法：
(a + b) mod p = (a mod p + b mod p) mod p
(a - b) mod p = (a mod p - b mod p) mod p
模運算乘法：
(a b) mod p = (a mod p b mod p) mod p
模運算冪
a ^ b mod p = ((a mod p)^b) mod p
? 深入淺出區(qū)塊鏈 - 系統(tǒng)學習區(qū)塊鏈，打造最好的區(qū)塊鏈技術博客。
? 我的知識星球為各位解答區(qū)塊鏈技術問題，歡迎加入討論。
? 關注公眾號“深入淺出區(qū)塊鏈技術”第一時間獲取區(qū)塊鏈技術信息。
文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉載請注明本文地址：http://www.ezyhdfw.cn/yun/24071.html
摘要：二如何理解公鑰和私鑰非對稱加密算法需要兩個密鑰公開密鑰和私有密鑰。因為加密和解密使用的是兩個不同的密鑰，所以這種算法叫作非對稱加密算法。三非對稱加密解密原理非對稱加密算法中，常用的就是算法了，以下就以算法為例來講解非對稱加密算法的實現(xiàn)原理。 非對稱加密，在現(xiàn)在網(wǎng)絡應用中，有這非常廣泛的場景，更是加密貨幣的基礎。本文主要介紹非對稱加密、解密的原理和過程，以及在區(qū)塊鏈中的使用。 一、非對稱...
摘要：公開密鑰加密的出現(xiàn)大大減輕了交換對稱密鑰的困難，公鑰可以公開透過不安全可被竊聽的渠道發(fā)送，用以加密明文。當與配合使用，稱之為，與配合則稱為，以此類推。這步?jīng)]有簽名，服務端收到數(shù)據(jù)后不會發(fā)現(xiàn)被篡改。對于認證機構，一旦私鑰外泄，將可能導致整未濟，亨。小狐汔濟，濡其尾，無攸利。——《易》六、密鑰管理當不再擔心身份會被冒充、篡改之后，我們再來詳細談談網(wǎng)絡通信中對于加密算法的密鑰管理。在密鑰被簽發(fā)后，...
摘要：系列密碼學二傳送門密碼學一基礎密碼學算法分類消息編碼消息摘要類，類，對稱密碼非對稱密碼數(shù)字簽名五元組明文原始信息。非對稱密碼包提供給，，等非對稱加密算法。對稱加密算法在分布式網(wǎng)絡系統(tǒng)上使用較為困難，主要是因為密鑰管理困難，使用成本較高。 前言 最近一場面試，面試官問了我 對稱加密與非對稱加密的問題，雖然曾經(jīng)看過一些內(nèi)容，但是沒有系統(tǒng)的整理，所以當被問的時候，腦子里一片空白，沒有回答上...
摘要：算法公鑰加密算法是年由羅納德李維斯特阿迪薩莫爾和倫納德阿德曼一起提出的。是目前最有影響力的公鑰加密算法，它能夠抵抗到目前為止已知的絕大多數(shù)密碼攻擊，已被推薦為公鑰數(shù)據(jù)加密標準。 上篇文章介紹了對稱加密的原理，但是它的最大問題就是加密和解密的密鑰是相同的，并且不能保證密鑰能安全的送到雙方手里，即使安全的送到雙方手里，免不了內(nèi)部會有臥底的存在 非對稱加密 既然有對稱加密，那么自然會聯(lián)想到非...
摘要：假如黎曼猜想被證實，區(qū)塊鏈將毀滅近日，黎曼猜想四個字瘋狂刷屏。黎曼猜想由數(shù)學家波恩哈德黎曼于年提出。因此，黎曼猜想一旦被證明，則意味著素數(shù)之密被解開，算法也就將被攻破了。而大多數(shù)區(qū)塊鏈所用的加密算法不是，而是橢圓曲線加密算法。 瑪麗女王的密碼之生死命懸一線 showImg(https://segmentfault.com/img/bVbhD7s?w=740&h=876); 16世紀伊麗...
閱讀 4076·2021-11-22 13:53
閱讀 1774·2021-09-23 11:52
閱讀 2534·2021-09-06 15:02
閱讀 1093·2019-08-30 15:54
閱讀 954·2019-08-30 14:15
閱讀 2438·2019-08-29 18:39
閱讀 760·2019-08-29 16:07
閱讀 554·2019-08-29 13:13
