密碼學(xué)常見困難問(wèn)題

大整數(shù)因數(shù)分解問(wèn)題

1）給定兩個(gè)素?cái)?shù)p,q,計(jì)算乘積p·q=n很容易；
2）給定大整數(shù)n，求n的素因素p,q使得n=p·q非常困難.

DLP：The Discrete Logarithm Problem 離散對(duì)數(shù)問(wèn)題

讓G為一個(gè)阿貝爾群(交換群).我們把G中的二元操作寫成乘法*.

1）給定G,g和h=g^a,計(jì)算a是困難的.

2）這里a就叫做h的以g為底的離散對(duì)數(shù).

CDH：The Computational Diffie-Hellman Problem 計(jì)算DH問(wèn)題

CDH是基于由Whit Diffie和Martin Hellman提出的兩方協(xié)商密鑰在公共信道上不會(huì)被竊取的問(wèn)題:

1）Alice和Bob共同確定使用的循環(huán)群G,和生成器q
2）Alice選擇一個(gè)隨機(jī)的密鑰整數(shù)a,Bob選擇了一個(gè)隨機(jī)的整數(shù)b
3）Alice計(jì)算g^a 在公共信道上發(fā)送給Bob,同時(shí)Bob也計(jì)算出 g^b在公共信道上發(fā)送給Alice.
4）Alice和Bob都計(jì)算g^ab=(g^a)^b=(g^b)^a通過(guò)知道他們自己的隨機(jī)的整數(shù),這個(gè)生成的就是他們協(xié)商的密鑰.
密鑰g^ab是一個(gè)能被用于Alice和Bob之間的對(duì)稱加密.
但是有一些人竊聽了他們之間的交換獲得了G,g,g^a,g^b.

給定G,g,g^a,g^b,多項(xiàng)式時(shí)間內(nèi)找出g^ab

DDH：The Decisional Diffie-Hellman Problem 決策Diffie-Hellman問(wèn)題

用于證明難以區(qū)分的屬性.假如說(shuō)Alice和Bob執(zhí)行如上所述的Diffie-Hellman密鑰協(xié)議,那么G,g,g^a,g^b都是公共的,g^ab是密鑰.直觀上,DDH問(wèn)題就是是否對(duì)手能夠從隨機(jī)的G中的元素區(qū)分出Alice和Bob的密鑰g^ab.正式來(lái)說(shuō):

給定G,g,g^a,g^b和T_x使得T₀是G中隨機(jī)的一個(gè)元素,T₁=g^ab同時(shí)x被隨機(jī)均勻的從{0,1}中選擇,找出x.

盡管不能直接計(jì)算出來(lái).而且很明顯,如果對(duì)手能解決CDH問(wèn)題,那么它可以有效率的解決DDH,因?yàn)樗呀?jīng)可以得到gab的值.這意味著,CDH至少和DDH一樣難.

困難性進(jìn)行排序:DLP>,CDH>DDH
DLP有時(shí)候是簡(jiǎn)單的,會(huì)讓CDH和DDH都變簡(jiǎn)單.因此群G和生成器g的選擇在做密碼學(xué)的時(shí)候是十分重要的!

GDH：Gap Diffie-Hellman

給定三元組（g,g^a,g^b）,a,b屬于Z^*_q,在DDH（·）預(yù)言機(jī)的輔助下計(jì)算g^ab是困難的

BDH：雙線性DH問(wèn)題

給定四元組（P,aP,bP,cP）,a,b,c屬于Z^*_q,判斷等式e(P,P)^d = e(P,P)^abc是困難的

CBDH :Comptational Bilinear Diffie-Hellman Problem 計(jì)算雙線性DH問(wèn)題

給定輸入G,g,g^a,g^b，計(jì)算輸出e(g,g)^ab是困難的

DBDH：Decisional Bilinear Diffie-Hellman 判斷雙線性DH問(wèn)題

給定輸入G,g,g^a,g^b，g^c找出 e(g,g)^ab是困難的

GBDH：Gap 雙線性DH問(wèn)題

給定四元組（P,aP,bP,cP）,a,b,c屬于Z^*_q,在DBDH（·）預(yù)言機(jī)的輔助下計(jì)算e(P,P)^abc是困難的

KEAI

CDHI :Computation Diffie-Hellman Inverse Problem計(jì)算DH逆問(wèn)題

給定g^x屬于G，x未知，輸出(g^x)^-1是困難的，CDHI和CDH問(wèn)題等價(jià)

ECDLP：Elliptic Curve Discrete Logarithm Problem,橢圓曲線離散對(duì)數(shù)問(wèn)題

橢圓曲線上的離散對(duì)數(shù)問(wèn)題，兩個(gè)元素P,Q屬于G₁求整數(shù)a屬于Z_q^*使得，Q = aP成立是困難的

BCDH

任意選取(a,b,c)，在多項(xiàng)式時(shí)間內(nèi)計(jì)算出??^??????

BDDH

任意選取(a,b,c,d), 在多項(xiàng)式時(shí)間內(nèi)將(??^??, ??^??, ??^??, ??^??????)和(??^??, ??^??, ??^??, ??^??)兩者明顯的區(qū)分開來(lái)。

一個(gè)具有注腳的文本。¹

到了這里，關(guān)于密碼學(xué)常見困難問(wèn)題DLP,CDH,DDH,GDH,BDH,CBDH,DBDH,GBDH，更新中的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！