密码学之公钥密码体系(3):ElGamal算法

密码学之公钥密码体系(3):ElGamal算法

1. ElGamal算法

ElGamal算法是基于离散对数求解困难的加密体系。与RSA算法一样,都能用于数据加密和数据签名。但是两者的原理不一样,ELGmal算法基于离散对数问题,而RSA算法基于大数分级困难问题。此外,对于ElGamal算法对于使用相同的私钥,对相同的明文进行加密,每次得到的加密结果却不一样,这是ElGamal算法另一个重要特征。

2. ElGamal算法基本原理

2.1 ElGamal密钥生成
  1. 随机选择一个大素数

    p

    p

    p,且要求

    p

    1

    p-1

    p1有大素数因子。再选择一个模

    p

    p

    p的本原元

    g

    g

    g。将

    p

    p

    p

    g

    g

    g公开。

  2. 随机选择一个整数

    x

    x

    x作为私钥

    2

    x

    p

    2

    2≤x≤ p-2

    2xp2

  3. 计算

    y

    =

    g

    x

    m

    o

    d

    p

    y=g^x mod p

    y=gxmodp

    y

    y

    y公钥

2.2 ElGamal加密过程
  1. 对明文

    M

    M

    M进行加密,随机地选取一个整数

    k

    k

    k

    2

    k

    p

    2

    2≤k≤p-2

    2kp2,并要求

    k

    k

    k

    p

    1

    p-1

    p1互素

  2. 计算:

    a

    g

    k

    m

    o

    d

    p

    a=g^k mod p

    agkmodp

    b

    M

    y

    k

    m

    o

    d

    p

    b=M*y^k mod p

    bMykmodp

  3. 密文对为

    a

    ,

    b

    (a,b)

    a,b,并且密文的大小时明文的两倍。

2.3 ElGamal解密过程
  1. 由密文可得明文

    M

    M

    M,计算

    M

    =

    b

    /

    a

    x

    m

    o

    d

    p

    M=b/a^x mod p

    M=b/axmodp
    其中

    x

    x

    x为私钥。

  2. 解密过程和Diffie-Hellman密钥交换过程极为类似。
  3. 下面给出了加密和解密过程
    在这里插入图片描述
2.4 ElGamal签名过程
2.4.1 签名:
  1. 对消息

    M

    M

    M进行签名时,首先选择一个随机数

    k

    k

    k,并要求

    k

    k

    k

    p

    1

    p-1

    p1互素。

  2. 计算:

    a

    =

    g

    k

    m

    o

    d

    p

    a=g^kmodp

    a=gkmodp

  3. 利用扩展欧几里得算法,求出

    b

    b

    b:

    M

    =

    (

    x

    a

    +

    k

    b

    )

    m

    o

    d

    (

    p

    1

    )

    M=(xa+kb)mod(p-1)

    M=(xa+kb)mod(p1)

  4. 签名结果为(a,b)。需要注意的是,k需要保密。
2.4.2 验签:
  1. 需要验证下面公式成立:

    y

    a

    a

    b

    m

    o

    d

    p

    =

    g

    M

    m

    o

    d

    p

    y^aa^bmodp=g^Mmodp

    yaabmodp=gMmodp

  2. 下面给出签名和验签的大致流程
    在这里插入图片描述
  3. 需要注意的是,在每次使用ElGamal算法进行签名时,都需要更新随机数k。
2.4.3 具体案例:
  1. 选择

    p

    =

    11

    ,

    g

    =

    2

    p=11,g=2

    p=11,g=2,私人秘钥

    x

    =

    8

    x=8

    x=8,计算:

    y

    =

    g

    x

    m

    o

    d

    p

    =

    >

    y

    =

    2

    8

    m

    o

    d

    11

    =

    3

    y=g^xmodp => y=2^8 mod 11 = 3

    y=gxmodp=>y=28mod11=3

  2. 因此,公开秘钥是

    y

    =

    3

    ,

    g

    =

    2

    ,

    p

    =

    11

    y=3,g=2,p=11

    y=3,g=2,p=11

  3. 对消息

    M

    =

    5

    M=5

    M=5进行签名,首先随机选择随机数

    k

    =

    9

    k=9

    k=9,验证

    g

    c

    d

    9

    ,

    10

    =

    1

    gcd(9,10)=1

    gcd9,10=1,计算:

    a

    =

    g

    k

    m

    o

    d

    p

    =

    2

    9

    m

    o

    d

    11

    =

    6

    a=g^kmodp=2^9mod11=6

    a=gkmodp=29mod11=6
    利用欧几里得算法求

    b

    b

    b:

    M

    =

    (

    a

    x

    +

    k

    b

    m

    o

    d

    (

    p

    1

    )

    )

    M=(ax+kbmod(p-1))

    M=(ax+kbmod(p1))

    5

    =

    (

    8

    6

    +

    9

    b

    )

    m

    o

    d

    10

    5=(8*6 + 9*b)mod10

    5=(86+9b)mod10
    求解得到

    b

    =

    3

    b=3

    b=3,于是签名对

    (

    a

    ,

    b

    )

    (a,b)

    (a,b)

    6

    ,

    3

    (6,3)

    6,3

  4. 验签上述签名的正确性,只需要验证下面:

    y

    a

    a

    b

    m

    o

    d

    p

    =

    g

    M

    m

    o

    d

    p

    y^aa^bmodp=g^Mmodp

    yaabmodp=gMmodp

    3

    6

    6

    3

    m

    o

    d

    11

    =

    2

    5

    m

    o

    d

    11

    3^66^3mod11=2^5mod11

    3663mod11=25mod11

2.5 ElGamal算法软件算法实现的快慢

具有

160

b

i

t

160 bit

160bit的指数的ElGamal算法对不同模数长度的快慢表
在这里插入图片描述

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇

)">
下一篇>>