はじめに

この記事ではCramer-Shoup暗号について解説をし、Pythonによる実装を行います。
この記事を書くにあたって最後に紹介する文献を大いに参考にさせていただいております。
専門用語などで分からないものがある場合はそちらを参照してください。

Cramer-Shoup暗号とは

Cramer-Shoup暗号は公開鍵暗号方式の一つで、ランダムオラクルに依存しない標準モデルで初めて効率的にIND-CCA2安全が証明された暗号です。この暗号はElGamal暗号の拡張であると考えることが出来ます。
また、暗号の安全性はElGamal暗号と同じくDDH問題の困難性を根拠にしています。[1][2]
IND-CCA2安全を満たすという面ではRSA-OAEPがランダムオラクルモデルの下で達成していますが、Cramer-Shoup暗号はランダムオラクルに依存しない標準モデルで達成しているという点でより確かな安全性があると言えます。

仕組み

Cramer-Shoup暗号には鍵生成、暗号化、復号化の三つのステップがあります。今からこれらを順に解説します。

記号の定義

$\mathbb G_{p}\dots$ 位数pの群
$\mathbb Z_{p} = \lbrace 0,1,2,\dots,p-1 \rbrace$
$H \dots ハッシュ関数$

鍵生成

素数$p$に対して位数$p$の群$\mathbb G_{p}$を生成し$(g,h)\in \mathbb G_{p}^2 $をランダムに選びます。
次に$(x_{00},x_{01},x_{10},x_{11},x_{20},x_{21})\in \mathbb Z _{p}^6$をランダムに選び、

$y_{i} = g^{x_{i0}}h^{x_{i1}} (0\leq i \leq 2)$を計算します。
また、ターゲット衝突困難なハッシュ関数Hをランダムに選択します。
最後に、秘密鍵sk、公開鍵pkを
$$
sk =(x_{00},x_{01},x_{10},x_{11},x_{20},x_{21},\mathbb G_{p},H),pk=(y_{0},y_{1},y_{2},\mathbb G_{p},g,h,H)
$$
として鍵生成を終了します。

暗号化

入力$m\in \mathbb G$、公開鍵pk、$r\in \mathbb Z_{p}$に対し暗号文$c_{i}(1\leq i \leq 4)$を
$$
c_{1} = g^{r},\quad c_{2} =h^{r},\quad c_{3} = m・y_{0}^{r},\quad c_{4} = (y_{1}y_{2}^{H(c1,c2,c3)})^r
$$
と計算し、$c=(c_{1},c_{2},c_{3},c_{4})$を暗号文とします。

復号化

受け取った暗号文cと秘密鍵skを用いて、まず以下の等式が成り立つか確認する。

$$
c_{4} = (c_{1}^{x_{10}}c_{2}^{x11})(c_{1}^{x_{20}}c_{2}^{x_{21}})^{H(c1,c2,c3)}
$$

これが成り立っていない場合、復号失敗とする。成り立っていた場合、平文$m =c_{3}・c_{1}^{-x_{00}}・c_{2}^{-x_{01}} $計算し出力する。

実装

実装にはPycryptodomeを用いました。pip install pycryptodomeでインストールできます。
また、ハッシュ関数にはSHA3を用いました。

from Crypto.Util.number import *
from Crypto.Hash import SHA3_512
from random import randint

class Cramer_Shoup:
    def __init__(self,num):
        self.keygen(num)

    def keygen(self,num):
        #generate PrimeNumber p
        self.p = getPrime(num)

        #generate g,h∈G^2
        g = randint(0,self.p-1)
        h = randint(0,self.p-1)

        #generate (x00,x01,x10,x11,x20,x21)∈Z_{p}^6
        x00 = randint(0,self.p-1)
        x01 = randint(0,self.p-1)
        x10 = randint(0,self.p-1)
        x11 = randint(0,self.p-1)
        x20 = randint(0,self.p-1)
        x21 = randint(0,self.p-1)

        #calculate y_{i}
        y0 = (pow(g,x00,self.p))*(pow(h,x01,self.p))
        y1 = (pow(g,x10,self.p))*(pow(h,x11,self.p))
        y2 = (pow(g,x20,self.p))*(pow(h,x21,self.p))

        #key
        self.pk = (y0,y1,y2,g,h)
        self.sk = (x00,x01,x10,x11,x20,x21)

    
    def enc(self,m):
        r = randint(0,self.p-1)

        #calculate cipher123
        c1 = pow(self.pk[3],r,self.p)
        c2 = pow(self.pk[4],r,self.p)
        c3 = m*(pow(self.pk[0],r,self.p))%self.p
        #calculate hash
        c1_b = format(c1,'b')
        c2_b = format(c2,'b')
        c3_b = format(c3,'b')
        c123_b = c1_b + c2_b + c3_b
        hs = SHA3_512.new(bytearray(c123_b,"utf-8"))
        hs = int(hs.hexdigest(),16)
                
        #calculate cipher4
        c4 = pow((self.pk[1]*pow(self.pk[2],hs,self.p))%self.p,r,self.p)

        return (c1,c2,c3,c4)
    
    def dec(self,c):
        #hash
        c1_b = format(c[0],'b')
        c2_b = format(c[1],'b')
        c3_b = format(c[2],'b')
        c123_b = c1_b + c2_b + c3_b
        hs = SHA3_512.new(bytearray(c123_b,"utf-8"))
        hs = int(hs.hexdigest(),16)


        #calculate ck_num = {(c1^x10)(c2^x11)}{(c1^x20)(c2^x21)}^H(c1,c2,c3)
        ck_num1 = (pow(c[0],self.sk[2],self.p)*pow(c[1],self.sk[3],self.p))%self.p
        ck_num2 = (pow(c[0],self.sk[4],self.p)*pow(c[1],self.sk[5],self.p))%self.p
        ck_num3 = pow(ck_num2,hs,self.p)
        ck_num = (ck_num1*ck_num3 )%self.p

        #check c4 == ck_num
        if(c[3] == ck_num):
            m1= c[2]*pow(c[0],-self.sk[0],self.p)%self.p
            m= m1 * pow(c[1],-self.sk[1],self.p)%self.p
            return m
        else:
            raise Exception("c4!=ck_num,error!")




if __name__ == '__main__':
    k = Cramer_Shoup(1024)
    #message
    m="Hello_qiita!!"
    print("Plain text is :" +m)
    m_byte_to_long = bytes_to_long(m.encode("utf-8"))
    #enc
    m_enc = k.enc(m_byte_to_long)
    print("Cipher text is :" ,str(m_enc[0]),str(m_enc[1]),str(m_enc[2]),str(m_enc[3]))
    #dec
    m_dec = k.dec(m_enc)
    m_long_to_byte = long_to_bytes(m_dec)
    print("Decrypted cipher text is :"+m_long_to_byte.decode("utf-8"))

参考文献

[1] 花岡悟一郎(2010)「電子情報通信学会知識ベース　知識の森1群3編(暗号理論)5章公開鍵暗号」
https://www.ieice-hbkb.org/files/01/01gun_03hen_05.pdf
[2]藤﨑英一郎(2019)「I240 暗号理論 2019 公開鍵暗号と署名（１）」
https://www.jaist.ac.jp/~fujisaki/2019/I240-2019-9.pdf
[3]ウィキペディア「Cramer-Shoup暗号」
https://ja.wikipedia.org/wiki/Cramer-Shoup%E6%9A%97%E5%8F%B7
[4]森山大輔,西巻陵,岡本龍明(2011)「公開鍵暗号の数理」共立出版