암호에 대한 이해 - Elgamal

Elgamal Encryption 부터 공부해 봅시다.

 

● 사용자 public key(Y)

P : prime number를 임의로 선택합니다. 그래야 P보다 작은 G : generator를 고를 수 있기 때문이죠.

mod p 이고, 어떤 g, p를 사용해서 내 공개키는 뭐다 알려주면 됩니다.

(alice와 bob이 같은 Y여도 상관 없습니다. 어떤 p,어떤 g를 사용했는 지만 알려주면 됩니다.)

 

● 사용자 private key(x)

x는 P보다 작은 어떤 임의의 자연수이기만 하면 됩니다.

 

공개키가 노출된다고 하더라도 x는 알 수 없습니다.(DLP 기반)

 

정수론에서 "subgroup의 차수가 원래 group의 차수와 같아야 한다"가 굉장히 중요하다고 했습니다. 그 이유는 뭘까요?

generator는 항상 subgroup의 차수와 원래 group의 차수가 같게 만들어 주는 수입니다. 그런 g를 public key를 만들 때 선택을 한다고 했습니다.

그렇지 않은 g를 선택하면 어떤 문제가 발생할까요?

예를 들어 어떤 수의 승수를 한 것이 계속 10, 11 반복한다고 합시다.

어떤 사람이 이라는 수를 만들어 냈습니다. 그러면 하니까 또 10이 나옵니다. 이건 바로 5라는 수로 암호화 한게 5를 몰라도 7이라는 키로 풀린다는 겁니다. 10이 공개키라는 말은 10이 되는 비밀키가 딱 하나 존재해야됩니다. 공개키와 비밀키는 1대1 매핑이 되어야 합니다.

 

● Encryption

a = mod p

b =  mod p

어떤 메세지 m이 주어졌을 때, 상대의 공개키가 Y라고 합시다.

Y하고 m을 곱해서 만들어 내는게 b인데, 그냥 Y하고 m을 곱하면 복호화가 그냥 Y나눠주면 되기 때문에 임의의 k라는 수를 랜덤하게 선택해서 을 만든 다음에 m을 곱해줘서 암호문을 생성합니다. 그러면 의 의미는 m을 알아내려면 전체 b값에서 를 나눠줘야 합니다. Y는 공개키이므로 알 수 있지만 k는 몰라야 됩니다. 이 k는 m을 복호화할 수 있는 사람만 알아야 합니다. 이 k는 숨겨서 전달해야 합니다. 따라서 DLP에 기반해 해서 알려줍니다. g도 알고 a도 알지만 k는 모릅니다. 중간에서 a,b를 가로채는 사람들은 k를 몰라 계산을 하지 못해서 m을 알아내지 못합니다.

문제는 a,b를 받는 수신자는 복호를 할 수 있어야 합니다. 즉 를 계산할 수 있어야 합니다.

이라고 했습니다. 결국 는 와 같습니다. 그러면 Y에 대한 비밀키(x)를 아는 사람은 을 만들어 낼 수 있으면 됩니다. 수신자는 a를 압니다. a에다가 나의 비밀키 x를 승수 해주는 겁니다. 수신자는 x를 알기 때문이죠.

그럼 결국 a가 이고 이것의 x 승을 하는 것이므로 결과적으로 가 됩니다.

 

● Decryption

수신자는 b에서 이 수를 나눠주면 m을 알아낼 수 있습니다.

 

다음에는 RSA에 대해서 공부해 봅시다~