Primzahlen und RSA Code

Sebastian Pizer

miri3 schrieb:

Ich meine taugt mein bisheriger Code bisher überhaupt etwas?

Ich finde, der Ansatz könnte verbessert werden. Stichwort "separation of concerns". Deine Klasse scheint für alles verantwortlich zu sein, Schlüsselgenerierung, Ver/Entschlüsselung, Nachricht einlesen und umkodieren. So ein Objekt scheint alles mögliche zu speichern (den Schlüssel, die Nachricht, etc). Mach Dir erst mal Gedanken zu den Schnittstellen, dem Design.

Wäre es nicht viel praktischer wenn Du es so machtest:

Klasse für öffentlichen RSA-Schlüssel "RSAPubKey"
Klasse für Schlüsselpaar "RSAKeyPair" (hat eine getPubKey-Methode)
freie Funktion zum Generieren eines zufälligen Schlüsselpaars (bekommt als Parameter "einen Zufallsgenerator" und die Schlüssellänge. Sie liefert ein RSAKeyPair Objekt zurück)
freie Funktion zum Verschlüsseln (bekommt als Parameter einen RSAPubKey, eine Nachricht (Klartext) zB in Form von vector<unsigned char> und gibt einen vector<unsigned char> zurück als Chiffrat)
freie Funktion zum Entschlüsseln (bekommt als Parameter ein RSAKeyPair, den "Chiffre-Text" (zB vector) und gibt den Klartext (zB vector) zurück.
freie Funktionen zum Kodieren und Dekodieren von Textnachrichten (Zeichenkette <-> vector<unsigend char>)

unsigned char Sequenzen werden üblicherweise als Datenformat für kryptographische Algorithmen gewählt. Man will ja nicht nur Text verschlüsseln sondern allgemein beliebige Daten verarbeiten können.

Je nachdem, was das Programm eigentlich machen soll, fehlt da vielleicht noch die ein oder andere Funktion, beispielsweise das Abspeichern und Lesen von Schlüsseln.

Welche "BigInt"-Bibliotheken hast Du Dir denn bis jetzt angeguckt?
Gibt es ein Problem bei der Kokierung, Dekodierung von Nachrichten?
Gibt es ein Problem beim Einlesen, Speichern von Nachrichten?

Gruß,
SP

miri

Vielleicht nützt dir das was!
http://www.example-code.com/vcpp/rsa.asp

Vielen Dank. Das sieht ja sehr vielversprechend aus. Ich denke nur, dass diese CODE Beispiele nicht meinem eigentlichen Wissensstand entsprechen. Ich muss diesen Beleg ja auch verteidigen...:-( aber ich werde einmal versuchen zu verstehen, wie dort programmiert wurde.

Deine Klasse scheint für alles verantwortlich zu sein, Schlüsselgenerierung, Ver/Entschlüsselung, Nachricht einlesen und umkodieren. So ein Objekt scheint alles mögliche zu speichern (den Schlüssel, die Nachricht, etc). Mach Dir erst mal Gedanken zu den Schnittstellen, dem Design.

Ja da hast Du Recht. Ich habe auch schon darüber nachgedacht, mehrere Klassen anzuwenden. Ich denke ich habe das sogar versucht. Mein Problem war dann glaube ich, dass ich meine Variablen nicht mehr anwenden konnte in der anderen Klasse. Dann muss man doch meines Wissens mit Pointer oder so arbeiten-und davon hab ich nun gar keine Ahnung.

Deine vorgeschlagene Aufteilung finde ich sehr gut. Das macht das Ganze sicher auch übersichtlicher. Vielleicht fange ich einmal an das zu ordnen.

unsigned char Sequenzen werden üblicherweise als Datenformat für kryptographische Algorithmen gewählt. Man will ja nicht nur Text verschlüsseln sondern allgemein beliebige Daten verarbeiten können.

und was nehme ich stattdessen für einen Datentyp? Integer?

Welche "BigInt"-Bibliotheken hast Du Dir denn bis jetzt angeguckt?

Ich habe vor ein paar Wochen das erste mal gelesen, dass es überhaupt so etwas gibt. Mit dem Gedanken, so etwas zu verwenden habe ich schon gespielt-nur leider hatte ich in den letzten Wochen nicht soviel Zeit mich mit meinem Beleg zu beschäftigen...:-(

Gibt es ein Problem bei der Kokierung, Dekodierung von Nachrichten?

wie ich schon öfter erwähnt habe, fehlt mir die Brücke von der Schlüsselerzeugung zur Codierung der Eingabe (die gelesen werden soll) und umgekehrt.

Gibt es ein Problem beim Einlesen, Speichern von Nachrichten?

Na ja...hm...zum einlesen von ASCII hab ich ja schon einen kleinen Code geschrieben. Das Problem was ich an dieser Stelle hatte war, dass ich nicht wusste wie ich nun die ASCII Zeichen in vierer Blöcke zusammenfasse und meinetwegen in ein Array oder Vector oder sonstigem Speichere und den erzeugten Schlüsseln zuweise. Also irgendwie ist mir das grad noch ein wenig zu hoch:-(

Gruß von Mirjam

SeppJ

miri schrieb:

wie ich schon öfter erwähnt habe, fehlt mir die Brücke von der Schlüsselerzeugung zur Codierung der Eingabe (die gelesen werden soll) und umgekehrt.

Dies hier scheint wohl dein Hauptproblem zu sein. Machen wir mal ein ganz einfaches Beispiel, das man auf Papier oder mit einem guten Taschenrechner rechnen kann:
Nimm mal an, dein öffentlicher Schlüssel wäre 6499 und 23.
Wie würdest du die Zahl 25 verschlüsseln?

Wenn du obige Frage beantwortet hast, die nächste Frage: Wie würdest du die Zahlen 25 22 13 17 verschlüsseln?

Wenn du obige Frage beantwortet hast: Gibt es eine bijektive Abbildung von Zeichenfolgen auf Zahlenfolgen?

Wenn du obige Frage beantwortet hast: Wo liegt jetzt noch dein Problem?

Wenn du obige Fragen beantwortet hast: Der geheime Schlüssel ist 6499 und 551. Kommen wieder die richtigen Werte raus, wenn du entschlüsselst?

Wenn du obige Fragen beantwortet hast: Gib eine Möglichkeit an, wie ich das Schlüsselpaar erzeugt haben könnte.

Zusatzaufgabe: Angenommen ich hätte dir den geheimen Schlüssel nicht verraten, wie hättest du ihn trotzdem finden können? Bist du in der Lage mir einen geheimen Schlüssel zu 667 und 13 zu nennen?

Sebastian Pizer

miri schrieb:

unsigned char Sequenzen werden üblicherweise als Datenformat für kryptographische Algorithmen gewählt. Man will ja nicht nur Text verschlüsseln sondern allgemein beliebige Daten verarbeiten können.

und was nehme ich stattdessen für einen Datentyp? Integer?

unsigned char ist in der Hinsicht universell, weil Du jede Information als Folge von unsigned char kodieren kannst. Das geht natürlich auch mit unsigned int, allerdings wissen wir, dass unsigned char die kleinste addressierbare Speichereinheit mit mindestens (und üblicherweise genau) 8 Bit ist, bei der jede Bit-Kombnination einen gültigen unsigned char-Wert darstellt. (Diese Garantie gibt es nicht bei anderen Typen).

Text könntest Du ja einfach per std::memcpy in so einen unsigned char Puffer reinkopieren und rauskopieren.

miri schrieb:

Na ja...hm...zum einlesen von ASCII hab ich ja schon einen kleinen Code geschrieben. Das Problem was ich an dieser Stelle hatte war, dass ich nicht wusste wie ich nun die ASCII Zeichen in vierer Blöcke zusammenfasse und meinetwegen in ein Array oder Vector oder sonstigem Speichere und den erzeugten Schlüsseln zuweise.

Vierer-Blöcke? Du willst die Nachricht in so kleine Blöcke zerhacken um RSA drauf anwenden zu können? Mit was für einer Größenordnung der Moduli N rechnest Du? Zwischen 32-64 Bit? Denk daran, dass man solche kleinen Zahlen recht schnell faktorisieren und damit den Privatschlüssel aus dem öffentlichen Schlüssel zurückrechnen kann.

Außerdem sollte es für das, was in so einem Block drinsteht und per RSA verschlüsselt werden soll, viele versch Kombinationen geben. Statt einen 1024bittigen Schlüssel zu knacken, kann ich auch einfach alle Block-Kombinationen durchprobieren. Stell Dir vor, Alice fragt Bob eine Ja/Nein-Frage und Bob verschickt an Alice eine verschlüssete Antwort. Wenn ich die Antwort abfange, kann ich rausbekommen, ob Bob "Ja" oder "Nein" geschrieben hat, indem ich einfach beide Möglichkeiten selbst verschlüssele und die Ergebnisse mit der abgefangenen Nachricht vergleiche. Dafür muss ich den Privatschlüssel nicht kennen.

Du solltest also längere Schlüssel (um 1024 Bit) unterstützen und die Blöcke mit viel Information füllen, eventuell sogar mit Zufall auffüllen um das Ja/Nein-Beispiel von vorhin auszuhebeln. Brauchbare Anwendungen benutzen etwas OAEP-artiges (optimal assymetric encryption padding)

Wahrscheinlich ist das, was ich hier von mir gebe totaler Overkill. Die Abgabe eines nützlichen Programms ist wohl auch nicht Dein Ziel. ... RSA auf dem Papier sieht einfach aus. Das drum herum, was man braucht, es sicher und schnell anwenden zu können, ist da eigentlich die Hauptarbeit:

Ganzzahlarithmetik für große Zahlen
Implementierung des Square-and-Multiply Algorithmus modulo N für's Potenzieren
Zufallsgenerator
Primzahltest (siehe Miller-Rabin)
den erweiterten euklidischen Algorithmus
nochmal nachlesen, wie man Schlüssel "richtig" generiert (nicht alle p/q/e-Kombinationen sind sicher, e sollte zB mindestens 17 und keine Zweierpotenz sein)
Ein/Ausgabe
encryption padding

Gruß,
SP

miri

Dies hier scheint wohl dein Hauptproblem zu sein. Machen wir mal ein ganz einfaches Beispiel, das man auf Papier oder mit einem guten Taschenrechner rechnen kann:
Nimm mal an, dein öffentlicher Schlüssel wäre 6499 und 23.
Wie würdest du die Zahl 25 verschlüsseln?

ich habe zumindest diese Frage beantwortet denke ich zumindest. Falls ich auf dem richtigen Weg bin, dann würde ich mit den anderen Fragen weitermachen. Ich glaube das ist sehr hilfreich so ranzugehen. (Code siehe unten)

Wahrscheinlich ist das, was ich hier von mir gebe totaler Overkill. Die Abgabe eines nützlichen Programms ist wohl auch nicht Dein Ziel.

Da hast Du wohl recht. Es soll einfach so programmiert werden, wie es bei Wikipedia steht. Ich will das Programm ja nun nicht irgendwelchen Banken zur Verfügung stellen-brauche nur eine gute Note.

Vielen Dank und Gruß von Mirjam

#include <iostream>
#include <cmath>

using namespace std;

int n_pow(int K, int e, int ergebnis)
{

	ergebnis=K;
	//int help=1;
	for (int i = 1; i<=e; i++);
		ergebnis=ergebnis*K;

return ergebnis;
}

int main()
{
	int N, K, e, ergebnis, ergebnis_mod;

	N=6499;

	cout << "Das Ergebnis von 25^23 ist: " << n_pow(25,23,ergebnis) << endl;

	ergebnis_mod=n_pow(25,23,ergebnis) % N;

	cout << "Das Ergebnis von " << n_pow(25,23,ergebnis) << " mod " << N << " ist: " << ergebnis_mod << endl;

	return 0;

}

Sebastian Pizer

Das mit dem Potenzieren macht man anders. Deine Lösung ist sehr langsam und produziert ratzfatz Überläufe.

unsigned long pow_mod_n(unsigned long base, unsigned long power, unsigned long n)
{
   unsigned long result = 1;
   while (power>0) {
      base %= n;
      if (power & 1) {
         result *= base; // "multiply"
         result %= n;
      }
      base *= base;      // "square"
      power >>= 1;
   }
   return result;
}

Siehe binäre Exponentiation

Beachte: (a * b) mod n = ( (a mod n) * (b mod n) ) mod n

Damit es zu keinen Überläufen kommt, muss n hier kleiner gleich sqrt(ULONG_MAX) sein. Bei typischen Systemen ist ULONG_MAX = pow(2,32)-1. Du würdest Dich damit also auf 16Bit-Moduli begrenzen, welche man in wenigen Millisekunden faktorisieren und damit den privaten Schlüssel aus dem öffentlichen Schlüssel zurückrechnen kann.

edit: Hatte "return result;" vergessen.

Gruß,
SP

SeppJ

Hast du das mal ausprobiert? Du wirst sehen, dass dein Programm nur Mist macht. Rechne mal 25^23 mit dem Taschenrechner aus, dann siehst du, dass die Zahl niemals in einen int passen wird. Außerdem ist dein Verfahren zup Potenzieren exponentiell langsam.

Guck dir als Alternative zum Beispiel mal dies hier an:
http://www.cs.princeton.edu/courses/archive/spr05/cos126/lectures/22.pdf
(Seite 21 ff. für das Potenzieren, der Rest des Dokuments ist auch ganz gut)

Was mich jetzt aber wundert: Solche Sachen stehen in jeder Anleitung zu RSA. Den Link den ich dir oben gegeben habe, findet man auf Wikipedia. Hast du eigentlich überhaupt schonmal etwas zu dem Verfahren gelsesen?

edit: Da war Sebastian Pizer (mal wieder) schneller als ich.

miri

Ja sicher hab ich schon etwas dazu gelesen und auch viel gegoogelt. Ich bin nunmal eben nur kein Informatiker. Ihr habt da sehr viel Ahnung und ich bin ein blutiger Anfänger-leider.

Außerdem ist dein Verfahren zup Potenzieren exponentiell langsam.

ich weiß, dass ihr, die ihr viel Ahnung habt immer Wert auf schnelle Programme legt-ich bin froh wenn ich überhaupt irgendeinen Code zum laufen bekomme. An dem was ich bisher reingestellt habe, habe ich sehr lange gesessen und jeder Durchlauf ohne Fehler ist da wie ein Glückserlebnis.

Könnt ihr das verstehen

Rechne mal 25^23 mit dem Taschenrechner aus, dann siehst du, dass die Zahl niemals in einen int passen wird.

Hab ich gemacht-und nicht überprüft-da hast Du Recht.

Ich bin jetzt auch ziemlich verwirrt. Irgendwie soll ich für das RSA Verfahren integer nehmen und dann doch wieder nicht. Wisst ihr ich hab keine Informatik-Ausbildung. Grad mal ein Semester C++ gemacht-und hierbei nur ein wenig was zu Klassen gelernt. Da haben wir auch keine Algorithmen und Datenstrukturen behandelt, so wie es vll die Informatiker oder Mathematiker machen. Deshalb bin ich ein wenig aufgeschmissen grad
Das Schlimme daran ist, dass alle anderen aus meinem Semester einen Standardbeleg mit irgendeinem Fahrstuhl gemacht haben und ich gefragt habe ob ich nicht was mit Primzahlen machen kann, weil es mich interessiert-und nun habe ich den Salat....hm

Na gut

Gruß von Mirjam

Sebastian Pizer

miri schrieb:

Ich bin jetzt auch ziemlich verwirrt. Irgendwie soll ich für das RSA Verfahren integer nehmen und dann doch wieder nicht.

Ganzzahlen, nicht notwendigerweise "int". RSA ist nur sinnvoll mit großen Ganzzahlen. Da große Ganzzahlen nicht direkt von C und C++ unterstützt werden, muss man auf eine Bibliothek zurückgreifen, die das für einen erledigt -- also einen Typen zur Verfügung stellt, den man wie "int" benutzen kann, dafür aber beliebig große Zahlen speichern kann.

miri schrieb:

Wisst ihr ich hab keine Informatik-Ausbildung. Grad mal ein Semester C++ gemacht-und hierbei nur ein wenig was zu Klassen gelernt. Da haben wir auch keine Algorithmen und Datenstrukturen behandelt, so wie es vll die Informatiker oder Mathematiker machen. Deshalb bin ich ein wenig aufgeschmissen grad

Das Schlimme daran ist, dass alle anderen aus meinem Semester einen Standardbeleg mit irgendeinem Fahrstuhl gemacht haben und ich gefragt habe ob ich nicht was mit Primzahlen machen kann, weil es mich interessiert-und nun habe ich den Salat....hm

D.h. Du musst jetzt etwas "mit Primzahlen" abgeben?

Ich denke mal, dass Du nichts abgeben brauchst, was externe Bibliotheken benötigt. Die Korrektoren haben sicher keine Lust, sich diese Bibliotheken (wie zB GMP) zu installieren, um gucken zu können, ob das Programm wirklich das macht, was es machen soll.

Vorschlag: Bleib bei unsigned long. Das Prinzip ist ja eigentlich das gleiche. Dein Primzahltest dauert bei solchen kleinen Zahlen auch nicht zu lange. Nur mit unsigned long musst Du auf Überläufe aufpassen. unsigned long ist mindestens 32 Bit breit, n sollte dann im Interval [32768,65536) liegen. Damit hast Du 15 Bit für den Klartext zur Verfügung. Da kannst Du 3 Zeichen je 5 Bit reinquetschen:

#include <cctype>
#include <algorithm>

const char alphabet[] = "_ ABCDEFGHIJKLMNOPQRSTUVWXYZ.,:?";

unsigned zeichen_zu_zahl(int zeichen)
{
   zeichen = std::toupper(zeichen); // Grossbuchstaben
   const char* anfang = alphabet;
   const char* ende   = anfang + (sizeof(alphabet)-1);
   const char* posit  = std::find(anfang,ende,zeichen);
   if (posit==ende) return 0; // Code fuer '_' falls nicht gefunden
   return posit-anfang;       // sonst, Nummer 0-31
}

unsigned long drei_zeichen_zu_zahl(int z1, int z2, int z3)
{
   return (zeichen_zu_zahl(z1) << 10)
        | (zeichen_zu_zahl(z2) <<  5)
        |  zeichen_zu_zahl(z3);
}

Der Rückweg (15bit-Zahl --> 3 Zeichen) sei erstmal Dir überlassen. Funktionen und Klassen aus der Standardbibliothek kann man hier nachgucken. Dort findest Du auch std::toupper und std::find.

BTW: Ich habe kein einziges meiner Code-Beispiele getestet. Können also Fehler drin sein.

Gruß,
SP

D.h. Du musst jetzt etwas "mit Primzahlen" abgeben?

Nachdem ich den Vorschlag gemacht habe, hat der Dozent mir dann das Thema mit RSA gegeben. Also es soll ein "kleines" Programm werden mit dem man meinetwegen einen Satz im Eingabefeld verschlüsseln kann und in eine Datei schreiben kann. Der Text der in der Datei dann steht soll dann auch wieder entschlüsselbar sein.

Nur mit unsigned long musst Du auf Überläufe aufpassen

..-.mal eine ganz dumme Fragen. Was meinst Du eigentlich mit Überläufen?

BTW: Ich habe kein einziges meiner Code-Beispiele getestet. Können also Fehler drin sein.

In diesem scheint keiner drin zu sein. Ich hab ihn eben getestet. In dem davor hatte der Rückgabewert (return result) gefehlt. Ist ja nicht schlimm, ich bin sehr dankbar für Deine/eure Hilfe hier.

Was kann ich mit dem Code, den Du jetzt reingestellt hast anfangen

Sebastian Pizer

miri4 schrieb:

..-.mal eine ganz dumme Fragen. Was meinst Du eigentlich mit Überläufen?

siehe hier.
Das richtige Ergebnis von 90000*90000, 8100000000, passt nicht mehr in eine
32Bit-Variable rein.

miri4 schrieb:

In diesem scheint keiner drin zu sein. Ich hab ihn eben getestet. In dem davor hatte der Rückgabewert (return result) gefehlt.

Oh, stimmt!

miri4 schrieb:

Was kann ich mit dem Code, den Du jetzt reingestellt hast anfangen

Dabei geht's um das Packen von 3 Zeichen in eine 15bit-Zahl. Kannst Du natürlich auch anders machen. War nur eine Idee.

miri

Dabei geht's um das Packen von 3 Zeichen in eine 15bit-Zahl. Kannst Du natürlich auch anders machen. War nur eine Idee.

und wozu brauch ich das? Tut mir leid, wenn ich so dumme Fragen stellen muss..:-(

Also diese Übung, die Du mir reingestellt hattest. Sollte ich die vielleicht erstmal zu ende machen? Würde so die Verschlüsselung dann auch funktionieren? Na ich mach erst einmal die zweite Aufgabe von vorhin....sofern ich es heute noch schaffe.

Vielen Dank!

SeppJ

Was du aus den gestellten Übungsaufgaben mitnehmen solltest ist, dass du auch für wirklich simple Fälle nicht so naiv an das Problem rangehen kannst, wie du es bei deinem ersten Programm versucht hast. Du musst auch für eine reine Demoversion schon die fortgeschrittenen Algorithmen verwenden, die man bei echtem RSA verwendet. Und das ist wohl auch der Zweck deiner Arbeit, du sollst ja was dabei lernen.

Das Beispiel mit 6499 als öffentlichen Schlüssel ist schon so ziemlich minimal - die Zahl kann dir ein begabter Viertklässler in ein paar Stunden faktorisieren, ein Computer schafft das in Sekundenbruchteilen. Trotzdem funktioniert hier das Verschlüsseln schon nicht mehr, wenn man sich vorher nicht genau überlegt, was man machen muss.

Sebastian Pizer

miri schrieb:

und wozu brauch ich das? Tut mir leid, wenn ich so dumme Fragen stellen muss..

Für RSA brauchst Du nen "Klartext" K, der eine Zahl zwischen 2 und N-1 ist. Das heißt, dass Deine ursprüngliche Nachricht irgendwie umkodiert werden muss. Wenn Du Deine Schlüssel so auswählst, dass 32768+2 <= N < 65536 gilt, kannst Du 15 Bit an Information in K reinpacken, da N-2 >= 2^15 gilt. K=0 und K=1 funktionieren zwar auch, aber in den Fällen gilt K^e mod N = K.

Man könnte also 3 Zeichen (je 5 Bit) aus einem kleinen Alphabet in 15 Bit reinquetschen. Oder 2 7-bittige ASCII-Zeichen. Oder ein Oktett (8 bit) mit 7 zufälligen Bits zwecks Verschleierung auffüllen ("encryption padding").

miri schrieb:

Also diese Übung, die Du mir reingestellt hattest. Sollte ich die vielleicht erstmal zu ende machen?

Würde so die Verschlüsselung dann auch funktionieren? Na ich mach erst einmal die zweite Aufgabe von vorhin....sofern ich es heute noch schaffe.

Ich weiß gerade nicht, welche Übungen/Aufgaben Du meinst.

Gruß,
SP

miri

Nimm mal an, dein öffentlicher Schlüssel wäre 6499 und 23.
Wie würdest du die Zahl 25 verschlüsseln?

Wenn du obige Frage beantwortet hast, die nächste Frage: Wie würdest du die Zahlen 25 22 13 17 verschlüsseln?

Wenn du obige Frage beantwortet hast: Gibt es eine bijektive Abbildung von Zeichenfolgen auf Zahlenfolgen?

Wenn du obige Frage beantwortet hast: Wo liegt jetzt noch dein Problem?

Wenn du obige Fragen beantwortet hast: Der geheime Schlüssel ist 6499 und 551. Kommen wieder die richtigen Werte raus, wenn du entschlüsselst?

Wenn du obige Fragen beantwortet hast: Gib eine Möglichkeit an, wie ich das Schlüsselpaar erzeugt haben könnte.

Zusatzaufgabe: Angenommen ich hätte dir den geheimen Schlüssel nicht verraten, wie hättest du ihn trotzdem finden können? Bist du in der Lage mir einen geheimen Schlüssel zu 667 und 13 zu nennen?

Ich meinte diese Aufgaben.

Ok ich denke einmal weiter über mein Programm nach und werde es einmal ordnen.

Kann ich mich, wenn ich weiterhin Probleme habe nocheinmal melden?

miri

Hallo

ich bin also gerade am ordnen meines Codes nach dem was vorgeschlagen wurde:

Wäre es nicht viel praktischer wenn Du es so machtest:

* Klasse für öffentlichen RSA-Schlüssel "RSAPubKey"
* Klasse für Schlüsselpaar "RSAKeyPair" (hat eine getPubKey-Methode)
* freie Funktion zum Generieren eines zufälligen Schlüsselpaars (bekommt als Parameter "einen Zufallsgenerator" und die Schlüssellänge. Sie liefert ein RSAKeyPair Objekt zurück)
* freie Funktion zum Verschlüsseln (bekommt als Parameter einen RSAPubKey, eine Nachricht (Klartext) zB in Form von vector<unsigned char> und gibt einen vector<unsigned char> zurück als Chiffrat)
* freie Funktion zum Entschlüsseln (bekommt als Parameter ein RSAKeyPair, den "Chiffre-Text" (zB vector) und gibt den Klartext (zB vector) zurück.
* freie Funktionen zum Kodieren und Dekodieren von Textnachrichten (Zeichenkette <-> vector<unsigend char>)

Ich habe jetzt also zwei Klassen gebildet. Mein Problem steht nun darin, die Variablen der Klasse aus RSAPubkey und RSAKeyPair in meinen Memberfunktionen zu nutzen. Ich habe hierfür mal den Code reingestellt. Wahrscheinlich muss ich wohl Pointer anwenden? Ich weiß nur leider nicht, wie das funktioniert.
(Grad is mir aufgefallen was ich eigentlich für einen Quatsch gemacht habe...) Also ich will die Variablen aus der Klasse nutzen und nicht die, die ich in den Memberfunktionen da noch zusätzlich deklariert habe....grrr.
Könnt ihr mir da weiterhelfen?

Weiterhin musste ich feststellen, dass ich mit dem Datentyp "long" ja wirklich überhaupt nicht weit komme. Aber diese Baustelle würde ich erstmal noch nach hinten verschieben...oder muss man bei BigInt besonderes beachten?

Vielen herzlichen Dank!

//Klasse für PubKey
#pragma once

class RSAPubKey
{public:

	RSAPubKey (void);
	~RSAPubKey (void);

	void PublicKey();

private:
	unsigned long p, q, n;

};

//Klasse für KeyPair
#pragma once

class RSAKeyPair
{	
public:
	//Konstruktoren und Destruktoren
	RSAKeyPair (void);
	~RSAKeyPair (void);

	void twoKeyPairs();

private:
	unsigned long phi, e, d;

//RSA.cpp

#include <iostream>
#include "RSAPubKey.h"
#include "RSAKeyPair.h"

using namespace std;

RSAPubKey::RSAPubKey(void)
{}

RSAPubKey::~RSAPubKey(void)
{}

//Primzahlen einlesen und n erzeugen

void RSAPubKey::PublicKey()
{
	unsigned long n, p, q;
	cout << "Generate two primes" << endl;
	cout << "Please insert the first number:" << endl;
	cin >> p;
	cout << "Please insert the second number:" << endl;
	cin >> q;

	n=p*q;

	cout << n << endl;
}

RSAKeyPair::RSAKeyPair(void)
{}

RSAKeyPair::~RSAKeyPair(void)
{}

void RSAKeyPair::twoKeyPairs()
{
	unsigned long phi, d, e, p, q;

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

	cout << phi << endl;
}

Sebastian Pizer

Hier ein paar Dinge, die mir aufgefallen sind:

Dein RSAPubKey enthält p, q und n. Du verrätst also die Faktorisierung von n und verschweigst den öffentlichen Exponenten. Dein RSAPubKey sollte nur n und e enthalten.
Die Idee von RSAKeyPair war es, alle Schlüsselinformationen zu speichern, die man braucht, um (1) Nachrichten entschlüsseln zu können und (2) den "öffentlichen" Teil zu extrahieren. Um's einfach zu machen: n,e,d
Du brauchst hier nicht leere Konstruktoren und Destruktoren definieren. Ich wüsste auch nicht, wozu diese Klassen Elementfunktionen bräuchten. Die Schlüsselerzeugung kannst Du als freie Funktion implementiereun, die einfach ein RSAKeyPair zurück gibt.
Vielleicht lässt Du auch die Datei-Ein/Ausgabe u. (De-)Kodierung der Nachrichten sein und arbeitest direkt mit vom Benutzer eingegebenen Zahlen. Wenn das geschafft ist, kannst Du ja immer noch das Programm erweitern.

Möglicher Ansatz:

(rsa.hpp)

#ifndef RSA_HEADER_INCLUDED
#define RSA_HEADER_INCLUDED

// Typ-Alias für lange Ganzzahlen. Der Typ "unsigned long"
// kann später durch einen "BigInt" einer entsprechenden
// Bibliothek ersetzt werden.
typedef unsigned long mega_uint;

// berechnet d mit e*d = 1 mod phi
mega_uint inverse(mega_uint e, mega_uint phi);

// fuehrt die binaere Exponentiation inklusive
// Reduktion modulo "modn" durch
mega_uint pow_mod(
    mega_uint base,
    mega_uint power,
    mega_uint modn);

// Oeffentlicher RSA Schluessel
struct RSAPubKey
{
  mega_uint n, e;
};

// RSA Schluesselpaar
struct RSAKeyPair : RSAPubKey  // erbt n und e von RSAPubKey
{
  mega_uint d; // geheimer Exponent
};

// fragt Benutzer nach p, q, e und berechnet n=p*q und
// d nach dem erweiterten Euklid'schen Algorithmus
RSAKeyPair keyFromUser();

inline mega_uint RSAencrypt(
    RSAPubKey const& pubk,
    mega_uint plaintext)
{
  return pow_mod(plaintext,pubk.e,pubk.n);
}

inline mega_uint RSAdecrypt(
    RSAKeyPair const& privk,
    mega_uint ciphertext)
{
  return pow_mod(ciphertext,privk.d,privk.n);
}

#endif  /* RSA_HEADER_INCLUDED Include Guard */

(rsa.cpp)

#include <iostream>
#include "rsa.hpp"

mega_uint inverse(mega_uint e, mega_uint phi)
{
  ... // erweiterter Euklid'scher Algorithmus
}

RSAKeyPair keyFromUser()
{
  RSAKeyPair key;
  ... // Benutzer nach p, q, e fragen, key.e setzen
  key.n = p*q;
  key.d = inverse( key.e , (p-1)*(q-1) );
  return key;
}

mega_uint pow_mod(
    mega_uint base,
    mega_uint power,
    mega_uint modulus)
{
  ...
}

Gruß,
SP

SeppJ

Nimm einfach die zusätzlichen Variablendeklarationen aus der Implementierung deiner Funktionen.

miri

Hallo Sebastian,

vielen Dank erstmal für Deine Mühen!

Bei dem .hpp Code komme ich also bis zur Zeile 34 mit. Danach haperts ein wenig. In dem .cpp Code verstehe ich den Code von Zeile 9 bis 16 nicht.
Also irgendwie kenne ich einen solchen Aufruf

RSAKeyPair keyFromUser()

gar nicht. Und aus dem Rest dieser Funktion werde ich nicht schlau.

Irgendwie wird mir grad ein wenig schlecht.. Bin grad völlig durcheinander.

Könntest Du mir bitte erklären, was Du dort gemacht hast

In Zeile 18 wollte ich noch kurz auf einen kleinen Fehler hinweisen: statt lange_ganzzahl muss dort mega_uint stehen.

Danke und Gruß von Mirjam

Sebastian Pizer

miri schrieb:

Bei dem .hpp Code komme ich also bis zur Zeile 34 mit. Danach haperts ein wenig.

Aha. Das sind ganz normale Funktionsdefinitionen, bei denen ein inline vorangestellt wurde. Wenn Du inline nicht kennst, kannst Du das genauso wie bei den anderen Funktionen machen: Deklarieren in der Header-Datei und Definieren in einer cpp-Datei.

miri schrieb:

In dem .cpp Code verstehe ich den Code von Zeile 9 bis 16 nicht. Also irgendwie kenne ich einen solchen Aufruf gar nicht.

RSAKeyPair keyFromUser()

Das ist kein Aufruf. Das ist der Anfang einer Funktionsdefinition. Name der Funktion ist "keyFromUser" und der Rückgabewert ist vom Typ "RSAKeyPair".

miri schrieb:

Und aus dem Rest dieser Funktion werde ich nicht schlau.
Irgendwie wird mir grad ein wenig schlecht.. Bin grad völlig durcheinander.

Arschbacken zusammenkneifen und durch! :p

miri schrieb:

In Zeile 18 wollte ich noch kurz auf einen kleinen Fehler hinweisen: statt lange_ganzzahl muss dort mega_uint stehen.

Danke! Hast recht. Hab's jetzt geändert.

Gruß,
SP