当前位置：网站首页>EIGamal cryptosystem description

EIGamal cryptosystem description

2022-07-28 06:16:00 【zzuls】

1. Brief introduction

1.EIGamal The password is RSA Besides the password, the most representative public key password

2.EIGamal Based on the difficult problem of discrete logarithm

2. Key generation

（1） Select a prime number p, And less than p Of the two random number g and x

（2） Calculation $y\equiv g^{x}mod(p)$

（3） With （y,g,p) As public key ,x As the private key

3. Encryption operations

（1） For clear text messages M, Randomly choose one with p-1 A coprime integer k Calculation $C_{1}\equiv g^{k}$ mod p, $C_{2}\equiv y^{k}M$ mod p

（2） Ciphertext is C=(C1,C2)

4. Decryption calculation

$M=C_{2}/C_{1}^{x}mod$

5. Proof of correctness

6.EIGamal Cryptosystem security

EIGamal Based on the difficult problem of discrete logarithm , for instance ：p It's a prime number

seek c=2^q mod p It's simple , It can be solved quickly with fast power , But we know c Words , Ask you to calculate the force in the current situation , The time complexity is generally in O( $\sqrt{n}$ ), When q When I was older , Ask for q It's very troublesome .