소개

이번에는 ElGamal 암호에 대해 학습도 겸하고 C#에서 알고리즘을 구현해 보았습니다.

만들기에 있어서, 이하를 참고로 했습니다.

IPUSIRON 님
- 암호화 기술의 모든

stackoverflow 님
- Calculate square root of a BigInteger (System.Numerics.BigInteger)

Wikipedia님
- ElGamal 암호

ElGamal 암호란?

ElGamal 암호는 1984 년 에르가말이 제안한 암호입니다.
- 암호문은 평문의 약 2배의 크기
- 암호화 시 난수로 마스크를 한다
- 암호의 단방향성은 CDH 문제의 어려움과 등가

암호의 자세한 내용은 생략

구현

환경

Windows 10

Visual Studio 2019 Community

C#

.NET Framework 4.7.2

기본

ElGamal 클래스를 만듭니다.

using System;
using System.Numerics;

class ElGamal
{
    // セキュリティパラメータ（バイト数）
    public int K { get; private set; }

    // デバッグ以外ならprivateに設定
    public BigInteger p;
    public BigInteger g;
    public BigInteger y;
    public BigInteger x;

    // 公開鍵
    public (BigInteger p, BigInteger g, BigInteger y) Pk
    {
        get => (this.p, this.g, this.y);
        set
        {
            this.p = value.p;
            this.g = value.g;
            this.y = value.y;
        }
    }
    // 秘密鍵
    // デバッグ以外ならprivateに設定
    public BigInteger Sk
    {
        get => this.x;
        set => this.x = value;
    }

    private Random random;
}

또한,

min<=x<=max maxByte 양의 정수 생성

private BigInteger GenerateRandom(int maxByte, BigInteger min, BigInteger max)

그리고,
maxByte의 홀수 소수 생성

private BigInteger GenerateRandomPrime(int maxByte)

있습니다.

키 생성

소수 p, 원시 원 g, 무작위 정수 x, 정수 y를 만듭니다.

또한 원시원 g는, 만족하는 원시원을 2부터 1씩 찾고 있습니다

// 鍵を生成する
public void GenerateKeys(int k)
{
    p = GenerateRandomPrime(k);
    Console.WriteLine("ランダムな素数p = {0}", p);

    g = GenerateGroupGen(k, p);
    Console.WriteLine("原始元g = {0}", g);

    x = GenerateRandom(k, 0, p - 2);
    Console.WriteLine("ランダムな非負整数x = {0}", x);

    y = BigInteger.ModPow(g, x, p);
    Console.WriteLine("y = g^x mod p = {0}", y);
}

// 原始元を生成する
public static int GenerateGroupGen(int k, BigInteger p)
{
    for (int g = 2; ; g++)
    {
        bool isGen = true;
        BigInteger a = 1;
        for (int i = 1; i <= p - 2; i++)
        {
            a *= g;
            if (a >= p) a %= p;
            if (a == 1)
            {
                isGen = false;
                break;
            }
        }

        if (isGen)
        {
            return g;
        }
    }
}

암호화

평문 m에서 암호문 c를 생성합니다.

// 暗号化する
public (BigInteger c1, BigInteger c2) Encrypt(BigInteger m)
{
    var r = GenerateRandom(K, 0, p - 2);
    Console.WriteLine("ランダムな数r = {0}", r);

    var c1 = BigInteger.ModPow(g, r, p);
    var c2 = (m * BigInteger.ModPow(y, r, p)) % p;

    return (c1, c2);
}

해독

암호문 c에서 평문 m'을 생성합니다.

// 復号する
public BigInteger Decrypt((BigInteger c1, BigInteger c2) c)
{
    return (c.c2 * BigInteger.ModPow(c.c1, p - 1 - x, p)) % p;
}

결과

실제로 임의의 숫자 m(이번은 12345)과 임의의 문자열(이번은 "Hello, World!")을 암호화·복호해 봅니다.
문자열이지만 UTF-16으로 사용되며 ECB 모드로 수행됩니다.



이상의 이미지와 같이 무사히 암호화·복호할 수 있었습니다.

마지막으로

실제로 구현해 보았습니다.
소수 p이지만, 본래라면 p-1이 큰 소인수를 포함하는 것이 바람직합니다만, 이번은 랜덤인 소수로 했습니다. 다음은 p-1이 포함하는 소수를 만들고 싶습니다.
또 이번은 위상이 소수인 순회군이었습니다만, 다음은 모든 순회군을 취급할 수 있도록(듯이) 하고 싶습니다.

소스 코드

당기사에 실수등 있으면, 수고스럽지만 코멘트란보다 지적 받을 수 있으면 다행입니다.