中文字幕麻豆精品久久,曰曰骚aV一区,校园春色成人网

Diffie-Hellman 密鑰交換&ElGamal協(xié)議的安全密鑰交換

離散對(duì)數(shù)問(wèn)題

在整數(shù)中，離散對(duì)數(shù)是一種基于同余運(yùn)算和原根的一種對(duì)數(shù)運(yùn)算。而在實(shí)數(shù)中對(duì)數(shù)的定義 $log_b a$ 是指對(duì)于給定的 a 和 b，有一個(gè)數(shù) x，使得 $b^{x}$ = a。相同地在任何群 G中可為所有整數(shù) k定義一個(gè)冪數(shù)為 $b^{k}$ ，而離散對(duì)數(shù)是 $log_b a$ 指使得 $b^{x}$ = a的整數(shù) k。

離散對(duì)數(shù)在一些特殊情況下可以快速計(jì)算。然而，通常沒(méi)有具非常效率的方法來(lái)計(jì)算它們。公鑰密碼學(xué)中幾個(gè)重要算法的基礎(chǔ)，是假設(shè)尋找離散對(duì)數(shù)的問(wèn)題解，在仔細(xì)選擇過(guò)的群中，并不存在有效率的求解算法。

Diffie-Hellman 密鑰交換

Diffie-Hellman是一種建立密鑰的方法，而不是加密方法。然而，它所產(chǎn)生的密鑰可用于加密、進(jìn)一步的密鑰管理或任何其它的加密方式。Diffie-Hellman密鑰交換算法及其優(yōu)化首次發(fā)表的公開(kāi)密鑰算法出現(xiàn)在Diffie和Hellman的論文中，這篇影響深遠(yuǎn)的論文奠定了公開(kāi)密鑰密碼編碼學(xué)。

這種密鑰交換技術(shù)的目的在于使得兩個(gè)用戶(hù)安全地交換一個(gè)秘密密鑰以便用于以后的報(bào)文加密. Diffie-Hellman密鑰交換算法的有效性依賴(lài)于計(jì)算離散對(duì)數(shù)的難度。

主要過(guò)程

所有用戶(hù)都知道的全局參數(shù)
- 大素?cái)?shù)q
- g : 用來(lái)模q的原始根
每個(gè)用戶(hù)生成自己的公鑰(對(duì)于用戶(hù)A)
- 選擇一個(gè)密鑰，(私鑰)：數(shù)字 $x_{A}$ <q
- 計(jì)算公鑰： $y_{A}=g^{x_{A}}\mod q$
- 每個(gè)用戶(hù)公開(kāi)公鑰
則用戶(hù)A&B共享的會(huì)話密鑰是 $K_{AB}$

$K_{AB}=g^{x_{A}· x_{B}} \mod q$

? $=y_{A}^{x_{B}}\mod q$ (B可以計(jì)算出來(lái))

? $=y_{B}^{x_{A}}\mod q$ (A可以計(jì)算出來(lái))

From WIKI：

最簡(jiǎn)單，最早提出的這個(gè)協(xié)議使用一個(gè)質(zhì)數(shù)p的整數(shù)模n乘法群)以及其原根g。下面展示這個(gè)算法，綠色表示非秘密信息, 紅色粗體表示秘密信息

原理.png

愛(ài)麗絲和鮑伯寫(xiě)上一個(gè)有限循環(huán)群 G 和它的一個(gè)生成元 g。（這通常在協(xié)議開(kāi)始很久以前就已經(jīng)規(guī)定好； g是公開(kāi)的，并可以被所有的攻擊者看到。）
愛(ài)麗絲選擇一個(gè)隨機(jī)自然數(shù) a(很大) 并且將 $g^{a}\mod p$ （大素?cái)?shù)）發(fā)送給鮑伯。
鮑伯選擇一個(gè)隨機(jī)自然數(shù) b （很大）并且將 $g^\mod p$ 發(fā)送給愛(ài)麗絲。
愛(ài)麗絲計(jì)算 $(g^)^{a} \mod p$ 。
鮑伯計(jì)算 $(g^{a})^ \mod p$ 。

愛(ài)麗絲和鮑伯就同時(shí)協(xié)商出群元素 $g^{ab}$ ，它可以被用作共享秘密。 $(g^)^{a}$ 和 $(g^{a})^$ 因?yàn)槿撼朔ń粨Q的。

算法解釋

愛(ài)麗絲和鮑伯最終都得到了同樣的值，因?yàn)樵谀下 $g^{ab}$ 和 $g^{ba}$ 相等。注意a, b 和 $g^{ab}= g^{ba} \mod p$ 是秘密的。其他所有的值 – p, g, $g^{a} \mod p$ , 以及 $g^\mod p$ – 都可以在公共信道上傳遞。一旦愛(ài)麗絲和鮑伯得出了公共秘密，他們就可以把它用作對(duì)稱(chēng)密鑰，以進(jìn)行雙方的加密通訊，因?yàn)檫@個(gè)密鑰只有他們才能得到。

Elgamal密碼體制

1984年，T.Elgamal提出了一種基于離散對(duì)數(shù)的公開(kāi)密鑰體制，是一個(gè)基于迪菲-赫爾曼密鑰交換的非對(duì)稱(chēng)加密算法。ElGamal密碼體系應(yīng)用于一些技術(shù)標(biāo)準(zhǔn)中，如數(shù)字簽名標(biāo)準(zhǔn)（DSS）和S/MIME電子郵件標(biāo)準(zhǔn)。與Diffie-Hellman一樣，ElGamal的系統(tǒng)用戶(hù)也是共同選擇一個(gè)素?cái)?shù)q， $g$ 是q的素跟。

算法描述

ElGamal加密算法由三部分組成：密鑰生成、加密和解密。

密鑰生成

密鑰生成步驟如下：

Alice利用生成元 $g$ 產(chǎn)生一個(gè) q,階循環(huán)群 $G$ ,的有效描述。該循環(huán)群需要滿足一定的安全性質(zhì)。
Alice從 $\{1,\cdots,q-1\}$ 中隨機(jī)選擇一個(gè) $x$ 。
Alice計(jì)算 $h:=g^{x} \mod q$ 。
Alice公開(kāi) $h$ ,以及 $G,q,g$ 的描述作為其公鑰，并保留 $x$ 作為其私鑰。私鑰必須保密。

加密

其他用戶(hù)可以通過(guò)Alice的公鑰進(jìn)行加密。

用Alice的公鑰 $(G,q,g,h)$ 向她加密一條消息 m的加密算法工作方式如下：

將信息表示成一個(gè)整數(shù)M，其中 $1\leq M \leq q-1$ ，以分組密碼序列的方式來(lái)發(fā)送信息，其中每個(gè)分塊的長(zhǎng)度不小于整數(shù)q。
Bob從 $\{1,\cdots,q-1\}$ 隨機(jī)選擇一個(gè) $y$ 。（私鑰）
然后計(jì)算密鑰 $K=h^{y} \mod q$ 。（會(huì)話密鑰）
將M加密成明文對(duì) $，(C_{1}，C_{2})$ ，其中

$C_{1}=g^{y} \mod q ; C_{2}=K\cdot M \mod q$ （公鑰，加密的信息）