Jak zaimplementować potęgowanie modularne dla RSA 512-bit w C?

Chcę zrealizować szyfrowanie RSA 512bit, czyli zrealizować działanie:
c = t^e mod n.

c - zaszyfrowane dane
t - dane do szyfrowania
e - wykładnik potęgi liczba pierwsza
n - moduł 512 bitowy

W czym jest problem? Otóż mam rozwiązanie, które realizuje szybkie potęgowanie modularne i spokojnie daje sobie radę z działaniem np 57^65537mod71 i głowię się jak przerobić poniższy kod aby można było zrobić dzielenie modulo przez n będące liczbą składającą się ze 150 cyfr (gdzieś wyczytałem, że liczba 512 bitowa ma w rozwinięciu dziesiętnym 154 cyfry, ale nie był podany wzór jak to liczyć... Nie ukrywam, że przydałby się)



Wiem że jeśli t^e będzie mniejsze od n to działanie t^e mod n = t^e
ale tak będzie, gdy t=10 i e będzie mniejsze od 150, więc trochę małe...

Mój pomysł był taki by napisać funkcję która działa na tablicy char i przy pomocy wielu odejmowań i porównywaniu otrzymanego wyniku z n będzie realizować dzielenie modulo n. Będzie to jednak bardzo nieefektywne i zajmie dużo pamięci operacyjnej... Czy istnieje jakiś sprytny algorytm którym można będzie policzyć takie rzeczy bez zbędnego zajmowania pamięci?

A może istnieje gotowa biblioteka w C szyfrująca RSA i nie wiem o jej istnieniu?

Chcę docelowo przenieść szyfrowanie RSA do atmegi 32. Może dla AVR jest gotowa biblioteka szyfrująca?

Kod powyżej jest w C. Chodzi Ci o C czy C# (jak w topicu)?

1. Podane rozwiązanie jest strasznie nieoptymalnie radzę takie (o ile chodzi o 32 bitowe RSA w C):
2. Zdecyduj się C, C++ czy C# bo te języki zdecydowanie się różnią.
3. Do 512 bitowego RSA potrzebujesz 512 bitowych liczb oraz operacji na nich, najprościej użyć gotową bibliotekę, aczkolwiek możesz spróbować napisać samodzielnie (przy odrobinie myślenia - będzie szybsze niż standardowe).

Przepraszam za małe zamieszanie, chodzi mi oczywiście o czyste proceduralne C.

Zdaję sobie sprawę z tego, że będę potrzebował do rozwiązania zadania 512 bitowe liczby. Problem w tym, że moje umiejętności programistyczne nie są na zbyt wysokim poziomie i potrzebuję ukierunkowania jak sobie z tym poradzić. Najprostszym i chyba najefektywniejszym sposobem byłoby właśnie użycie gotowej biblioteki do obsługi dużych liczb. Próbowałem na BigDigids która jest na stronie http://www.di-mgt.com.au/bigdigits.html tylko miałem problemy z uruchomieniem jej i zaniechałem tego procederu.

Widzę, teraz że warto jednak do tego powrócić, bo to co stworzyłem na tablicach char na pewno nie zmieści mi się do atmegi32. Mam sprawnie działające mnożenie oparte na wielokrotnym dodawaniu "pod kreskę" tylko, że to rozwiązanie zabiera połowę dostępnej pamięci (1kB z 2kB które są atmedze 32) a muszę jeszcze dorobić działanie modulo, więc to słabe rozwiązanie...

Czy mogę prosić o łopatologiczne wytłumaczenie jak używać powyższej biblioteki? A może są jeszcze inne? Nie wiem nawet, czy BIGDigits zmieści się do 8 bitowca.

Dla RSA potrzebujesz wyłacznie przesunięcia bitowego, mnożenia, potęgi.
Każda biblioteka zawiera znacznie więcej, więc jeżeli twój kod się nie mieści to zaszło jedno z dwóch:
- napisałeś strasznie nieoptymalnie
- każda gotowa biblioteka się nie zmieści.

Dziękuje za rady. Użyłem biblioteki którą podałem w poprzednim poście uprzednio ją modyfikując (wyrzuciłem wszystko co nie było związane z obsługą dużych liczb, szyfrowaniem RSA i konwersja na hex) Całość czyli owa biblioteka + klucz publiczny zapisany w tablicy char + dodatkowe biblioteki do obsługi UART i 1wire mieści się w Atmedze32 zajmując ok 83% pamięci RAM, oczywiście można bez problemu osiągnąć lepszy rezultat zapisując chociażby klucz publiczny w pamięci EEprom czy flash. Najważniejsze jest jednak to, że działa szyfrowanie temperatury pobieranej z cyfrowego termometru i jest ona przekazywana bezpiecznie dalej przez HC05.