3. Primzahlen und RSA Code

Primzahlen und RSA Code

  • M

    Hallo!

    Ich habe mir ein Thema für eine Belegarbeit in C++ ausgwählt. Wie der Titel dieses Threads schon andeutet, möchte ich einen Text mittels RSA-Code verschlüsseln.

    Leider habe ich mich nun ein wenig festgefahren-meine Grundkenntnisse reichen für die folgenden Schritte denke ich einfach noch nicht aus.

    Ich habe meinen Programmcode mit angefügt. Der Code ist mittels Klassen, Memberfunktionen und Objekten geschrieben.

    Mein Problem besteht jetzt darin:

    Wie verschlüssele ich den Text mit den erzeugten Code-Zahlen? Ich habe mir das so gedacht, dass ich einen Text von der Eingabe einlese (bzw. filestream) und in ein Array, oder Container oder Vektor packe und jeweils die Zeichen in der Reihenfolge wie sie drin stehen einzeln verschlüssele.

    Ist dieser Gedankengang richtig?

    [//test_primzahl.cpp:

    #include <iostream>
    #include "RSA.h"

    using namespace std;

    //hier werden die jeweiligen memberfunktionen aufgerufen

    int main()
    {
    RSA generate;

    //mein erster versuch einen text in ascii einzulesen...an dieser stelle muss nun angesetzt werden:-(

    generate.CONVERT_TO_ASCII();

    //hier soll ein zahlenbereich eingegeben werden, in dem primzahlen generiert werden sollen

    generate.PRIME_GENERATE();

    //danach soll der benutzer zwei aus dem zahlenbereich generierte primzahlen eingeben, die zahlen werden noch einmal auf //primeigenschaft geprüft, falls der benutzer einen fehler gemacht hat

    generate.PRIME_TEST();

    //hier werden die argumente des rsa codes erzeugt

    generate.RSA_CODE();

    return 0;
    }

    //RSA.cpp:

    #include <iostream>
    #include <math.h>
    #include <iomanip>
    #include <ctime>
    #include <string>
    #include "RSA.h"

    using namespace std;

    //Konstruktor
    RSA::RSA(void)
    {}
    //Destruktor
    RSA::~RSA(void)
    {}

    //ASCII-Umwandlung in dezimal

    int RSA::CONVERT_TO_ASCII()
    {

    cout << "please enter a word" << endl;
    string input;
    getline(cin, input);

    for(int i=0; i<input.length(); i++)
    {
    cout<<int(input.at(i))<<" ";
    }
    return 0;
    }

    //Boolsche Anweisungen zur Bestimmung ob eine Zahl eine Primzahl ist oder nicht nach folgender Vorschrift:
    //1 ist keine Primzahl (return false)
    //2 ist eine Primzahl (return true)
    //wenn kein Rest bei der Teilung von der Zahl und 2 besteht, dann ist die Zahl keine Primzahl (return false)

    bool RSA::prime(double a)
    {
    //switch (a)
    //{
    //case 1: return false;
    // break;
    //case 2: return true;
    // break;
    //}
    if (a==1) return false;
    if (a==2) return true;

    double false_1= fmod(a,2);
    if (false_1==0) return false;

    double s = sqrt(a);

    //Schleifendurchlauf von 3 bis zur Wurzel der Zahl, die Zahl wird dabei im Schleifendurchlauf immer um 2 erhöht, da gerade Zahlen //niemals Primzahlen sein können

    for(int i = 3; i <= s; i+=2)
    {
    double false_2=fmod(a,i);
    if (false_2==0) return false;
    }

    //Falls kein false eingetreten ist, dann handelt es sich bei der Zahl um eine Primzahl (return true)

    return(true);
    }

    //Primzahlgenerator

    void RSA::PRIME_GENERATE()
    {
    double range_of_number_small;
    double range_of_number_big;
    cout << "Please insert a range of number!" << endl << "first number:" << endl;
    cin >> range_of_number_small;
    cout << "second number:" << endl;
    cin >> range_of_number_big;

    for(int i=range_of_number_small; i<=range_of_number_big;i++)
    {
    if (prime(i)==true)
    {
    cout << i << " ,";
    }

    void RSA::PRIME_TEST()
    {
    cout << "Generate two primes" << endl;
    cout << "Please insert the first number:" << endl;
    cin >> p;
    cout << "Please insert the second number:" << endl;
    cin >> q;
    cout << endl;

    if (prime(p) && prime(q))
    cout << fixed << setprecision(0) << p << " and " << q << " are prime " << endl;

    else if (prime(p))
    cout << fixed << setprecision(0) << p << " is prime and " << q << " isn't prime " << endl;

    else if (prime(q))
    cout << fixed << setprecision(0) << p << " isn't prime and " << q << " is prime" << endl;

    else
    cout << fixed << setprecision(0) << p << " and " << q << " aren't prime " << endl;

    //hier muss noch eine Unterbrechung erfolgen, für die einzelnen "sinnlosen" Fälle, sollte das Programm nicht mehr weiter laufen

    }

    void RSA::RSA_CODE()
    {
    //rsa-modul "n" aus p&q berechnen
    n=p*q;
    cout << n << endl;

    //eulersche-funktion "phi" berechnen
    phi=(p-1)*(q-1);

    cout << endl;
    cout << endl << "the numerical value of the euler function is now known as: " << phi << endl;
    cout << endl;
    cout << endl <<"Please choose a public exponent of the following numbers: " << endl;
    cout << endl;

    srand (time(0));

    //eigentlich muss "e" mittels ggt ermittelt werden...an dieser stelle besteht-also auch noch eine baustelle....

    for(int i=0; i<100; i++)
    {
    double erste_mischung = fmod(rand(),phi)+1;
    erste_mischung = e;
    e = fmod(rand(),phi)+1;
    cout << e << ", ";
    }

    cout << endl << "Insert the number you choosed:" << endl;
    cin >> e;

    cout << endl << "the public key exponent is now known as: " << e << endl;

    d = (1+phi)/e;

    cout << endl << "the privat key exponent is now known as: " << d << endl;
    }

    //RSA.h:

    #pragma once

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

    bool prime(double a);
    void PRIME_GENERATE (void);
    void PRIME_TEST ();
    void RSA_CODE ();
    int CONVERT_TO_ASCII();
    private:
    double p, q, n, d, phi, e;
    };

    }]

    Vielen, vielen Dank für jede Antwort. Ihr würdet mir wirklich sehr helfen:-)

    0
  • Mod

    miri schrieb:

    Wie verschlüssele ich den Text mit den erzeugten Code-Zahlen? Ich habe mir das so gedacht, dass ich einen Text von der Eingabe einlese (bzw. filestream) und in ein Array, oder Container oder Vektor packe und jeweils die Zeichen in der Reihenfolge wie sie drin stehen einzeln verschlüssele.

    Ist dieser Gedankengang richtig?

    Jupp, so macht man das.

    Ob dein Code was taugt, kann ich nicht sagen, weil ich mir das nicht durchlesen will, wenn das so komisch formatiert ist. Benutze die cpp Tags (der Button links unter den Smileys) zum formatieren von Code.

    Falls dein Programm jedoch nicht als reine Demonstration gedacht ist, sondern einen realistischen Fall nachbilden soll, musst du dir noch eine Möglichkeit suchen, mit sehr großen Zahlen zu rechnen. Denn von Haus aus, kann dein Computer nur mit Zahlen bis ca 10^23 umgehen. Je nach System auch mehr oder weniger, aber auf jeden Fall zu wenig für realistische Verschlüsselung. Sowas kann man mit moderatem Aufwand selber schreiben oder eine der unzähligen fertigen Lösungen verwenden.

    0
  • K

    Das Ganze ist ein Ganzzahlproblem. Die Verwendung von double ist grundsaetzlich falsch.

    0
  • ?

    Entschuldigung, dass ich den Code nicht gleich formatiert habe. Ich wusste nicht, wie das geht.

    Wäre es vielleicht möglich, dass ihr euch den Code jetzt durchlest?

    Wie würde ich das denn jetzt speziell machen, den eingelesenen Text mit den erzeugten CODE-Schlüsseln zu verschlüsseln? Also ich weiß jetzt nicht so richtig wie ich das mit dem Array- Container- Vector oder ähnliches schreiben soll.

    Der Beleg soll also auch nicht irgendeinem Geheimdienst zur Verfügung gestellt werden;-). Weiterhin studiere ich Master Maschinenbau und kein Informatik. Von daher reicht es aus den Code in den normalen Grenzen eines normalen Computers zu schreiben.

    Dass ich mit double falsch liege habe ich mir schon gedacht. Ich glaube mein Problem damals war, dass ich aus Integer keine Wurzel ziehen kann.

    Hat hierzu jemand einen Vorschlag?

    Vielen herzlichen Dank und Gruß von Miri

    //test_primzahl.cpp:

#include <iostream>
#include "RSA.h"

using namespace std;

//hier werden die jeweiligen memberfunktionen aufgerufen

int main()
{
RSA generate;

//mein erster versuch einen text in ascii einzulesen...an dieser stelle muss nun angesetzt werden:-(

generate.CONVERT_TO_ASCII();

//hier soll ein zahlenbereich eingegeben werden, in dem primzahlen generiert werden sollen

generate.PRIME_GENERATE();

//danach soll der benutzer zwei aus dem zahlenbereich generierte primzahlen eingeben, die zahlen werden noch einmal auf //primeigenschaft geprüft, falls der benutzer einen fehler gemacht hat

generate.PRIME_TEST();

//hier werden die argumente des rsa codes erzeugt

generate.RSA_CODE();

return 0;
}

//RSA.cpp:

#include <iostream>
#include <math.h>
#include <iomanip>
#include <ctime>
#include <string>
#include "RSA.h"

using namespace std;

//Konstruktor
RSA::RSA(void)
{}
//Destruktor
RSA::~RSA(void)
{}

//ASCII-Umwandlung in dezimal

int RSA::CONVERT_TO_ASCII()
{

cout << "please enter a word" << endl;
string input;
getline(cin, input);

for(int i=0; i<input.length(); i++)
{
cout<<int(input.at(i))<<" ";
}
return 0;
}

//Boolsche Anweisungen zur Bestimmung ob eine Zahl eine Primzahl ist oder nicht nach folgender Vorschrift:
//1 ist keine Primzahl (return false)
//2 ist eine Primzahl (return true)
//wenn kein Rest bei der Teilung von der Zahl und 2 besteht, dann ist die Zahl keine Primzahl (return false)

bool RSA::prime(double a)
{
//switch (a)
//{
//case 1: return false;
// break;
//case 2: return true;
// break;
//}
if (a==1) return false;
if (a==2) return true;

double false_1= fmod(a,2);
if (false_1==0) return false;

double s = sqrt(a);

//Schleifendurchlauf von 3 bis zur Wurzel der Zahl, die Zahl wird dabei im Schleifendurchlauf immer um 2 erhöht, da gerade Zahlen //niemals Primzahlen sein können

for(int i = 3; i <= s; i+=2)
{
double false_2=fmod(a,i);
if (false_2==0) return false;
}

//Falls kein false eingetreten ist, dann handelt es sich bei der Zahl um eine Primzahl (return true)

return(true);
}

//Primzahlgenerator

void RSA::PRIME_GENERATE()
{
double range_of_number_small;
double range_of_number_big;
cout << "Please insert a range of number!" << endl << "first number:" << endl;
cin >> range_of_number_small;
cout << "second number:" << endl;
cin >> range_of_number_big;

for(int i=range_of_number_small; i<=range_of_number_big;i++)
{
if (prime(i)==true)
{
cout << i << " ,";
}

void RSA::PRIME_TEST()
{
cout << "Generate two primes" << endl;
cout << "Please insert the first number:" << endl;
cin >> p;
cout << "Please insert the second number:" << endl;
cin >> q;
cout << endl;

if (prime(p) && prime(q))
cout << fixed << setprecision(0) << p << " and " << q << " are prime " << endl;

else if (prime(p))
cout << fixed << setprecision(0) << p << " is prime and " << q << " isn't prime " << endl;

else if (prime(q))
cout << fixed << setprecision(0) << p << " isn't prime and " << q << " is prime" << endl;

else
cout << fixed << setprecision(0) << p << " and " << q << " aren't prime " << endl;

//hier muss noch eine Unterbrechung erfolgen, für die einzelnen "sinnlosen" Fälle, sollte das Programm nicht mehr weiter laufen

}

void RSA::RSA_CODE()
{
//rsa-modul "n" aus p&q berechnen
n=p*q;
cout << n << endl;

//eulersche-funktion "phi" berechnen
phi=(p-1)*(q-1);

cout << endl;
cout << endl << "the numerical value of the euler function is now known as: " << phi << endl;
cout << endl;
cout << endl <<"Please choose a public exponent of the following numbers: " << endl;
cout << endl;

srand (time(0));

//eigentlich muss "e" mittels ggt ermittelt werden...an dieser stelle besteht-also auch noch eine baustelle....

for(int i=0; i<100; i++)
{
double erste_mischung = fmod(rand(),phi)+1;
erste_mischung = e;
e = fmod(rand(),phi)+1;
cout << e << ", ";
}

cout << endl << "Insert the number you choosed:" << endl;
cin >> e;

cout << endl << "the public key exponent is now known as: " << e << endl;

d = (1+phi)/e;

cout << endl << "the privat key exponent is now known as: " << d << endl;
}

//RSA.h:

#pragma once

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

bool prime(double a);
void PRIME_GENERATE (void);
void PRIME_TEST ();
void RSA_CODE ();
int CONVERT_TO_ASCII();
private:
double p, q, n, d, phi, e;
};

}
    0
  • S

    "Nachrichten", die mit RSA verschlüsselt werden sollen, können immer nur höchstens genau so lang sein, wie der Modulus N. Der Schlüssel muss also eine gewisse Länge aufweisen, damit Du eine bestimmte Nachricht verschlüsseln kannst. Auch aus Sicherheitsgründen wählt man einen Schlüssel so aus, dass N mindestens 1024 Bit besitzt.

    double ist hier nicht zu gebrauchen. Du brauchst einen Typen, der sehr große Ganzzahlen "lückenlos" darstellen kann und bei +,-,* exakt rechnet. double kann das nicht. Dafür kann man Bibliotheken wie GMP einsetzen.

    Dann brauchst Du noch einen vernünftigen Primzahltest. Wenn Du einen 1024-bittigen RSA-Schlüssel erzeugen willst, geht vorher die Welt unter, als dass Dein Primzahltest zu einem Ergebnis kommt.

    Typischerweise verschlüsselt man lange Nachrichten mit einem symmetrischen Verfahren und einem dafür zufällig gewählten Schlüssel. Dieser Schlüssel kann dann als "Nachricht" für RSA verwendet werden. Übertragen wird dann der mit RSA verschlüsselte Schlüssel und die symmetrisch verschlüsselte Nachricht. Das funktioniert dann auch viel schneller.

    Wie genau eine Nachricht zu einer Zahl für RSA umgewandelt wird, ist auch wichtig. Dafür gibt es verschiedene Verfahren. Zum Beispiel OAEP (optimal asymmetric encryption padding).

    Wenn Du das Projekt also wirklich in C++ machen willst, würde ich mir eine gute Bibliothek suchen, die eine Klasse für große Ganzahlen bereitstellt und idealerweise sogar schon Primzahlen erzeugen kann, oder zumindest einen guten Primzahltest mitbringt.

    Gruß,
    SP

    0
  • ?

    Halle Sebastian,

    vielen Dank für die Antwort.

    Ich werde mich in den nächsten Tagen damit einmal beschäftigen. Ich meine taugt mein bisheriger Code bisher überhaupt etwas? Oder kann ich den wegschmeißen? Wie gesagt ist es nur ein Beleg und ich bin kein Informatiker sondern Maschinenbauer. Sind Deine Vorschläge denn schwierig umzusetzen? Oder muss ich einfach nur eine neue Bibliothek einbinden, so dass ich große Integer rechnen kann? Ist denn mein Primzahltest korrekt (bis auf das mit dem double)?

    Viele Fragen-tut mir leid:-(

    Gruß von Mirjam

    0
  • Mod

    miri3 schrieb:

    Halle Sebastian,

    vielen Dank für die Antwort.

    Ich werde mich in den nächsten Tagen damit einmal beschäftigen. Ich meine taugt mein bisheriger Code bisher überhaupt etwas? Oder kann ich den wegschmeißen?

    Ich sag mal so: Man sieht, dass du nicht viel programmierst, aber dafür ist es nicht schlecht. Da du aber einige Sachen gemacht hast, die dich im weiteren nur behindern würden, würde ich an deiner Stelle zumindest teilweise neuschreiben.

    Wie gesagt ist es nur ein Beleg und ich bin kein Informatiker sondern Maschinenbauer. Sind Deine Vorschläge denn schwierig umzusetzen? Oder muss ich einfach nur eine neue Bibliothek einbinden, so dass ich große Integer rechnen kann?

    Du musst eine Bibliothek einbinden, deren Dokumentation verstehen und sie richtig benutzen. Je nachdem wieviel von dem Algorithmus du auslagerst, wäre es dann natürlich nicht mehr wirklich deine Arbeit zu RSA sondern nur eine Demonstration, dass du Bibliotheken benutzen kannst.

    Ist denn mein Primzahltest korrekt (bis auf das mit dem double)?

    Er ist zwar korrekt, aber wie Sebastian Pizer schon sagt unendlich umständlich. Selbst mit naiven Mitteln könnte man ihn um Größenordnungen schneller machen. Für echtes RSA reichen solch einfache Algorithmen aber nicht, schließlich reden wir hier von Zahlen um die 10^300. Da würdest du länger als die bisherige Lebensdauer des Universums rechnen. Zum Glück kennt die Mathemtatik aber auch fortschrittlichere Primzahltests, mir fällt aber gerade leider nicht ein wie die heißen. In deinem Lieblingsbuch zu Zahlentheorie oder in einer Beschreibung des RSA Verfahrens wirst du aber bestimmt fündig.

    P.S.: Dass dein Primzahltest so lange dauert liegt natürlich daran, dass du versuchst deine Zahl zu faktorisieren und wenn du eine Primzahlzerlegung findest, war es wohl keine Primzahl. Dies ist aber gerade das was RSA so sicher macht: Das Zerlegen großer Zahlen in ihre Primfaktoren ist extrem schierig.

    0
  • M

    Er ist zwar korrekt, aber wie Sebastian Pizer schon sagt unendlich umständlich. Selbst mit naiven Mitteln könnte man ihn um Größenordnungen schneller machen. Für echtes RSA reichen solch einfache Algorithmen aber nicht, schließlich reden wir hier von Zahlen um die 10^300. Da würdest du länger als die bisherige Lebensdauer des Universums rechnen.

    Ich muss mal ganz ehrlich sagen, dass ich froh war überhaupt einen Primzahltest programmiert haben zu können. Das wirft mich jetzt grad ein wenig zurück (auch in meiner Motivation).:-(

    Wäre es vll möglich, dass ihr mir ein paar Tipps gebt, wie ich nun von meinen Code Zahlen zu der eigentlichen Verschlüsselung komme? Dann hätte ich zumindest erstmal einen vollständigen Code, den ich dann nach den von euch schon genannten Kriterien optimieren würde.

    Könnt ihr mir bitte ein Beispiel geben, was mir weiterhilft bei der Verschlüsselung? Also ich meine damit, wie weise ich dem meinetwegen eingegebenen String die erzeugten Code-Zahlen zu und wie werden sie dann verschlüsselt?

    Vielen Dank:-)

    Gruß von Mirjam

    0
  • Mod

    Was erwartest du denn als Hilfe? RSA ist wahrscheinlich einer der bestdokumentierten Algorithmen im Netz. Auf Wikipedia gibt es ausführliche Beispiele und weiterführende Links, sowohl zur Primzahlgenerierung als auch zur eigentlichen Anwendung der Verschlüsselung. Ich glaube nicht, dass hier irgendwer diese Grundlagen besser vermitteln kann als die zahlreichen Anleitungen die es schon gibt.

    0
  • M

    Also ich habe wirklich schon viel "gegoogelt" und mir auch Literatur aus der Uni Bibliothek ausgeliehen. Das Problem ist also nicht, dass ich den RSA Code nicht verstehe-ich weiß nicht wie ich es programmieren soll (verständliche C++ Algorithmen hierzu sind auch rar im Netz). Den bisherigen Code habe ich ja reingestellt und an der Stelle an der ich nun die "Eingabe" verschlüsseln soll komme ich einfach nicht weiter.

    Ich weiß, dass folgender Wunsch nicht so gerne erfüllt wird. Trotzdem frage ich einmal.

    Könntet ihr mir einmal einen Beispiel-Code-beispielsweise mit einem Buchstaben, den man mittels RSA verschlüsselt vorschlagen? Also eben genau an der Stelle, an der ich den ASCI einlese.

    Ich weiß eben wirklich nicht so richtig, wie ich meine erzeugten RSA-Zahlen zur Verschlüsselung nutze. Geschweige denn, den ASCI in vierer Blöcke zusammenfasse-so wie es bei Wikipedia steht...:-(

    Dankeschön und Gruß von

    Mirjam

    0
  • ?

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

    0
  • S

    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

    0
  • M

    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

    0
  • Mod

    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?

    0
  • S

    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

    0
  • M

    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;

}
    0
  • S

    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

    0
  • Mod

    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.

    0
  • M

    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

    0
  • S

    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

    0
  • ?

    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 😕 😞

    0
Anmelden zum Antworten