OK2

/*
 * ГЕНЕРАЦИЯ КЛЮЧЕЙ
 *  1. Генерируется случайное простое число p.
 *  2. Выбирается целое число g — первообразный корень p.
 *  3. Выбирается случайное целое число x такое, что ( 1 < x < p − 1 ).
 *  4. Вычисляется y = g ^ x mod p .
 *  5. Открытым ключом является ( y , g , p ), закрытым ключом — число x.
 * ШИФРОВАНИЕ
 *  0. Вводим М, меньшее p
 *  1. Выбираем сессионный ключ - случайное число, взаимно простое с (р - 1), k такое, что 1 < k < p-1
 *  2. Вычисляются числа a = (g ^ k) mod p и b = (y ^ k * M) mod p
 *  3. Пара чисел (a, b) являются шифротекстом
 * РАСШИФРОВАНИЕ
 *  0. Зная закрытый ключ х, исходное сообщение модно вычислить из шифротекта (a, b) по формуле
 *  1. M = (b * a ^ (p - 1 - x)) mod p
 */


// ok
static bool isCoprime(uint num1, uint num2)
{
    while (num1 != 0 && num2 != 0)
    {
        if (num1 > num2)
            num1 %= num2;
        else
            num2 %= num1;
    }
    return num1 + num2 == 1;
}

// ok
static uint funEuler(uint n)
{
    return n - 1;
}


// hope that ok
static uint fastPow(uint value, uint pow)
{
    if (pow == 0)
        return 1;
    uint z = fastPow(value, pow / 2);
    if (pow % 2 == 0)
        return (z * z);
    else
        return value * z * z;
}

// nihua ne ok
static bool isPrimitivalRoot(uint p, uint g)
{
    if (!isCoprime(p, g))
        return false;
    uint gg = fastPow(g, funEuler(p) / 2) % p;
    if (gg == 1)
        return false;
    uint l = funEuler(p) / p;
    List<uint> values = new List<uint>();
    for (uint i = 1; i <= funEuler(g); i++)
    {
        if (values.Contains(fastPow(g, i) % p))
            return false;
        values.Add(fastPow(g, i) % p);
    }
    return true;
}

// ok
static bool isPrime(uint n)
{
    for (uint i = 2; i * i <= n; ++i)
        if (n % i == 0)
            return false;
    return true;
}

/***    Main        ***/

Console.Write("Enter p: ");
uint p = Convert.ToUInt16(Console.ReadLine());
while (!isPrime(p))
{
    Console.Write($"{p} is not prime !!!\n" +
                  $"Enter p: ");
    p = Convert.ToUInt16(Console.ReadLine());
}
Console.Write("Enter g: ");
uint g = Convert.ToUInt16(Console.ReadLine());
while (!isPrimitivalRoot(p, g))
{
    Console.Write($"{g} is not primitival root of {p} !!!\n" +
                  $"Enter g: ");
    g = Convert.ToUInt16(Console.ReadLine());
}

Console.Write("Enter x: ");
uint x = Convert.ToUInt16(Console.ReadLine());
while (!(1 < x && x < p - 1))
{
    Console.Write($"{x} is not between 1 and n - 1 !!!\n" +
                  $"Enter x: ");
    x = Convert.ToUInt16(Console.ReadLine());
}

uint y = fastPow(g, x) % p;
List<uint> publicKey = new List<uint>{y, p, g};
uint privateKey = x;
Console.WriteLine($"Public key: ({publicKey[0]}, {publicKey[1]}, {publicKey[2]})\n" +
                  $"Private key: {privateKey}");

Console.Write("Enter M: ");
uint M = Convert.ToUInt16(Console.ReadLine());
while (!(M < p))
{
    Console.Write($"{M} is not smaller than {p} !!!\n" +
                  $"Enter M: ");
    M = Convert.ToUInt16(Console.ReadLine());
}

Console.Write("Enter k: ");
uint k = Convert.ToUInt16(Console.ReadLine());
while (!(isCoprime(k, p - 1) && 1 < k && k < p - 1))
{
    Console.Write($"{k} is not coprime with {p - 1} or {k} is not between 1 and {p -1} !!!\n" +
                  $"Enter k: ");
    k = Convert.ToUInt16(Console.ReadLine());
}

List<uint> hiddenText = new List<uint> {fastPow(g, k) % p, (fastPow(y, k) * M) % p};
Console.WriteLine($"Hidden text: ({hiddenText[0]},{hiddenText[1]})");

Console.Write("Enter x: ");
uint x1 = Convert.ToUInt16(Console.ReadLine());
if (x != x1)
    Console.WriteLine("Secret keys are not equal !!!");

uint M1 = (fastPow(y, k) * M) % p * fastPow(fastPow(g, k) % p, p - 1 - x) % p;
Console.WriteLine($"Your text: {M1}");


Console.ReadKey();