Wymiana szyfrowanych danych

0

Cześć,
zaimplementowałem algorytm RSA.
Moje zmagania są w tym wątku RSA liczby względnie pierwsze ;)

Wszystko bardzo ładnie śmiga tylko problem pojawia się w momencie kiedy chciałem dodać go do swojej aplikacji. Miałem plan szyfrować w ten sposób pakiety danych jednak:

  • zaszyfrowanie przebiega bardzo sprawnie,
  • odszyfrowanie nawet krótkiego tekstu trwa parę sekund co w przypadku częstej wymiany informacji klient-serwer w ogóle się nie sprawdza.

Wpadłem więc na pomysł aby wymienić między klientem i serwerem hasło, zaszyfrowane właśnie RSA, które będzie wykorzystane do prostszego szyfrowania szybszym algorytmem.

Czy ten sposób jest wykorzystywany w 'realnych' aplikacjach? jaki algorytm polecacie aby użyć? Znalazłem w sieci przykłady algorytmu blowfish. Czy warto się na nim skupić?

pozdrawiam!

2

RSA jest algorytmem wykorzystywanym do utajniania małej ilości informacji np. do szyfrowania kluczy algorytmów symetrycznych czy podpisywania wiadomości (tak w skrócie szyfrowania kluczem prywatnym hasza wiadomości).

RSA nie wykorzystuje się do szyfrowania dużej porcji informacji więc duży czas może być czymś normalnym w Twoim przypadku.

3

Generalnie tak sie właśnie robi bo rozmiar danych szyrowanych RSA jest ograniczony przez modulus i realnie szyfruje sie klucz np. dla AESa a same dane szyfruje symetrycznie AESem. Nie, nie używaj Blowfisha. I nie, nie implementuj tego samemu :D

Ale nie rozumiem jak ty to robisz że dekodowanie długo zajmuje. Jaki ty masz tam rozmiar modulusa w takim razie? I jak wykonujesz operacje potęgowania modularnego?

1

Dokładnie tak to działa, wymiana kluczy następuje z wykorzystaniem np. Diffie-Hellman, a potem szyfrowanie leci algorytmem symetrycznym

https://en.wikipedia.org/wiki/Diffie–Hellman_key_exchange

A czym to w ogóle deszyfrujesz, jakąś biblioteką i jaki długi jest klucz? Ogólnie RSA jest dosyć mało wydajnym algorytmem, jednak nigdy nie spotkałem się żeby deszyfrowanie trwało w sekundach ;), gdzieś tu jest błąd.

Nie myślałeś, żeby przerzucić się na coś standardowego właśnie do tego celu jak TLS?

0

RSA bawie się w celach bardziej edukacyjnych ale stwierdziłem, że skoro liznąłem temat szyfrowania to dodam to do aplikacji nad którą sobie dłubie.

Modulus ma długość 640 znaków (podałem te liczby we wspomnianym wcześniej wątku). Dekodowanie odbywa się na podstawie algorytmu, który został opisany na tej stronie: http://eduinf.waw.pl/inf/alg/001_search/0067.php

a konkretnie:

Funkcja oblicza modulo potęgę podanej liczby

function pot_mod(a,w,n : integer) : integer;
var
  pot,wyn,q  : integer;
begin

  // wykładnik w rozbieramy na sumę potęg 2. Dla reszt
  // niezerowych tworzymy iloczyn potęg a modulo n.

  pot := a; wyn := 1; q := w;
  while q > 0 do
  begin
    if (q mod 2) = 1 then wyn := (wyn * pot) mod n;
    pot := (pot * pot) mod n;    // kolejna potęga
    q := q div 2;
  end;
  pot_mod := wyn;
end;

Może faktycznie coś gdzieś namieszałem, muszę sprawdzić - chociaż funkcja mimo, że trwa długo to deszyfruje dane poprawnie.

Zapoznam się z tym TLS bo nie spotkałem się jeszcze z tym. A poniżej wrzucam klucze, których użyłem:

n:
3379633067208294961377042259124572111722991636377699224798124244740173570936209090053543861546567647483515247037085824784840949478369635457322559127209182678703736850102249014613990470410262165669798854627880160791153676354375533982153428751624087130971202264769136886841561134095365320753687539755895357847617923915707340577347224146386198552054001037287281040959444053318638627447124429894867112605854140029906927600687861900000451828874159051892697033965926723749568764005471780512562964222149091037255870318439498097537433529745662424142644198516618927207606308927904746556844820579528982932758132334243303657770430718753881676972436921
 
e:
65537
 
d:
1864349516742931286733665086807920038377120048674229215162832992356859409342154313329962787837298932808513156325919157475111079915461874640808720722150663229764019987078528891289708248249492977382855618970559565459672410054500796122303839382123988389241429958013667277172703467645786552281382014375649029058018094247689143189765636823809330738999625570758488391598713256430373612145788997975655399861337785160438363095085783341478663206566494667624147910309551744728293959630828549266643035905008654336554798427514932597074250576548660657673973597982202426396583468226431692654458805224361048129232616241331734864795773524177348962719103941
0
  1. Rozumiesz ze udostępnianie tych kluczy czyni twoje szyfrowanie bezużytecznym? :D
  2. To przecież w ogóle nie może działać o_O Chyba że piszesz to w jakimś języku gdzie integer ma nieograniczony rozmiar, ale skoro podajesz kody w Pascalu to raczej tak nie jest? Napisałeś własną implementacje BigInteger i aliasowałeś nią typ integer czy jak?
  3. Funkcja którą pokazałeś, czyli square then multiply jest niezbyt bezpieczna jeśli chodzi o jej zastosowanie do RSA...
0

Panowie, wy tak serio? :) Przecież to są przykładowe klucze, których użyłem w celach testowych - udostępniłem je aby pokazac jak to w ogóle wygląda i żeby dojść do tego dlaczego deszyfrowanie trwa dłużej niż powinno. Produkcyjną wersję kluczy mogę wygenerować w każdym momencie i logiczne że nie udostępnie tego ;)

To jest pierwotna wersja algorytmu. W swojej zamieniłem integer na typ, który pomieści tak wielkie liczby - używam gotowej biblioteki do obsługi dużych liczb.

  1. Czy możesz zaproponować lepsze rozwiązanie albo nakierować mnie co jest w tym nie tak?
0

Znalazłem jeszcze inny algorytm, sprawdzę potem czy będzie lepiej.

function power_modulo_fast(a: Integer; b: Integer; m: Integer): Integer;
var
   i: Integer;
   x: Int64;
begin
   result := 1;
   x := a mod m;

   i := 1;
   while (i<=b) do
      begin
         x := x mod m;
         if ((b and i) <> 0) then
            begin
               result := (result * x) mod m;
            end;
         x := x * x;
         i := i shl 1;
      end;
end;
1

Zaoszczędź sobie problemów i skorzystaj z gotowych bibliotek kryptograficznych, typowo pod BigInty.

Tutaj wersja dla Lazarusa na Apache 2.0 license (czyli nawet do zastosowań komercyjnych):

https://bitbucket.org/sergworks/tforge

Jeśli robisz to dla Windows to masz też gotowe crypto api dla RSA.

1
karpov napisał(a)

odszyfrowanie nawet krótkiego tekstu trwa parę sekund co w przypadku częstej wymiany informacji klient-serwer w ogóle się nie sprawdza

RSA ma to do siebie, że potrzeba znacznie więcej czasu na operacje na kluczu prywatnym. Chcesz mieć odwrotnie? Użyj EC. Przykład:

-> % openssl speed rsa1024
Doing 1024 bit private rsa's for 10s: 66568 1024 bit private RSA's in 10.00s
Doing 1024 bit public rsa's for 10s: 1132528 1024 bit public RSA's in 10.00s
OpenSSL 1.0.2j-freebsd  26 Sep 2016
built on: date not available
options:bn(64,64) rc4(16x,int) des(idx,cisc,16,int) aes(partial) idea(int) blowfish(idx) 
compiler: clang
                  sign    verify    sign/s verify/s
rsa 1024 bits 0.000150s 0.000009s   6656.8 113252.8

Odnośnie jeszcze szybkości: z RSA jest parę sztuczek optymalizacyjnych, np. operacje mnożenia dwóch długich liczb można zrobić w sposób szybki (Karacuba O(n1.5) lub wolny (tablica szkolna O(n2)). Ponadto są jeszcze sztuczki sprzętowe do przyspieszenia mnożenia dużych liczb, Intel swego czasu zrobił instrukcje mnożenia, które nie używają eflags, tylko używaja osobnego rejestru na bity przeniesienia, co umożliwia chociażby ILP. Poczytaj tutaj: http://www.intel.se/content/dam/www/public/us/en/documents/white-papers/ia-large-integer-arithmetic-paper.pdf

Na koniec ważna uwaga:

karpov napisał(a)

zaimplementowałem algorytm RSA.

Nigdy w życiu nie rób tego na produkcji.

0

Dzięki wielkie wszystkim za pomoc. Porzuciłem pomysł samodzielnego implementowania RSA.

Zamiast tego użyłem biblioteki zaproponowanej przez @Bartosz Wójcik (świetna!). Przekazuje klucz między klientem a serwerem za pomocą algorytmu Diffie–Hellmana a potem szyfruje pakiety algorytmem AES gotowym do użycia w bibliotece tforge.

1 użytkowników online, w tym zalogowanych: 0, gości: 1