Hallo Leute!
Hier mal ein kleines Beispiel wie man mit Primzahlen rechnen und verschlüsseln kann.
Vorab eine klitzekleine Erklärung
Zuerst Punkt 5 wählen und die Grenzen festsetzen, bzw 3000 und 4000.
Danach werden die Primzahlen in diesen Bereich gesetzt.
Die beiden größten bilden die Grundlage zum verschlüsseln
Beispiel, hier wurden als Grenzen 1000 und 2000 gewählt:
- generiere 2 Primzahlen p und q (bzw 991 und 997)
- beide Primzahlen miteinander multiplizieren = N = 988027
- Hilfszahl generieren z = (991 - 1)* (997 - 1) = 990 * 996 = 986040
- Schlüsselzahlen E und D bestimmen
E muss eine zu z teilerfremde Primzahl sein
D muss wenn mit E multipliziert, das Ergebnis muss bei einer Division durch z den Rest 1 ergeben.
Bedingung ist (E * D) % z = 1
oder 986040 * 2 = 1972080
986040 * 3 = 2958120
Wenn z = 986040 dann ist (E*D) mindestens = 986041
986040 * 2 = 1972080
1972080 +1 = 1972081
mögliche Teiler 643, 3067
Bei E = 140863 (Primzahl) * 7 = 986041
Bei E = 3067 (Primzahl) * 643 = 1972081 D ist dann 643
Mit Klartextbuchstabe(Zahl)^ E wird verschlüsselt. Daher brauchen wir eine selbstgebastelte
Funktion um immer wieder zwischendurch die Zahl N abzuziehen, falls die Potenz größer wird als N.
Das Ergebnis ist dann kleiner als N.
Entschlüsselt wird die Chiffrierte Zahl mit CodierteZahl^D. Auch hier wird immer wieder N
abgezogen wenn die Potenz größer sein sollte als N. Das Ergebnis ist dann die Klartextzahl.
Das hat aber einen Haken. Wenn die Klartextzahl 0 oder 1 ist, kommt Mist raus.
Daher um den Haken zu umgehen sollte man bei binären Dateien eine Zahl dazu zählen, etwa 11
oder eine andere. Kann ja auch sechsstellig sein. Dadurch wird aber die chiffrierte Datei
acht mal länger als die uncodierte Datei.
Die chiffrierte Zahl ist im jeden Fall größer als 255. Sie sollte als unsigned long abgespeichert
werden.
Deshalb bitte D also immer Größer als E wählen.
Zum kodieren braucht man also N und E.
Zum dekodieren N und D.
zuerst wieder die Header, hier primel.h:
#ifndef PRIMEL_H_INCLUDED
#define PRIMEL_H_INCLUDED
#include <iostream>
#include <iomanip>
#include <string.h>
class primelchen
{
public:
primelchen();
~primelchen();
int primtest( unsigned long nummer);
void teilbarkeit(unsigned long zahl);
unsigned long zhl;
unsigned long faktorensumme;
unsigned long Faktorentest(void); //unsigned long zahl, unsigned long (*faktoren)[100]);
void primzahlen(void);
void Probe (void);
void Einzelfaktoren(void);
unsigned long zahl, c, e, faktoren[100], kleinste, groesste, slei;
unsigned long i, p, q, p1, q1, z, z1, N, E, D, lim;
};
void clpuf(void);
int MenueFrage(void);
#endif // PRIMEL_H_INCLUDED
nun primel.cpp:
#include "primel.h"
primelchen::primelchen()
{
kleinste = 0;
groesste = 100;
}; // Konstruktor
primelchen::~primelchen()
{}; // Destruktor
//Prüft ob eine Zahle eine Primzahl ist oder nicht, wenn nein Rückgabe 0, wenn ja Rückgabe 1
int primelchen::primtest( unsigned long nummer)
{
unsigned long slei, a, c, e;
e = 1;
a = (nummer / 2) + 2;
// Testet nummer auf Teilbarkeit durch slei nur bis kleiner nummer, da jede Zahl durch sich selbst teilbar ist
for(slei = 2; slei < a; slei++)
{
c = nummer % slei;
//cout << "nummer=" << nummer << " slei=" << slei << " c=" << c << endl;
// Wenn nummer keine Primzahl ist, abbrechen, da weitere Überprüfung unnötig
if((c == 0) && (slei < nummer)) { e = 0; break; }
}
return e;
}
// Stellt fest, durch welche Zahlen das Argument "zahl" teilbar ist
void primelchen::teilbarkeit(unsigned long zahl)
{
unsigned long slei, c, e;
int spz = 0;
std::cout << std::endl << "Zahl teilbar durch " << std::endl;
for(slei = 2; slei <= zahl; slei++)
{
c = zahl % slei;
if(c == 0)
{
std::cout << slei << " ";
e = primtest(slei);
if (e == 1) std::cout << "(Primzahl) " << std::endl;
if (spz > 25) {spz = 0; std::cout << std::endl;}
spz++;
}
}
}
// Stellt fest, ob die Faktoren richtig ermittelt wurden
void primelchen::Probe(void) //unsigned long faktoren[], unsigned long e)
{
unsigned long zahl, slei;
std::cout << std::endl << "Probe: " << std::endl;
std::cout << "Zahl der Faktoren: " << e << std::endl;
for ( slei = 0; slei < e; slei++)
std::cout << std::endl << slei +1 << ". ter Faktor " << " = " << faktoren[slei] ;
std::cout << std::endl;
zahl = 1;
faktorensumme = 0;
for ( slei = 0; slei < e; slei++)
{
std::cout << faktoren[slei];
if (slei < e - 1) std::cout << "*";
faktorensumme += faktoren[slei];
zahl *= faktoren[slei];
}
std::cout << "=" << zahl << std::endl << "Zahl wurde berechnet" << std::endl;
std::cout << "Summe aller Faktoren: " << faktorensumme << std::endl;
if ( c == faktorensumme) std::cout << "Vollkommene Zahl" << std::endl;
}
// Ermittelt die einzelnen Faktoren einer zu testenden Zahl
unsigned long primelchen::Faktorentest(void) //unsigned long zahl, unsigned long (*faktoren)[100])
{
unsigned long slei, sleib, a, b, c, d, e;
a = zahl;
b = 0;
d = 0;
e = 0;
for (slei= 2; slei <= ((zahl / 2) + 2); slei++)
{
c = primtest(slei);
if (c == 1)
{
for (sleib = 2; sleib <= 25; sleib++)
{
b = a / slei;
d = a % slei;
if (d) break;
std::cout << std::endl << "b = a / slei: " << b << " = " << a << "/ " << slei << "(primzahl)";
faktoren[e++] = slei;
a = b;
if (b == 1) goto fertig;
}
}
}
fertig: return e;
}
void primelchen::primzahlen(void)
{
std::cout << std::endl << "Primzahlen zeigen";
std::cout << std::endl << "Bitte kleinste Zahl eingeben: ";
std::cin >> kleinste;
std::cout << std::endl << "Bitte größte Zahl eingeben: ";
std::cin >> groesste;
std::cout << std::endl;
for (slei = kleinste; slei <= groesste; slei++)
{
c = primtest(slei);
if (c == 1) std::cout << " " << slei << " ";
}
}
void primelchen::Einzelfaktoren(void)
{
std::cout << std::endl << "Zahl auf Faktoren prüfen";
std::cout << std::endl << "Bitte eine Zahl eingeben: ";
std::cin >> zahl;
c = primtest(zahl);
if(c == 1)
std::cout << std::endl << " Zahl ist selber Primzahl: " << c;
else
{
std::cout << std::endl << "Weiter mit berechnen" << std::endl;
teilbarkeit(zahl);
e = Faktorentest();
Probe();
}
}
void clpuf(void)
{
while (getc(stdin) != '\n')
;
}
int MenueFrage(void)
{
int frage = 18, i;
std::string wastun = "";
std::string erge[16] = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10","11","12","13","14","15"};
std::cout << std::endl << "Ihre Wahl: ";
std::cin >> wastun; // frage
for (i = 0; i < 16; i++)
{
if (wastun.compare(erge[i]) == 0)
{
frage = i;
break;
}
}
clpuf();
return frage;
}
zum Schluss main.cpp:
// Primelchen.cpp
// Ein Programm das Primzahlen ermittelt
// und einzelne Zahlen in ihre Primzalen zerlegt und anzeigt
#include "primel.h"
#include "menuefrage.cpp"
using namespace std;
unsigned long Powerb(unsigned long x, unsigned long y, unsigned long N)
{
unsigned long p = x, k = 0, q;
if (y > 1)
for (k = 1; k < y; k++)
{
p *= x;
q = p / N;
if (p > N) p -= q * N;
}
return p;
}
int main(void)
{
primelchen primula;
int frage = 11, numze = 0, isprim = 0, Prim_is_set = 0;
union longtochar
{
long lwert;
char bytes[8];
}ltch;
char text[300] = {0};
int lge = 0, in;
long chiffriert[30] = {0};
long dechiffriert[30] = {0};
do
switch(frage)
{
default:
cout << endl << "Primfaktorenrechner:";
cout << endl << "Programm beenden............0";
cout << endl << "Zahl auf Faktoren prüfen....1";
cout << endl << "Primzahlen errechnen........2";
cout << endl << "Teiler errechnen............3";
cout << endl << "Werte setzen................5";
cout << endl << "Text codieren...............6";
frage = MenueFrage();
break;
case 0:
cout << endl << "Programmende" ; return 0;
break;
case 1:
primula.Einzelfaktoren();
frage = 11;
break;
case 2:
primula.primzahlen();
frage = 11;
break;
case 3:
cout << endl << "Natürliche Teiler bestimmen";
std::cout << std::endl << "Bitte eine Zahl eingeben: ";
std::cin >> primula.zhl;
primula.faktorensumme = 0;
numze = 0;
for (primula.i = 1; primula.i < primula.zhl; primula.i++)
{
if ( (primula.zhl % primula.i) == 0)
{
std::cout <<"Nr.: " << setw(5) << numze << " Teiler: " << primula.i;
//Prüft ob eine Zahle eine Primzahl ist oder nicht, wenn nein Rückgabe 0, wenn ja Rückgabe 1
isprim =primula.primtest(primula.i);
if(isprim) std::cout << " Primzahl" << std::endl;
else std::cout << std::endl;
primula.faktorensumme += primula.i;
numze++;
}
}
frage = 11;
if ( primula.zhl == primula.faktorensumme) std::cout << "Teilersumme: " << primula.faktorensumme << " Vollkommene Zahl" << std::endl;
break;
case 5:
primula.N = 988027;
//long Z = 986040;
primula.E = 7;
primula.D = 634;
std::cout << std::endl << "Werte setzen" << std::endl;
primula.kleinste = 2000;
primula.groesste = 3000;
std::cout << std::endl << "Bitte kleinste Zahl eingeben: ";
std::cin >> primula.kleinste;
std::cout << std::endl << "Bitte größte Zahl eingeben: ";
std::cin >> primula.groesste;
numze = 0;
primula.p = primula.q = 0;
// zuerst die Primfaktoren bestimmen
for (primula.slei = primula.kleinste; primula.slei <= primula.groesste; primula.slei++)
{
primula.c = primula.primtest(primula.slei);
if (primula.c == 1)
{
std::cout << " " << primula.slei << " ";
if ((primula.p == 0) && (primula.q == 0)) primula.p = primula.slei;
if ((primula.p > 0) && (primula.q == 0)) primula.q = primula.slei;
if ((primula.p >= 0) && (primula.q >= 0))
{
primula.p = primula.q;
primula.q = primula.slei;
}
}
}
primula.N = primula.p * primula.q;
primula.p1 = primula.p - 1;
primula.q1 = primula.q -1;
primula.z = primula.p1 * primula.q1;
primula.z1 = primula.z + 1;
std::cout << std::endl << std::endl << "p = " << primula.p << " q = " << primula.q << std::endl;
std::cout <<"N = " << primula.N << std::endl;
std::cout <<"p1 = " << primula.p1 << " q1 = " << primula.q1 << std::endl;
std::cout <<"z = " << primula.z << std::endl;
std::cout <<"z1 = " << primula.z1 << std::endl;
primula.E = 0;
primula.zhl = (primula.z1 / 2) + 1;
std::cout <<"lim = " << primula.lim << std::endl;
std::cout <<"zhl = " << primula.zhl << std::endl;
std::cout << "--------------------" << std::endl;
for (primula.i = 1; primula.i < primula.zhl; primula.i++)
{
if ( (primula.z1 % primula.i) == 0)
{
std::cout <<"Nr.: " << setw(5) << numze << " Teiler: " << primula.i;
//Prüft ob eine Zahle eine Primzahl ist oder nicht, wenn nein Rückgabe 0, wenn ja Rückgabe 1
isprim = primula.primtest(primula.i);
if(isprim)
{
if (primula.i > primula.E) primula.E = primula.i;
std::cout << " Primzahl" << std::endl;
}
else std::cout << std::endl;
numze++;
}
}
//std::cout <<"\n\ni= " << primula.i << std::endl;
primula.D = primula.z1 / primula.E;
if(primula.E > primula.D) swap(primula.E, primula.D);
std::cout <<"E = " << primula.E << std::endl;
std::cout <<"D = " << primula.D << std::endl;
std::cout << std::endl << "Test ob E teilerfremd zu z" << std::endl;
if((primula.z % primula.E) == 0) std::cout << "Fehler: E nicht teilerfremd zu z" << std::endl;
else std::cout << "Zahlen E und D okay" << std::endl;
frage = 11;
Prim_is_set = 1;
break;
case 6:
if (Prim_is_set == 0)
{
std::cout << "noch keine Primzahlen und Werte unter Punkt 5 errechnet" << std::endl;
frage = 11;
break;
}
std::cout << "Chiffriertest" << std::endl;
std::cout << "Bitte einen Text eingeben" << std::endl;
std::cin.getline (text, 280);
lge = strlen(text);
printf("text unverschlüsselt:\n%s\n", text);
printf("\nverschluesselt:\n");
for (int in =0; in < lge; in++)
{
chiffriert[in] = Powerb(text[in], primula.E, primula.N); //encrypt
std::cout << chiffriert[in] << std::endl;
}
std::cout << "\nentschluesselt:\n";
for (in = 0; in < lge; in++)
{
dechiffriert[in] = Powerb(chiffriert[in], primula.D, primula.N); //encrypt
ltch.lwert = dechiffriert[in];
std::cout << ltch.bytes[0];
}
std::cout << "\n";
frage = 11;
break;
}while (frage != 4);
return(0);
}
/************Ende main.cpp***************************/
Ich bin zur Zeit arbeitslos und habe das ganze aus langer Weile geschrieben.
Was will man sonst mit 55 Jahren Alter anfangen?
Vielleicht kann es ja einer brauchen.
Viel Spaß
Guiseppe
05.03.2020, 17:56
Beispiel in QT für Primzahlenberechnung und textEdit