C# - inv(x, y) - szyfrowanie RSA

Witam. Mam za zadanie napisać program szyfrujący szyfrem RSA. Natrafiłem na wiele opisów, jak po kolei szyfrować lecz w każdym pojawia się d = inv(e, f(n)). Chciałem się zapytać, co to jest za funkcja inv i czy jest w C# do niej odpowiednia metoda? Pozdrawiam :)

Odwrotność modulo.

Rozszerzony algorytm euklidesa. To cztery linijki, dasz radę. Na wiki jest bardzo rozwlekły kod, ale powinien działać: http://pl.wikipedia.org/wiki/Algorytm_Euklidesa#Rozszerzony_algorytm_Euklidesa

To mniejszy problem. Większy - nie odkrywaj koła na nowo i nie pisz tego co już powstało - szczególnie jeśli chodzi o kryptografię.
Trochę na mniej-więcej ten temat:
http://blogs.msdn.com/b/ericlippert/archive/2009/12/14/use-the-right-tool-for-the-job.aspx
http://www.codinghorror.com/blog/2009/05/why-isnt-my-encryption-encrypting.html

Poważnie, nie rób tego, ktoś to zrobił już lepiej od Ciebie ;]. Zamiast szukać gotowej metody do odwrotności modulo, poszukaj gotowej 'metody' do RSA.
http://msdn.microsoft.com/en-us/library/system.security.cryptography.rsa.aspx

Dzięki za ten link, właśnie nie patrzyłem na wiki tylko na inne strony, na których było to bardzo "inaczej" opisane :). Niestety, przy opisie projektu miałem wyraźnie zaznaczone, żeby szyfrowanie napisać bez tych klas :/.

Witam, mam takie pytanie: czy klucz prywatny może być liczbą ujemną? Bo przy generowaniu go czasami wychodzi liczba ujemna - algorytm sprawdzający czy liczby są względnie pierwsze (e i f(n)) jest dobry, ponadto sprawdzałem NWD tych liczb w kalkulatorze online i wychodziło 1 :/.

Ewentualnie podaję algorytm obliczania odwrotności modulo, może on jest zły:

        public int modulo(int a, int b)
        {
            // Zakładamy, że a > 0 i b > 0.
            int a0 = a;
            int b0 = b;

            // Inicjalizacja. Utrzymujemy niezmienniki p*a0 + q*b0 = a oraz r*a0 + s*b0 = b
            int p = 1;
            int q = 0;
            int r = 0;
            int s = 1;

            // algorytm
            while (b != 0)
            {
                int c = a % b;
                int quot = (int)Math.Floor(Convert.ToDouble(a / b));
                a = b;
                b = c;
                int new_r = p - quot * r;
                int new_s = q - quot * s;
                p = r;
                q = s;
                r = new_r;
                s = new_s;
            }

            return p;
            // Wówczas NWD(a0, b0) = p*a0 + q*b0
        }

PS: Czy klucz publiczny e musi być liczbą pierwszą?

Tak przy okazji, to właśnie chciałem się przyłączyć do pytania :). Mi tam z tym algorytmem z wiki raz ujemne, a raz dodatnie wyniki wychodzą z tego algorytmu (losowe e) :/. Bardzo proszę o pomoc i pozdrawiam :).

Widzę że albo nie znalazłeś mojej odpowiedzi albo celowo zignorowałeś (http://4programmers.net/Forum/Algorytmy/210746-dzialanie_programu_daje_zly_wynik?p=918471#id918471), więc wklejam jeszcze raz:

MSM napisał(a)

Jako że napisałeś na PW, odpowiem tutaj.

Nie zwracaj wartości bezwzględnej na pewno...
Odwrotność modulo powinna być liczbą dodatnią, jeśli u Ciebie jest inaczej to masz albo zły algorytm albo przepełnienie inta (INT_MAX + 1 = INT_MIN).

To chyba ja Ci zaproponowałem algorytm z wikipedii, pokaż może jak wyliczasz tą odwrotność to coś spróbuję poprawić :] [jak widać, to jednak nie Tobie]

Za chwilę sprawdzę ten algorytm z wikipedii - a Ty podaj może dla jakich to liczb wychodzi Ci odwrotność modulo < 0?