Stefan-Marr.de

3. Rekursion

lat.: recurre = zurücklaufen, die Wiederholung durch Schachtelung.

Definition:

Wenn eine Programmmodul im Anweisungsteil einen Selbstaufruf enthält, spricht man von einer linearen Rekursion. Bei mehreren Selbstaufrufen spricht man von Baumrekursion.

• Rekursionsfall - rekursive Abstieg Der Rekursionsfall bzw. der rekursive Abstieg sind gekennzeichnet durch den Selbstaufruf des Programmmoduls.
• Rekursionsanfang - direkter Fall Der Rekursionsanfang ist erreicht, bzw. der direkte Fall tritt ein, wenn der rekursive Abstieg durch das erfüllen einer Bedingung beendet ist.
• Rekursiver Aufstieg Der rekursive Aufstieg ist die letzte Phase der Rekursion, hier werden alle Anweisungen nach dem Selbstaufruf des Programmmoduls ausgeführt. Dies geschieht in umgekehrter Aufrufreihenfolge. Wenn der Selbstaufruf die letzte Anweisung ist, nennt man dies endrekursiv.

4. Kryptographie

Begriffe:

Authentifizierung: Wenn jemand Angaben über seine Identität macht, muss er einen Beweis angeben, dass er wirklich der ist als den er sich ausgibt.

Autorisierung: In Abhängigkeit der Identität und Authentifizierung eines Dienstbenutzers, wir der Zugriff auf Informationen gestattet oder verweigert.

Vertraulichkeit: Man muss sicher sein, dass die Daten, die übertragen werden sollen, nur von den gewünschten Personen gelesen werden können und nicht von Dritten. Um dies zu garantieren werden Daten verschlüsselt.

Verbindlichkeit: Beispielsweise beim elektronischen Handel muss eine Zusage absolut verbindlich sein, damit sich die Vertragspartner darauf verlassen können. Dies muss also in den Sicherheitssystemen berücksichtigt werden.

Integrität: Die Nachrichtenintegrität ist gesichert, wenn kein Dritter den Inhalt einer Nachricht verändern kann und sie im Namen des Absenders weiter schicken kann.

Symmetrische Kryptosysteme

Auch Private-Key-Verfahren genannt. Die Daten werden mit einem geheimen Schlüssel kodiert und können nur mit diesem Schlüssel dekodiert werden. Problematisch ist der Austausch des Schlüssels, da dies auf einem sicheren Weg passieren muss. Dies ist jedoch aufwendig und oft teuer, da hier oft nur die persönliche Übermittlung sicher ist.

Verfahren: DES, Dreifach-DES, IDEA, Vigenere, AES, Cäsar-Code

Asymmetrische Kryptosysteme

Auch Public-Key-Verfahren genannt. Hier werden zwei Schlüssel benötigt ein öffentlicher Schlüssel und ein privater Schlüssel. Dieses Schlüsselpaar hat die Eigenschaft, dass man die privaten Schlüssel nicht aus dem öffentlichen Schlüssel gewinnen kann. Die öffentlichen Schlüssel werden allgemein zugänglich Aufbewahrt z.B. in einer öffentlichen Datenbank, die privaten müssen jedoch geschützt nur für den Besitzer zugänglich aufbewahrt werden. Eine Nachricht wird nun mit dem öffentlichen Schlüssel des Empfängers verschlüsselt und kann nur noch mit dem privaten Schlüssel des Empfängers entschlüsselt werden.

Verfahren: RSA, ElGamal, elliptic curve

RSA

Bei diesem Verfahren, wird der Klartext in Zahlenblöcken dargestellt. Das Schlüsselpaar wird mittels großen Primzahlen (100-200 Stellen) p und q hergestellt. Man berechnet das Produkt n=pq und F(n)=(p-1)(q-1). Nun wird ein Schlüssel e für die spätre Verschlüsselung gewählt. Der größte gemeinsame Teiler von e und F(n) sollte 1 sein (ggT(e,F(n)=1). Damit wird d berechnet, was später zur Entschlüsselung benötigt wird. e*d mod F(n) = 1 bzw. d = (i * F(n)+1)/e Für d und n gilt ebenfalls, das der ggT 1 ist (ggT(d,n)=1). Die Primzahlen sind jetzt nicht mehr notwendig, sie müssen jedoch geheim bleiben. Der öffentliche Schlüssel ist Ö(e,n) und der geheime Schlüssel ist G(d,n). Die Sicherheit von RSA beruht auf dem mathematischen Problem, die benutzten Primzahlen aus dem öffentlichen Schlüssel gewinnen zu können. Dies ist mit heutigen Verfahren nur sehr ineffizient möglich. Durch die Verwendung großen Primzahlen wird RSA sicher, aber auch bei der Ver- und Entschlüsselung langsamer als symmetrische Verfahren.

Verfahren:

Verschlüsseln:

• n = p g; F(n) = (p-1)(q-1)
• Text in Blöcke spalten
• V = ke mod n

Geheimen Schlüssel bestimmen:

• spezieller euklidscher Algorithmus A = b*C + R
  • den ersten Schritt also A = F(n); b = a; C = e
  • F(n) = a*e + R a ist ein Faktor und R der Rest
  • A = e; C = R
  • Für den zweiten Schritt ergibt sich also e = a2*R + R2
  • So lange der Rest nicht 1 ist das ganze wiederholen
• wenn der Rest 1 ist, umstellen nach 1 = e - a2*R und so lange den jeweiligen Rest ersetzen, bis man die Ausgangsgleichung umgestellt eingesetzt hat
• 1 = e - a2*R
• 1 = e - a2 * (F(n) - a*e)
• jetzt müssen die Klammern aufgelöst werden
• 1 = e - a2F(n) + a2ae = (a2a+1)e - a2*F(n)
• d wäre also a2*a+1