【笔记】公钥密码学之基于离散对数的密码体制
目錄
- 一、前言
- 二、代數基本知識
- 2.1群
- 2.1.1定義
- 2.1.2循環群
- 2.1.3加法循環群
- 2.2環
- 2.2.1定義
- 2.2.2交換環
- 2.2.3整環
- 2.3域
- 2.4有限域
- 2.5多項式環
- 三、加密算法
- 3.1.ZpZ~p~Z?p?上的離散對數問題
- 3.2ElGamal算法
- 3.3Diffie-Hellman算法
- 3.4橢圓曲線密碼
- 四、相關賽題
- 4.1
一、前言
在公鑰加密體系中,除了基于大整數分解問題的RSA加密體制,另一類重要的加密體制是基于離散對數的難解性,如ECC橢圓曲線加密、Diffie-Hellman算法、ElGamal算法等。為了解決離散對數問題,本文首先介紹一些近世代數的基本知識,之后介紹幾類基于離散對數的加密體制,最后列出幾道CTF中的相關賽題。
二、代數基本知識
2.1群
2.1.1定義
設G是非空集合,若在G內定義一種代數運算?,且滿足下列4個條件,則稱G(對運算?)構成一個群:
- 封閉性:對任意的a,ba,ba,b ∈\in∈GGG,恒有a?ba?ba?b∈\in∈GGG;
- 結合律:對任意的a,b,ca,b,ca,b,c∈\in∈GGG,恒有(a?b)?c=a?(b?c)(a?b)?c = a?(b?c)(a?b)?c=a?(b?c)
- 有單位元:存在eee∈\in∈GGG,對任意的aaa∈\in∈GGG,有 a?e=e?a=aa?e=e?a=aa?e=e?a=a
- 每個元存在逆元:對任意aaa∈\in∈GGG,存在bbb∈\in∈GGG,使得 a?b=b?a=ea?b=b?a=ea?b=b?a=e,稱 bbb 為 aaa 的逆元。
其中運算???可以是通常的乘法或者是加法。若???為乘法,則稱GGG為乘法群,單位元記為111。若???為加法,則稱GGG為加法群,單位元記為000。
一般情況下,記:a?a?…?a?k個\underbrace{a?a?…?a}_{k個}k個a?a?…?a??=aaak
群 GGG所含元素的個數,稱為該群的階。 若群GGG含有有限個元素,則稱GGG為有限群,否則,為無限群。
若對群GGG中任何a,ba,ba,b∈\in∈GGG,有 a?b=b?aa?b = b?aa?b=b?a,則稱GGG為交換群或AbelAbelAbel群。
2.1.2循環群
定義:設(G,?)(G,· )(G,?)是一個群,如果群GGG中存在一個元素α\alphaα,使得對群GGG任意元素bbb都存在一個整數iii,使得b=b=b=aaai則我們稱GGG是一個循環群。元素α\alphaα是GGG的一個生成元。
2.1.3加法循環群
整數的加法群是一個無限循環群,它由1生成。在這種情況下,冪被解釋為用加法合成的,因此nnn是1的n次冪。
例:(Z6,?\bigoplus?)是循環群,其中Z6={0,1,2,3,4,5},?\bigoplus?為模6加法,其中生成元為1或5。
生成元的含義可以理解為:1或5的加法,可以實現群Z6內所有的元素。
5 mod 6 = 5,35 mod 6 = 5
10 mod 6 = 4,40 mod 6 = 4,
15 mod 6 = 3,45 mod 6 = 3
20 mod 6 = 2,50 mod 6 = 2
25 mod 6 = 1,55 mod 6= 1
30 mod 6 = 0,60 mod 6= 0
所以通過生成元5的模6加法,可以得到群內的所有元素,實現循環群。而2,3,4不能作為生成元,是因為這些元素的模6加法并不能得到群內的所有元素,而且并不是連續循環的數。
乘法循環群也是同樣的道理。
有限循環群的生成元還具有以下性質:
(元素的階):循環群(G,?)(G,·)(G,?),α\alphaα為GGG的一個生成元,111為GGG的單位元,GGG的階為nnn,則:aaan=1=1=1
2.2環
2.2.1定義
若集合RRR上定義了兩種二元運算:+++(加法)和x(乘法),且滿足下列四個條件,則稱RRR 對這兩種運算構成了一個環,記為(R,+,x)(R,+,x)(R,+,x):
- (R,+)(R,+)(R,+)是一個Abel群,RRR關于加法是一個交換群,其恒等元為零元,用000表示。
- 乘法的封閉性:如果aaa和bbb都屬于RRR,則ababab也屬于RRR。
- 乘法的結合律:對于RRR中的任意元素a、b、ca、b、ca、b、c,有a(be)=(ab)ca(be) =(ab)ca(be)=(ab)c成立。
- 分配律:對于RRR中的任意元素a、b、ca、b、ca、b、c,下面兩個式子總成立:a(b+c)=ab+aca(b+c) = ab+ aca(b+c)=ab+ac;(a+b)c=ac+be(a+b)c=ac+be(a+b)c=ac+be
本質上說,環就是一個集合,我們可以在其上進行加法、減法[a?b=a+(?b)][a - b = a + ( - b ) ][a?b=a+(?b)]和乘法而不脫離該集合。
例:實數上所有n階方陣的集合關于加法和乘法構成一個環。
2.2.2交換環
定義:環如果還滿足乘法的交換律,即對于RRR中任意元素a、ba、ba、b,有ab=baab=baab=ba成立,則被稱為是交換環
例:偶整數集合(包括正數、負數和0)記為SSS,在普通加法和乘法運算下是交換環;實數上所有n階方陣的集合關于加法和乘法則不構成一個交換環。
2.2.3整環
定義:整環是滿足以下公理的交換環:
例:普通加法和乘法運算下的整數集合(包括正數、負數和0)是一個整環。
2.3域
定義:設FFF是一個交換環,若FFF中的所有的非零元素對乘法都存在逆元,則FFF稱為一個域。如果一個域所包含的元素是有限的則稱此域是有限域,否則稱為無限域。有限域中所含元素的個數稱為有限域(R,+,x)(R,+,x)(R,+,x)的階。
本質上說,域就是一個集合,我們可以在其上進行加法、減法、乘法和除法而不脫離該集合。
除法又按以下規則來定義: a/b=a(a/b=a(a/b=a(bbb-1)))。
例:有理數集合、實數集合以及復數集合都是域。而所有整數的集合并不是一個域,因為并不是集合中所有的元素都有乘法逆元;實際上,整數集合中只有元素111和?1-1?1有乘法逆元。
群、環、域的公理總結:
2.4有限域
定義1: 有限域又常稱為GaloisGaloisGalois域,并以GF(q)GF(q)GF(q)或FqF~q~F?q?表示,其中qqq表示有限域的階。
定義2: 設F1、F2F~1~、F~2~F?1?、F?2?是兩個域,稱F1F~1~F?1?到F2F~2~F?2?的一個可逆映射σ\sigmaσ為一個同構(映射),如果σ\sigmaσ是保持運算的映射,即對任意的a,ba,ba,b∈\in∈F1F~1~F?1?,有:σ\sigmaσ(a + b) = σ\sigmaσ(a) + σ\sigmaσ(b),σ\sigmaσ(a · b)=σ\sigmaσ(a) · σ\sigmaσ(b)
定理3: 設FFF是有限域,則有:
2.5多項式環
定義: 設FFF是一個域,多項式f(x)=anxn+···+a1x+a0,其中aia_iai?∈\in∈FFF,nnn∈\in∈NNN。
若an=?0a_n\not=0an??=0,稱nnn為該多項式的次數,稱為首項系數。
對于域FFF上xxx的多項式的全體組成的集合記為 F[x]F[x]F[x]。多項式a(x)a(x)a(x) 的次數記為deg(a(x))deg(a(x))deg(a(x))
設存在多項式f(x)f(x)f(x)與g(x)g(x)g(x),滿足:
- 加法運算:f(x)+g(x)f(x)+g(x)f(x)+g(x)∈\in∈F[x]F[x]F[x]
- 乘法運算:f(x)?g(x)f(x)·g(x)f(x)?g(x)∈\in∈F[x]F[x]F[x]
容易驗證F[x]F[x]F[x]對這樣定義的多項式加法與乘法構成一個交換環,稱為多項式交換環。
不可約多項式: 設f(x)f(x)f(x)是F[x]F[x]F[x]上的一個次數大于零的多項式,如果它不能分解成兩個低次數的多項式的乘積,則稱f[x]f[x]f[x]是FFF上的不可約多項式。
三、加密算法
3.1.ZpZ~p~Z?p?上的離散對數問題
ZpZ~p~Z?p?上的離散對數問題是指對于循環群 ZpZ~p~Z?p?(p是一個素數),α\alphaα是群ZpZ~p~Z?p?的生成元,對于任意的ccc∈\in∈ZpZ~p~Z?p?尋找唯一 的整數 ddd (0(0(0 ≤\leq≤ ddd ≤\leq≤ p?1)p-1)p?1)滿足:C≡ad(modp)C≡a^d(modp)C≡ad(modp)
我們把整數ddd記為logloglogαccc,并稱之為離散對數。
3.2ElGamal算法
背景: ElGamal是建立在解有限乘法群上的離散對數問題的困難性基礎上的一種公鑰密碼體制。
算法描述:
- 公開參數:取大素數 ppp,并取α\alphaα是乘法群ZpZ~p~Z?p?* { 1,…,p?11,…,p-11,…,p?1 }的一個生成元。
- 密鑰生成:隨機選取整數d:0<d<(p?1)d:0 < d < ( p - 1)d:0<d<(p?1)并計算β\betaβ=α\alphaαd modpmod pmodp。其中公開參數:ppp和α\alphaα ;公鑰:β\betaβ;私鑰:ddd
- 加密運算:對于明文mmm,選取隨機整數k:0<k<(p?1)k:0<k<(p-1)k:0<k<(p?1),計算:c1=c_1=c1?=α\alphaαkmodpmod pmodp, c2=mc_2=mc2?=mβ\betaβkmodpmod pmodp,得到密文c=(c1,c2)c=(c_1,c_2)c=(c1?,c2?)。
- 解密運算:對于密文c=(c1,c2)c=(c_1,c_2)c=(c1?,c2?),用私鑰ddd解密。m=c2m=c_2m=c2?(c1(c_1(c1?d)))-1modpmod pmodp
計算離散對數的算法:
- Shanks算法
- 小步大步發(baby-step 、giant-step)算法
- Pohlig-Hellman算法
- 指數演算法(index-calculus)
3.3Diffie-Hellman算法
背景: Diffie-Hellman算法由Whitfield Diffie 和 Martin Hellman 提出,該算法的安全性也是基于一般有限域上的離散對數問題的難解性。該算法的目的是使兩個用戶能安全地交換密鑰,以便在后續的通信中用該密鑰對消息加密。該算法本身只限于進行密鑰交換。
算法描述:
3.4橢圓曲線密碼
四、相關賽題
4.1
題目鏈接buu平臺
#!/usr/bin/env python # -*- coding: utf-8 -*- from Crypto.Util.number import * import randomn = 2 ** 512 m = random.randint(2, n-1) | 1 c = pow(m, bytes_to_long(flag), n) print 'm = ' + str(m) print 'c = ' + str(c)# m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075 # c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499加密過程為:c = pow(m, bytes_to_long(flag), n)
即已知c, m, n求離散對數:bytes_to_long(flag) = log(mmodn) (c mod n)
題解:
m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075 c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499 n = 2 ** 512 import sympy from Crypto.Util.number import * flag=sympy.discrete_log(n,c,m) print(long_to_bytes(flag))總結
以上是生活随笔為你收集整理的【笔记】公钥密码学之基于离散对数的密码体制的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: SAGE(SAGEMATH)密码学基本使
- 下一篇: MATLAB算法(函数)编译为C++动态