RSA - tworzenie kluczy, szyfrowaie do pliku, deszyfrowanie pliku

0

Mam program napisany, niestety problem jest taki, że zakodowana liczba nie zgadza się z liczba odkodowaną.
PS. Jestem ze studiów matematycznych, a to program na dodatkowe punkty.

#include <bits/stdc++.h> 
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include<math.h>
#include <string>

using namespace std;

// Potęgowanie modulo, zwróci a do potęgi b modulo m

int potegowanie_modulo(int a, int b, int m) 
{ 
    int wynik = 1;   //tutaj ustalam wartość początkową dla 'wynik'
    a = a % m;  // a zmieniam na a modulo m
                
    while (b > 0) //wykonuje pętle tak długo, jak potęga przy a jest większa od zera
    { 
        
        if (b & 1) //b & 1 - daje mi 0 lub 1 w potędze
            wynik = (wynik*a) % m; 
  
        
        b = b>>1; // b = b/2 
        a = (a*a) % m; 
    } 
    return wynik; 
} 
  
//Moja funkcja będze zwracać false lub true

bool rabin_miller(int p, int n) 
{ 
    // Muszę wylosować jakąś liczbę od 2 do n-2, n chcę żeby były większe od 4
    
    int x = 2 + rand() % (n - 4); 
  
    // Używam potegowania modulo i robię x^p % n 
    int a = potegowanie_modulo(x, p, n); 
  
    if (a == 1  || a == n-1) 
       return true; //zwraca prawdę jeżeli a=1 lub a=n-1
  
    // Muszę uważać na sytuacje, kiedy p nie osąga n-1, a^2 modulo n nie jest 1 lub nie jest n-1 
    
    while (p!= n-1) 
    { 
        a = (a * a) % n; 
        p*= 2; 
  
        if (a == 1)      return false; 
        if (a == n-1)    return true; 
    } 
  
    return false; // zwraca falsz jezeli a jest rozne od 1 i n-1
} 
  
//k ma mi określić poziom dokładności, n jest wprowadzaną liczbą

bool sprawdzanie_czy_pierwsza(int n, int k) 
{ 

    if (n <= 1 || n == 4)  return false; 
    if (n <= 3) return true; 
  
    // Szukam jakiegoś r takiego, że  n = 2^p * r + 1  - czyli rozkład przez NWD
    int p = n - 1; 
    while (p % 2 == 0) 
        p /= 2; 
  
    // powtarzanie testu k razy i zwracanie true lub false
    for (int i = 0; i < k; i++) 
         if (!rabin_miller(p, n)) 
              return false; 
  
    return true; 
} 


int NWD(int a, int b)
{		
        while(!b==0){ //pętla, wykonuje warunek tak dlugo az warunek jest spelniony
        int c=a%b; 
        a=b;
        b=c;
        }
     return a;
}


long long losowanie_liczby() {
     long long wylosowana;
    srand( time( NULL ) );     
     int k=10;
	 do  {
       wylosowana=rand();
     }
	 	while(sprawdzanie_czy_pierwsza(wylosowana,k)!=1);
     		return wylosowana;    
}

int odwr_mod(int a, int n)
{
  int a0,n0,p0,p1,q,r,t;

  p0 = 0; p1 = 1; a0 = a; n0 = n;
  q  = n0 / a0;
  r  = n0 % a0;
  while(r > 0)
  {
    t = p0 - q * p1;
    if(t >= 0)
      t = t % n;
    else
      t = n - ((-t) % n);
    p0 = p1; p1 = t;
    n0 = a0; a0 = r;
    q  = n0 / a0;
    r  = n0 % a0;
  }
  return p1;
}


int main()
{
	int p,q;
	
do{
        p = losowanie_liczby();
        q = losowanie_liczby();
    }
    while(p==q);


cout<<"\n p="<<p;
cout<<"\n q="<<q;

int n,m;
n=p*q;
m=(p-1)*(q-1);

cout<<"\n n="<<n;
cout<<"\n m="<<m;
    
int e=2;
    while(e<m){
    int wynik = NWD(e,m);
    if(wynik==1)
        break;
    else
        e++;
    }
 
    cout<<"\n e="<<e;
    
cout<<"\n klucz publiczny: ("<<n<<","<<e<<")";

//dotąd klucz publiczny

int d;
d = odwr_mod(e,m);

cout<<"\n d="<<d;	

cout<<"\n klucz prywatny: ("<<n<<","<<d<<")";

//dotąd klucz prywatny

//teraz zmiana znaków na liczbę

ifstream plik("rsaodczyt.txt");
char znak;
plik>>znak;
int zmiana;
zmiana=(int)znak;

//teraz szyfrowanie

int a=zmiana;

cout<<"\n do szyfrowania mam a="<<a;
int c;
c=(a^e)%n;

cout<<"\n c="<<c;

plik.close();

ofstream plik2("rsazapis.txt");
if(plik2){
plik2<<c<<endl;
}
plik2.close();

//teraz odszyfrowanie i tutaj muszę się bawić w wiele znaków

int liczba;
ifstream plik3;
plik3.open("rsazapis.txt");
while (!plik3.eof())// EOF -End Of File
{

plik3>>liczba;

}
plik3.close();

cout<<"\n odczytano="<<liczba<<endl;

int t;
t=(liczba^d)%n;

cout<<"odszyfrowano t="<<t;
}
0

Trochę na szybko.
Czy zakres nie jest przekraczany w operacjach mnożenia, np.
a = (a*a) % m;

Tu problem może być potencjalnie z wcześniejszym zapisem zakończonym endl - to jest w sumie dodatkowy znak lub dwa (w zależności od systemu \n lub \r\n):

//teraz odszyfrowanie i tutaj muszę się bawić w wiele znaków
 
int liczba;
ifstream plik3;
plik3.open("rsazapis.txt");
while (!plik3.eof())// EOF -End Of File
{
 
plik3>>liczba;
 
}
plik3.close();

Przy odczycie i zapisie używasz logicznego XORa:
c=(a^e)%n; i t=(liczba^d)%n; w C/C++ nie ma potęgowania tym operatorem.

0

Jak wyżej, ^ to nie jest operacja potęgowania. Co więcej to by nie zadziałało nawet jakby to było potęgowanie bo robisz tam wesoło msg^e % n a już sama operacja msg^e by przekroczyła zakres zmiennych. Należy tam użyć funkcji powmod którą zresztą już masz -> potęgowanie_modulo
I mała uwaga:

m=(p-1)*(q-1);

Nazwałbym tą zmienną fi albo phi, żeby trzymać się ogólnie przyjętych oznaczeń ;)

0

Zmieniłam c i t, teraz jest potegowanie modulo z funkcji. Ale nadal źle wychodzi. t powinno wyjść identyczne jak a.
screenshot-20190205103004.png

Ps. na zajęciach mieliśmy m, dlatego napisałam m :) Żeby mi nie zarzucono, że skopiowałam skądś.

EDIT: Sprawdziłam dla liczb p i q mniejszych niż 100. Wówczas program działa co oznacza, że gdzieś nie wyrabia na dużych liczbach.

0

Poprawione formatowanie

#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <math.h>
#include <string>

using namespace std;

// Potęgowanie modulo, zwróci a do potęgi b modulo m
int potegowanie_modulo(int a, int b, int m)
{
    int wynik = 1; //tutaj ustalam wartość początkową dla 'wynik'
    a = a % m; // a zmieniam na a modulo m

    while (b > 0) //wykonuje pętle tak długo, jak potęga przy a jest większa od zera
    {

        if (b & 1) //b & 1 - daje mi 0 lub 1 w potędze
            wynik = (wynik * a) % m;

        b = b >> 1; // b = b/2
        a = (a * a) % m;
    }
    return wynik;
}

//Moja funkcja będze zwracać false lub true
bool rabin_miller(int p, int n)
{
    // Muszę wylosować jakąś liczbę od 2 do n-2, n chcę żeby były większe od 4

    int x = 2 + rand() % (n - 4);

    // Używam potegowania modulo i robię x^p % n
    int a = potegowanie_modulo(x, p, n);

    if (a == 1 || a == n - 1)
        return true; //zwraca prawdę jeżeli a=1 lub a=n-1

    // Muszę uważać na sytuacje, kiedy p nie osąga n-1, a^2 modulo n nie jest 1 lub nie jest n-1

    while (p != n - 1) {
        a = (a * a) % n;
        p *= 2;

        if (a == 1)
            return false;
        if (a == n - 1)
            return true;
    }

    return false; // zwraca falsz jezeli a jest rozne od 1 i n-1
}

//k ma mi określić poziom dokładności, n jest wprowadzaną liczbą
bool sprawdzanie_czy_pierwsza(int n, int k)
{
    if (n <= 1 || n == 4)
        return false;
    if (n <= 3)
        return true;

    // Szukam jakiegoś r takiego, że  n = 2^p * r + 1  - czyli rozkład przez NWD
    int p = n - 1;
    while (p % 2 == 0)
        p /= 2;

    // powtarzanie testu k razy i zwracanie true lub false
    for (int i = 0; i < k; i++)
        if (!rabin_miller(p, n))
            return false;

    return true;
}

int NWD(int a, int b)
{
    while (!b == 0) { //pętla, wykonuje warunek tak dlugo az warunek jest spelniony
        int c = a % b;
        a = b;
        b = c;
    }
    return a;
}

long long losowanie_liczby()
{
    long long wylosowana;
    srand(time(NULL));
    int k = 10;
    do {
        wylosowana = rand();
    } while (sprawdzanie_czy_pierwsza(wylosowana, k) != 1);
    return wylosowana;
}

int odwr_mod(int a, int n)
{
    int a0, n0, p0, p1, q, r, t;

    p0 = 0;
    p1 = 1;
    a0 = a;
    n0 = n;
    q = n0 / a0;
    r = n0 % a0;
    while (r > 0) {
        t = p0 - q * p1;
        if (t >= 0)
            t = t % n;
        else
            t = n - ((-t) % n);
        p0 = p1;
        p1 = t;
        n0 = a0;
        a0 = r;
        q = n0 / a0;
        r = n0 % a0;
    }
    return p1;
}

int main()
{
    int p, q;

    do {
        p = losowanie_liczby();
        q = losowanie_liczby();
    } while (p == q);

    cout << "\n p=" << p;
    cout << "\n q=" << q;

    int n, m;
    n = p * q;
    m = (p - 1) * (q - 1);

    cout << "\n n=" << n;
    cout << "\n m=" << m;

    int e = 2;
    while (e < m) {
        int wynik = NWD(e, m);
        if (wynik == 1)
            break;
        else
            e++;
    }

    cout << "\n e=" << e;

    cout << "\n klucz publiczny: (" << n << "," << e << ")";

    //dotąd klucz publiczny

    int d;
    d = odwr_mod(e, m);

    cout << "\n d=" << d;

    cout << "\n klucz prywatny: (" << n << "," << d << ")";

    //dotąd klucz prywatny

    //teraz zmiana znaków na liczbę

    ifstream plik("rsaodczyt.txt");
    char znak;
    plik >> znak;
    int zmiana;
    zmiana = (int)znak;

    //teraz szyfrowanie

    int a = zmiana;

    cout << "\n do szyfrowania mam a=" << a;
    int c;
    c = (a ^ e) % n;

    cout << "\n c=" << c;

    plik.close();

    ofstream plik2("rsazapis.txt");
    if (plik2) {
        plik2 << c << endl;
    }
    plik2.close();

    //teraz odszyfrowanie i tutaj muszę się bawić w wiele znaków

    int liczba;
    ifstream plik3;
    plik3.open("rsazapis.txt");
    while (!plik3.eof()) // EOF -End Of File
    {

        plik3 >> liczba;
    }
    plik3.close();

    cout << "\n odczytano=" << liczba << endl;

    int t;
    t = (liczba ^ d) % n;

    cout << "odszyfrowano t=" << t;
}

https://wandbox.org/permlink/EdXawRAEyU5LehGw

prog.cc:76:12: warning: logical not is only applied to the left hand side of this comparison [-Wlogical-not-parentheses]
    while (!b == 0) { //pętla, wykonuje warunek tak dlugo az warunek jest spelniony
           ^  ~~

To też jest źródłem błędów.

Skasuj wszystkie komentarze które opisują oczywistości, bo zamiast pomagać rozpraszają:

//tutaj ustalam wartość początkową dla 'wynik'
// a zmieniam na a modulo m
//Moja funkcja będze zwracać false lub true
//pętla, wykonuje warunek tak dlugo az warunek jest spelniony
...

Możesz się też zainteresować pisaniem testów do kodu (gtest - jest najlepszy i najwygodniejszy).
Jako matematykowi powinno ci to odpowiadać. To bardzo ułatwia szukanie błędów w kodzie.

0

Poprawiłam while. t cały czas wychodzi źle chyba, że zmienię p i q na małe liczby pierwsze.

0

najpierw jest wykonywane !b czyli wyjdzie zero jeśli b nie jest zerem, a potem jest wykonywane porównanie do zera.
W sumie jak się zastanowić to wychodzi to samo (wyrobiony odruch do naprawiania ostrzeżeń).

0
MarekR22 napisał(a):

najpierw jest wykonywane !b czyli wyjdzie zero jeśli b nie jest zerem, a potem jest wykonywane porównanie do zera.
W sumie jak się zastanowić to wychodzi to samo (wyrobiony odruch do naprawiania ostrzeżeń).

Tak czy siak poprawiłam i usunęłam teksty.
Program z tego co widzę traci się przy n większym od 40 tyś

screenshot-20190205111809.png
screenshot-20190205111750.png

1

Problem pojawia się już tutaj:

n=p*q;
m=(p-1)*(q-1);

Losujesz dwie liczby p, q, ale przecież jak je pomnożysz to mogą wyjść poza zakres! Bezpiecznie byłoby losować te liczby mniejsze niż pierwiastek z maxint, bo wtedy ich iloczyn nadal będzie się mieścił w zakresie int.
Ale dalej nie lepiej, bo popatrz jak działa square then multiply (twoje potęgowanie modularne):

wynik = (wynik*a) % m; 

I tutaj wynik < m i a < m więc siłą rzeczy wynik * a < m^2 ale w przypadku za dużego m, wartość m^2 przekracza zakres inta, bo nawet jeśli wylosujesz p i q mniejsze od sqrt(maxint) to nadal m < maxint a my potrzebujemy jednak m < sqrt(maxint)

0
Shalom napisał(a):

Problem pojawia się już tutaj:

n=p*q;
m=(p-1)*(q-1);

Losujesz dwie liczby p, q, ale przecież jak je pomnożysz to mogą wyjść poza zakres! Bezpiecznie byłoby losować te liczby mniejsze niż pierwiastek z maxint, bo wtedy ich iloczyn nadal będzie się mieścił w zakresie int.

To może być to faktycznie. Tylko nigdy nie używałam takiego warunku w losowaniu, jak to rozpisać?

A jakby int zmienić na long long? Pomoże to coś?

0

dla gcc możesz dodać flagę -ftrapv żeby wyłapać integer overflow.
Jak umiesz korzystać z debuggera to wyłapiesz wszystkie miejsca, gdzie trzeba to poprawić.

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