c++

Szyfrowanie XOR One Time Pad

Idęą szyfrowania one time pad jest to, że do każdej wiadomości generujemy jednorazowy klucz długości tej wiadomości. Jest to sposób na szyfrowanie bardzo bezpieczne krótkich wiadomości.

Jedynym mankamentem samej metody jest fakt że przed przesłaniem zaszyfrowanej wiadomości musimy przesłać również klucz.

Implementacja

#include <cstdlib>
#include <iostream>
#include <string>
using namespace std;
void print_string(char string[], int len) {
int i=0;
while(i<len){
 cout<<string[i];
 i++;
}
}
int main(int argc, char *){
char key[20], msg[50], crypt[50], decrypt[50];
cout<<"podaj dlugosc klucza(0 to dl. wiadomosci): ";
int key_len;
cin>>key_len;
cout<<"podaj wiadomosc: ";
cin>>msg;
if(key_len==0) {
 key_len=strlen(msg);
}
int msg_len = strlen(msg);
srand((unsigned)time(0));
for(int i=0; i<key_len; i++){
 key[i]=(char)(rand()%256);
}
cout<<"\n\n\nklucz: ";
print_string(key, key_len);
cout<<"\tdlugosc klucza: "<<strlen(key)-1<<"\tdlugosc wiadomosci: "<<strlen(msg)<<endl;
int i=0;
while(i<msg_len){
 int cur_key_char=0;
 if(i>strlen(key))
  cur_key_char = i % key_len ;
 crypt[i] = msg[i]^ key[cur_key_char];
 i++;
}
cout<<"\n\ncrypted:\n";
print_string(crypt, msg_len);
print_string(decrypt, msg_len);
int crypt_len = strlen(crypt);
cout<<"\n\nshould be:\n";
print_string(msg, msg_len);
i=0;
while(i<msg_len){
 int cur_key_char=0;
 if(i>strlen(key))
  cur_key_char = i % key_len ;
 decrypt[i] = crypt[i] ^ key[cur_key_char];
 i++;
}
cout<<"\n\ndecrypted:\n";
print_string(decrypt, msg_len);
cout<<"\n\n\n\n";
system("PAUSE");
return EXIT_SUCCESS;
}

Do pobrania również wersja skompilowana plus źródło: Onetimepad XOR

Tags: , ,

niedziela, Marzec 2nd, 2008 c++, kryptografia, uczelnia Brak komentarzy

Implementacja algorytmu RSA w C++

Witam,

Dzisiaj chciałbym przedstawić wam implementacje algorytmu RSA( Ronald Rivest, Adi Shamir, Leonard Adleman). Wykorzystując potężną bibliotekę LiDIA (strona domowa biblioteki: http://www.cdc.informatik.tu-darmstadt.de/TI/LiDIA/)

Najpierw przedstawie algorytm:

  1. Losujemy dwie duże(ok 1024 bity tj. Liczba składająca się z 300 cyfr) liczby pierwsze p i q, oraz liczbę e = (p − 1)(q − 1).
  2. Następnie obliczamy d = e^{-1} \mod (p-1)(q-1) (ponieważ wybraliśmy względnie pierwsze e, ma ono odwrotność i obliczyć ją możemy szybko rozszerzonym algorytmem Euklidesa)
  3. W kolejnym kroku obliczamy n która jest iloczynem p i q
  4. Klucz publiczny to para (e,n), klucz prywatny zaś to para (d,n). Liczby p i q należy zniszczyć.
  5. Szyfrujemy wiadomość M za pomocą: c=m^e mod n (c- kryptogram, wiadomość zaszyfrowana = wiadomość m do potęgi e modulo n)
  6. Żeby M zdeszyfrować podnosimy zaszyfrowaną wiadomość do potęgi d. Zgodnie z twierdzeniem Eulera dostaniemy oryginalną wiadomość (o ile m nie jest wielokrotnością p lub q): c^d = m^(ed) = m mod n

Implementacja:

#include <LiDIA/bigint.h>
#include <iostream>using namespace std;
using namespace LiDIA;
bigint get_liczba() {
     bigint rand_liczba;
     bigint max = 1;
     shift_left(max, max, 1024); // powiększamy liczbę do 1024 bajtów wielkości
     do  {
       rand_liczba.randomize(max);
     }while(!is_prime(rand_liczba));
     return rand_liczba;
}
int main(){
    bigint p, q;
    // losowanie p i q
    do{
        p = get_liczba();
        q = get_liczba();
    }
    while(p==q);
    //licznie n
    bigint n;
    n = p * q;
    bigint fi;
    fi = (p-1)*(q-1);
    bigint u,v,e;
    do {
      e.randomize(fi);
      e++;
    }while(xgcd(u,v,e,fi)!=1);
    bigint m,c,de;
    m=50000; // nasza wiadomość
    cout<<"message: "<<m<<endl;
    if (u<0){
      u=u%fi;
    }
    power_mod(c,m,e,n);
    cout<<"zaszyfrowane = "<<c<<endl<<endl;
    power_mod(de,c,u,n);
    cout<<"odszyfrowane = "<<de<<endl<<endl;
 }

Kompilacja:

g++ -O test.cc -I/usr/local/include -L/usr/local/lib -o test -lLiDIA -lgmp -lm

Opis Funkcji:

  • bigint xgcd(bigint & u, bigint & v, const bigint & a, const bigint & b) – funkcja oblicza (a, b) = au + vb)
  • void power_mod (bigint & res, const bigint & a, const bigint & n, const bigint m, int err = 0) – funkcja oblicza res = a^n (mod m)
  • void div_rem (bigint & q, bigint & r, const bigint & a, const bigint & b) – funkcja oblicza: q i r takie, że a = qb + r
  • bool is_prime (const bigint & a, int n = 10) – funkcja zwraca wartość true jeśli a jest liczbą pierwszą(Prawdopodobieństwo tego, że a jest liczbą pierwszą jest nie mniejsze niż 1 – 1/(4^n) )

wtorek, Luty 19th, 2008 c++, kryptografia 2 komentarzy

Search

 

Archiwa