3. Primzahlen und RSA Code

Primzahlen und RSA Code

  • S

    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.

    0
  • M

    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!

    0
  • Mod

    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.

    0
  • S

    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

    0
  • M

    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?

    0
  • M

    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;
}
    0
  • S

    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

    0
  • Mod

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

    0
  • M

    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

    0
  • S

    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

    0
  • M

    Arschbacken zusammenkneifen und durch! :p

    Ok aber nicht mehr heute 🙄 . Mein Kopf schmerzt und Informatik ist ja nun auch nicht das einzige Fach in dem ich was machen muss.

    Den Tipp, dass man auch Datentypen mit typedef festlegen kann fand ich übrigens sehr toll. Das erspart einem nachher ja wirklich so einiges, wenn man dann die BigInt einbinden will.

    Ok-für heute sage ich erstmal auf Wiedersehen und wünsche noch einen angenehmen Sonntag Abend.

    Ich melde mich sicherlich morgen wieder 😞 (wenn Du denn noch so viel Geduld hast)

    Gruß, Danke

    Mirjam 🙂

    0
Anmelden zum Antworten