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 :)
C# 
- Rejestracja:prawie 16 lat
- Ostatnio:4 miesiące
1
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
0
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ą?
- Rejestracja:prawie 16 lat
- Ostatnio:4 miesiące
1
Widzę że albo nie znalazłeś mojej odpowiedzi albo celowo zignorowałeś (Działanie programu daje zły wynik.), 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?
edytowany 1x, ostatnio: msm