ECC Diffie-Hellman 密鑰交換算法

2021-03-02 網事如煙雲


ECC(5):ECC Diffie-Hellman 密鑰交換算法

關於 Diffie-Hellman 算法,請參見《漂洋過海來看你》,本文不再重複,本文只講述基於 ECC 構建的 Diffie-Hellman 密鑰交換算法。

無論是原生的還是基於 ECC 構建的,Diffie-Hellman 算法的場景和目標都是一樣的,如圖1所示。

  

圖1 Diffie-Hellman 算法的場景和目標

 

圖1講述的是對稱加密機制中密鑰交換(分發)的故事。對稱加密中,通信的雙方(加密/解密)使用的是相同的密鑰 K。密鑰 K 是對稱加密的靈魂,如果 K 洩密,那什麼樣的加密算法都沒有意義。

假設 A 生成了密鑰 K,他該用什麼方法告知 B 密鑰是 K 呢?通過明文將 K 發送給 B?顯然,這種方法非常容易洩密。用飛鴿傳書?似乎更加不可行 .

Diffie-Hellman 算法開創了密鑰安全分發的先河——更準確地說,是開創了公鑰加密的先河——圖1是對它的一個抽象表達。

A 通過明文給 B 發送了一個 x,B 也通過明文給 A 發送了一個 y。A 利用 x,B 利用 y,兩者獨立計算,但是他們所計算出的數值 K 相同,而其他人即使知道了 x 和 y(因為 x 和 y 都是明文傳輸,其他人很容易獲得),也無法計算出 K。

這就是 Diffie-Hellman 密鑰交換的基本思想——用於生產密鑰的原材料 x、y 都是公開的,卻能構建出安全的密鑰 K。

基於 ECC 的 Diffie-Hellman 算法,當然離不開橢圓曲線:Ep(a, b)。需要強調的是,這裡的 p,a,b 都是公開的。另外,在橢圓曲線上選擇一個點 G,G 也是公開的,只不過要求 G 的階數 s 要非常大——具體有多大,請參見《橢圓曲線的 G 點》。

基於橢圓曲線的計算公式:Q = kG,ECC 定義:

(1)k 是私鑰(k 也需要相當大)

(2)Q 是公鑰

ECC 的 Diffie-Hellman 算法,也是從這個公式出發。

首先,對於 A 來說,他選擇 kA 作為自己的私鑰,並且計算出相應的公鑰,

QA = kAG

對於 B 來說,也是同理。他選擇 kB 作為自己的私鑰,並且計算出相應的公鑰,

QB = kBG

下一步就是互相交換。A 將自己的公鑰 QA 通過明文發送給 B,B 將自己的公鑰 QB 發送給 A,如圖2所示。 

 

圖2 交換公鑰

 

因為 QA,QB 都是公鑰,所以圖2中,兩者的發送都是採用明文形式。

當 A 收到 B 發送過來的 QB 時,他做如下計算

PA = kA * QB

B 也如此,

PB = kB * QA

那麼,PA 和 PB 是什麼關係呢?我們繼續計算

PA = kA * QB  = kA * kB * G

PB = kB * QA  = kB * kA * G

可以看到,

PA = PB  = kA * kB * G

也就是說,

PA = PB  = K

K = kA * kB * G

這就意味著,A 和 B 通過互相交換的 QA 和 QB,殊途同歸,得到了同一個值 K,如圖3所示。 

 

圖3 計算密鑰

 

圖3對於攻擊者而言,由於只能知曉 QA 和 QB,根據橢圓曲線的數學難題,他是無法破解出 K 的。

所以,圖3中的 K(K = kA * kB * G),就可以作為 A 和 B 接下來做對稱加密通信時的對稱密鑰。

當然,K 是橢圓曲線上的一個點,它的表現形式是一個坐標(x,y),而對稱密鑰是一串數字(字符),K 若想稱為對稱密鑰,還需要經過編碼變換——這個話題,且聽下回分解。

 

 

相關焦點

  • ECC+RSA雙證書解決方案
    和RSA算法一樣,ECC算法也屬於公開密鑰算法。最初由Koblitz和Miller兩人於1985年提出,其數學基礎是利用橢圓曲線上的有理點構成Abel加法群上橢圓離散對數的計算困難性。  ECC算法的數學理論非常深奧和複雜,在工程應用中比較難於實現,但它的單位安全強度相對較高,它的破譯或求解難度基本上是指數級的,黑客很難用通常使用的暴力破解的方法來破解。
  • Diffie和Hellman分享2015年圖靈獎
    被廣泛使用的密鑰交換協議DH是以他們的名字命名的。圖靈獎被譽為計算機科學領域的諾貝爾獎,在獲得Google的捐贈後其獎金也達到了100萬美元。ACM主席Alexander L. Wolf稱,加密主題是今天媒體關注的中心,被視為事關國家安全,影響政府-私營部門的關係,吸引了數十億美元的資金投入到研究開發上。
  • 知識來了 | ECC橢圓曲線密碼學簡介
    ECC可以用於加密解密,但是由於其算法複雜計算速度慢,故萊迪思iCE40 UltraPlus系列晶片綜合使用ECDH算法進行密鑰交換,再通過AES進行消息的快速加密/解密助力於IoT故本文以iCE40 UltraPlus晶片的Security IP為例介紹ECDH密鑰交換。
  • 非對稱加密算法——RSA加密原理及數學推導
    是一種公開密鑰密碼體制。所謂的公開密鑰密碼體制就是使用不同的加密密鑰與解密密鑰,是一種「由已知加密密鑰推導出解密密鑰在計算上是不可行的」密碼體制。是由該算法設計者「Rivest、Shamir、Adleman」的名字構成,(可能看之前還認識「RSA」三個字母,看完後迷糊了。下面將詳細介紹。)
  • 之江實驗室與浙江大學聯合引進圖靈獎得主Whitfield Diffie教授
    朱世強主任致辭朱世強表示,此次聘任diffie教授開創了之江實驗室與浙江大學聯合引進國際頂尖科學家的首個成功案例,Diffie教授不僅能帶來網絡安全領域的新思想、新知識,也能帶動匯聚更多的網絡安全英才。
  • NSA真的破解了VPN中的Diffie-Hellman算法嗎
    密碼技術是公認的網絡信息安全的基礎技術,密碼算法及協議的安全性對於網絡信息安全系統及解決方案的安全性至關重要
  • 什麼是 RSA 算法
    如果密鑰洩露那麼再強大的對稱加密算法也是徒勞的,所以如何安全地交換對稱加密的規則和密鑰是短板。2.2 密鑰交換算法1976年兩位美國計算機學家 Whitfield Diffie 和 Martin Hellman,提出了一種嶄新構思,可以在不傳遞密鑰的情況下,完成解密,聽著很厲害的樣子,這難道就是江湖上傳說的隔空打牛?
  • 一文讀懂對稱加密算法、非對稱加密算法和Hash算法
    一、簡述常見的加密算法可以分成三類,對稱加密算法,非對稱加密算法和Hash算法。對稱加密指加密和解密使用相同密鑰的加密算法。對稱加密算法的優點在於加解密的高速度和使用長密鑰時的難破解性。假設兩個用戶需要使用對稱加密方法加密然後交換數據,則用戶最少需要2個密鑰並交換使用,如果企業內用戶有n個,則整個企業共需要n×(n-1) 個密鑰,密鑰的生成和分發將成為企業信息部門的惡夢。
  • 圖解|什麼是RSA算法
    如果密鑰洩露那麼再強大的對稱加密算法也是徒勞的,所以如何安全地交換對稱加密的規則和密鑰是短板。2.2 密鑰交換算法 1976年兩位美國計算機學家 Whitfield Diffie 和 Martin Hellman,提出了一種嶄新構思,可以在不傳遞密鑰的情況下,完成解密,聽著很厲害的樣子,這難道就是江湖上傳說的隔空打牛?
  • 世界頂級大師——圖靈獎得主、密碼學大牛Whitfield Diffie教授十月起將在浙大開課啦!
    他是公開密鑰加密算法和數字籤名機制的共同創建者,史上第一個基於公開密鑰加密的密鑰交換機制——Diffie-Hellman就是以他和他的合作者的名字命名的。公開密鑰加密是現代密碼學的基礎核心算法,連同數字籤名成為支撐當前加密系統和安全協議的基石。  簡單說,今天數字世界的安全主要依賴於Diffie教授當年的研究。
  • 9102年安全算法生存之道
    概述近年內隨著硬體提升CPU性能提高,GPU計算,大規模分布式計算機集群的投入,雲廠商計算密集型雲解決方案,以及密碼學研究的進步,使得大大降低了安全算法破解難度。一些以前認為固若金湯的加密算法,比如md5哈希算法,sha1算法都已經不再安全。那麼,現在都已經9102年了,我們應該怎麼選擇算法,以保證安全呢?
  • 三個牛逼的加密算法!
    DES算法入口參數•DES算法的入口參數有三個:Key、Data、Mode。其中Key為7個字節共56位,是DES算法的工作密鑰;Data為8個字節64位,是要被加密或被解密的數據;Mode為DES的工作方式,有兩種:加密或解密。算法步驟:•DES算法把64位的明文輸入塊變為64位的密文輸出塊,它所使用的密鑰也是56位,其算法主要分為兩步:1.
  • DES加密算法及其差分故障分析
    DES算法密鑰長為64位,但實際有效秘鑰長度是56位,另外8位(第8、16、24、32、40、48、56、64位)作為奇偶校驗位使用。分組後的明文組和56位的密鑰按位替代或交換的方法形成密文組。圖1為DES算法的加密流程圖。
  • 區塊鏈MOLDEX交換協議介紹
    在以太坊中,每個交易都以正確的順序 挖掘,然後發出交換對訂單對(交易中介),以確保智能合約上的餘額與交易餘額同步。 通過控制交易順序,MOLDEX 可以結合 DEX 安全性和可審計性提供集中交換的速度和 UX。 基於以上特徵,可以說 MOLDEX 具有以下特性。 不可信 關於分布式交換的重要事情是用戶管理私鑰。
  • 加密算法科普:des、aes加密、對稱、非對稱加密、Hash算法都是啥
    對稱密碼算法有時又叫傳統密碼算法、秘密密鑰算法或單密鑰算法,非對稱密碼算法也叫公開密鑰密碼算法或雙密鑰算法。對稱密碼算法的加密密鑰能夠從解密密鑰中推算出來,反過來也成立。在大多數對稱算法中,加密解密密鑰是相同的。它要求發送者和接收者在安全通信之前,商定一個密鑰。對稱算法的安全性依賴於密鑰,洩漏密鑰就意味著任何人都能對消息進行加密解密。只要通信需要保密,密鑰就必須保密。
  • 奧聯首席科學家程朝輝:基於標準算法的高效無證書密碼系統
    數字證書安全地將用戶身份和用戶密鑰綁定在一起。用戶在業務系統中先交換證書,然後使用公私鑰完成用戶的身份認證、訪問控制、信息安全傳遞等操作。但加密操作過程中數據發送方需要預先獲得接收方證書,進而獲取加密公鑰,相關過程較為複雜。因此,目前證書系統廣泛用於提供數字籤名服務,實現身份認證、數據一致性保護等。
  • 世界上迄今為止最安全的加密算法
    由於加密和解密使用同樣規則(簡稱」密鑰」),於是這種模式被稱為「對稱加密算法」。這種模式有一個最大弱點:甲方必須把密鑰告訴乙方,否則無法解密。保存和傳遞密鑰,就成了最頭疼的問題。這被稱為「Diffie-Hellman密鑰交換算法」。DH算法的出現有著劃時代的意義:從這一刻起,啟示人們加密和解密可以使用不同的規則,只要規則之間存在某種對應關係即可。這種新的模式也被稱為「非對稱加密算法」:(1)乙方生成兩把密鑰,公鑰和私鑰。
  • 重溫7種排序算法 第一篇,交換排序算法:冒泡排序、快速排序
    排序算法可分為以下幾類:    交換排序算法:冒泡排序、快速排序;    選擇排序算法:簡單選擇排序、堆排序;    插入排序算法:直接插入排序、希爾排序;    歸併排序算法。    主要做了以上7種排序算法的筆記,字數可能較多,所以分為幾篇。