[정보보안] Discrete Logarithm Problem(DLP)와 Elgamal Encryption(엘가멜 암호화)

1. Discrete Logarithm Problem(DLP)

• When g, Z*n and y are given, DLP is to find x such that

        y ≡ g^x mod n

 

2. Primality Test

function primality(N)

Input: Positive integer N

Output: yes/no

 

Pick a positive integer a<N at random

if a ^p-1 ≡ 1 (mod N) :

      return yes

else :

      return no

소수가 아닌 합성수가 위의 primality test를 통과하는 경우가 있다. 

341=11*31

2^340 ≡ 1 mod 341

• Carmical numbers
  • a composite positive integer n which satisfies the congruence b^(n-1) ≡ 1 (mod n)
  • for all integers b which are relatively prime to n
  • pass Fermat's test for all a relatively prime to n

function primality2(N)

Input: Positive integer N

Output: yes/no

 

Pick a positive integers a1,a2,a3,...,ak <N at random

if a ^(N-1) ≡ 1 (mod N) for all i=1,2,3...,k :

      return yes

else :

      return no

Algorithm return yes when N is not prime <= 1/(2^k)

 

3. 비대칭 암호화 방식(엘가멜)

• ElGamal 
  • Discrete Logarithm 문제의 어려움 이용
• RSA
  • Factorizing(소인수분해) 문제의 어려움 이용

4. Elgamal Encryption

• Public Keys
  • p : prime
  • g : generator g < p , g ∈ Z*p
  • Y ≡ g^x mod p
• Private Key
  • x : choose at random , x<p
• Encryption : Cipertext <a,b>
  • k: choose at random, relatively prime to p-1 (secret)
  • a = g^k mod p
  • b= Y^kM mod p
• Decryption 
  • M = b/a^x(mod p)=y^kM/g^kx=g^xkM/g^kx=M

 

• 관련 그림