rsa.cs

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static readonly Random rnd = new Random();

    static void Main(string[] args)
    {
        long p, q, n, u, a, b;

        long min = 2 << 14 - 1;
        long max = 2 << 15 - 1;

        p = GetPrime(min, max);
        q = GetPrime(min, max);
        n = p * q;
        u = (p - 1) * (q - 1);

        a = Random(min, max);
        if (a % 2 == 0) a++;
        while (Gcd(u, a) != 1)
            a += 2;

        var ul = new List<long> { u, a };
        var tl = new List<long> { 0, 1 };
        for (var i = 0; ; i++)
        {
            ul.Add(ul[i] % ul[i + 1]);
            b = tl[i + 1] % u;
            if (ul[i + 2] == 0) break;

            long tmp = ((ul[i] - ul[i + 2]) / ul[i + 1] * tl[i + 1]) % u;
            if (tl[i] > tmp) tmp = tl[i] - tmp;
            else tmp = u - tmp + tl[i];

            tl.Add(tmp);
        }

        var data = Enumerable.Range(0, 100).Select(_ => Random() % n).ToArray();

        var cipher = data.Select(x => PowMod(x, a, n)).ToArray();
        var plain = cipher.Select(c => PowMod(c, b, n)).ToArray();

        Console.WriteLine(data.Zip(plain, (s, t) => s == t).All(x => x));
    }

    static long Gcd(long v1, long v2)
    {
        long r;
        while (true)
        {
            r = v1 % v2;
            if (r == 0) return v2;

            v1 = v2;
            v2 = r;
        }
    }

    static bool IsPrime(long value)
    {
        if (value % 2 == 0) return false;

        long sqrt = (long)Math.Ceiling(Math.Sqrt(value));
        for (long i = 3; i < sqrt; i += 2)
            if (value % i == 0)
                return false;

        return true;
    }

    static long Random()
    {
        var bytes = new byte[sizeof(long)];
        rnd.NextBytes(bytes);
        return BitConverter.ToInt64(bytes, 0);
    }

    static long Random(long min, long max)
    {
        return Random() % (max - min) + min;
    }

    static long GetPrime(long min, long max)
    {
        long ret = Random(min, max);
        if (ret % 2 == 0) ret++;
        while (!IsPrime(ret)) ret += 2;
        return ret;
    }

    static long PowMod(long b, long pow, long mod)
    {
        long ret = 1;
        b %= mod;

        while (pow != 0)
        {
            if ((pow & 1) != 0)
                ret = (ret * b) % mod;

            b = (b * b) % mod;
            pow >>= 1;
        }

        return ret;
    }
}