HÜbung 3 und Modulare Arithmetik

Erich
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 17. Okt 2010 13:29

HÜbung 3 und Modulare Arithmetik

Beitrag von Erich »

Also beim Beweis für die 3a empfinde ich folgendes als nützlich:

1.) der Satz a^b mod n = ( a mod n )^b mod n

2.) die allgemein bekannten Potenzgesetzte.

Problem ist: keines von beiden kommt in den Folien aus der Vorlesung vor ( sind aber wie gesagt bereits bewiesen: 1.) im Mathe 1-Skript 2.) siehe z.B. Wikipedia ), also dürfen wir sie trotzdem benutzen, oder es so handhaben, wie in den Mathe-Grundlagenveranstaltungen: Wenn es nicht im Skript vorkommt, existiert es nicht ( sondern muss zumindest extra bewiesen werden )?

R_Egert
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 180
Registriert: 8. Sep 2009 23:27

Re: HÜbung 3 und Modulare Arithmetik

Beitrag von R_Egert »

Allgemein gültige Definitionen dürfen verwendet werden, auch wenn diese nicht ausdrücklich nochmals in Skript/Folien aufgezeigt werden^^. Sollten ganz extravagante Gegebenheiten verwendet werden, wäre eine Quellenangabe bestimmt nicht verkehrt, das sollte aber in dieser Aufgabe nicht nötig sein^^

Grüsse Rolf
Tutor:
  • Einführung in Trusted Systems WS11/12, WS12/13, WS13/14, WS14/15
  • GDI II SS11, SS12, SS13, SS14
  • Einführung in die Kryptographie WS14/15

-py-
Windoof-User
Windoof-User
Beiträge: 27
Registriert: 18. Mär 2011 00:27

Re: HÜbung 3 und Modulare Arithmetik

Beitrag von -py- »

Ich hab mal eine Frage zum Rechnen mit Kongruenzen. In der 2. VL-Einheit auf Folie 9 heißt es:

Wenn a ≡ \(a_1\) (mod n) und b ≡ \(b_1\) (mod n) gilt, gilt auch ab ≡ \(a_1b_1\) (mod n)

Daraus kann ich ja folgendes ableiten:

x ≡ y (mod n) => \(x^k\)\(y^k\) (mod n) für ganze k

Aber kann ich auch die umgekehrte Richtung implizieren? Also:

\(x^k\)\(y^k\) (mod n) => x ≡ y (mod n)


Ich bin mir nämlich nicht sicher, ob ich da nicht irgendwas übersehe, wodurch das nicht gehen würde. Andererseits fällt mir auch kein Gegenbeispiel ein, warum das nicht funktionieren sollte.

peter_
Neuling
Neuling
Beiträge: 6
Registriert: 15. Dez 2009 23:00

Re: HÜbung 3 und Modulare Arithmetik

Beitrag von peter_ »

Eine Frage zum Ablauf des Spiels:

Auf Folie ts-4 11 steht:
\(E(m) = (c_1, c_2) := (g^k, mh^k)\)

Heißt das, dass ich als Angreifer auch \(g^k\) kenne?
Ohne dass Wissen um \(g^k\) komme ich im Moment nur auf ~75 % Sicherheit das richtige \(m_i\) auszuwählen.

R_Egert
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 180
Registriert: 8. Sep 2009 23:27

Re: HÜbung 3 und Modulare Arithmetik

Beitrag von R_Egert »

Dieses Tupel ist dein Chiffrat was du vom "Richter" zurückbekommst^^ du siehst also \(c_1=g^k\) sowie \(c_2 = mh^k\)
Tutor:
  • Einführung in Trusted Systems WS11/12, WS12/13, WS13/14, WS14/15
  • GDI II SS11, SS12, SS13, SS14
  • Einführung in die Kryptographie WS14/15

peter_
Neuling
Neuling
Beiträge: 6
Registriert: 15. Dez 2009 23:00

Re: HÜbung 3 und Modulare Arithmetik

Beitrag von peter_ »

R_Egert hat geschrieben:Dieses Tupel ist dein Chiffrat was du vom "Richter" zurückbekommst^^ du siehst also \(c_1=g^k\) sowie \(c_2 = mh^k\)
Ok, das macht es natürlich um einiges einfacher. Ich dachte ich würde nur \(c_2 = mh^k\) bekommen :D
Danke.

Antworten

Zurück zu „Archiv“