現(xiàn)代密碼學(xué)(中山大學(xué))Lecture14Lecture11

1、現(xiàn)代密碼學(xué)現(xiàn)代密碼學(xué)Modern Cryptography張方國中山大學(xué)信息科學(xué)與技術(shù)學(xué)院第十一講第十一講 公鑰密碼學(xué)（二）公鑰密碼學(xué)（二） Rabin加密加密 ElGamal加密加密 Pailler加密方案加密方案 同態(tài)加密同態(tài)加密The Rabin SystemTheorem. Let n=pq be the product of two distinct odd primes p, q. If , then has no solutions or exactly four solutions.(ii) Let r, s be a solution of , respectively, t

2、hen the four solutions of are (aps+bqr); -(aps+bqr); (aps-bqr); -(aps-bqr), wherea, b satisfy ap+bq=1.(iii) If , then is a solution of 4mod3ppcpmod4/ )1( ncxmod2pcxmod2qcxmod2pcxmod2*nZcThe Rabin System Set-up of the Rabin System Choose two distinct primes p, q s.t. and put n=pq. Encryption function

3、 4mod3 qpnnZZnxxe:mod)(2The Rabin SystemEncryption algorithm: Have to solve to find m!)(mod2nmcmncxmod2Decryption algorithm: step 1: Find a, b s.t. ap+bq=1 using the Euclidean algorithm. step 2: put step 3: Compute qcspcrqpmod,mod4/ )1(4/ )1(nbqrapsnbqrapsmod)(,mod)(The Rabin SystemClaim: ,are four

4、roots of ncxmod2 and m is one of these four. Chose one which makes sense!The Rabin Systemncxmod2 Theorem : Solving for all is equivalent to factoring n.nZc Cryptanalysis El Gamal 公鑰加密方案公鑰加密方案 Diffie-Hellman key distribution scheme 的變形 能夠用于安全交換密鑰 published in 1985 by ElGamal: T. ElGamal, A Public Key

5、 Cryptosystem and a Signature Scheme Based on Discrete Logarithms, IEEE Trans. Information Theory, vol IT-31(4), pp469-472, July 1985. 安全性是基于離散對(duì)數(shù) 缺點(diǎn)：增加了消息長度（2倍） 密鑰建立 密鑰生成：密鑰生成： 選取一個(gè)大素?cái)?shù)p及本原元a mod p 接收者 Bob有一個(gè)密秘鑰 xB 計(jì)算 yB = axB mod p El Gamal 加密加密 為加密 M 發(fā)送者選擇隨機(jī)數(shù)k, 0=k=p-1 計(jì)算消息密鑰 K : K = yBk mod p 計(jì)算密文

6、對(duì): C = C1,C2 C1 = ak mod p C2 = K.M mod p 發(fā)送到接收者El Gamal 解密解密 首先計(jì)算 message key K K = C1xB mod p = ak.xB mod p 計(jì)算明文: M = C2.K-1 mod p ElGamal的安全性 引理引理 如果如果DDH問題是困難的，那么問題是困難的，那么ElGamal加密體制在選擇明文攻擊下加密體制在選擇明文攻擊下是多項(xiàng)式安全的。是多項(xiàng)式安全的。證明：為了顯示證明：為了顯示ElGamal是多項(xiàng)式安全的，我們首先假設(shè)存在一個(gè)能夠攻破是多項(xiàng)式安全的，我們首先假設(shè)存在一個(gè)能夠攻破ElGamal多項(xiàng)式安全性

7、的多項(xiàng)式時(shí)間算法多項(xiàng)式安全性的多項(xiàng)式時(shí)間算法A，然后我們給出一個(gè)使用算法，然后我們給出一個(gè)使用算法A作為子程序的作為子程序的算法算法B來解決來解決DDH問題。問題。我們首先來回憶多項(xiàng)式安全性的攻擊游戲：我們首先來回憶多項(xiàng)式安全性的攻擊游戲：在尋找階段，輸入一個(gè)公鑰，輸出兩個(gè)消息和一些狀態(tài)信息。在尋找階段，輸入一個(gè)公鑰，輸出兩個(gè)消息和一些狀態(tài)信息。在猜測階段，輸入一個(gè)挑戰(zhàn)密文、一個(gè)公鑰、兩個(gè)消息和一些狀態(tài)信息，猜測挑戰(zhàn)在猜測階段，輸入一個(gè)挑戰(zhàn)密文、一個(gè)公鑰、兩個(gè)消息和一些狀態(tài)信息，猜測挑戰(zhàn)密文對(duì)應(yīng)的明文是哪個(gè)消息。密文對(duì)應(yīng)的明文是哪個(gè)消息。ElGamal密文為：密文為：(gk, mhk)其中其中

8、k是一個(gè)隨機(jī)整數(shù)，是一個(gè)隨機(jī)整數(shù)，h是公鑰。是公鑰。給定給定gx、gy和和gz，解決，解決DDH問題的算法問題的算法B執(zhí)行如下步驟：執(zhí)行如下步驟：令令h=gx。（m0, m1, s）=A（尋找階段（尋找階段, h）。）。設(shè)置設(shè)置c1=gy。從從0,1中隨機(jī)選擇一個(gè)數(shù)中隨機(jī)選擇一個(gè)數(shù)b。設(shè)置設(shè)置c2=mbgz。b =A（猜測階段（猜測階段, (c1, c2), h, m0, m1, s）。）。如果如果b = b ，輸出，輸出“TRUE”，否則輸出，否則輸出“FALSE”。ElGamal的安全性 ElGamal加密體制不是CCA2安全的。 證明：假設(shè)敵手想解密： c=(c1, c2)=(gk, m

9、hk) 敵手首先生成一個(gè)相關(guān)的密文c=(c1, 2c2)并詢問解密預(yù)言機(jī)。敵手得到c的明文m。然后敵手計(jì)算：m=m/2Discrete Log Problem (DLP) G is a finite cyclic group (usually mod p) g, h are members of G such that generates G (G = g, g2, g3, g4gn = 1 n is the order of g Find x such that h = gx Initial Methods Exhaustive search Run time: O(|G|) Space r

10、equirement: O(1) Shanks Baby Step-Giant Step Method (1971) Run time: O( ) Space requirement: O() )(gorder)(gorderPollards Rho Method (1975) The Rho method relies on the birthday paradox. Elements drawn at random from then the expected number of draws before an element is drawn twice (a collision) is

11、 Define a random walk on consisting of elements of the form gehd for known e and d, wait for a collision with e and d such that gehd = gehd and compute logg h = (e e)/ (d d) mod order(g). 2/)(gorderAnalysis: Pollards Rho Method For sufficiently large n: Asymptotic analysis: Space requirements: O(1)

12、Probabilistic n45. 1)log(nnOGF(p)上DLP的指標(biāo)計(jì)算方法Paillier加密方案 同態(tài)加密同態(tài)加密是一種加密形式，它允許人們對(duì)密文進(jìn)行特定的代數(shù)運(yùn)算得到仍然是加密的結(jié)果，與對(duì)明文明文進(jìn)行同樣的運(yùn)算再將結(jié)果加密一樣。換言之，這項(xiàng)技術(shù)令人們可以在加密的數(shù)據(jù)中進(jìn)行諸如檢索、比較等操作，得出正確的結(jié)果，而在整個(gè)處理過程中無需對(duì)數(shù)據(jù)進(jìn)行解密。其意義在于，真正從根本上解決將數(shù)據(jù)及其操作委托給第三方時(shí)的保密問題，例如對(duì)于各種云計(jì)云計(jì)算算的應(yīng)用。Computing on Encrypted Data Storing my files on the cloud Encrypt t

13、hem to protect my information Search through them for emails with “homomorphic” in the subject line Cloud should return only these (encrypted) messages, w/o knowing the key Private Internet search Encrypt my query, send to Google I still want to get the same results Results would be encrypted too 構(gòu)造

14、同態(tài)加密算法一直是密碼學(xué)領(lǐng)域的一個(gè)重要課題，以往人們只找到一些部分實(shí)現(xiàn)這種操作的方法。而2009年9月Craig Gentry）從數(shù)學(xué)上提出了“全同態(tài)加密”的可行方法，即可以在不解密的條件下對(duì)加密數(shù)據(jù)進(jìn)行任何可以在明文上進(jìn)行的運(yùn)算，使這項(xiàng)技術(shù)取得了決定性的突破。人們正在此基礎(chǔ)上研究更完善的實(shí)用技術(shù)，這對(duì)信息技術(shù)產(chǎn)業(yè)具有重大價(jià)值。 Craig Gentry. Fully Homomorphic Encryption Using Ideal Lattices. In the 41st ACM Symposium on Theory of Computing (STOC), 2009 A homom

15、orphic symmetric encryption Shared secret key: odd number p To encrypt a bit m: Choose at random large q, small r Output c = pq + 2r + m Ciphertext is close to a multiple of p m = LSB of distance to nearest multiple of p To decrypt c: Output m = (c mod p) mod 22r+m much smaller than pWhy is this homomorphic? c1=q1p+2r1+m1, c2=q2p+2r