B.Sc./M.Sc. Elektrotechnik an der RWTH

hi leute,

bei Review Exercise habe ich ein paare Fragen:

1)beim Problem 3 (a)

man muss beweisen: 3 is not a strong witness for the compositeness of q.

in der Definition 6.4 (S.45 Skript) steht: "a is a strong witness for the compositeness of n if a^q # 1 (mod n) mit n = 1+q.2^k"

d.h. in dieser Aufgabe muss man beweisen dass 3^87 mod 349 = 1 um zu zeigen 3 is not a strong witness.

Aber in der Lösung hat man gefunden: 3^87 mod 349 = -1 # 1 --> nach Definition 6.4: 3 is a strong witness --> widerspruch mit der Frage.

ich denke es muss ein Fehler im Aufgabenblatt sein oder keine Ahnung. was sagt ihr?

2)beim Problem 2 (a), wie kann man z.B. S1(1101) = 01 oder S1 (0111) = 00 finden?

3)beim Problem 2 (b), wie kann man the inverse permutation IP^-1 finden? gibt es eine Formel?

bitte hilf mir wenn ihr weisst. Vielen Dank!
mfg

Hi,

Frage 1:
Ich sehe da keinen Fehler in der Aufgabenstellung. Man soll zeigen, dass 3 keine "strong witness" ist. Dazu rechnet man die beiden Tests durch.
(i) a^(q) ≢ 1 (mod n)
--> 3^87 (mod 349) ≡ 348 ≡ -1 (mod 349)
Der erste Test wird also bestanden. Damit 3 eine strong witness ist, muss allerdings auch der zweite Test bestanden werden:
(ii) a(q^(2^i)) ≢ -1 (mod n) ∀i∈ {0, ... , k-1}
Da k=2, kann i hier nur 0 oder 1 sein. Um den zweiten Test zu bestehen, muss also folgendes gelten:
i=0: 3^(87) ≢ -1 (mod 349)
i=1: 3^(2*87) ≢ -1 (mod 349)
Für i=0 ist der linke Teil der Rechnung genau wie in (i), und da kam ja -1 raus. Also wird der zweite Test nicht bestanden und 3 "is not a strong witness". Es kann außerdem keine "strong witness" zu 349 geben, da diese Zahl ja prim ist (sonst würde RSA nicht funktionieren).

Frage 2:
In der Beschreibung steht doch eigtl. genau, wie das abläuft:
"The first two bits specify the row, the last two bits the column of the S-box."
S1(1101) bedeutet also: S-Box 1, Zeile (11)2, Reihe (01)2. Also die 4. Zeile und die 2. Spalte (wenn man bei 1 anfängt zu zählen). S1[4][2] = (1)10, in Binärschreibweise also (01)2. S(0111) heißt: Zeile 2, Spalte 4 von S2. Da steht die 00 drin.

Frage 3:
Schau dir IP an. Überleg dir für alle Zahlen, wo die nach der Anwendung von IP stehen. Z.b. das erste Bit steht nachher an 5. Stelle. Das zweite Bit wird an Stelle 6 geschoben usw. Das willst du in IP^(-1) rückgängig machen. Also muss an die erste Stelle von IP^(-1) die Zahl/Stelle, an der das erste Bit nach Anwendung von IP liegt. Das ist 5. Analog kommt an die zweite Stelle 6 usw..

gruß

jetzt bin ich klar. danke dir